第十二章 博弈論(運籌學-重慶大學,熊中楷)

1、運籌學運籌學熊中楷教授熊中楷教授博博 弈弈 論論運籌學運籌學熊中楷教授熊中楷教授1943年，盟年，盟 軍轟炸軍轟炸日軍增援部隊。日軍增援部隊。雙方均知天氣雙方均知天氣, 均知均知對方可能的策略對方可能的策略日日 軍山本五十六軍山本五十六 策策 略略走北線走北線（陰天）（陰天）走南線走南線（晴天）（晴天）盟盟軍軍 肯肯 策策尼尼 略略將將軍軍走北線走北線（陰天）（陰天）轟炸轟炸2天天轟炸轟炸2天天走南線走南線（晴天）（晴天）轟炸轟炸1天天轟炸轟炸3天天盟盟 軍：首先考慮軍：首先考慮每個策略至少能每個策略至少能贏多少，然后選贏多少，然后選最有利的策略最有利的策略日軍：首先考慮日軍：首先考慮對方每個

2、策略至對方每個策略至多會損失多少，多會損失多少，然后選損失最少然后選損失最少的策略的策略基本思路：基本思路： 從最壞處著想，去爭取最好的結果從最壞處著想，去爭取最好的結果Max Min aij = Min Max aij = a11 =2歷史事實：歷史事實：有效轟炸有效轟炸2天天第十二章：第十二章：博弈及其應用博弈及其應用 運籌學運籌學熊中楷教授熊中楷教授博弈論博弈論( 對策論對策論 )文化革命中：階級斗爭為綱，面對面的斗爭，文化革命中：階級斗爭為綱，面對面的斗爭， 背靠背的揭發(fā)背靠背的揭發(fā)囚徒的難題：坦白從寬，抗拒從嚴囚徒的難題：坦白從寬，抗拒從嚴 （坦白從寬，（坦白從寬， 牢底住穿？）牢底

3、住穿？）甲乙二人合伙搶劫，訂立攻甲乙二人合伙搶劫，訂立攻守同謀，警察證據(jù)不足，采守同謀，警察證據(jù)不足，采用各個擊破，心理戰(zhàn)術用各個擊破，心理戰(zhàn)術囚徒甲不坦白囚徒甲不坦白囚徒甲坦白囚徒甲坦白囚徒乙不坦白囚徒乙不坦白 （0。05，0。05）（甲拘（甲拘15天，乙拘天，乙拘15天）天） （1，4）（甲判刑甲判刑1年，乙判刑年，乙判刑4年）年）囚徒乙坦白囚徒乙坦白 （4，1）（甲判刑甲判刑4年，乙判刑年，乙判刑1年）年） （10，10）（甲判刑甲判刑10年乙判刑年乙判刑10年）年）上面模型的應用：十字路口兩個家用電器商店，相同產(chǎn)品，獨立定價，雙方按高價比上面模型的應用：十字路口兩個家用電器商店，相同產(chǎn)

4、品，獨立定價，雙方按高價比雙方按低價獲利大，但比不上單方降價。本來雙方商定按高價，但實際可能單方降價雙方按低價獲利大，但比不上單方降價。本來雙方商定按高價，但實際可能單方降價雙方最佳結果是：抗拒從寬。雙方最佳結果是：抗拒從寬。 實際結果往往是：實際結果往往是：坦白從寬，坦白從寬， 牢底住穿牢底住穿第十二章：第十二章：博弈及其應用博弈及其應用 運籌學運籌學熊中楷教授熊中楷教授第十二章：第十二章：博弈及其應用博弈及其應用 博弈論博弈論( 對策論對策論 )各方策略對應效果各方策略對應效果-用矩陣表示用矩陣表示運籌學運籌學熊中楷教授熊中楷教授量化戰(zhàn)略決策：量化戰(zhàn)略決策： 如圖，某城市被三條河分割成為如

5、圖，某城市被三條河分割成為A, B, C 三個區(qū)，城市人口三個區(qū)，城市人口A區(qū)占區(qū)占40，B區(qū)占區(qū)占30，C區(qū)占區(qū)占30。 目前，該城市沒有溜冰場，甲乙兩個公司目前，該城市沒有溜冰場，甲乙兩個公司計劃建溜冰場，甲公司計劃建兩個溜冰場，乙公司計計劃建溜冰場，甲公司計劃建兩個溜冰場，乙公司計劃建一個溜冰場，每個公司都知道：如果某區(qū)有兩個劃建一個溜冰場，每個公司都知道：如果某區(qū)有兩個溜冰場，那么這兩個溜冰場將平分該區(qū)業(yè)務；如果某溜冰場，那么這兩個溜冰場將平分該區(qū)業(yè)務；如果某區(qū)只有一個溜冰場，那么這個溜冰場將獨占該區(qū)業(yè)務，區(qū)只有一個溜冰場，那么這個溜冰場將獨占該區(qū)業(yè)務，如果某區(qū)沒有溜冰場，那么該區(qū)業(yè)務

6、將平均分配到城如果某區(qū)沒有溜冰場，那么該區(qū)業(yè)務將平均分配到城市的三個溜冰場，每個公司都希望更多的市場份額。市的三個溜冰場，每個公司都希望更多的市場份額。 甲，乙兩個公司的最優(yōu)策略是什么？雙方最優(yōu)策甲，乙兩個公司的最優(yōu)策略是什么？雙方最優(yōu)策略時兩個公司市場份額各為多少？略時兩個公司市場份額各為多少？答案：公司甲的最優(yōu)策略是在答案：公司甲的最優(yōu)策略是在A區(qū)區(qū), B區(qū)各建一個溜區(qū)各建一個溜冰場或者在在冰場或者在在A區(qū)區(qū), C區(qū)各建一個溜冰場；區(qū)各建一個溜冰場；公司乙的最優(yōu)策略是公司乙的最優(yōu)策略是 在在A區(qū)建一個溜冰場。區(qū)建一個溜冰場。 第十二章：第十二章：博弈及其應用博弈及其應用 運籌學運籌學熊中楷

