第九章 運(yùn)籌學(xué)博弈論

第九章博弈論引言完全信息靜態(tài)博弈(有鞍點(diǎn)的博弈,混合策略,納什均衡)完全信息靜態(tài)博弈(非零和的情況,納什均衡)教學(xué)目的與要求:理解具有競爭性問題的博弈思想,對納什均衡概念有初步的認(rèn)識,掌握矩陣博弈的求解方法.重點(diǎn)與難點(diǎn):有鞍點(diǎn)的靜態(tài)博弈和無鞍點(diǎn)的靜態(tài)博弈,難點(diǎn)是納什均衡的概念.教學(xué)方法:通過大量的實(shí)例講解相關(guān)概念和解法,并進(jìn)行課堂討論.思考題,討論題,作業(yè):兩個課堂討論題,本章習(xí)題.參考資料:見前言.學(xué)時分配:6學(xué)時.引言§1.在社會活動,經(jīng)濟(jì)和經(jīng)濟(jì)管理,軍事活動中,經(jīng)常會遇到具有競爭性或利益相對抗的現(xiàn)象,例如下棋,打橋牌,體育競賽,市場競爭,廣告戰(zhàn),價格戰(zhàn),軍事斗爭等.競爭的各方總是想用最好的策略擊敗對方,取得盡可能好的結(jié)果,這就是博弈現(xiàn)象.博弈現(xiàn)象是一種特殊的決策,在不確定決策分析中,決策者的對手是”大自然”,它對決策者的各種策略不產(chǎn)生反應(yīng),但在博弈現(xiàn)象中,代替”大自然”的是”有理性的人”,因而任何一方做出的決定都必須充分考慮其他對手可能作出的反應(yīng).早期的博弈實(shí)例是中國春秋戰(zhàn)國時代的齊王和田忌賽馬的故事:齊王有上,中,下三等馬,他麾下的大將也有上,中,下三等馬,但是同等級的馬都比齊王差一些.賽馬時齊王表示按上,中,下的順序出馬,而田忌的謀士讓他按下,上,中的順序出馬,比賽結(jié)果田忌贏了一千金.請思考:這是一種什么類型的博弈?理論上齊王不會輸,但他為什么輸了?在國外,1912年E.Zermelo用集合論研究過下棋問題,四十年代由于生產(chǎn)和戰(zhàn)爭的需要,博弈理論得到了發(fā)展,系統(tǒng)博弈理論的形成則以1944年V.Neumann,O.Morgensten合著的《博弈論和經(jīng)濟(jì)行為》一書為標(biāo)志.1994年瑞士皇家科學(xué)院決定將諾貝爾經(jīng)濟(jì)學(xué)獎授予納什(Nash),哈薩尼(Harsanyi)和澤爾騰(Selten)三人,表彰他們在博弈理論和應(yīng)用研究方面作出的杰出貢獻(xiàn).目前,博弈論在定價,招投標(biāo),拍賣,委托代理以及很多重要的經(jīng)營決策中得到應(yīng)用,它已成為現(xiàn)代經(jīng)濟(jì)學(xué)的重要基礎(chǔ).約翰·納什（JOHNF.NASH）美國人(1928-)，由于他與另外兩位數(shù)學(xué)家在非合作博弈的均衡分析理論方面做出了開創(chuàng)性的貢獻(xiàn)，對博弈論和經(jīng)濟(jì)學(xué)產(chǎn)生了重大影響，而獲得1994年諾貝爾經(jīng)濟(jì)獎。約翰·海薩尼（JOHNC.HARSANYI）美國人，由于他與另外兩位數(shù)學(xué)家在非合作博弈的均衡分析理論方面做出了開創(chuàng)性的貢獻(xiàn)，對博弈論和經(jīng)濟(jì)學(xué)產(chǎn)生了重大影響，由此獲得諾貝爾經(jīng)學(xué)獎。

約翰·納什

1928年生于美國約翰·海薩尼

1920年生于美國

萊因哈德·澤爾騰

1930年生于德國

三人在非合作博弈的均衡分析理論方面做出了開創(chuàng)性貢獻(xiàn)對博弈論和經(jīng)濟(jì)學(xué)產(chǎn)生了重大影響

瑞典諾貝爾基金會官方網(wǎng)站透露了近20年諾貝爾經(jīng)濟(jì)學(xué)獎得主名單及其主要貢獻(xiàn)(即獲獎理由)：

2004年挪威經(jīng)濟(jì)學(xué)家芬恩-基德蘭德(FinnE.Kydland)和美國經(jīng)濟(jì)學(xué)家愛德華-普雷斯科特(EdwardC.Prescott)

