運(yùn)籌學(xué)對(duì)策論

運(yùn)籌學(xué)對(duì)策論第1頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月2

在日常生活中，我們經(jīng)?？吹揭恍┫嗷ブg的競(jìng)爭(zhēng)、比賽性質(zhì)的現(xiàn)象，如下棋、打撲克、體育競(jìng)賽等。

在經(jīng)濟(jì)領(lǐng)域，各國(guó)之間的貿(mào)易談判，各公司、企業(yè)之間的市場(chǎng)爭(zhēng)奪，各公司、企業(yè)之間的加工、訂貨、合作談判等等，都是競(jìng)爭(zhēng)現(xiàn)象。

在政治方面，國(guó)際上政府間的各種外交談判，各方都想在談判中處于有利地位，爭(zhēng)取到對(duì)自己有利的結(jié)果。各國(guó)之間或國(guó)內(nèi)各集團(tuán)之間的戰(zhàn)爭(zhēng)，是一種你死我活的斗爭(zhēng)，雙方都千方百計(jì)要戰(zhàn)勝對(duì)方。第2頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月3

例：兩個(gè)兒童玩的“石頭—剪子—布”游戲和我國(guó)古代的“齊王賽馬”就是典型的對(duì)策論研究的例子。

在這類(lèi)行為中，參加斗爭(zhēng)或競(jìng)爭(zhēng)的各方各自具有不同的目標(biāo)和利益，為了達(dá)到各自的目標(biāo)和利益各方必須考慮對(duì)手的各種可能的行動(dòng)方案，并力圖選取對(duì)自己最為有利或最為合理的方案，對(duì)策論就是研究對(duì)策行為中斗爭(zhēng)各方是否存在著最合理的行動(dòng)方案，以及如何找到這個(gè)合理的行動(dòng)方案的數(shù)學(xué)理論和方法。第3頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月4二、對(duì)策問(wèn)題的三個(gè)基本要素

（1）局中人：在一場(chǎng)競(jìng)賽或斗爭(zhēng)中，每一個(gè)有決策權(quán)的參與者(個(gè)人或集團(tuán))稱(chēng)為一個(gè)局中人。只有兩個(gè)局中人的對(duì)策現(xiàn)象稱(chēng)為“兩人對(duì)策”，而多于兩個(gè)局中人的對(duì)策稱(chēng)為“多人對(duì)策”。

（2）策略：一個(gè)對(duì)策中，每個(gè)局中人都有供他選擇的實(shí)際可行的完整的行動(dòng)方案，我們把一個(gè)局中人一個(gè)可行的自始至終通盤(pán)籌劃的行動(dòng)方案，稱(chēng)為這個(gè)局中人的一個(gè)策略。如果在一個(gè)對(duì)策中，每個(gè)局中人都只有有限個(gè)策略，則稱(chēng)為“有限對(duì)策問(wèn)題”，否則稱(chēng)為“無(wú)限對(duì)策問(wèn)題”。第4頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月5

（3）贏得函數(shù)（支付函數(shù)）：一局對(duì)策結(jié)束時(shí)的結(jié)果（如收入或支出）稱(chēng)為得失。每個(gè)局中人在一局對(duì)策結(jié)束時(shí)的得失，不僅與該局中人自身所選擇的策略有關(guān)，而且與全體局中人所取定的一組策略有關(guān)。所以，一局對(duì)策結(jié)束時(shí)每個(gè)局中人的“得失”是全體局中人所取定的一組策略的函數(shù)，通常稱(chēng)作贏得函數(shù)（支付函數(shù)）。把每個(gè)局中人各自所取的一個(gè)策略所組成的策略組稱(chēng)為“局勢(shì)”，于是“得失”是“局勢(shì)”的函數(shù)。第5頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月6第二節(jié)矩陣對(duì)策的基本定理

特點(diǎn)：①局中人只有兩人，分別用局中人Ⅰ和局中人Ⅱ表示，雙方都只有有限個(gè)策略可供選擇，②局中人的“得失”相加等于零，這種對(duì)策稱(chēng)為“零和對(duì)策”。在兩人有限零和對(duì)策中，局中人Ⅰ的所獲等于局中人Ⅱ的所失。假定在局勢(shì)(αi,βj)下(即局中人Ⅰ取策略αi

，局中人Ⅱ取策略βj

時(shí)所形成的局勢(shì))，局中人Ⅰ的收入或贏得是aij（“aij”是負(fù)數(shù)時(shí)，表示局中人Ⅰ是支出）。Ⅰ的策略集為：Ⅱ的策略集為：一、矩陣對(duì)策的數(shù)學(xué)模型第6頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月7

