2012 年諾貝爾經濟學獎得主 Alvin Roth 與 Lloyd Shapley 對經濟學的發展做出了哪些貢獻？

12-05

中文新聞來源：http://finance.ifeng.com/roll/20121015/7150085.shtml
英文新聞來源：http://news.yahoo.com/2-americans-win-nobel-economics-prize-111239568--finance.html
其中英文的描述是：Americans Alvin Roth and Lloyd Shapley were awarded the Nobel economics prize on Monday for research that helps explain the market processes at work when doctors are assigned to hospitals, students to schools and human organs for transplant to recipients.
這兩位的研究幫助解釋了醫院簽約醫生，學校錄取學生，以及移植從捐獻者到接受者的過程中市場機制起到的作用。具體是什麼內容呢？另外此二人還有哪些著作或者理論？

算是做這個方面研究的，有如下見解：
Shapley 可以算是 von Neumann 之後最厲害的數理經濟學家，沒有之一。把他的工作分開，至少可以拿三個諾獎了：
1、關於 stochastic game 的結果，被視為 stochastic game 的開山之作，雖然我不是特別的熟悉。
2、Gale Shapley deferred acceptance algorithm，整個 matching 理論可以說是建立在這個演算法以及後面的 gale"s top trading cycles algorithm 之上的。提一點，整個模型和 stable matching 的存在性是 Gale 提出的，但他沒解決，發信給幾個朋友，其中就有 Shapley，後者直接給出了 DA 演算法。
3、Shapley value，這個不用說，合作博弈中最著名的概念之一。

其實，老沙早該拿獎了，下面列出類似的諾獎的貢獻以作對比
Nash：nash equilibrium、nash bargaining solution，當然 nash 還有一個嵌入定理以及一些數學方面的結果
selten：subgame perfect equilibrium 和 perfect equilibrium
harsanyi：bayesian game
aumann：common knowledge
schelling：恕我孤陋寡聞，不知這位幹了什麼
hurwicz：機制設計的鼻祖
maskin：implementation theory，repeated game 里也有貢獻
myerson：revelation principle，optimal auction

當然，還要為 gale 鳴不平，08 年就去世了，否則 matching 的這個諾獎他也有份。

有人提到另一個 https://en.wikipedia.org/wiki/Stephen_Ross_%28economist%29，我覺得 Alvin Roth 並不比前者差，將整個理論用於實際，比如學生入學、換腎這些問題。Roth 在其中可以算得上是領袖，當然 deserve 這個獎項了。

2012年的獎給matching這個微觀理論的子方向，所以雖然獲獎二人尤其Shapley在經濟學上有別的殊大貢獻，我僅回答他們在matching方向的工作。

Shapley在此方向的貢獻主要是與Gale合寫的這個方向的開山論文 (College admissions and the stability of marriage)，在文中一舉奠定了這個方向的1.核心問題 (stability)，2. 解的概念 (stable matchings), 3. 分析框架，並且 4. 證明了解的存在性，找到了求解的演算法。有趣的是這篇創始論文寫作的初衷竟然類似「趣味數學」, 是作者為了闡明數學素質教育的合理方式，說教數學「學以致用」而發展一個例子（見原文結尾部分）。發表文章的期刊American Mathematical Monthly不是嚴肅的學術期刊，而是面向普通讀者的科普刊物。所以文章開天闢地多少有點無心插柳。Shapley後來在matching方向的工作不算太多。Gale倒是一鼓作氣繼續做了很多貢獻，可惜逝不逢時，否則這次諾獎也必有他一份。

