網(wǎng)絡(luò)結(jié)構(gòu)與效應(yīng)原理：第10章 匹配市場

匹配市場

（買賣雙方直接見面的市場）（第10章）一個測試從上面的n*n矩陣中，選出n個不同行不同列的元素，使其和最大96314637296417963825461837267641213845216632974？？？匹配市場的場景某一類商品（例如房子），一群賣方和一群同樣數(shù)量的買方商品的質(zhì)量不同，大家的認(rèn)識也有差別買方對商品各有一個底價，都追求利益最大化市場按照供需關(guān)系自動調(diào)整價格，試圖達(dá)成買賣雙方的某種匹配我們關(guān)心最終能否大家都滿意賣方：市場清倉，商品在底價之上都賣出去了買方：得到差價最大的商品匹配市場基本模型：二部圖受限組

－

供不應(yīng)求

－

物以稀為貴，加價！偏好賣家圖價格調(diào)整后的偏好賣家圖市場是高效的：總是可以通過調(diào)整價格，得到具有完美匹配的偏好賣家圖匹配市場操作的一般過程（1）azcybx000賣方

買方12，4，28，7，67，5，2估值價格匹配市場操作的一般過程（2）azcybx100賣方

買方12，4，28，7，67，5，2估值價格匹配市場操作的一般過程（3）azcybx200賣方

買方12，4，28，7，67，5，2估值價格匹配市場操作的一般過程（4）azcybx310賣方

買方12，4，28，7，67，5，2估值價格特別地，實(shí)現(xiàn)了最大估值之和（23），即“社會最優(yōu)”我們不由得會想起開始的測試問題給定一個N＊N矩陣（A），從中選擇N個不同行不同列元素，aij（即i，j分別在｛1，2，…，N｝中遍歷），使得和最大。似乎是可以通過“調(diào)整價格”實(shí)現(xiàn)的！前面的測試?yán)齼r格＋1后偏好賣家圖沒變，稀缺商品再加價！9631463729641000096314637296412000買方受限組：｛2，4｝對應(yīng)賣方｛1｝1看那個大些的例子初始價格為0，形成偏好賣家圖，看其中是否存在一個買家受限組7963825461837267641213845216632974000000與受限買家關(guān)聯(lián)的賣家調(diào)整價格形成新的偏好賣家圖（看到邊的調(diào)整），再看是否存在買家受限組7963825461837267641213845216632974110101與受限買家關(guān)聯(lián)的賣家調(diào)整價格形成新的偏好賣家圖（看到邊的調(diào)整），再看是否存在買家受限組7963825461837267641213845216632974211202與受限買家關(guān)聯(lián)的賣家調(diào)整價格形成新的偏好賣家圖（看到邊的調(diào)整），此時已經(jīng)沒有受限組存在完美匹配7963825461837267641213845216632974311203匹配市場中的計(jì)算：啟示我們看到市場經(jīng)濟(jì)中的一些基本概念：理性的人、價格、供需關(guān)系、物以稀為貴、均衡、社會最優(yōu)，…通過一個簡單的模型：匹配市場（偏好賣家圖、根據(jù)受限組進(jìn)行價格調(diào)整，…）得到了生動的表達(dá)。而一旦這么做了，也隱含著一個計(jì)算問題的高效解決（市場機(jī)制扮演了一個高效的問題求解器的角色！）社會計(jì)算、跨學(xué)科計(jì)算思維的一個具體示例市場清倉價格的形成：算法給定買方估值，賣方從初始價格（0,0,…,0）開始，按照輪次進(jìn)行下述操作：構(gòu)造偏好賣家圖識別是否存在買方受限組（S）若沒有，則偏好賣家圖中存在完美匹配，結(jié)束。否則，將受限組對應(yīng)的賣方集合N(S)中的價格都＋1

（也就是根據(jù)需求調(diào)整價格，“物以稀為貴”）

若因此使所有賣方價格都>0，則統(tǒng)一約減最低價至0。開始下一輪。（注：統(tǒng)一約減不影響偏好賣家圖關(guān)系）這個過程為什么一定能結(jié)束？給定初始設(shè)定，按照輪次進(jìn)行下述操作：構(gòu)造偏好賣家圖識別是否存在買方受限組（S）若沒有，則偏好賣家圖中存在完美匹配，結(jié)束。否則，將受限組對應(yīng)的賣方集合N(S)中的價格都＋1，

若因此使所有賣方價格都>0，則統(tǒng)一約減最低價至0。開始下一輪為什么不會來回“震蕩”，始終得不到存在完美匹配的偏好賣家圖？算法過程一定能結(jié)束：證明定義市場的勢能：所有參與者潛在回報(bào)之和賣方：當(dāng)前價格，a1,a2,…,ak；買方(i)：“估值減去對應(yīng)價格”的最大值，max(vij-aj)勢能初值（a=0）：我們?nèi)绻苷f明在上述算法過程中，（1）勢能每一輪單調(diào)減，（2）但總不會小于0；則就說明了過程一定結(jié)束。“結(jié)束”＝“無受限集”。偏好賣家圖中邊對應(yīng)的差價這個過程為什么一定結(jié)束？（續(xù)）設(shè)買賣雙方各有K人，觀察勢能在每一輪的變化，可見只有價格a的變化會引起勢能的變化。在操作過程中有兩處可能會引起a的變化（1）必定發(fā)生：因受限集S造成的N(S)中元素價格＋1（2）不一定發(fā)生：統(tǒng)一約減a至最小價格為0可見賣方勢能之和，由于（1）增加N(S)，由于（2）減少K但總保持是≥0買方勢能之和，由于（1）減少S>N(S)

，由于（2）增加K結(jié)果也總是≥0（因?yàn)関≥0，且算法過程保證了總存在一個a=0）于是市場勢能在每輪都單調(diào)遞減，且下界為0。清倉價格的不唯一性但都是“社會最優(yōu)”（12＋6＋5＝23）上述有沒有矛盾？我們說，達(dá)到“市場清倉”就意味著“社會最優(yōu)”社會最優(yōu)即社會福利最大化，社會福利定義為所有參與人回報(bào)之和（包括買賣雙方），也等價于無沖突的買方估值之和在論證中又說勢能單調(diào)減勢能定義為所有參與人潛在回報(bào)之和

潛在回報(bào)不等于可達(dá)回報(bào)小結(jié)市場經(jīng)濟(jì)概念下，價格取決于供需關(guān)系，供需關(guān)系則依賴于買方對價值的