用矩陣表示為(稱(chēng)為局中人Ⅰ的贏得矩陣或局中人Ⅱ的支付矩陣):

我們稱(chēng)兩人有限零和對(duì)策為矩陣對(duì)策，記為：G＝{Ⅰ,Ⅱ；S1,S2；A}或G＝{S1，S2；A}。第7頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月8例1:設(shè)有矩陣對(duì)策，局中人Ⅱ的支付矩陣如下：

如果各局中人都不想冒險(xiǎn)，必須考慮對(duì)方會(huì)選擇策略使他得到最差的收入。因此各局中人都選擇理智的決策行為。解：

α3→α3→β1→α4→β3第8頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月9

局中人Ⅰ的各種策略的最差收入是支付陣中各種策略所對(duì)應(yīng)行的最小數(shù)。如果不存僥幸心理，他對(duì)每個(gè)策略只能期望得到最差的收入。即：

那么為了得到盡可能好的結(jié)局，只能從這些最小數(shù)之中的找最大者（最大的最小者），即選擇能在最差的可能結(jié)果中得到最好結(jié)果的策略。即：－8，2，－9，－3即選擇策略α2。第9頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月10

同樣，局中人Ⅱ的各種策略的最差收入（最大支出）是支付矩陣中各列的最大數(shù)，即：局中人Ⅱ選擇這些最大數(shù)中的最小者。即：16，2，5即選擇策略β2。Ⅰ的最優(yōu)策略為α2,Ⅱ的最優(yōu)策略為β2

。第10頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月11

定義:設(shè)G＝{S1，S2；A}為矩陣對(duì)策,其中S1＝{α1,α2,…αm}，S2＝{β1,β2,…βn}。A=(aij)m×n，若滿(mǎn)足等式：

則稱(chēng)純局勢(shì)(αi*，βj*)為G在純策略下的解（或平衡局勢(shì)）。記VG＝ai*j*，稱(chēng)VG為對(duì)策G的值,αi*，βj*分別稱(chēng)為局中人I、II的最優(yōu)純策略。

例1的對(duì)策G的解為（α2，β2），α2，β2分別是局中人I和II的最優(yōu)純策略，VG=2。

從例1中可以看出，矩陣的元素a22既是所在行的最小元素，又是所在列的最大元素，即：第11頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月12

定理1：矩陣對(duì)策A=(aij)m×n有解的充分必要條件是：存在純局勢(shì)(αi*，βj*)，使得對(duì)一切i=1,2,…,m,j=1,2,…,n均有：i=1,2,3,4；j=1,2,3

將這一事實(shí)推廣到一般矩陣對(duì)策，可得如下定理：證明：先證充分性，由于對(duì)任意i，j均有：

故：第12頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月13另一方面，對(duì)任意i，j均有：所以：于是：所以：第13頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月14再證必要性，若G有解。而對(duì)于所有的i而言，必存在一個(gè)i*使：對(duì)于所有的j而言，必存在一個(gè)j*使：因?yàn)椋河谑牵旱?4頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月15稱(chēng)滿(mǎn)足條件的(αi*,βj*)為矩陣對(duì)策G的一個(gè)鞍點(diǎn)。但：于是有：故對(duì)一切的i,j都有：

意義：如果局中人I選擇策略αi*

，局中人II不選擇策略βj*

，而選擇策略βj，則局中人II的支付只會(huì)增多。也就是說(shuō)：策略βj*是II的最優(yōu)策略。第15頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月16

注意：一個(gè)矩陣對(duì)策G如果存在鞍點(diǎn)，鞍點(diǎn)可能不止一個(gè)。但是在不同的鞍點(diǎn)處，支付值相等，都等于對(duì)策的值。（無(wú)差異性）

如果(αi,βj)以及(αk,βl)都是對(duì)策G的鞍點(diǎn)，則(αk,βj)與(αi,βl)也是該問(wèn)題的鞍點(diǎn)。（可交換性）

