《數(shù)學(xué)建模 第十一章博弈模型M11-2010》由會員分享，可在線閱讀，更多相關(guān)《數(shù)學(xué)建模 第十一章博弈模型M11-2010（80頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第 十 一 章 博 弈 模 型11.1 進 攻 與 撤 退 的 抉 擇11.2 讓 報 童 訂 購 更 多 的 報 紙11.3 “一 口 價 ” 的 戰(zhàn) 略 11.4 不 患 寡 而 患 不 均 11.5 效 益 的 合 理 分 配 11.6 加 權(quán) 投 票 中 權(quán) 力 的 度 量 單一決策主體決策變量目標函數(shù)約束條件決策主體的決策行為發(fā)生直接相互作用 (相互影響)博 弈 模 型 非 合 作 博 弈合 作 博 弈三要素博弈模型(G ame Theory)多個決策主體優(yōu)化模型(Optimization)決 策 問 題 （ Decision Problem）靜態(tài)、動態(tài)信息完全、不完全軍事、政治、經(jīng)

2、濟、企業(yè)管理和社會科學(xué)中應(yīng)用廣泛 1944年6月初，盟軍在諾曼底登陸成功. 到8月初的形勢： 背景 11.1 進 攻 與 撤 退 的 抉 擇雙方應(yīng)該如何決策 ？強化缺口盟軍(預(yù)備隊)撤退進攻德軍盟軍(加)盟軍(英)盟軍(美一)盟軍(美三)東進原地待命 模 型 假 設(shè) 博弈參與者為兩方（盟軍和德軍） 盟軍有3種使用其預(yù)備隊的行動：強化缺口，原地待命，東進；德軍有2種行動：向西進攻或向東撤退. 博弈雙方完全理性，目的都是使戰(zhàn)斗中己方獲得的凈勝場次（勝利場次減去失敗場次）盡可能多. 盟軍勝1場盟軍敗2場東進無戰(zhàn)斗盟軍勝2場原地待命無戰(zhàn)斗盟軍勝1場強化缺口向東撤退向西進攻盟軍德軍完全信息靜態(tài)博弈 共同

