8. Matching — One to One Two-sided Matching

Jun He June 01, 2026

中文English 匹配Matching 稳定匹配Stable Matching 延迟接受算法Deferred Acceptance 婚姻市场Marriage Market 防策略Strategy-proof

8. Matching — One to One Two-sided Matching

Note

本章导读本章讨论婚姻市场——一对一、双边匹配。先给出设定与匹配 $\mu$（二阶映射），用个体理性、被对阻塞定义稳定匹配（等价于核）。核心结论：双边一对一问题稳定匹配总存在（Thm 8.1），由 延迟接受算法（DAA） 构造性证明（四人室友例 8.1 说明多边时可能无稳定匹配）。随后给出未匹配者集合在所有稳定匹配中不变（Thm 8.2），DAA 的效率：男方提议的 $\mu_M$ 对男方 Pareto 最优、对女方最差（Thm 8.3/8.4 与推论 8.1）；最后说明 DAA 非防策略（与 Gibbard–Satterthwaite 相关）。

8. Matching — One to One Two-sided Matching

Note

Overview This chapter discusses the marriage market — one-to-one, two-sided matching. We set up matching $\mu$ (an order-2 mapping) and define stable matching (equivalent to the core) via individual rationality and being blocked by a pair. The core result: a stable matching always exists for two-sided one-to-one problems (Thm 8.1), proved constructively by the Deferred Acceptance Algorithm (DAA) (the four-agent roommate example 8.1 shows more-than-two-sided problems may have none). We then show the set of unmatched persons is constant across all stable matchings (Thm 8.2), and the efficiency of DAA: the man-proposing $\mu_M$ is Pareto-optimal for men and worst for women (Thm 8.3/8.4 and Corollary 8.1); finally we explain DAA is not strategy-proof (related to Gibbard–Satterthwaite).

8.1 Set-up

记男性集合 $M=\{m_1,m_2,\dots,m_n\}$，女性集合 $W=\{w_1,w_2,\dots,w_p\}$；典型元素 $m\in M$、$w\in W$。
每个 $x\in M\cup W$ 在市场另一侧的个体及其自身上有严格排序 $\succ_x$。

8.1 Set-up

Denote the set of men by $M=\{m_1,m_2,\dots,m_n\}$ and women by $W=\{w_1,w_2,\dots,w_p\}$; typical elements $m\in M$, $w\in W$.
Each $x\in M\cup W$ has a strict ranking $\succ_x$ over individuals on the other side of the market and himself (herself).

Tip

注记 8.1 / Remark 8.1 严格排序意味着排序中无无差异或并列。排序包含异性所有人以及该 agent 自身；把自身纳入排序，使 agent 可有"不与排在自己之下者结婚"的决策规则。Strict ranking means there will be no indifference or ties in the ranking. The ranking includes everyone of different gender and the agent himself (herself). Including himself (herself) allows the agent the decision rule that he (she) will not marry the one ranked below himself (herself).

一个匹配是映射 $\mu:M\cup W\to M\cup W$ 使 $\mu(m)\in W\cup\{m\}$、$\mu(w)\in M\cup\{w\}$。

若 $\mu(x)=x$，则该 agent 保持单身。
映射 $\mu$ 是二阶的：$\mu(\mu(x))=x$——即与你匹配者的匹配就是你自己；二阶映射即一对一映射。

8.2 Rationality of matching

A matching is a mapping $\mu:M\cup W\to M\cup W$ s.t. $\mu(m)\in W\cup\{m\}$ and $\mu(w)\in M\cup\{w\}$.

if $\mu(x)=x$, then the agent stays single.
the mapping $\mu$ is of order 2: $\mu(\mu(x))=x$ — the match of the person to whom you are matched is yourself; a mapping of order 2 is a one-to-one mapping.

8.2 Rationality of matching

Important

