姜啟源等編《數(shù)學(xué)模型》第四版 課件 第十一章博弈模型

1、第十一章第十一章 博弈模型博弈模型11.1 進(jìn)攻與撤退的抉擇進(jìn)攻與撤退的抉擇11.2 讓報(bào)童訂購(gòu)更多的報(bào)紙讓報(bào)童訂購(gòu)更多的報(bào)紙11.3 “一口價(jià)一口價(jià)”的戰(zhàn)略的戰(zhàn)略 11.4 不患寡而患不均不患寡而患不均 11.5 效益的合理分配效益的合理分配 11.6 加權(quán)投票中權(quán)力的度量加權(quán)投票中權(quán)力的度量 單一決策主體單一決策主體決策變量決策變量目標(biāo)函數(shù)目標(biāo)函數(shù)約束條件約束條件決策主體的決策決策主體的決策行為發(fā)生直接相行為發(fā)生直接相互作用互作用 (相互影響相互影響)博弈模型博弈模型非合作博弈非合作博弈合作博弈合作博弈三要素三要素博弈模型博弈模型(Game Theory)多個(gè)決策主體多個(gè)決策主體優(yōu)化模型優(yōu)

2、化模型(Optimization)決策問(wèn)題（Decision Problem）靜態(tài)、動(dòng)態(tài)靜態(tài)、動(dòng)態(tài)信息完全、不完全信息完全、不完全軍事、政治、經(jīng)濟(jì)、企業(yè)管理和社會(huì)科學(xué)中應(yīng)用廣泛軍事、政治、經(jīng)濟(jì)、企業(yè)管理和社會(huì)科學(xué)中應(yīng)用廣泛 1944年年6月初，盟軍在諾曼底登陸成功月初，盟軍在諾曼底登陸成功. 到到8月初的形勢(shì)：月初的形勢(shì)： 背背景景11.1 進(jìn)攻與撤退的抉擇進(jìn)攻與撤退的抉擇雙方應(yīng)該如何決策雙方應(yīng)該如何決策 ？強(qiáng) 化強(qiáng) 化缺口缺口盟軍盟軍(預(yù)備隊(duì)預(yù)備隊(duì))撤退撤退進(jìn)攻進(jìn)攻德軍德軍盟軍盟軍(加加)盟軍盟軍(英英)盟軍盟軍(美一美一)盟 軍盟 軍(美三美三)東進(jìn)東進(jìn)原地原地待命待命模型假設(shè)模型假設(shè) 博

3、弈參與者為兩方（盟軍和德軍）博弈參與者為兩方（盟軍和德軍） 盟軍有盟軍有3種使用其預(yù)備隊(duì)的行動(dòng)：強(qiáng)化缺口，原地種使用其預(yù)備隊(duì)的行動(dòng)：強(qiáng)化缺口，原地待命，東進(jìn)；德軍有待命，東進(jìn)；德軍有2種行動(dòng)：向西進(jìn)攻或向東撤退種行動(dòng)：向西進(jìn)攻或向東撤退. 博弈雙方博弈雙方完全理性完全理性，目的都是使戰(zhàn)斗中己方獲得，目的都是使戰(zhàn)斗中己方獲得的凈勝場(chǎng)次（勝利場(chǎng)次減去失敗場(chǎng)次）盡可能多的凈勝場(chǎng)次（勝利場(chǎng)次減去失敗場(chǎng)次）盡可能多. 盟軍勝盟軍勝1場(chǎng)場(chǎng)盟軍敗盟軍敗2場(chǎng)場(chǎng)東進(jìn)東進(jìn)無(wú)戰(zhàn)斗無(wú)戰(zhàn)斗盟軍勝盟軍勝2場(chǎng)場(chǎng)原地待命原地待命無(wú)戰(zhàn)斗無(wú)戰(zhàn)斗盟軍勝盟軍勝1場(chǎng)場(chǎng)強(qiáng)化缺口強(qiáng)化缺口向東撤退向東撤退向西進(jìn)攻向西進(jìn)攻盟軍盟軍德軍德軍完全

4、信息完全信息靜態(tài)博弈靜態(tài)博弈 共同知識(shí)共同知識(shí)(以上信息雙方共有以上信息雙方共有) 雙方同時(shí)做出決策雙方同時(shí)做出決策博弈模型博弈模型 博弈參與者集合博弈參與者集合N=1,2(1為盟軍，為盟軍，2為德軍為德軍) 用用u1(a1，a2)表示對(duì)盟軍產(chǎn)生的結(jié)果，即凈勝場(chǎng)次，表示對(duì)盟軍產(chǎn)生的結(jié)果，即凈勝場(chǎng)次，稱(chēng)為盟軍的稱(chēng)為盟軍的效用函數(shù)效用函數(shù). 盟軍勝盟軍勝1場(chǎng)場(chǎng)盟軍敗盟軍敗2場(chǎng)場(chǎng)東進(jìn)東進(jìn)無(wú)戰(zhàn)斗無(wú)戰(zhàn)斗盟軍勝盟軍勝2場(chǎng)場(chǎng)原地待命原地待命無(wú)戰(zhàn)斗無(wú)戰(zhàn)斗盟軍勝盟軍勝1場(chǎng)場(chǎng)強(qiáng)化缺口強(qiáng)化缺口向東撤退向東撤退向西進(jìn)攻向西進(jìn)攻盟軍盟軍德軍德軍12020123ijmM 盟軍行動(dòng)盟軍行動(dòng)a1 A1=1,2,3(強(qiáng)化缺口強(qiáng)

5、化缺口/原地待命原地待命/東進(jìn)東進(jìn))； 德軍行動(dòng)德軍行動(dòng)a2 A2=1,2(進(jìn)攻進(jìn)攻/撤退撤退)。 (行動(dòng)：即純戰(zhàn)略行動(dòng)：即純戰(zhàn)略)支付矩陣支付矩陣（Payoff Matrix） 完全競(jìng)爭(zhēng)完全競(jìng)爭(zhēng): 零和博弈零和博弈 (常數(shù)和博弈常數(shù)和博弈) u2(a1，a2)對(duì)應(yīng)對(duì)應(yīng) -M博弈的解的概念：博弈的解的概念：納什均衡納什均衡 (NE: Nash Equilibrium)不存在不存在(純純)NE.2 , 1),(),(,3 , 2 , 1),(),(22*12*2*121*211*2*11aaauaauaaauaau(純戰(zhàn)略純戰(zhàn)略)納什均衡納什均衡Nash: 1994年獲諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)年獲諾貝爾經(jīng)

6、濟(jì)學(xué)獎(jiǎng)NE: 單向改變戰(zhàn)略不能提高自己效用，單向改變戰(zhàn)略不能提高自己效用，即每一方的戰(zhàn)略即每一方的戰(zhàn)略對(duì)于他方的戰(zhàn)略而言都是最優(yōu)的對(duì)于他方的戰(zhàn)略而言都是最優(yōu)的,稱(chēng)為稱(chēng)為最優(yōu)反應(yīng)最優(yōu)反應(yīng). 12020123ijmM(純純)NE: a*=(a1*, a2*) =(2, 2) 1, 12 , 21 , 22, 21 , 11, 1M非常數(shù)和非常數(shù)和博弈博弈(雙矩雙矩陣表示陣表示)混合戰(zhàn)略（策略：混合戰(zhàn)略（策略：Strategy) 盟軍的盟軍的混合戰(zhàn)略混合戰(zhàn)略集集 期望收益期望收益盟軍盟軍德軍德軍 S1=p=(p1, p2, p3) | 311, 10iiipp德軍的德軍的混合戰(zhàn)略混合戰(zhàn)略集集 S2=

