運(yùn)籌學(xué)課程對策論

對策論

GameTheory

“理智人”間的競爭策略1二、引言三、矩陣對策對策現(xiàn)象對策論對策問題的三個基本要素對策問題的分類具有鞍點的矩陣對策無鞍點的矩陣對策最優(yōu)混合策略的解法本章主要內(nèi)容一、對策論導(dǎo)論2

博弈論導(dǎo)論—博弈論的演化歷程

最早的對策論思想產(chǎn)生于中國春秋時期，孫武的《孫子兵法》現(xiàn)代經(jīng)濟(jì)博弈論起源可以追溯到1944年，由美國著名數(shù)學(xué)家馮·諾依曼（JohnNeumann）與經(jīng)濟(jì)學(xué)家奧·摩根斯坦（OscarMorgensten）合著的《博弈論與經(jīng)濟(jì)行為》31994：納什（Nash）、海薩尼（J.Harsanyi）、澤爾騰（R.Selten）

1996莫里斯（JamesA.Mirrlees）和維克瑞（WilliamVickrey）納什的基本貢獻(xiàn)是證明了非合作博弈均衡解及其存在性，建立了作為博弈論基礎(chǔ)的“納什均衡”概念；海薩尼則把不完全信息納入到博弈論方法體系中；澤爾騰的貢獻(xiàn)在于將博弈論由靜態(tài)向動態(tài)的擴(kuò)展，建立了“子博弈精練納什均衡”的概念。這兩位經(jīng)濟(jì)學(xué)家的貢獻(xiàn)集中于運(yùn)用博弈論對現(xiàn)實經(jīng)濟(jì)問題的解釋。博弈論導(dǎo)論—博弈論和諾貝爾經(jīng)濟(jì)學(xué)獎4這三位作為不對稱信息市場理論的奠基人被授予諾貝爾經(jīng)濟(jì)學(xué)獎，以表彰他們分別在檸檬品市場等不對稱信息理論研究領(lǐng)域做出的基礎(chǔ)性貢獻(xiàn)。這些貢獻(xiàn)發(fā)展了博弈論的方法體系，拓寬了其經(jīng)濟(jì)解釋范圍。貢獻(xiàn)主要在于通過實驗室實驗來測試根據(jù)經(jīng)濟(jì)學(xué)理論而做出預(yù)測的未知或不確定性。是對以博弈論為基礎(chǔ)構(gòu)建的理論模型進(jìn)行實證證偽工作的一大創(chuàng)舉。他們通過博弈理論分析增加了世人對合作與沖突的理解。其理論模型應(yīng)用在解釋社會中不同性質(zhì)的沖突、貿(mào)易糾紛、價格之爭以及尋求長期合作的模式等經(jīng)濟(jì)學(xué)和其他社會科學(xué)領(lǐng)域。博弈論導(dǎo)論—博弈論和諾貝爾經(jīng)濟(jì)學(xué)獎2001：阿克洛夫（Akerlof）、斯賓塞（Spence）、斯蒂格利茨（Stiglitz）2002：弗農(nóng)史密斯（Smith）2005：奧曼（Aumann）、謝林（Schelling）5約翰·納什

1928年生于美國約翰·納什（JOHNF.NASH）美國人(1928-)，由于他與另外兩位數(shù)學(xué)家在非合作博弈的均衡分析理論方面做出了開創(chuàng)性的貢獻(xiàn)，對博弈論和經(jīng)濟(jì)學(xué)產(chǎn)生了重大影響，而獲得1994年諾貝爾經(jīng)濟(jì)獎。納什均衡(完全信息靜態(tài)博弈)卡內(nèi)基—梅隆大學(xué)科學(xué)碩士、普林斯頓大學(xué)數(shù)學(xué)博士。主要研究領(lǐng)域：博弈論和微分幾何學(xué)。主要貢獻(xiàn)：非合作博弈均衡、經(jīng)濟(jì)博弈論6約翰·福布斯·納什7

《美麗心靈》是一部關(guān)于一個真實天才的極富人性的劇情片。故事的原型是數(shù)學(xué)家小約翰-福布斯-納什(Nash),普林斯頓大學(xué)的著名教授，諾貝爾經(jīng)濟(jì)學(xué)獎的獲得者(1994年)，他在博弈理論方面的巨大發(fā)現(xiàn)甚至改變了我們的日常生活。但另一方面，納什也是一個悲劇人物，他的一生為精神分裂癥所困。在歷經(jīng)苦痛的人生里，納什一方面在運(yùn)用自己那優(yōu)美絕倫的大腦，另一方面也在與他的大腦進(jìn)行著頑強(qiáng)的抗?fàn)帯Ｗ罱K理性為他帶來了心靈的和平，納什終于摘取了科學(xué)事業(yè)上的桂冠。