Roth在matching的貢獻可分三方面。其一是理論方面：Roth在八十年代和一系列合作者的工作極大開拓了對於stable matchings的分析；Roth也是把non-cooperative game theory引入matching研究的先驅（之前matching的思想範式是略已過氣的cooperative game theory），讓matching融入了博弈論的主流。其二是實踐方面：Roth仔細分析了不少實際的雙邊matching market，提出很多對現有分配機制的修改整肅的意見，漸漸被相關單位採納並且運行良好（這應該是他最重要的貢獻，也是極少有的經濟學理論直接指導政策制定並收效明顯的例子）。其三是培養新人方面：Roth在哈佛時指導的不少學生後來漸漸成為了matching研究的中堅力量；雖然matching「學界」現在有點「近親繁殖」的意思，但是關係親密，其樂融融，有經濟學界不多見的大家庭的感覺。

說句題外話：2009年諾貝爾經濟獎宣布的當天早晨我在Roth老師教的Market Design的課堂里；同學們紛紛祝福他早日獲獎，老師還很不好意思，言語無措，哈哈。

說一個課里學的內容：Bondareva-Shapley Theorem

1960年科斯發表了The problem of social cost，可謂一時洛陽紙貴。但人們逐漸發現所謂Coase theorem自身的模糊性導致和後來的許多的理論很難協調。

比如考慮一個合作博弈，Aragaki，Bob和Carl考慮合作。第一個人的邊際貢獻是0，第二個人的邊際貢獻是1，第三個人的邊際貢獻是0. 假設獲得支付最小的那個人是Carl，那麼他可以在現有的支付 $x$ 基礎上向Aragaki提議 $(1-x-epsilon, 0, x+epsilon)$ 的分配方案，而Aragaki也自然樂於接受。但是這是我們把之前故事裡人物換一下，比如Carl換成Bob，這樣的故事可以永遠進行下去。

比如這裡我們說的當一個合作博弈有一個empty core的時候。Bondareva（1963）和Shapley（1967），也就是Bondareva-Shapley Theorem可以看成給出了non-empty core的充要條件。雖然它對計算core沒什麼幫助，但對證明某一類博弈是否具有non-empty core是有用的（這塊我還沒有學習，可參考 @陳茁的答案：經濟學中有哪些著名的均衡？它們之間是否存在聯繫？ - 陳茁的回答）。

首先coalitional game with transferable utility的定義。對於參與者的集合 $N$ ，它的每個子集在這個博弈中的新名字是coalition，TU game的核心是賦予每個coalition一個金額，使得只要這個coalition包含的所有成員一致同意（形成這個coalition而不是加入其它的coalition，以及這個金額的分配方案），成員就可以獲得事前約定的金額。可以簡潔的表示為： $v: 2^N setminus varnothing o mathbb{R}$

這個TU game的core(表示為 $mathcal{C}(N; v)$ )則是「穩定的」，不會出現上面舉的Aragaki，Bob和Carl的情況的分配方案。具體的： $mathcal{C}(N; v) := { {x_i}_{i in N} mid sum_{iin N}x_i = v(N), forall S subsetneq N(sum_{iin S}x_i geq v(S))}$

對於一族coalitions, $mathcal{D}$ (coalition就是組成players的集合 $N$ 的子集)，如果叫做 balanced collection of coalitions，如果對於所有的 $i in N$ ，我們有一組賦予每個 $mathcal{D}$ 中的coalition的權重，表示為 $S mapsto delta_S$ (我們要求 $delta_S in mathbb{R}_{++}$ )滿足：

$sum_{{S in mathcal{D} mid i in S}} delta_S = 1$

或者也可以用示性函數表示，這裡 $chi^S : N o {0,1}$ 滿足

$chi^S (i) egin{cases} 1 i in S \ 0 i otin S end{cases}$
Balanced collection of coalitions滿足存在一族balancing weight， ${delta_S}_{S in mathcal{D}}$ 使得
$sum_{S in mathcal{D}} delta_S chi^S = chi^N$

Bondareva-Shapley Theorem: TU game的core如果是非空的話，則對於任何一個balanced collection of coalitions， $mathcal{D}$ ，它的任何一個balancing weight， ${delta_S}_{S in mathcal{D}}$ 滿足：
$v(N) geq sum_{S in mathcal{D}}delta_S v(S)$