同樣，如果局中人II選擇策略βj*

，局中人I不選擇策略αi*

，而選擇策略αi，則局中人I的所獲只會(huì)減少。也就是說(shuō)：策略αi*是局中人I的最優(yōu)策略。第16頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月17G有四個(gè)鞍點(diǎn)：對(duì)策的值為VG＝

5。例2：給定矩陣對(duì)策G＝{S1，S2；A}，其中：第17頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月18二、矩陣對(duì)策的混合策略

矩陣對(duì)策G有鞍點(diǎn)時(shí)，就存在最優(yōu)解(最優(yōu)純策略)，但是否一切矩陣對(duì)策問(wèn)題中，各局中人都有上述意義的最優(yōu)純策略呢?答案是否定的。例1：石頭、剪刀、布不存在上述純策略意義下的解。第18頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月19

對(duì)于該例而言，直觀的看：雙方采用三個(gè)純策略的頻率均應(yīng)為1／3：1／3：1／3。由于每個(gè)局中人在一局對(duì)策中必取某個(gè)純策略，因此采取任何一個(gè)純策略的概率都應(yīng)是1／3。

一般地，設(shè)局中人I以概率x1,x2,…，xm來(lái)分別選取他的純策略α1，α2，…αm

；而局中人II以概率y1,

y2,…，yn來(lái)選用自己的純策略β1，β2，…βn

。于是：令x=(x1,x2,…，xm)T,y=(y1,y2,…，yn)T則稱(chēng)這樣的x和y為局中人I、II的混合策略。第19頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月20記：

此時(shí)，當(dāng)局中人I以概率

xi采用αi

時(shí)，局中人II以概率

yj采用

βj

時(shí)，支付aij

出現(xiàn)的概率為xi

yj

。于是局中人I收入（贏得）的期望值為：

則稱(chēng)G＊＝{S1＊，S2＊；E}為G＝{S1，S2；A}的混合擴(kuò)充。第20頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月21混合策略對(duì)策矩陣可表示如下：

混合策略問(wèn)題的解也是以最大最小化和最小最大化標(biāo)準(zhǔn)為根據(jù)的。第21頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月22

當(dāng)局中人I選擇某個(gè)混合策略

x

時(shí)，對(duì)于局中人II的任意選擇y,

I的期望所獲至少是：

于是局中人I希望選擇x，使上式最大，保證局中人I的期望所獲不小于：

這就是局中人I的最大最小化標(biāo)準(zhǔn)。

同理：當(dāng)局中人II選擇某個(gè)混合策略y

時(shí)，對(duì)于I的任意選擇x，II的期望支付至多是：

于是局中人II希望選擇

y，使上式最小，保證局中人II的期望支付不多于：這就是局中人II的最小最大化標(biāo)準(zhǔn)。第22頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月23例1：求解矩陣對(duì)策G＝{S1，S2；A}

，其中：如果令：則得問(wèn)題的最優(yōu)解。解：設(shè)X=(x,1－x)T,Y=(y,1－y)T

且對(duì)策的值為：第23頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月24另解：

（用微分求極值的方法）且對(duì)策的值為：第24頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月25

定義

:

G＊＝{S1＊,S2＊；E}為矩陣對(duì)策G＝{S1,S2；A}的混合擴(kuò)充，若存在(x*,y*)滿(mǎn)足等式：則稱(chēng)(x*,y*)為G在混合策略下的解。稱(chēng)VG＝E(x*,y*)

為對(duì)策G的值,x*,y*分別稱(chēng)為I、II的最優(yōu)混合策略。

定理2：混合策略x*和y*是G的解的充分必要條件是：對(duì)一切混合策略x,y有：稱(chēng)(x*,y*)是對(duì)策問(wèn)題在混合策略意義下的鞍點(diǎn)。第25頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月26當(dāng)局中人I

取純策略αi時(shí)，記其贏得函數(shù)為于是三、矩陣對(duì)策的基本定理當(dāng)局中人II取純策略βj時(shí)，記其贏得函數(shù)為于是第26頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月27則有：

定理3：混合策略x*和y*是G的解的充分必要條件是：對(duì)任意的i,j有：第27頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月28則證明：必要性顯然，只需證充分性，若對(duì)任意i,j均有：即：所以x*和y*是G的解。第28頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月29注意到：可以寫(xiě)成：于是定理3可以改述為：

