運(yùn)籌學(xué)第9章-博弈論課件

1、2022/7/25第9章 博弈論1 CONTENTS目錄2022/7/259.1 博弈的基本要素與分類9.2 完全信息靜態(tài)博弈9.3 零和博弈29.1 博弈的基本要素與分類2022/7/25何謂決策？背景什么是博弈？國際爭端：美、俄、中之間微妙的關(guān)系；敘利亞問題等最近烏克蘭危機(jī)，普京與西方國家的較量政黨競選：不同黨派的競選策略中央政府與地方政府：上有政策下有對策企業(yè)之間：價(jià)格戰(zhàn)、互聯(lián)網(wǎng)電商之爭共同之處：人或群體之間的利益沖突、對抗42022/7/25囚徒困境 52022/7/25背景囚徒困境兩個(gè)囚犯都可以做出自己的選擇：坦白抵賴警方給他們的規(guī)則：兩人都抵賴，就都會被輕判,各判一年；兩人都坦白，

2、各判8年；一方抵賴，一方坦白，坦白者無罪釋放，抵賴者重判10年62022/7/25背景囚徒困境A. W. Tucker的囚犯困境(Prisoners Dilemma)： 囚徒B-8，-80 ,-10-10, 0-1，-1囚徒A 坦白抵賴坦白抵賴72022/7/25背景囚徒困境說明了什么在（坦白、坦白）這個(gè)組合中，兩囚徒和都不能通過單方面的改變行動(dòng)增加自己的收益，于是誰也沒有動(dòng)力游離這個(gè)組合，因此這個(gè)組合是納什均衡，也叫非合作均衡。82022/7/25背景囚徒困境的意義“囚徒的兩難選擇”有著廣泛而深刻的意義。個(gè)人理性與集體理性的沖突，各人追求利己行為而導(dǎo)致的最終結(jié)局是一個(gè)“納什均衡”，也是對所有

3、人都不利的結(jié)局。92022/7/25背景對經(jīng)典經(jīng)濟(jì)學(xué)的沖擊古典經(jīng)濟(jì)學(xué)的創(chuàng)始人亞當(dāng)斯密曾經(jīng)描述，市場機(jī)制這只“看不見的手”，會引導(dǎo)人們自利的行為促進(jìn)社會的福利。博弈論的“囚徒困境”卻揭示，非合作的自利行為可能導(dǎo)致兩敗俱傷的情景。 102022/7/25背景現(xiàn)實(shí)中的“囚徒困境”見義勇為者常常孤立無緣；我國的應(yīng)試教育制度下，學(xué)生的負(fù)擔(dān)、家長的焦慮；軍備競賽價(jià)格大戰(zhàn)（曾經(jīng)的家電大戰(zhàn)、民航大戰(zhàn)、牛奶業(yè)大戰(zhàn)）112022/7/25背景Elements of Game Theory 參與人一個(gè)博弈中的決策主體，他的目的是通過選擇行動(dòng)（或策略）以最大化自己的效用。參與人可能是自然人，也可能是團(tuán)體，如企業(yè)，國家

4、等。重要的是：每個(gè)參與人必須有可供選擇的行動(dòng)和一個(gè)很好定義的偏好函數(shù)。不做決策的被動(dòng)主體只能被當(dāng)作環(huán)境參數(shù)。122022/7/25背景行動(dòng) Action or Moves參與人在博弈的某個(gè)時(shí)點(diǎn)的行動(dòng)選擇。如囚徒困境中囚徒的行動(dòng)選擇集合坦白,抵賴N個(gè)參與人的行動(dòng)的有序集稱為行動(dòng)組合例如：（坦白，坦白），（坦白，抵賴）132022/7/25背景囚徒困境的例子A. W. Tucker的囚犯困境(Prisoners Dilemma)： 囚徒 B-8，-80 ,-10-10, 0-1，-1囚徒 A 坦白抵賴坦白抵賴142022/7/25背景支付payoff在一個(gè)特定的策略組合下參與人得到的確定效用水平，