3、知識(以上信息雙方共有) 雙方同時做出決策 博 弈 模 型 博弈參與者集合N=1,2(1為盟軍，2為德軍) 用u1(a1，a2)表示對盟軍產(chǎn)生的結(jié)果，即凈勝場次，稱為盟軍的效用函數(shù). 盟軍勝1場盟軍敗2場東進無戰(zhàn)斗盟軍勝2場原地待命無戰(zhàn)斗盟軍勝1場強化缺口向東撤退向西進攻盟軍德軍 12 02 01 23ijmM 盟軍行動a1 A1=1,2,3(強化缺口/原地待命/東進)； 德軍行動a2 A2=1,2(進攻/撤退)。 (行動：即純戰(zhàn)略)支付矩陣（Payoff Matrix） 完全競爭: 零和博弈 (常數(shù)和博弈) u 2(a1，a2)對應(yīng) -M 博 弈 的 解 的 概 念 ：納什均衡 (NE: N

4、ash Equilibrium)不存在(純)NE .2,1),(),( ,3,2,1),(),( 22*12*2*12 1*211*2*11 aaauaau aaauaau(純戰(zhàn)略)納什均衡Nash: 1994年 獲 諾 貝 爾 經(jīng) 濟 學(xué) 獎NE: 單向改變戰(zhàn)略不能提高自己效用，即每一方的戰(zhàn)略對于他方的戰(zhàn)略而言都是最優(yōu)的,稱為最優(yōu)反應(yīng). 12 02 01 23ijmM (純)NE: a*=(a1*, a2*) =(2, 2) 1,12,2 1,22,2 1,11,1M非常數(shù)和博弈(雙矩陣表示) 混合戰(zhàn)略（策略：Strategy) 盟軍的混合戰(zhàn)略集 期望收益盟軍德軍 S1=p=(p1, p2,

5、 p3) | 31 1,10 i ii pp德軍的混合戰(zhàn)略集 S2= q=(q1, q2) | 21 1,10 i ii qqTSp pMq 1max TSq pMq2min完全信息靜態(tài)博弈有限博弈矩陣博弈 (2人)零和博弈常數(shù)和博弈 ),(),( ),( 12 31 211 qpUqpU qmppMqqpU i j jijiT 模 型 求 解理性推理：不管自己怎么做，另一方總是希望盡量使自己得分盡量低.（二人零和博弈，完全競爭） 盟軍德軍TSp pMq1max TSq pMq2min線性規(guī)劃 從一個給定的戰(zhàn)略中期望得到的贏得，總是采用該策略時他們可能得到的最壞的贏得！ 盟軍可以用min pM

6、來衡量策略p的好壞 max U 1(p) = min pM min U2(q) = max MqT 德軍可以用max MqT來衡量策略q的好壞 (p*, q*): 混合(策略)納什均衡(Mixed NE) p2*=3/5，p3*=2/5q1*=1/5，q2*=4/5最優(yōu)值均為2/5 占優(yōu)(dominate)：盟軍的行動2占優(yōu)于1 （前面的非常數(shù)和博弈M類似）混合策略似乎不太可行! 但概率可作為參考. -現(xiàn)實：盟軍讓預(yù)備隊原地待命（行動2），而德軍沒有選擇撤退（行動2），結(jié)果德軍大敗. 模 型 評 述 博弈規(guī)則至關(guān)重要的，如參與人決策的時間順序、決策時擁有哪些信息等. 11 01 00M多人(或

7、非常數(shù)和)博弈問題，一般不能用上面的線性規(guī)劃方法求解，而通過納什均衡的定義求解. 小 結(jié) ： 博 弈 模 型 的 基 本 要 素 參與人 理性假設(shè) 行動順序（靜態(tài)、動態(tài)） 信息結(jié)構(gòu)（完全、不完全） 行動空間（及戰(zhàn)略空間） 效用函數(shù) 參 與 者 完 全 理 性 (最 大 化 效 用 )其他因素納什均衡單 向 改 變 戰(zhàn) 略 不 能 提 高 自 己 效 用 11.2 讓 報 童 訂 購 更 多 的 報 紙 報童模型回顧訂購價w，零售價p，處理價v（pwv0）需求量：密度函數(shù)f(x)、分布函數(shù)F(x), F(0)=0訂購Q份報紙，期望銷售量為 QQQQ Q dxxFQQFQdxxFxxF dxxQf

8、dxxxfQS 0000 )()(1()(|)( )()()(期望存貨量 Q dxxFQSQQI 0 )()()(期望利潤 QvwQSvpwQQvIQpSQG )()()()()()( 最優(yōu)訂購量Qr vp wpQF r )( Qr(w) 11.2 讓 報 童 訂 購 更 多 的 報 紙 問題假設(shè)報社報紙成本價為c，wcv )()( Max wQcw rcw vp wpFcw 1)( w*完全信息動態(tài)博弈：常稱Stackelberg G ame (兩階段) 子博弈完美均衡: (w*，Qr(w) vp cpQF )( *一般w*c Qr(w*) wbv)bp wpvp cp )()( bpvp

9、vcbbww b )()()( )()()( )()()()()( *bUbUvp vbbU bUbUvp bpbU QvcQSvpbUbU srs srr sr 回 收 協(xié) 議 模 型 模型二 回收數(shù)量協(xié)議 報社回收 達到協(xié)調(diào)報童回收，報童利潤, 報社利潤; 利潤任意分配都可達到 按批發(fā)價回收，比例為 Q QQ QQ dxxFdxxfxQdxxQfQI )1()1()1(01 )()()()()( Q dxxFQIQIQI )1(012 )()()()( 報童利潤 QQ Qr dxxFvpdxxFQwp wQQvIQwIQpSQwU )1(0)1( 21 )()()()( )()()(),(

10、 0),( rQr Q QwU 0)1()1)()(1)( rr QFvwQFwp vp cpQF )( * )1()1)()/()(1)( *QFvwvpcpwp )1()1)()( )()( *QFvpvc vcvpvww q 回 收 協(xié) 議 模 型 模 型 評 述 協(xié)議參數(shù)的確定：不能單方?jīng)Q定雙方談判（合作博弈） 還有很多其他類型的協(xié)議，也可以達到協(xié)調(diào)一種更簡單的協(xié)議批發(fā)價w成本c收取一定加盟費如何評價比較協(xié)議的優(yōu)缺點？是否能達到協(xié)調(diào)是否能任意分配利潤協(xié)議執(zhí)行成本有多高 11.3 “一 口 價 ” 的 戰(zhàn) 略 背 景 為了節(jié)省“討價還價”時間，考慮“一口價”模式. 雙方同時報價：若買價賣

11、價，則以均價成交; 否則不成交.問 題 雙方應(yīng)如何報價？ 雙方總能成交嗎？（效率估計） “討價還價”很浪費買賣雙方的寶貴時間. 模 型 假 設(shè) 與 建 立 賣方知道物品對自己的價值，但買方不知道. 買方知道物品對自己的價值，但賣方不知道. 雙方都知道（如猜出）對方價值的分布信息.賣方價值vs, 買方價值vb, 均服從U0,1 (均勻分布) 賣方報價ps, 買方報價pb, pb ps時成交價p (pb+ps)/2成交效用：賣方U1=p- vs, 買方U2= vb p; 不成交: 0雙方完全理性(最大化自己的期望效用 ).以上為雙方的共同知識. 賣方報價ps ps(vs)買方報價pb pb(vb)