獲獎理由：在動態(tài)宏觀經(jīng)濟(jì)學(xué)方面做出了巨大貢獻(xiàn)。

2003年美國經(jīng)濟(jì)學(xué)家羅伯特-恩格爾(RobertF.EngleIII)和英國經(jīng)濟(jì)學(xué)家克萊夫-格蘭杰(CliveW.J.Granger)

獲獎理由：在經(jīng)濟(jì)時間數(shù)列中運(yùn)用了統(tǒng)計學(xué)的方法。

2002年美國學(xué)者丹尼爾-卡尼曼(DanielKahneman)和弗農(nóng)-史密斯(VernonL.Smith)

獲獎理由：在心理和實(shí)驗(yàn)經(jīng)濟(jì)學(xué)研究方面做出了開創(chuàng)性工作。

2001年三位美國學(xué)者喬治-阿克爾洛夫(GeorgeA.Akerlof)、邁克爾-斯彭斯(A.MichaelSpence)和約瑟夫-斯蒂格利茨(JosephE.Stiglitz)

獲獎理由：在“對充滿不對稱信息市場進(jìn)行分析”領(lǐng)域做出了重要貢獻(xiàn)。

2000年美國芝加哥大學(xué)的詹姆斯-赫克曼(JamesJ.Heckman)和加州大學(xué)伯克利分校的丹尼爾-麥克法登(DanielL.McFadden)

獲獎理由：在微觀計量經(jīng)濟(jì)學(xué)領(lǐng)域做出了重大貢獻(xiàn)。

1999年加拿大著名經(jīng)濟(jì)學(xué)家羅伯特-蒙代爾教授(RobertA.Mundell)

獲獎理由：對不同匯率體制下的貨幣和財政政策以及最優(yōu)貨幣區(qū)域的分析做出了偉大貢獻(xiàn)。

1998年印度籍經(jīng)濟(jì)學(xué)家阿馬蒂亞-森(AmartyaSen)

獲獎理由：對福利經(jīng)濟(jì)學(xué)以及發(fā)展經(jīng)濟(jì)學(xué)做出了突破性貢獻(xiàn)。

1997年美國經(jīng)濟(jì)學(xué)家邁倫-斯科爾斯(MyronS.Scholes)和羅伯特-默頓(RobertC.Merton)

獲獎理由：前者給出了著名的布萊克-斯科爾斯期權(quán)定價公式，該法則已成為金融機(jī)構(gòu)涉及金融新產(chǎn)品的思想方法；后者對布萊克-斯科爾斯公式所依賴的假設(shè)條件做了進(jìn)一步減弱，在許多方面對其做了推廣。

1996年英國人(JamesA.Mirrlees)和美國人威廉-維克瑞(WilliamVickrey)

獲獎理由：前者在信息經(jīng)濟(jì)學(xué)理論領(lǐng)域做出了重大貢獻(xiàn)，尤其是不對稱信息條件下的經(jīng)濟(jì)激勵理論的論述；后者在信息經(jīng)濟(jì)學(xué)、激勵理論、博弈論等方面都做出了重大貢獻(xiàn)。

1995年美國人羅伯特-盧卡斯(RobertE.LucasJr.)

獲獎理由：倡導(dǎo)和發(fā)展了理性預(yù)期與宏觀經(jīng)濟(jì)學(xué)研究的運(yùn)用理論，深化了人們對經(jīng)濟(jì)政策的理解，并對經(jīng)濟(jì)周期理論提出了獨(dú)到的見解。

1994年美國人約翰-海薩尼(JohnC.Harsanyi)和美國人約翰-納什(JohnF.NashJr.)以及德國人萊因哈德-澤爾騰(ReinhardSelten)

獲獎理由：在非合作博弈的均衡分析理論方面做出了開創(chuàng)性的貢獻(xiàn)，對博弈論和經(jīng)濟(jì)學(xué)產(chǎn)生了重大影響。

1993年美國人羅伯特-福格爾(RobertW.Fogel)和道格拉斯-諾斯(DouglassC.North)

獲獎理由：前者用經(jīng)濟(jì)史的新理論及數(shù)理工具重新詮釋了過去的經(jīng)濟(jì)發(fā)展過程；后者建立了包括產(chǎn)權(quán)理論、國家理論和意識形態(tài)理論在內(nèi)的“制度變遷理論”。

1992年美國人加里-貝克(GaryS.Becker)

獲獎理由：揭示并澄清了經(jīng)濟(jì)制度結(jié)構(gòu)和函數(shù)中交易費(fèi)用和產(chǎn)權(quán)的重要性。