5、或是指參與人得到的期望效用水平。均衡equilibrium指所有參與人的最優(yōu)策略形成的組合。152022/7/25背景策略strategies參與人在給定信息集的情況下的行動(dòng)規(guī)則，它規(guī)定參與人在什么時(shí)候選擇什么行動(dòng)。策略與行動(dòng)：策略是行動(dòng)的規(guī)則而不是行動(dòng)本身。在靜態(tài)博弈中，策略和行動(dòng)是相同的。策略必須是完備的，要給出參與人在每一種可想象得到的情況下的行動(dòng)選擇。162022/7/25背景行動(dòng)的順序(sequence order)對于博弈的結(jié)果非常重要。有關(guān)靜態(tài)和動(dòng)態(tài)博弈的區(qū)分就是基于行動(dòng)的順序做出的。同樣的行動(dòng)集合，行動(dòng)的順序不同，每個(gè)參與人的最優(yōu)決策就不同，博弈的結(jié)果也不同。尤其在不完全信息博

6、弈中，后行動(dòng)者依賴觀察先行動(dòng)者的行動(dòng)來獲取信息。172022/7/25背景開發(fā)不開發(fā)開發(fā)不開發(fā)開發(fā)不開發(fā)開發(fā)商A開發(fā)商B (-3, -3) (1, 0) ( 0, 1) (0,0) 行動(dòng)的順序(sequence order)182022/7/25背景開發(fā)不開發(fā)開發(fā)不開發(fā)開發(fā)不開發(fā) (-3, -3) (1, 0) ( 0, 1) (0,0) 開發(fā)商A開發(fā)商B開發(fā)商A策略空間開發(fā)，不開發(fā)開發(fā)商B策略空間不開發(fā),開發(fā)，開發(fā),不開發(fā)，開發(fā),開發(fā)，不開發(fā),不開發(fā)行動(dòng)的順序(sequence order)192022/7/25背景信息 information參與人有關(guān)博弈的知識，特別是有關(guān)自然的選擇，其他

7、參與人的特征和行動(dòng)的知識。202022/7/25背景信息與博弈知己知彼，百戰(zhàn)不殆。信息在博弈中發(fā)揮著重要的作用。冷戰(zhàn)時(shí)期，美國與蘇聯(lián)的間諜戰(zhàn)已眾所周知，驅(qū)逐間諜和交換間諜也是常有的事情。蘇聯(lián)解體后，俄羅斯與美國之間的冷戰(zhàn)結(jié)束，然而間諜戰(zhàn)并沒有因此而消失。早在2000多年前我國著名的孫子兵法中就強(qiáng)調(diào)了間諜的作用。在第13篇用間篇中討論了間諜的種類、作用及用法。 212022/7/25背景信息與博弈田忌賽馬之所以成功，得益于對對手的賽馬信息了如指掌。 完全信息的博弈“上當(dāng)?shù)墓哦獭?不完全信息博弈222022/7/25背景順序和信息博弈論非常強(qiáng)調(diào)時(shí)間和信息的重要性，認(rèn)為時(shí)間和信息是影響博弈均衡的主

