數(shù)學(xué)建模 第十一章博弈模型M11-2010.ppt

1、第十一章 博弈模型,11.1 進(jìn)攻與撤退的抉擇 11.2 讓報(bào)童訂購(gòu)更多的報(bào)紙 11.3 “一口價(jià)”的戰(zhàn)略 11.4 不患寡而患不均 11.5 效益的合理分配 11.6 加權(quán)投票中權(quán)力的度量,單一決策主體,決策變量目標(biāo)函數(shù)約束條件,決策主體的決策行為發(fā)生直接相互作用 (相互影響),博弈模型,非合作博弈,合作博弈,三要素,多個(gè)決策主體,決策問(wèn)題（Decision Problem）,軍事、政治、經(jīng)濟(jì)、企業(yè)管理和社會(huì)科學(xué)中應(yīng)用廣泛,1944年6月初，盟軍在諾曼底登陸成功. 到8月初的形勢(shì)：,背景,11.1 進(jìn)攻與撤退的抉擇,雙方應(yīng)該如何決策 ？,模型假設(shè),博弈參與者為兩方（盟軍和德軍）,盟軍有3種使

2、用其預(yù)備隊(duì)的行動(dòng)：強(qiáng)化缺口，原地待命，東進(jìn)；德軍有2種行動(dòng)：向西進(jìn)攻或向東撤退.,博弈雙方完全理性，目的都是使戰(zhàn)斗中己方獲得的凈勝場(chǎng)次（勝利場(chǎng)次減去失敗場(chǎng)次）盡可能多.,完全信息靜態(tài)博弈,共同知識(shí)(以上信息雙方共有),雙方同時(shí)做出決策,博弈模型,博弈參與者集合N=1,2(1為盟軍，2為德軍),用u1(a1，a2)表示對(duì)盟軍產(chǎn)生的結(jié)果，即凈勝場(chǎng)次，稱為盟軍的效用函數(shù).,盟軍行動(dòng)a1 A1=1,2,3(強(qiáng)化缺口/原地待命/東進(jìn))； 德軍行動(dòng)a2 A2=1,2(進(jìn)攻/撤退)。 (行動(dòng)：即純戰(zhàn)略),支付矩陣 （Payoff Matrix）,完全競(jìng)爭(zhēng): 零和博弈 (常數(shù)和博弈),u2(a1，a2)對(duì)應(yīng)

3、-M,博弈的解的概念：納什均衡 (NE: Nash Equilibrium),不存在(純)NE,(純戰(zhàn)略)納什均衡,Nash: 1994年獲諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng),NE: 單向改變戰(zhàn)略不能提高自己效用，即每一方的戰(zhàn)略對(duì)于他方的戰(zhàn)略而言都是最優(yōu)的,稱為最優(yōu)反應(yīng).,(純)NE: a*=(a1*, a2*) =(2, 2),非常數(shù)和博弈(雙矩陣表示),混合戰(zhàn)略（策略：Strategy),盟軍的混合戰(zhàn)略集,期望收益,盟軍,德軍,S1=p=(p1, p2, p3) |,德軍的混合戰(zhàn)略集,S2= q=(q1, q2) |,完全信息靜態(tài)博弈 有限博弈矩陣博弈 (2人) 零和博弈常數(shù)和博弈,模型求解,理性推理：不管自

4、己怎么做，另一方總是希望盡量使自己得分盡量低.（二人零和博弈，完全競(jìng)爭(zhēng)）,盟軍,德軍,線性規(guī)劃,從一個(gè)給定的戰(zhàn)略中期望得到的贏得，總是采用該策略時(shí)他們可能得到的最壞的贏得！,盟軍可以用min pM來(lái)衡量策略p的好壞,max U1(p) = min pM,min U2(q) = max MqT,德軍可以用max MqT來(lái)衡量策略q的好壞,(p*, q*): 混合(策略)納什均衡(Mixed NE),p2*=3/5，p3*=2/5,q1*=1/5，q2*=4/5,最優(yōu)值均為2/5,占優(yōu)(dominate)：盟軍的行動(dòng)2占優(yōu)于1 （前面的非常數(shù)和博弈M類似）,混合策略似乎不太可行! 但概率可作為參考