1990年美國人哈里-馬科維茨(HarryM.Markowitz)、默頓-米勒(MertonH.Miller)和威廉-夏普(WilliamF.Sharpe)

獲獎理由：在金融經(jīng)濟(jì)學(xué)方面做出了開創(chuàng)性工作。

1989年挪威人特里夫-哈維默(TrygveHaavelmo)

獲獎理由：建立了現(xiàn)代經(jīng)濟(jì)計量學(xué)的基礎(chǔ)性指導(dǎo)原則。

1988年法國人莫里斯-阿萊斯(MauriceAllais)

獲獎理由：在市場理論及資源有效利用方面做出了開創(chuàng)性貢獻(xiàn)，并對一般均衡理論重新做了系統(tǒng)闡述。

1987年美國人羅伯特-索洛(RobertM.Solow)

獲獎理由：對增長理論做出貢獻(xiàn)。提出長期的經(jīng)濟(jì)增長主要依靠技術(shù)進(jìn)步，而不是依靠資本和勞動力的投入。

1986年美國人詹姆斯-布坎南(JamesM.BuchananJr.)

獲獎理由：將政治決策的分析同經(jīng)濟(jì)理論結(jié)合起來，使經(jīng)濟(jì)分析擴(kuò)大和應(yīng)用到社會,政治法規(guī)的選擇

1985年意大利人弗蘭科-莫迪利安尼(FrancoModigliani)

獲獎理由：第一個提出儲蓄的生命周期假設(shè)，這一假設(shè)在研究家庭和企業(yè)儲蓄中得到了廣泛應(yīng)用。什么是博弈論?所謂博弈是指局中人按一定規(guī)則,在充分考慮其他局中人可能采取的策略的基礎(chǔ)上,從自己的策略集中選取相應(yīng)策略,并從中得到回報的過程.博弈是一種特殊的決策,在決策論中,決策者的對手是大自然,在博弈論中,代替大自然的是有理性的人,因而任何一方做出決定時,都必須考慮其他對手可能作出的反應(yīng).構(gòu)成博弈的三個要素:1.局中人(Players):是指參與競爭的各方,它可以是一個人,也可以是一個集團(tuán),但局中人必須是有決策權(quán)的主體,而不是參謀或從屬人員.在博弈中局中人可以有兩方,稱為二人博弈;也可以有多方,稱為多人博弈,在多人博弈中又可分為結(jié)盟和不結(jié)盟的情況.2.策略(Strategies):指局中人所擁有的對付其他局中人的手段,方案的集合.在靜態(tài)博弈中,策略必須是一個獨(dú)立的完整的行動,而不能是若干相關(guān)行動中的某一步.例如在齊王和田忌賽馬的博弈中,雙方都有六個策略:(上,中,下),(上,下,中),(中,上,下),(中,下,上),(下,中,上),(下,上,中),這六個策略形成一個策略集合.在一局對策中,局中人的策略只有有限個,稱為有限策略,否則為無限策略.相應(yīng)每個局中人的策略選擇形成的策略組稱為一個局勢.3.收益函數(shù)(Payofffunction):指一局博弈后各局中人的輸贏得失,用正的數(shù)字表示局中人的贏得,負(fù)的數(shù)字表示局中人的損失.顯然,收益函數(shù)的取值與局中人選定的策略有關(guān),于是一局博弈的”得失”是”局勢”的函數(shù).博弈論的研究建立在下述假設(shè)前提下:即參與博弈的各局中人都是理性的.對”理性”的理解:”理性人是指有一個很好定義的偏好,在面臨給定的約束條件下最大化自己的偏好.”“博弈中一個理性的決策必定建立在預(yù)測其他局中人的反應(yīng)之上.一個局中人將自己置身于其他局中人的位置并為他著想從而預(yù)測其他局中人將選擇的行為,在這個基礎(chǔ)上該局中人決定自己最理想的行動.”博弈的三個要素,即局中人,策略集和收益函數(shù)構(gòu)成了博弈信息,根據(jù)不同信息可對博弈做如下分類:1.按局中人對信息掌握情況分為:完全信息博弈和不完全信息博弈;2.按局中人采取行動的次序分為:如果同時采取行動或在互相保密情況下采取行動,稱為靜態(tài)博弈;如果采取行動有先后,后采取行動的人可以觀察到前面人采取的行動,稱為動態(tài)博弈.我們只研究完全信息靜態(tài)博弈.§2.完全信息靜態(tài)博弈(一)設(shè)博弈中只有局中人A,B;局中人A的策略集為