Definitions 8.1–8.3（rationality & stability） Def 8.1（个体理性）：$\mu$ 个体理性（等价于不被任何个体阻塞），当且仅当 $\mu(x)\succ_x x$ 对 $\forall x:\mu(x)\ne x$。（Rmk 8.2：任何不单身者都被匹配给严格优于单身的对象。）
Def 8.2（被对阻塞）：$\mu$ 被 $m$ 与 $w$ 阻塞，当且仅当 $w\succ_m\mu(m)$ 且 $m\succ_w\mu(w)$。（Rmk 8.3：若一男一女彼此都觉得对方严格优于现匹配，则二人阻塞该匹配并选择在一起。）
Def 8.3（稳定匹配）：$\mu$ 稳定，当且仅当 $\mu$ 不被任何个体（即个体理性）或任何对阻塞。（Rmk 8.4：稳定匹配实为核的等价概念，因唯一可能的联盟只有个体或对，但此处称稳定匹配。）Def 8.1 (Individual rationality): $\mu$ is individually rational (equivalently, not blocked by any individual) iff $\mu(x)\succ_x x$ for $\forall x:\mu(x)\ne x$. (Rmk 8.2: any individual not single is matched to someone strictly preferred to staying single.)
Def 8.2 (Blocked by pair): $\mu$ is blocked by $m$ and $w$ iff $w\succ_m\mu(m)$ and $m\succ_w\mu(w)$. (Rmk 8.3: if a man and a woman each find each other strictly better than the match they have, they block that matching and stay with each other.)
Def 8.3 (Stable match): $\mu$ is stable iff $\mu$ is not blocked by any individual (individually rational) or any pair. (Rmk 8.4: a stable match is an equivalent concept to the core since the only possible coalitions are individual or pair, but here we call it a stable match.)

8.3 Existence of stable matching

自然要问：稳定匹配是否总存在？只要匹配是双边的，答案就是肯定的。若匹配多于两边，则可能出问题，如下面的四边室友匹配例所示。

8.3 Existence of stable matching

The natural question: does a stable matching always exist? The answer is yes as long as the matching is two-sided. If the matching is more than two-sided, there might be problems, as the following four-sided roommate example shows.

Important

Example 8.1（Roommate matching / 室友匹配）四个 agent $a,b,c,d$ 要配成两对室友，偏好如下表。即 $a$ 是 $b$ 的最爱；$b$ 是 $c$ 的最爱；$c$ 是 $a$ 的最爱；$a,b,c$ 都不喜欢 $d$。$a,b,c$ 每人都是某人的最爱，故无论怎么配，与 $d$ 配对者总能去找以他为最爱的人阻塞该匹配——故无稳定匹配。Four agents $a,b,c,d$ are to be matched into two pairs of roommates, with the preferences below. So $a$ is $b$'s favorite; $b$ is $c$'s favorite; $c$ is $a$'s favorite; $a,b,c$ all dislike $d$. Each of $a,b,c$ is someone's favorite, so whatever the match, the one matched with $d$ can always go to the one to whom he is the favorite to block the match — so there is no stable match.

$\succ_a$	$\succ_b$	$\succ_c$	$\succ_d$
$c$	$a$	$b$	(not
$b$	$c$	$a$	important)
$d$	$d$	$d$

现考虑双边（婚姻）问题。

Now consider the two-sided (marriage) problem.

Important

Theorem 8.1 双边一对一匹配问题总存在稳定匹配。A stable matching always exists for two-sided one-to-one matching problems.

为证明，定义一个输出总为稳定匹配的算法——男方提议的延迟接受算法（Deferred Acceptance Algorithm, $\text{DAA}_M$）：

初始化：所有男女均未订婚。
第 $k$ 步：每个未订婚男士向尚未拒绝他的、可接受的女士中他最偏好的那位提议（若有）。（脚注 8.1：只有未订婚男士可提议。）
第 $k+1$ 步：每位女士拒绝所有不可接受男士的提议；在可接受男士的提议中，只接受她最偏好的一个，拒绝其余。
若女士不拒绝某男士提议，二人订婚。
若女士在后续步骤收到新提议，她会把新提议与现订婚对象放在一起，接受其中最好的。
算法终止：当无男士提议时停止。停止时所有订婚者配对，所有单身者与自己匹配。

此过程产生匹配 $\mu_M$。须证 $\mu_M$ 良定义（有限步内完成且输出是匹配）且稳定。

To prove it, define an algorithm whose output is always a stable matching — the man-proposing Deferred Acceptance Algorithm ($\text{DAA}_M$):

Initialize: all men and women are unengaged.
Step $k$: each unengaged man proposes to his most preferred acceptable woman among those who have not yet rejected him, if any. (footnote 8.1: only unengaged men can make proposals.)
Step $k+1$: each woman rejects all proposals from unacceptable men, and among proposals from her acceptable men she accepts only her most preferred one and rejects the rest.
if a woman doesn't reject a man's proposal, they become engaged.
if a woman receives new proposals in later steps, she puts those together with her current engagement and accepts the best among them.
Stop: the algorithm stops when no man proposes. When it stops, all engaged couples are matched and all singles are matched to themselves.

This produces a matching $\mu_M$. We must show $\mu_M$ is well-defined (finishes in finite steps and the outcome is a matching) and stable.

Important

