用計算機軟件解決博弈論問題

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

2、件解決博弈論 問題。我們會與書本知識緊密結(jié)合，有興趣的同學(xué)請先把課本準(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)代人如何運用仿真軟件解決博弈論問題，實現(xiàn)預(yù)測未來、智勝 對手的目的，甚至改

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

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

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

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

7、進”等。我們首先把博弈用雙矩陣表示出來: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的支付（贏得）矩陣，axn為局中人B的支付（贏得）矩陣。J mxn則矩陣博弈可以記為：G=A,B;S17S2,Ca,Cb或 G=S1,S2,CA,CB若存在策略對x g S1, y g S使得廠一.一. .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則稱(x,y)為g在混合策略納什均衡。其中純策略為混合策略的特殊情況。這里的表達式與書中P83的寫法實質(zhì)上是一樣的，只是采用了矩陣的語言而已。而用計算機求解納什均衡常用的Lemke-Howson算法主要運用下述定理:cAy xTCAy,i -1,2,m I J J-1cbx xTCByj - 1,2,，nij i、i=1是納什均衡解的充分必要條件。Lemke-Howson算法主要用于解決數(shù)學(xué)中的

9、線性規(guī)劃問題，用Lemke-Howson 算法把博弈論問題表達成線性規(guī)劃問題，然后就可以很容易用計算機軟件求解。 這里我們不展開介紹Lemke-Howson算法，將目光集中在軟件應(yīng)用方面。三、應(yīng)用計算機軟件解決博弈論常見問題通過Lemke-Howson算法，博弈問題就可以轉(zhuǎn)化為線性優(yōu)化問題，能夠用 Lingo軟件進行求解。首先介紹博弈論中不能不提的問題，比如P7囚徒困境問題：乙坦白 抵賴坦白(-3,-3)(0,-5)甲抵賴(-5,0)(-1,-1)我們可以在Lingo上進行編程：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為概率空間的上下分割點，可以自由設(shè)置。乙獵鹿打兔獵鹿(10,10)(0,4)甲打兔(0,4)(4,4)例如我們在獵鹿博弈中把獵人甲獵鹿的概率分割為10等份，

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

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