充分性證明略複雜，可參考博弈論教科書界的MWG，Maschler，Solan and Zamir（2013）（Game Theory - Cambridge Books Online）。

回到我們Aragaki，Bob和Carl的TU game，考慮 $mathcal{D} = {{Aragaki, Bob}, {Bob, Catherine}, {Catherine, Aragaki}}$ ,則他們對應的 $delta_S$ 均為 $frac{1}{2}$ , 所以 $sum_{S in mathcal{D}}delta_S v(S) = frac{3}{2}$ ,但是 $v(N) = 1$ ，所以Bondareva-Shapley Theorem的條件沒有達成。

可以預見的是
很長一段時間，大家會弄混兩個螺絲
本來的大熱門--斯蒂芬羅斯沒有獲獎，這個羅斯創立了大名鼎鼎的套利定價理論。我現在看的教材就是他的。為他打抱不平！
獲獎的是另一個螺絲---大家記清楚以備茶餘飯後談資
後一個羅斯的理論頗為拗口，先佔樓。待續

-------------------------------------------
再次致敬約翰納什！這次的熱點又是博弈論

下面是 我不知百度之環節

沙普利使用合作博弈方法來研究和對比不同的匹配方法，其關鍵在於保證配對是穩定的。所謂穩定，指的是不存在這樣兩個市場主體，它們都更中意於他人，勝過它們當前的另一半匹配對象。
　　沙普利和他的同事找到了所謂的GS演算法(Gale-Shapley演算法)。這一方法還限制了市場主體操縱匹配過程的動機。沙普利所設計的方法能系統性地對兩個市場主體至少其中一方有利。
　　羅斯意識到了沙普利的理論和計算可讓實踐中重要市場的運作方式變得更清晰。在一系列的實驗性研究中，羅斯和他的同事表明，為了理解某個特定市場制度為何成功，研究其穩定性是關鍵所在

我們定位在GS演算法上，發現這個是關鍵，似乎別的都是廢話。
好，現在上經典得不能再經典的例子

給定一組男人和一組女人，每個人在心目中都對所有的異性有一個傾慕度排序，從最喜歡到最不喜歡依次排序1、2、3。現在給出問題，如何對這些男女進行配對使得在分配好後不出現偷情的現象。
演算法
可以有男人優先和女人優先兩種演算法。以男人優先為例，為代碼如下：

1. while 存在男人m是自由的且還沒對每個女人都求過婚
2. 選擇這個男人m
3. 令w是m的優先表中還沒求過婚的最高排名的女人
4. if w是自由的
5. （m，w）變成約會狀態
6. else w當前與m1約會
7. if w更偏愛m1而不愛m
8. m保持自由
9. else w更偏愛m而不愛m1
10. （m，w）變成約會狀態
11. m1變成自由
12. endif
13. endif
14. endwhile

需要特別注意的是！雖然從第9、10行來看，女人能夠選擇更好的伴侶。但從第3行來看，男人能夠優先選擇排名最高的女人。實際上，第9、10行只是為了保證婚姻的穩定性。

我們看-完代碼就明白了，這個GS就是為了確保匹配穩定！
不難推出，學生入學，骨髓捐獻都是這個求婚拒絕演算法的擴展甚至生搬硬套

沙普利的牛逼之處，在於他證明了任意兩個集合，這樣的匹配總是存在的

以下是高校錄取的例子
我們將看到Gale-Shapley解決高校錄取問題的一個例子：
a. 假設有5個高校 U = {W, X, Z, Y, V}，每個高校只能錄取4個學生，一共錄取20個學生
b. 總共有20個考生，為了方便將他們按成績排序好 S = {sA, sB, sC,..., sS, sT}
c. 每個高校對考生的偏好相同，都希望得到最好的學生，即偏好都是(sA &> sB &> sC ... &> sS &> sT)
d. 每個考生對五個高校都有一個偏好排序，例如 sa 對五個學校好感度排名是（W &> X &> Z &> Y &> V）,按照上一節的方法對偏好表擴充，變成（W1 &> W2 &> W3 &> W4 &> W5 &> X1 &> X2 ...&> V4 &> V5）。
將我們的所有學生的偏好列成下面的表格：