7、 q=(q1, q2) | 211, 10iiiqqTSppMq1maxTSqpMq2min完全信息靜態(tài)博弈完全信息靜態(tài)博弈有限博弈矩陣博弈有限博弈矩陣博弈 (2人人)零和博弈零和博弈常數(shù)和博弈常數(shù)和博弈 ),(),(),(1231211qpUqpUqmppMqqpUijjijiT模型求解模型求解理性推理：理性推理：不管自己怎么做，另一方總是希望盡量不管自己怎么做，另一方總是希望盡量使自己得分盡量低使自己得分盡量低.（二人零和博弈，完全競(jìng)爭(zhēng)）（二人零和博弈，完全競(jìng)爭(zhēng)） 盟軍盟軍德軍德軍TSppMq1maxTSqpMq2min線性線性規(guī)劃規(guī)劃 從一個(gè)給定的戰(zhàn)略中期望得到的贏得，總是從一個(gè)給定的戰(zhàn)

8、略中期望得到的贏得，總是采用該策略時(shí)他們可能得到的最壞的贏得！采用該策略時(shí)他們可能得到的最壞的贏得！ 盟軍可以用盟軍可以用min pM來(lái)衡量策略來(lái)衡量策略p的好壞的好壞 max U1(p) = min pM min U2(q) = max MqT 德軍可以用德軍可以用max MqT來(lái)衡量策略來(lái)衡量策略q的好壞的好壞 (p*, q*): 混合混合(策略策略)納什均衡納什均衡(Mixed NE) p2*=3/5，p3*=2/5q1*=1/5，q2*=4/5最優(yōu)值均為最優(yōu)值均為2/5占優(yōu)占優(yōu)(dominate)：盟軍的行動(dòng)：盟軍的行動(dòng)2占優(yōu)于占優(yōu)于1 （前面的非常數(shù)和博弈（前面的非常數(shù)和博弈M類(lèi)似）

9、類(lèi)似）混合策略似乎不太可行混合策略似乎不太可行! 但但概率概率可作為可作為參考參考. -現(xiàn)實(shí)現(xiàn)實(shí)：盟軍讓預(yù)備隊(duì)原地待命（行動(dòng)：盟軍讓預(yù)備隊(duì)原地待命（行動(dòng)2），而德軍），而德軍沒(méi)有選擇撤退（行動(dòng)沒(méi)有選擇撤退（行動(dòng)2），結(jié)果德軍大?。?，結(jié)果德軍大敗. 模型評(píng)述模型評(píng)述 博弈規(guī)則博弈規(guī)則至關(guān)重要的，如參與人決策的時(shí)間順序、至關(guān)重要的，如參與人決策的時(shí)間順序、決策時(shí)擁有哪些信息等決策時(shí)擁有哪些信息等. 110100M多人多人(或非常數(shù)和或非常數(shù)和)博弈問(wèn)題，一般不能用上面的線性博弈問(wèn)題，一般不能用上面的線性規(guī)劃方法求解，而通過(guò)納什均衡的定義求解規(guī)劃方法求解，而通過(guò)納什均衡的定義求解. 小結(jié)：博弈模型的

10、基本要素小結(jié)：博弈模型的基本要素 參與人參與人 理性假設(shè)理性假設(shè) 行動(dòng)順序（靜態(tài)、動(dòng)態(tài)）行動(dòng)順序（靜態(tài)、動(dòng)態(tài)） 信息結(jié)構(gòu)（完全、不完全）信息結(jié)構(gòu)（完全、不完全） 行動(dòng)空間（及戰(zhàn)略空間）行動(dòng)空間（及戰(zhàn)略空間） 效用函數(shù)效用函數(shù) 參與者完全理性參與者完全理性(最大化效用最大化效用)其他因素其他因素納什均衡納什均衡單向改變戰(zhàn)略不能提高自己效用單向改變戰(zhàn)略不能提高自己效用11.2 讓報(bào)童訂購(gòu)更多的報(bào)紙讓報(bào)童訂購(gòu)更多的報(bào)紙 報(bào)報(bào)童童模模型型回回顧顧訂購(gòu)價(jià)訂購(gòu)價(jià)w，零售價(jià)，零售價(jià)p，處理價(jià)，處理價(jià)v（pwv0）需求量：密度函數(shù)需求量：密度函數(shù)f(x)、分布函數(shù)、分布函數(shù)F(x), F(0)=0訂購(gòu)訂購(gòu)Q份

11、報(bào)紙，期望銷(xiāo)售量為份報(bào)紙，期望銷(xiāo)售量為 QQQQQdxxFQQFQdxxFxxFdxxQfdxxxfQS0000)()(1 ()(| )()()()(期望存貨量期望存貨量QdxxFQSQQI0)()()(期望利潤(rùn)期望利潤(rùn) QvwQSvpwQQvIQpSQG)()()()()()(最優(yōu)訂購(gòu)量最優(yōu)訂購(gòu)量Qr vpwpQFr)(Qr(w) 11.2 讓報(bào)童訂購(gòu)更多的報(bào)紙讓報(bào)童訂購(gòu)更多的報(bào)紙 問(wèn)問(wèn)題題假設(shè)報(bào)社報(bào)紙成本價(jià)為假設(shè)報(bào)社報(bào)紙成本價(jià)為c，wcv )()( MaxwQcwrcwvpwpFcw1)( w*完全信息動(dòng)態(tài)博弈：常稱(chēng)完全信息動(dòng)態(tài)博弈：常稱(chēng)Stackelberg Game (兩階段兩階段)

12、子博弈完美均衡子博弈完美均衡: (w*，Qr(w)vpcpQF)(*一般一般w*c Qr(w*) wbv)bpwpvpcp)()(bpvpvcbbwwb)()()()()()()()()()()(*bUbUvpvbbUbUbUvpbpbUQvcQSvpbUbUsrssrrsr回收協(xié)議模型回收協(xié)議模型 模型二模型二 回收數(shù)量協(xié)議回收數(shù)量協(xié)議 報(bào)社回收?qǐng)?bào)社回收 達(dá)到協(xié)調(diào)達(dá)到協(xié)調(diào)報(bào)童回收?qǐng)?bào)童回收，報(bào)童利潤(rùn)，報(bào)童利潤(rùn), 報(bào)社利潤(rùn)報(bào)社利潤(rùn); 利潤(rùn)任意分配都可達(dá)到利潤(rùn)任意分配都可達(dá)到 按批發(fā)價(jià)回收，比例為按批發(fā)價(jià)回收，比例為 QQQQQdxxFdxxfxQdxxQfQI)1 ()1 ()1 (01)()(

13、)()()(QdxxFQIQIQI)1(012)()()()(報(bào)童利潤(rùn)報(bào)童利潤(rùn)QQQrdxxFvpdxxFQwpwQQvIQwIQpSQwU)1(0)1(21)()()()()()()(),(0),(rQrQQwU0)1()1)()(1)(rrQFvwQFwpvpcpQF)(*)1()1)()/()(1)(*QFvwvpcpwp)1()1)()()()(*QFvpvcvcvpvwwq回收協(xié)議模型回收協(xié)議模型 模型評(píng)述模型評(píng)述 協(xié)議參數(shù)的確定：協(xié)議參數(shù)的確定：不能單方?jīng)Q定不能單方?jīng)Q定雙方談判（合作博弈）雙方談判（合作博弈） 還有很多其他類(lèi)型的協(xié)議，也可以達(dá)到協(xié)調(diào)還有很多其他類(lèi)型的協(xié)議，也可以達(dá)到