Definition 8.4（Acceptable） $m$ 对 $w$ 可接受，当且仅当 $m\succ_w w$；类似地 $w$ 对 $m$ 可接受当且仅当 $w\succ_m m$。（脚注 8.3：已订婚女士仍可接受提议并与现订婚对象比较以决定换或不换；但已订婚男士不能再提议、也不能主动解除订婚，除非其对象离开他使他重新未订婚。）$m$ is acceptable to $w$ iff $m\succ_w w$; similarly $w$ is acceptable to $m$ iff $w\succ_m m$. (footnote 8.3: an already-engaged woman can still take proposals and compare with her current engagement to switch or stay; but an engaged man cannot make new proposals or disengage until his partner leaves him and makes him unengaged again.)

Note

证明 / Proof (Theorem 8.1: well-defined & stable)

1. 良定义：(a) $\text{DAA}_M$ 在有限步内停止，因每个男士至多提议 $\text{card}(W)$ 次，故总轮数不超过 $\text{card}(W)\times\text{card}(M)$。(b) 输出是匹配，因每对订婚者只彼此订婚；若个体未订婚则与自身匹配。
2. 稳定：(a) $\mu_M$ 个体理性，因无人会与不可接受的对象订婚（男士从不向不可接受女士提议；女士总拒绝不可接受提议）。(b) 再证 $\mu_M$ 不被任何对阻塞：考虑任意对 $m,w$ 使 $w\succ_m\mu_M(m)$，须证 $\mu_M(w)\succ_w m$。由算法，男士 $m$ 总沿其列表逐个下移、从不跳过；若 $w\succ_m\mu_M(m)$，则 $w$ 必在 $\text{DAA}_M$ 某步拒绝过 $m$。于是要么 (A) $m$ 对 $w$ 不可接受，证毕；要么 (B) $w$ 当时已与她更偏好的 $m'$ 订婚。因 $w$ 在算法中"逐步升级"（脚注 8.4：$\text{DAA}_M$ 中女士的男士排序只升不降，至少不变），故 $\mu_M(w)\succsim_w m'\succ_w m$，证毕。$\blacksquare$

1. Well-defined: (a) $\text{DAA}_M$ stops in finite steps because each man makes at most $\text{card}(W)$ proposals, so it cannot be more than $\text{card}(W)\times\text{card}(M)$ rounds. (b) The outcome is a matching because each pair of engaged individuals is engaged only to one another; and an unengaged individual is matched to himself/herself.
2. Stable: (a) $\mu_M$ is individually rational because no one is ever engaged to an unacceptable mate (a man never proposes to an unacceptable woman; a woman always rejects unacceptable proposals). (b) Now show $\mu_M$ is not blocked by any pair: consider any pair $m,w$ with $w\succ_m\mu_M(m)$; we must show $\mu_M(w)\succ_w m$. By the algorithm, man $m$ always moves down his list one by one and never skips; if $w\succ_m\mu_M(m)$, then $w$ must have rejected $m$ at some step of $\text{DAA}_M$. So either (A) $m$ is unacceptable to $w$, and we are done; or (B) $w$ was engaged to some $m'$ she prefers to $m$. Since $w$ "trades up" during the algorithm (footnote 8.4: in $\text{DAA}_M$ a woman's ranking of men only moves up, or at least stays the same), $\mu_M(w)\succsim_w m'\succ_w m$, and the proof is done. $\blacksquare$

Tip

注记 8.5–8.6 / Remarks 8.5–8.6 8.5：任何动态过程中，若某函数单调，则它可能收敛而绝不循环。$\text{DAA}_M$ 中女性处境沿步骤（弱）改善，故结果不会循环。8.6：DAA 算法与稳定匹配的存在性不要求偏好严格。若 agent 列表中有并列，只需任意打破并列、给它们一个顺序，结论仍成立——因为要阻塞匹配，两个个体都须严格更优。8.5: in any dynamic process, if a function is monotone, then it can possibly converge and never cycle. In $\text{DAA}_M$, women's situations (weakly) improve along the steps, so the result won't cycle. 8.6: the DAA algorithm and existence of stable matching don't require strict preferences. If there are ties in agents' lists, simply break the ties and order them arbitrarily and the same result holds, because for a pair to block, both individuals must be strictly better off.

类似地，可定义女方提议的 $\text{DAA}_W$，也给出稳定匹配 $\mu_W$。下面看一个例子。

Similarly, we can define the woman-proposing $\text{DAA}_W$, which also gives a stable matching $\mu_W$. Let's see an example.

Important

