Information Technology Reference
In-Depth Information
Stability and Optimality in Matching Problems
with Weighted Preferences
Maria Silvia Pini
1
, Francesca Rossi
1
,
Kristen Brent Venable
1
, and Toby Walsh
2
1
Department of Pure and Applied Mathematics, University of Padova
Padova, Italy
2
NICTA and UNSW, Sydney, Australia
{
mpini,frossi,kvenable
}
@math.unipd.it,
Toby.Walsh@nicta.com.au
Abstract.
The stable marriage problem is a well-known problem of matching
men to women so that no man and woman, who are not married to each other,
both prefer each other. Such a problem has a wide variety of practical applica-
tions, ranging from matching resident doctors to hospitals, to matching students
to schools or more generally to any two-sided market. In the classical stable mar-
riage problem, both men and women express a strict preference order over the
members of the other sex, in a qualitative way. Here we consider stable marriage
problems with weighted preferences: each man (resp., woman) provides a score
for each woman (resp., man). Such problems are more expressive than the clas-
sical stable marriage problems. Moreover, in some real-life situations it is more
natural to express scores (to model, for example, profits or costs) rather than a
qualitative preference ordering. In this context, we define new notions of stabil-
ity and optimality, and we provide algorithms to find marriages which are stable
and/or optimal according to these notions. While expressivity greatly increases by
adopting weighted preferences, we show that in most cases the desired solutions
can be found by adapting existing algorithms for the classical stable marriage
problem. We also investigate manipulation issues in our framework. More pre-
cisely, we adapt the classical notion of manipulation to our context and we study
if the procedures which return the new kinds of stable marriages are manipulable.
Keywords:
Stable marriages, Weighted preferences.
1
Introduction
The stable marriage problem (SM) [9] is a well-known problem of matching the ele-
ments of two sets. It is called the
stable marriage
problem since the standard formula-
tion is in terms of men and women, and the matching is interpreted in terms of a set of
marriages. Given
n
men and
n
women, where each person expresses a strict ordering
over the members of the opposite sex, the problem is to match the men to the women
so that there are no two people of opposite sex who would both rather be matched
with each other than their current partners. If there are no such people, all the mar-
riages are said to be
stable
. In [4] Gale and Shapley proved that it is always possible