14、協(xié)調(diào)一種更簡(jiǎn)單的協(xié)議一種更簡(jiǎn)單的協(xié)議批發(fā)價(jià)批發(fā)價(jià)w成本成本c收取一定加盟費(fèi)收取一定加盟費(fèi)如何評(píng)價(jià)比較協(xié)議的優(yōu)缺點(diǎn)？如何評(píng)價(jià)比較協(xié)議的優(yōu)缺點(diǎn)？是否能達(dá)到協(xié)調(diào)是否能達(dá)到協(xié)調(diào)是否能任意分配利潤(rùn)是否能任意分配利潤(rùn)協(xié)議執(zhí)行成本有多高協(xié)議執(zhí)行成本有多高11.3 “一口價(jià)一口價(jià)”的戰(zhàn)略的戰(zhàn)略 背景背景 為了節(jié)省為了節(jié)省“討價(jià)還價(jià)討價(jià)還價(jià)”時(shí)間，考慮時(shí)間，考慮“一口價(jià)一口價(jià)”模式模式. 雙方同時(shí)報(bào)價(jià)雙方同時(shí)報(bào)價(jià)：若買(mǎi)價(jià)：若買(mǎi)價(jià)賣(mài)價(jià)，則以均價(jià)成交賣(mài)價(jià)，則以均價(jià)成交; 否則不成交否則不成交.問(wèn)題問(wèn)題 雙方應(yīng)如何報(bào)價(jià)？雙方應(yīng)如何報(bào)價(jià)？ 雙方總能成交嗎？（效率估計(jì)）雙方總能成交嗎？（效率估計(jì)） “討價(jià)還價(jià)討價(jià)還價(jià)”很

15、浪費(fèi)買(mǎi)賣(mài)雙方的寶貴時(shí)間很浪費(fèi)買(mǎi)賣(mài)雙方的寶貴時(shí)間.模型假設(shè)與建立模型假設(shè)與建立 賣(mài)方知道物品對(duì)自己的價(jià)值，但買(mǎi)方不知道賣(mài)方知道物品對(duì)自己的價(jià)值，但買(mǎi)方不知道. 買(mǎi)方知道物品對(duì)自己的價(jià)值，但賣(mài)方不知道買(mǎi)方知道物品對(duì)自己的價(jià)值，但賣(mài)方不知道. 雙方都知道（如猜出）對(duì)方價(jià)值的分布信息雙方都知道（如猜出）對(duì)方價(jià)值的分布信息.賣(mài)方價(jià)值賣(mài)方價(jià)值vs, 買(mǎi)方價(jià)值買(mǎi)方價(jià)值vb, 均服從均服從U0,1 (均勻分布均勻分布) 賣(mài)方報(bào)價(jià)賣(mài)方報(bào)價(jià)ps, 買(mǎi)方報(bào)價(jià)買(mǎi)方報(bào)價(jià)pb, pb ps時(shí)成交價(jià)時(shí)成交價(jià)p (pb+ps)/2成交效用：賣(mài)方成交效用：賣(mài)方U1=p- vs, 買(mǎi)方買(mǎi)方U2= vb p; 不成交不成交: 0雙

16、方完全理性雙方完全理性(最大化自己的期望效用最大化自己的期望效用 ).以上為雙方的共同知識(shí)以上為雙方的共同知識(shí).賣(mài)方報(bào)價(jià)賣(mài)方報(bào)價(jià)ps ps(vs)買(mǎi)方報(bào)價(jià)買(mǎi)方報(bào)價(jià)pb pb(vb)雙方戰(zhàn)略雙方戰(zhàn)略戰(zhàn)略組合戰(zhàn)略組合( ps(vs), pb(vb) 何時(shí)構(gòu)成均衡？何時(shí)構(gòu)成均衡？定義在定義在0，1區(qū)間上、取值也區(qū)間上、取值也在在0，1區(qū)間上的非減函數(shù)區(qū)間上的非減函數(shù). 不完全信息靜態(tài)博弈（靜態(tài)貝葉斯博弈）不完全信息靜態(tài)博弈（靜態(tài)貝葉斯博弈）貝葉斯納什均衡貝葉斯納什均衡單向改變戰(zhàn)略不能單向改變戰(zhàn)略不能提高自己效用提高自己效用.信息非對(duì)稱(chēng)（不完全信息）信息非對(duì)稱(chēng)（不完全信息）模型假設(shè)與建立模型假設(shè)與建立

17、均衡條件均衡條件具體戰(zhàn)略具體戰(zhàn)略(函數(shù)函數(shù))形式不同，均衡就可能不同形式不同，均衡就可能不同.單一價(jià)格戰(zhàn)略單一價(jià)格戰(zhàn)略賣(mài)方：賣(mài)方：買(mǎi)方：買(mǎi)方：雙方戰(zhàn)略互為最優(yōu)反應(yīng)，所以構(gòu)成雙方戰(zhàn)略互為最優(yōu)反應(yīng)，所以構(gòu)成貝葉斯納什均衡貝葉斯納什均衡！)(Pr*2)(| )(maxsbbssbbbbsppvpvpvpvpEps)(Pr*2)(| )(maxssbssbssbbpvppvppvpEpvbxvxvxvpssss, 1,)(xvxvxvpbbbb, 0,)(模型假設(shè)與建立模型假設(shè)與建立單一價(jià)格戰(zhàn)略效率為單一價(jià)格戰(zhàn)略效率為x(1-x)/0.50.5x0.5效率最大效率最大(1/2)對(duì)給定的對(duì)給定的(vs,

18、 vb)，當(dāng)，當(dāng)vsxj=1-xi時(shí)，時(shí)，i(x)xi-i (xi -xj)= i -(2i -1)xi關(guān)于關(guān)于xi的系數(shù)非正的系數(shù)非正 （過(guò)分（過(guò)分“愧疚愧疚” ）效用函數(shù)效用函數(shù)財(cái)富總額為財(cái)富總額為1接受提議：甲乙所得接受提議：甲乙所得x1=1-s, x2= s；否則：；否則：x1=x2=0 ijixxxxxxxUjiiijiii3, 2 , 10 ,max0 ,max),(210ii2/1i模型求解模型求解如果不接受，則如果不接受，則x1=x2=0; U1(s)=U2(s)=0 . 若若s1/2,則則x2 x1乙的最優(yōu)反應(yīng)乙的最優(yōu)反應(yīng)乙的最優(yōu)反應(yīng)（給定乙的最優(yōu)反應(yīng)（給定s）如果接受，則如

19、果接受，則x1=1-s, x2=s. 若若s1/2,則則x2x1U2(s)00 ,max0 ,max),(21jiiijiiixxxxxxxU1/20 ) 12()(22sssU2222)21 ()21 ()(ssssU s )21/()(222s當(dāng)當(dāng) s 接受接受; 否則，不接受否則，不接受)(2s2/1)(02s易知易知 (s1/2, 兩者一致兩者一致) 2/12模型求解模型求解Case 1: 甲知道乙的甲知道乙的2 若若s1/2,則則x2 x1甲的決策甲的決策s=1/2時(shí)達(dá)到最大值時(shí)達(dá)到最大值1/2甲的決策甲的決策(只需考慮乙接受情形只需考慮乙接受情形) 12(1)(11sssU 若若s

20、1/2,則則x2 x1但但 s )(2sssssU) 12(1)21 (1)(1111)21/()(222* ss2/11均衡均衡: (s*,接受接受)s*嚴(yán)格小于嚴(yán)格小于50%; 是乙的是乙的“憤怒憤怒”系數(shù)系數(shù)2的增函數(shù)的增函數(shù). 模型求解：甲的決策模型求解：甲的決策Case 2: 甲不知道乙的甲不知道乙的2, 但知道但知道2知道分布知道分布F(2) 若若s1/2,則則x2 x1甲的決策甲的決策 若若s1/2,則則x2 x1U1(s)=1-s-1(2s-1) 同前同前期望效用期望效用乙接受概率乙接受概率s*1)(min0)(maxFF)(, 1)()(),21/()(, 0sssssssF

21、ssp)(,) 12(1)()(),21/() 12(1 )(, 0)(11111ssssssssFssssEU)21/() 12(1 11)()(ssFsMaxsss模型解釋模型解釋 甲永遠(yuǎn)不會(huì)提出大于甲永遠(yuǎn)不會(huì)提出大于/的方案的方案s 乙拒絕過(guò)小的方案乙拒絕過(guò)小的方案s很好地解釋了實(shí)際中的最后通牒博弈很好地解釋了實(shí)際中的最后通牒博弈 乙接受概率隨乙接受概率隨s增加不減增加不減參考文獻(xiàn)參考文獻(xiàn)11.5 效益的合理分配效益的合理分配11321xxx457323121xxxxxx例例甲乙丙三人合作經(jīng)商，若甲乙合作獲利甲乙丙三人合作經(jīng)商，若甲乙合作獲利7元，元，甲丙合作獲利甲丙合作獲利5元，乙丙合

22、作獲利元，乙丙合作獲利4元，元，三人合作獲利三人合作獲利11元元. 又知每人單干獲利又知每人單干獲利1元元.問(wèn)三人合作時(shí)如何分配獲利？問(wèn)三人合作時(shí)如何分配獲利？記甲乙丙三人分配為記甲乙丙三人分配為),(321xxxx 解不唯一解不唯一(5，3，3)(4，4，3)(5，4，2)1,321xxx)(1Ivxniiniivxi, 2 , 1),(2121210sssvsvssvv),()()()(,2, 1nI集合 (1) Shapley合作對(duì)策合作對(duì)策滿足實(shí)函數(shù)，子集)(svIs I,v n人合作對(duì)策，人合作對(duì)策，v特征函數(shù)特征函數(shù)),(21nxxxxn人從人從v(I)得到的分配，滿足得到的分配，

23、滿足v(s) 子集子集s的獲利的獲利!)!1()!()(nssnswniisvsvswxiSsi,),()()(21公理化方法公理化方法 s 子集子集 s中的元素?cái)?shù)目，中的元素?cái)?shù)目， Si 包含包含i的所有子集的所有子集)( sw由由 s 決定的決定的“貢獻(xiàn)貢獻(xiàn)”的權(quán)重的權(quán)重 Shapley值值)()(isvsv i 對(duì)合作對(duì)合作s 的的“貢獻(xiàn)貢獻(xiàn)”)(siShapley合作對(duì)策合作對(duì)策三人三人(I=1,2,3)經(jīng)商中甲的分配經(jīng)商中甲的分配x1的計(jì)算的計(jì)算 1/3 1/6 1/6 1/3)1()()(svsvsw)( sws)1()(svsv)1(sv)(sv1S1 1 2 1 3 I1 7

24、5 11 0 1 1 4 1 6 4 7 1/3 1 2/3 7/3x1=13/3類(lèi)似可得類(lèi)似可得 x2=23/6, x3=17/6)1()()(11svsvswxSs1 2 2 3合作對(duì)策的應(yīng)用合作對(duì)策的應(yīng)用 污水處理費(fèi)用的合理分擔(dān)污水處理費(fèi)用的合理分擔(dān)20km38km河流河流三城鎮(zhèn)地理位置示意圖三城鎮(zhèn)地理位置示意圖123 污水處理，排入河流污水處理，排入河流.三城鎮(zhèn)可單獨(dú)建處理廠，三城鎮(zhèn)可單獨(dú)建處理廠，或聯(lián)合建廠或聯(lián)合建廠(用管道將污水用管道將污水由上游城鎮(zhèn)送往下游城鎮(zhèn)由上游城鎮(zhèn)送往下游城鎮(zhèn)).Q1=5Q3=5Q2=3Q污水量，污水量，L管道長(zhǎng)度管道長(zhǎng)度建廠費(fèi)用建廠費(fèi)用P1=73Q0.71

25、2管道費(fèi)用管道費(fèi)用P2=0.66Q0.51L230)3(,160)2(,230573) 1 (712. 0CCC35020566. 0)35(73)2 , 1 (51. 0712. 0C36538366. 0)53(73)3 , 2(51. 0712. 0C46358566. 0)55(73) 3 , 1 (51. 0712. 0C460)3() 1 (CC污水處理的污水處理的5 種方案種方案1）單獨(dú)建廠）單獨(dú)建廠620)3()2() 1 (1CCCD總投資總投資2）1, 2合作合作3）2, 3合作合作4）1, 3合作合作580)3()2 , 1 (2CCD總總投資投資595) 3 , 2()