8、要因素。在博弈過程中，參與者之間的信息傳遞決定了其行動(dòng)空間和最優(yōu)策略的選擇；同時(shí)參與人的行動(dòng)次序(Sequence Order）對博弈最后的均衡有直接的影響。232022/7/25背景博弈的分類 博弈論根據(jù)其所采用的假設(shè)不同而分為合作博弈理論和非合作博弈理論。兩者的區(qū)別在于參與人在博弈過程中是否能夠達(dá)成一個(gè)具有約束力的協(xié)議 (binding agreement)。倘若不能，則稱非合作博弈Non-cooperative game。 合作博弈強(qiáng)調(diào)的是集體主義，團(tuán)體理性 Collective Rationality，是效率、公平、公正。 242022/7/25背景非合作博弈 而非合作博弈則主要研究人

9、們在利益相互影響的局勢中如何選擇策略使得自己的收益最大，強(qiáng)調(diào)個(gè)人理性、個(gè)人最優(yōu)決策，其結(jié)果則不一定是有效率的。本課程主要介紹非合作博弈，也就是各方在給定的約束條件下如何追求各自利益最大化，最后達(dá)到力量均衡。 252022/7/25背景博弈的分類及對應(yīng)的均衡靜態(tài)動(dòng)態(tài)完全信息完全信息靜態(tài)博弈納什均衡；Nash(1950)完全信息動(dòng)態(tài)博弈子博弈精煉納什均衡；澤爾騰（1965）不完全信息不完全信息靜態(tài)博弈貝葉斯納什均衡；海薩尼（1967-1968）不完全信息動(dòng)態(tài)博弈精煉貝葉斯納什均衡；澤爾騰（1975）Kreps,Wilson(1982),Fudenberg,Tirole(1991)行動(dòng)的順序信息26

10、2022/7/25背景博弈論的理論意義博弈論對于社會科學(xué)有著重要的意義，它正成為社會科學(xué)研究范式中的一種核心工具，以至于我們可稱博弈論是“社會科學(xué)的數(shù)學(xué)”，或者說是關(guān)于社會的數(shù)學(xué)。從理論上講，博弈論是研究理性的行動(dòng)者（agents）相互作用的形式理論，而實(shí)際上它正深入到經(jīng)濟(jì)學(xué)、政治學(xué)、社會學(xué)等等，被各門社會科學(xué)所應(yīng)用。272022/7/25背景博弈論與經(jīng)濟(jì)學(xué)博弈論進(jìn)入主流經(jīng)濟(jì)學(xué)，反映了經(jīng)濟(jì)學(xué)發(fā)展的幾個(gè)趨勢：經(jīng)濟(jì)學(xué)研究的對象越來越轉(zhuǎn)向個(gè)體；經(jīng)濟(jì)學(xué)越來越轉(zhuǎn)向人與人關(guān)系的研究;經(jīng)濟(jì)學(xué)越來越重視對信息的研究,特別是信息不對稱對個(gè)人選擇及制度安排的影響。282022/7/25背景 1994 The pr

11、ize was awarded jointly to John Harsanyi, John F. Nash and Reinhard Selten for their pioneering analysis of equilibria in the theory of non-cooperative games.292022/7/25背景 1996 The prize was awarded jointly to James A. Mirrless and William Vickery for their pioneering analysis ofInformation Economic

12、s （不對稱信息條件下激勵(lì)機(jī)制問題）302022/7/25背景 2001 The prize was awarded jointly to Jeorge Akerlof（阿克洛夫）、Michael Spence（斯賓塞）and Joseph Stiglitz（斯蒂格利茨） for their pioneering analysis of非對稱信息市場分析方面杰出貢獻(xiàn) 312022/7/25背景The prize was awarded jointly to Thomas C. Schelling (謝林） Robert Aumann （奧曼）The two worked independent

13、ly to apply game theory to social and political problems. 2005 322022/7/25背景 要想在現(xiàn)代社會做一個(gè)有文化的人，你必須對博弈論有一個(gè)大致了解。著名經(jīng)濟(jì)學(xué)家保羅薩繆爾森332022/7/25背景為什么要學(xué)習(xí)博弈論博弈論告訴人們，要學(xué)會理解他人都有自己的思想，每個(gè)個(gè)體都是理性的，所以必須了解競爭對手的思想。但博弈論并不是療法，并不是處方。博弈論可以解釋經(jīng)濟(jì)中許多低效率現(xiàn)象的根源，找出導(dǎo)致低效率的制度原因，從而幫助政府制訂、修改政策完善交易制度和提高經(jīng)濟(jì)效率。349.2 完全信息靜態(tài)博弈2022/7/25背景9.2.1 博弈的

14、策略式表述Normal (Strategic) Form Representation 完全信息靜態(tài)博弈標(biāo)準(zhǔn)式描述G = S1,S2,Sn; u1,u2,un.N = Set of players (2 Prisoners)Si = Set of pure strategies of player i (Prisoner 1 can confess (C) or dont confess (D).ui = payoff function of player i (u1(C; c) = -8).Set of strategy profiles: S1 S2 Sn =In prisoners di

15、lemma (PD) game, one strategy profile is (C; c).362022/7/25背景 智豬博弈每次按出10個(gè)蘿卜，按者付出2個(gè)單位成本。小豬按，大豬先到，支付（收益）（9，1）；大豬按，小豬先到，支付（收益）（6，4）同時(shí)按，支付（收益）（7，3） 5，14，49，-10，0大豬按 等待 按等待小豬372022/7/25背景實(shí)際生活中的智豬博弈搭便車北約內(nèi)部，美國承擔(dān)了防務(wù)開支很大比例的份額，大大便宜了西歐和日本。美國經(jīng)濟(jì)學(xué)家曼庫爾.奧爾森將這一現(xiàn)象稱為“小國對大國的剝削” “當(dāng)家的不鬧事”公共物品，窮人和富人修路博弈（中產(chǎn)階級對社會的穩(wěn)定作用）；大企業(yè)大

16、投入做廣告，小企業(yè)花精力模仿;大股東對管理者的監(jiān)督。382022/7/25背景智豬博弈與企業(yè)策略在實(shí)力懸殊公司之間的價(jià)格競爭策略也是這個(gè)道理。如果公司是弱小的一方，則可以選擇如下策略：（蒙牛、東星航空）首先是等待，靜觀其變。允許市場上占主導(dǎo)地位的品牌開拓本行業(yè)所有產(chǎn)品的市場需求。將自己的品牌定位在較低價(jià)格上，以享受主導(dǎo)品牌的強(qiáng)大廣告所帶來的市場機(jī)會。其次是不要貪婪，妄圖將“大豬”應(yīng)得的那份也據(jù)為己有。只要主導(dǎo)品牌認(rèn)為弱小公司不會對自己形成威脅，它就會不斷創(chuàng)造市場需求。392022/7/25背景智豬博弈與企業(yè)策略如果公司是“智豬博弈”中的大豬，在行業(yè)市場中占主導(dǎo)地位，則可采取以下策略：首先要接受

17、小公司。作為主導(dǎo)品牌，加強(qiáng)廣告宣傳，創(chuàng)造和開拓對行業(yè)所有產(chǎn)品的市場需求才是真正的利益所在。不要采取降價(jià)這種浪費(fèi)資源的做法與小企業(yè)競爭，除非它對公司形成了真正的威脅。正是小企業(yè)采取的低價(jià)格阻止了潛在進(jìn)入者的涌入。402022/7/25背景9.2.2 博弈的均衡分析（1）占優(yōu)策略不論其他參與人選擇什么策略，它的最優(yōu)策略是唯一的，這樣的最優(yōu)策略被稱為（嚴(yán)格）占優(yōu)策略。412022/7/25背景A Normal Form GamePlayer 2Player 112,1111,1214,1311,1010,1112,1210,1510,1313,14422022/7/25背景The OutcomeTh

18、is outcome is called a Nash equilibrium:“a” is player 1s best response to “C”.“C” is player 2s best response to “a”.Player 2Player 112,1111,1214,1311,1010,1112,1210,1510,1313,14432022/7/25背景Key InsightsLook for dominant strategies When a game has a strictly dominant strategy, expect a rational playe

19、r to choose it.Put yourself in your rivals shoes442022/7/25背景（2）Dominated Strategy(劣策略)10 , 1025 , 2020 , 3015 , 25 Here, player II has a third option - to give his product away for free. No matter what player I does, player II is better off with another strategy. This is hence a dominated strategy.

20、RightMiddleUpdownPLAYER IPLAYER II15 , 1530 , 20Left452022/7/25背景Elimination of Strictly Dominated StrategiesA player has a strictly dominated strategy if there is one action/strategy which always provides a lower payoff than another strategy, no matter what other players do.If you cross off (除去）all

21、 strictly dominated strategies, sometimes you are left with only NE.462022/7/25背景Repeated elimination can find the NE472022/7/25背景Nash 均衡占優(yōu)均衡重復(fù)剔除劣策略的均衡Elimination of Strictly Dominated Strategies482022/7/25背景Sometimes there arent dominated strategies so you have to check for NE cell by cell Eliminat

22、ion of Strictly Dominated Strategies492022/7/25背景（3）Nash均衡Formally, a strategy profile forms a NE , if for every player i, ui(si*, s-i*) ui(si, s-i*), for any siWhat is equilibrium? Equilibrium is a strategy combination where no one player has an incentive to change her /his strategy given the strat

23、egies of the other players.502022/7/25背景囚徒困境的例子A. W. Tucker的囚犯困境(Prisoners Dilemma)： 囚徒B-8，-80 ,-10-10, 0-1，-1囚徒A 坦白抵賴坦白抵賴512022/7/25背景9.2.3 策略式博弈的納什均衡求解方法（1）求解有限策略博弈的分析方法劃線法箭頭法522022/7/25背景(1)求解有限策略博弈的分析方法劃線法的基本思路：每一位參與者先找出自己針對其他參與人的每種策略或策略組合（對多人博弈）的最佳策略，最后互為最優(yōu)策略的組合即為均衡。532022/7/25背景劃線法-8 , -80 , -

24、10-1,-1Dont confessConfessDont confessConfessPrisoner BPrisoner A-10 , 0(1)求解有限策略博弈的分析方法542022/7/25左中右上1, 0 2, 30, 2下0, 31, 12, 0Player 1Player 2(1)求解有限策略博弈的分析方法552022/7/25箭頭法的基本思路： 是對博弈中的每一個(gè)策略組合進(jìn)行分析，考察在每一個(gè)策略組合處各個(gè)博弈方能否通過單獨(dú)改變自己的策略而增加收益，直到得到的策略組合只有指向的箭頭，沒有指離的箭頭，即為均衡。(1)求解有限策略博弈的分析方法562022/7/25箭頭法-8 ,

25、-80 , -10-1,-1Dont confessConfessDont confessConfessPrisoner BPrisoner A-10 , 0(1)求解有限策略博弈的分析方法572022/7/25(2)求解無限策略博弈的分析方法Cournot duopoly寡頭競爭模型在庫諾特模型里，有兩個(gè)參與人，分別為企業(yè)1和企業(yè)2，他們生產(chǎn)并銷售同一種產(chǎn)品，同時(shí)分別決定生產(chǎn)的產(chǎn)量，以追求各自利潤或效用最大化。 該博弈中企業(yè) 的策略是選擇產(chǎn)量 。企業(yè) 的效用函數(shù)就是其利潤函數(shù)，分別表示為其中 表示企業(yè) 的生產(chǎn)成本； 表示產(chǎn)品的市場價(jià)格，是與兩個(gè)企業(yè)的產(chǎn)量相關(guān)的函數(shù)。582022/7/25Co

26、urnot duopoly寡頭競爭模型為簡單起見，令 ，其中 企業(yè)1和企業(yè)2 的最優(yōu)策略選擇問題可分別表示為求解如下的優(yōu)化問題：而求解最優(yōu)解的方法是對每家企業(yè)的利潤函數(shù)求一階導(dǎo)數(shù)，并令其等于零，即一階條件，我們稱這個(gè)一階條件的解為企業(yè)1(或2)對企業(yè)2(或1)的策略的反應(yīng)函數(shù)(reaction function)。592022/7/25根據(jù)上式，不難求出企業(yè)1和企業(yè)2的反應(yīng)函數(shù)分別為：上述兩個(gè)反應(yīng)函數(shù)的交點(diǎn)其實(shí)就是該博弈的納什均衡解 。Cournot duopoly寡頭競爭模型602022/7/25Cournot duopoly寡頭競爭模型612022/7/25那也就是說，均衡點(diǎn) 即為兩個(gè)反應(yīng)

27、函數(shù)組成的方程組的解，求解該方程組即得Cournot duopoly寡頭競爭模型622022/7/25思考如果兩個(gè)企業(yè)之間的博弈不是靜態(tài)的，企業(yè)1先選擇，即是Leader；而企業(yè)2后行動(dòng)，即是follower，會有什么博弈結(jié)果？632022/7/259.2.4 混合策略納什均衡及其求解Soccer Penalty Kicks-1 , 1 1 , -1 1 , -1-1 , 1G O A L I EL RKICKER L R642022/7/25社會福利問題政府與流浪漢之間的博弈政府的策略選擇：救濟(jì)，不救濟(jì)流浪漢的策略選擇：找工作，游蕩3 , 2-1 , 30, 0游蕩找工作不救濟(jì)救濟(jì)流浪漢政府

28、-1 , 1非零和博弈652022/7/25分析類似的問題還有許多：如門衛(wèi)與小偷，偷稅與查稅等。以上例子都有一個(gè)共同的特征：每個(gè)參與人都想猜透對方的策略，同時(shí)又不想讓對方猜透自己的策略。這類問題都不存在原來意義上的Nash均衡，因此有必要拓展Nash均衡的定義。662022/7/25案例分析以猜硬幣為例蓋幣者：蓋幣者要使猜幣者不能準(zhǔn)確猜中自己的策略，只有以隨機(jī)的方式出招；設(shè)蓋幣者出正面的概率為x,則出反面的概率為1-x;必須選擇出正面和反面的概率，使猜者不論猜正面或反面，其期望收益是相同的。猜幣者：猜正面的期望收益：x+(1-x)(-1)猜反面的期望收益：x(-1)+(1-x) x+(1-x)

29、(-1)= x (-1)+(1-x) x*=1/2672022/7/25案例分析同理，若設(shè)猜幣者猜正面的概率為y,則在均衡時(shí)，其概率為：y*=1/2在該例中，假設(shè)了每個(gè)參與人在其策略空間上，有一概率分布,如蓋幣者x,1-x,猜幣者y,1-y,其均衡為： （1/2，1/2，1/2，1/2）682022/7/25混合策略 Mixed strategy純策略（pure strategy)： 如果一個(gè)策略規(guī)定參與人在每一個(gè)給定的信息情況下只選擇一種特定的行動(dòng)，稱為純策略?；旌喜呗裕?如果一個(gè)策略規(guī)定參與人在給定的信息情況下以某種概率分布隨機(jī)地選擇不同的行動(dòng)，稱為混合策略。692022/7/25混合策略

30、 Mixed strategy定義： 在博弈G=S1,S2,Sn;u1,u2,un中，參與人i的策略空間為Si=si1,si2,sik,若 是參與人 i選擇策略 sij的概率，且有: 則稱 是參與人i的一個(gè)混合策略。702022/7/25混合策略組合用 表示參與人的混合策略空間； 稱為一個(gè)混合策略組合；期望效用函數(shù)：712022/7/25混合策略Nash均衡定義： 是一個(gè)混合策略Nash均衡，若對所有參與人i，有722022/7/25混合策略納什均衡的求解方法支付（效用）最大化法支付（效用）等值法739.3 零和博弈2022/7/259.3.1 基本概念零和博弈（Zero-Sum game)設(shè)

31、有兩個(gè)局中人（參與人）參與人1有m個(gè)策略S1=a1,a2,am參與人2 有n個(gè)策略S2 =b1,b2,bn對任一策略組合（ai,bj),參與人1得到aij，參與人2得到- aij記A為參與人1的贏得矩陣（收益矩陣）；而參與人2的贏得矩陣為-A。二人零和博弈G=S1,S2; A)752022/7/25Zero-sum game （零和博弈）762022/7/25另一種分析視角對每一個(gè)參與人，分析自己的每一個(gè)策略下，最壞的結(jié)果(意味著對對方最有利的結(jié)果），然后從中確定一個(gè)最好的結(jié)果，對應(yīng)的策略即為自己的最佳策略772022/7/25零和博弈例：782022/7/25結(jié)果分析參與人1按最大最小原則參

32、與人2按最小最大原則minj maxi aij = maxi minj aij =ai*j*=2 maxi minj aij minj maxi aij792022/7/259.3.2 矩陣博弈的純策略納什均衡均衡（解）定義設(shè)G(S1,S2;A)為一個(gè)矩陣對策（博弈），其中S1=a1,a2,am, S2 =b1,b2,bn, A=(aij)mxn. 若 minj maxi aij = maxi minj aij 則稱使上式成立的純策略組合（ai*,bj*)為博弈G的均衡（解）。802022/7/25求解812022/7/25判別定理零和博弈均衡存在的判別定理: 零和博弈G=S1,S2;A存在純