Example 8.2 用男方提议与女方提议 DAA 求下列严格偏好下的稳定匹配。每个个体都严格偏好与另一侧任何人结婚而非单身，唯 $m_5$ 宁愿单身也不与 $w_3$ 结婚（故 $\succ_{m_5}$ 列表不含 $w_3$）。Use both man-proposing and woman-proposing DAA to find stable matchings given the following strict preferences. Each individual strictly prefers being married to anyone on the other side over being single, except $m_5$ who prefers being single to marrying $w_3$ (so $\succ_{m_5}$ omits $w_3$).

$$ \begin{aligned} \succ_{m_1}&:w_1,w_2,w_3,w_4 & \succ_{w_1}&:m_2,m_3,m_1,m_4,m_5\\ \succ_{m_2}&:w_4,w_3,w_2,w_1 & \succ_{w_2}&:m_3,m_1,m_2,m_4,m_5\\ \succ_{m_3}&:w_4,w_3,w_1,w_2 & \succ_{w_3}&:m_5,m_4,m_1,m_2,m_3\\ \succ_{m_4}&:w_1,w_4,w_3,w_2 & \succ_{w_4}&:m_1,m_4,m_5,m_2,m_3\\ \succ_{m_5}&:w_1,w_2,w_4 && \end{aligned} $$

先看男方提议 DAA（以 $\to$ 表示提议）：

第 1 步：(a) $m_1\to w_1$、$m_2\to w_4$、$m_3\to w_4$、$m_4\to w_1$、$m_5\to w_1$。(b) $w_1$ 接受 $m_1$，拒绝 $m_4,m_5$。(c) $w_4$ 接受 $m_2$，拒绝 $m_3$。
第 2 步：(a) $m_1,m_2$ 此步不能提议。(b) $m_3\to w_3$、$m_4\to w_4$、$m_5\to w_2$。(c) $w_3$ 接受 $m_3$。(d) $w_4$ 接受 $m_4$，拒绝 $m_2$，故 $m_2$ 重新单身。(e) $w_2$ 接受 $m_5$。
第 3 步：(a) 只有 $m_2$ 能提议，$m_2\to w_3$。(b) $w_3$ 接受 $m_2$，拒绝 $m_3$，故 $m_3$ 重新单身。
第 4 步：(a) 只有 $m_3$ 能提议，$m_3\to w_1$。(b) $w_1$ 接受 $m_3$，拒绝 $m_1$，故 $m_1$ 重新单身。
第 5 步：(a) 只有 $m_1$ 能提议，$m_1\to w_2$。(b) $w_2$ 接受 $m_1$，拒绝 $m_5$，故 $m_5$ 重新单身。
第 6 步：(a) 只有 $m_5$ 能提议，$m_5\to w_4$。(b) $w_4$ 拒绝 $m_5$。
第 7 步：无男士可再提议，算法停止。

最终匹配：$w_2\leftrightarrow m_1$，$w_1\leftrightarrow m_3$，$w_3\leftrightarrow m_2$，$w_4\leftrightarrow m_4$，$m_5\leftrightarrow m_5$。

再看女方提议 DAA：

第 1 步：(a) $w_1\to m_2$、$w_2\to m_3$、$w_3\to m_5$、$w_4\to m_1$。(b) $m_2$ 接受 $w_1$。(c) $m_3$ 接受 $w_2$。(d) $m_5$ 拒绝 $w_3$。(e) $m_1$ 接受 $w_4$。
第 2 步：(a) 只有 $w_3$ 能提议，$w_3\to m_4$。(b) $m_4$ 接受 $w_3$。
第 3 步：无女士可再提议，算法停止。

最终匹配：$w_1\leftrightarrow m_2$，$w_2\leftrightarrow m_3$，$w_3\leftrightarrow m_4$，$w_4\leftrightarrow m_1$，$m_5\leftrightarrow m_5$。

注意男方与女方提议 DAA 都给出稳定匹配，但结果不同。另注意两种稳定匹配中未匹配者集合都恒为 $\{m_5\}$。这一观察可由下面定理推广。

First, the man-proposing DAA (let $\to$ denote a proposal):