8

囚徒困境問題納什均衡：（坦白，坦白）

-1，-1

-10，0

0，-10

-8，-8囚徒B坦白抵賴坦白抵賴囚徒A坦白從寬，抗拒從嚴(yán)著名博弈問題9

市場進(jìn)入阻撓

0，300

0，300

-10，0

40，50在位者默許斗爭進(jìn)入不進(jìn)入進(jìn)入者納什均衡：（進(jìn)入，默許）（不進(jìn)入，斗爭）著名博弈問題10智豬博弈按鈕食槽著名博弈問題11假設(shè)豬圈里有一頭大豬、一頭小豬。豬圈的一頭有豬食槽，另一頭安裝著控制豬食供應(yīng)的按鈕，按一下按鈕會有10個單位的豬食進(jìn)槽，但是誰按按鈕就會首先付出2個單位的成本，若大豬先到槽邊，大小豬吃到食物的收益比是9∶1；同時到槽邊，收益比是7∶3；小豬先到槽邊，收益比是6∶4。那么，在兩頭豬都有智慧的前提下，最終結(jié)果是小豬選擇？？？。12小豬行動等待大豬行動5

14

4等待9

-10

0小豬的選擇將是等待13

齊王賽馬著名博弈問題齊王與田忌賽馬.雙方約定:從各自的上中下三個等級

的馬中各選一匹參賽;每匹馬只能參賽一次;每次比賽雙方各出一匹馬,負(fù)者要付給勝者千金.不同等級的馬,高等級優(yōu)于低等級;同等級的馬中,齊王的馬優(yōu)于田忌的馬;如何對策???14引言

對策現(xiàn)象各種比賽：體育、棋類等比賽

政治方面：外交談判經(jīng)濟(jì)方面：貿(mào)易談判、爭奪市場、各種經(jīng)營競爭等

具有競爭或?qū)剐再|(zhì)的現(xiàn)象15對策論

對策論是關(guān)于相互影響的決策者的研究。是研究具有競爭或者對抗性質(zhì)現(xiàn)象的理論與方法。研究對策現(xiàn)象的一種定量分析理論與方法。也稱為博弈論參加競爭或?qū)沟母鞣骄哂胁煌睦婧湍繕?biāo)，為了達(dá)到各自的利益和目標(biāo)，各方必須考慮對手的各種可能的行動方案，并力圖選擇對自己最有利或最合理的方案。16對策問題的三個基本要素

1．局中人（players）一個對策中有權(quán)決定自己行動方案的對策參加者稱為局中人。通常用I表示局中人的集合，如果有n個局中人，則I＝{1,2,…,n}。

對策論中對局中人的一個重要的假設(shè)：每個局中人都是“理性的”、等智力的。

2．策略（strategies）對策中，可供局中人選擇的一個實際可行的完整的行動方案稱為一個策略。一般每個局中人的策略集S中至少應(yīng)包括兩個策略。17

如“齊王與田忌賽馬”中：

齊王有6個策略：{(上中下)，(上下中),(中上下),(中下上),(下上中),(下中上)}

田忌有6個策略：{(上中下)，(上下中),(中上下),(中下上),(下上中),(下中上)}3.贏得函數(shù)(支付函數(shù))（payofffunction）