33、策略的充分必要條件是，對任意的，i=1,.m, j=1,.,n,有： ai*j* 稱為矩陣A的鞍點(diǎn)822022/7/25零和博弈均衡的性質(zhì)性質(zhì)1 （無差別性） 若 （ai1,bj1)和（ai2,bj2),是博弈G的兩個(gè)解（均衡），則有ai1j1=ai2j2性質(zhì)2 (可交換性) 若（ai1,bj1)和（ai2,bj2),是博弈G的兩個(gè)解（均衡），則（ai1,bj2)和（ai2,bj1)也是博弈G的均衡。832022/7/25Sometimes there arent any NEZero-sum game （零和博弈）842022/7/259.3.3 矩陣博弈的混合策略納什均衡零和博弈的混合策略

34、及其均衡設(shè)有兩個(gè)局中人（參與人）參與人1有m個(gè)純策略S1=a1,a2,am 混合策略用x=（ x1,x2,xm）表示參與人2 有n個(gè)純策略S2 =b1,b2,bn 混合策略用y=（ y1,y2,ym）表示記A為參與人1的贏得矩陣（收益矩陣）；而參與人2的贏得矩陣為-A。852022/7/25零和博弈的混合策略博弈G=S1,S2; A)862022/7/25零和博弈的混合策略局中人1的贏得函數(shù)：872022/7/25零和博弈的混合策略均衡定義：混合策略均衡滿足以下條件： 882022/7/25零和博弈的混合策略均衡定理：零和博弈G在混合策略意義下有解的充分必要條件：存在x*,y*,使對任意的x,