定理4：矩陣對(duì)策G＝{S1,S2；A}有解的充要條件是存在數(shù)v，使得x,y

分別是下述兩個(gè)不等式組的解：第29頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月30

定理5：（對(duì)策基本定理）任何矩陣對(duì)策G在混合策略下一定有解。證明：由定理3，只需證明存在混合策略x*和y*，使得（3）式成立，為此考慮如下兩個(gè)線性規(guī)劃：第30頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月31容易驗(yàn)證（P）和（D）是互為對(duì)偶規(guī)劃，而且

是（P）的一個(gè)可行解，是(D)的一個(gè)可行解，由線性規(guī)劃對(duì)偶理論可知，(P)和(D)是都存在最優(yōu)解(x*，w*)

和(y*,v*)，且最優(yōu)值w*=v*，即:i=1，2,…,m,j=1，2,…,n.第31頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月32又由：可得：

定理5的證明是構(gòu)造性的證明，同時(shí)給出了求解方法。第32頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月33

定理6：設(shè)（x*，y*）是矩陣對(duì)策G解，v=VG，則第33頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月34矩陣對(duì)策G＝{S1，S2；A}。（1）若（即A中第k行的每個(gè)元素≥A中第l行的每個(gè)元素）稱(chēng)局中人I的策略αk優(yōu)超于策略αl；則可在A中去掉第l行，矩陣對(duì)策G的解不變。（2）如果：（即A中第k列的每個(gè)元素≤A中第l列的每個(gè)元素）稱(chēng)局中人II的策略βk

優(yōu)超于策略βl

。則可在A中去掉第第l列，矩陣對(duì)策G的解不變。優(yōu)超定理：第34頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月35第三節(jié)矩陣對(duì)策的求解一、2×2對(duì)策的方程法則稱(chēng)G為2×2對(duì)策。

若G沒(méi)有純策略下的解，則G的最優(yōu)混合策略x*=(x1,

x2

)T,y*

=(y1,y2

)T滿(mǎn)足下列方程組：且其中v=VG

.第35頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月36例1：求解求解矩陣對(duì)策G＝{S1，S2；A}

，其中：解：在A中由于：第3行≥第2行，第4行≥第1行，因此從A中劃去1，2兩行，得：第36頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月37在A1中由于：第1列≤第3列，第2列≤第4列，因此從A1中劃去3，4兩列，得：在A2中由于：第1行≥第3行，因此從A2中劃去第3行，得：在A3中由于：第2列≤第3列，因此從A3中劃去第3列，得：第37頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月38分別求解方程組得：得x3=1/3,x4

=2/3,y1=1/2,y2

=1/2,v=5.由此對(duì)于原問(wèn)題A而言，最優(yōu)解為：第38頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月39二、2×n和m×2對(duì)策的圖解法解：設(shè)局中人I

的混合策略為(x,1－x)T,局中人I

的最少得益為如下圖中由局中人II

選擇β1,β2,β3

時(shí)所確定的三條直線2x

＋7(1－x)＝v，3x

＋5(1－x)＝v，11x

＋2(1－x)＝v在x處縱坐標(biāo)的最小者，即如圖中折線B1BB2B3。例2：求解求解矩陣對(duì)策G＝{S1，S2；A}

，其中：第39頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月40012511237xVVβ3β1β2B1BB2B3A

所以對(duì)局中人I來(lái)說(shuō)，他的策略就是確定x使他的得益達(dá)到最大。按最大最小原則應(yīng)選擇x＝OA，而AB即為對(duì)策的值。為求出x和對(duì)策的值VG，可聯(lián)立過(guò)B點(diǎn)的兩條直線β2和β3所確定的方程。第40頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月41解得：x

＝3/11，VG=49/11。此外從圖中可看出，局中人II的最優(yōu)策略只由β2和β3組成（不選β1），可由方程組所確定：解得：y2=9/11，y3=2/11。所以最優(yōu)解為：第41頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月42例3：求解矩陣對(duì)策G＝{S1，S2；A}，其中：

解：設(shè)局中人II

的混合策略為(y,1－y)T,局中人II的最大支付為如下圖中由局中人I選擇α1,α2,α3