局中人B的策略集為完全信息是指所有局中人對其他局中人各自策略集以及不同局勢下的收益函數(shù)都有完全的了解.一.二人零和博弈博弈的三個要素的矩陣表示(局中人A的收益)

局中人B局中人A策略策略局中人A的收益函數(shù)可用如下的矩陣表示:二人零和博弈也稱為矩陣博弈.博弈可表為例1寫出”石頭,剪子,布”游戲的收益矩陣.石頭贏剪刀1分,布贏石頭1分,剪刀贏布1分.解:甲的策略集為{石頭,布,剪刀}乙的策略集為{石頭,布,剪刀}乙甲石頭布剪刀石頭布剪刀0-1110-1-110例2寫出齊王和田忌賽馬中齊王的收益矩陣.贏一場得一千金.解:田忌齊王二.具有鞍點(diǎn)的博弈通過下面的例3說明,什么是局中人的最優(yōu)純策略,如何求出這個純策略以及博弈解和博弈值的概念.乙甲博弈過程的描述:從收益表中可知,甲方的最大收益是19,他當(dāng)然希望得到這個值,于是甲使用策略對付乙.但是乙方已估計到甲方的心理而使用策略對付甲,使他不但得不到19,反而要輸?shù)?2.此時甲也估計到乙方的心理,使用策略,使乙得不到12反而輸?shù)?.當(dāng)甲方使用策略時,乙方使用任何策略都要輸,當(dāng)然他希望輸?shù)纳僖恍?因此乙方只能使用策略,這時甲贏得2,乙輸?shù)?,達(dá)到了平衡,博弈結(jié)束.我們注意到,博弈論是研究有理智的局中人在每一個局勢下采取的行動.他們在選擇策略時,要考慮到對方總是采取對自己最不利的策略來對抗.基于這一原則,最優(yōu)策略不是冒險性的結(jié)果,而是審慎的留有余地的周密安排.如果雙方都不存在冒險心理,為了達(dá)到最佳結(jié)局,甲必須計算他的每個策略與乙的各策略博弈后的結(jié)果,從而求出使用每個策略帶來的最壞收益,再從這些最壞收益中選出一個最大收益值,這個值對應(yīng)的行策略就是甲方的最優(yōu)純策略.同樣乙方應(yīng)從收益表中每列找出最大正數(shù)(恰為乙方輸?shù)舻臄?shù)值),為了減少損失,應(yīng)從這些數(shù)字中求出最小數(shù),它所對應(yīng)的列策略為乙方的最優(yōu)純策略.計算過程如下:幾點(diǎn)說明:1.在有鞍點(diǎn)的矩陣博弈中,鞍點(diǎn)可以不唯一.例如2.策略的優(yōu)超性.策略的優(yōu)超性的定義:說明:這種做法可能會丟掉一些最優(yōu)解,但不會影響博弈的結(jié)論,如果上面的不等式有嚴(yán)格不等式,就不會出現(xiàn)丟解的現(xiàn)象了.利用策略的優(yōu)超性化簡下面的矩陣博弈,并求出局中人的最優(yōu)純策略和博弈值.3.有鞍點(diǎn)的博弈是少數(shù)情況,大量的博弈問題不存在鞍點(diǎn),齊王的收益矩陣就不存在鞍點(diǎn).博弈問題的實(shí)例1:百貨商店的選址問題.假設(shè)有一條街道,居民對各種日用品的需求是均勻的,為一個常數(shù),且愿意就近購買.現(xiàn)有兩家百貨商店,分別想沿街道選定自己的位置,問如何選址對雙方最有利(將街道看成一條曲線).博弈問題的實(shí)例2:某城市由匯合的三條河分割為三個區(qū),城市居民中40%住在A區(qū),30%住在B區(qū),30%住在C區(qū).現(xiàn)有甲,乙兩公司要在市內(nèi)修建超級市場,甲公司建兩個,乙公司建一個.每個公司都知道,如果在一個區(qū)內(nèi)建兩個超市,則兩個市場平分該區(qū)業(yè)務(wù),如果某區(qū)建一個超市,則獨(dú)攬?jiān)搮^(qū)業(yè)務(wù),若某區(qū)無超市其業(yè)務(wù)平均分散在三個超市中,每個公司都想把超市建在營業(yè)額最多的地方.(1)將該問題表達(dá)成一個二人零和博弈,并寫出甲公司的收益矩陣;(2)甲,乙兩公司的最優(yōu)策略是什么,在兩公司都取得最優(yōu)策略時,它們各占有多大的市場份額?三.無鞍點(diǎn)矩陣博弈的混合策略1.2×2無鞍點(diǎn)矩陣博弈的特殊解法例4乙甲行最小值634834(max)列最大值68(min)該矩陣博弈顯然不存在鞍點(diǎn).對他們的博弈過程作出如下的描述:2.無鞍點(diǎn)矩陣博弈的線性規(guī)劃解法BA例5BA901001101101009012010080解:設(shè)A的混合策略為B的混合策略為解得到例6求齊王與田忌賽馬中雙方的最優(yōu)混合策略解:齊王的線性規(guī)劃為解得齊王的最優(yōu)混合策略為問題:理論上齊王應(yīng)贏得一千金,但是實(shí)際比賽中他為什么輸?shù)粢磺Ы?在無鞍點(diǎn)的矩陣博弈中,雙方采取何種純策略是應(yīng)當(dāng)保密的.3.無鞍點(diǎn)矩陣博弈的布朗(Brown)算法布朗(Brown)算法是一種近似算法,給定局中人A的收益矩陣算法步驟:1.甲方任選一行,然后乙方選擇與該行中最小元素相對應(yīng)的那一列;2.在第1步里乙方所選的列中,與最大元素相對應(yīng)的行即為甲方應(yīng)選的行;3.乙方把到目前為止甲方選擇的各行求和,并選擇與最小和元素對應(yīng)的列;4.甲方把到目前為止乙方選擇的列求和,并選擇與最大和元素對應(yīng)的行.如果要求迭代的次數(shù)已達(dá)到,轉(zhuǎn)第5步,否則轉(zhuǎn)回第3步;5.分別計算博弈值的上界和下界6.令是甲方選擇i行的次數(shù)比例;是乙方選擇j列的次數(shù)比例.分別為甲,乙的近似混合策略.例7用布朗算法求解矩陣博弈(迭代10次)1234567891013-2211632105311361557197823992711103113111234567891031475314710-21-1-303642013457911121314四.納什均衡(Nashequilibrium)納什均衡是博弈論的基礎(chǔ).在二人零和博弈中,雙方尋求的最優(yōu)解是一種均衡解,達(dá)到這種均衡時,無論是純策略解還是混合策略解,只要其他局中人不改變自己的策略,則任何一方單獨(dú)改變自己的策略只能帶來收益或效用的減少,因此這些均衡解也稱為納什均衡,換言之,納什均衡是一種策略組合,它是每個局中人的策略對其他局中人策略的最優(yōu)反應(yīng).納什證明了在任何非合作有限博弈中,都存在至少一個納什均衡.§3.完全信息靜態(tài)博弈(二)現(xiàn)在研究二人非零和博弈BA策略策略一.用劃線法求具有純策略的納什均衡例7二人博弈如下表所示BA解:先利用策略的優(yōu)超性簡化雙元矩陣.BA納什均衡是每個局中人策略對其他局中人策略的最優(yōu)反應(yīng).對于A來說,針對B分別采取策略時,A的最優(yōu)反應(yīng)分別是策略其收益值分別是5,6,4.按劃線法,在這幾個數(shù)字下分別劃一橫線;對于B來說,相對于A采取的策略,B的最優(yōu)反應(yīng)策略是,分別在對應(yīng)的收益值6,6下劃橫線.如果收益值下都有橫線,這一對值就是納什均衡解,對應(yīng)的策略組合為本題中,納什均衡解為(4,6),對應(yīng)的策略組為BA納什均衡解為(4,6),對應(yīng)的策略組為二.兩個著名的博弈例子例8囚徒困境問題:(1950年數(shù)學(xué)家塔克任美國斯坦福大學(xué)教授,在給一些心理學(xué)家講演時,對當(dāng)時正在研究的博弈問題作了形象的描述)設(shè)有甲,犯乙兩名嫌疑因同一樁罪行被捕,警方希望他們坦白并提供對方犯罪證據(jù),規(guī)定如兩人均坦白各判刑3年;如一方坦白另一方不坦白,坦白一方從輕釋放,不坦白一方判刑8年;如兩人均不坦白,由于犯罪事實(shí)證據(jù)很多不能成立,只能每人各判1年,分析甲,乙兩名犯罪嫌疑人的各自策略和納什均衡解.解:乙甲坦白不坦白坦白不坦白(-3,-3)(0,-8)(-8,0)(-1,-1)根據(jù)劃線法納什均衡解是(坦白,坦白).但是從表中明顯看出,兩名犯罪嫌疑人最好的結(jié)局是(-1,-1),即雙方均不坦白.如何理解這一矛盾的結(jié)果呢?這個例子說明,就個人利益和群體利益而言,在考慮最優(yōu)解時,出發(fā)點(diǎn)不同,結(jié)果也不同,個人的理性選擇與群體的理性選擇是不一