Step 1: (a) $m_1\to w_1$, $m_2\to w_4$, $m_3\to w_4$, $m_4\to w_1$, $m_5\to w_1$. (b) $w_1$ accepts $m_1$, rejects $m_4,m_5$. (c) $w_4$ accepts $m_2$, rejects $m_3$.
Step 2: (a) $m_1,m_2$ cannot propose. (b) $m_3\to w_3$, $m_4\to w_4$, $m_5\to w_2$. (c) $w_3$ accepts $m_3$. (d) $w_4$ accepts $m_4$, rejects $m_2$, so $m_2$ becomes single again. (e) $w_2$ accepts $m_5$.
Step 3: (a) only $m_2$ can propose, $m_2\to w_3$. (b) $w_3$ accepts $m_2$, rejects $m_3$, so $m_3$ single again.
Step 4: (a) only $m_3$ can propose, $m_3\to w_1$. (b) $w_1$ accepts $m_3$, rejects $m_1$, so $m_1$ single again.
Step 5: (a) only $m_1$ can propose, $m_1\to w_2$. (b) $w_2$ accepts $m_1$, rejects $m_5$, so $m_5$ single again.
Step 6: (a) only $m_5$ can propose, $m_5\to w_4$. (b) $w_4$ rejects $m_5$.
Step 7: no man can propose, the algorithm stops.

Final matching: $w_2\leftrightarrow m_1$, $w_1\leftrightarrow m_3$, $w_3\leftrightarrow m_2$, $w_4\leftrightarrow m_4$, $m_5\leftrightarrow m_5$.

Then, the woman-proposing DAA:

Step 1: (a) $w_1\to m_2$, $w_2\to m_3$, $w_3\to m_5$, $w_4\to m_1$. (b) $m_2$ accepts $w_1$. (c) $m_3$ accepts $w_2$. (d) $m_5$ rejects $w_3$. (e) $m_1$ accepts $w_4$.
Step 2: (a) only $w_3$ can propose, $w_3\to m_4$. (b) $m_4$ accepts $w_3$.
Step 3: no woman can propose, the algorithm stops.

Final matching: $w_1\leftrightarrow m_2$, $w_2\leftrightarrow m_3$, $w_3\leftrightarrow m_4$, $w_4\leftrightarrow m_1$, $m_5\leftrightarrow m_5$.

Both man-proposing and woman-proposing DAA yield a stable matching, but the results differ. Note also the set of unmatched persons remains constant in both, namely $\{m_5\}$. This observation generalizes by the following theorem.

Important

Theorem 8.2 给定所有 agent 的严格偏好，未匹配者集合在所有稳定匹配中恒定不变。Given strict preferences of all agents, the set of unmatched persons is constant over all stable matches.

Note

证明 / Proof (Theorem 8.2)

