用計(jì)算機(jī)軟件解決博弈論問(wèn)題

1、博弈論與信息經(jīng)濟(jì)學(xué)課堂展示用計(jì)算機(jī)軟件解決博弈論問(wèn)題我們首先來(lái)回顧一下今天要交的作業(yè)題P124#3-7。題目如下：乙紅 黑八、紅(3,1) (0,0)甲黑(0,0) (1,4)我想在座各位應(yīng)該可以很輕松地解決這道問(wèn)題，利用反應(yīng)函數(shù)可以求得Nash均衡解：(0,1)，(0,1)(0.8,0.2)，(0.25,0.75)(1,0)，(1,0)但是當(dāng)矩陣階數(shù)很大時(shí)，或是博弈參與人很多時(shí)，這一類(lèi)問(wèn)題幾乎不能通過(guò) 人工求解，怎么辦？我們可以通過(guò)計(jì)算機(jī)軟件來(lái)幫助自己學(xué)習(xí)博弈論知識(shí)，解決 博弈論問(wèn)題。比如上題可以在Gambit軟件中進(jìn)行求解。今天我們的Presentation的主題即是簡(jiǎn)單介紹如何用計(jì)算機(jī)軟

2、件解決博弈論 問(wèn)題。我們會(huì)與書(shū)本知識(shí)緊密結(jié)合，有興趣的同學(xué)請(qǐng)先把課本準(zhǔn)備在手。一、現(xiàn)代博弈論軟件的應(yīng)用( HYPERLINK /node/21527025 /node/21527025)在2011年9月3日的Economist雜志上發(fā)表了一篇文章題為：Game theory in practiceComputing: Software that models human behaviour can make forecasts, outfox rivals and transform negotiations文中介紹了現(xiàn)代人如何運(yùn)用仿真軟件解決博弈論問(wèn)題，實(shí)現(xiàn)預(yù)測(cè)未來(lái)、智勝 對(duì)手的目的，甚至改

3、變了人們的談判方式。因博弈論經(jīng)濟(jì)學(xué)著作而獲得2005年 諾貝爾獎(jiǎng)的耶路撒冷希伯來(lái)大學(xué)學(xué)者Robert Aumann表示，事實(shí)證明模擬軟件應(yīng) 用于拍賣(mài)尤其成功。比如說(shuō)，以色列政府幾年前曾經(jīng)在一次煉油設(shè)備拍賣(mài)會(huì)上采 用了一個(gè)新花樣。為了鼓勵(lì)更多更高的出價(jià)，以色列政府為喊價(jià)第二高的競(jìng)價(jià)者 設(shè)立了 1200萬(wàn)美元的獎(jiǎng)勵(lì)。這是個(gè)昂貴的錯(cuò)誤。軟件分析結(jié)果顯示，倘若沒(méi)有 這份嘉獎(jiǎng)，最高競(jìng)價(jià)會(huì)比實(shí)際最高出價(jià)高出1200萬(wàn)美元。競(jìng)逐者們選擇出低價(jià) 因?yàn)檩數(shù)舻娜丝梢钥开?jiǎng)金發(fā)一筆橫財(cái)。這筆失去的價(jià)值加上付出的獎(jiǎng)勵(lì)，以色列 政府的損失共計(jì)約2400萬(wàn)美元。后來(lái)人們就得出這樣的結(jié)論:“dont presume you

4、know what the solution is” without help from modelling software 沒(méi)有模擬軟件 的幫助，“永遠(yuǎn)別自以為知道解決問(wèn)題的辦法”(Brad Miller)。當(dāng)然人們并不需要 100%依賴(lài)于軟件。希伯來(lái)大學(xué)的一個(gè)學(xué)生用筆答方式證出了以色列政府的2400 萬(wàn)美元損失。但該大學(xué)的一名教授稱(chēng)，這位學(xué)生花了大約兩天時(shí)間才做出證明。除了拍賣(mài)外，博弈論還有很多實(shí)際應(yīng)用：預(yù)測(cè)未來(lái)政府變革，軍事影響等戰(zhàn)勝對(duì)手法律問(wèn)題，商品競(jìng)拍，公司并購(gòu)等轉(zhuǎn)變談判方式電腦談判，公共品定價(jià)等加州蒙特利海軍研究生院的Guillermo Owen表示，博弈論軟件對(duì)于發(fā)現(xiàn) 本拉登在