26、 1 (3CCD總投資總投資合作不會(huì)實(shí)現(xiàn)合作不會(huì)實(shí)現(xiàn)55638) 35(66. 020566. 0)535(73) 3 , 2 , 1 (51. 051. 0712. 05CD5）三城合）三城合作總投資作總投資D5最小最小, 應(yīng)聯(lián)合建廠應(yīng)聯(lián)合建廠 建廠費(fèi)：建廠費(fèi)：d1=73 (5+3+5)0.712=453 12 管道費(fèi)：管道費(fèi)：d2=0.66 50.51 20=30 23 管道費(fèi)：管道費(fèi)：d3=0.66 (5+3)0.51 38=73D5城城3建議：建議：d1 按按 5:3:5分擔(dān)分擔(dān), d2,d3由城由城1,2擔(dān)負(fù)擔(dān)負(fù)城城2建議：建議：d3由城由城1,2按按 5:3分擔(dān)分擔(dān), d2由城由城

27、1擔(dān)負(fù)擔(dān)負(fù)城城1計(jì)算：計(jì)算：城城3分擔(dān)分擔(dān) d1 5/13=174C(3), 城城2分擔(dān)分擔(dān) d1 3/13+d3 3/8 =132C(1)不同意不同意! !D5如何分擔(dān)？如何分擔(dān)？230) 3(160) 2(230) 1 (CCC0)3()2()1(,0)(vvvv3 ,2, 1I集合特征函數(shù)特征函數(shù)v(s)聯(lián)合聯(lián)合(集集s)建廠比單獨(dú)建廠節(jié)約的投資建廠比單獨(dú)建廠節(jié)約的投資),(321xxxx 三城從三城從節(jié)約投資節(jié)約投資v(I)中得到的分配中得到的分配40350160230)2 , 1 ()2() 1 ()21 (CCCv 64556230160230) 3 , 2 , 1 () 3 ()

28、 2() 1 ()(0) 31 (25365230160) 3 , 2() 3 () 2() 32(CCCCIvvCCCv Shapley合作對(duì)策合作對(duì)策計(jì)算計(jì)算城城1從從節(jié)約投資中得到的分配節(jié)約投資中得到的分配x1)1()()(svsvsw)(sws) 1()(svsv) 1(sv)(svs1 1 2 1 3 I 0 40 0 640 0 0 250 40 0 39 1 2 2 31/3 1/6 1/6 1/3 0 6.7 0 13 x1 =19.7,城城1 C(1)-x1=210.4, 城城2 C(2)-x2=127.8, 城城3 C(3)-x3=217.8三城在總投資三城在總投資556中

29、的分擔(dān)中的分擔(dān)x2 =32.1, x3=12.2x2最大，如何解釋?zhuān)孔畲?，如何解釋?zhuān)績(jī)?yōu)點(diǎn)：優(yōu)點(diǎn)：公正、合理，有公理化基礎(chǔ)。公正、合理，有公理化基礎(chǔ)。如如n個(gè)單位治理污染個(gè)單位治理污染, 通常知道第通常知道第i方單獨(dú)治理的投資方單獨(dú)治理的投資yi 和和n方共同治理的投資方共同治理的投資Y, 及第及第i方不參加時(shí)其余方不參加時(shí)其余n-1方的方的投資投資zi (i=1,2, ,n). 確定共同治理時(shí)各方分擔(dān)的費(fèi)用確定共同治理時(shí)各方分擔(dān)的費(fèi)用.iijjzyiIv)(其他其他v(s)均不知道均不知道, 無(wú)法用無(wú)法用Shapley合作對(duì)策合作對(duì)策求解求解Shapley合作對(duì)策小結(jié)合作對(duì)策小結(jié)若定義特征函數(shù)

30、為合作的獲利若定義特征函數(shù)為合作的獲利(節(jié)約的投資節(jié)約的投資)，則有，則有,)(),()(YyIvniivnii1210缺點(diǎn)：缺點(diǎn)：需要知道所有合作的獲利，即要定義需要知道所有合作的獲利，即要定義I=1,2,n的的所有子集所有子集(共共2n-1個(gè)個(gè))的特征函數(shù)，實(shí)際上常做不到的特征函數(shù)，實(shí)際上常做不到.),(nbbb1記設(shè)只知道設(shè)只知道)(iIvbi無(wú)無(wú) i 參加時(shí)參加時(shí)n-1方合作的獲利方合作的獲利)(IvB及全體合作的獲利全體合作的獲利021inxxxxxB),(的分配求各方對(duì)獲利),(),7 , 5 , 4(11321xxxxbB求，即已知求解合作對(duì)策的其他方法求解合作對(duì)策的其他方法例例

31、. 甲乙丙三人合作經(jīng)商，若甲乙合作獲利甲乙丙三人合作經(jīng)商，若甲乙合作獲利7元，元，甲丙合作獲利甲丙合作獲利5元，乙丙合作獲利元，乙丙合作獲利4元，三人元，三人合作獲利合作獲利11元元. 問(wèn)三人合作時(shí)如何分配獲利？問(wèn)三人合作時(shí)如何分配獲利？（1）協(xié)商解）協(xié)商解00,AbAxTT11nniiibxxbxxBx11將剩余獲利將剩余獲利 平均分配平均分配 ixBnBbbnxBnxxiiiii1)(111),7 , 5 , 4(.Bb例模型模型以以n-1方合作的獲利為下限方合作的獲利為下限TTbxA求解求解iiibbnx11 xi 的下限的下限, 3),1 , 3 , 4(ixBx) 2 , 4 , 5

