The Prize in Economic Sciences 2012 Toroorn omstabillch Figure1:2012年诺贝尔经济学奖 课程网站 http://math.sjtu.edu.cn/course/skymath/ 第-∞讲2012年诺贝尔经济学奖 2012年诺贝尔经济学奖授予哈佛大学商学院教授罗斯(Alvin E. Roth)和加州大学洛杉矶分校教授夏普利(Lloyd S.Shapley)。祝贺 他们！罗斯教授在哈佛任教，夏普利教授本科在哈佛数学系就读，因此今 年的两个诺奖得主都算哈佛的人，祝贺哈佛大学！ (©上海交通大学加油！©) 两位经济学奖的主要贡献是“the theory of stable allocations and the practice of market design”,即稳定匹配理论(stable matching theory)和市 场设计。稳定匹配理论广泛地应用于实际生活。例如，如何设计高考填报 志愿方法，如何将捐献的器官分配到需要的病人，如何将实习医生分配到 各个医院等。夏普利的主要贡献是提供了一个理论上的最优方案，称之为 “Gale-Shapley方法”。以高考填报志愿为例，该方法的基本思想是，让 分数最高的人先报，每个大学挑选它最中意的学生，踢掉其它候选人：然 后让分数次高的人填报，大学依然挑选最中意的人：最后直到所有学生都 被录取为止。这一机制可以确保公平和效率。 1
Figure 1: 2012❝ì✓✏➨▲➷ø ➅➜✤Õ http://math.sjtu.edu.cn/course/skymath/ ✶ −∞ ù 2012 ❝ì✓✏➨▲➷ø 2012❝ì✓✏➨▲➷ø➬❷▼➹➀➷û➷✓✓➬Û❞↔Alvin E. Roth↕Ú❭➨➀➷âë➑➞☎✓➬❣✃⑤↔Lloyd S. Shapley↕✧ ✻å ➛❶➐Û❞✓➬✸▼➹❄✓➜❣✃⑤✓➬✢❽✸▼➹ê➷❳ÒÖ➜ Ï❞✽ ❝✛ü❻ìø✚❒Ñ➂▼➹✛❁➜✻å▼➹➀➷➐ (,þ➦✂Ï➀➷❭❤➐,) ü➔➨▲➷ø✛❒❻③➫✴the theory of stable allocations and the practice of market design✵➜❂➢➼➎✛♥Ø(stable matching theory)Ú➼ ⑤✗❖✧➢➼➎✛♥Ø✷➁✴❆❫✉➣❙✮➵✧⑦❳➜❳Û✗❖♣⑧❲✞ ➇✑➄④➜ ❳Ûòí③✛ì✭➞✛✔■❻✛➽❁➜❳Ûò➣❙➎✮➞✛✔ ❼❻➎✓✤✧ ❣✃⑤✛❒❻③➫❏ø✡➌❻♥Øþ✛⑩❵➄❨➜→❷➃ ✴Gale-Shapley➄④✵✧➧♣⑧❲✞➇✑➃⑦➜ ❚➄④✛➘✢❣➂➫➜✹ ➞ê⑩♣✛❁❦✞➜③❻➀➷❪➚➜⑩➙➾✛➷✮➜❍❑Ù➜ÿ➚❁➯✱ ✹➞ê❣♣✛❁❲✞➜ ➀➷➑✱❪➚⑩➙➾✛❁➯⑩❺✔↕❦➷✮Ñ ✚➵✒➃➂✧ù➌➴➏➀➧✭✂ú➨Ú✟➬✧ 1
Figure2:2012年诺贝尔经济学奖得主阿尔文·罗斯 阿尔文-罗斯(A1vinE.Roth,1951.12.19-),哈佛商学院经济及工商管 理教授。罗斯1971年本科毕业于哥伦比亚大学，获得运筹学学士学位，随 后赴斯坦福大学攻读研究生，1973年获运筹学硕士学位，一年后获运筹学 博士学位。离开斯坦福之后，罗斯直到1982年一直在伊利诺斯大学任教。 此后他在匹兹堡大学担任安德鲁梅隆经济学教授直到1998年，之后他加入 哈佛大学并在此工作至今。罗斯是美国杰出年轻教授奖：斯隆奖的获得 者，古根海姆基金会会士，美国艺术和科学院院士。他还是美国国家经济 研究局(NBER)和美国计量经济学学会成员。罗斯在博弈论、市场设计和 实验经济学领域都曾作出重大贡献，在很多方面印证了“Gale-Shapley方 法”。 2
Figure 2: 2012❝ì✓✏➨▲➷ø✚❒❈✏➞·Û❞ ❈✏➞-Û❞(Alvin E. Roth➜1951.12.19-)➜▼➹û➷✓➨▲✾óû✰ ♥✓➬✧ Û❞1971❝✢❽✳➆✉①Ô✬æ➀➷➜➻✚✩✃➷➷➡➷➔➜➅ ❆❞✧✹➀➷ôÖï➘✮➜ 1973❝➻✩✃➷❛➡➷➔➜➌❝➻✩✃➷ ➷➡➷➔✧❧♠❞✧✹❷➜Û❞❺✔1982❝➌❺✸➒⑤ì❞➀➷❄✓✧ ❞➛✸➎❬✄➀➷ú❄❙✙➦-r➒➨▲➷✓➬❺✔1998❝➜❷➛❭❭ ▼➹➀➷➾✸❞ó❾➊✽✧ Û❞➫④■★Ñ❝➈✓➬ø➭❞➒ø✛➻✚ ö➜✔❾➦✵➘✼➡➡➡➜④■➨âÚ❽➷✓✓➡✧ ➛❸➫④■■❬➨▲ ï➘Û(NBER)Ú④■❖þ➨▲➷➷➡↕✡✧ Û❞✸➷❽Ø✦➼⑤✗❖Ú ➣✟➨▲➷✰➁Ñ◗❾Ñ➢➀③➜✸éõ➄→❁②✡✴Gale-Shapley➄ ④✵✧ 2
CAFP Figure3:2012年诺贝尔经济学奖得主劳埃德，夏普利 劳埃德.夏普利(1923年6月2日生于美国麻省剑桥)是杰出的美国数学家 和经济学家，对数理经济学、特别是博弈论做出过杰出贡献，被认为是博 弈论的具体化身。1943年应征入伍，作为美国空军士兵在中国成都服役， 并因破解苏联气象密码获得铜质勋章。1948年获得哈佛大学数学学士学 位。1953年获得普林斯顿大学博士学位。1954年重返兰德公司至1981年。 自1981年起，任加州大学洛杉矶分校数理经济学教授。夏普利是1994年诺 贝尔经济学奖得主纳什的高中同学。 夏普利获奖的最大原因是他和David Gale(1921.12.13-2008.3.7）于1962年 所创的“Gale-Shapley方法”，其核心是市场匹配的合理原则应该是“情投 意合”而非“价高者得”. 3
Figure 3: 2012❝ì✓✏➨▲➷ø✚❒◆❉✙·❣✃⑤ ◆❉✙·❣✃⑤(1923❝6✛2❋✮✉④■æ➂ê①)➫★Ñ✛④■ê➷❬ Ú➨▲➷❬➜éê♥➨▲➷✦❆❖➫➷❽Ø ❽Ñ▲★Ñ③➜✚❅➃➫➷ ❽Ø✛ä◆③✜✧1943❝❆✍❭❰➜❾➃④■➌✁➡❲✸➙■↕ÑÑ➳➜ ➾Ï➺✮⑨éí➊➋è➻✚Ô➓✃Ù✧1948❝➻✚▼➹➀➷ê➷➷➡➷ ➔✧1953❝➻✚✃✕❞î➀➷➷➡➷➔✧ 1954❝➢❼❂✙ú✐➊1981❝✧ ❣1981❝å➜❄❭➨➀➷âë➑➞☎ê♥➨▲➷✓➬✧ ❣✃⑤➫1994❝ì ✓✏➨▲➷ø✚❒❇➓✛♣➙Ó➷✧ ❣✃⑤➻ø✛⑩➀✝Ï➫➛ÚDavid Gale (1921.12.13-2008.3.7) ✉ 1962❝ ↕▼✛✴Gale-Shapley➄④✵➜ÙØ✪➫➼⑤➎✛✛Ü♥✝❑❆❚➫✴➐Ý ➾Ü✵✌➎✴❞♣ö✚✵. 3
KSW35断韩纱服感 Figure4:稳定婚姻问题 By all means marry.If you get a good wife you will become happy and if you get a bad one you will become a philosopher'?--Socrates(苏格拉 底B.C.469-B.C.399) Gale-Shapley.方法最初应用于婚烟匹配问题，称为“stable marriage problem”(简称SMP)。该问题如下： 设有N个想结婚的男子和N个想结婚的女子，他们每个人都对每个异性 按照自己钟情的程度给予排名（排名越靠前表示钟情的程度越深）.问题是如 何匹配才能使每个人的选择都是最好的呢？ 4
Figure 4: ➢➼➫Ó➥❑ By all means marry. If you get a good wife you will become happy and if you get a bad one you will become a philosopher?—Socrates(⑨❶✳ ✳B.C.469-B.C.399) Gale-Shapley➄④⑩Ð❆❫✉➫Ó➎✛➥❑➜→➃✴stable marriage problem✵(④→SMP)✧❚➥❑❳❡➭ ✗❦N❻➂✭➫✛■❢ÚN❻➂✭➫✛å❢➜➛❶③❻❁Ñé③❻➱✺ ❯ì❣❈➝➐✛➜Ý❽❷ü➯ (ü➯✖❶❝▲➠➝➐✛➜Ý✖✢). ➥❑➫❳ Û➎✛â❯➛③❻❁✛➚❏Ñ➫⑩Ð✛◗➸ 4
A(1,2) 1(B,A) B(1,2) 2(A,B) Figure5:稳定婚姻 什么是稳定婚姻？ 首先，稳定婚姻当然应该是每个人都有自己的配偶 其次，如果现有的婚烟匹配中，某男子更钟情于某女子而不是现在的 妻子、同时该女子也更钟情于该男子而不是现在的丈夫，则他们有可能 “私奔”，这样的婚姻自然不是稳定的，称为不稳定婚姻匹配(unstable marriage matching).因此，稳定的婚姻匹配应该杜绝这样的男子和女子同 时存在，即稳定婚姻匹配应该是没有男子更钟情于某女子的同时该女子也 更钟情于该男子.换句话说，对于每一个人，他心目中比他当前伴侣更好的 异性，都不会认为他也是一个更好的选择。 问题：稳定婚姻是否存在？ 答案：l962年，Gale-Shapley说，是的，稳定婚姻一定存在（但不必唯 -),因为Gale-Shapley算法.(D.Gale and L.S.Shapley:"College Admis- sions and the Stability of Marriage",American Mathematical Monthly 69, 9-14,1962.) 例子.如图所示，设有2男A、B,2女1、2，括号内的顺序表示他们对 异性的钟情程度.试给出最好的婚姻匹配 课堂练习.设有3男A、B、C,3女1、2、3，他们各自对异性的钟情程 度如下表： A(1,2,3) 1(C,A,B) B(1,3,2) +9◆◆+ 2(A,C,B) C(2,3,1) 3(A,B,C) 试给出最好的婚姻匹配 5
Figure 5: ➢➼➫Ó ➓♦➫➢➼➫Ó➸ ➘❦➜➢➼➫Ó✟✱❆❚➫③❻❁Ñ❦❣❈✛✛ó. Ù❣➜❳❏②❦✛➫Ó➎✛➙➜✱■❢➁➝➐✉✱å❢✌Ø➫②✸✛ Ó❢✦ Ó➒❚å❢➃➁➝➐✉❚■❢✌Ø➫②✸✛à➴➜❑➛❶❦➀❯ ✴❤✛✵➜ù✘✛➫Ó❣✱Ø➫➢➼✛➜ →➃Ø➢➼➫Ó➎✛(unstable marriage matching). Ï❞➜➢➼✛➫Ó➎✛❆❚Úýù✘✛■❢Úå❢Ó ➒⑧✸➜ ❂➢➼➫Ó➎✛❆❚➫✈❦■❢➁➝➐✉✱å❢✛Ó➒❚å❢➃ ➁➝➐✉❚■❢. ❺é④❵➜é✉③➌❻❁➜➛✪✽➙✬➛✟❝❾➾➁Ð✛ ➱✺➜ÑØ➡❅➃➛➃➫➌❻➁Ð✛➚❏✧ ➥❑➭➢➼➫Ó➫➘⑧✸➸ ❽❨➭1962❝➜Gale-Shapley ❵➜➫✛➜➢➼➫Ó➌➼⑧✸(✂Ø✼➁ ➌)➜Ï➃ Gale-Shapley ➂④.( D. Gale and L. S. Shapley: ”College Admissions and the Stability of Marriage”, American Mathematical Monthly 69, 9-14, 1962.) ⑦❢. ❳ã↕➠➜✗❦2■A✦B➜2å1✦2➜✮Ò❙✛❫❙▲➠➛❶é ➱✺✛➝➐➜Ý. ➪❽Ñ⑩Ð✛➫Ó➎✛. ➅✱ö❙. ✗❦3■A✦B✦C➜3å1✦2✦3➜➛❶❼❣é➱✺✛➝➐➜ Ý❳❡▲➭ A(1, 2, 3) · · · · · · 1(C, A, B) B(1, 3, 2) · · · · · · 2(A, C, B) C(2, 3, 1) · · · · · · 3(A, B, C) ➪❽Ñ⑩Ð✛➫Ó➎✛. 5
Figure6:盖尔-夏普利算法 Gale-Shapley方法：M=男子的集合，W=女子的集合 function stableMatching Initialize all m∈M and w∈V to free while 3 free man m who still has a woman w to propose to w=m's highest ranked such woman to whom he has not yet proposed if w is free (m,w)become engaged else some pair (m',w)already exists if w prefers m to m' (m,w)become engaged m'becomes free else (m',w)remain engaged } 6
Figure 6: ❳✏-❣✃⑤➂④ Gale-Shapley➄④: M=■❢✛✽Ü➜W=å❢✛✽Ü function stableMatching { Initialize all m ∈ M and w ∈ W to free while ∃ free man m who still has a woman w to propose to { w = m0 s highest ranked such woman to whom he has not yet proposed if w is free (m, w) become engaged else some pair (m0 , w) already exists if w prefers m to m0 (m, w) become engaged m0 becomes free else (m0 , w) remain engaged } } 6
Figure7:恋爱策略 求婚策略、男子主动策略 第一轮：先让所有男子向自己最满意的女子求婚，然后让所有女子挑 选最中意的，并剔除所有其它人选 第二轮：让没有被选中的男子再次向自己第二满意的女子求婚，然后 让所有女人挑选最中意的，并剔除所有其它人选： 第三轮：重复第二轮，直到所有人找到了配偶为止 结论：(1)男子主动策略是男子的最佳策略！换句话说，每个男子的妻 子是“最佳的”，即在稳定婚姻匹配中每个男子更钟情的女子都会认为现 在的丈夫更好 (2)男子主动策略是女子的最差策略！换句话说，每个女子的丈夫是 “最差的”，即每个女子现在的丈夫是所有稳定婚姻匹配中她所最不心仪 的男子 ©©启示1：下下手为强，后下手遭殃！©© ©©启示2：数学可以帮你获得诺贝尔经济学奖，也可以帮你实现 美好的人生理想！©© 7
Figure 7: ô❖üÑ ➛➫üÑ✦■❢❒➘üÑ ✶➌Ó➭❦✹↕❦■❢➉❣❈⑩÷➾✛å❢➛➫➜✱✹↕❦å❢❪ ➚⑩➙➾✛➜➾●Ø↕❦Ù➜❁➚➯ ✶✓Ó➭✹✈❦✚➚➙✛■❢✷❣➉❣❈✶✓÷➾✛å❢➛➫➜✱ ✹↕❦å❁❪➚⑩➙➾✛➜➾●Ø↕❦Ù➜❁➚➯ ✶♥Ó➭➢❊✶✓Ó➜❺✔↕❦❁é✔✡✛ó➃➂. ✭Ø➭(1)■❢❒➘üÑ➫■❢✛⑩❩üÑ! ❺é④❵➜③❻■❢✛Ó ❢➫✴⑩❩✛✵➜❂✸➢➼➫Ó➎✛➙③❻■❢➁➝➐✛å❢Ñ➡❅➃② ✸✛à➴➁Ð. (2)■❢❒➘üÑ➫å❢✛⑩☛üÑ! ❺é④❵➜③❻å❢✛à➴➫ ✴⑩☛✛✵➜❂③❻å❢②✸✛à➴➫↕❦➢➼➫Ó➎✛➙➝↕⑩Ø✪↕ ✛■❢. ,, é➠ 1➭ ❡❡➹➃r➜❡➹❀✠! ,, ,, é➠ 2➭ ê➷➀➧➄❭➻✚ì✓✏➨▲➷ø➜➃➀➧➄❭➣② ④Ð✛❁✮♥➂! ,, 7