5、巴基斯坦藏身于阿伯塔巴德起到了重要作用。洛杉磯加州大學(xué)的博弈 論學(xué)者Barry O Neill描述了怎樣通過(guò)軟件來(lái)協(xié)助離婚協(xié)議過(guò)程。( HYPERLINK /econport/request?page=web_or_list&categoryID= /econport/request?page=web or list&categoryID= 2#27通過(guò)網(wǎng)絡(luò)我們可以了解一些常用的博弈論仿真軟件 Trade Network Game (TNG)、Extensive Form Game Applet、Gambit、Game Theory Simulation Software、 Normal Fo

6、rm Game Applet，我們稍后會(huì)介紹Gambit的應(yīng)用，但在介紹前我們要 理解這些軟件應(yīng)用的原理。二、博弈論軟件應(yīng)用的原理博弈論，又稱(chēng)為對(duì)策論或賽局理論，它不僅是經(jīng)濟(jì)學(xué)的分支，更是現(xiàn)代數(shù)學(xué) 的一個(gè)分支，運(yùn)籌學(xué)中的重要組成部分。國(guó)內(nèi)外的很多學(xué)者都曾經(jīng)用專(zhuān)門(mén)的數(shù)學(xué) 軟件Mathematical Matlab、Lingo來(lái)研究如何求解博弈論問(wèn)題，如趙東方2005 年發(fā)表“運(yùn)用Mathematica軟件包求解2人矩陣對(duì)策”，洪俊田、趙東方2006年 發(fā)表“運(yùn)用Lingo軟件包求解雙矩陣對(duì)策的方法”，以及郭雷、高作峰、蘇微微、 馬穎2007年發(fā)表“運(yùn)用Matlab程序求解雙矩陣對(duì)策的一般方法及改

7、進(jìn)”等。我們首先把博弈用雙矩陣表示出來(lái):B1同 Bnai(CA,CB) (CA,CB)(CA,CB )111112121n1na (ca , CB) (CA , CB )(ca , CB )2212122222n 2nam(ca , cb ) (ca , cb )(ca , cb )mm1 m1m2 m2mn mnCa - ca）為局中人A的支付（贏(yíng)得）矩陣，axn為局中人B的支付（贏(yíng)得）矩陣。J mxn則矩陣博弈可以記為：G=A,B;S17S2,Ca,Cb或 G=S1,S2,CA,CB若存在策略對(duì)x g S1, y g S使得廠(chǎng)一.一. .xTCAy xTCAy, Vx g S1?、XTCB

8、y xTCBy, Vy g S2其中x -(X, x2,xm)s.t 咒 x. -1,0 x. 1,1 i mi-1y - (y1, y2,yn)s.t 咒 yJ = 1,0 yJ 1,1 J nj-1則稱(chēng)(x,y)為g在混合策略納什均衡。其中純策略為混合策略的特殊情況。這里的表達(dá)式與書(shū)中P83的寫(xiě)法實(shí)質(zhì)上是一樣的，只是采用了矩陣的語(yǔ)言而已。而用計(jì)算機(jī)求解納什均衡常用的Lemke-Howson算法主要運(yùn)用下述定理:cAy xTCAy,i -1,2,m I J J-1cbx xTCByj - 1,2,，nij i、i=1是納什均衡解的充分必要條件。Lemke-Howson算法主要用于解決數(shù)學(xué)中的

9、線(xiàn)性規(guī)劃問(wèn)題，用Lemke-Howson 算法把博弈論問(wèn)題表達(dá)成線(xiàn)性規(guī)劃問(wèn)題，然后就可以很容易用計(jì)算機(jī)軟件求解。 這里我們不展開(kāi)介紹Lemke-Howson算法，將目光集中在軟件應(yīng)用方面。三、應(yīng)用計(jì)算機(jī)軟件解決博弈論常見(jiàn)問(wèn)題通過(guò)Lemke-Howson算法，博弈問(wèn)題就可以轉(zhuǎn)化為線(xiàn)性?xún)?yōu)化問(wèn)題，能夠用 Lingo軟件進(jìn)行求解。首先介紹博弈論中不能不提的問(wèn)題，比如P7囚徒困境問(wèn)題：乙坦白 抵賴(lài)坦白(-3,-3)(0,-5)甲抵賴(lài)(-5,0)(-1,-1)我們可以在Lingo上進(jìn)行編程：sets:optA/1.2/: x;optB/1.2/: y;AXB(optA,optB) : Ca, Cb;end