5、. -現(xiàn)實(shí)：盟軍讓預(yù)備隊(duì)原地待命（行動(dòng)2），而德軍沒(méi)有選擇撤退（行動(dòng)2），結(jié)果德軍大敗.,模型評(píng)述,博弈規(guī)則至關(guān)重要的，如參與人決策的時(shí)間順序、決策時(shí)擁有哪些信息等.,多人(或非常數(shù)和)博弈問(wèn)題，一般不能用上面的線性規(guī)劃方法求解，而通過(guò)納什均衡的定義求解.,小結(jié)：博弈模型的基本要素,參與人,理性假設(shè),行動(dòng)順序（靜態(tài)、動(dòng)態(tài)）,信息結(jié)構(gòu)（完全、不完全）,行動(dòng)空間（及戰(zhàn)略空間）,效用函數(shù),參與者完全理性(最大化效用),其他因素,納什均衡,單向改變戰(zhàn)略不能提高自己效用,11.2 讓報(bào)童訂購(gòu)更多的報(bào)紙,報(bào)童模型回顧,訂購(gòu)價(jià)w，零售價(jià)p，處理價(jià)v（pwv0） 需求量：密度函數(shù)f(x)、分布函數(shù)F(x),

6、F(0)=0,訂購(gòu)Q份報(bào)紙，期望銷售量為,期望存貨量,期望利潤(rùn),最優(yōu)訂購(gòu)量Qr,Qr(w),11.2 讓報(bào)童訂購(gòu)更多的報(bào)紙,問(wèn)題,假設(shè)報(bào)社報(bào)紙成本價(jià)為c，wcv, w*,完全信息動(dòng)態(tài)博弈：常稱Stackelberg Game (兩階段) 子博弈完美均衡: (w*，Qr(w),一般w*c Qr(w*) Q* 整體利潤(rùn)有損失,能否改善(協(xié)調(diào))？,假設(shè)報(bào)社與報(bào)童聯(lián)合，整體利潤(rùn)最大,價(jià)格折扣協(xié)議模型,折扣方案wd(Q) 下，報(bào)童效用(期望利潤(rùn)),達(dá)到協(xié)調(diào),假設(shè)報(bào)社與報(bào)童聯(lián)合，整體期望利潤(rùn),關(guān)于Q的減函數(shù)(非線性),，報(bào)童利潤(rùn) ，報(bào)社利潤(rùn) 利潤(rùn)的任意分配比例都可達(dá)到,模型一 回收價(jià)格協(xié)議,原訂貨量,達(dá)到

7、協(xié)調(diào),整體最優(yōu),b，報(bào)童利潤(rùn) ，報(bào)社利潤(rùn) 利潤(rùn)的任意分配比例都可達(dá)到,回收價(jià)b (pwbv),回收協(xié)議模型,模型二 回收數(shù)量協(xié)議,報(bào)社回收,達(dá)到協(xié)調(diào),報(bào)童回收,，報(bào)童利潤(rùn), 報(bào)社利潤(rùn); 利潤(rùn)任意分配都可達(dá)到,按批發(fā)價(jià)回收，比例為,報(bào)童利潤(rùn),回收協(xié)議模型,模型評(píng)述,協(xié)議參數(shù)的確定： 不能單方?jīng)Q定 雙方談判（合作博弈）,還有很多其他類型的協(xié)議，也可以達(dá)到協(xié)調(diào),一種更簡(jiǎn)單的協(xié)議 批發(fā)價(jià)w成本c 收取一定加盟費(fèi),如何評(píng)價(jià)比較協(xié)議的優(yōu)缺點(diǎn)？,是否能達(dá)到協(xié)調(diào),是否能任意分配利潤(rùn),協(xié)議執(zhí)行成本有多高,11.3 “一口價(jià)”的戰(zhàn)略,背景,為了節(jié)省“討價(jià)還價(jià)”時(shí)間，考慮“一口價(jià)”模式.,雙方同時(shí)報(bào)價(jià)：若買價(jià)賣價(jià)，

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

