Information Technology Reference
In-Depth Information
stable marriage of
c
(
P
)
, since it considers the happiness of the men reordered according
to their links with the women, rather than according their single preferences.
This holds, for example, when we assume to have an SMW with preference values
that are all different and we consider the notion of link-maximal-stability.
Proposition 8.
Given an SMW
P
where the preference values are all different, the mar-
riage returned by algorithm
link-maximal-stable-GS
algorithm over
P
is link-maximal-
stable and it has the highest link.
5
Manipulation
In [18] Roth has shown that, when there are at least three men and three women, every
stable marriage procedure is manipulable, i.e., there is a profile where an agent, mis-
reporting his preferences, obtains a stable marriage which is better than or equal to the
one obtained by telling the truth. In stable marriage problems, agents can manipulate in
two ways: by changing the preference ordering [18], or by truncating the preference list
[5].
We now would like to check if agents have additional ways of manipulating in our
context, by changing only the preference weights, while preserving the preference or-
dering and not truncating the preference list.
In the following, we will call a
w-manipulation attempt
by an agent
a
the mis-
reporting of the weights in
a
's preferences which preserves the true preference ordering.
Also, we will say that a w-manipulation attempt of an agent
a
is
successful
if the re-
sulting marriage for
a
is better than or equal to the marriage obtained by using the true
preference weights of
a
, and that a stable marriage procedure is
w-manipulable
if there
is a profile with a successful w-manipulation attempt for an agent.
We will show that every stable marriage procedure which returns an
α
-stable mar-
riage, a link-additive, or a link-maximal stable marriage, is w-manipulable.
Theorem 3.
Let
α
be any natural number
>
1
. Every procedure which returns an
α
-
stable marriage is w-manipulable.
Proof.
Let
be, respectively, the set of women and
men. Consider the following instance of an SMW, say
P
,
{
w
1
,w
2
,w
3
}
and
{
m
1
,m
2
,m
3
}
m
1
:
w
[
x
+2
α
]
2
>w
[
x
+
α
]
1
{
>
w
[
x
3
,m
2
:
w
[
x
+2
α
]
>w
[
x
+
α
]
2
>w
[
x
3
,m
3
:
w
[
x
+2
α
]
>w
[
x
+
α
]
2
>w
[
x
3
,w
1
:
m
[
x
+
α
+1]
1
1
1
>m
[
x
+
α
]
2
>m
[
x
3
,w
2
:
m
[
x
+2
α
]
>m
[
x
+
α
]
1
>m
[
x
2
,w
3
:
m
[
x
+2
α
]
>m
[
x
+
α
]
2
>m
[
x
3
}
.
3
1
P
has two
α
-stable marriages:
M
1
=
{
(
m
1
,w
1
)
,
(
m
2
,w
3
)
,
(
m
3
,w
2
)
}
and
M
2
=
{
(
m
1
,w
3
)
,
(
m
2
,w
1
)
,
(
m
3
,w
2
)
}
. Assume that
w
1
mis-reports her preferences as fol-
lows:
w
1
:
m
[
x
+2
α
]
2
>m
[
x
3
, i.e., assume that she changes the weight given
to
m
1
from
x
+
α
+1
to
x
+2
α
. Let us denote with
P
the resulting problem.
P
has a unique
α
-stable marriage, that is
M
1
, which is the best
α
-stable marriage for
w
1
in
P
. Therefore, it is convenient for
w
1
to change her weights to get a better or equal
result w.r.t the one obtained by telling the truth. Also, since
P
has a unique
α
-stable
marriage, every procedure which returns an
α
-stable marriage returns such a marriage.
Thus, every procedure is w-manipulable.
>m
[
x
+
α
]
1
