Information Technology Reference
In-Depth Information
Theorem 4.
Every stable marriage procedure that returns a link-additive stable mar-
riage is w-manipulable.
Proof.
Let
be, respectively, the set of women and men. Con-
sider the following instance of an SMW, say
P
:
{
w
1
,w
2
}
and
{
m
1
,m
2
}
{m
1
:
w
[6]
2
>w
[4
1
,m
2
:
w
[5]
2
>
w
[2
1
,w
1
:
m
[3]
1
>m
[2
2
,w
2
:
m
[5]
1
>m
[2
2
}
.
P
has a unique link-additive stable mar-
riage, which is
M
1
=
{
(
m
1
,w
2
)
,
(
m
2
,w
1
)
}
. Assume that
w
1
mis-reports her prefer-
ences as follows:
w
1
:
m
[100]
1
>m
[2
2
, i.e., she changes the weight given to
m
1
from
3
to
100
. Then, in the new problem, that we call
P
, there is a unique link-additive stable
marriage, i.e.,
M
2
=
, which is better for
w
1
in
P
. Since in
P
there is a unique link-additive-stable marriage, every procedure which returns a link-
additive stable marriage will return it. Thus, every procedure is w-manipulable.
{
(
m
1
,w
1
)
,
(
m
2
,w
2
)
}
A similar result can be shown also for stable marriage procedures that return a link-
maximal stable marriage.
Summarizing, even if we don't allow the agents to modify their preference ordering
or to truncate their preference list, they can manipulate simply by changing the values
of their weights. Moreover, it is possible to see that some ideas to prevent manipula-
tion, such as to assign equal weight to all top alternatives and to put a bound over the
relative weights of two consecutive elements in every ordering, are ineffective to avoid
w-manipulation.
6
Conclusions and Future Work
In this paper we have considered stable marriage problems with weighted preferences,
where both men and women can express a score over the members of the other sex. In
particular, we have introduced new stability and optimality notions for such problems
and we have compared them with the classical ones for stable marriage problems with
totally or partially ordered preferences. Also, we have provided algorithms to find mar-
riages that are optimal and stable according to these new notions by adapting the Gale-
Shapley algorithm. Moreover, we have investigated manipulation issues in our context.
We have also considered an optimality notion (that is, lex-male-optimality) that ex-
ploits a voting rule to linearize the partial orders. We intend to study if this use of voting
rules within stable marriage problems may have other benefits. In particular, we want to
investigate if the procedure defined to find such an optimality notion inherits the prop-
erties of the voting rule with respect to manipulation: we intend to check whether, if
the voting rule is NP-hard to manipulate, then also the procedure on SMW that exploits
such a rule is NP-hard to manipulate. This would allow us to transfer several existing
results on manipulation complexity, which have been obtained for voting rules, to the
context of procedures to solve stable marriage problems with weighted preferences.
Acknowledgements.
This work has been partially supported by the MIUR PRIN 20089
M932N project “Innovative and multi-disciplinary approaches for constraint and pref-
erence reasoning”.