9、戰(zhàn)略,戰(zhàn)略組合( ps(vs), pb(vb) 何時(shí)構(gòu)成均衡？,定義在0，1區(qū)間上、取值也在0，1區(qū)間上的非減函數(shù).,不完全信息靜態(tài)博弈（靜態(tài)貝葉斯博弈）,貝葉斯納什均衡,單向改變戰(zhàn)略不能提高自己效用.,信息非對(duì)稱（不完全信息）,模型假設(shè)與建立,均衡條件,具體戰(zhàn)略(函數(shù))形式不同，均衡就可能不同.,單一價(jià)格戰(zhàn)略,賣方： 買方：,雙方戰(zhàn)略互為最優(yōu)反應(yīng)，所以構(gòu)成貝葉斯納什均衡！,模型假設(shè)與建立,單一價(jià)格戰(zhàn)略效率為,x(1-x)/0.50.5,x0.5 效率最大(1/2),對(duì)給定的(vs, vb)，當(dāng)vsvb時(shí)稱為交易是有利的.,在給定的戰(zhàn)略組合下，有利的全部交易中能夠 實(shí)際發(fā)生交易的比例稱為該戰(zhàn)略

10、的交易效率.,單一價(jià)格戰(zhàn)略,線性價(jià)格戰(zhàn)略,賣方報(bào)價(jià)ps(vs) as+csvs; 買方報(bào)價(jià)pb(vb) ab+cbvb,雙方戰(zhàn)略互為最優(yōu)反應(yīng)， 構(gòu)成貝葉斯納什均衡！,買方：,買方: (同理),不成立時(shí)也適用（不唯一）,線性價(jià)格戰(zhàn)略,評(píng)述,效率（線性價(jià)格戰(zhàn)略）,效率為 1/4*3/4 =9/16,可以證明，線性均衡效率最大.,不存在使所有有利的交易都成交的均衡戰(zhàn)略組合.,信息的不完全（非對(duì)稱信息）降低了交易效率.,包含了交易價(jià)值(交易給雙方帶來(lái)的效用之和，即vbvs)大于1/4的所有有效交易.,11.4 不患寡而患不均,最后通牒博弈(Ultimatum Game),問(wèn)題,甲乙兩人就分配筆錢（如1

11、00元）進(jìn)行博弈.,甲首先提出分配方案 (分給乙的錢: s).,現(xiàn)實(shí)中的情況果真如此嗎？ 多數(shù)s總額的4050% s越小，越容易被乙拒絕,完全信息動(dòng)態(tài)博弈：均衡結(jié)果是(s=0,乙接受); 如果要求嚴(yán)格均衡，則s=分錢.,如果乙接受，則按此分配 ；否則雙方什么也得不到.,公平：利他互惠？,自私： 理性 非理性？,模型假設(shè)與建立,1. 每個(gè)參與者都喜歡對(duì)所有參與者公平的結(jié)果；,2. 每個(gè)參與者自己受到不公平對(duì)待時(shí)的“憤怒”，勝過(guò)其他參與者受到不公平對(duì)待時(shí)的“愧疚”,否則，xixj=1-xi時(shí)， i(x)xi-i (xi -xj)= i -(2i -1)xi 關(guān)于xi的系數(shù)非正 （過(guò)分“愧疚” ）,

12、效用函數(shù),財(cái)富總額為1 接受提議：甲乙所得x1=1-s, x2= s；否則：x1=x2=0,模型求解,如果不接受，則x1=x2=0; U1(s)=U2(s)=0 .,若s1/2,則x2 x1,乙的最優(yōu)反應(yīng),乙的最優(yōu)反應(yīng)（給定s）,如果接受，則x1=1-s, x2=s.,若s1/2,則x2x1,U2(s)0,1/20,易知,(s1/2, 兩者一致),模型求解,Case 1: 甲知道乙的2,若s1/2,則x2 x1,甲的決策,s=1/2時(shí)達(dá)到最大值1/2,甲的決策(只需考慮乙接受情形),均衡: (s*,接受),s*嚴(yán)格小于50%; 是乙的“憤怒”系數(shù)2的增函數(shù).,模型求解：甲的決策,Case 2:

13、 甲不知道乙的2, 但知道2知道分布F(2),若s1/2,則x2 x1,甲的決策,若s1/2,則x2 x1,U1(s)=1-s-1(2s-1) 同前,期望效用,乙接受概率,s*,模型解釋,甲永遠(yuǎn)不會(huì)提出大于/的方案s,乙拒絕過(guò)小的方案s,很好地解釋了實(shí)際中的最后通牒博弈,乙接受概率隨s增加不減,參考文獻(xiàn),11.5 效益的合理分配,例,甲乙丙三人合作經(jīng)商，若甲乙合作獲利7元， 甲丙合作獲利5元，乙丙合作獲利4元， 三人合作獲利11元. 又知每人單干獲利1元. 問(wèn)三人合作時(shí)如何分配獲利？,記甲乙丙三人分配為,解不唯一,(5，3，3) (4，4，3) (5，4，2) ,(1) Shapley合作對(duì)策

14、, I,v n人合作對(duì)策，v特征函數(shù),n人從v(I)得到的分配，滿足,v(s) 子集s的獲利,公理化方法,s子集 s中的元素?cái)?shù)目， Si 包含i的所有子集,由s決定的“貢獻(xiàn)”的權(quán)重, i 對(duì)合作s 的“貢獻(xiàn)”,Shapley合作對(duì)策,三人(I=1,2,3)經(jīng)商中甲的分配x1的計(jì)算,1/3 1/6 1/6 1/3,1 1 2 1 3 I,1 7 5 11,0 1 1 4,1 6 4 7,1/3 1 2/3 7/3,x1=13/3,類似可得 x2=23/6, x3=17/6,1 2 2 3,合作對(duì)策的應(yīng)用 污水處理費(fèi)用的合理分擔(dān),污水處理，排入河流.,三城鎮(zhèn)可單獨(dú)建處理廠，或聯(lián)合建廠(用管道將污水

15、由上游城鎮(zhèn)送往下游城鎮(zhèn)).,Q污水量，L管道長(zhǎng)度 建廠費(fèi)用P1=73Q0.712 管道費(fèi)用P2=0.66Q0.51L,污水處理的5 種方案,1）單獨(dú)建廠,總投資,2）1, 2合作,3）2, 3合作,4）1, 3合作,總投資,總投資,合作不會(huì)實(shí)現(xiàn),5）三城合作總投資,D5最小, 應(yīng)聯(lián)合建廠,建廠費(fèi)：d1=73(5+3+5)0.712=453 12 管道費(fèi)：d2=0.66 50.51 20=30 23 管道費(fèi)：d3=0.66 (5+3)0.51 38=73,D5,城3建議：d1 按 5:3:5分擔(dān), d2,d3由城1,2擔(dān)負(fù),城2建議：d3由城1,2按 5:3分擔(dān), d2由城1擔(dān)負(fù),城1計(jì)算：城3

