这是第四套习题,对应 Unit 7 和 Unit 8,也就是第 32 讲到第 42 讲。一共 16 道题,每道题都有完整的解答。
这一部分的特点是:规则成了主角。前面的题是"给定规则,玩家怎么玩",这里更多是"给定一群人,规则该怎么设计、分配该怎么分"。
怎么用这套题
先做,再看。 拿一张纸,每道题先写下自己的答案,哪怕只是一个方向。写完再去看解答。没写就看,你看到的是"别人的答案",不是"你的错误"。
难度。 每道题标了难度:
- ★ 巩固:直接用一个定义,或者一步计算。
- ★★ 标准:两三步,或者要自己把一段话翻译成式子。
- ★★★ 挑战:要把几个想法拼在一起,或者里面藏着一个陷阱。
不需要任何工具。 所有题都可以用纸笔做出来,数字都很小。每道题的数字,我都另外验算过,验算过程不放在这里。
解答怎么写的。 每道题的解答分四步:思路、过程、答案、常见错误。
| 题号 | 主题 | 对应讲 |
|---|---|---|
| 1 | 三人博弈的核:何时为空 | 第 32 讲 |
| 2 | 机场跑道的 Shapley 值 | 第 33 讲 |
| 3 | 手套:核与 Shapley 值不一致 | 第 32、33 讲 |
| 4 | 纳什讨价还价 | 第 34 讲 |
| 5 | 交替出价:耐心的价值 | 第 34 讲 |
| 6 | 学校匹配:延迟接受、顶层交易圈、波士顿 | 第 35 讲 |
| 7 | 稳定婚姻:谁提议,谁占便宜 | 第 35 讲 |
| 8 | 租金和谐 | 第 36 讲 |
| 9 | 一价与二价拍卖,保留价 | 第 37、39 讲 |
| 10 | 赢者诅咒 | 第 37 讲 |
| 11 | VCG:每个人付自己给别人添的麻烦 | 第 38 讲 |
| 12 | 最优拍卖:虚拟价值 | 第 39 讲 |
| 13 | 同一批选票,不同的计票办法 | 第 40 讲 |
| 14 | 中位选民 | 第 41 讲 |
| 15 | 拥堵:Braess 与 Pigou | 第 42 讲 |
| 16 | 判断题:哪些话是错的 | 综合 |
题目
第一部分 合作博弈(第 32–33 讲)
题 1(★★)三人博弈的核
三个人(1、2、3)合作能创造的价值:三个人一起 100;任意两个人一起 a;单独一个人 0。
(1)a = 70 时,核是不是空的?为什么?
(2)a = 60 时,(40,30,30)在核里吗?(50,25,25)呢?
(3)a = 60 时,一个人在核里最多能拿到多少?举一个核里的分配。
(4)a = 60 时,Shapley 值是什么?在核里吗?
题 2(★★)机场跑道的 Shapley 值
三家航空公司共用一条跑道。它们需要的跑道成本(单位:百万):公司 1 需要 20,公司 2 需要 50,公司 3 需要 80。一条跑道修到能满足最长需求的那家,就满足了所有人。一个联盟的成本等于联盟里最长需求的成本。
(1)用"大家按随机顺序依次加入、每人付自己带来的新增成本"的办法,求三家各自应分摊的成本(即 Shapley 值)。
(2)有一个简便的算法:把跑道按"需求的层次"切成段,每一段由用到它的人平分。用它再算一遍,核对结果。
题 3(★★)手套:核和 Shapley 值不一致
三个人:甲、乙各有一只左手手套,丙有一只右手手套。一副(一左一右)手套值 1。一个联盟创造的价值 = 能配成的副数。
(1)核是什么?
(2)Shapley 值是什么?
(3)Shapley 值在核里吗?说明理由。这说明了什么?
第二部分 讨价还价、匹配与分割(第 34–36 讲)
题 4(★★)纳什讨价还价
两个人分 100 元。谈不拢,甲得 10,乙得 30(这叫"谈崩点")。
(1)纳什讨价还价解(最大化两人"比谈崩点多得的部分"的乘积)是什么?
(2)如果谈崩点变成(30,30),解是什么?
(3)这说明了什么?
题 5(★★★)交替出价:耐心的价值
两个人分 1 元。甲先提议,乙接受就成交,乙拒绝就轮到乙提议,以此类推;每多等一轮,甲的收益乘以 δ₁,乙的乘以 δ₂。已知无限轮的子博弈完美均衡中,先提议者的份额是 (1 − δ₂) ÷ (1 − δ₁δ₂)。
(1)δ₁ = δ₂ = 0.9。甲(先提议)得多少?
(2)δ₁ = 0.8,δ₂ = 0.9(甲不太耐心)。甲得多少?
(3)δ₁ = 0.9,δ₂ = 0.8(乙不太耐心)。甲得多少?
(4)δ 都趋近 1 时,结果是什么?为什么说"耐心"是谈判力?
题 6(★★★)学校匹配
四个学生(a、b、c、d)、四所学校(W、X、Y、Z),每校一个名额。
学生的志愿(从最喜欢到最不喜欢):
- a:W、X、Y、Z
- b:X、Z、W、Y
- c:W、Z、Y、X
- d:Z、Y、W、X
学校的优先顺序(从最优先到最不优先):
- W:d、a、c、b
- X:b、d、c、a
- Y:a、b、c、d
- Z:c、d、b、a
(1)用学生提议的延迟接受,一轮一轮写出结果。
(2)用顶层交易圈(每个学生指向最喜欢的剩余学校,每所学校指向优先顺序最高的剩余学生,找圈、成交、移走),一步一步写出结果。
(3)用波士顿规则(第一轮被录取就定下来),写出结果。
(4)三种结果,学生 a、c、d 各得到第几志愿?
(5)顶层交易圈的结果稳定吗?(找一个学生和一所学校,学生更喜欢那所学校,学校也更优先这位学生。)
题 7(★★)稳定婚姻
三位男士(m1、m2、m3)、三位女士(w1、w2、w3)。
男士的偏好:m1:w3、w1、w2;m2:w2、w1、w3;m3:w1、w3、w2。
女士的偏好:w1:m2、m1、m3;w2:m1、m3、m2;w3:m2、m3、m1。
(1)男士提议的延迟接受:结果是什么?
(2)女士提议的延迟接受:结果是什么?
(3)这个博弈一共有 3 个稳定匹配,另一个是(m1–w1,m2–w2,m3–w3)。检查它确实稳定。
(4)比较三个稳定匹配,男士提议的结果对男士还是对女士更好?
题 8(★★★)租金和谐
三个室友甲、乙、丙,租一套有三间卧室的房子,总租金 900。每人对三间房(1 号、2 号、3 号)的估价(愿意付的最高价):
| 1 号 | 2 号 | 3 号 | |
|---|---|---|---|
| 甲 | 500 | 250 | 150 |
| 乙 | 300 | 400 | 200 |
| 丙 | 350 | 250 | 300 |
(1)怎么分房,让大家的估价之和最大?
(2)找一组房租(三间之和 900),使得没有人羡慕别人的房间加价格。
(3)这样的房租唯一吗?
第三部分 拍卖与机制设计(第 37–39 讲)
题 9(★★★)一价与二价拍卖,保留价
三个竞标人,对一件物品的估价各自独立,在 0 到 1 之间均匀分布。
(1)一价拍卖(出价最高的人赢,付自己的出价):对称均衡里,估价 v 的人出多少?估价 0.9 的人出多少,期望收益是多少?
(2)二价拍卖(出价最高的人赢,付第二高的出价):估价 0.9 的人怎么出?期望收益是多少?
(3)两种拍卖,卖家的期望收入各是多少?
(4)只有两个竞标人,二价拍卖,保留价 0.5(出价都低于保留价就不卖)。卖家的期望收入是多少?与没有保留价比较。物品卖不出去的概率是多少?
题 10(★★)赢者诅咒
一件物品的真实价值是 V,没有人知道。每个竞标人对它的估计 = V + 误差,误差在 −10 到 10 之间均匀分布,彼此独立。每个竞标人都按自己的估计出价,出价最高的赢。
(1)最高的估计,比真实价值平均高多少?(对于 n 个竞标人,n 个均匀误差中最大的那个的期望是 10 × (n − 1) ÷ (n + 1)。)分别算 n = 2、5、10。
(2)如果赢家按自己的估计付钱,平均会亏多少?
(3)理性的竞标人应该怎么做?
题 11(★★)VCG:每个人付自己给别人添的麻烦
三位竞标人,卖两件一样的物品,每人最多要一件,估价分别是 10、8、5。用 VCG(每个赢家付的钱 = 如果没有这位赢家,其他人能多得到的价值)。
(1)谁赢?谁付多少?卖家的收入是多少?
(2)估价 10 的人,如果谎报成 6,结果会不会变?如果报成 4 呢?
(3)如果第三位的估价是 9,结果如何?
题 12(★★★)最优拍卖:虚拟价值
卖家卖一件物品,竞标人估价各自独立,在 0 到 1 之间均匀分布。“虚拟价值"是 φ(v) = 2v − 1。最优拍卖:把物品给虚拟价值最高、而且非负的人。
(1)虚拟价值为 0 的估价是多少?这就是最优保留价。
(2)n = 2 时,卖家的期望收入是多少?没有保留价时是多少?
(3)n = 3 时,最优拍卖的期望收入是多少?没有保留价时是多少?
(4)为什么对卖家来说,有时候宁可"不卖”?
第四部分 社会选择(第 40–41 讲)
题 13(★★★)同一批选票,不同的计票办法
100 个选民,对 A、B、C 三位候选人的排序:
| 排序 | 人数 |
|---|---|
| A > B > C | 30 |
| A > C > B | 5 |
| B > A > C | 25 |
| C > A > B | 10 |
| C > B > A | 30 |
(B > C > A 的人数是 0。)
(1)只数第一名,谁赢?
(2)两两比较,谁能打败其余所有人(孔多塞赢家)?
(3)波达计分(第一名 2 分,第二名 1 分,第三名 0 分),谁赢?
(4)两轮决选(只数第一名,前两名进入第二轮),谁赢?
(5)如果 C 退出,只剩 A 和 B,谁赢?这说明了什么?
题 14(★★)中位选民
7 位选民,理想的立场(0 到 100 的一条线)分别是 10、20、30、50、60、80、100。每人投给离自己立场更近的候选人。
(1)候选人 A 站在 50,候选人 B 站在 55。谁赢?B 站在 40 呢?
(2)中位数立场是多少?为什么站在中位数的候选人,不会输给任何其他位置的候选人?
(3)现在由这 7 个人"报告立场",最后的结果取中位数。立场 20 的人,如果谎报成 0,结果会变吗?如果取平均数呢?
第五部分 拥堵(第 42 讲)
题 15(★★★)拥堵:Braess 与 Pigou
(Ⅰ)Braess。 3600 位上班族从 S 去 T。路线 S→A→T:S→A 耗时 = 这条路上的人数 ÷ 100(分钟),A→T 固定 45 分钟。路线 S→B→T:S→B 固定 45 分钟,B→T 耗时 = 人数 ÷ 100。
(1)没有捷径时,均衡里每人耗时多少?
(2)修一条耗时为 0 的免费捷径 A→B,均衡里每人耗时多少?是变好还是变坏?
(3)捷径耗时 c = 18 分钟时,均衡里每人耗时多少?三条路线各多少人?
(4)c 至少多大,捷径就没人用?
(Ⅱ)Pigou。 一群司机选两条路:路 1 固定 1 小时;路 2 的耗时是走路 2 的人所占比例的平方。
(5)均衡时每人耗时多少?让平均耗时最短的安排是什么,平均耗时多少?
(6)要用过路费让大家自己走到最优安排,路 2 的过路费该是多少?
题 16(★)判断题:这些话对吗
判断对错,并用一两句话说明理由。
(a)合作博弈的核总是非空的。
(b)Shapley 值一定在核里。
(c)延迟接受总得到稳定匹配,而且对提议的一方最有利。
(d)一价拍卖的卖家收入,一般比二价拍卖高。
(e)VCG 机制能让卖家收入最大。
(f)Arrow 定理说,所有的计票办法都会出现"循环"。
解答
第一部分 合作博弈
题 1 解答
思路: 核 = 没有任何联盟能靠自己做得更好的分配。
过程与答案:
(1)a = 70。三个"两人联盟"的要求:x₁ + x₂ 不小于 70,x₁ + x₃ 不小于 70,x₂ + x₃ 不小于 70。三式相加:2(x₁ + x₂ + x₃) 不小于 210,即三个人合计至少 105。可是三个人一起只有 100,不够。所以核是空的。
(2)a = 60:要求每对至少 60。(40,30,30):1、2 合计 70,1、3 合计 70,2、3 合计 60,都不小于 60;个人都不小于 0;合计 100。在核里。(50,25,25):2、3 合计只有 50,小于 60,2 和 3 可以自己结成联盟拿 60,不在核里。
(3)每对至少 60,三个人合计 100:任何一个人 i 拿到的 x_i = 100 − (另外两人合计) 不大于 100 − 60 = 40。最多 40。核里的一个分配:(40,40,20):1、2 合计 80,1、3 合计 60,2、3 合计 60,合计 100,在核里。
(4)Shapley 值:三个人完全对称,各 100/3 ≈ 33.3。每对合计 66.7,不小于 60,在核里。
常见错误: 以为"三个人合起来创造的价值大于两个人的价值,所以核总有解"。题(1)里,三个人一起(100)比不过"三个对子"的总要求(105),核是空的。
题 2 解答
思路: 每个人的 Shapley 值是这个人在所有加入顺序中带来的新增成本的平均。
过程与答案:
(1)六种加入顺序下,每人带来的新增成本:成本函数 c({1}) = 20,c({2}) = 50,c({3}) = 80,任何包含 3 的联盟 80,包含 2 但不含 3 的联盟 50。
| 顺序 | 公司 1 | 公司 2 | 公司 3 |
|---|---|---|---|
| 1、2、3 | 20 | 30 | 30 |
| 1、3、2 | 20 | 0 | 60 |
| 2、1、3 | 0 | 50 | 30 |
| 2、3、1 | 0 | 50 | 30 |
| 3、1、2 | 0 | 0 | 80 |
| 3、2、1 | 0 | 0 | 80 |
平均:公司 1 = (20 + 20 + 0 + 0 + 0 + 0) ÷ 6 = 20/3 ≈ 6.67;公司 2 = (30 + 0 + 50 + 50 + 0 + 0) ÷ 6 = 65/3 ≈ 21.67;公司 3 = (30 + 60 + 30 + 30 + 80 + 80) ÷ 6 = 155/3 ≈ 51.67。合计 80,正好是整条跑道的成本。
(2)切成三段:第一段 0 到 20,公司 1、2、3 都用,成本 20,三人平分:每人 20/3。第二段 20 到 50,公司 2、3 用,成本 30,两人平分:各 15。第三段 50 到 80,只有公司 3 用,成本 30,全由公司 3 付。于是:公司 1 = 20/3;公司 2 = 20/3 + 15 = 65/3;公司 3 = 20/3 + 15 + 30 = 155/3。与(1)一致。
常见错误: 把跑道成本按"需求的比例"分(20、50、80 的比例);那样公司 1 要付 20 ÷ 150 × 80 ≈ 10.7,比 Shapley 值高:它的需求本来就在所有人的需求之内,应该付得少。
题 3 解答
思路: 左手手套是"多的一边",右手手套是"稀缺的一边"。
过程与答案:
(1)核:任何一个"左 + 右"的联盟能创造 1,所以需要 x_甲 + x_丙 不小于 1,x_乙 + x_丙 不小于 1。三个人合计 1。如果丙拿到少于 1,那么 x_甲 + x_乙 = 1 − x_丙 大于 0,而 x_甲 + x_丙 不小于 1,x_乙 + x_丙 不小于 1,相加:x_甲 + x_乙 + 2x_丙 不小于 2,所以 (1 − x_丙) + 2x_丙 = 1 + x_丙 不小于 2,x_丙 不小于 1。所以核只有一个点:丙得 1,甲、乙各得 0。
(2)Shapley 值:看丙在六种加入顺序里的新增贡献。丙排第 1 位:前面没有人,新增 0。丙排第 2 位:前面有一只左手手套(甲或乙),丙加入后配成 1 副,新增 1。丙排第 3 位:前面是两只左手手套,丙加入后还是只能配成 1 副,新增 1。三个位置各占 1/3,丙的平均 = (0 + 1 + 1) ÷ 3 = 2/3。甲和乙对称,各分剩下的一半:各 1/6。
(3)不在核里:甲、丙合起来只拿到 1/6 + 2/3 = 5/6,小于甲丙自己结成联盟能创造的 1。甲和丙有动力离开。这说明:核只看"谁也不想离开",把稀缺的一方全部给丙;Shapley 值看的是"平均贡献",给了多的一方一些。两者回答的是不同的问题,Shapley 值不一定在核里。
常见错误: 以为 Shapley 值总是"公平的、稳定的"。公平(按贡献)和稳定(谁也不想退出)是两回事。
第二部分 讨价还价、匹配与分割
题 4 解答
思路: 最大化双方"比谈崩点多得的部分"的乘积。
过程与答案:
(1)设甲得 x,乙得 100 − x。乘积 (x − 10)(100 − x − 30) = (x − 10)(70 − x)。两个因子的和是 60(固定),乘积在相等时最大:x − 10 = 70 − x,x = 40。结果:甲 40,乙 60。直观:先给每人谈崩点(10 和 30),剩下的 100 − 40 = 60 平分,各 30。
(2)谈崩点(30,30):(x − 30)(70 − x),因子和 40,相等时最大:x − 30 = 70 − x,x = 50。结果(50,50)。
(3)甲的谈崩点从 10 升到 30,甲的份额从 40 升到 50。 谈崩点越高(不谈成也过得不错),谈成时的份额越大。这就是"威胁点"的作用:好的替代选择是谈判力。
常见错误: 以为平分 100 就是"公平",而忽略了谈崩点(10 对 30);纳什解里,是先扣除谈崩点,再平分剩下的。
题 5 解答
思路: 直接代入公式;比较谁更耐心。
过程与答案:
(1)δ₁ = δ₂ = 0.9:甲得 (1 − 0.9) ÷ (1 − 0.81) = 0.1 ÷ 0.19 ≈ 0.526。
(2)δ₁ = 0.8,δ₂ = 0.9:(1 − 0.9) ÷ (1 − 0.72) = 0.1 ÷ 0.28 ≈ 0.357。
(3)δ₁ = 0.9,δ₂ = 0.8:(1 − 0.8) ÷ (1 − 0.72) = 0.2 ÷ 0.28 ≈ 0.714。
(4)δ 都趋近 1:比如 δ₁ = δ₂ = δ,份额 = (1 − δ) ÷ (1 − δ²) = 1 ÷ (1 + δ),趋近 1/2。先提议的优势消失。耐心是谈判力:(2)里甲只有 0.8,虽然先提议,却只得 0.357,比乙还少;(3)里乙只有 0.8,甲得 0.714。
常见错误: 以为"先提议的人总占便宜";双方都很耐心时,先后的差别变得很小,耐心的差别更重要。
题 6 解答
思路: 三种规则各算一遍。
过程与答案:
(1)延迟接受:第 1 轮:a→W,b→X,c→W,d→Z。W 的优先顺序:d、a、c、b。W 收到 a 和 c,暂时留 a(a 比 c 优先),拒绝 c。X 留 b,Z 留 d。第 2 轮:c→Z(第二志愿)。Z 的优先顺序:c、d、b、a。c 比 d 优先,Z 换成 c,拒绝 d。第 3 轮:d→Y(第二志愿)。Y 没人,留下 d。结果:a–W,b–X,c–Z,d–Y。
(2)顶层交易圈:第 1 步:每个学生指向最喜欢的学校:a→W,b→X,c→W,d→Z。每所学校指向优先顺序最高的学生:W→d,X→b,Y→a,Z→c。找圈:b→X→b(b 与 X 成圈);c→W→d→Z→c(c、W、d、Z 成圈)。成交:b 得 X;c 得 W;d 得 Z。移走 b、c、d 和 X、W、Z。第 2 步:只剩 a 和 Y:a 得 Y。结果:a–Y,b–X,c–W,d–Z。
(3)波士顿规则:第 1 轮:a、c 申请 W,a 的优先顺序更高,a 被录取(定下来);b 被 X 录取;d 被 Z 录取;c 被拒绝。第 2 轮:c 申请第二志愿 Z,Z 已满,拒绝。第 3 轮:c 申请第三志愿 Y,被录取。结果:a–W,b–X,c–Y,d–Z。
(4)各得第几志愿:
| a | c | d | |
|---|---|---|---|
| 延迟接受 | W(第 1) | Z(第 2) | Y(第 2) |
| 顶层交易圈 | Y(第 3) | W(第 1) | Z(第 1) |
| 波士顿 | W(第 1) | Y(第 3) | Z(第 1) |
(b 在三种规则下都得 X,第 1 志愿。)
(5)不稳定:a 更喜欢 W(第 1 志愿),而学校 W 的优先顺序里 a(第 2)比现在得到它的 c(第 3)更优先。a 和 W 互相更愿意,是一个阻塞对(a 有"正当的怨言")。延迟接受是稳定的,顶层交易圈不是。
常见错误: 在波士顿规则里,被第一轮拒绝的学生,第二轮申请第二志愿时,要先看那所学校还有没有名额:已满就不能再收。
题 7 解答
思路: 提议的一方,每次向自己最喜欢的、还没拒绝过自己的对象求婚。
过程与答案:
(1)男士提议:第 1 轮:m1→w3,m2→w2,m3→w1,三个人向不同的女士求婚,每位女士只收到一个,都暂时接受,结束。结果:m1–w3,m2–w2,m3–w1,每位男士都得到自己的第一选择。
(2)女士提议:第 1 轮:w1→m2,w2→m1,w3→m2。m2 收到 w1 和 w3,m2 的偏好是 w2、w1、w3:更喜欢 w1,留下 w1,拒绝 w3。第 2 轮:w3→m3(w3 的第二选择),m3 没人,留下。结果:w1–m2,w2–m1,w3–m3。
(3)检查(m1–w1,m2–w2,m3–w3)里每一个"更喜欢对方的一对":m1 更喜欢 w3,可是 w3 现在的伴侣 m3 比 m1 更合 w3 的意(w3 的偏好是 m2、m3、m1),不构成阻塞。m2 已经得到第一选择 w2,不会离开。m3 更喜欢 w1,可是 w1 更喜欢自己现在的伴侣 m1(w1 的偏好是 m2、m1、m3),不构成阻塞。再从女士这边看:w1 更喜欢 m2,可是 m2 更喜欢 w2;w2 更喜欢 m1 和 m3,可是 m1 更喜欢 w1、m3 更喜欢 w3;w3 更喜欢 m2,可是 m2 更喜欢 w2。没有阻塞对,稳定。
(4)三个稳定匹配:(i)m1–w1,m2–w2,m3–w3;(ii)m1–w2,m2–w1,m3–w3(女士提议的结果);(iii)m1–w3,m2–w2,m3–w1(男士提议的结果)。男士提议的结果(iii)对男士最好(每人都得到第一选择),对女士是最差的一个(w1 得 m3,第 3 选择;w2 得 m2,第 3 选择;w3 得 m1,第 3 选择)。提议的一方占便宜。
常见错误: 以为稳定匹配只有一个。这里有 3 个,谁来提议决定了落在哪一个。
题 8 解答
思路: 先找总估价最大的分配,再找让每个人都不羡慕的价格。
过程与答案:
(1)六种分配的估价之和:甲 1、乙 2、丙 3:500 + 400 + 300 = 1200;甲 1、乙 3、丙 2:500 + 200 + 250 = 950;甲 2、乙 1、丙 3:250 + 300 + 300 = 850;甲 2、乙 3、丙 1:250 + 200 + 350 = 800;甲 3、乙 1、丙 2:150 + 300 + 250 = 700;甲 3、乙 2、丙 1:150 + 400 + 350 = 900。最大是 1200:甲住 1 号,乙住 2 号,丙住 3 号。
(2)要找价格 p₁ + p₂ + p₃ = 900,使得每个人在自己的房间"估价 − 价格"不小于在别的房间的。试 p = (400,300,200):甲:500 − 400 = 100;在 2 号 250 − 300 = −50,在 3 号 150 − 200 = −50,100 最大。乙:400 − 300 = 100;在 1 号 300 − 400 = −100,在 3 号 200 − 200 = 0,100 最大。丙:300 − 200 = 100;在 1 号 350 − 400 = −50,在 2 号 250 − 300 = −50,100 最大。没有人羡慕。 三人的剩余都是 100。
(3)不唯一。比如(350,350,200)也行:甲 500 − 350 = 150,在 2 号 250 − 350 = −100,在 3 号 150 − 200 = −50;乙 400 − 350 = 50,在 1 号 300 − 350 = −50,在 3 号 200 − 200 = 0;丙 300 − 200 = 100,在 1 号 350 − 350 = 0,在 2 号 250 − 350 = −100。都不羡慕。一般地,一个范围内的价格都可以(比如,1 号的价格大约在 290 到 500 之间)。
常见错误: 把房租按"估价的比例"分:那样不能保证没人羡慕。要同时决定谁住哪间和付多少。
第三部分 拍卖与机制设计
题 9 解答
思路: 一价拍卖要"打折"出价;二价拍卖说真话;两者的期望收入相同。
过程与答案:
(1)n = 3:对称均衡里估价 v 的人出 v × (n − 1) ÷ n = 2v/3。估价 0.9 的人出 0.6。这个人赢,当且仅当另外两人的出价都低于 0.6,即另外两人的估价都低于 0.9,概率 0.9² = 0.81。期望收益 = (0.9 − 0.6) × 0.81 = 0.243。
(2)二价拍卖说真话:出 0.9。赢的时候付第二高的出价(等于另外两人估价的最大值 W)。期望收益 = ∫₀^0.9 (0.9 − w) × 2w dw = 0.9 × 0.81 − (2/3) × 0.729 = 0.729 − 0.486 = 0.243。与一价相同。
(3)n = 3:一价拍卖:赢家出价 = 2/3 × 最高估价,期望最高估价是 n ÷ (n + 1) = 3/4,所以期望收入 = 2/3 × 3/4 = 1/2。二价拍卖:期望收入 = 第二高估价的期望 = (n − 1) ÷ (n + 1) = 1/2。相等(收入等价)。
(4)n = 2,二价,保留价 r = 0.5。分三种情形:两人都低于 0.5(概率 0.25):不卖,收入 0。恰有一人高于 0.5(概率 2 × 0.5 × 0.5 = 0.5):以 0.5 卖出,收入 0.5。两人都高于 0.5(概率 0.25):卖给高的,价格 = 较低的估价,在 0.5 到 1 之间均匀,平均 0.5 + 0.5 ÷ 3 = 2/3。期望收入 = 0.5 × 0.5 + 0.25 × 2/3 = 0.25 + 0.1667 = 5/12 ≈ 0.4167。没有保留价时:1/3 ≈ 0.333。设了保留价,收入更高。卖不出去的概率 = 两人都低于 0.5 = 1/4。
常见错误: 一价拍卖里,以为"出价低一点就能多赚,所以卖家收入更低"。竞标人的出价会反映这一点,在均衡里期望收入一样。
题 10 解答
思路: 赢的人,往往是误差最正的那个。
过程与答案:
(1)n 个误差里最大的,平均是 10 × (n − 1) ÷ (n + 1)。n = 2:10 × 1/3 ≈ 3.33;n = 5:10 × 4/6 ≈ 6.67;n = 10:10 × 9/11 ≈ 8.18。竞标人越多,赢家的估计比真实价值高得越多。
(2)赢家按自己的估计付钱,付的比真实价值平均高同样的数:n = 2 平均亏 3.33,n = 5 平均亏 6.67,n = 10 平均亏 8.18。这就是赢者诅咒:赢了,恰恰说明你的估计是所有人里最乐观的。
(3)理性的竞标人要把"我赢了"这个事实也考虑进去:出价要比自己的估计低,竞标人越多,要低得越多(大约就是上面的数)。赢了是坏消息,要在出价时就扣掉。
常见错误: 以为"我的估计是无偏的,所以按估计出价就不会亏"。无偏是对"所有估计"说的,而赢了的那个,是被选出来的最乐观的一个。
题 11 解答
思路: 每个赢家付的钱 = 没有这位赢家时,其他人能多得到的价值。
过程与答案:
(1)两件物品,估价 10、8、5:估价 10 和 8 的人赢(总价值最大)。估价 10 的人(甲):没有甲时,另外两人(8、5)各拿一件,总价值 13;有甲时,另外两人的价值只有乙的 8;差 13 − 8 = 5,甲付 5。估价 8 的人(乙):没有乙时,甲、丙拿,总价值 15;有乙时,另外两人的价值只有甲的 10;差 15 − 10 = 5,乙付 5。丙付 0。卖家的收入 = 5 + 5 = 10。(每个赢家付的,恰好是被挤出去的人的估价 5。)
(2)甲谎报成 6:还是在前两名里,赢,付的还是 5(付的钱由别人决定,不取决于甲的报价)。结果不变。甲谎报成 4:低于乙(8)和丙(5),甲输,得 0;而说真话的收益是 10 − 5 = 5。更差。所以说真话最好。
(3)丙的估价是 9:前两名是 10 和 9,乙(8)输。甲:没有甲时,乙、丙(8、9)取前两,总价值 17;有甲时,另外两人的价值是丙的 9;差 17 − 9 = 8,甲付 8。丙:没有丙时,甲、乙取(10、8),总价值 18;有丙时,另外两人的价值是甲的 10;差 18 − 10 = 8,丙付 8。每个赢家付的,恰好是被挤出去的乙的估价 8。卖家收入 16。
常见错误: 以为赢家付自己的报价(第一价格);VCG 里,价钱取决于别人的报价,所以说真话是占优的。
题 12 解答
思路: 卖家要的不是"估价最高"的人,而是"虚拟价值最高、且不为负"的人。
过程与答案:
(1)φ(v) = 2v − 1 = 0,v = 1/2。保留价 1/2:估价低于 1/2 的人,虚拟价值为负,不卖给这个人。
(2)n = 2:卖家的期望收入 = 最高估价的虚拟价值(非负时)的期望 = 2 × ∫ from 1/2 to 1 的 (2v − 1) × v dv。先算 2 × [(2/3)v³ − v²/2] 在 1/2 到 1 的差:上限(v = 1):2/3 − 1/2 = 1/6;下限(v = 1/2):(2/3)(1/8) − 1/8 = 1/12 − 1/8 = −1/24;差 = 1/6 + 1/24 = 5/24;乘 2 得 5/12 ≈ 0.4167。没有保留价:1/3。(与题 9(4)一致。)
(3)n = 3:期望收入 = 3 × ∫ from 1/2 to 1 的 (2v − 1) × v² dv = 3 × [(2/4)v⁴ − v³/3] 在 1/2 到 1 的差:上限:1/2 − 1/3 = 1/6;下限:(1/2)(1/16) − (1/3)(1/8) = 1/32 − 1/24 = −1/96;差 = 1/6 + 1/96 = 17/96;乘 3 得 17/32 ≈ 0.531。没有保留价:(n − 1) ÷ (n + 1) = 1/2。设了最优保留价,收入从 0.5 升到 0.531。
(4)设保留价,是用"有时卖不出去"的代价,换"卖出去时价格更高"。估价刚好略高于 1/2 的人,如果被卖给这个人,只能收到约 1/2;而保留价把价格抬到至少 1/2,对所有更高估价的人都有效。当参与的人少,(比如 n = 2)这一点格外重要。
常见错误: 把保留价定成卖家自己对物品的估价(成本)。最优保留价高于这个数(这里卖家成本是 0,保留价却是 1/2)。
第四部分 社会选择
题 13 解答
思路: 同一批选票,不同的计票办法,结果可以三种不同。
过程与答案:
(1)只数第一名:A 的第一名 = 30 + 5 = 35;B = 25;C = 10 + 30 = 40。C 赢。
(2)两两比较:A 对 B:A 排在 B 前的人:A > B > C(30)、A > C > B(5)、C > A > B(10)= 45;B 排在 A 前:B > A > C(25)、C > B > A(30)= 55。B 赢 A(55 对 45)。B 对 C:B 排在 C 前:A > B > C(30)、B > A > C(25)= 55;C 排在 B 前:A > C > B(5)、C > A > B(10)、C > B > A(30)= 45。B 赢 C(55 对 45)。所以 B 是孔多塞赢家。
(3)波达计分:A = 30 × 2 + 5 × 2 + 25 × 1 + 10 × 1 + 30 × 0 = 60 + 10 + 25 + 10 = 105;B = 30 × 1 + 5 × 0 + 25 × 2 + 10 × 0 + 30 × 1 = 30 + 50 + 30 = 110;C = 30 × 0 + 5 × 1 + 25 × 0 + 10 × 2 + 30 × 2 = 5 + 20 + 60 = 85。B 赢。
(4)两轮决选:第一轮 C(40)、A(35)进入第二轮,B(25)被淘汰。第二轮 A 对 C:A 排在 C 前:A > B > C(30)、A > C > B(5)、B > A > C(25)= 60;C 排在 A 前:C > A > B(10)、C > B > A(30)= 40。A 赢(60 对 40)。
(5)C 退出,A 对 B:A 排在 B 前 = 45,B 排在 A 前 = 55:B 赢。这说明:C 是"搅局者":只数第一名时,C 拿走了 A 的部分支持者,却不能赢;如果 C 不出现,B 赢;有 C 时,只数第一名是 C 赢,两轮决选是 A 赢。同一批选票,三种办法,三个不同的赢家(C、B、A)。哪个是"民意"?没有标准答案:Arrow 定理说,没有一种办法能同时满足所有合理的要求。
常见错误: 把"第一名最多"当成"最受欢迎":这里 C 第一名最多,可是有 60% 的人把 C 排在 A 之后,55% 的人把 C 排在 B 之后。
题 14 解答
思路: 立场在一条线上、每人偏好"离自己越近越好"时,中位数立场是赢家。
过程与答案:
(1)A 站 50,B 站 55:分界点 52.5。离 A 更近的:立场不超过 52.5 的人:10、20、30、50,共 4 人;离 B 更近:60、80、100,共 3 人。A 赢(4 对 3)。B 站 40:分界点 45。离 B 近:10、20、30,3 人;离 A(50)近:50、60、80、100,4 人。A 赢(4 对 3)。
(2)中位数立场 = 排在中间的第 4 个人 = 50。站在 50 的候选人,对手无论站在哪一边,对手那边的人都不超过一半(比如对手站在 55 以上,对手最多赢得立场 52.5 以上的人,最多 3 人),所以站在中位数的候选人不会输。这就是中位选民定理。
(3)取中位数:立场 20 谎报成 0:排序后 0、10、30、50、60、80、100,中位数仍是 50,没变。(说真话,中位数也是 50。)如果谎报成别的更低的数,也没有变化;向上谎报(比如 100)反而让中位数升到 50 以上更糟。说真话是最优的。 取平均数:真实平均数 = (10 + 20 + 30 + 50 + 60 + 80 + 100) ÷ 7 = 350 ÷ 7 = 50。立场 20 的人谎报成 0:平均数 = 330 ÷ 7 ≈ 47.1,更接近 20。有好处。 所以取平均数,可以靠夸大立场来操纵;取中位数则不能。
常见错误: 以为"中位数和平均数差不多"。这里两者恰好都是 50,可是防不防谎报完全不同。
第五部分 拥堵
题 15 解答
思路: 均衡时,用到的每条路线耗时相等,没用到的路线不更快。
过程与答案:
(1)没有捷径:两条路线对称,各 1800 人。S→A 耗时 1800 ÷ 100 = 18,加 45:63 分钟。
(2)免费捷径:所有人都走 S→A→B→T:S→A 上 3600 人,36 分钟;捷径 0;B→T 上 3600 人,36 分钟:72 分钟。看另外两条路线:S→A→T:36 + 45 = 81;S→B→T:45 + 36 = 81,都比 72 慢,没人想换。从 63 变成 72,变坏了(3600 大于临界的 3000)。
(3)c = 18:设 y 人走 S→A→T,y 人走 S→B→T,z 人走捷径,2y + z = 3600。每条窄路上的人数 m = y + z。三条路线耗时相等:S→A→T:m ÷ 100 + 45;S→A→B→T:m ÷ 100 + 18 + m ÷ 100。令相等:m ÷ 100 + 45 = 2m ÷ 100 + 18,m ÷ 100 = 27,m = 2700。耗时 = 27 + 45 = 72 分钟。y = 3600 − 2700 = 900,z = 2700 − 900 = 1800。三条路线:S→A→T 900 人,S→B→T 900 人,捷径 1800 人。每条路线耗时:S→A→T:27 + 45 = 72;捷径:27 + 18 + 27 = 72。✓。
(4)捷径没人用:每条窄路 1800 人时,捷径路线的耗时 = 18 + c + 18 = 36 + c 不小于 63,c 不小于 27。
(5)均衡:所有人走路 2:耗时 1² = 1 小时,路 1 也是 1,没人想换;平均 1。让平均最短:设路 2 的比例是 x,平均耗时 = (1 − x) × 1 + x × x² = 1 − x + x³。求最低点:−1 + 3x² = 0,x = 1/√3 ≈ 0.577;平均 = 1 − 0.577 + 0.192 = 约 0.615。均衡比最优多花 1 ÷ 0.615 ≈ 1.63 倍。
(6)过路费等于"你给别人添的那份堵":路 2 的耗时 ℓ(x) = x²,每多一个人,给路 2 上所有人添的总耗时 = x × ℓ′(x) = x × 2x = 2x²;在 x = 1/√3 时,2x² = 2/3。过路费 = 2/3 小时。检验:路 2 的花费 = x² + 2/3 = 1/3 + 2/3 = 1,等于路 1,所以大家自己走到 x = 1/√3。
常见错误: (2)里以为"多一条路,不会更差"。(5)里把"让平均最短"当成"让路 2 的耗时等于路 1 的耗时":那是均衡,不是最优。
题 16 解答
(a)错。 题 1(1):a = 70 时,核是空的。
(b)错。 题 3:Shapley 值(1/6,1/6,2/3)不在核(0,0,1)里。
(c)对。 延迟接受总得到稳定匹配,对提议的一方最有利(题 7:男士提议时每个人都得到第一选择)。
(d)错。 在这个标准的设定下,一价和二价拍卖的期望收入相等(题 9(3),收入等价);一价里竞标人出价更低,抵消了赢家付自己出价的好处。
(e)错。 VCG 保证说真话和效率,却不一定使卖家收入最大;最优拍卖要设保留价(题 12),会牺牲一点效率,换更高的收入。
(f)错。 Arrow 定理说:没有一种办法能同时满足一组合理的要求;它不是说"所有办法都会循环"。(循环是孔多塞悖论,只在某些选票下出现;题 13 的这批选票就没有循环,B 是孔多塞赢家。)
做完之后
如果这一套错得多的地方是……
- 题 1、2、3(核与 Shapley 值):回到第 32、33 讲,重点是"核看稳定,Shapley 值看平均贡献"。
- 题 4、5(讨价还价):回到第 34 讲,重点是"谈崩点和耐心就是谈判力"。
- 题 6、7、8(匹配与分割):回到第 35、36 讲,重点是"稳定的含义"和"谁来提议"。
- 题 9、10、11、12(拍卖与机制):回到第 37–39 讲,重点是"出价和估价的关系"和"让说真话成为最优"。
- 题 13、14(投票):回到第 40、41 讲,重点是"同一批选票,不同办法结果不同"和"取中位数不怕谎报"。
- 题 15(拥堵):回到第 42 讲,重点是"均衡不等于最优"和"过路费等于你给别人添的堵"。
一个自我检验: 把题 6 里学校 X 的优先顺序,改成"d、b、c、a",你能不能不查书,重新算延迟接受的结果,并说出有没有学生因此变好?