時(shí)所確定的三條直線2y＋7(1－y)＝v，9y＋6(1－y)＝v，11y＋2(1－y)＝v在y處縱坐標(biāo)的最小者，即如圖中折線上的B點(diǎn)。第42頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月43012611297yVVBAα1α2α3

對(duì)局中人II來(lái)說(shuō)，他的策略就是確定y使他的支付達(dá)到最小。按最小最大原則應(yīng)選擇y＝OA，為求出y和對(duì)策的值VG，可聯(lián)立過(guò)B

點(diǎn)的兩條直線α1和α2所確定的方程。第43頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月44解得：y＝1/8，VG=51/8。

此外從圖中可看出，局中人II的最優(yōu)策略只由α1和α2組成（不選α3），可由方程組所確定：解得：x1=3/8，x2=5/8。所以最優(yōu)解為：第44頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月45三、線性規(guī)劃法由前面定理可知，對(duì)策G的解滿(mǎn)足下列線性規(guī)劃：作變量替換：第45頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月46則于是上述線性規(guī)劃等價(jià)于下面的線性規(guī)劃問(wèn)題。

由此求解一個(gè)對(duì)策問(wèn)題，就相當(dāng)于求解上面的對(duì)偶問(wèn)題：第46頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月47例4：利用線性規(guī)劃法求解矩陣對(duì)策G＝{S1,S2；A}.【注】如果aij不滿(mǎn)足非負(fù)性，則存在一個(gè)正數(shù)k，使得aij+k≥0

令B=(bij)=(aij+k)，求解對(duì)策問(wèn)題

{S1，S2；B}

，可以證明：?jiǎn)栴}{S1，S2；B}與問(wèn)題{S1，S2；A}的最優(yōu)策略相同，且有：其中：第47頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月48解：建立相應(yīng)的線性規(guī)劃模型及用單純形法求解后一個(gè)問(wèn)題，先標(biāo)準(zhǔn)化為：第48頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月49用單純形表求解如下：第49頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月50第50頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月51由此最優(yōu)解為：第51頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月52第四節(jié)兩人有限非零和對(duì)策

例1：“囚徒困境”甲乙是同案囚犯，被隔離審訊。如果兩個(gè)都抵賴(lài)，因?yàn)樽C據(jù)不充分，兩人都只能判1年。如果只有一方坦白，則無(wú)罪釋放；而另一方則屬抗拒從嚴(yán)，判10年。但如果兩人都坦白，則各判5年。

下表給出了“囚徒困境”博弈問(wèn)題的戰(zhàn)略式表述，為了實(shí)現(xiàn)各自的效用最大化，雙方格采取何種策略呢?

坦白β1抵賴(lài)β2坦白α1(－5,－5

)(0,－10

)抵賴(lài)α2(－10，0

)(－1,－1

)第52頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月53

假設(shè)該博弈是一次性的，對(duì)于囚犯甲而言，不管乙選擇坦白還是抵賴(lài)，他選擇坦白都比選擇抵賴(lài)更好。這種不管對(duì)方選擇何種策略，局中人的最優(yōu)選擇總是不變的那個(gè)策略被稱(chēng)為該局中人的優(yōu)超策略。此例中坦白為甲的優(yōu)超策略，同樣道理坦白也是乙的優(yōu)超策略。結(jié)果是，兩個(gè)囚徒爭(zhēng)先恐后地都選擇坦白，各判刑5年。從而(坦白，坦白)也就構(gòu)成了該博弈的優(yōu)超策略均衡（稱(chēng)為納什均衡）。第53頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月54

囚犯困境反映了一個(gè)深刻的問(wèn)題，這就是個(gè)人理性與集體理性的矛盾，如果兩個(gè)人都抵賴(lài)，對(duì)局中人組成的集體而言，可謂帕累托最優(yōu)，但是這并不滿(mǎn)足個(gè)人理性導(dǎo)致的納什均衡(坦白，坦白)，因而，這個(gè)帕累托改進(jìn)在靜態(tài)博弈中辦不到。囚徒困境說(shuō)明納什均衡并不一定導(dǎo)致帕累托最優(yōu)，從而動(dòng)搖了傳統(tǒng)經(jīng)濟(jì)學(xué)中個(gè)人效用最大化行為必然導(dǎo)致社會(huì)福利最優(yōu)的基本命題。