12、雙方戰(zhàn)略戰(zhàn)略組合( ps(vs), pb(vb) 何時構(gòu)成均衡？定義在0，1區(qū)間上、取值也在0，1區(qū)間上的非減函數(shù). 不完全信息靜態(tài)博弈（靜態(tài)貝葉斯博弈）貝葉斯納什均衡單 向 改 變 戰(zhàn) 略 不 能提 高 自 己 效 用 .信 息 非 對 稱 （ 不 完 全 信 息 ）模 型 假 設(shè) 與 建 立 均衡條件具體戰(zhàn)略(函數(shù))形式不同，均衡就可能不同.單 一 價 格 戰(zhàn) 略賣方：買方：雙方戰(zhàn)略互為最優(yōu)反應(yīng)，所以構(gòu)成貝葉斯納什均衡！)(Pr*2 )(|)(max sbbssbbbbsp pvpvpvpvpEps )(Pr*2 )(|)(max ssbssbssbbp vppvppvpEpv b xv

13、xvxvp ssss ,1,)( xv xvxvp bbbb ,0,)( 模 型 假 設(shè) 與 建 立 單一價格戰(zhàn)略效率為x(1-x)/0.50.5x0.5效率最大(1/2)對給定的(vs, vb)，當vsxj=1-xi時，i(x)xi-i (xi -xj)= i -(2i -1)xi關(guān)于xi的系數(shù)非正 （過分“愧疚” ）效用函數(shù)財富總額為1接受提議：甲乙所得x1=1-s, x2= s；否則：x1=x2=0 iji xxxxxxxU jiiijiii 3,2,1 0,max0,max),( 21 0 ii 2/1i 模 型 求 解如果不接受，則x1=x2=0; U1(s)=U2(s)=0 . 若

14、s1/2,則x2 x1乙 的 最 優(yōu) 反 應(yīng)乙 的 最 優(yōu) 反 應(yīng) （ 給 定 s）如果接受，則x1=1-s, x2=s. 若s1/2,則x2x1U2(s)0 0,max0,max),( 21 jiiijiii xxxxxxxU 1/20 )12()( 22 sssU 2222 )21()21()( ssssU s )21/()( 222 s當 s 接受; 否則，不接受)( 2s 2/1)(0 2 s易知 (s1/2, 兩者一致) 2/12 模 型 求 解Case 1: 甲 知 道 乙 的 2 若s1/2,則x2 x1甲 的 決 策 s=1/2時達到最大值1/2甲 的 決 策 (只 需 考 慮

15、 乙 接 受 情 形 )12(1)( 11 sssU 若s1/2,則x2 x1但 s )( 2s ssssU )12(1)21(1)( 1111 )21/()( 222* ss 2/11 均 衡 : (s*,接 受 ) s*嚴格小于50%; 是乙的“憤怒”系數(shù)2的增函數(shù). 模 型 求 解 ： 甲 的 決 策Case 2: 甲 不 知 道 乙 的 2, 但 知 道 2知 道 分 布 F(2) 若s1/2,則x2 x1甲 的 決 策 若s1/2,則x2 x1 U1(s)=1-s-1(2s-1) 同前期望效用乙接受概率s * 1)(min 0)(max FF )(,1 )()(),21/( )(,0

16、 ss sssssF ssp )(,)12(1 )()(),21/()12(1 )(,0)( 11 111 sss sssssFs sssEU )21/()12(1 11)()( ssFsMaxsss 模 型 解 釋 甲永遠不會提出大于/的方案s 乙拒絕過小的方案s很好地解釋了實際中的最后通牒博弈 乙接受概率隨s增加不減參考文獻 11.5 效 益 的 合 理 分 配11 321 xxx 45732 31 21 xx xx xx 例甲乙丙三人合作經(jīng)商，若甲乙合作獲利7元，甲丙合作獲利5元，乙丙合作獲利4元，三人合作獲利11元. 又知每人單干獲利1元.問三人合作時如何分配獲利？記甲乙丙三人分配為)

17、,( 321 xxxx解不唯一(5，3，3)(4，4，3)(5，4，2) 1, 321 xxx )(1 Ivxni i niivxi ,2,1),( 212121 0 sssvsvssvv ),()()( )( ,2,1 nI 集合 (1) Shapley合 作 對 策滿足實函數(shù)，子集)(svIs I,v n人合作對策，v特征函數(shù)),( 21 nxxxx n人從v(I)得到的分配，滿足v(s) 子集s的獲利 ! )!1()!()( n ssnsw niisvsvswx iSsi ,),()()( 21 公理化方法s子集 s中的元素數(shù)目， Si 包含i的所有子集)( sw 由s決定的“貢獻”的權(quán)

18、重 Shapley值)()( isvsv i 對合作s 的“貢獻”)( siShapley合 作 對 策 三人(I=1,2,3)經(jīng)商中甲的分配x1的計算 1/3 1/6 1/6 1/3)1()()( svsvsw )( sw s )1()( svsv )1(sv )(sv 1S 1 1 2 1 3 I 1 7 5 11 0 1 1 4 1 6 4 7 1/3 1 2/3 7/3x 1=13/3類似可得 x2=23/6, x3=17/6 )1()()(11 svsvswx Ss 1 2 2 3 合 作 對 策 的 應(yīng) 用 污 水 處 理 費 用 的 合 理 分 擔20km 38km河流三城鎮(zhèn)地理

19、位置示意圖1 2 3 污水處理，排入河流.三城鎮(zhèn)可單獨建處理廠，或聯(lián)合建廠(用管道將污水由上游城鎮(zhèn)送往下游城鎮(zhèn)).Q1=5 Q3=5Q2=3 Q污水量，L管道長度建廠費用P 1=73Q0.712管道費用P2=0.66Q0.51L 230)3(,160)2(,230573)1( 712.0 CCC 35020566.0)35(73)2,1( 51.0712.0 C 36538366.0)53(73)3,2( 51.0712.0 C 46358566.0)55(73)3,1( 51.0712.0 C 460)3()1( CC 污 水 處 理 的 5 種 方 案1）單獨建廠620)3()2()1(1

20、 CCCD總投資2）1, 2合作3）2, 3合作4）1, 3合作580)3()2,1( 2 CCD總投資595)3,2()1(3 CCD總投資合作不會實現(xiàn) 55638)35(66.0 20566.0)535(73)3,2,1( 51.0 51.0712.05 CD5）三城合作總投資D5最小, 應(yīng)聯(lián)合建廠 建廠費：d1=73(5+3+5)0.712=453 12 管道費：d2=0.66 50.51 20=30 23 管道費：d3=0.66 (5+3)0.51 38=73D5城3建議：d1 按 5:3:5分擔, d2,d3由城1,2擔負城2建議：d3由城1,2按 5:3分擔, d2由城1擔負城1計

21、算：城3分擔 d15/13=174C(3), 城2分擔 d 13/13+d3 3/8 =132C(1)不 同 意 ! D5如何分擔？230)3( 160)2( 230)1( CCC 0)3()2()1(,0)( vvvv 3,2,1I集合特征函數(shù)v(s)聯(lián)合(集s)建廠比單獨建廠節(jié)約的投資),( 321 xxxx 三城從節(jié)約投資v(I)中得到的分配40350160230)2,1()2()1()21( CCCv 64556230160230)3,2,1()3()2()1()( 0)31( 25365230160)3,2()3()2()32( CCCCIvv CCCv Shapley合 作 對 策

22、 計算城1從節(jié)約投資中得到的分配x1)1()()( svsvsw )(sw s )1()( svsv )1(sv )(svs 1 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 x 1 =19.7,城1 C(1)-x1=210.4, 城2 C(2)-x2=127.8, 城3 C(3)-x3=217.8三城在總投資556中的分擔x2 =32.1, x3=12.2 x2最大，如何解釋？ 優(yōu) 點 ：公正、合理，有公理化基礎(chǔ)。如n個單位治理污染, 通常知道第i方單獨治理的投資yi 和n方共同治理的投資Y, 及

23、第i方不參加時其余n-1方的投資zi (i=1,2, ,n). 確定共同治理時各方分擔的費用. iij j zyiIv )(其他v(s)均不知道, 無法用Shapley合作對策求解 Shapley合作對策小結(jié)若定義特征函數(shù)為合作的獲利(節(jié)約的投資)，則有 ,)(),()( YyIvniiv ni i 1210 缺 點 ：需要知道所有合作的獲利，即要定義I=1,2,n的所有子集(共2n-1個)的特征函數(shù)，實際上常做不到. ),( nbbb 1記設(shè)只知道)( iIvbi 無 i 參加時n-1方合作的獲利)(IvB及全體合作的獲利021 in xxxxxB ),( 的分配求各方對獲利),(),7,5

24、,4(11 321 xxxxbB 求，即已知 求 解 合 作 對 策 的 其 他 方 法例. 甲乙丙三人合作經(jīng)商，若甲乙合作獲利7元，甲丙合作獲利5元，乙丙合作獲利4元，三人合作獲利11元. 問三人合作時如何分配獲利？ （ 1） 協(xié) 商 解 00, AbAx TT 11 nniii bxx bxx Bx 11將剩余獲利 平均分配 ixB nBbbnxBnxx iiiii 1)(1 11),7,5,4(. Bb例模型 以n-1方合作的獲利為下限 TT bxA 求解 iii bbnx 11 xi 的下限,3),1,3,4( ixBx )2,4,5()1,1,1( xx （ 2） Nash解 ),(

25、 1 nddd 記為現(xiàn)狀點（談判時的威懾點） ii i ii idx Bxts dxxma . )(ii xd 在此基礎(chǔ)上“均勻地”分配全體合作的獲利B模型0id )(1 iii dBndx平均分配獲利B2）Nash解 1）協(xié)商解 （ 3） 最 小 距 離 解的上限為記xxxx n),( 1 ii ii iixx Bxts xxnmi . )( 2模型 第i 方的邊際效益 ii bBx 若令nBbbnx iii 111),7,5,4(. Bb例 )(1 Bxnxx iii 3）最小距離解 1）協(xié)商解,6),4,6,7( Bxx i )2,4,5()2,2,2( xx （ 4） 滿 意 解 ii

26、 iii de dxu 滿意度Bxts unmixma i ii . )( di現(xiàn)狀點(最低點)ei理想點(最高點)模型iiii xexd , 4）基于滿意度的解 1）協(xié)商解iii xed ,0 )(* iiii ii i deudx de dBu 的比例分配中在按 iiiii xxBxxx （ 5） Raiffi 解 jj xbBnjj 獲利為方合作時的原來無參與當,1)( jininxxxxx jiijj ,1,)1(2,2 :)1的分配基礎(chǔ)上進行方合作獲利的分配（在Bnx 方再等分方平分，和先由11 nnjxj得到再平均取, nj 21 ij jiii xnxnxnnx )1(2 121

27、1 )4,6,7(),1,3,4( xx 與協(xié)商解x=(5,4,2)比較11),7,5,4(. Bb例 )1252,12113,324（x 求 解 合 作 對 策 的 6種 方 法 （ 可 分 為 三 類 ）Shapley合作對策A類B類! )!1()!()( n ssnsw niisvsvswx iSsi ,2,1),()()( )(),( IvBiIvbi 只需Issv ),(需要所有協(xié)商解)(1 iii xBnxx下限ix Nash解 )(1 iii dBndx現(xiàn)狀id最小距離解 )(1 Bxnxx iii上限ix滿意解)( iiiii ii ii deudx de dBu di現(xiàn)狀,

28、ei理想iiii xexd , ii bBx ,1bAx B類4種方法相同 例：有一資方(甲)和二勞方(乙,丙), 僅當資方與至少一勞方合作時才獲利10元，應(yīng)如何分配該獲利？Raiffi解C類)(),( IvBiIvbi 只需方再等分方平分，和先由上限對每個11, nnjxj j 10)(),10,10,0(),(. IvBbiIvbB i )67.1,67.1,67.6().( xShapleyA )0,0,10(, xbBx ii )0,0,10(1 TT bAx )83.0,83.0,34.8(x ij jiii xnxnxnnxRaiffiC )1(2 1211).( )0,0,10(

29、x B類：計算簡單，便于理解，可用于各方實力相差不大的情況；一般來說它偏袒強者. C類： 考慮了分配的上下限，又吸取了Shapley的思想，在一定程度上保護弱者.A類：公正合理；需要信息多，計算復(fù)雜.求 解 合 作 對 策 的 三 類 方 法 小 結(jié) 11.6 加 權(quán) 投 票 中 權(quán) 力 的 度 量 背 景 “一人一票”顯示投票和表決的公正. 股份制公司每位股東投票和表決權(quán)的大小由所占有的股份多少決定. 一些國家、地區(qū)的議會、政府的產(chǎn)生，由所屬的州、縣等各個區(qū)域推出的代表投票決定. 代表投票的權(quán)重取決于所代表區(qū)域的人口數(shù)量. 經(jīng) 濟 或 政 治 機 構(gòu) 權(quán) 力 的 分 配 背 景 典 型 案

30、例 : 美 國 總 統(tǒng) 選 舉 實 行 的 選 舉 人 制 度 美全國50個州和華盛頓特區(qū)共538張選舉人票. 獲選舉人票數(shù)一半以上的總統(tǒng)候選人當選總統(tǒng). 各州選舉人票數(shù)與該州在國會的參、眾議員數(shù)相等. 參議員每州兩位，眾議員人數(shù)由各州人口比例確定. 各州人口懸殊巨大使各州選舉人票數(shù)相差很大. (如加利福尼亞州選舉人票55張，阿拉斯加州只3張) 背 景 典 型 案 例 : 美 國 總 統(tǒng) 選 舉 實 行 的 選 舉 人 制 度 總統(tǒng)候選人在各州內(nèi)進行普選，獲得相對多數(shù)選票的候選人得到該州的全部選舉人票. 48個州和華盛頓特區(qū)都實行“勝者全得” ：在加利福尼亞州以微弱多數(shù)普選獲勝的總統(tǒng)候選人可得

31、到全部55張選舉人票. 若有幾個人口多的州如此，在選舉人投票中就可能使各州累計得票最多的候選人反而不能獲勝.選舉結(jié)果違反全國多數(shù)人的意愿. 2000年 布 什 與 戈 爾 進 行 的 競 選 中 ， 戈 爾 最 終 敗 給 布 什 ！ 問 題由若干區(qū)域(如省、縣等)組成的機構(gòu)中，每區(qū)代表的數(shù)量按照人口比例分配，進行投票選舉和表決時，每區(qū)的全體代表投相同的票. 每區(qū)各派一位代表(投票人)，按照他們所代表的各區(qū)人口比例賦予投票的權(quán)重.如何度量每位代表的投票對最終結(jié)果的影響力(權(quán)力). 介紹兩種合理的、度量權(quán)力的數(shù)量指標. 通過實例給出它們的應(yīng)用. 調(diào)整投票人的權(quán)重使其權(quán)力大致與代表的人口成比例.

32、加 權(quán) 投 票 中 權(quán) 力 的 度 量背景 加 權(quán) 投 票 與 獲 勝 聯(lián) 盟 例1 一縣5區(qū)(A, B, C, D, E )人口為 60, 20, 10, 5, 5 (千人). 每區(qū)一位代表按人口比例分配其投票權(quán)重為12, 4, 2, 1, 1. 按簡單多數(shù)規(guī)則(權(quán)重之和超過總權(quán)重一半)決定投票結(jié)果.將A區(qū)分成人口相等的3個子區(qū)A1，A2，A3 每區(qū)代表的投票權(quán)重為4，4，4，4，2，1，1 決定投票結(jié)果的區(qū)域集合：A1，A2，A3 ，A1, A2, B, A1, A3, C, D, A1, B, C, E , A1, A3, B, D ， A區(qū)代表是獨裁者(能決定投票結(jié)果), 其他代表都是

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

34、BAC: 從B增至BA時BA變?yōu)楂@勝聯(lián)盟A下有4條橫線，B, C下各有1條橫線 Shapley指標（4，1，1） （4/6, 1/6, 1/6） 歸一化 Shapley權(quán) 力 指 標 寫出投票人的共n!個全排列; 對每一個排列由左向右依次檢查，若某位投票人加入時該集合變成獲勝聯(lián)盟，稱該投票人為決定者(Pivot); 將每位投票人在所有排列中的成為決定者的次數(shù)除以n!定義為他們的Shapley權(quán)力指標. =/ n!, =(1, 2, ,n) n人加權(quán)投票系統(tǒng)S (4)=3: 2, 1, 1 例2 W=（AB ,AC, ABC） =(4/6, 1/6, 1/6) B和C對稱, 2=3 Shaple