反证。设存在两稳定匹配 $\mu,\mu'$ 使 $\exists m_1\in M,w_1\in W$，$\mu(m_1)=m_1$ 而 $\mu'(m_1)=w_1$。由严格偏好与两匹配的稳定性，$w_1=\mu'(m_1)\succ_{m_1}m_1=\mu(m_1)$。因 $\mu$ 下 $w_1$ 未配给 $m_1$，必 $m_2=\mu(w_1)\succ_{w_1}m_1$，否则 $(m_1,w_1)$ 阻塞 $\mu$。同理 $\mu'$ 下 $m_2$ 未配给 $w_1$，必 $w_2=\mu'(m_2)\succ_{m_2}w_1=\mu(m_2)$，否则 $(m_2,w_1)$ 阻塞 $\mu'$。反复此程序，得 $\forall m\in M$，$\mu'(m)\succ_m\mu(m)$，即所有男士 Pareto 偏好 $\mu'$ 胜 $\mu$。由 Thm 8.4，所有女士 Pareto 偏好 $\mu$ 胜 $\mu'$。记 $\mu,\mu'$ 下匹配对数为 $k_\mu,k_{\mu'}$。故 $\mu$ 中已匹配男士在 $\mu'$ 中也匹配，$k_\mu\le k_{\mu'}$；$\mu'$ 中已匹配女士在 $\mu$ 中也匹配，$k_\mu\ge k_{\mu'}$，故 $k_\mu=k_{\mu'}$。再证 $\mu$ 中未匹配男士不能在 $\mu'$ 中匹配：若不然，$\mu$ 中未匹配的 $m_i$ 在 $\mu'$ 中匹配，因 $k_\mu=k_{\mu'}$，必有 $m_j$ 在 $\mu$ 匹配而 $\mu'$ 未匹配，则 $\mu(m_j)\succ_{m_j}\mu'(m_j)$，与 $\mu'(m)\succ_m\mu(m)$（$\forall m$）矛盾。$\blacksquare$

By contradiction. Suppose there exist two stable matches $\mu,\mu'$ with $\exists m_1\in M,w_1\in W$, $\mu(m_1)=m_1$ but $\mu'(m_1)=w_1$. By strict preferences and stability of both, $w_1=\mu'(m_1)\succ_{m_1}m_1=\mu(m_1)$. Since under $\mu$, $w_1$ is not matched to $m_1$, it must be $m_2=\mu(w_1)\succ_{w_1}m_1$, else $(m_1,w_1)$ blocks $\mu$. By the same logic, since $m_2$ is not matched to $w_1$ under $\mu'$, it must be $w_2=\mu'(m_2)\succ_{m_2}w_1=\mu(m_2)$, else $(m_2,w_1)$ blocks $\mu'$. Repeating this procedure, $\forall m\in M$, $\mu'(m)\succ_m\mu(m)$, i.e. all men Pareto prefer $\mu'$ to $\mu$. By Thm 8.4, all women Pareto prefer $\mu$ to $\mu'$. Denote the number of matches under $\mu,\mu'$ by $k_\mu,k_{\mu'}$. So all men matched in $\mu$ are matched in $\mu'$, $k_\mu\le k_{\mu'}$; all women matched in $\mu'$ are matched in $\mu$, $k_\mu\ge k_{\mu'}$, so $k_\mu=k_{\mu'}$. Then no man unmatched in $\mu$ can be matched in $\mu'$: if not, an $m_i$ unmatched in $\mu$ is matched in $\mu'$; since $k_\mu=k_{\mu'}$, there must be $m_j$ matched in $\mu$ but not in $\mu'$, so $\mu(m_j)\succ_{m_j}\mu'(m_j)$, contradicting $\mu'(m)\succ_m\mu(m)$ ($\forall m$). $\blacksquare$

8.4 Efficiency of DAA

Important

Definition 8.5（Achievable）对市场相对两侧的 $i,j\in M\cup N$，称 $i$ 对 $j$ 可达（achievable），当且仅当 $i,j$ 在某个稳定匹配中彼此匹配。注意若 $i$ 对 $j$ 可达，则 $j$ 对 $i$ 可达。For $i,j\in M\cup N$ on opposite sides, $i$ is achievable for $j$ iff $i$ and $j$ are matched to one another in some stable matching. Note if $i$ is achievable for $j$, then $j$ is achievable for $i$.

Important

Theorem 8.3 给定严格偏好，稳定匹配 $\mu_M$ 被男方 Pareto 偏好于任何其他稳定匹配（即 $\mu_M$ 对所有男士至少与任何其他稳定匹配一样好，且至少一个男士严格偏好 $\mu_M$）；类似地 $\mu_W$ 被女方 Pareto 偏好于任何其他稳定匹配。Given strict preferences, the stable matching $\mu_M$ is Pareto preferred by the men to any other stable matching ($\mu_M$ is at least as good as any other stable matching to all men, and at least one man strictly prefers $\mu_M$); similarly $\mu_W$ is Pareto preferred by the women to any other stable matching.

Note

证明 / Proof (Theorem 8.3)

由对称性，只需证 $\mu_M$ 被男方 Pareto 偏好于其他每个稳定匹配。只需证：在 $\text{DAA}_M$ 中没有男士被任何可达女士拒绝，从而每个男士匹配到他最偏好的可达对象（可能是自己）。归纳法证。设在 $\text{DAA}_M$ 某步（女士拒绝提议之时），到目前为止无男士被可达女士拒绝过。设此步 $w$ 拒绝 $m$，只需证 $w$ 对 $m$ 不可达。若 $m$ 对 $w$ 不可接受，则 $w$ 对 $m$ 不可达，证毕。若 $m$ 对 $w$ 可接受，则 $w$ 拒绝 $m$ 必因偏向某 $m'$（她已或将与之订婚），$m'\succ_w m$。由归纳假设，$m'$ 严格偏好 $w$ 胜过除迄今拒绝过 $m'$ 者外的任何女士，而那些拒绝者对 $m'$ 不可达。故设存在稳定 $\mu$ 使 $\mu(m)=w$ 且包括 $m'$ 在内人人匹配到可达对象，则 $w\succ_{m'}\mu(m')$，又 $m'\succ_w m$，故 $(w,m')$ 阻塞 $\mu$，与 $\mu$ 稳定矛盾。故无稳定 $\mu$ 使 $\mu(m)=w$，即 $w$ 对 $m$ 不可达。由归纳，$\mu_M$ 下任何拒绝 $m$ 的女士对 $m$ 不可达，对 $\forall m\in M$ 成立。$\blacksquare$

By symmetry, it suffices to prove $\mu_M$ is Pareto preferred by the men to every other stable matching. We only need to show that in $\text{DAA}_M$ no man is ever rejected by an achievable woman, so each man is matched to his most preferred achievable mate (possibly himself). By induction. Assume at a step of $\text{DAA}_M$ (when women reject proposals) that up to now no man has been rejected by an achievable woman. Suppose $w$ rejects $m$ at this step; it suffices to show $w$ is not achievable for $m$. If $m$ is unacceptable to $w$, then $w$ is not achievable for $m$, done. If $m$ is acceptable to $w$, then $w$ rejects $m$ in favor of some $m'$ (already engaged or to become engaged), $m'\succ_w m$. By the induction hypothesis, $m'$ strictly prefers $w$ to any woman except those who have so far rejected $m'$, all of whom are not achievable for $m'$. So suppose there is a stable $\mu$ with $\mu(m)=w$ and everyone including $m'$ matched to an achievable mate; then $w\succ_{m'}\mu(m')$, and also $m'\succ_w m$, so $(w,m')$ blocks $\mu$, contradicting stability of $\mu$. So no stable $\mu$ has $\mu(m)=w$, i.e. $w$ is not achievable for $m$. By induction, any woman who rejects $m$ under $\mu_M$ is not achievable for $m$, for $\forall m\in M$. $\blacksquare$

Important

Theorem 8.4 给定严格偏好，若 $\mu,\mu'$ 均为稳定匹配，则 $\mu$ 被男方 Pareto 偏好于 $\mu'$，当且仅当 $\mu'$ 被女方 Pareto 偏好于 $\mu$。Given strict preferences, if $\mu$ and $\mu'$ are both stable matchings, then $\mu$ is Pareto preferred by men to $\mu'$ if and only if $\mu'$ is Pareto preferred by women to $\mu$.

Note

证明 / Proof (Theorem 8.4)

设 $\mu,\mu'$ 稳定且 $\mu$ 被男方 Pareto 偏好于 $\mu'$，则二者不同 $\mu\ne\mu'$。反证：设 $\mu'$ 不被女方 Pareto 偏好于 $\mu$。由严格偏好，$\mu\ne\mu'$ 不可能所有女士都无差异，故 $\exists w\in W$ 使 $\mu(w)\succ_w\mu'(w)$。因 $\mu'$ 稳定，$\mu'(w)\succsim_w w$，由传递性 $\mu(w)\succ_w\mu'(w)\succsim_w w$，故 $w$ 在 $\mu$ 下非单身。于是 $\exists m\in M$ 使 $m=\mu(w)\ne\mu'(w)$，从而 $w=\mu(m)\ne\mu'(m)$。因男方 Pareto 偏好 $\mu$ 胜 $\mu'$，故 $w=\mu(m)\succ_m\mu'(m)$。现同时有 $w\succ_m\mu'(m)$ 与 $m\succ_w\mu'(w)$，即 $(m,w)$ 阻塞 $\mu'$，与 $\mu'$ 稳定矛盾。$\blacksquare$

Suppose $\mu,\mu'$ stable and $\mu$ Pareto preferred by men to $\mu'$, which implies $\mu\ne\mu'$. By contradiction: suppose $\mu'$ is not Pareto preferred by women to $\mu$. By strict preferences, for $\mu\ne\mu'$ not all women can be indifferent, so $\exists w\in W$ with $\mu(w)\succ_w\mu'(w)$. Since $\mu'$ is stable, $\mu'(w)\succsim_w w$, and by transitivity $\mu(w)\succ_w\mu'(w)\succsim_w w$, so $w$ is not single under $\mu$. So $\exists m\in M$ with $m=\mu(w)\ne\mu'(w)$, hence $w=\mu(m)\ne\mu'(m)$. Since men Pareto prefer $\mu$ to $\mu'$, $w=\mu(m)\succ_m\mu'(m)$. Now both $w\succ_m\mu'(m)$ and $m\succ_w\mu'(w)$ hold, i.e. $(m,w)$ blocks $\mu'$, contradicting stability of $\mu'$. $\blacksquare$

Important

Corollary 8.1（To Theorem 8.3 and 8.4）在所有稳定匹配中，$\mu_M$ 对女方最差、$\mu_W$ 对男方最差：男方 Pareto 偏好任何其他稳定匹配胜过 $\mu_W$，女方 Pareto 偏好任何其他稳定匹配胜过 $\mu_M$。Among all stable matchings, $\mu_M$ is the worst for women and $\mu_W$ is the worst for men: men Pareto prefer any other stable matching to $\mu_W$, and women Pareto prefer any other stable matching to $\mu_M$.

Note

证明 / Proof (Corollary 8.1)

对任意稳定匹配 $\mu$，由 Thm 8.3，$\mu_M\succsim_{\text{all men}}\mu$ 且 $\mu_W\succsim_{\text{all women}}\mu$。由 Thm 8.4，$\mu\succsim_{\text{all women}}\mu_M$ 且 $\mu\succsim_{\text{all men}}\mu_W$，于是 $\mu_M\succsim_{\text{all men}}\mu\succsim_{\text{all men}}\mu_W$ 且 $\mu_W\succsim_{\text{all women}}\mu\succsim_{\text{all women}}\mu_M$。$\blacksquare$

For any stable matching $\mu$, by Thm 8.3, $\mu_M\succsim_{\text{all men}}\mu$ and $\mu_W\succsim_{\text{all women}}\mu$. By Thm 8.4, $\mu\succsim_{\text{all women}}\mu_M$ and $\mu\succsim_{\text{all men}}\mu_W$, giving $\mu_M\succsim_{\text{all men}}\mu\succsim_{\text{all men}}\mu_W$ and $\mu_W\succsim_{\text{all women}}\mu\succsim_{\text{all women}}\mu_M$. $\blacksquare$

严格偏好对 Thm 8.4 成立很重要。下例说明偏好非严格时 Thm 8.4 失败。

Strict preferences are important for Theorem 8.4. The following example shows Theorem 8.4 fails when preferences are not strict.

Important

Example 8.3（Strict preferences important for Theorem 8.4）下列偏好中 $w_1$ 对 $m_1,m_2$ 无差异（并列）。一个稳定匹配 $\mu:m_1\leftrightarrow w_1,m_2\leftrightarrow w_2$；另一稳定匹配 $\mu':m_1\leftrightarrow w_2,m_2\leftrightarrow w_1$。女方 Pareto 偏好 $\mu'$ 胜 $\mu$，但男方并不 Pareto 偏好 $\mu$ 胜 $\mu'$，故 Thm 8.4 失败。In the preferences below $w_1$ is indifferent between $m_1,m_2$ (a tie). One stable match $\mu:m_1\leftrightarrow w_1,m_2\leftrightarrow w_2$; another $\mu':m_1\leftrightarrow w_2,m_2\leftrightarrow w_1$. Women Pareto prefer $\mu'$ to $\mu$, but men do NOT Pareto prefer $\mu$ to $\mu'$, so Theorem 8.4 fails.

$\succ_{m_1}$	$\succ_{m_2}$	$\succ_{w_1}$	$\succ_{w_2}$
$w_1$	$w_1$	$m_1,m_2$	$m_1$
$w_2$	$w_2$		$m_2$

8.5 Non-strategy-proof

在 §9.2 将引入的社会选择设定中，每个匹配结果可视为 $X$ 中的一个社会状态，而算法（如 DAA）是社会选择函数。

注意 DAA 中没有 agent 是独裁者，因稳定匹配要求个体理性：若某"独裁者"在另一侧人人的列表中都排在单身之下，则其偏好无关紧要、他将单身，与他是独裁者矛盾。
如 Gibbard–Satterthwaite 定理（§9.2.3 引入并证明）所述，DAA 作为社会选择函数不防策略：该定理称所有防策略的社会选择函数都是独裁的，而 DAA 不容独裁者。
故在男方提议 DAA 中，男方总有动机沿真实排序如实揭示偏好，而女方须以隐藏真实偏好为策略以求更好结果。女方提议 DAA 中结论相反。

8.5 Non-strategy-proof

In the setting of social choices introduced in §9.2, each matching outcome can be regarded as a social state in $X$, and the algorithms (e.g. DAA) are social choice functions.

Note no agent in DAA is a dictator because stable matching requires individual rationality: if a "dictator" is ranked below staying single on everyone's list on the other side, then his preference won't matter and he will be single, contradicting that he is a dictator.
As stated by the Gibbard–Satterthwaite Theorem (introduced and proved later in §9.2.3), DAA as a social choice function is not strategy-proof: the theorem states all strategy-proof social choice functions are dictatorial, but DAA doesn't allow a dictator.
So in man-proposing DAA, men always have the incentive to reveal their true preferences by going down their real ranking list, but women must have incentives to hide their true preferences as a strategy to get a better result. The flipped fact is true for woman-proposing DAA.

\(\succ_a\)	\(\succ_b\)	\(\succ_c\)	\(\succ_d\)
\(c\)	\(a\)	\(b\)	(not
\(b\)	\(c\)	\(a\)	important)
\(d\)	\(d\)	\(d\)

\(\succ_{m_1}\)	\(\succ_{m_2}\)	\(\succ_{w_1}\)	\(\succ_{w_2}\)
\(w_1\)	\(w_1\)	\(m_1,m_2\)	\(m_1\)
\(w_2\)	\(w_2\)		\(m_2\)