35、 y有：892022/7/25零和博弈的混合策略均衡定理：零和博弈G在混合策略意義下有解的充分必要條件：存在x*,y*,使對任意的i=1,2,m; j=1,2,n 有：902022/7/259.3.4 矩陣博弈的求解如果設(shè) , ，則參與人1的期望收益可表示為： 或定理9. 6 是矩陣博弈 的混合策略納什均衡解的充要條件是：定理9. 7 任一矩陣博弈 都一定存在混合策略意義下的納什均衡解。 912022/7/25定理9.7的證明是構(gòu)造性的，不僅證明了矩陣對策解的存在性，同時(shí)也給出了矩陣對策的一般求解方法，即線性規(guī)劃方法。矩陣對策的求解可轉(zhuǎn)化為求解互為對偶的線性規(guī)劃問題P)和D)。只要在問題P)中

36、，做適當(dāng)變換，即令：則問題P)等價(jià)于如下線性規(guī)劃問題P：9.3.4 矩陣博弈的求解922022/7/25同理，只要令： ,則問題D)等價(jià)于如下線性規(guī)劃問題D：顯然，問題P)和D)是互為對偶的線性規(guī)劃，可通過單純形法求解。然后再通過上述變換的逆變換，即可求得原對策問題的解。9.3.4 矩陣博弈的求解932022/7/25例9.5利用線性規(guī)劃方法求解矩陣對策 ，其中：解：該矩陣對策的最優(yōu)解可轉(zhuǎn)化為求解兩個(gè)互為對偶的線性規(guī)劃問題如下：P) D)9.3.4 矩陣博弈的求解942022/7/25求解線性規(guī)劃P)和D)得：所以，該對策問題的解為：9.3.4 矩陣博弈的求解952022/7/25除了利用線性