經過我們用python語言（強烈推薦解決小問題時用此種語言）寫的小程序來實現Gale-Shapley演算法，最終給出了最穩定匹配如下：
學校 W 的錄取名單是（sA, sB, sD, sF）
學校 X 的錄取名單是（sC, sI, sJ, sP）
學校 Z 的錄取名單是（sE, sM, sR, sS）
學校 Y 的錄取名單是（sH, sK, sQ, sT）
學校 V 的錄取名單是（sG, sL, sN, sO）
如果Gale-Shapley演算法是有效的話，那麼我們可以肯定這組錄取結果必定達到了「社會最優」。

So What？
搞研究的人最怕別人問：so what? 所以接下來，我們來看看結果揭示了一個什麼重要啟示。
首先，我們的演算法是好的。因為每一位被錄取的同學都能在自身成績之上獲得最大的滿足：他們當中沒有人被自己最不喜歡的學校錄取！
其次，注意 sA, sB, sC, sD 等成績名列前茅的同學，他們都被自己的第一志願錄取了，也就是說他們都能夠去自己的dream school！話語權最是歸牛人的，對吧？
再來看看成績最差的兩位同學，sS, ST同學成績雖然不怎麼樣，但是一個被自己的第三志願，另一個被自己的第二志願錄取了，結果還是很理想的。所以，選學校的確很重要，避開牛人們哄搶的學校是一種不錯的策略。

搞清楚這個演算法，大致就知道這個穩定匹配是個啥東西了。
想到了再補充歡迎拍磚！

---------------------------------
個人吐槽，這個理論看似很玄乎，但數學上對於這個匹配的問題似乎早有研究。而且證明唯一性從數學的角度是一個難度很低的活。這項工作也更偏實用而非理論。經濟學獎頒給這個工作，我個人持保留意見。我認為套利定價是難得一見的理論，斯蒂芬羅斯更值得授予諾貝爾獎。這個獎，我只能說，約翰納什太TM碉堡了

-----------------------
再補充點從數學的角度
演算法的可終止性可證：每個男人按照自己的偏愛序一個個求婚下來，一定有一個女人會要他——試想一個男人被一百個女人拒絕掉了，那他的偏愛序中已經沒有人可以求婚了，所以他得不到配對，對應地對面也肯定有一個剩女，可是這個剩女曾經拒絕過他呀，也就是說她有更好的追求者呀，她怎麼可能成為剩女呢？
演算法的正確性也可證：假設有A男和B女私奔了。那麼A在B的偏愛序中必然比B的丈夫靠前，按照演算法，女人最後選擇的一定是所有向她求婚的男人中她最喜歡的，這就是說A沒有向B求過婚（要不然B選的就是他了）。然而，男人是按照自己的偏愛序依次求婚的，而A又喜歡B甚於自己的老婆，所以A又必然向B求過婚。推出矛盾，故不可能出現私奔。

班門弄斧，同樣是男士優先的匹配演算法：
for m in NotMatchedMen[]
for w in m.desireList[]
if w. available()
match(m,w) // and set m. available() and w. available() False.
else // means: w. available() is False, w.matched() is m1.
if w.prefer(m) &> w.prefer(m1)
match(m.w)
m1. available() set True
endif
endif
endfor
endfor

對我來說。
他的配對理論教給我，遇到喜歡的男生要主動去追。

Alvin Roth不了解。
至於Lloyd Shapley，學過博弈論的沒有人不知道Shapley value吧。
只想感嘆下，Shapley和Nash 是同一個時代的，等到今年才獲獎。由此可見，得諾獎不但要看貢獻，還得要活的久。
更新下答案：http://www.infzm.com/content/82035

居然沒有提到Who gets what and why.