Information Technology Reference
In-Depth Information
Definition 2 (Dominance).
Given two
α
-stable marriages, say
M
and
M
,
M
domi-
nates
M
if every man is married in
M
to more or equally preferred woman than in
M
and there is at least one man in
M
married to a more preferred woman than in
M
.
Example 6.
Let us consider the SMW shown in Example 5. We recall that
α
is
2
and
that the
α
-stable marriages of this problem are
M
1
=
{
(
m
1
,w
1
)
,
(
m
2
,w
2
)
}
and
M
2
=
{
(
m
1
,w
2
)
,
(
m
2
,w
1
)
}
. It is possible to see that:
-
M
2
does not dominate
M
1
since, for
m
1
,
M
1
(
m
1
)
>M
2
(
m
1
)
and
-
M
1
does not dominate
M
2
since, for
m
2
,
M
2
(
m
2
)
>M
1
(
m
2
)
.
We now discriminate among the
α
-stable marriages of an SMW, by considering the
preference values given by women and men to order pairs that differ for less than
α
.
In this paper we will consider a marriage optimal when the most popular men are as
happy as possible and they are married with their most popular best
α
-feasible women.
However, we could also consider a marriage optimal when the least popular men are as
happy as possible and they are married with their most popular best
α
-feasible women.
To compute a strict ordering on the men where the most popular men (resp., the most
popular women) are ranked first, we follow a reasoning similar to the one considered in
[15,17], that is, we apply a voting rule [1] to the preferences given by the women (resp.,
by the men). More precisely, such a voting rule takes in input the preference values
given by the women over the men (resp., given by the men over the women) and returns
a strict total order over the men (resp., women).
Definition 3 (Lex-male-Optimal).
Consider an SMW
P
, a natural number
α
, and a
voting rule
r
. Let us denote with
o
m
(resp.,
o
w
) the strict total order over the men
(resp., over the women) computed by applying
r
to the preference values that the women
give to the men (resp., the men give to the women). An
α
-stable marriage
M
is
lex-
male-optimal
w.r.t.
o
m
and
o
w
, if, for every other
α
-stable marriage
M
, the following
conditions hold:
-
there is a man
m
i
such that
M
(
m
i
)
o
w
M
(
m
i
)
,
-
for every man
m
j
≺
o
m
m
i
,
M
(
m
j
)
≤
M
(
m
j
)
.
Proposition 2.
Given an SMW
P
, a strict total ordering
o
m
(resp.,
o
w
) over the men
(resp., women),
-
there is a unique lex-male-optimal
α
-stable marriage w.r.t.
o
m
and
o
w
,say
L
.
-
L
may be different from the male-optimal stable marriage of
c
(
P
)
;
-
if
α
(
P
)
has a unique undominated weakly stable marriage, say
L
,then
L
coincides
with
L
,otherwise
L
is one of the undominated weakly stable marriages of
α
(
P
)
.
Example 7.
Let us consider the SMW,
P
, shown in Example 5. We have shown previ-
ously that this problem has two
α
-weakly stable marriages that are undominated. We
now want to discriminate among them by considering the lex-male-optimality notion.
Let us consider as voting rule the rule that takes in input the preference values given by
the women over the men (resp., by the men over the women) and returns a strict prefer-
ence ordering over the men (resp., women). This preference ordering is induced by the