32、() 1 , 1 , 1 ( xx（2）Nash解解 ),(1nddd記為現(xiàn)狀點(diǎn)（談判時(shí)的威懾點(diǎn)）為現(xiàn)狀點(diǎn)（談判時(shí)的威懾點(diǎn)）iiiiiidxBxtsdxxma. .)(iixd 在此基礎(chǔ)上在此基礎(chǔ)上“均勻地均勻地”分配全體合作的獲利分配全體合作的獲利B模型模型0id)(1iiidBndx平均分配獲利平均分配獲利B2）Nash解解 1）協(xié)商解）協(xié)商解（3）最小距離解）最小距離解的上限為記xxxxn),(1iiiiiixxBxtsxxnmi. .)(2模型模型 第第i 方的邊際效益方的邊際效益iibBx若令若令nBbbnxiii111),7 , 5 , 4(.Bb例)(1Bxnxxiii3）最小距

33、離解）最小距離解 1）協(xié)商解）協(xié)商解, 6),4 , 6 , 7(Bxxi) 2 , 4 , 5 () 2 , 2 , 2 (xx（4）滿意解）滿意解iiiiidedxu滿意度Bxtsunmixmaiii.)(di現(xiàn)狀點(diǎn)現(xiàn)狀點(diǎn)(最低點(diǎn)最低點(diǎn))ei理想點(diǎn)理想點(diǎn)(最高點(diǎn)最高點(diǎn))模型模型iiiixexd,4）基于滿意度的解）基于滿意度的解 1）協(xié)商解）協(xié)商解iiixed , 0)(*iiiiiiideudxdedBu的比例分配中在按iiiiixxBxxx（5）Raiffi 解解jjxbBnjj獲利為方合作時(shí)的原來(lái)無(wú)參與當(dāng),1)(jininxxxxxjiijj, 1,) 1(2,2:)1的分配基礎(chǔ)上進(jìn)

34、行方合作獲利的分配（在Bnx方再等分方平分，和先由11nnjxj得到再平均取,nj21ijjiiixnxnxnnx) 1(21211) 4 , 6 , 7 (),1 , 3 , 4(xx與協(xié)商解與協(xié)商解x=(5,4,2)比較比較11),7 , 5 , 4(.Bb例)1252,12113,324（x求解合作對(duì)策的求解合作對(duì)策的6種方法（可分為三類(lèi)）種方法（可分為三類(lèi)）Shapley合作對(duì)策合作對(duì)策A類(lèi)類(lèi)B類(lèi)類(lèi)!)!1()!()(nssnswniisvsvswxiSsi, 2 , 1),()()()(),(IvBiIvbi只需Issv),(需要所有協(xié)商解協(xié)商解)(1iiixBnxx下限ixNash

35、解解 )(1iiidBndx現(xiàn)狀id最小距離解最小距離解)(1Bxnxxiii上限ix滿意解滿意解)(iiiiiiiiideudxdedBudi現(xiàn)狀現(xiàn)狀, ei理想理想iiiixexd,iibBx,1bAxB類(lèi)類(lèi)4種方法相同種方法相同例：有一資方例：有一資方(甲甲)和二勞方和二勞方(乙乙,丙丙), 僅當(dāng)資方與至少僅當(dāng)資方與至少一勞方合作時(shí)才獲利一勞方合作時(shí)才獲利10元，應(yīng)如何分配該獲利？元，應(yīng)如何分配該獲利？Raiffi解解C類(lèi)類(lèi))(),(IvBiIvbi只需方再等分方平分，和先由上限對(duì)每個(gè)11,nnjxjj10)(),10,10, 0(),(.IvBbiIvbBi)67. 1 ,67. 1

36、,67. 6().(xShapleyA)0 , 0 ,10(,xbBxii)0 , 0 ,10(1TTbAx)83. 0 ,83. 0 ,34. 8(xijjiiixnxnxnnxRaiffiC) 1(21211).()0 ,0 ,10(xB類(lèi)：類(lèi)：計(jì)算簡(jiǎn)單，便于理解，可用于各方實(shí)計(jì)算簡(jiǎn)單，便于理解，可用于各方實(shí)力相差不大的情況；一般來(lái)說(shuō)它偏袒強(qiáng)者力相差不大的情況；一般來(lái)說(shuō)它偏袒強(qiáng)者. C類(lèi)：類(lèi)： 考慮了分配的上下限，又吸取了考慮了分配的上下限，又吸取了Shapley的思想，在一定程度上保護(hù)弱者的思想，在一定程度上保護(hù)弱者.A類(lèi)：類(lèi)：公正合理；需要信息多，計(jì)算復(fù)雜公正合理；需要信息多，計(jì)算復(fù)雜

37、.求解合作對(duì)策的三類(lèi)方法小結(jié)求解合作對(duì)策的三類(lèi)方法小結(jié)11.6 加權(quán)投票中權(quán)力的度量加權(quán)投票中權(quán)力的度量 背景背景“一人一票一人一票”顯示投票和表決的公正顯示投票和表決的公正. 股份制公司每位股東投票和表決權(quán)的大小由所股份制公司每位股東投票和表決權(quán)的大小由所占有的占有的股份股份多少?zèng)Q定多少?zèng)Q定. 一些國(guó)家、地區(qū)的議會(huì)、政府的產(chǎn)生，由所屬的一些國(guó)家、地區(qū)的議會(huì)、政府的產(chǎn)生，由所屬的州、縣等各個(gè)區(qū)域推出的代表投票決定州、縣等各個(gè)區(qū)域推出的代表投票決定. 代表投票的權(quán)重取決于所代表區(qū)域的代表投票的權(quán)重取決于所代表區(qū)域的人口人口數(shù)量數(shù)量. 經(jīng)濟(jì)或政治機(jī)構(gòu)權(quán)力的分配經(jīng)濟(jì)或政治機(jī)構(gòu)權(quán)力的分配 背景背景典型

