Information Technology Reference
In-Depth Information
for SMWs that are based on the strength of the link of the pairs (man,woman), we com-
pare them with the classical stability notion, and we show how to find marriages that are
stable according to these notions with the highest global link. In Section 5 we analyze
manipulation issues in our context. In Section 6 we summarize the results contained in
the paper, and we give some hints for future work.
A preliminary version of this paper has been presented in [16].
2
Background
We now give some basic notions on classical stable marriage problems, stable marriage
problems with partial orders, and stable marriage problems with weighted preferences.
2.1
Stable Marriage Problems
A stable marriage problem (SM) [9] of size n is the problem of finding a stable marriage
between n men and n women. Such men and women each have a preference ordering
over the members of the other sex. A marriage is a one-to-one correspondence between
men and women. Given a marriage M ,aman m , and a woman w , the pair ( m, w ) is a
blocking pair for M if m prefers w to his partner in M and w prefers m to her partner
in M . A marriage is said to be stable if it does not contain blocking pairs.
The sequence of all preference orderings of men and women is usually called a
profile . In the case of classical stable marriage problem (SM), a profile is a sequence of
strict total orders.
Given a SM P , there may be many stable marriages for P . However, it is interesting
to know that there is always at least one stable marriage.
Given an SM P ,a feasible partner for a man m (resp., a woman w )isawoman w
(resp., a man m ) such that there is a stable marriage for P where m and w are married.
The set of all stable marriages for an SM forms a lattice, where a stable marriage
M 1 dominates another stable marriage M 2 if men are happier (that is, are married to
more or equally preferred women) in M 1 w.r.t. M 2 . The top of this lattice is the stable
marriage where men are most satisfied, and it is usually called the male-optimal stable
marriage. Conversely, the bottom is the stable marriage where men's preferences are
least satisfied (and women are happiest, so it is usually called the female-optimal stable
marriage). Thus, a stable marriage is male-optimal iff every man is paired with his
highest ranked feasible partner.
The Gale-Shapley (GS) algorithm [4] is a well-known algorithm to solve the SM
problem. At the start of the algorithm, each person is free and becomes engaged during
the execution of the algorithm. Once a woman is engaged, she never becomes free again
(although to whom she is engaged may change), but men can alternate between being
free and being engaged. The following step is iterated until all men are engaged: choose
a free man m ,andlet m propose to the most preferred woman w on his preference list,
such that w has not already rejected m .If w is free, then w and m become engaged. If
w is engaged to man m ', then she rejects the man ( m or m ') that she least prefers, and
becomes, or remains, engaged to the other man. The rejected man becomes, or remains,
 
Search WWH ::




Custom Search