35、y權(quán) 力 指 標 例3 某股份公司4個股東分別持有40%, 30%, 20%, 10%的股份, 公司的決策需經(jīng)持有半數(shù)以上股份的股東的同意才可通過, 求4個股東在公司決策中的Shapley指標. 4個股東A,B,C,D的加權(quán)投票系統(tǒng) S=6: 4，3，2，1 A,B,C,D 有4!=24個全排列，找出決定者，下劃橫線： 決定者次數(shù)=(10, 6, 6, 2) =(5/12, 3/12, 3/12, 1/12) W m=(AB ,AC, BCD）B和C對稱, 2=3 ABCD ABDC ACBD ACDB ADBC ADCB BACD BADC BCAD BCDA BDAC BDCA CABD

36、CADB CBAD CBDA CDAB CDBA DABC DACB DBAC DBCA DCAB DCBA保留B在C之前的12個排列統(tǒng)計A,B(C),D為決定者的次數(shù). 簡化 Banzhaf 權(quán) 力 指 標 S(4)=3: 2, 1, 1 例2 Shapley指標=(4/6, 1/6, 1/6) W=(AB ,AC, ABC）獲勝聯(lián)盟AB: 由于A的加入才成為獲勝聯(lián)盟 由于B的加入才成為獲勝聯(lián)盟AC: 由于A的加入才成為獲勝聯(lián)盟 由于C的加入才成為獲勝聯(lián)盟ABC: 由于A的加入才成為獲勝聯(lián)盟ABACABCA下有3條橫線，B, C下各有1條橫線 Banzhaf指標（3，1，1） （3/5, 1

37、/5, 1/5） 歸一化 Banzhaf 權(quán) 力 指 標 寫出投票人的獲勝聯(lián)盟集W; 對每一個獲勝聯(lián)盟檢查每位投票人是否決定者; 將每位投票人在所有獲勝聯(lián)盟中的成為決定者的次數(shù)歸一化, 定義為Banzhaf權(quán)力指標=(1,2, ,n). n人加權(quán)投票系統(tǒng)例3 4個股東A,B,C,D的加權(quán)投票系統(tǒng) S=6: 4, 3, 2, 1 W=（AB ,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) 歸一化 Banzh

38、af 指 標 Shapley指 標 投票人的全排列 對排列由左向右檢查決定者 統(tǒng)計每人在所有排列中的決定者次數(shù) 投票人的獲勝聯(lián)盟集 對獲勝聯(lián)盟檢查決定者 統(tǒng)計每人在所有獲勝聯(lián)盟中的決定者次數(shù)每個排列中有且只有一個決定者每個組合中沒有或有(幾個)決定者(=/ n!) 已歸一化需歸一化才得到都滿足度量權(quán)力的數(shù)量指標應(yīng)該具有的性質(zhì). 加 權(quán) 投 票 與 權(quán) 力 指 標 的 應(yīng) 用 例4 拳擊比賽設(shè)2個5人裁判組, 每人一票. 若第1組以5:0 或4:1判選手甲勝, 則甲勝; 若以3:2判甲勝, 則第2組再判; 除非第2組以0:5或1:4判甲負, 其他情況最終都判甲勝. 將以上裁判規(guī)則用加權(quán)投票系統(tǒng)表

39、示; 計算系統(tǒng)的Shapley指標和Banzhaf指標. 設(shè)兩組10人同時裁判, 組成N=A, A, A, A, A, B, B, B, B, B 極小獲勝聯(lián)盟W m = 3A2B , S=q: a, a, a, a, a, 1, 1, 1, 1, 1 (4A , 2A4B),4 qa ,42 qa ,23 qa 第1組5人權(quán)重各2, 第2組人權(quán)重各1, 按簡單多數(shù)規(guī)則執(zhí)行. a=2, q=8 例4極小獲勝聯(lián)盟Wm = 3A2B , (4A , 2A4B)一個B在所有排列中的決定者次數(shù)/ 10！(3A1B)B(2A3B)(2A3B)B(3A1B) !5!41435CC !5!43 425CC

40、0635.0)(!10!5!4 34251435 CCCC一個A的Shapley指標 1365.0)56341(51 =(0.1365, , 0.1365, 0.0635, , 0.0635) 計算S=8: 2, 2, 2, 2, 2, 1, 1, 1, 1, 1 的Shapley指標一個B的 Shapley指標 只需考察Shapley指標 例4計算S=8: 2, 2, 2, 2, 2, 1, 1, 1, 1, 1 的Banzhaf指標考察A，B可能成為決定者的那些獲勝聯(lián)盟類型和個數(shù) 獲勝聯(lián)盟類型4A 4A1B 3A2B 3A3B 2A4B 2A5B聯(lián)盟個數(shù)5 25 100 100 50 10

41、A為決定者次數(shù)20 100 300 300 100 20B為決定者次數(shù)0 0 200 0 200 0A為決定者的次數(shù)與B為決定者的次數(shù)之比 840:400 =(0.1355, , 0.1355, 0.0645, , 0.0645) =(0.1365, , 0.1365, 0.0635, , 0.0635) w=(0.1333, , 0.1333, 0.0667, , 0.0667) 對比總和 840總和 400 例5 “團 結(jié) 就 是 力 量 ” 嗎 ？40位議員組成議會, “民主黨”(M)11席, “共和黨”(G )14席,獨立人士(D) 15席, 投票采取簡單多數(shù)規(guī)則, 21票通過. 在獨

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

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

44、 7 6 5 4 3 2 1 0 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 M 加 入位置 i G加入位置 j D (j7, i8 )M(j7, i8 )D MG G (j 7) (i, j)對應(yīng)左下方方格,共272個(除對角線).對角線以下方格G在M之前加入 數(shù)決定者方格:M49, G 100, D123 M=49/272=0.180G = 100/272=0.368D=0.452 例5 “團 結(jié) 就 是 力 量 ” 嗎 ？“共和黨”不結(jié)盟“共和黨”結(jié)盟“民主黨”不結(jié)盟M=0.275 G =0.350 M=0.188 G =0.556“民主黨”結(jié)

45、盟M=0.367 G =0.306 M=0.180 G =0.368 不論”民主黨”是否結(jié)盟，”共和黨”結(jié)盟總比單干好. “共和黨”一旦結(jié)盟，”民主黨”不結(jié)盟更好. 從”民主黨”角度看, 應(yīng)該盡量保持大家都是單干的局面, 若率先結(jié)盟會誘使”共和黨”也結(jié)盟, 結(jié)果會敗得很慘. 從獨立人士角度看, 若只有”民主黨”或”共和黨”結(jié)盟自己都有損失, 但若兩個黨均結(jié)盟, 反而可得漁翁之利 . 兩 種 權(quán) 力 指 標 的 公 理 化 Shapley指標1954年提出, 1975年公理化. Banzhaf指標1965年提出, 1979年公理化. 投票人集合I=1, 2, , n, 投票系統(tǒng)S=q: w1,

46、w2, ，wn niiSvSvn snsvSh Si ISi ,2,1),()(! )!()!1()( niiSvSvvBz Si ISni ,2,1),()(21)( 1 Banzhaf 指 標Shapley指 標I的任一子集S對應(yīng)一個實值、單調(diào)函數(shù)v, 若S為獲勝聯(lián)盟v(S)=1, 否則v(S)=0. 若i在S中是決定者, 1)()( iSvSv 計算i為決定者的次數(shù) 按排列計算 (sS中人數(shù)) 兩 種 權(quán) 力 指 標 的 公 理 化 i=A i=B i=CA B A C A B C A B A C1/22 1/4 1/4 1/4 1/4 1/4Bz 3/4 1/4 1/4s 2 2 3

47、2 2(s-1)! (3-s)!/ 3! 1/6 1/6 2/6 1/6 1/6Sh 4/6 1/6 1/61)()( iSvSv公理化Bz是/2 n-1, 未歸一化, =(3/4,1/4,1/4),稱絕對Banzhaf指標, 通常比更能反映投票人權(quán)力的真實性.用公理化公式計算例2 S (4)=3: 2, 1, 1的指標Sh和Bz與定義得到的=(4/6, 1/6, 1/6), =(3/5, 1/5, 1/5) 比較. 兩 種 權(quán) 力 指 標 的 概 率 解 釋 投票人對結(jié)果的影響力 投票人能左右結(jié)果的概率. 例2 S(4)=3: 2, 1, 1RA 事件“A能左右結(jié)果”BCCBCBRA 4/3

48、)( ARPBARCAR CB ,可解釋為在各位投票人獨立地、以1/2的概率投贊成或反對票的條件下, 每位投票人能左右結(jié)果的概率. Banzhaf 指 標B,C均以1/2的概率獨立投贊成或反對票 4/1)()( CB RPRP BB投贊成票B投反對票 B )4/1,4/1,4/3()(),(),( CBA RPRPRP 兩 種 權(quán) 力 指 標 的 概 率 解 釋 例2 S(4)=3: 2, 1, 1p每位投票人獨立投贊成票的概率, q=1-p投反對票概率Shapley指 標 222 )()(,22)( pppqRPRPppppqRP CBA BCCBCBRA BARCAR CB ,p在0, 1

49、均勻分布 A, B, C能左右結(jié)果的概率 3/2)( 10 dpRP A 6/1)()( 1010 dpRPdpRP CB可解釋為在各位投票人獨立且 0, 1均勻概率分布地投贊成票的條件下，每位投票人能左右結(jié)果的概率. )6/1,6/1,6/4()(,)(,)( 101010 dpRPdpRPdpRP CBA 調(diào) 整 加 權(quán) 投 票 系 統(tǒng) 例1 人口60, 20, 10, 5, 5 (千人), 比例p=(12, 4, 2, 1, 1) 以p為權(quán)重簡單多數(shù)規(guī)則下投票系統(tǒng)S=11: 12, 4, 2, 1, 1 Banzhaf指標=(1, 0, 0, 0, 0)與p相差很大. 投票人對結(jié)果的權(quán)力

50、與他所代表的人口比例失調(diào). 調(diào)整加權(quán)投票系統(tǒng)的目的: 尋求一組權(quán)重和定額, 使加權(quán)投票系統(tǒng)S= q: w1, w2, ，wn的Banzhaf指標與人口比例p相近似, 且當n較大時近似程度很高 .在權(quán)重不變而增大定額q的情況下, 借助分析極小獲勝聯(lián)盟的辦法, 尋找與p相近似的加權(quán)投票系統(tǒng). 調(diào) 整 加 權(quán) 投 票 系 統(tǒng) 例1 人口比例 p=(12, 4, 2, 1, 1) 系統(tǒng)S=11: 12, 4, 2, 1, 1 權(quán)重不變、增大定額, 尋找與p相近似的投票系統(tǒng). Banzhaf指標=(1, 0, 0, 0, 0)S Wm =(1,2,3,4,5)=(11/21, 5/21, 3/21, 1

51、/21, 1/21 ) S=15: 12, 4, 2, 1, 1 這個是人口比例 p的一個不錯的近似! 12: 12, 4, 2, 1, 1 13: 12, 4, 2, 1, 1 AB ,AC, AD ,AE14: 12, 4, 2, 1, 1 AB ,AC, ADE15: 12, 4, 2, 1, 1 AB ,ACD, ACE16: 12, 4, 2, 1, 1 AB ,ACDE 2=3=4=52=3 1234= 53=4=5(1, 0, 0, 0, 0) 調(diào) 整 加 權(quán) 投 票 系 統(tǒng) 合適地定義與p之間的“距離”(與p看作n維空間的兩個點)作為衡量近似程度的指標. 按照實際需要確定該指標

52、的一個“閾值” 1）給出權(quán)重w和定額q的初值;2）編程計算及與p的距離, 距離小于閾值時停止,否則轉(zhuǎn)3；3）改變w和q, 轉(zhuǎn)2.當n較大時調(diào)整權(quán)重和定額, 尋找與p近似的投票系統(tǒng). 每調(diào)整一次權(quán)重和定額, 必須使極小獲勝聯(lián)盟的結(jié)構(gòu)有所變化, 才有可能改進. 任何一個構(gòu)造和規(guī)則有明確定義的投票系統(tǒng)都可用極小獲勝聯(lián)盟來描述, 并常可表示成加權(quán)投票系統(tǒng)(如例4). 權(quán) 力 度 量 模 型 評 述 存在即使確定了極小獲勝聯(lián)盟也無法表為加權(quán)投票系統(tǒng)的情況. H illiard給出區(qū)別加權(quán)與非加權(quán)投票系統(tǒng)的數(shù)學(xué)方法, 并提供權(quán)重和定額的算法，或者指明不存在權(quán)重和定額的矛盾教材參考文獻35. 兩種權(quán)力指標常

53、常給出相同或近似的結(jié)果, 從理論上區(qū)分它們的數(shù)學(xué)公理既不直觀, 使用時也不具說服力,所以在應(yīng)用中公理化方法并不能解決選擇哪個指標的問題. 權(quán) 力 度 量 模 型 評 述 道理上更淺顯, 容易口頭解釋, 更易為實際工作者接受. 作為對策論中著名的Shapley值方法的副產(chǎn)品在數(shù)學(xué)界更有市場. 適于設(shè)計投票系統(tǒng), 在代表尚未選出之前假定所有投票意愿的等可能性是合理的. 適于評價投票系統(tǒng), 代表已經(jīng)選出, 他們的立場為眾人所知. 在加權(quán)投票系統(tǒng)中定義量化的權(quán)力指標，是將數(shù)學(xué)應(yīng)用于社會政治領(lǐng)域的一個有意義的范例. 提 出 與 “ 計 量 經(jīng) 濟 學(xué) ” 類 似 的 新 學(xué) 科 “ 計 量 政 治學(xué) ” . Shapley指 標 Banzhaf指 標