2012 年諾貝爾經濟學獎得主 Alvin Roth 與 Lloyd Shapley 對經濟學的發展做出了哪些貢獻? | 知乎問答精選

 

A-A+

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

2019年03月11日 知乎問答精選 暫無評論 閱讀 1 ℃ 次

【陳行的回答(44票)】:

可以預見的是

很長一段時間,大家會弄混兩個螺絲

本來的大熱門--斯蒂芬羅斯沒有獲獎,這個羅斯創立了大名鼎鼎的套利定價理論。我現在看的教材就是他的。為他打抱不平!

獲獎的是另一個螺絲---大家記清楚以備茶餘飯後談資

後一個羅斯的理論頗為拗口,先占樓。待續

-------------------------------------------

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

下面是 我不知 百度之 環節

沙普利使用合作博弈方法來研究和對比不同的匹配方法,其關鍵在於保證配對是穩定的。所謂穩定,指的是不存在這樣兩個市場主體,它們都更中意於他人,勝過它們當前的另一半匹配對象。

沙普利和他的同事找到了所謂的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求過婚。推出矛盾,故不可能出現私奔。

【袁亮的回答(5票)】:

【王諾諾的回答(11票)】:

對我來說。

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

【JacobK的回答(1票)】:

班門弄斧,同樣是男士優先的匹配算法:

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

【知乎用戶的回答(0票)】:

songshuhui.net/archives

誰能說說這有什麼特別好處,鄙人粗淺,除了感覺到被配圖簡介所掩蓋的部分潛力,感覺像周星馳看鞏俐:很普通嘛

標籤:-經濟 -投資 -經濟學 -商業 -博弈論 -諾貝爾獎 -瑞典銀行經濟學獎


相關資源:





給我留言