穩定分配理論

穩定分配理論是由2012諾獎獲得者沙普利使用合作博弈的方法來研究和對比不同的匹配方法而創立的理論。該理論的難點在於要保證一個配對是穩定的。所謂穩定，指的是不存在這樣兩個市場主體，他們都更中意於彼此、勝過他們當前的另一半。1962年，沙普利和他的同事蓋爾找到了一個叫做GS演演算法(Gale-Shapleyalgorithm)的方法。他們在《College admissions and the stability of marriage》一文介紹了分配理論下的高校問題及穩定婚姻機制。這篇論文也為穩定分配理論提供了理論基礎。運用GS演演算法，他們分別解決了以下兩個難題：一是如何使學校招收到更滿意的學生，而新生也不必因報錯志願而落榜。二是如何使單身男女實現速配，又不發生與他人私奔的行為。在第二個問題的研究中，他們假設有10名男人和10名女人，設想先讓所有男人向自己最滿意的女人求婚，然後讓所有女人挑選最中意的男人，並剔除所有其他人選；再讓沒有被選中的男人再次向自己第二滿意的女人求婚，然後讓所有女人挑選最中意的男人，並剔除所有其他人選。這一過程不斷重複，直到所有人找到了配偶為止。他們的這種方法能確保匹配是穩定的，不會出現婚後私奔等現象。沙普利從數學和博弈論的角度，尋求出了這類分配問題的穩定解，為更多經濟問題的解決提供了有意義的指導和借鑒。這些方法同時也限制了市場主體操縱匹配過程的動機，而且沙普利設計的方法能夠系統性地對兩個市場主體中主動的一方有利。

穩定匹配的核心思想是實現一種穩定狀態，在這種狀態下，在匹配完結時不再存在這樣兩個市場主體，它們都更中意於他人，勝過它們當前的另一半匹配對象。在現實中，我們熟悉的8分鐘相親、學校和學生匹配等例子就是基於穩定市場匹配理論的思想發展而來的。其中雙邊模型和延遲接受演演算法是穩定匹配理論的兩塊重要基石。

雙邊匹配模型很多市場及社會制度的主要功能就是讓其中的主體能和另一個主體相匹配：例如，學生和學校，職員和公司，適婚男女之間。這種市場匹配主要分為“單邊市場匹配”(Single-Sided MarketMatch)和“雙邊市場匹配”(Two-Sided MarketMatch)。其中“單邊市場匹配”指市場中僅存在一個集合，集合中的個體根據各自的偏好相互匹配。然而，單邊市場匹配中的“室友”現象會導致匹配的不穩定。當假設存在四個“室友”{1，2，3，4｝，其中1最偏好2，2最偏好3，3最偏好1，且他們把4都列為最不偏好者。在這種情況下，任何兩兩分組都無法實現穩定，因為和4分在一起的人會結束當前匹配去和已經匹配的人再次匹配，且這次新的匹配將會成功，使得市場一直無法實現穩定(Gale&Shapley，1962)。“雙邊匹配模型”最早由Gale和Shapley(1962)從研究學生申請學校模型和婚姻穩定問題而提出。所謂的“雙邊市場”是指存在這樣一個市場，市場中有兩類個體集合，第一類集合中的個體只能和第二類集合中的個體相匹配。他們證明了在這樣一個雙邊市場中，只要個體的偏好具有完備性及可傳遞性，以及市場足夠的自由，能允許個體進行任何潛在可能的匹配，

那麼市場中總是存在穩定匹配。同樣以4個室友為例，假設任意2個人睡上鋪，2個人睡下鋪，現在要求只有睡不同鋪的人相互匹配，此時就形成了雙邊市場匹配模型。同時，Gale和Sha-pley指出市場匹配穩定時滿足以下兩個條件：(1)市場中不存在來自不同類的兩個個體在偏好上可以實現相互匹配，但沒有匹配的情況；(2)已經配對成功的個體不會嘗試結束當前的配對，並試圖與來自另一類且已匹配成功的個體進行匹配。

雙邊匹配模型存在穩定匹配這一特性，使得其在理論和實踐上都得到了廣泛的關注，其中一個重要的運用就是勞動力市場的匹配。Shapley和Shubik(1972)利用數學模型抽象了一個充斥著不可分割商品的雙邊市場，市場中的每一位參與者既是商品的需求者也是商品的供給者。他們發現在這更為一般化的市場中匹配穩定的性質依舊很穩健。

Roth最早對雙邊匹配模型在解決實踐問題中的應用進行了研究。他意識到Shapley有關穩定市場匹配的理論和計算可讓市場的運作方式變得更清晰。20世紀50年代，美國內科醫生的初級勞動力市場的組織方式能保證絕大多數個體匹配成功，但這種匹配缺乏穩定性。Roth(1984)的後續實驗研究將Shapley的匹配設計應用於內科醫生的初級勞動力市場，他的研究結果表明該種匹配方法能減少原有組織方式下所產生的匹配不穩定及其它存在的無序問題。