38、案例典型案例: : 美國(guó)總統(tǒng)選舉實(shí)行的選舉人制度美國(guó)總統(tǒng)選舉實(shí)行的選舉人制度 美全國(guó)美全國(guó)50個(gè)州和華盛頓特區(qū)共個(gè)州和華盛頓特區(qū)共538張張選舉人票選舉人票. 獲選舉人票數(shù)獲選舉人票數(shù)一半以上一半以上的總統(tǒng)候選人當(dāng)選總統(tǒng)的總統(tǒng)候選人當(dāng)選總統(tǒng). 各州各州選舉人票數(shù)選舉人票數(shù)與該州在國(guó)會(huì)的參、眾議員數(shù)相等與該州在國(guó)會(huì)的參、眾議員數(shù)相等. 參議員每州兩位，眾議員人數(shù)由各州參議員每州兩位，眾議員人數(shù)由各州人口比例人口比例確定確定. 各州人口懸殊巨大使各州人口懸殊巨大使各州選舉人票數(shù)相差很大各州選舉人票數(shù)相差很大. (如加利福尼亞州選舉人票如加利福尼亞州選舉人票55張，阿拉斯加州只張，阿拉斯加州只3張張

39、) 背景背景典型案例典型案例: : 美國(guó)總統(tǒng)選舉實(shí)行的選舉人制度美國(guó)總統(tǒng)選舉實(shí)行的選舉人制度 總統(tǒng)候選人在各州內(nèi)進(jìn)行普選，獲得總統(tǒng)候選人在各州內(nèi)進(jìn)行普選，獲得相對(duì)多數(shù)相對(duì)多數(shù)選票的候選人得到該州的選票的候選人得到該州的全部選舉人票全部選舉人票. 48個(gè)州和華盛頓特區(qū)都實(shí)行個(gè)州和華盛頓特區(qū)都實(shí)行“勝者全勝者全得得” ：在加利福尼亞州以在加利福尼亞州以微弱多數(shù)微弱多數(shù)普選獲勝的普選獲勝的總統(tǒng)候選人可得到總統(tǒng)候選人可得到全部全部55張張選舉人票選舉人票. 若有幾個(gè)人口多的州如此，在選舉人投票中就若有幾個(gè)人口多的州如此，在選舉人投票中就可能使各州可能使各州累計(jì)得票最多的候選人累計(jì)得票最多的候選人反而不

40、能獲勝反而不能獲勝.選舉結(jié)果違反選舉結(jié)果違反全國(guó)多數(shù)人全國(guó)多數(shù)人的意愿的意愿. 2000年年布什布什與與戈?duì)柛隊(duì)栠M(jìn)行的競(jìng)選中，戈?duì)栕罱K敗給布什！進(jìn)行的競(jìng)選中，戈?duì)栕罱K敗給布什！ 問(wèn)題問(wèn)題由若干區(qū)域由若干區(qū)域(如省、縣等如省、縣等)組成的機(jī)構(gòu)中，每區(qū)組成的機(jī)構(gòu)中，每區(qū)代表的數(shù)量按照人口比例分配，進(jìn)行投票選舉代表的數(shù)量按照人口比例分配，進(jìn)行投票選舉和表決時(shí)，每區(qū)的全體代表投相同的票和表決時(shí)，每區(qū)的全體代表投相同的票. 每區(qū)各派一位代表每區(qū)各派一位代表(投票人投票人)，按照他們所代表，按照他們所代表的各區(qū)人口比例賦予投票的權(quán)重的各區(qū)人口比例賦予投票的權(quán)重.如何度量每位代表的投票對(duì)最終結(jié)果的影響力如何

41、度量每位代表的投票對(duì)最終結(jié)果的影響力(權(quán)力權(quán)力). 介紹兩種合理的、度量權(quán)力的數(shù)量指標(biāo)介紹兩種合理的、度量權(quán)力的數(shù)量指標(biāo). 通過(guò)實(shí)例給出它們的應(yīng)用通過(guò)實(shí)例給出它們的應(yīng)用. 調(diào)整投票人的權(quán)重使其權(quán)力大致與代表的人口成比例調(diào)整投票人的權(quán)重使其權(quán)力大致與代表的人口成比例. 加權(quán)投票中權(quán)力的度量加權(quán)投票中權(quán)力的度量背背景景加權(quán)投票與獲勝聯(lián)盟加權(quán)投票與獲勝聯(lián)盟 例例1 一縣一縣5區(qū)區(qū)(A, B, C, D, E )人口為人口為 60, 20, 10, 5, 5 (千人千人). 每區(qū)一位代表按人口比例分配其投票權(quán)重為每區(qū)一位代表按人口比例分配其投票權(quán)重為12, 4, 2, 1, 1. 按按簡(jiǎn)單多數(shù)規(guī)則簡(jiǎn)單

42、多數(shù)規(guī)則(權(quán)重之和超過(guò)總權(quán)重一半權(quán)重之和超過(guò)總權(quán)重一半)決定投票結(jié)果決定投票結(jié)果.將將A區(qū)分成人口相等的區(qū)分成人口相等的3個(gè)子區(qū)個(gè)子區(qū)A1，A2，A3 每區(qū)代表的投票權(quán)重為每區(qū)代表的投票權(quán)重為4，4，4，4，2，1，1 決定投票結(jié)果的區(qū)域集合決定投票結(jié)果的區(qū)域集合：A1，A2，A3 ，A1, A2, B, A1, A3, C, D, A1, B, C, E , A1, A3, B, D ， A區(qū)代表是區(qū)代表是獨(dú)裁者獨(dú)裁者(能決定投票結(jié)果能決定投票結(jié)果), 其他代表都是其他代表都是傀儡傀儡. 改改革革加權(quán)投票與獲勝聯(lián)盟加權(quán)投票與獲勝聯(lián)盟 加權(quán)投票系統(tǒng)加權(quán)投票系統(tǒng)投票人集合投票人集合N=A，B，C

43、, (n人人)權(quán)重權(quán)重w1, w2, ，wn 定額定額q 投贊成票的投票人權(quán)重之和投贊成票的投票人權(quán)重之和 q時(shí)決議通過(guò)時(shí)決議通過(guò). w=w1+ w2,+wn，一般，一般 w/2wj, 則則kikj.Shapley權(quán)力指標(biāo)權(quán)力指標(biāo) S(4)=3: 2, 1, 1 例例23位投票人的位投票人的全排列全排列: ABC, ACB, BAC, BCA, CAB, CBA 主任主任A,教授教授B,學(xué)生學(xué)生C的加權(quán)投票系統(tǒng)的加權(quán)投票系統(tǒng) ABC: 從從A增至增至AB時(shí)時(shí)AB變?yōu)楂@勝聯(lián)盟變?yōu)楂@勝聯(lián)盟ACB: 從從A增至增至AC時(shí)時(shí)AC變?yōu)楂@勝聯(lián)盟變?yōu)楂@勝聯(lián)盟BCA:從從BC增至增至BCA時(shí)時(shí)BCA變?yōu)楂@勝聯(lián)

44、盟變?yōu)楂@勝聯(lián)盟ABCACB BAC BCA CAB CBA BAC: 從從B增至增至BA時(shí)時(shí)BA變?yōu)楂@勝聯(lián)盟變?yōu)楂@勝聯(lián)盟A下有下有4條橫線，條橫線，B, C下各有下各有1條橫線條橫線 Shapley指標(biāo)（指標(biāo)（4，1，1） （4/6, 1/6, 1/6） 歸一化歸一化 Shapley權(quán)力指標(biāo)權(quán)力指標(biāo) 寫(xiě)出投票人的共寫(xiě)出投票人的共n!個(gè)全個(gè)全排列排列; 對(duì)每一個(gè)排列對(duì)每一個(gè)排列由左向右由左向右依次檢查，若某位投票人加入依次檢查，若某位投票人加入時(shí)該集合變成獲勝聯(lián)盟，稱(chēng)該投票人為時(shí)該集合變成獲勝聯(lián)盟，稱(chēng)該投票人為決定者決定者(Pivot); 將每位投票人在所有排列中的成為將每位投票人在所有排列中的