37、規(guī)劃法求解矩陣對策，還可使用方程組法，該方法的使用應(yīng)歸功于矩陣對策解的如下性質(zhì)，即定理9.8。定理9. 8設(shè) 是矩陣博弈 的解, 則有：1) 若 ，則 ；而若 ，則 。2) 若 ，則 ；而若 ，則 。定理9. 8表明，當(dāng)矩陣對策的最優(yōu)策略中的 和 均不為零時(shí)，矩陣對策的最優(yōu)解可轉(zhuǎn)化為求解如下兩個(gè)方程組：1) 2)9.3.4 矩陣博弈的求解962022/7/25例9.6試用方程組法求解矩陣對策“田忌賽馬”:戰(zhàn)國時(shí)齊王與其大將田忌賽馬，雙方約定各出上、中 、下 3個(gè)等級的馬各一匹進(jìn)行比賽，共賽馬3次，每次比賽的勝者贏得敗者 一百金。已知在同一等級馬的比賽中，齊王的馬可穩(wěn)操勝券，但田忌的上、中等級的

38、馬分別可勝齊王的中、下等級的馬。 解： 田忌與齊王在排列賽馬出場順序時(shí)，可分別選擇 6種策略，即包括: (上，中，下 )，(中，上，下 )，(下，中，上 )，(上，下，中 )，(中，下，上 )，(下，上，中 )，則齊王的 贏得矩陣為：9.3.4 矩陣博弈的求解972022/7/25易知，A沒有鞍點(diǎn)，即對齊王和田忌來說都不存在最優(yōu)純策略，不妨設(shè)齊王和田忌的最優(yōu)混合策略分別為從矩陣A的元素來看，每個(gè)局中人選擇其策略集中的任一策略的可能性都是存在的，所以可事先假定9.3.4 矩陣博弈的求解982022/7/25于是，該矩陣對策的最優(yōu)解可轉(zhuǎn)化為求解如下兩個(gè)方程組： I) II)9.3.4 矩陣博弈的求

