You've successfully subscribed to The Daily Awesome
Great! Next, complete checkout for full access to The Daily Awesome
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.
Success! Your billing info is updated.
Billing info update failed.

算法 | 稳定匹配 - Stable Matching

. 4 min read

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 upon
    termination 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 to
    partner 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], and husband[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 proposals
    made by man m.

也可以基于链表实现,删除头节点即可

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

  1. 对于解不唯一的样例,Gale-Shapley 算法总会给出相同的匹配吗?
  • valid partner:  Man m is a valid partner of woman w if there exists some stable
    matching 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)

  1. (S* ) Suppose some man is paired with someone other than best
    partner. Men propose in decreasing order of preference  some
    man is rejected by valid partner.
  2. (S* ) Let Y be first such man, and let A be first valid woman that rejects him.
  3. Let S be a stable matching where A and Y are matched.
  4. (S* ) When Y is rejected, A forms (or reaffirms) engagement with a man, say Z, whom she prefers to Y.
  5. Let B be Z's partner in S.
  6. (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)
  7. (S* ) But A prefers Z to Y. (4)
  8. 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.

  1. Suppose A-Z matched in S*, but Z is not worst valid partner for A.
  2. There exists stable matching S in which A is paired with a man, say
    Y, whom she likes less than Z.
  3. Let B be Z's partner in S.
  4. Z prefers A to B (in S*. A and B are both valid partners). [man-optimality]
  5. Thus, A-Z is an unstable in S

END