7、教授熊中楷教授解：解：(1) 顯然，公司甲不會把兩個溜冰場建在同一個區(qū)。顯然，公司甲不會把兩個溜冰場建在同一個區(qū)。所以，兩個公司策略各有三種：所以，兩個公司策略各有三種： A區(qū)區(qū)B區(qū)區(qū)C區(qū)區(qū)策略策略1110策略策略2101策略策略3011 A區(qū)區(qū)B區(qū)區(qū)C區(qū)區(qū)策略策略1100策略策略2010策略策略3001公司甲公司甲公司乙公司乙第十二章：第十二章：博弈及其應用博弈及其應用 運籌學運籌學熊中楷教授熊中楷教授表中數(shù)字表中數(shù)字1表示在該區(qū)建一個溜冰場，表示在該區(qū)建一個溜冰場，0表示在該區(qū)不建溜冰場。表示在該區(qū)不建溜冰場。設市場總份額為設市場總份額為100，如果市場由兩個公司平分，則各占，如果市場由兩

8、個公司平分，則各占50份，現(xiàn)在定義份，現(xiàn)在定義公司甲的損益值為：在各種組合策略下公司甲所占市場份額因此公司甲公司甲的損益值為：在各種組合策略下公司甲所占市場份額因此公司甲的損益如下：的損益如下： 第十二章：第十二章：博弈及其應用博弈及其應用 運籌學運籌學熊中楷教授熊中楷教授 公公 司司 乙乙 公公司司甲甲 策略策略1A 區(qū)區(qū)策略策略2B區(qū)區(qū)策略策略3C區(qū)區(qū)Min aij 策略策略1A B區(qū)區(qū)70757070*策略策略2AC區(qū)區(qū)70707570*策略策略3B C區(qū)區(qū)60727260 Max aij70*7575 如果公司乙采用策略如果公司乙采用策略1，則甲最高可能收益則甲最高可能收益70如果公司

9、甲采用策略如果公司甲采用策略1，則無論乙如何，甲最低則無論乙如何，甲最低可能收益可能收益20公司甲的公司甲的 損益損益如果公司乙如果公司乙C區(qū)，區(qū)，甲甲B C區(qū)甲收益區(qū)甲收益72第十二章：第十二章：博弈及其應用博弈及其應用 運籌學運籌學熊中楷教授熊中楷教授(2 )這個對策有兩個鞍點這個對策有兩個鞍點a11 和和 a21 公司甲的最優(yōu)純策略是公司甲的最優(yōu)純策略是 策略策略1 或者或者 策策 略略2，即在，即在A區(qū)區(qū), B區(qū)各建一個溜冰場或者在在區(qū)各建一個溜冰場或者在在A區(qū)區(qū), C區(qū)各建一個溜冰場；區(qū)各建一個溜冰場；公司乙的最優(yōu)純策略是公司乙的最優(yōu)純策略是 策略策略1， 即在即在A區(qū)建一個溜冰場。

10、區(qū)建一個溜冰場。對策值對策值V=20, 雙方最優(yōu)策略時甲公司市場份額為雙方最優(yōu)策略時甲公司市場份額為70，乙公司市場份額，乙公司市場份額為為30Max Min aij = Min Max aij = a11 = a21 =20 第十二章：第十二章：博弈及其應用博弈及其應用 運籌學運籌學熊中楷教授熊中楷教授請你按自己的思路來分析并請你按自己的思路來分析并且確定一個決策方案。且確定一個決策方案。全班分四個組討論這一個案全班分四個組討論這一個案例，派代表發(fā)言，要求有爭例，派代表發(fā)言，要求有爭論。論。第十二章：第十二章：博弈及其應用博弈及其應用 運籌學運籌學熊中楷教授熊中楷教授 已知：已知：趙妻喜歡歌

11、劇趙妻喜歡歌劇趙喜看足球趙喜看足球 趙妻看歌劇趙妻看歌劇 趙妻看足球趙妻看足球 趙趙看歌劇看歌劇妻滿意，趙不滿妻滿意，趙不滿意，兩人共周末意，兩人共周末 （2，4） 雙方失望雙方失望 （0，0） 趙趙看足球看足球不能共周末，不能共周末，雙方滿意雙方滿意 （1，1）趙滿意，妻不滿趙滿意，妻不滿意，兩人共周末意，兩人共周末 （4，2）夫妻愛好問題對策效用矩陣夫妻愛好問題對策效用矩陣趙妻得兩張今晚的歌劇票，趙得兩張今晚的足球票？趙妻得兩張今晚的歌劇票，趙得兩張今晚的足球票？第十二章：第十二章：博弈及其應用博弈及其應用 運籌學運籌學熊中楷教授熊中楷教授 清官難斷？究竟誰怕誰？清官難斷？究竟誰怕誰？當我們好不容易從奴隸到將軍，當我們好不容易從奴隸到將軍，我們的我們的“那一位那一位”卻從將軍變卻從將軍變成了元帥，我們的命是不是太成了元帥，我們的命是不是太苦了？苦了？第十二章：第十二章：博弈及其應用博弈及其應用 運籌學運籌學熊中楷教授熊中楷教授供