局勢：每個局中人從各自的策略集合中選取一個策略參加對策，形成的一個處于競爭的策略組。如：齊王選策略(上中下)，田忌選策略(中上下)，構(gòu)成一個局勢{(上中下)，(中上下)}。局勢的得失總和為0。一局對策的得失，即局中人的得失。叫贏得（支付）函數(shù)，對有限策略集，叫贏得（支付）矩陣。18設(shè)si是第i個局中人的一個策略，則n個局中人的策略形成的策略組合s＝(s1，s2,…,sn)就是一個局勢。若記S為全部局勢的集合，則S＝S1×S2×…×Sn當(dāng)一個局勢s出現(xiàn)后，應(yīng)該為每一局中人i規(guī)定一個贏得值(或所失值)Hi(s)。顯然，Hi(s)是定義在S上的函數(shù)，稱為局中人i的贏得函數(shù)。在“齊王賽馬”中，局中人集合I＝{1,2}，齊王和田忌的策略集可分別用表示。這樣,齊王的任一策略αi和田忌的任一策略βj就構(gòu)成了—個局勢sij，如果α1=(上,中,下)，βl＝(上,中,下)．則在局勢s11下，齊王的贏得為H1(s11)＝3，田忌的贏得為H2(s11)=-3當(dāng)局中人、策略集和贏得函數(shù)這3個要素確定后，一個對策模型也就給定了。19例：兩個賭博參加者甲、乙各出示一枚硬幣，在不讓對方看見的情況下，將硬幣放在桌子上，若兩個硬幣都呈正面或都呈反面則甲得1元，乙付出1元；若兩個硬幣一個呈正面另一個呈反面則乙得1元，甲付出1元。局中人：甲、乙策略：si={正面，反面}i=1,2局勢：S={(正,反)，(正,正)，(反,正)，(反,反)}支付函數(shù)：H1(正,反)=-1，H1(正,正)=1，H1(反,正)=-1，H1(反,反)=1，H2(正,反)=1，H2(正,正)=-1，H2(反,正)=1，H2(反,反)=-120對策問題的分類對策動態(tài)對策靜態(tài)對策結(jié)盟對策不結(jié)盟對策微分對策聯(lián)合對策合作對策有限無限二人多人二人多人零和非零和零和非零和零和非零和零和非零和21矩陣對策二人有限零和對策（對抗對策）：局中人2個每個局中人的策略集中的策略數(shù)目有限每一局勢的對策均有確定的損益值，并且對同一局勢的兩個局中人的益損值之和為零。221(上中下)2(上下中)3(中上下)4(中下上)5(下上中)6(下中上)1(上中下)31111-12(上下中)1311-113(中上下)1-131114(中下上)-1113115(下上中)11-11316(下中上)111-113齊王田忌aij23

例：某單位秋季決定冬季取暖用煤的貯量。冬季用煤貯量在較暖、正常和較冷情況下分為10、15和20噸。設(shè)冬季煤價也隨寒冷程度而變，在上述三種情況下分別為100、150和200元/噸，已知秋季煤價為100元/噸，冬季氣象未能予知，問秋季合理貯煤量為多少？設(shè)局中人甲為：貯煤量決策者；局中人乙為：未來冬季氣候。費用總和=秋季貯煤量費用+冬季補(bǔ)購煤量費用1(較暖)2(正常)3(較冷)1(10噸)-(10×100)=-1000-(10×100+5×150)=-1750-(10×100+10×200)=-30002(15噸)-(15×100)=-1500-(15×100)=-1500-(15×100+5×200)=-25003(20噸)-(20×100)=-2000-(20×100)=-2000-(20×100)=-2000甲乙aij則贏得矩陣為：2425矩陣對策問題解的假設(shè)：例：設(shè)有一矩陣博弈G={S1，S2；H}，其中H=具有鞍點的矩陣對策26如果雙方部不想冒險、都不存在僥幸心理，而是考慮到對方必然會設(shè)法使自己所得最少這一點，就應(yīng)該從各自可能出現(xiàn)的最不利的情形中選擇一個最有利的情形作為決策的依據(jù)，這就是所謂“理智行為”，也是對策雙方實際上可以接受并采取的一‘種穩(wěn)妥的方法。

從各自可能出現(xiàn)的最不利的情形中選擇一個最有利的情形作為決策的依據(jù)局中人1局中人2H=H=27定義1：設(shè)G={S1，S2；H}為一矩陣博弈，其中S1={α1,α2,…,αm}，S2={β1,β2,…,βn}，H=(aij)m×n，若等式成立。記，稱vG為博弈G的值，使上式成立的純局勢為純策略下的解，分別稱為局中人1，2的最優(yōu)純策略。

定理1

矩陣博弈G={S1，S2；H}在純策略意義下有解的充要條件是：存在純局勢，使得對任意i和j，有

≤≤28充分性：29必要性：30定義2（鞍點）設(shè)f(x,y)為一個定義在x∈A

及y∈B上的實值函數(shù)，若存在x*∈A，y*∈B，使得對一切x∈A

和y∈B有f(x,y*)≤f(x*,y*)≤f(x*,y)則稱(x*,y*)為函數(shù)f的一個鞍點。鞍點行元素變化趨勢列元素變化趨勢具有鞍點對策求解：31無鞍點的矩陣對策兩小孩玩游戲：1(石頭)2(剪刀)3(布)1(石頭)01-12(剪刀)-1013(布)1-10甲乙aij贏得矩陣為：（無鞍點）32定義3（混合策略）33定義4（混合局勢、混合策略意義下的解、對策值）34例題：35