10、setsdata:Ca = -3 0-5 -1;Cb = -3 -50 -1;enddataVa=sum(AXB(i,j): Ca(i,j)*x(i)*y(j);Vb=sum(AXB(i,j): Cb(i,j)*x(i)*y(j);for(optA(i):sum(optB(j) : Ca(i,j)*y(j)=Va);for(optB(j):sum(optA(i) : Cb(i,j)*x(i)u);for(optA(i):x(1)v);u、v為概率空間的上下分割點(diǎn)，可以自由設(shè)置。乙獵鹿打兔獵鹿(10,10)(0,4)甲打兔(0,4)(4,4)例如我們?cè)讷C鹿博弈中把獵人甲獵鹿的概率分割為10等份，

11、每一份為0.1， 并分別運(yùn)行程序解得區(qū)間Nash均衡解0Wx1W0.1x=(0,1),y=(0,1)0.1Wx1W0.2無(wú)解0.2Wx1W0.3無(wú)解0.3Wx1W0.4x=(0.4,0.6),y=(0.4,0.6)0.4Wx1W0.50.5Wx1W0.6無(wú)解0.6Wx1W0.7無(wú)解0.7Wx1W0.8無(wú)解0.8Wx1W0.9無(wú)解0.9Wx1W1x=(1,0),y=(1,0)由此我們求出了獵鹿博弈的全部Nash均衡。盡管通過(guò)概率空間的分割可以 把Nash均衡逐個(gè)找出，但因?yàn)檫@種分割具有主觀(guān)性，在有些時(shí)候并不能做到面 面俱到，況且這種簡(jiǎn)單重復(fù)勞動(dòng)也不是我們所希望的。四、應(yīng)用博弈論專(zhuān)業(yè)軟件解決博弈論

12、常見(jiàn)問(wèn)題必須強(qiáng)調(diào)的是這些數(shù)學(xué)軟件并非博弈論專(zhuān)業(yè)軟件，并不能完美地解答博弈論 問(wèn)題，這里的“不能”當(dāng)然是指還有待一些專(zhuān)家學(xué)者去開(kāi)發(fā)新的應(yīng)用。為了更好 地利用計(jì)算機(jī)，我們專(zhuān)門(mén)介紹一款博弈論專(zhuān)門(mén)軟件Gambit。Gambit相比前面提到的軟件，其優(yōu)勢(shì)在于無(wú)須另外編程，而且用戶(hù)界面非 常直觀(guān)。例如我們用Gambit可以直接求解P48情侶博弈的Nash均衡。麗娟足球 芭蕾足球(2,1)(0,0)大海芭蕾(-1,-1)(1,2)這里的操作顯然比反應(yīng)函數(shù)法計(jì)算要快。而且，作為專(zhuān)業(yè)的博弈軟件，它還 可以處理我們筆算不了的高維情形和多個(gè)局中人的博弈。例如P91高維情形BLRT(3,4)(2,2)A M(1,1)(2,1)B(0,0)(0,1)以及P116多人博弈乙丙A LRU(0,0,10)(-5,-5,0)甲D(-5,-5,0)(1,1,-5)乙丙BLRU(-2,-2,0)(-5,-5,0)甲D(-5,-5,0)(-1,-1,5)這里需要指出Gambit作為簡(jiǎn)單的博弈論軟件還有很多缺陷，比如不能處理 無(wú)數(shù)個(gè)解的博弈論問(wèn)題，這是就需要更高級(jí)的仿真軟件來(lái)模擬博弈中人的行為。五、結(jié)束盡管計(jì)算機(jī)方法可以替代人工處理繁瑣的計(jì)算，但是