Information Technology Reference
In-Depth Information
to find a matching that makes all marriages stable, and provided a polynomial time al-
gorithm which can be used to find one of two extreme stable marriages, the so-called
male-optimal
or
female-optimal
solutions. The Gale-Shapley algorithm has been used
in many real-life scenarios [20], such as in matching hospitals to resident doctors [19],
medical students to hospitals, sailors to ships [13], primary school students to secondary
schools [21], as well as in market trading.
In the classical stable marriage problem, both men and women express a strict pref-
erence order over the members of the other sex in a qualitative way. Here we consider
stable marriage problems with weighted preferences. In such problems each man (resp.,
woman) provides a score for each woman (resp., man). Stable marriage problems with
weighted preferences are interesting since they are more expressive than the classical
stable marriage problems, since in classical stable marriage problem a man (resp., a
woman) cannot express how much he (resp., she) prefers a certain woman (resp., man).
Moreover, they are useful in some real-life situations where it is more natural to express
scores, that can model notions such as profit or cost, rather than a qualitative preference
ordering. In this context, we define new notions of stability and optimality, we compare
such notions with the classical ones, and we show algorithms to find marriages which
are stable and/or optimal according to these notions. While expressivity 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 precisely, we adapt the
classical notion of manipulation to our context and we show that in some cases the pro-
cedures which return the new kinds of stable marriage are manipulable.
Stable marriage problems with weighted preferences have been studied also in [8,12].
However, they solve these problems by looking at the stable marriages that maximize
the sum of the weights of the married pairs, where the weights depend on the spe-
cific criteria used to find an optimal solution, that can be minimum regret criterion [8],
the egalitarian criterion [12] or the Lex criteria [12]. Therefore, they consider as stable
the same marriages that are stable when we don't consider the weights. We instead use
the weights to define new notions of stability that may lead to stable marriages that
are different from the classical case. They may rely on the difference of weights that
a person gives to two different people of the other sex, or by the strength of the link
of the pairs (man,woman), i.e., how much a person of the pair wants to be married
with the other person of the pair. The classical definition of stability for stable marriage
problems with weighted preferences has been considered also in [2] that has used a
semiring-based soft constraint approach [3] to model and solve these problems.
The paper is organized as follows. In Section 2 we give the basic notions of classical
stable marriage problems, stable marriage problems with partially ordered preferences
and stable marriage problems with weighted preferences (SMWs). In Section 3 we in-
troduce a new notion of stability, called
α
-stability for SMWs, which depends on the
difference of scores that every person gives to two different people of the other sex, and
we compare it with the classical notion of stability. Moreover, we give a new notion
of optimality, called lex-optimality, to discriminate among the new stable marriages,
which depends on a voting rule. We show that there is a unique optimal stable marriage
and we give an algorithm to find it. In Section 4 we introduce other notions of stability
