Roommate market problem: (N,P) 其中N為agent set， P_i 為over N的linear order

matching f:N o N

marriage market 為roommate market 的特殊形態

設定基本一致，問題在於roommate market 可能core為空

不為空的roommate market 叫solvable problem

通過block pair的方法可以把matching的改變過程定義為一個Directed graph (V,E),其中端點v為某個matching f，連接f和f的邊緣e為f變成另一個f的過程（by blocked pair path）

Main Results:

1)可解性(Tan, 1991)：

提供了可解性的充分必要條件

考慮N的一個子集A，對其排序寫為(a1,a2,...ak)。討論一下三種情況

k=1: A為單點集 （ singleton）

k=2: A為pair of mutually acceptable agents IFF forall iin{1,2}:a_{i-1} P_{i}a_i ext{ (subscript modulo 2) }

k>2:A為ring IFF forall iin{1,...,k}: a_{i+1}P_{i}a_{i-1}P_i a_i

方便起見這3種case的A都叫環

將N分為一個partition M,M是stable的 IFF

1） M里的每個元素A都是環

2） forall A,Bin M ext{ (A=B is possible) }: forall a_i,b_j ext{ such that }a_{i+1} eq b_j:b_j P_{a_i}a_{i-1} Rightarrow b_{j-1} P_{b_j}a_i

對一個M，我們將M里的元素A稱作odd/even的如果|A|為奇數/偶數

Remark: 任何(N,P)都有stable partition M；且任意兩個stable partition的odd sets 都一樣（kind of lone wolf thm ）————這裡可將M視為若干個子市場：母市場N變成M，M里每個人內部消化

THM 1: (N,P)不可解 IFF N存在某個stable partition M有odd set

2） Random Path (DMX,2004: idea from RV 1990 and Chung 2000)：

THM 2:考慮一個可解的(N,P). 對任意matching f, 存在一個path {f,f_1,...,f_K} 。其中fk+1是由fk的blocked pair path生成，而fK是stable的

3） P-stability (ILM 2008,弱化了穩定性) ：

考慮一個stable partition M. 某個matching f為P-stable IFF forall Ain M: forall iin{1,..,k}:f(a_i) in{a_{i+1},a_{i-1}} ext{ except for a unique agent j with } f(a_j)=a_j ext{ when A is odd}

簡而言之就是通過幹掉某個人(單身forever)來讓odd set 變even set

Remark: random path在這裡也成立。 從任意matching f開始可以生成一個path保證重點是個P-stable matching

4） Absorbing sets (ILM 2013,從圖論討論)

考慮一個abstract system (F,R) 其中F為所有matching的set，R為F上的二項關係。R表示了blocked pair path的路徑

f R f IFF f是由f生成(by some blocked pair)

所以對任意（N,P）可以生成一個(F,R)

考慮(F,R)的一個閉環關係 R^T ：如果存在一個path {f_1,f_2,..f_K} such that forall 2<kleq K:f_k R f_{k-1} 則 f_K R^T f_1

Remark: 顯而易見這個閉關關係滿足推移性

對F的一個子集G，我們稱G為關於(F,R)的absorbing set IFF

forall f,fin G (f eq f): f R^T f \ forall fin G: otexists fin Fsetminus G ext{ such that } f R^T f

簡而言之 就是G內部隨便搞，但是外部穩定(outer stability)

考慮某個stable partition M,我們可以生成一個absorbing set G.

在G里，agent分為兩種：1種是找到了穩定的另一半，不會block了；另一種是找不到穩定的另一半，AKA 對G里的某個f 第二種agent可以組成block pair。

對某個G，我們將第一種agent稱為satisfied agents S(G)，第二種稱為dissatisfied agents D(G)

對任意兩個absorbing set G,G，它們的agent分類一樣 AKA S(G)=S(G),D(G)=D(G)

5)Stochastic stability (KKW, 2010 類似perfect equ)

類似abstract system，對prblem構造一個馬爾科夫過程(F,T), 其中F為所有matching的set，T為transition matrix

對任意兩個matching f,f T(f,f)為f到f『的概率

實際變化還是和之前一樣follow blocked pair path

考慮(F,T)上的absorbing set G，所有G的集合為AG

Remark: stable matching set subset AG subset IR set

對矩陣T，類似完美/顫抖手均衡，考慮agents犯下mistake的可能，犯錯概率為e

則有新的轉移矩陣Te

Te(f,f)=T(f,f)+ecdotsum_{{i,j}in NB(f,f)} q(f,{i,j})

NB(f,f)為f到f』變換里的non-blocking pair們的set

q為在state f時(顯然馬爾科夫下每個matching f都是個state了)某個non-blocking pair (i,j)被選上block的概率

顯然，因為可能犯錯，所以這個轉移的AG就只能是F本身了——因為在任何state都可能犯錯

於是我們知道對於這樣的轉移我們有穩定的分布(invariant distribution) p^*_e

接著類似完美均衡讓e向0收斂，我們有limit invariant distribution p* over (F,T)

p*的support稱作stochastically stable matching set SS

對任意f,f定義它們的距離為不變的pair相似度 d(f,f)=|{iin N| f(i)=f(i)}|

類似地對任意matching f和某個F的子集F，兩者距離為 d(f,F)=max_{fin F} d(f,f)

THM 1: 考慮AG里的一個set G和一個non-absorbing matching f. 存在一個blocking path 從f到f*。其中 f^*in G,d(f,G)geq d(f,G)

THM 2:對任何roommate problem,其AG=其SS

推薦閱讀：

相关文章