39、解992022/7/25解得 。所以，齊王和田忌的最優(yōu)混合策略分別為：需要注意的是，該方法由于事先假定 和 均不為零，所以當(dāng)對策解 的某些分量為零時(shí)，上述方程組1)和2)可能無解。因此，該方法具有一定的局限性。但對于 2*2對策，即局中人I的贏得矩陣為：9.3.4 矩陣博弈的求解1002022/7/25如果A沒有鞍點(diǎn)，則該對策存在最優(yōu)混合策略，且容易證明：各局中人的最優(yōu)混合策略中 和 均大于零。于是，最優(yōu)混合策略等價(jià)于求解如下方程組1)和2)： 1) 2) 上述方程組1)和2)存在嚴(yán)格的非負(fù)解，即：9.3.4 矩陣博弈的求解1012022/7/25例9.7 設(shè) 對策的贏得矩陣為：求該對策的最優(yōu)

40、策略和值。解：根據(jù)定義易知，A沒有鞍點(diǎn)。所以，由上述公式直接可計(jì)算該對策的最優(yōu)策略和值分別為：9.3.4 矩陣博弈的求解1022022/7/25根據(jù)定理9.8，除了線性方程組法和2*2對策的公式法，還可用圖解法求解矩陣對策，下面主要介紹 2*N對策的圖解法如下：1) 在直角坐標(biāo)系中作直線I: ;II: 。2) 在直線I處按矩陣第二行的值標(biāo)縱坐標(biāo)，在直線II處按矩陣第一行的值標(biāo)縱坐標(biāo)。其意義是當(dāng)局中人I采用其中一個(gè)純策略時(shí)，局中人II各策略相對應(yīng)的贏得值。3) 按列的方向?qū)⒏鲗?yīng)的縱坐標(biāo)值連成直線。4) 令 ，即局中人I的混合策略，按最小最大原則在圖中確定局中人I的最優(yōu)策略。具體方法是：讓 x在(0,1) 內(nèi)變動(dòng)，找出經(jīng)過點(diǎn)(x,0) 的垂線與上述直線交點(diǎn)中縱坐標(biāo)最小的點(diǎn)集，然后再從中找出縱坐標(biāo)最大的點(diǎn)P所對應(yīng)的橫坐標(biāo)即為所求。9.3.4 矩陣博弈的求解1032022/7/255) 確定經(jīng)過點(diǎn)P的兩條相交直線，根據(jù)兩條相交直線列出對應(yīng)的方程組，求出x* 。6) 根據(jù)定理9.8，計(jì)算出y*的值。9.3.4 矩陣博弈的求解1042022/7/25例9.8 試用圖解法求解矩陣對策 ,其中：解：該對策沒有鞍點(diǎn)，設(shè)局中人I的混合策略為 , 。過數(shù)軸上坐標(biāo)原點(diǎn)和(1,0)點(diǎn)分別作兩條垂線I-I和II-II，垂線上