Some Representative Problems

Stable Matching Problem

Hospital - Residents Matching

Goal

Given a set of preferences among hospitals and med school students, design a self-reinforcing admission process.

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.

Marriage Matching

Goal

Given $n$ men and $n$ women, let each of them rate each other of another sex from 1 to n.

A blocking pair in the Stable Marriage Problem is a pair (m,w)(m, w)(m,w) (a man and a woman) who are not matched in the current pairing but would prefer each other over their assigned partners.

Formally, a pair (m,w)(m, w)(m,w) is a blocking pair if:

  1. Man mmm prefers woman www over his current match w′w’w′ (if he has one).
  2. Woman www prefers man mmm over her current match m′m’m′ (if she has one).

If such a pair exists, they have an incentive to leave their assigned partners and pair up together, making the matching unstable.

A matching is stable if no blocking pair exists.

Example

Let’s consider 3 men (A, B, C) and 3 women (X, Y, Z).

Each person ranks the members of the opposite gender from 1 (most preferred) to 3 (least preferred).

Man First Choice Second Choice Third Choice
A X Y Z
B Y X Z
C X Z Y
Woman First Choice Second Choice Third Choice
X B A C
Y C B A
Z A B C

解法：Gale-Shapley（延迟接受算法, DA Algorithm）

Gale-Shapley 算法能保证找到一个稳定匹配。

算法流程

  1. 男性向自己最喜欢的女性求婚（如果被拒绝，他会向次喜欢的求婚）。
  2. 女性会暂时接受她最喜欢的求婚者，并拒绝其余的人（如果她后来收到更好的求婚，她可以更换）。
  3. 被拒绝的男性会继续向自己的次优选择求婚。
  4. 重复上述步骤，直到所有人都匹配成功。

最终，算法会终止，并且所有匹配都是稳定的。