16、分擔(dān) d15/13=174C(1),不同意!,D5如何分擔(dān)？,特征函數(shù)v(s)聯(lián)合(集s)建廠比單獨(dú)建廠節(jié)約的投資,三城從節(jié)約投資v(I)中得到的分配,Shapley合作對(duì)策,計(jì)算城1從節(jié)約投資中得到的分配x1,x1 =19.7,城1 C(1)-x1=210.4, 城2 C(2)-x2=127.8, 城3 C(3)-x3=217.8,x2 =32.1, x3=12.2,x2最大，如何解釋？,優(yōu)點(diǎn)：公正、合理，有公理化基礎(chǔ)。,如n個(gè)單位治理污染, 通常知道第i方單獨(dú)治理的投資yi 和n方共同治理的投資Y, 及第i方不參加時(shí)其余n-1方的投資zi (i=1,2, ,n). 確定共同治理時(shí)各方分擔(dān)的

17、費(fèi)用.,其他v(s)均不知道, 無(wú)法用Shapley合作對(duì)策求解,Shapley合作對(duì)策小結(jié),若定義特征函數(shù)為合作的獲利(節(jié)約的投資)，則有,缺點(diǎn)：需要知道所有合作的獲利，即要定義I=1,2,n的所有子集(共2n-1個(gè))的特征函數(shù)，實(shí)際上常做不到.,求解合作對(duì)策的其他方法,例. 甲乙丙三人合作經(jīng)商，若甲乙合作獲利7元， 甲丙合作獲利5元，乙丙合作獲利4元，三人 合作獲利11元. 問(wèn)三人合作時(shí)如何分配獲利？,（1）協(xié)商解,將剩余獲利 平均分配,模型,以n-1方合作的獲利為下限,求解, xi 的下限,（2）Nash解,為現(xiàn)狀點(diǎn)（談判時(shí)的威懾點(diǎn)）,在此基礎(chǔ)上“均勻地”分配全體合作的獲利B,模型,（3