45、成為決定者的次數(shù)決定者的次數(shù)除除以以n!定義為他們的定義為他們的Shapley權(quán)力指標(biāo)權(quán)力指標(biāo). =/ n!, =(1, 2, ,n) n人加權(quán)投票系統(tǒng)人加權(quán)投票系統(tǒng)S(4)=3: 2, 1, 1 例例2W=（AB ,AC, ABC） =(4/6, 1/6, 1/6) B和和C對(duì)稱(chēng)對(duì)稱(chēng), 2=3 Shapley權(quán)力指標(biāo)權(quán)力指標(biāo) 例例3 某股份公司某股份公司4個(gè)股東分別持有個(gè)股東分別持有40%, 30%, 20%, 10%的股份的股份, 公司的決策需經(jīng)持有半數(shù)以上股份的股東的同公司的決策需經(jīng)持有半數(shù)以上股份的股東的同意才可通過(guò)意才可通過(guò), 求求4個(gè)股東在公司決策中的個(gè)股東在公司決策中的Shapl

46、ey指標(biāo)指標(biāo). 4個(gè)股東個(gè)股東A,B,C,D的加權(quán)投票系統(tǒng)的加權(quán)投票系統(tǒng) S=6: 4，3，2，1 A,B,C,D 有有4!=24個(gè)全排列，找出個(gè)全排列，找出決定者決定者，下劃?rùn)M線：，下劃?rùn)M線： 決定者次數(shù)決定者次數(shù)=(10, 6, 6, 2) =(5/12, 3/12, 3/12, 1/12) Wm=(AB ,AC, BCD）B和和C對(duì)稱(chēng)對(duì)稱(chēng), 2=3 ABCD ABDC ACBD ACDB ADBC ADCB BACD BADC BCAD BCDA BDAC BDCA CABD CADB CBAD CBDA CDAB CDBA DABC DACB DBAC DBCA DCAB DCBA保留

47、保留B在在C之前的之前的12個(gè)排列統(tǒng)計(jì)個(gè)排列統(tǒng)計(jì)A,B(C),D為決定者的次數(shù)為決定者的次數(shù). 簡(jiǎn)化簡(jiǎn)化Banzhaf 權(quán)力指標(biāo)權(quán)力指標(biāo) S(4)=3: 2, 1, 1 例例2Shapley指標(biāo)指標(biāo)=(4/6, 1/6, 1/6) W=(AB ,AC, ABC）獲勝聯(lián)盟獲勝聯(lián)盟AB: 由于由于A的加入才成為獲勝聯(lián)盟的加入才成為獲勝聯(lián)盟 由于由于B的加入才成為獲勝聯(lián)盟的加入才成為獲勝聯(lián)盟AC: 由于由于A的加入才成為獲勝聯(lián)盟的加入才成為獲勝聯(lián)盟 由于由于C的加入才成為獲勝聯(lián)盟的加入才成為獲勝聯(lián)盟ABC: 由于由于A的加入才成為獲勝聯(lián)盟的加入才成為獲勝聯(lián)盟ABACABCA下有下有3條橫線，條橫線，

48、B, C下各有下各有1條橫線條橫線 Banzhaf指標(biāo)（指標(biāo)（3，1，1） （3/5, 1/5, 1/5） 歸一化歸一化 Banzhaf 權(quán)力指標(biāo)權(quán)力指標(biāo) 寫(xiě)出投票人的寫(xiě)出投票人的獲勝聯(lián)盟集獲勝聯(lián)盟集W; 對(duì)每一個(gè)對(duì)每一個(gè)獲勝聯(lián)盟獲勝聯(lián)盟檢查檢查每位投票人是否每位投票人是否決定者決定者; 將每位投票人在所有將每位投票人在所有獲勝聯(lián)盟獲勝聯(lián)盟中的成為中的成為決定者的次數(shù)決定者的次數(shù)歸一化歸一化, 定義為定義為Banzhaf權(quán)力指標(biāo)權(quán)力指標(biāo)=(1,2, ,n). n人加權(quán)投票系統(tǒng)人加權(quán)投票系統(tǒng)例例3 4個(gè)股東個(gè)股東A,B,C,D的加權(quán)投票系統(tǒng)的加權(quán)投票系統(tǒng) S=6: 4, 3, 2, 1 W=（A

49、B ,AC, ABC, ABD, ACD, BCD, ABCD） AB AC ABC ABD ACD BCD ABCD=（5，3，3，1） =(5/12, 3/12, 3/12, 1/12) =(5/12, 3/12, 3/12, 1/12) 歸一化歸一化 Banzhaf 指標(biāo)指標(biāo) Shapley指標(biāo)指標(biāo) 投票人的全投票人的全排列排列 對(duì)排列對(duì)排列由左向右由左向右檢查檢查決定者決定者 統(tǒng)計(jì)每人在所有排列中的統(tǒng)計(jì)每人在所有排列中的決定者次數(shù)決定者次數(shù) 投票人的投票人的獲勝聯(lián)盟集獲勝聯(lián)盟集 對(duì)對(duì)獲勝聯(lián)盟獲勝聯(lián)盟檢查檢查決定者決定者 統(tǒng)計(jì)每人在所有統(tǒng)計(jì)每人在所有獲勝獲勝聯(lián)盟聯(lián)盟中的決定者次數(shù)中的決定

50、者次數(shù)每個(gè)每個(gè)排列中有且只有一個(gè)排列中有且只有一個(gè)決定者決定者每個(gè)每個(gè)組合中沒(méi)有或有組合中沒(méi)有或有(幾個(gè)幾個(gè))決定者決定者(=/ n!) 已歸一化已歸一化需需歸一化才得到歸一化才得到都滿足度量權(quán)力的數(shù)量指標(biāo)應(yīng)該具有的性質(zhì)都滿足度量權(quán)力的數(shù)量指標(biāo)應(yīng)該具有的性質(zhì). 加權(quán)投票與權(quán)力指標(biāo)的應(yīng)用加權(quán)投票與權(quán)力指標(biāo)的應(yīng)用 例例4 拳擊比賽設(shè)拳擊比賽設(shè)2個(gè)個(gè)5人裁判組人裁判組, 每每人人一票一票. 若第若第1組以組以5:0 或或4:1判選手甲勝判選手甲勝, 則甲勝則甲勝; 若以若以3:2判甲勝判甲勝, 則第則第2組再判組再判; 除非第除非第2組以組以0:5或或1:4判甲負(fù)判甲負(fù), 其他情況最終都判甲勝其他情

51、況最終都判甲勝. 將以上裁判規(guī)則用加權(quán)投票系統(tǒng)表示將以上裁判規(guī)則用加權(quán)投票系統(tǒng)表示; 計(jì)算系統(tǒng)的計(jì)算系統(tǒng)的Shapley指標(biāo)和指標(biāo)和Banzhaf指標(biāo)指標(biāo). 設(shè)兩組設(shè)兩組10人同時(shí)裁判人同時(shí)裁判, 組成組成N=A, A, A, A, A, B, B, B, B, B 極小獲勝聯(lián)盟極小獲勝聯(lián)盟Wm =3A2B , S=q: a, a, a, a, a, 1, 1, 1, 1, 1 (4A , 2A4B),4qa ,42qa,23qa第第1組組5人權(quán)重各人權(quán)重各2, 第第2組人權(quán)重各組人權(quán)重各1, 按簡(jiǎn)單多數(shù)規(guī)則執(zhí)行按簡(jiǎn)單多數(shù)規(guī)則執(zhí)行. a=2, q=8 例例4極小獲勝聯(lián)盟極小獲勝聯(lián)盟Wm =3A

52、2B , (4A , 2A4B)一個(gè)一個(gè)B在所有排列中的決定者次數(shù)在所有排列中的決定者次數(shù)/ 10！(3A1B)B(2A3B)(2A3B)B(3A1B)! 5 ! 41435CC! 5 ! 43425CC0635. 0)(!10! 5 ! 434251435CCCC一個(gè)一個(gè)A的的Shapley指標(biāo)指標(biāo) 1365. 0)56341 (51=(0.1365, , 0.1365, 0.0635, , 0.0635) 計(jì)算計(jì)算S=8: 2, 2, 2, 2, 2, 1, 1, 1, 1, 1 的的Shapley指標(biāo)指標(biāo)一個(gè)一個(gè)B的的 Shapley指標(biāo)指標(biāo) 只需考察只需考察Shapley指標(biāo)指標(biāo) 例例

53、4 計(jì)算計(jì)算S=8: 2, 2, 2, 2, 2, 1, 1, 1, 1, 1 的的Banzhaf指標(biāo)指標(biāo)考察考察A，B可能成為決定者的那些可能成為決定者的那些獲勝聯(lián)盟類(lèi)型和個(gè)數(shù)獲勝聯(lián)盟類(lèi)型和個(gè)數(shù) 獲勝聯(lián)盟類(lèi)型獲勝聯(lián)盟類(lèi)型4A 4A1B 3A2B3A3B 2A4B2A5B聯(lián)盟個(gè)數(shù)聯(lián)盟個(gè)數(shù)5251001005010A為決定者次數(shù)為決定者次數(shù)2010030030010020B為決定者次數(shù)為決定者次數(shù)0020002000A為決定者的次數(shù)與為決定者的次數(shù)與B為決定者的次數(shù)之比為決定者的次數(shù)之比 840:400 =(0.1355, , 0.1355, 0.0645, , 0.0645) =(0.1365

54、, , 0.1365, 0.0635, , 0.0635) w=(0.1333, , 0.1333, 0.0667, , 0.0667) 對(duì)對(duì)比比總和總和 840總和總和 400例例5 “團(tuán)結(jié)就是力量團(tuán)結(jié)就是力量”嗎？嗎？40位議員組成議會(huì)位議員組成議會(huì), “民主黨民主黨”(M)11席席, “共和黨共和黨”(G)14席席,獨(dú)立人士獨(dú)立人士(D) 15席席, 投票采取簡(jiǎn)單多數(shù)規(guī)則投票采取簡(jiǎn)單多數(shù)規(guī)則, 21票通過(guò)票通過(guò). 在在獨(dú)立獨(dú)立和黨派和黨派結(jié)盟結(jié)盟情況下計(jì)算議員的情況下計(jì)算議員的Shapley指標(biāo)指標(biāo).1. 獨(dú)立獨(dú)立投票系統(tǒng)投票系統(tǒng) S(1)=21;1,1,1 每位議員的每位議員的Shap

55、ley指標(biāo)相等指標(biāo)相等：i=1/40, i=1, ,40“民主黨民主黨”、”共和黨共和黨”、獨(dú)立人士議員的、獨(dú)立人士議員的Shapley指標(biāo)：指標(biāo)：M=11/40=0.275, G=14/40=0.350,D=15/40=0.375 通過(guò)通過(guò)黨派黨派結(jié)盟能加強(qiáng)權(quán)力嗎結(jié)盟能加強(qiáng)權(quán)力嗎? 2. “民主黨民主黨”(M)11 位議員結(jié)盟系統(tǒng)位議員結(jié)盟系統(tǒng)S(2) =21;11,1,1 例例5 “團(tuán)結(jié)就是力量團(tuán)結(jié)就是力量”嗎？嗎？計(jì)算計(jì)算M 29 個(gè)1MM加入加入, 成為決定者成為決定者 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 2

56、3 24 25 26 27 28 29 30M= 11/30=0.367 在余下的在余下的1-11/30=19/30中中G和和D的的Shapley指標(biāo)指標(biāo)按照按照14:15分配分配G= (19/30)*(14/29)=0.306,D=0.327 對(duì)比對(duì)比 S(1)=21;1,1,1 :M=0.275, G=0.350,D=0.375 考察考察M在在30人中的位置人中的位置 : M+G(14)+D(15)“民主黨民主黨“結(jié)盟使結(jié)盟使M增加增加 , G,D減少減少. 例例5 “團(tuán)結(jié)就是力量團(tuán)結(jié)就是力量”嗎？嗎？3. “共和黨共和黨”14位議員也結(jié)盟位議員也結(jié)盟, 系統(tǒng)系統(tǒng)S(3) =21;11,1

57、4,1,1 15 個(gè)1MG1716151413121110 9 8 7 6 5 4 3 2 1 00 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 M 加加 入位置入位置 i G加加入入位位置置 jD (j7, i8 )M(j7, i8 )DMGG (j 7)(i, j)對(duì)應(yīng)左下方方格對(duì)應(yīng)左下方方格,共共272個(gè)個(gè)(除對(duì)角線除對(duì)角線).對(duì)角線對(duì)角線以下方格以下方格G在在M之前加入之前加入 數(shù)數(shù)決定者決定者方格方格:M49, G100, D123 M=49/272=0.180G= 100/272=0.368D=0.452 例例5 “團(tuán)結(jié)就是力量團(tuán)結(jié)就是力量”

58、嗎？嗎？“共和黨共和黨”不結(jié)盟不結(jié)盟“共和黨共和黨”結(jié)盟結(jié)盟“民主黨民主黨”不結(jié)不結(jié)盟盟M=0.275 G=0.350M=0.188 G=0.556“民主黨民主黨”結(jié)盟結(jié)盟M=0.367 G=0.306M=0.180 G=0.368 不論不論”民主黨民主黨”是否結(jié)盟，是否結(jié)盟，”共和黨共和黨”結(jié)盟總比單干好結(jié)盟總比單干好. “共和黨共和黨”一旦結(jié)盟，一旦結(jié)盟，”民主黨民主黨”不結(jié)盟更好不結(jié)盟更好. 從從”民主黨民主黨”角度看角度看, 應(yīng)該盡量保持大家都是單干的局面應(yīng)該盡量保持大家都是單干的局面, 若率先結(jié)盟會(huì)誘使若率先結(jié)盟會(huì)誘使”共和黨共和黨”也結(jié)盟也結(jié)盟, 結(jié)果會(huì)敗得很慘結(jié)果會(huì)敗得很慘. 從

59、獨(dú)立人士角度看從獨(dú)立人士角度看, 若只有若只有”民主黨民主黨”或或”共和黨共和黨”結(jié)盟結(jié)盟自己都有損失自己都有損失, 但若兩個(gè)黨均結(jié)盟但若兩個(gè)黨均結(jié)盟, 反而可得漁翁之利反而可得漁翁之利 .兩種權(quán)力指標(biāo)的公理化兩種權(quán)力指標(biāo)的公理化 Shapley指標(biāo)指標(biāo)1954年提出年提出, 1975年公理化年公理化. Banzhaf指標(biāo)指標(biāo)1965年提出年提出, 1979年公理化年公理化. 投票人集合投票人集合I=1, 2, , n, 投票系統(tǒng)投票系統(tǒng)S=q: w1, w2, ，wn niiSvSvnsnsvShSiISi, 2 , 1),()(!)!()!1()(niiSvSvvBzSiISni, 2 ,

60、 1),()(21)(1Banzhaf 指標(biāo)指標(biāo)Shapley指標(biāo)指標(biāo)I的任一子集的任一子集S對(duì)應(yīng)一個(gè)實(shí)值、單調(diào)函數(shù)對(duì)應(yīng)一個(gè)實(shí)值、單調(diào)函數(shù)v, 若若S為獲勝聯(lián)盟為獲勝聯(lián)盟v(S)=1, 否則否則v(S)=0. 若若i在在S中是決定者中是決定者, 1)()(iSvSv 計(jì)算計(jì)算i為決定者的次數(shù)為決定者的次數(shù) 按排列計(jì)算按排列計(jì)算 (sS中人數(shù)中人數(shù))兩種權(quán)力指標(biāo)的公理化兩種權(quán)力指標(biāo)的公理化 i=Ai=Bi=CA BA CA B CA BA C1/221/41/41/41/41/4Bz3/41/41/4s22322(s-1)! (3-s)!/ 3!1/61/62/61/61/6Sh4/61/61/