Information Technology Reference
In-Depth Information
Similarly, we can show that
I
α
(
P
)
I
α
(
P
)
, then there is a
pair (man,woman), say
(
m, w
)
,in
P
such that
m
prefers
w
to
w
by at least degree
α
and
w
prefers
m
to
m
by at least degree
α
. By definition of
α
(
P
)
,thismeansthat
m
prefers
w
to
w
and
w
prefers
m
to
m
in
α
(
P
)
and so
M
⊇
I
w
(
α
(
P
))
. In fact, if
M
∈
∈
I
w
(
α
(
P
))
, i.e.,
M
is not a
weakly stable marriage for
α
(
P
)
.
This means that, given an SMW
P
, every algorithm that is able to find a weakly stable
marriage for
α
(
P
)
provides an
α
-stable marriage for
P
.
Example 5.
Assume that
α
is
2
. Let us consider the following instance of an SMW, say
P
.
-
m
1
:
w
[3
1
>w
[2]
2
-
m
2
:
w
[4]
1
>w
[2]
2
,
-
w
1
:
m
[8
1
>m
[5
2
,
-
w
2
:
m
[3]
>m
[1
2
.
1
The SMP
α
(
P
)
is the following:
-
m
1
:
w
1
w
2
,
-
m
2
:
w
1
>w
2
,
-
w
1
:
m
1
>m
2
,
-
w
2
:
m
1
>m
2
.
The set of the
α
-stable marriages of
P
, that coincides with the set of the weakly
stable marriages of
α
(
P
)
, by Theorem 1, contains the following marriages:
M
1
=
{
(
m
1
,w
1
)
,
(
m
2
,w
2
)
}
and
M
2
=
{
(
m
1
,w
2
)
,
(
m
2
,w
1
)
}
.
On the other hand, not all stable marriage problems with partially ordered preferences
can be expressed as stable marriage problems with weighted preferences such that the
stable marriages in the two problems coincide. More precisely, given any SMP problem
P
, we would like to be able to generate a corresponding SMW problem
P
and a value
α
such that, in
P
, the weights of elements ordered in
P
differ more than
α
, while those
of elements that are incomparable in
P
differ less than
α
. Consider for example the case
of a partial order over six elements, defined as follows:
x
1
>x
2
>x
3
>x
4
>x
5
and
x
1
>y>x
5
. Then there is no way to choose a value
α
and a linearization of the partial
order such that the weights of
x
i
and
x
j
differ for at least
α
, for any i,j between 1 and
5, while at the same time the weight of
y
and each of the
x
i
's differ for less than
α
.
3.2
Dominance and Lex-Male-Optimality
We recall that in SMPs a weakly-stable marriage dominates another weakly-stable mar-
riage if men are happier (or equally happy) and there is at least a man that is strictly
happier. The same holds for
α
-stable marriages. As in SMPs there may be more than
one undominated weakly-stable marriage, in SMWs there may be more than one un-
dominated
α
-stable marriage.
