第11章机制设计与市场设计
引言
第10章提问：给定偏好和禀赋，竞争性市场能否产生有效结果？答案——是的，在福利定理条件下——将市场机制视为既定。本章反转这个问题：给定期望结果，我们能否设计一个机制来实现它？
机制设计常被称为"逆向博弈论"。不是预测博弈的结果，而是设计博弈以产生期望结果。市场设计将这些思想应用于现实制度——拍卖、匹配市场、频谱分配、肾脏交换。
学完本章后，你将能够：
- 阐述显示原理并解释它如何简化机制设计
- 定义激励相容并将其应用于机制设计问题
- 推导最优拍卖（迈尔森）和收入等价
- 阐述吉巴德-萨特斯韦特不可能性结果
- 将Gale-Shapley算法应用于匹配市场
- 评估现实市场制度的设计
前置知识：第7章（博弈论基础、纳什均衡）和第10章（福利定理、一般均衡）。
重要文献：Myerson (1981); Vickrey (1961); Clarke (1971); Groves (1973); Gale & Shapley (1962); Roth (2002); Milgrom (2004)。
11.1 社会选择与显示原理
社会选择函数
社会选择函数（SCF）。 从代理人的类型（私有信息 — 估值、偏好）到结果的映射：$$f: \Theta_1 \times \cdots \times \Theta_n \to \mathcal{A}$$，其中 $\Theta_i$ 是代理人 $i$ 的类型空间，$\mathcal{A}$ 是可能分配的集合。
挑战在于：代理人的类型是私人信息。我们如何让他们如实披露其类型？
机制
机制。 一个由消息（策略）空间 $\mathcal{M}_i$ 和结果函数 $g: \mathcal{M}_1 \times \cdots \times \mathcal{M}_n \to \mathcal{A}$ 组成的对 $(\mathcal{M}, g)$。如果在均衡中机制的结果等于 $f(\theta)$，则该机制实现了社会选择函数 $f$。
图 11.1.机制设计时间线。
- 自然将类型 $\theta_i$ 分配给代理人（私人的）
- 代理人向机制发送消息 $m_i$
- 机制将消息映射为分配+转移：$g(m_1, \ldots, m_n) = (a, t_1, \ldots, t_n)$
机制设计者选择规则（消息空间和结果函数）以实现期望的社会选择函数。
显示原理
显示原理。 任何由任何机制在任何均衡概念下可实现的社会选择函数，也可以由一个直接机制实现，其中代理人如实报告其类型。
直接机制。 每个代理人的消息空间等于其类型空间（$\mathcal{M}_i = \Theta_i$）的机制。代理人只需直接报告其私有信息。显示原理保证仅关注直接机制不会损失一般性。
激励相容（IC）。 如果如实报告是每个代理人的均衡策略——没有代理人能通过虚报其类型而获益——则机制是激励相容的。激励相容有两种强度：占优策略（DSIC）和贝叶斯（BIC）。
占优策略激励相容（DSIC）。 对每个代理人来说，真实报告是最优的，无论其他代理人如何报告。DSIC 机制对关于他人行为的信念具有稳健性：$U_i(\theta_i, \theta_i) \geq U_i(\hat{\theta}_i, \theta_i)$ 对所有 $\hat{\theta}_i$ 和所有 $\theta_{-i}$ 成立。
贝叶斯激励相容（BIC）。 在对他人类型的期望下，真实报告是最优的（假设他人也真实报告）。比 DSIC 弱但允许更丰富的可实现结果集。要求代理人对类型分布有正确的信念。
直接机制要求每个代理人简单地报告其类型（私人信息）。如果如实报告是均衡策略——没有代理人能从撒谎中获益——则该机制是激励相容的（IC）。
这是机制设计中最强大的简化——可以说是整个经济理论中最强大的简化。原则上，可能的机制空间是无限大的。拍卖可以有任意数量的轮次、任意竞标规则、任意支付公式。匹配算法可以以任何可想象的方式运行。在所有可能的机制中搜索最优者似乎毫无希望。
显示原理指出：你不必搜索。无论任何机制能实现什么结果，一个直接机制（只需要求每个人如实报告）可以实现相同的结果。因此，机制设计问题简化为：找到最优的分配规则和支付规则作为报告类型的函数，受制于如实报告是最优的约束。这将一个无限广泛的搜索转化为一个明确定义的优化问题。
Dominant-strategy incentive compatible (DSIC): $$U_i(\theta_i, \theta_i) \geq U_i(\hat{\theta}_i, \theta_i) \quad \forall \hat{\theta}_i, \forall \theta_{-i}$$
(Eq. 11.1)
Bayesian incentive compatible (BIC): $$E_{\theta_{-i}}[U_i(\theta_i, \theta_i)] \geq E_{\theta_{-i}}[U_i(\hat{\theta}_i, \theta_i)] \quad \forall \hat{\theta}_i$$
(Eq. 11.2)
DSIC更强但更难实现。BIC更弱但允许更多机制。
11.2 吉巴德-萨特斯韦特定理
吉巴德-萨特斯韦特定理。 如果至少有 3 个备选方案且社会选择函数是满射的（每个备选方案都可达），则唯一的 DSIC 社会选择函数是独裁 — 一个代理人的偏好决定结果，与其他人无关。
这是机制设计中对应阿罗不可能定理的结果。它表明，在一般社会选择设定下，没有非独裁机制能在占优策略中引出真实偏好。
突破口：限制定义域。在准线性偏好（$U_i = v_i(a) + t_i$，其中 $t_i$ 是货币转移）下，吉巴德-萨特斯韦特障碍被突破。VCG机制通过转移支付实现效率和DSIC。
11.3 VCG机制
VCG机制。 VCG 机制有效分配（$\max \sum_i v_i$）并向每个代理人收取等于其对他人施加的外部性的支付。真实报告是占优策略，因为每个代理人的支付仅取决于他人的报告。
维克里拍卖（第二价格密封投标）。 单一物品的最简单 VCG 机制：最高出价者赢得物品并支付第二高出价。真实出价是占优策略，因为支付与获胜者的出价无关。由 Vickrey（1961）提出。
克拉克枢纽规则。 VCG 支付公式：代理人 $i$ 支付没有 $i$ 时其他人能达到的社会福利与有 $i$ 时其他人实际达到的社会福利之差。每个代理人的“关键性”取决于其对他人结果的改变程度。
维克里-克拉克-格罗夫斯（VCG）机制通过货币转移，以如实报告为占优策略实现有效分配。
有效分配：$a^*(\theta) = \arg\max_a \sum_i v_i(a, \theta_i)$ — 最大化总价值。
VCG payment for agent $i$: $$t_i(\theta) = \sum_{j \neq i} v_j(a^*(\theta_{-i}), \theta_j) - \sum_{j \neq i} v_j(a^*(\theta), \theta_j)$$
(Eq. 11.3)
代理人 $i$ 支付她对他人施加的外部性——有她和没有她时其他人福利的差额。
为什么如实报告是占优策略？在如实报告下，代理人 $i$ 的收益为：
$$v_i(a^*(\theta)) + t_i = v_i(a^*(\theta)) + \sum_{j \neq i} v_j(a^*(\theta_{-i})) - \sum_{j \neq i} v_j(a^*(\theta))$$
这简化为 $\sum_j v_j(a^*(\theta)) - \sum_{j \neq i} v_j(a^*(\theta_{-i}))$。第二项不依赖于 $i$ 的报告。因此 $i$ 通过选择报告来最大化 $\sum_j v_j(a^*(\theta))$ 以最大化其收益——这恰好在她如实报告时发生，因为 $a^*$ 已经最大化了总价值。
互动：VCG支付计算器
输入代理人对单一不可分割物品的估值。计算器计算VCG支付（对单物品等同于第二价格拍卖）。
Click "Compute" to see results.
例 11.1 — 公共物品的VCG
三位市民对一座桥的估值分别为 $v_1 = 30$、$v_2 = 25$、$v_3 = 15$。成本为 $C = 60$。
若 $\sum v_i > C$ 则建造：\$10 > 60$ → 是。
克拉克税支付：
- $t_1 = C - (v_2 + v_3) = 60 - 40 = 20$（代理人1必须补足差额）
- $t_2 = C - (v_1 + v_3) = 60 - 45 = 15$
- $t_3 = C - (v_1 + v_2) = 60 - 55 = 5$
总收取：\$10 + 15 + 5 = 40 < 60$。存在20的预算赤字——VCG通常不能实现预算平衡。每个代理人支付其"枢纽"贡献。
11.4 最优拍卖与收入等价
拍卖形式
| 形式 | 规则 | 获胜者支付 |
|---|
| 英式（升序） | 竞标者提高出价；最后竞标者获胜 | 第二高价值（近似） |
| 荷兰式（降序） | 价格下降直到有人认领 | 其出价 |
| 第一价格密封投标 | 最高出价获胜 | 其出价 |
| 第二价格密封投标（维克里） | 最高出价获胜 | 第二高出价 |
维克里拍卖（第二价格密封投标）是DSIC的：每个竞标者的占优策略是按其真实价值 $v_i$ 出价。高于 $v_i$ 出价有以高于价值的价格中标的风险；低于 $v_i$ 出价有在第二高出价低于 $v_i$ 时错失的风险。
收入等价
收入等价定理（Myerson, 1981）。 如果竞标者是风险中性的，具有独立私人估值且从相同分布抽取，则任何满足以下条件的拍卖机制：(a) 将物品分配给估值最高的竞标者，(b) 给予估值最低的竞标者零期望收益 — 产生相同的期望收入。
这是一个惊人的结果。它表明拍卖形式之间看似巨大的差异——公开与密封、升序与降序、第一价格与第二价格——在这些条件下对期望收入是无关的。
收入等价何时失效：
- 风险厌恶竞标者：在第一价格拍卖中出价更激进 → 第一价格拍卖收入更高
- 相关价值："赢者诅咒"在不同形式中对行为的影响不同
- 非对称竞标者：不同的价值分布打破等价
- 预算约束：资金受限的竞标者可能无法按真实价值出价
互动：拍卖模拟器
设置竞标者数量及其价值分布。运行单次拍卖查看个别结果，或运行100轮观察收入等价（各种形式的平均收入趋于一致）。调整风险厌恶滑块以打破等价。
Click a button to run the auction simulator.
迈尔森最优拍卖
虚拟价值。 竞标者的虚拟价值 $\psi(\theta_i) = \theta_i - (1 - F(\theta_i))/f(\theta_i)$ 将真实价值向下调整，以考虑卖方为激励真实出价而必须留给的信息租金。最优拍卖最大化期望虚拟剩余而非期望真实剩余。
最优保留价。 即使物品对卖方价值为零，卖方也拒绝出售的最低出价。设定在虚拟价值等于零处：$\psi(r^*) = 0$。最优保留价在销售概率和从高价值竞标者提取的收入之间进行权衡。
当卖方想要最大化收入（而非效率）时，迈尔森证明了最优机制使用虚拟价值：
$$\psi(\theta_i) = \theta_i - \frac{1 - F(\theta_i)}{f(\theta_i)}$$
(Eq. 11.4)
其中 $F$ 是竞标者价值分布的CDF，$f$ 是PDF。
$$\text{Allocate to highest virtual value if } \psi(\theta_i) > 0$$
(Eq. 11.5)
最优拍卖将物品分配给虚拟价值最高的竞标者，前提是其为正值。如果所有虚拟价值均为负，卖方保留物品。这意味着一个保留价——卖方设置等于 $\psi^{-1}(0)$ 的最低出价。
$$r^*: \quad \psi(r^*) = r^* - \frac{1 - F(r^*)}{f(r^*)} = 0$$
(Eq. 11.6)
$$\text{All mechanisms with the same allocation rule yield the same expected revenue}$$
(Eq. 11.7)
例 11.2 — 最优保留价
价值在 $[0, 1]$ 上均匀分布：$F(\theta) = \theta$，$f(\theta) = 1$。
$\psi(\theta) = \theta - (1-\theta)/1 = 2\theta - 1$
$\psi(\theta) = 0 \implies \theta = 1/2$。最优保留价 = \$1/2$。
带保留价 \$1/2$ 的第二价格拍卖是最优的：只有当至少一个竞标者的估值超过 \$1/2$ 时，物品才会售出。
互动：迈尔森最优拍卖
对于从Uniform$[0, V_{\max}]$中抽取的价值，虚拟价值为 $\psi(\theta) = 2\theta - V_{\max}$。拖动保留价滑块。收入曲线显示期望收入作为保留价的函数。最优保留价（最大化期望收入）被突出显示。
Loading...
例 11.4 — 激励相容检验
政府向两家公司之一分配许可证。公司 $i$ 的私人价值 $\theta_i \in \{L, H\} = \{10, 50\}$，各以等概率出现。
提议机制：将许可证分配给报告更高价值的公司；平局时分配给公司1。支付：获胜者支付30。
检验高价值公司（$\theta = 50$）的IC：
- 如实报告（$H$）：以3/4概率获胜（对手为$L$或平局时获胜）。收益 = \$1/4 \times (50 - 30) = 15$。
- 报告$L$：仅当对手也报告$L$且你是企业1时获胜，否则失败。期望收益 $\leq 1/4 \times 20 = 5$。
如实报告更优。IC对类型 $H$ 成立。
检验低价值公司（$\theta = 10$）的IC：
- 如实报告（$L$）：很可能失败。期望收益 $\approx 0$。
- 报告$H$：以3/4概率获胜但支付30 > 10。收益 = \$1/4 \times (10 - 30) = -15$。
如实报告更优。IC对类型 $L$ 成立。该机制是激励相容的。
例 11.5 — 收入等价验证
两个竞标者的价值独立地从 $U[0, 100]$ 中抽取。
第二价格拍卖：期望收入 = $E[\text{2nd highest value}] = 100/3 \approx 33.33$。
第一价格拍卖：2个竞标者的最优出价：$b(\theta) = \theta/2$。期望收入 = $E[\max(b_1, b_2)] = E[\max(\theta_1/2, \theta_2/2)] = E[\max(\theta_1, \theta_2)]/2 = (200/3)/2 = 100/3 \approx 33.33$。
两种形式都产生 \$100/3$ 的期望收入，验证了收入等价。第一价格拍卖产生较低的收入波动（每个获胜者恰好支付其价值的一半），而第二价格拍卖的波动较高（支付取决于第二高价值，可能变化很大）。
迈尔森-萨特斯韦特不可能性
迈尔森-萨特斯韦特定理（1983）。 在具有私有信息的双边交易中 — 一个买方和一个卖方，各自只知道自己的估值 — 不存在同时实现以下四项的机制：- 个体理性 (IR)：双方自愿参与
- 激励相容 (IC)：双方真实报告
- 预算平衡 (BB)：无需外部补贴
- 效率：当且仅当 $v_B > c_S$ 时发生交易
直觉：卖方想要夸大其成本（以获取更高价格）。买方想要低报其价值（以少付款）。激励相容要求向双方留下"信息租金"。这些租金成本高昂，在预算平衡下，没有足够的剩余来支付双方的租金并确保所有有效交易发生。
私人信息下的现实谈判——工资谈判、二手车购买、并购交易——总是涉及某些低效率。发布价格、声誉系统和标准化合同等制度缓解了这一问题，但无法完全消除。
11.5 匹配市场
市场设计。 经济学中设计现实世界制度和分配机制的分支，应用机制设计和匹配理论解决实际问题。关键应用包括医学住院医师匹配 (NRMP)、学校选择、肾脏交换和频谱拍卖。Roth 称之为“经济学家作为工程师”。
某些物品不能通过价格分配——我们不应该（或不该）出售学校入学名额、器官移植或住院医师职位。匹配市场使用算法替代。
Gale-Shapley延迟接受算法
稳定匹配。 一种匹配，其中没有未匹配的一对双方都更喜欢对方而非当前的匹配对象。稳定性确保没有“私奔” — 没有一对有动机和能力偏离分配的匹配。
延迟接受算法。 用于找到稳定匹配的 Gale-Shapley 算法：提议方按偏好顺序提出要约，回应方暂时持有最佳要约并拒绝其余，被拒绝的提议方转向下一个选择。算法在最多 $n^2$ 轮内终止。
提议方最优稳定匹配。 当一方在延迟接受算法中提议时产生的稳定匹配。它是提议方的最似稳定匹配和回应方的最差稳定匹配。这种不对称性意味着谁提议具有重大的分配后果。
策略防护性。 如果真实报告对每个参与者都是占优策略，则机制是策略防谋的。延迟接受算法对提议方是策略防谋的，但对回应方不是。
设定： 市场的两方（例如，学生和学校）。每个代理人对另一方进行排名。
算法（提议方最优版本）：- 每个提议方向其排名第一的对象提议
- 每个回应方暂时接受最佳提议并拒绝其余
- 被拒绝的提议方向其下一个选择提议
- 重复直到没有拒绝发生
$$\text{GS terminates in } \leq n^2 \text{ rounds and produces the proposer-optimal stable matching}$$
(Eq. 11.8)
定理（Gale & Shapley, 1962）。该算法在最多 $n^2$ 轮内终止，并产生稳定匹配——没有未匹配的配对双方都偏好对方而非其当前匹配。
性质：
- 稳定性：没有未匹配的配对双方都偏好对方而非其指定匹配——没有"私奔"。
- 提议方最优：在所有稳定匹配中，提议方最优版本找到对提议方最好的那个——也是对回应方最差的。
- 对提议方策略防护：如实披露偏好是提议方的占优策略。
- 对回应方非策略防护：回应方有时可以通过虚报偏好获益。
互动：Gale-Shapley逐步演示
输入学生和学校的偏好列表。算法动画展示每一轮：提议、暂时接受和拒绝。以逗号分隔的名称输入偏好（例如"W,X,Y,Z"）。
例 11.3 — 四名学生的Gale-Shapley
四名学生（A、B、C、D）和四所学校（W、X、Y、Z）。学生提议。
| 学生 | 偏好 | 学校 | 偏好 |
|---|
| A | W > X > Y > Z | W | B > A > D > C |
| B | X > W > Y > Z | X | A > B > C > D |
| C | W > Y > X > Z | Y | C > D > A > B |
| D | Y > W > X > Z | Z | D > C > B > A |
最终匹配：A-W、B-X、C-Y、D-Z。这是稳定的：没有配对想要偏离。使用上面的互动工具逐步验证。
互动：提议方优势
分别运行学生提议和学校提议的Gale-Shapley。比较两个稳定匹配。提议方总是获得其最优稳定匹配；回应方获得其最差稳定匹配。
现实世界的市场设计
- 住院医师匹配（NRMP）：使用Roth重新设计的Gale-Shapley版本。学生提议。该匹配每年处理约40,000个职位。
- 择校（波士顿、纽约）：策略防护机制取代了惩罚诚实报告的可操纵系统。
- 肾脏交换：Roth、Sönmez和Ünver设计了交换协议，允许不兼容的供体-患者配对交换供体。
- 频谱拍卖：Milgrom和Wilson为FCC设计了组合拍卖。2017年的激励拍卖筹集了198亿美元。
阿尔文·罗斯（2012年诺贝尔奖，与劳埃德·沙普利共享）将此描述为"经济学家即工程师"——运用经济理论不仅解释世界，还设计改善人们生活的现实制度。
更广泛的启示：市场不是自发产生的自然物体。它们是被设计的制度——决定谁获得什么、以什么价格、通过什么过程的规则、算法和执行机制。设计至关重要。
线索案例：Maya的企业
该市决定拍卖在市中心黄金地段经营柠檬水摊的专营权。三位潜在供应商：Maya（$v_M = 50$/天）、Nate（$v_N = 35$/天）、Olivia（$v_O = 20$/天）。价值从 $U[0, 60]$ 中抽取。
第二价格拍卖（维克里）：占优策略是如实竞标。Maya出价50，Nate出价35，Olivia出价20。Maya获胜，支付35。
最优拍卖（迈尔森）：虚拟价值，其中 $F(\theta) = \theta/60$，$f(\theta) = 1/60$：
$\psi(\theta) = \theta - (60 - \theta) = 2\theta - 60$
保留价：$\psi(\theta) = 0 \implies \theta = 30$。
Maya的虚拟价值：\$1(50) - 60 = 40$。Nate的：\$10$。Olivia的：$-20$（被最优拍卖排除）。
在保留价为30的第二价格拍卖中：Maya获胜，支付 $\max(35, 30) = 35$。
历史视角
Roth的"经济学家即工程师"。阿尔文·罗斯（2012年诺贝尔奖）将机制设计从纯理论转化为重新设计真实市场的实用学科。他的工作表明，市场是被设计的制度，而非自然现象。
全国住院医师匹配项目（NRMP）：Roth诊断了原始住院医师匹配失败的原因（不稳定性、策略操纵），并使用延迟接受算法重新设计。新系统每年匹配约40,000名住院医师。
肾脏交换：Roth、Sonmez和Unver设计了交换协议，允许不兼容的供体-患者配对通过移植链交换供体，挽救了数千人的生命。这是纯粹的市场设计——在没有价格的情况下创建一个市场。
择校：Roth及其同事用策略防护系统替代了波士顿可操纵的学校分配机制。在旧系统下，如实报告偏好的家长会受到惩罚；在新系统下，诚实总是最优的。
频谱拍卖：Milgrom和Wilson（2020年诺贝尔奖）为FCC设计了组合拍卖，在有效分配频谱许可证的同时筹集了数十亿美元。2017年的激励拍卖单独筹集了198亿美元。
共同线索：经济理论提供蓝图，但实施需要理解具体的制度背景——纯理论所抽象掉的那些"细节"。
总结
- 机制设计反转博弈论：不是预测结果，而是设计博弈以实现期望结果。
- 显示原理表明，任何可实现的结果都可以通过代理人如实报告的直接机制来实现。这极大地简化了设计问题。
- 吉巴德-萨特斯韦特：没有转移支付时，只有独裁是一般意义上的DSIC。在准线性偏好下，VCG机制以占优策略真实报告实现效率。
- 收入等价：具有相同分配规则的标准拍卖产生相同的期望收入。迈尔森最优拍卖使用虚拟价值和保留价来最大化卖方收入。
- 迈尔森-萨特斯韦特不可能性：在私人信息下的双边贸易不能同时实现有效、激励相容、个体理性和预算平衡。
- 匹配市场（Gale-Shapley）产生不使用价格的稳定匹配。该算法对提议方是策略防护的，并在多项式时间内终止。
- 市场设计将这些思想应用于现实制度：住院医师匹配、择校、肾脏交换、频谱拍卖。
关键公式
| 标签 | 公式 | 描述 |
|---|
| 式 11.1 | $U_i(\theta_i, \theta_i) \geq U_i(\hat{\theta}_i, \theta_i)$ for all $\hat{\theta}_i, \theta_{-i}$ | DSIC |
| 式 11.2 | $E[U_i(\theta_i, \theta_i)] \geq E[U_i(\hat{\theta}_i, \theta_i)]$ | BIC |
| 式 11.3 | $t_i = \sum_{j \neq i} v_j(a^*(\theta_{-i})) - \sum_{j \neq i} v_j(a^*(\theta))$ | VCG支付 |
| 式 11.4 | $\psi(\theta) = \theta - (1-F(\theta))/f(\theta)$ | 迈尔森虚拟价值 |
练习题
基础练习
- 一个不可分割物品拍卖给两个竞标者，价值 $v_1 = 10$、$v_2 = 7$。计算以下各情形的获胜者和支付：(a) 第一价格密封投标（假设每个竞标者削价一半），(b) 第二价格密封投标，(c) 英式拍卖。
- 三个投票者对三个备选方案 {A, B, C} 进行排序。构造偏好档案，使得：(a) 多数规则产生循环（孔多塞悖论），(b) 独裁规则避免循环。
- 对以下设定运行Gale-Shapley（学生提议）：学生 {1,2,3}，学校 {X,Y,Z}。偏好：1: X>Y>Z, 2: Y>X>Z, 3: X>Y>Z。学校：X: 1>2>3, Y: 2>3>1, Z: 3>1>2。
应用练习
- 政府希望有效分配碳排放许可。比较：(a) VCG机制（企业报告减排成本），(b) 标准拍卖，(c) 限额交易市场。在什么条件下它们产生相同的分配？
- 解释为什么eBay使用第二价格拍卖（代理出价）而非第一价格拍卖。维克里结果与eBay的设计有何关联？
- 波士顿择校机制（改革前）惩罚那些列出热门学校但不具高优先级的家长。解释为什么这不是策略防护的，以及延迟接受如何解决这一问题。
- 迈尔森-萨特斯韦特定理表明，在私人信息下有效的双边贸易是不可能的。然而eBay、Craigslist和二手车市场每天促成数百万笔交易。这些制度如何缓解不可能性结果？
挑战题
- 推导 $n$ 个竞标者的第二价格拍卖的最优保留价，其价值独立同分布于 $U[0, 1]$。证明保留价为 \$1/2$，与 $n$ 无关。期望收入作为 $n$ 的函数是什么？
- 证明Gale-Shapley算法产生稳定匹配。（提示：假设存在阻塞对。证明这与算法的拒绝逻辑矛盾。）
- 一个卖方有两件相同物品和三个竞标者，价值 $v_1 > v_2 > v_3$。为这个多单位拍卖设计VCG机制。每个获胜者支付多少？
- 考虑一个匹配市场，其中一方有严格偏好但另一方对某些匹配无差异（平局）。Gale-Shapley是否仍然产生稳定匹配？如果平局被随机打破，结果是否唯一？