OI-wiki 稳定匹配专题稳定婚姻问题与 Gale–Shapley 延迟接受算法【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki本文是 OI-wiki 图匹配系列中关于稳定匹配stable matching的完整技术指南。它以稳定婚姻问题为切入点系统讲解稳定匹配的形式化模型、可接受偏好与稳定性的严格定义并围绕 1962 年 Gale 与 Shapley 提出的延迟接受算法deferred acceptance algorithm展开先给出算法流程与复杂度分析再结合 OI-wiki 仓库内的 C 参考实现 与配套测试数据 逐行解读实现细节最后深入稳定匹配的四个核心定理存在性、求婚方最优性、格结构、未匹配集合唯一性及其在学院招生、稳定室友、住房分配等变体问题中的应用。读完本文你将能够独立完成稳定婚姻问题的建模、实现与正确性论证并理解稳定匹配理论中偏好驱动与图结构驱动两种匹配范式的本质区别。稳定匹配问题的引入稳定匹配问题stable matching problem是组合优化与合作博弈论中的经典问题。与传统的图论匹配可参考 图的匹配总述其中覆盖二分图与一般图的最大匹配、最大权匹配不同稳定匹配引入了个体偏好和稳定性的限制这使得算法的设计更多地依赖于偏好顺序而非单纯的图结构。在稳定匹配的模型中每个个体对潜在的匹配对象具有一个偏好顺序问题希望在这些个体之间建立一种稳定的匹配关系在一个稳定的匹配中不存在任何一组个体会因为能获得更优的选择而合谋偏离当前的匹配结果。这一性质使得稳定匹配及其相关问题被广泛地应用于劳动力市场、学校录取、医疗资源分配等真实场景——这些场景的共同特点是匹配双方各自有偏好而最终方案必须没有人有动力反悔。在算法竞赛中最常出现的稳定匹配问题是双边市场的一对一匹配即稳定婚姻问题stable marriage problem。本文重点介绍稳定婚姻问题及其求解算法。稳定婚姻问题模型与形式化定义稳定婚姻问题是最早被研究的稳定匹配问题。类比二分图匹配见 二分图最大匹配它可以描述为婚恋市场上的匹配问题假设有男士和女士若干每个人都对异性有一组偏好顺序目标是找到一种匹配方式使得没有一对男女更愿意抛弃各自的匹配对象而选择彼此。问题描述匹配市场由若干男士 $M$ 和若干女士 $W$ 构成。每个人都对异性有严格的偏好顺序对于每位男士 $m\in M$都存在集合 $W\cup{m}$ 上一个严格的全序 $\preceq_m$对于每位女士 $w\in W$都存在集合 $M\cup{w}$ 上一个严格的全序 $\preceq_w$。注意除了在异性之间相互比较之外每个人还会将自身加入到这个偏好顺序中。这表示这个人只会接受与排在自身前面的异性匹配这些异性称为可接受的acceptable。显然不可接受的异性的偏好顺序是无足轻重的原则上只需要给出可接受的异性之间的偏好顺序即可。因此这种存在不可接受异性的偏好也称为列表不完整的偏好preferences with incomplete lists。例子假设 $m$ 是一位男士$w_1,w_2,w_3$ 是三位女士且有偏好关系 $w_1\prec_m m \prec_m w_2\prec_m w_3$ 成立。那么男士 $m$ 相对于和女士 $w_1$ 匹配更喜欢单身相对于单身更喜欢和女士 $w_2$ 匹配相对于和女士 $w_2$ 匹配更喜欢和女士 $w_3$ 匹配。对于男士 $m$女士 $w_1$ 就是不可接受的而女士 $w_2,w_3$ 就是可接受的。匹配与稳定性市场上的一个匹配$\mu:M\cup W\rightarrow M\cup W$ 需要满足如下两条性质只匹配异性或自身对所有 $m\in M$ 都有 $\mu(m)\in W\cup{m}$且对所有 $w\in W$ 都有 $\mu(w)\in W\cup{w}$匹配是相互的对所有 $i\in M\cup W$ 都有 $i \mu(\mu(i))$。一个匹配 $\mu$ 中可能存在两种不稳定因素阻塞个体blocking individual如果存在个体 $i\in M\cup W$ 使得 $\mu(i)\prec_i i$——即相对于当前的匹配对象个体 $i$ 宁愿单身——就称 $i$ 是匹配 $\mu$ 的阻塞个体。阻塞对blocking pair如果存在一对异性 $m\in M$ 和 $w\in W$ 使得 $\mu(m)\prec_m w$ 且 $\mu(w)\prec_w m$——即相对于当前各自的匹配对象男士 $m$ 和女士 $w$ 更希望和对方在一起——就称 $(m,w)$ 是匹配 $\mu$ 的阻塞对。如果一个匹配 $\mu$ 既不存在阻塞个体也不存在阻塞对就称匹配 $\mu$ 是稳定的stable。稳定匹配中所有人都无法破坏当前的局面单身的人找不到愿意同他在一起的人结婚的人既不愿意离婚单身也找不到愿意同他私奔的人。稳定匹配问题就是在问对于任意给定的一组偏好顺序是否都存在一个稳定匹配如果是如何求出这样的稳定匹配Gale–Shapley 延迟接受算法Gale 和 Shapley 在 1962 年提出了延迟接受算法deferred acceptance algorithm可以对任意给定的一组偏好顺序求出一个稳定匹配。因此稳定匹配一定存在。算法流程Gale–Shapley 算法有两个对称的版本分别由男士求婚和女士求婚。以男士求婚的版本为例算法流程如下初始化算法开始时每位女士都视为保留着她对其自身的求婚请求每位男士都标记为活跃的。求婚活跃的男士会向他可接受但是尚未求婚过的女士中最喜欢的那位求婚如果这样的女士不存在就无需进行任何操作。无论求婚与否将所有男士都标记为不活跃的。筛选收到新的求婚请求的女士会将他们与之前保留的求婚请求比较只保留其中最喜欢的那一个可能是她自身并拒绝所有其他的求婚请求。将遭到拒绝的男士恢复标记为活跃的。终止重复前两个步骤直到没有活跃的男士为止。此时女士接受她们当前保留的求婚请求。这样得到的匹配结果就是一个稳定匹配。复杂度由于每位男士向每位女士至多求婚一次算法在 $O(|M||W|)$ 时间内一定会结束。参考实现仓库源码逐段解读OI-wiki 仓库在 docs/graph/code/graph-matching/stable-match/stable-match.cpp 中提供了针对模板题 SPOJ STABLEMPStable Marriage Problem的完整参考实现并声明支持strict preferences with incomplete lists严格偏好、列表可能不完整。下面结合源码剖析其实现技巧。数据结构定义struct StableMatching { int nx, ny; std::vectorstd::vectorint pref_x, pref_y; // Preferences: preferred first, only acceptable. std::vectorint match_x, match_y; // Matching: -1 means unmatched. StableMatching(int nx, int ny) : nx(nx), ny(ny), pref_x(nx), pref_y(ny), match_x(nx, -1), match_y(ny, -1) {} // ... };其中pref_x[i]是男士 $i$求婚方 X的偏好列表越靠前越喜欢且只包含可接受的异性pref_y[j]同理是女士 $j$接受方 Y的偏好列表match_x[i]、match_y[j]记录最终匹配结果-1表示未匹配。这正是文档所述列表不完整的偏好在实现层面的体现不可接受的异性根本不出现在列表中。核心solve()函数void solve() { // Compute Ys ranks over X. std::vectorstd::vectorint ranks(ny, std::vectorint(nx)); for (int j 0; j ! ny; j) { for (int i 0; i ! pref_y[j].size(); i) { ranks[j][pref_y[j][i]] nx - i; } } // Initialize. std::vectorint waitlist(ny); // Best proposal rank for j in Y. std::vectorint ids(nx); // Next j in Y for i in X to propose to. std::queueint q; // Currently active is in X. for (int i 0; i ! nx; i) q.push(i); // Loop. while (!q.empty()) { auto i q.front(); q.pop(); auto j pref_x[i][ids[i]]; if (ranks[j][i] waitlist[j]) { if (waitlist[j]) q.push(pref_y[j][nx - waitlist[j]]); waitlist[j] ranks[j][i]; } else { q.push(i); } } // Output. for (int j 0; j ! ny; j) { if (waitlist[j]) { int i pref_y[j][nx - waitlist[j]]; match_x[i] j; match_y[j] i; } } }这份实现把文档中的四步流程压缩为一个精巧的循环几个关键设计的含义如下预处理女士对男士的排名表ranks对女士 $j$ 的偏好列表按位置 $i$从 0 开始赋值ranks[j][pref_y[j][i]] nx - i。这样排名值越大表示越受偏好第一偏好获得 $nx$末位偏好获得 $1$而未被列入列表的男士自动保持默认值 $0$——恰好对应不可接受的语义。于是女士 $j$ 当前最偏好的求婚者可以直接比较排名值大小得出。waitlist[j]充当候选名单它记录女士 $j$ 当前保留的最佳求婚请求的排名值初始为 $0$语义上即文档所说女士保留着她对其自身的求婚请求宁缺毋滥。排名值为 $0$ 时表示女士当前单身。ids[i]记录每个男士求婚进度男士 $i$ 每次求婚的对象是pref_x[i][ids[i]]即偏好列表中下一个尚未求婚过的女士这与活跃的男士会向他可接受但是尚未求婚过的女士中最喜欢的那位求婚一一对应。q队列维护活跃男士集合初始时所有男士入队。出队的男士求婚一次若被女士拒绝ranks[j][i] waitlist[j]即当前保留者的排名不差于他则重新入队等待下一轮若求婚成功则此前被顶替的男士pref_y[j][nx - waitlist[j]]即当前排名值恰为waitlist[j]的那位会被重新入队恢复为活跃状态。结束条件队列为空即没有活跃的男士此时每位持有请求的女士取出pref_y[j][nx - waitlist[j]]作为最终配偶并写入match_x、match_y。可以验证循环过程中每位男士至多对其偏好列表中的每位女士求婚一次整个循环体至多执行 $O(|M||W|)$ 次与文档给出的复杂度上界一致。输入输出格式solve()与main()输入第一行为测试组数 $T$每组数据第一行为 $n$男女各 $n$ 人随后 $n$ 行是女士Y 侧的偏好——每行先给出行首序号读取后丢弃再给出 $n$ 个偏好值再 $n$ 行是男士X 侧的偏好同样每行首个数被丢弃。所有编号按 $1$ 基输入、内部转为 $0$ 基x - 1。输出按男士编号升序打印(i1) (match_x[i]1)即每位男士匹配到的女士编号。运行示例与测试数据验证仓库在 docs/graph/examples/graph-matching/stable-match/stable-match.in 中提供了两组测试数据对应的期望输出在 docs/graph/examples/graph-matching/stable-match/stable-match.ans。以第一组$n4$为例女士的偏好列表为女士偏好1 表示最喜欢W14 3 1 2W22 1 3 4W31 3 4 2W44 3 1 2男士的偏好列表为男士偏好1 表示最喜欢M13 2 4 1M22 3 1 4M33 1 2 4M43 2 4 1按男士求婚的 Gale–Shapley 算法运行第一轮 M1、M2、M3、M4 分别向各自第一偏好的女士求婚其中 M1 与 M2 暂时被接受、M3 和 M4 被 W3 拒绝随后被拒绝的男士依次转向下一偏好求婚……最终得到期望输出1 3 2 2 3 1 4 4即 M1–W3、M2–W2、M3–W1、M4–W4。读者可以对照上面的源码逐步推演验证实现与算法流程完全吻合。稳定匹配的性质稳定匹配有着良好的理论性质。首先Gale–Shapley 算法构造性地证明了稳定匹配一定存在。定理 1存在性Gale and Shapley, 1962定理 1Gale–Shapley 算法得到的是一个稳定匹配。因此稳定匹配存在。证明思路男士不会对他不接受的女士求婚女士也会立即拒绝她不接受的男士的求婚。因此最终互相匹配的男士和女士一定是彼此接受的不可能存在阻塞个体。要证明它是稳定匹配只需要说明不存在阻塞对。反证法。假设 $(m,w)$ 是一个阻塞对。那么在男士 $m$ 向 $\mu(m)$ 求婚之前他一定已经向 $w$ 求过婚。但是既然女士 $w$ 拒绝了 $m$她一定是收到了她更喜欢的人 $m$ 的求婚请求。如果 $m\neq \mu(w)$那么女士 $w$ 相对于 $m$ 只会更喜欢 $\mu(w)$。由此相对于 $m$女士 $w$ 一定更喜欢最终的匹配对象 $\mu(w)$。这与 $(m,w)$ 是阻塞对矛盾。所以匹配是稳定的。推论如果 $|M||W|$ 且所有异性都是可接受的那么存在一个稳定的完美匹配。定理 2求婚方最优性Gale and Shapley, 1962Gale–Shapley 算法中可以由男士求婚也可以由女士求婚。一般情况下这两个版本的算法得到的稳定匹配并不相同。事实上由男士求婚的 Gale–Shapley 算法得到的稳定匹配是所有稳定匹配中对于男士最有利的反之亦然由女士求婚的版本对所有女士最有利。定理 2设 $\mu_M$ 和 $\mu_W$ 分别是由男士和女士求婚的 Gale–Shapley 算法得到的稳定匹配。对于任何稳定匹配 $\mu$都有 $\mu(m)\preceq_m\mu_M(m)$ 对所有 $m\in M$ 成立且 $\mu(w)\preceq_w\mu_W(w)$ 对所有 $w\in W$ 成立。证明思路根据对称性只需要证明 $\mu(m)\preceq_m\mu_M(m)$ 对所有 $m\in M$ 成立。为此考虑由男士求婚的 Gale–Shapley 算法记 $k(m,w)$ 为女士 $w$ 拒绝男士 $m$ 的求婚时算法进行到的轮次这个轮次对所有满足 $\mu_M(m)\prec_m w$ 的 $(m,w)$ 都是良定义的。假设 $\mu_M$ 并非对所有男士都最有利即存在稳定匹配 $\mu$ 和男士 $m\in M$ 使得 $\mu_M(m)\prec_m\mu(m)$。由于 $\mu_M$ 稳定有 $m\preceq_m\mu_M(m)\prec_m\mu(m)$所以 $\mu(m)$ 是女士$k(m,\mu(m))$ 良定义。不妨设 $m$ 是所有这样的男士中 $k(m,\mu(m))$ 最小的那个。设算法中女士 $w\mu(m)$ 拒绝 $m$ 时保留的是男士 $m$ 的求婚请求即 $m\mu(w)\prec_w m$。由于 $\mu$ 稳定$(w,m)$ 不能是阻塞对且 $\mu(m)\neq w$所以 $w\prec_{m}\mu(m)$。又因为算法中女士 $w$ 未必会保留 $m$ 到最后所以 $\mu_M(m)\preceq_{m}w\prec_{m}\mu(m)$。此时 $k(m,\mu(m))$ 良定义且由于 $w\prec_{m}\mu(m)$女士 $\mu(m)$ 拒绝 $m$ 之后 $w$ 才会保留 $m$即 $k(m,\mu(m)) k(m,\mu(m))$与 $m$ 的选取矛盾。故 $\mu_M$ 是对所有男士最有利的稳定匹配。稳定匹配的分解与 Knuth 引理一个匹配市场可能存在指数级数量的稳定匹配。设 $\mathcal S$ 为全体稳定匹配的集合在这个集合上可以定义两个偏序$\mu_1\preceq_M\mu_2$当且仅当 $\mu_1(m)\preceq_m\mu_2(m)$ 对所有 $m\in M$ 都成立$\mu_1\preceq_W\mu_2$当且仅当 $\mu_1(w)\preceq_w\mu_2(w)$ 对所有 $w\in W$ 都成立。这两个偏序分别表示匹配结果对于所有男士和所有女士都更优。一般地两个稳定匹配未必是可比的。但是任意两个稳定匹配 $\mu_1,\mu_2$ 都诱导如下所示的分解使得分解所得的三个部分中分别成立 $\mu_1\preceq_M\mu_2$、$\mu_1\mu_2$ 和 $\mu_2\preceq_M\mu_1$。注意尽管图中没有直接绘制出但 $\mu_1\mu_2$ 的那一部分其实包含了匹配到自身即未匹配的情形。这一分解依赖于如下的引理引理Knuth, 1976设 $\mu_1$ 和 $\mu_2$ 是两个稳定匹配。设 $M(\mu_i){m\in M : \mu_j(m)\prec_m\mu_i(m)}$ 和 $W(\mu_i){w\in W:\mu_j(w)\prec_w\mu_i(w)}$ 分别为更偏好 $\mu_i$ 中匹配结果的男士和女士的集合$i,j1,2$ 且 $i\neq j$。那么$\mu_1$ 和 $\mu_2$ 都是 $M(\mu_1)$ 与 $W(\mu_2)$ 之间的双射也都是 $M(\mu_2)$ 与 $W(\mu_1)$ 之间的双射。证明思路设 $m\in M(\mu_1)$。由于 $m\preceq_m \mu_2(m)\prec_m\mu_1(m)$所以 $\mu_1(m)\in W$。令 $w\mu_1(m)$。因为 $\mu_2(w)\neq m$而 $\mu_2(w)\prec_w m$ 又意味着 $(m,w)$ 是 $\mu_2$ 的阻塞对所以 $\mu_1(w)m\prec_w\mu_2(w)$即 $w\in W(\mu_2)$。这说明 $\mu_1(M(\mu_1))\subseteq W(\mu_2)$。由对称性还可建立 $\mu_2(W(\mu_2))\subseteq M(\mu_1)$。由于 $\mu_1$、$\mu_2$ 都是单射所以 $|M(\mu_1)||W(\mu_2)|$ 且两个映射都是满射从而都是双射。同理可证另一组。定理 3稳定匹配的格结构Conway and Knuth, 1976上述引理说明偏序集 $(\mathcal S,\preceq_M)$ 和 $(\mathcal S,\preceq_W)$ 互为对偶。而且在每个偏序下集合 $\mathcal S$ 都构成一个格。因为 $\mathcal S$ 是有限的这两个格一定存在最大元和最小元——这两个最值元素分别就是前文提到的两个版本的 Gale–Shapley 算法所得到的稳定匹配。定理 3偏序集 $(\mathcal S,\preceq_M)$ 和 $(\mathcal S,\preceq_W)$ 是相互对偶的格。而且$\mu_M$ 和 $\mu_W$ 分别是 $(\mathcal S,\preceq_M)$ 的最大元和最小元也分别是 $(\mathcal S,\preceq_W)$ 的最小元和最大元。证明思路根据引理容易说明两个偏序集对偶若 $\mu_1\preceq_M\mu_2$则 $M(\mu_1)\varnothing$由引理得 $W(\mu_2)\varnothing$此即 $\mu_2\preceq_W\mu_1$反之亦然。结合定理 2 即得 $\mu_M$、$\mu_W$ 是两个偏序集的最值元素。还需证明两个偏序集是格。由对称性只需证明 $(\mathcal S,\preceq_M)$ 是格再根据交、并运算的对称性只需证明稳定匹配的并仍是稳定匹配。形式化地对于任意 $\mu_1,\mu_2\in\mathcal S$需要证明对所有 $m\in M$ 满足 $\mu(m)\mu_1(m)\lor_m\mu_2(m)$ 的匹配 $\mu\mu_1\lor_M\mu_2$ 是稳定匹配其中 $\lor_m$ 是全序 $\preceq_m$ 下的并运算即两者中 $m$ 更喜欢的那个。仍采用引理中的记号对 $i\in M(\mu_1)\cup W(\mu_2)$有 $\mu(i)\mu_1(i)$否则 $\mu(i)\mu_2(i)$。由于 $\mu_1$、$\mu_2$ 都稳定、不存在阻塞个体$\mu$ 也同样如此。假设 $(m,w)$ 是 $\mu$ 的阻塞对若 $m\in M(\mu_1)$则 $\mu_2(m)\prec_m\mu_1(m)\mu(m)\prec_m w$此时若 $w\in W(\mu_2)$则 $\mu_1(w)\mu(w)\prec_w m$$(m,w)$ 是 $\mu_1$ 的阻塞对矛盾否则 $w\in W\setminus W(\mu_2)$则 $\mu_2(w)\mu(w)\prec_w m$$(m,w)$ 是 $\mu_2$ 的阻塞对也矛盾。$m\in M\setminus M(\mu_1)$ 的情形只能导出同样的矛盾。由反证法这样的阻塞对不存在$\mu_1\lor_M\mu_2$ 是稳定匹配命题得证。定理 4未匹配集合的唯一性McVitie and Wilson, 1970最后在所有稳定匹配中未匹配的男士和女士的集合都是固定的。定理 4设 $\mu_1$ 和 $\mu_2$ 是两个稳定匹配那么 $\mu_1$ 和 $\mu_2$ 的不动点集合相同。证明思路假设存在 $m\in M$ 使得 $\mu_1(m)m$ 且 $\mu_2(m)\neq m$ 对某组 $\mu_1,\mu_2\in\mathcal S$ 成立。此时有 $m\in M(\mu_2)$。由引理可知 $m\mu_1(m)\in W(\mu_1)$这与 $m\in M$ 矛盾。所以不存在这样的 $m\in M$同理也不存在这样的 $w\in W$。故任意两个稳定匹配的不动点集合必然相同。策略性质除了本节讨论的这些性质外稳定匹配还有一些良好的策略性质——例如个体通过虚假申报偏好能获益的程度是有限的。关于这些内容可以参见文末提供的文献。相关变体问题稳定匹配及其类似问题还出现在许多其他情境中。学院招生问题college admissions problem如果将稳定婚姻问题中一对一的限制放宽允许多对一匹配就得到了学院招生问题。此时一个学院可以招收多名学生只要不超过招生限额但一名学生仍然只允许进入至多一个学院学习。类似的情景还出现在公司招聘、医院招收实习医生等场景中。对于这类问题Gale–Shapley 算法仍然适用。例如由学生申请的 Gale–Shapley 算法中学院可以维持一个不超过限额长度的候选名单waitlist每次只要在申请数量超过限额时拒绝最差学生的申请即可。前文关于稳定匹配性质的讨论对这一场景仍然适用。特别地定理 4 对应的版本是在所有稳定匹配中学校能够招到的学生人数是固定的。这也称为乡村医院定理rural hospitals theorem——因为它意味着无论如何更改匹配机制只要得到的结果是稳定的那些招不满医生的乡村医院永远招不到人。稳定室友问题stable roommates problem如果将稳定婚姻问题中只能匹配异性的条件放宽就得到了稳定室友问题。此时初始只有若干名学生需要两两结对成为室友。对于这类问题稳定匹配未必存在。Irving 在 1985 年提出了可以在 $O(n^2)$ 时间内解决该问题的算法。住房分配问题house allocation problem稳定婚姻问题中两组个体互相有偏好所以是双边匹配问题。除此之外还可以考虑单边匹配问题。一个常见的场景是住房分配问题有 $n$ 名居民各自拥有一套住房每人对所有住房有一个严格偏好。现在要将这些住房重新分配给这些居民要求每名居民都不能分配到比初始更差的住房且不存在任何数量的居民可以私自交换房产、得到更满意的结局。对于这一问题可以通过Top Trading Cycle 算法在 $O(n^2)$ 时间内解决。这类问题还出现在肾移植等场景中。竞赛习题以下题目可用于检验对稳定匹配模型与算法的掌握程度题目在 OI-wiki 原文档的习题列表中亦有收录UOJ 41.【清华集训 2014】矩阵变换需要将稳定匹配的思想迁移到矩阵行变换的背景下识别出偏好与稳定性的对应关系从而套用 Gale–Shapley 式论证。Codeforces 1147 F. Zigzag Game将稳定匹配嵌入博弈论场景是稳定婚姻问题与游戏策略结合的进阶练习。参考资料与延伸阅读本主题的核心参考文献bibliographic 信息整理自原文档可据此在学术数据库中检索原文Gale, David, and Lloyd S. Shapley. College admissions and the stability of marriage.The American mathematical monthly69, no. 1 (1962): 9-15.延迟接受算法的原始论文Irving, Robert W. An efficient algorithm for the stable roommates problem.Journal of Algorithms6, no. 4 (1985): 577-595.Knuth, Donald Ervin. Marriages stables. Technical report (1976).McVitie, David G., and Leslie B. Wilson. Stable marriage assignment for unequal sets.BIT Numerical Mathematics10, no. 3 (1970): 295-309.Roth, Alvin E., and Marilda Sotomayor. Two-sided matching.Handbook of game theory with economic applications1 (1992): 485-541.Roth, Alvin E. Deferred acceptance algorithms: History, theory, practice, and open questions.International Journal of Game Theory36, no. 3-4 (2008): 537-569.关于稳定匹配的理论与实证设计可参见 2012 年诺贝尔经济学奖的科普材料Shapley 与 Roth 因稳定匹配理论与市场设计实践获奖。仓库内延伸阅读稳定匹配属于匹配理论中偏好驱动的一支与之对照的图结构驱动匹配算法增广路、交错树、Hall 定理、Tutte 定理、二分图最大匹配与最大权匹配、一般图匹配等参见 图的匹配总述、二分图最大匹配 与 二分图最大权匹配文中格论与对偶偏序的术语定义参见 偏序关系与格。【免费下载链接】OI-wiki:star2: Wiki of OI / ICPC for everyone. 某大型游戏线上攻略内含炫酷算术魔法项目地址: https://gitcode.com/GitHub_Trending/oi/OI-wiki创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考