定理4（存在性定理）：任意一個給定的矩陣對策一定有解，局中人雙方總有一個最優(yōu)混合策略，即：36

定理5：若矩陣對策值為V，則下面兩組不等式的解是局中人甲、乙的最優(yōu)混合策略：37

矩陣對策在混合策略意義下的解總是存在的，求解的基本方法為線性規(guī)劃法。38

⑴對局中人甲，希望對策的局勢值越大越好。若第i行所有元素≥第l行所有元素，即j=1,2,…,n，則甲理智，必采用i純策略而舍去l純策略，不影響最優(yōu)策略和策略鞍點值。此時稱i策略為對l策略的優(yōu)勢策略。⑵對局中人乙，希望對策的局勢值越小越好。若第j列所有元素≤第k列所有元素，即，i=1,2,…,m，

則乙理智，必采用j純策略而舍去k

純策略，不影響最優(yōu)策略和策略鞍點值。此時稱j策略為對k

策略的優(yōu)勢策略。

若存在優(yōu)勢策略，則支付矩陣階數(shù)可降低優(yōu)勢原則：（某一策略對其他策略具有支配作用）39由G得到一個新的矩陣策略G’40原贏得矩陣按優(yōu)勢原則簡化后贏得矩陣41第4行優(yōu)于第1行劃去第1行42第3行優(yōu)于第2行劃去第2行43第1列優(yōu)超于第3列劃去第3列44第2列優(yōu)超于第4列劃去第4列45劃去第5列1/3第1列+2/3第2列優(yōu)超于第5列倍數(shù)之和不能超過1（概率組合）第1行優(yōu)超于第3行劃去第2行46

解析法：適用于縮減后的支付矩陣為n×n方陣的無鞍點對策問題。

設(shè)甲的混合策略為(x1,x2,…,xn)，乙的混合策略為(y1,y2,…,yn)。贏得期望值為：

47⑴甲的期望值方程為：

⑵乙的期望值方程為：

解得甲的最優(yōu)混合策略為

X*=(x1*,…,xn*);

解得乙的最優(yōu)混合策略為Y*=(y1*,…,yn*)

對策值V=V*

48例：求兩小孩玩游戲?qū)Σ叩淖顑?yōu)混合策略無鞍點且不能縮減。

設(shè)甲的混合策略為(x1,x2,x3)，乙的混合策略為(y1,y2,y3)。得失期望值為：

49⑴甲小孩的期望值方程為：

⑵乙小孩的期望值方程為：

解得甲的最優(yōu)混合策略為

X*=(1/3,1/3,1/3),V*=0

解得乙的最優(yōu)混合策略為

Y*=(1/3,1/3,1/3),V*=0;

甲、乙兩小孩均以1/3的同等概率取石頭、剪刀、布純策略，在不考慮其它因素的前提下，多局競爭的結(jié)果是最終和局，誰也不占優(yōu)勢，反映雙方純策略實力相等。50例：求齊王與田忌賽馬對策的最優(yōu)混合策略

無鞍點且不能縮減

設(shè)齊王的混合策略為(x1,x2,x3,x4,x5,x6)

田忌的混合策略為(y1,y2,y3,y4,y5,y6)

51⑴齊王的期望值方程為：

⑵田忌的期望值方程為齊王的最優(yōu)混合策略為X*=(1/6,1/6,1/6,1/6,1/6,1/6)V*=1田忌的最優(yōu)混合策略為Y*=(1/6,1/6,1/6,1/6,1/6,1/6),V*=1

52

拉格朗日乘子法：適用于縮減后的支付矩陣為n×n方陣的無鞍點對策問題。

設(shè)甲的混合策略為(x1,x2,…,xn)

乙的混合策略為(y1,y2,…,yn)。得失期望值為：

s.t.

,

即:s.t.

,

53求出最優(yōu)混合策略和對策值，并且有：

54例：求下列對策的最優(yōu)混合策略⑴解下列方程組：⑵解下列方程組：無鞍點且不能縮

設(shè)甲的混合策略為(x1,x2,x3)，乙的混合策略為(y1,y2,y3)。拉氏函數(shù)為：55解得乙的最優(yōu)混合策略為Y*=(14/45,11/45,20/45),V*=29/45

解得甲的最優(yōu)混合策略為

X*=(20/45,11/45,14/45),V*=29/45

注意：因為沒有顧及變量非負(fù)的要求，解析法與拉氏法不是對所有的有解支付矩陣均能得到正確答案。例：求下列對策的最優(yōu)混合策略。無鞍點且不能縮減56⑴解下列方程組：解