Stable Matching
Definition
Goal: Given n men and n women, find a "suitable" matching.
- Participants rate members of opposite sex.
- Each man lists women in order of preference from best to worst.
- Each woman lists men in order of preference from best to worst.
特征:二分图,按照优先度排序
Unstable pair: applicant x and hospital y are unstable if:
- x prefers y to its assigned hospital
- y prefers x to one of its admitted students.
Stable assignment: Assignment with no unstable pairs.
- Natural and desirable condition.
- Individual self-interest will prevent any applicant/hospital deal from being made.
Perfect matching: everyone is matched monogamously
- Each man gets exactly one woman.
- Each woman gets exactly one man.
Stability:no incentive for some pair of participants to undermine assignment by joint action。
- In matching M, an unmatched pair m-w is unstable if man m and woman w prefer each other to current partners.
- Unstable pair m-w could each improve by eloping.
Stable matching:perfect matching with no unstable pairs.
Stable matching problem: Given the preference lists of n men and n women, find a stable matching if one exists.
稳定匹配不一定存在,如分配室友:
Stable roommate problem:
- 2n people; each person ranks others from 1 to 2n-1.
- Assign roommate pairs so that no unstable pairs.

此反例可以结合二分图中的相关证明理解
Gale-Shapley Algorithm
Initialize each person to be free.
while (some man is free and hasn't proposed to every woman) {
Choose such a man m
w = 1st woman on m's list to whom m has not yet proposed
if (w is free)
assign m and w to be engaged
else if (w prefers m to her fiancé m')
assign m and w to be engaged, and m' to be free
else
w rejects m
}
Proof of Correctness
Termination
Observation:
- Men propose to women in decreasing order of preference
- Once a woman is matched, she never becomes unmatched; she only "trades up."
Claim: Algorithm terminates after at most $n^2$ iterations of while loop.
Each time through the while loop a man proposes to a new woman. There are only n2 possible proposals.
Perfection
Claim. All men and women get matched.
Pf. (by contradiction)
- Suppose, for sake of contradiction, that Zeus is not matched upontermination of algorithm.
- Then some woman, say Amy, is not matched upon termination.
- By Observation 2, Amy was never proposed to.
- But, Zeus proposes to everyone, since he ends up unmatched. ▪
Stability
Claim. No unstable pairs.
Pf. (by contradiction)
- Suppose A-Z is an unstable pair: each prefers each other topartner in Gale-Shapley matching S*.
- Case 1: Z never proposed to A.
- Z prefers his GS partner to A.
- A-Z is stable.
- Case 2: Z proposed to A.
- A rejected Z (right away or later)
- A prefers her GS partner to Z.
- A-Z is stable.
- In either case A-Z is stable, a contradiction. ▪
Efficient Implementation
Representing men and women:
- Assume men are named 1, …, n.
- Assume women are named 1', …, n'.
Engagements:
- Maintain a list of free men, e.g., in a queue
- Maintain two arrays
wife[m]
, andhusband[w]
. - set entry to 0 if unmatched
- if m matched to w then wife[m]=w and husband[w]=m
Men proposing:
- For each man, maintain a list of women, ordered by preference
- Maintain an array
count[m]
that counts the number of proposalsmade by manm
.
也可以基于链表实现,删除头节点即可
Women rejecting/accepting:
- For each woman, create inverse of preference list of men.
- Constant time access for each query after O(n) preprocessing.
Other Understanding
- 对于解不唯一的样例,Gale-Shapley 算法总会给出相同的匹配吗?
- valid partner: Man m is a valid partner of woman w if there exists some stablematching in which they are matched.
- Man-optimal assignment: Each man receives best valid partner.
All executions of GS yield man-optimal assignment, which is a stable matching.
主动方占优,该算法男性主动发出匹配请求。
Man Optimality
Claim. _GS matching S is man-optimal._*
Pf. (by contradiction)
- (S* ) Suppose some man is paired with someone other than bestpartner. Men propose in decreasing order of preference someman is rejected by valid partner.
- (S* ) Let Y be first such man, and let A be first valid woman that rejects him.
- Let S be a stable matching where A and Y are matched.
- (S* ) When Y is rejected, A forms (or reaffirms) engagement with a man, say Z, whom she prefers to Y.
- Let B be Z's partner in S.
- (S* ) Z not rejected by any valid partner at the point when Y is rejected by A. Thus, Z prefers A to B. (2,4)
- (S* ) But A prefers Z to Y. (4)
- Thus A-Z is unstable in S.
Woman Pessimality
- Woman-pessimal assignment. Each woman receives worst valid partner.
Claim. GS finds woman-pessimal stable matching S*
Pf.
- Suppose A-Z matched in S*, but Z is not worst valid partner for A.
- There exists stable matching S in which A is paired with a man, sayY, whom she likes less than Z.
- Let B be Z's partner in S.
- Z prefers A to B (in S*. A and B are both valid partners). [man-optimality]
- Thus, A-Z is an unstable in S
END