對(duì)囚犯困境問(wèn)題作進(jìn)一步分析，不難發(fā)現(xiàn)，盡管甲與乙各自的最佳選擇都是坦白，如果雙方均選擇抵賴(lài)，各判刑1年，顯然比雙方均坦白時(shí)答判刑5年的結(jié)局要好，因此，其最佳選擇與最優(yōu)結(jié)局并不一致。出現(xiàn)所謂的“囚徒困境”。第54頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月55

設(shè)對(duì)策G的局中人Ⅰ和Ⅱ，雙方都只有有限個(gè)策略，其中

在局勢(shì)(αi,βj)下(即局中人Ⅰ取策略α，局中人Ⅱ取策略βj

時(shí)所形成的策略組合)，局中人Ⅰ的贏得值是aij，局中人Ⅱ的贏得值是bij。分別用矩陣表示為A和B。Ⅰ的策略集為：Ⅱ的策略集為：非合作兩人對(duì)策第55頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月56

定義：對(duì)于非合作兩人對(duì)策G，如果αi*是局中人Ⅰ對(duì)Ⅱ的策略βj*的最優(yōu)策略，βj*是局中人Ⅱ?qū)Β竦牟呗驭羒*的最優(yōu)策略，則稱(chēng)局勢(shì)(αi*，βj*)是該問(wèn)題的一個(gè)納什均衡（即誰(shuí)都不愿單獨(dú)改變策略）

。第56頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月57

本博弈的納什均衡為(大豬按，小豬等待)。

例2：“智豬博弈”豬圈有一頭大豬、一頭小豬，按一下按鈕會(huì)有10個(gè)單位的飼料，但按按鈕需要2個(gè)單位成本。

按β1等待β2按α1(5，1

)(4，4

)等待α2（9，－1）(0，0

)第57頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月58

例3：“夫妻博弈”丈夫喜歡看球賽，妻子喜歡逛商場(chǎng)。他們都寧愿在一起，也不愿分開(kāi)行動(dòng)。

本例有兩個(gè)納什均衡結(jié)果會(huì)出現(xiàn)，要么一起去看球賽，要么一起去逛商場(chǎng)，但在一次博弈中究竟會(huì)出現(xiàn)哪一種？

看球賽β1逛商場(chǎng)β2看球賽α1(2，1

)(0，0

)逛商場(chǎng)α2(0，0

)(1，3)第58頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月59

這個(gè)博弈也有兩個(gè)納什均衡，一個(gè)是(進(jìn)攻，退卻)，另一個(gè)是(退卻，進(jìn)攻)。

進(jìn)攻β1退卻β2進(jìn)攻α1(-3，-3

)(2，0

)退卻α2(0，2

)(0，0)

例4：“斗雞博弈”有兩個(gè)斗雞A、B，它們各有兩個(gè)策略：進(jìn)攻或退卻。第59頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月60(0，300

)(0，300

)不進(jìn)入α2(－10,0

)(40,50

)進(jìn)入α1阻撓β2默許β1

進(jìn)入者在位者

這個(gè)博弈也有兩個(gè)納什均衡，一個(gè)是(進(jìn)入，默許)，另一個(gè)是(不進(jìn)入，斗爭(zhēng))，而(不進(jìn)入，默許)卻不是一個(gè)納什均衡。

例5:

“市場(chǎng)進(jìn)入壁壘”設(shè)想一個(gè)壟斷企業(yè)已占領(lǐng)市場(chǎng)(稱(chēng)為“在位者”)，另一個(gè)企業(yè)很想進(jìn)入市場(chǎng)(稱(chēng)為“進(jìn)入者”)，在位者想保持其壟斷地位，就要阻撓進(jìn)入者進(jìn)入．假定雙方在各種策賂組合下的贏得短陣如表所示：第60頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月61非合作兩人對(duì)策的解法

對(duì)其他局中人的任一策略組合，找出局中人i的最佳策略，并在其得益值下劃線。若存在一個(gè)策略組合，使得所有局中人的得益值下都劃了線，則該策略組合就是一個(gè)納什均衡。求納什均衡的方法如下:第61頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月62例1：囚犯困境(－1，－1

)(－10，0

)抵賴(lài)α2(0,－10

)(－5,－5

)坦白α1抵賴(lài)β2坦白β1