18、）最小距離解,模型,第i 方的邊際效益,若令,（4）滿意解,di現(xiàn)狀點(diǎn)(最低點(diǎn)) ei理想點(diǎn)(最高點(diǎn)),模型,（5）Raiffi 解,與協(xié)商解x=(5,4,2)比較,求解合作對(duì)策的6種方法（可分為三類）,Shapley合作對(duì)策,A類,B類,協(xié)商解,Nash解,最小距離解,例：有一資方(甲)和二勞方(乙,丙), 僅當(dāng)資方與至少一勞方合作時(shí)才獲利10元，應(yīng)如何分配該獲利？,Raiffi解,C類,B類：計(jì)算簡(jiǎn)單，便于理解，可用于各方實(shí)力相差不大的情況；一般來(lái)說(shuō)它偏袒強(qiáng)者.,C類： 考慮了分配的上下限，又吸取了Shapley的思想，在一定程度上保護(hù)弱者.,A類：公正合理；需要信息多，計(jì)算復(fù)雜.,求解合

19、作對(duì)策的三類方法小結(jié),11.6 加權(quán)投票中權(quán)力的度量,背景,“一人一票”顯示投票和表決的公正.,股份制公司每位股東投票和表決權(quán)的大小由所占有的股份多少?zèng)Q定.,一些國(guó)家、地區(qū)的議會(huì)、政府的產(chǎn)生，由所屬的州、縣等各個(gè)區(qū)域推出的代表投票決定.,代表投票的權(quán)重取決于所代表區(qū)域的人口數(shù)量.,經(jīng)濟(jì)或政治機(jī)構(gòu)權(quán)力的分配,背景,典型案例: 美國(guó)總統(tǒng)選舉實(shí)行的選舉人制度,美全國(guó)50個(gè)州和華盛頓特區(qū)共538張選舉人票.,獲選舉人票數(shù)一半以上的總統(tǒng)候選人當(dāng)選總統(tǒng).,各州選舉人票數(shù)與該州在國(guó)會(huì)的參、眾議員數(shù)相等.,參議員每州兩位，眾議員人數(shù)由各州人口比例確定.,各州人口懸殊巨大使各州選舉人票數(shù)相差很大.,(如加利福尼

20、亞州選舉人票55張，阿拉斯加州只3張),背景,典型案例: 美國(guó)總統(tǒng)選舉實(shí)行的選舉人制度,總統(tǒng)候選人在各州內(nèi)進(jìn)行普選，獲得相對(duì)多數(shù)選票的候選人得到該州的全部選舉人票.,48個(gè)州和華盛頓特區(qū)都實(shí)行“勝者全得” ：,在加利福尼亞州以微弱多數(shù)普選獲勝的總統(tǒng)候選人可得到全部55張選舉人票.,若有幾個(gè)人口多的州如此，在選舉人投票中就可能使各州累計(jì)得票最多的候選人反而不能獲勝.,選舉結(jié)果違反全國(guó)多數(shù)人的意愿.,2000年布什與戈?duì)栠M(jìn)行的競(jìng)選中，戈?duì)栕罱K敗給布什！,問(wèn)題,由若干區(qū)域(如省、縣等)組成的機(jī)構(gòu)中，每區(qū)代表的數(shù)量按照人口比例分配，進(jìn)行投票選舉和表決時(shí)，每區(qū)的全體代表投相同的票.,每區(qū)各派一位代表(投

21、票人)，按照他們所代表的各區(qū)人口比例賦予投票的權(quán)重.,如何度量每位代表的投票對(duì)最終結(jié)果的影響力(權(quán)力).,介紹兩種合理的、度量權(quán)力的數(shù)量指標(biāo). 通過(guò)實(shí)例給出它們的應(yīng)用. 調(diào)整投票人的權(quán)重使其權(quán)力大致與代表的人口成比例.,加權(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.,按簡(jiǎn)單多數(shù)規(guī)則(權(quán)重之和超過(guò)總權(quán)重一半)決定投票結(jié)果.,將A區(qū)分成人口相等的3個(gè)子區(qū)A1，A2，A3,每區(qū)代表的投票權(quán)重為4，4，4，4，2，1，1,決定投票結(jié)果

22、的區(qū)域集合：A1，A2，A3 ，A1, A2, B, A1, A3, C, D, A1, B, C, E , A1, A3, B, D ， ,A區(qū)代表是獨(dú)裁者(能決定投票結(jié)果), 其他代表都是傀儡.,改革,加權(quán)投票與獲勝聯(lián)盟,加權(quán)投票系統(tǒng),投票人集合N=A，B，C, (n人),權(quán)重w1, w2, ，wn,定額q 投贊成票的投票人權(quán)重之和 q時(shí)決議通過(guò).,w=w1+ w2,+wn，一般 w/2qw,對(duì)簡(jiǎn)單多數(shù)規(guī)則且權(quán)重取整數(shù)，q為大于w/2的最小整數(shù),S=q: w1, w2, ，wn,獲勝聯(lián)盟 權(quán)重之和定額q的投票人子集.,極小獲勝聯(lián)盟如果沒(méi)有它的一個(gè)真子集也是獲勝聯(lián)盟.,獲勝聯(lián)盟集W,極小獲勝

23、聯(lián)盟集Wm,加權(quán)投票與獲勝聯(lián)盟,例2 某系一委員會(huì)由主任A 、教授B 、學(xué)生C組成，投票權(quán)重為w1, w2, w3.,幾種加權(quán)投票系統(tǒng)：,S(1)=3: 3, 1, 1,Wm=(A),極小獲勝聯(lián)盟集Wm,A是獨(dú)裁者, B,C是傀儡,S(2)=2: 1, 1, 1,Wm=(AB, AC, BC),A,B,C權(quán)力相同,S(3)=4: 2, 2, 1,Wm=(AB),S(4)=3: 2, 1, 1,Wm=(AB ,AC),A,B權(quán)力相同,C是傀儡,B,C權(quán)力相同,A有否決權(quán),Wm=(AB ,AC),5: 3, 2, 2 , ,S與Wm或W的關(guān)系參看習(xí)題,加權(quán)投票與獲勝聯(lián)盟,每個(gè)投票人的投票對(duì)結(jié)果的影

24、響不直接依賴于他的權(quán)重.,每個(gè)投票人對(duì)結(jié)果的影響才是他的權(quán)力最重要的度量.,(相對(duì))權(quán)力指標(biāo)為k =(k1, k2, k3),S(1)=3: 3, 1, 1,Wm=(A),S(2)=2: 1, 1, 1,Wm=(AB, AC, BC),S(3)=4: 2, 2, 1,Wm=(AB),S(4)=3: 2, 1, 1,Wm=(AB ,AC),k(1) =(1, 0, 0 ),k(2)=(1, 1, 1 ),k(3)=(1, 1, 0 ),k(4)=,例2 某系一委員會(huì)由主任A 、教授B 、學(xué)生C組成，投票權(quán)重為w1, w2, w3.,(?, 1, 1 ),尋找公平、合理的度量投票人權(quán)力的數(shù)量指標(biāo).

25、,權(quán)力指標(biāo)（Power index）,S=q: w1, w2, ，wn,G=(N, W),度量投票人權(quán)力的數(shù)量指標(biāo)應(yīng)該具有的性質(zhì)：,1. 每個(gè)投票人i 有一個(gè)非負(fù)實(shí)數(shù)ki作為他的權(quán)力指標(biāo).,2. 當(dāng)且僅當(dāng) (i是傀儡)時(shí)ki=0.,4. 當(dāng)投票人i和j在W中“對(duì)稱”時(shí)ki=kj.,5. 歸一化 (不是必須).,滿足這些性質(zhì)的數(shù)量指標(biāo)并不唯一.,Shapley權(quán)力指標(biāo),Banzhaf 權(quán)力指標(biāo),3. 若權(quán)重wiwj, 則kikj.,Shapley權(quán)力指標(biāo),S(4)=3: 2, 1, 1,例2,3位投票人的全排列: ABC, ACB, BAC, BCA, CAB, CBA,主任A,教授B,學(xué)生C的

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

27、=(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),Shapley權(quán)力指標(biāo),例3 某股份公司4個(gè)股東分別持有40%, 30%, 20%, 10%的股份, 公司的決策需經(jīng)持有半數(shù)以上股份的股東的同意才可通過(guò), 求4個(gè)股東在公司決策中的Shapley指標(biāo).,4個(gè)股東A,B,C,D的加權(quán)投票系統(tǒng) S=6: 4，3，2，1,A,B,C,D 有4!=24個(gè)全排列，找出決定者，下劃?rùn)M線：,決定者次數(shù)=(10, 6, 6, 2),=(5/12, 3/12, 3/12, 1/12),Wm=(AB ,AC, BCD）,

28、B和C對(duì)稱, 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,保留B在C之前的12個(gè)排列統(tǒng)計(jì)A,B(C),D為決定者的次數(shù).,簡(jiǎn)化,Banzhaf 權(quán)力指標(biāo),S(4)=3: 2, 1, 1,例2,Shapley指標(biāo)=(4/6, 1/6, 1/6),W=(AB ,AC, ABC）,獲勝聯(lián)盟,AB: 由于A的加入才成為獲勝聯(lián)盟,由于B的加入才成為獲勝聯(lián)盟,AC: 由于A的加入才成為獲勝聯(lián)盟,由于C的加

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

30、ABCD,=（5，3，3，1）,=(5/12, 3/12, 3/12, 1/12),=(5/12, 3/12, 3/12, 1/12),Banzhaf 指標(biāo),Shapley指標(biāo),投票人的全排列,對(duì)排列由左向右檢查決定者,統(tǒng)計(jì)每人在所有排列中的決定者次數(shù),投票人的獲勝聯(lián)盟集,對(duì)獲勝聯(lián)盟檢查決定者,統(tǒng)計(jì)每人在所有獲勝聯(lián)盟中的決定者次數(shù),每個(gè)排列中有且只有一個(gè)決定者,每個(gè)組合中沒(méi)有或有(幾個(gè))決定者,(=/ n!) 已歸一化,需歸一化才得到,都滿足度量權(quán)力的數(shù)量指標(biāo)應(yīng)該具有的性質(zhì).,加權(quán)投票與權(quán)力指標(biāo)的應(yīng)用,例4 拳擊比賽設(shè)2個(gè)5人裁判組, 每人一票. 若第1組以5:0 或4:1判選手甲勝, 則甲勝

31、; 若以3:2判甲勝, 則第2組再判; 除非第2組以0:5或1:4判甲負(fù), 其他情況最終都判甲勝.,將以上裁判規(guī)則用加權(quán)投票系統(tǒng)表示; 計(jì)算系統(tǒng)的Shapley指標(biāo)和Banzhaf指標(biāo).,設(shè)兩組10人同時(shí)裁判, 組成N=A, A, A, A, A, B, B, B, B, B,極小獲勝聯(lián)盟Wm =,3A2B ,S=q: a, a, a, a, a, 1, 1, 1, 1, 1,(4A ,2A4B),第1組5人權(quán)重各2, 第2組人權(quán)重各1, 按簡(jiǎn)單多數(shù)規(guī)則執(zhí)行.,例4,極小獲勝聯(lián)盟Wm =,3A2B ,(4A ,2A4B),一個(gè)B在所有排列中的決定者次數(shù)/ 10！,(3A1B)B(2A3B),(

32、2A3B)B(3A1B),一個(gè)A的Shapley指標(biāo),=(0.1365, , 0.1365, 0.0635, , 0.0635),計(jì)算S=8: 2, 2, 2, 2, 2, 1, 1, 1, 1, 1 的Shapley指標(biāo),一個(gè)B的 Shapley指標(biāo),只需考察,例4,計(jì)算S=8: 2, 2, 2, 2, 2, 1, 1, 1, 1, 1 的Banzhaf指標(biāo),考察A，B可能成為決定者的那些獲勝聯(lián)盟類型和個(gè)數(shù),A為決定者的次數(shù)與B為決定者的次數(shù)之比 840:400,=(0.1355, , 0.1355, 0.0645, , 0.0645),=(0.1365, , 0.1365, 0.0635,

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

34、0.375,通過(guò)黨派結(jié)盟能加強(qiáng)權(quán)力嗎?,2. “民主黨”(M)11 位議員結(jié)盟系統(tǒng)S(2) =21;11,1,1,例5 “團(tuán)結(jié)就是力量”嗎？,計(jì)算M,M= 11/30=0.367,在余下的1-11/30=19/30中G和D的Shapley指標(biāo)按照14:15分配,G= (19/30)*(14/29)=0.306,D=0.327,對(duì)比 S(1)=21;1,1,1 :M=0.275, G=0.350,D=0.375,“民主黨“結(jié)盟使M增加 , G,D減少.,例5 “團(tuán)結(jié)就是力量”嗎？,3. “共和黨”14位議員也結(jié)盟, 系統(tǒng)S(3) =21;11,14,1,1,G (j 7),(i, j)對(duì)應(yīng)左下方

35、方格,共272個(gè)(除對(duì)角線).,對(duì)角線以下方格 G在M之前加入,數(shù)決定者方格: M49, G100, D123,M=49/272=0.180 G= 100/272=0.368 D=0.452,例5 “團(tuán)結(jié)就是力量”嗎？,不論”民主黨”是否結(jié)盟，”共和黨”結(jié)盟總比單干好.,“共和黨”一旦結(jié)盟，”民主黨”不結(jié)盟更好.,從”民主黨”角度看, 應(yīng)該盡量保持大家都是單干的局面, 若率先結(jié)盟會(huì)誘使”共和黨”也結(jié)盟, 結(jié)果會(huì)敗得很慘.,從獨(dú)立人士角度看, 若只有”民主黨”或”共和黨”結(jié)盟自己都有損失, 但若兩個(gè)黨均結(jié)盟, 反而可得漁翁之利 .,兩種權(quán)力指標(biāo)的公理化,Shapley指標(biāo)1954年提出, 197

36、5年公理化.,Banzhaf指標(biāo)1965年提出, 1979年公理化.,投票人集合I=1, 2, , n, 投票系統(tǒng)S=q: w1, w2, ，wn,Banzhaf 指標(biāo),Shapley指標(biāo),I的任一子集S對(duì)應(yīng)一個(gè)實(shí)值、單調(diào)函數(shù)v, 若S為獲勝聯(lián)盟v(S)=1, 否則v(S)=0. 若i在S中是決定者,兩種權(quán)力指標(biāo)的公理化,公理化Bz是/2n-1, 未歸一化, =(3/4,1/4,1/4),稱絕對(duì)Banzhaf指標(biāo), 通常比更能反映投票人權(quán)力的真實(shí)性.,用公理化公式計(jì)算例2 S(4)=3: 2, 1, 1的指標(biāo)Sh和Bz,與定義得到的=(4/6, 1/6, 1/6), =(3/5, 1/5, 1/5) 比較.,兩種權(quán)力指標(biāo)的概率解釋,投票人對(duì)結(jié)果的影響力 投票人能左右結(jié)果的概率.,例2 S(4)=3: 2, 1, 1,RA 事件“A能左右結(jié)果”,可解釋為在各位投票人獨(dú)立地、以1/2的概率投贊成或反對(duì)票的條件下, 每位投票人能左右結(jié)果的概率.,Banzhaf 指標(biāo),兩種權(quán)力指標(biāo)的概率解釋,例2 S(4)=3: 2, 1, 1,p每位投票人獨(dú)立投贊成票的概率, q=1-p投反對(duì)票概率,Shapley指標(biāo),p在0, 1均勻分布,A,