圖1 戰(zhàn)略式博弈

1. 問題提出

囚徒困境（prisoner’ dilemma）_{——Tuncker 20世紀50年代}（純戰(zhàn)略）

兩 個小偷作案后被警察抓住，分別 不同的屋子里審訊。在審訊之前，小偷從律師那里得知：如果兩個人都坦白，將被各判刑4年；如果兩個人都抵賴，將會因為證據(jù)不足而各判1年；如果其中一人坦 白而另一人抵賴，坦白的將會得到寬大處理而被無罪釋放，而抵賴的將重判，判刑6年。試問兩個小偷將會如何選擇？

純戰(zhàn)略：參與人在給定信息下只選擇一種特定的戰(zhàn)略（行動）。

猜硬幣（混合戰(zhàn)略）

兩個參與人各握一枚硬幣，雙方同時選擇是正面向上（記作O）還是背面向上（記作R），即他們的戰(zhàn)略空間都是{O，R}。若兩枚硬幣是一致的（即全部背面向上或者全部正面向上），參與人2贏得參與人1的硬幣；若兩枚硬幣不一致，則參與人1贏得參與人2的硬幣。

混合戰(zhàn)略：參與人在給定信息下以某種概率分布隨機地選擇不同的行動（戰(zhàn)略空間上的概率分布）。解釋了一個參與人對其他參與人所采取行動的不確定性。

在一個給定的n人戰(zhàn)略式博弈中，對于任一參與人，設(shè)，則參與人i的一個混合戰(zhàn)略為定義在戰(zhàn)略集上的一個概率分布，其中表示參與人i選擇戰(zhàn)略的概率，即滿足：且。

2. 問題描述——戰(zhàn)略式博弈

戰(zhàn)略式博弈（strategic form game）：也稱標準式博弈，是一種相互作用的決策模型，這種模型假設(shè)每個參與人僅選擇一次行動或行動計劃（戰(zhàn)略），并且這些選擇是同時進行的。

適用：不需要考慮博弈過程的完全信息博弈問題(特別是完全信息靜態(tài)博弈)

戰(zhàn)略式博弈三要素：

1) 參與人集合

2) 每位參與人非空的戰(zhàn)略集，即

3) 每位參與人定義在所有戰(zhàn)略組合上的偏好關(guān)系或者效用函數(shù)

有限博弈：（參與人人數(shù)有限）且，（每個參與人的戰(zhàn)略數(shù)有限），記為或

“囚徒困境”博弈戰(zhàn)略式描述：

表1 “囚徒困境”戰(zhàn)略式描述

“猜硬幣”戰(zhàn)略式描述：

表2 “猜硬幣”戰(zhàn)略式描述

3. 問題的解——Nash均衡（純戰(zhàn)略）、混合戰(zhàn)略Nash均衡（混合戰(zhàn)略）

1) 重復(fù)剔除劣戰(zhàn)略行為（化簡原博弈問題）

在n人博弈中，如果對于參與人i，存在戰(zhàn)略，對，有，則稱戰(zhàn)略為參與人i的劣戰(zhàn)略（嚴格劣戰(zhàn)略），或者戰(zhàn)略相對于占優(yōu)；有，且，使得，則稱戰(zhàn)略為參與人i的弱劣戰(zhàn)略。

參與人i將會把從中剔除掉，直接從戰(zhàn)略集中選擇自己的戰(zhàn)略。------------------------->，其中

注：如果每次剔除的是嚴格劣戰(zhàn)略，均衡結(jié)果與剔除順序無關(guān)；如果剔除的是弱劣戰(zhàn)略，均衡結(jié)果可能與剔除順序有關(guān)。

2) 純戰(zhàn)略——Nash均衡（Nash Equilibrium）_{——John Nash 20世紀50年代}

在一個給定的n人戰(zhàn)略式博弈中，戰(zhàn)略組合是一個Nash均衡，當且僅當，時，有或者，。

3) 混合戰(zhàn)略——混合戰(zhàn)略Nash均衡

在一個給定的n人戰(zhàn)略式博弈中，混合戰(zhàn)略組合為一個Nash均衡，當且僅當，，有。

支撐求解法

支撐（記為）是指參與人按照選擇戰(zhàn)略時，純戰(zhàn)略組合中以大于0的概率出現(xiàn)的所有純戰(zhàn)略組合的集合，即

有限n人戰(zhàn)略式博弈的支撐求解法：

1) 構(gòu)造出所有的混合戰(zhàn)略均衡的支撐。

2) 對于每個給定的支撐，求解如下方程組。

3) 驗證方程組的解。

a) 解都大于0。即

b) 不存在一個不屬于支集的戰(zhàn)略，給定其他參與人的戰(zhàn)略，參與人i采用所得到的期望效用大于采用支集中戰(zhàn)略的期望效用。即但，

規(guī)劃求解法

將求解博弈的混合戰(zhàn)略Nash均衡轉(zhuǎn)換為對一個規(guī)劃問題進行求解。

有限n人戰(zhàn)略式博弈的規(guī)劃求解法：

Wilson奇數(shù)定理（oddness theorem）：幾乎所有的有限戰(zhàn)略式博弈都有有限奇數(shù)個Nash均衡。

參考文獻：

[1] 羅云峰. 博弈論教程. 北京: 清華大學出版社, 北京交通大學出版社, 2007.