甲乙因此(坦白，坦白)

構(gòu)成了該博弈的納什均衡。第62頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月63例3：夫妻博弈

看球賽β1逛商場(chǎng)β2看球賽α1(2，1

)(0，0

)逛商場(chǎng)α2(0，0

)(1，3)

這個(gè)博弈有兩個(gè)納什均衡，一個(gè)是(看球賽，看球賽)，另一個(gè)是(逛商場(chǎng)，逛商場(chǎng))。第63頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月64(0，300

)(0，300

)不進(jìn)入α2(－10,0

)(40,50

)進(jìn)入α1阻撓β2默許β1

進(jìn)入者在位者例5:市場(chǎng)進(jìn)入壁壘

因此(進(jìn)入，默許)和(不進(jìn)入，阻撓)是該問(wèn)題的兩個(gè)鈉什均衡。第64頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月65混合策略納什均衡

上面介紹了在純策略意義下非合作兩人對(duì)策納什均衡的概念及求解方法，但有些對(duì)策不存在純策略意義下的納什均衡，考慮下面的例子。第65頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月66(0，0)(－1，1

)不救濟(jì)α2(－1,3

)(3,2)救濟(jì)α1游蕩β2尋找工作β1

政府流浪漢

例6：局中人是政府和一個(gè)流浪漢，流浪漢有兩個(gè)策略：尋找工作或游蕩；政府也有兩個(gè)策略：救濟(jì)或不救濟(jì)。政府幫助流浪漢的前提是后者必須試圖尋找工作；否則，政府不予以幫助；而流浪漢只在得不到救濟(jì)時(shí)才會(huì)尋找工作，如表給出了對(duì)策的贏得雙矩陣：第66頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月67

同樣局中人可以考慮按照一定的隨機(jī)方式來(lái)確定一個(gè)策略組合的混合策略。每個(gè)局中人作出決策時(shí)，不是只選用一個(gè)純策略，而是按照預(yù)先確定的一組概率來(lái)選取他們所有可能采用的策略。

容易理解：當(dāng)流浪漢選擇尋找工作時(shí)，政府的最優(yōu)策略是救濟(jì)；當(dāng)流浪者選擇游蕩時(shí)，政府的最優(yōu)策略是不救濟(jì)；當(dāng)政府策略為不救濟(jì)時(shí)，流浪漢的最優(yōu)策略是尋找工作；當(dāng)政府選擇救濟(jì)時(shí)，流浪漢的最優(yōu)策略是游蕩。總之，在純策略下，沒(méi)有一個(gè)策略組合構(gòu)成納什均衡。第67頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月68

局中人I以概率x1,x2,…,xm來(lái)分別選取純策略α1,α2

…,αm

；而局中人II以概率y1,y2,…，yn來(lái)選用自己的純策略β1,β2,…,βn。于是：

稱(chēng)x=(x1,x2,…，xm)T,y=(y1,y2,…，yn)T分別為I和II的混合策略。

設(shè)A，B分別為局中人I和II的贏得矩陣，且都是為m×n矩陣。第68頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月69則局中人I和II的混合策略集為：

當(dāng)局中人I和II的混合策略分別為x和y時(shí)，局中人I和II的期望贏得值分別為：第69頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月70如果一個(gè)混合策略組合(x*,y*)同時(shí)滿(mǎn)足：且

則稱(chēng)策略組合(x*,y*)

是一個(gè)混合策賂納什均衡，其中(x,y)分別是局中人I和II的任意混合策略。

例6中假定政府以概率x選擇救濟(jì)．概率1－x選擇不救濟(jì)，即政府的混合策略為(x,1－x)；流浪漢以概率y選擇尋找工作，以概率1－y選擇游蕩，即流浪漢的混合策略為(y,1－y)。那么政府的期望贏得函數(shù)為：第70頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月71同樣，流浪漢的期望贏得函數(shù)為：令得令得第71頁(yè)，課件共78頁(yè)，創(chuàng)作于2023年2月72

這就是說(shuō)，在混合策略均衡中，流浪漢在對(duì)付政府給定的混合策略下，最優(yōu)策略是以1／5的概率選擇尋找工作,而以4／5的概率選擇游蕩，即：