納什平衡的計算問題

許道云

（ 貴州大學 計算機科學與技術學院，貴州 貴陽 550025 ）

納什平衡的計算問題

許道云

（ 貴州大學 計算機科學與技術學院，貴州 貴陽 550025 ）

本文介紹了博弈的形式描述系統，混合博弈實質上是基于純博弈系統框架下在策略集上引入概率分布。局中人之間的不合作性表現分布之間的獨立性。給出了囚犯二難概型博弈系統與其純博弈系統納什平衡之間的聯系，并對概率納什平衡的計算進行了討論。

純博弈系統； 離散概型博弈系統； 納什平衡； 支付計算

博弈論的產生背景主要源于經濟學中經濟行為沖突的量化分析與行為推斷[1]。隨著不同博弈系統（模型）的提出以及在其它領域的應用，人們開始注意到：博弈論的應用不僅局限于經濟領域。除了經濟學家以外，數學家和計算機科學家對博弈論的基本理論、數學描述、應用聯系展開了更加深入的研究。如：參考文獻[2]用非線性分析方法對納什平衡的存在性及性質展開系統研究，參考文獻[3]則將納什平衡與（優先）邏輯程序的回答集相聯系，等等。

我們感興趣如下問題的研究：

（1）博弈論中的一些思想和結論在布爾公式可滿足性問題（SAT問題）、以及在一般約束可滿足性問題（CSP問題）中的聯系和應用。

（2）弱納什平衡問題。混合博弈（本文稱概型博弈）的納什平衡總是存在的。但是，純博弈的納什平衡不一定存在。而由一個純博弈系統可以誘導出一個概型博弈系統。一種自然的想法是：如果一個純博弈系統的納什平衡不存在，如何從對應的概型博弈系統的納什平衡近似決定原系統的近似納什平衡（稱為弱納什平衡問題）。

（3）納什平衡判定問題。純博弈的納什平衡不一定存在。于是自然有如下判定問題：

NE問題（Nash Equilibrium Problem）：

NE問題應該是一個NP-完全問題。

我們關心的是：哪種類型，或在何種充分條件下，納什平衡必然存在？

（4）計算納什平衡（如果存在）的有效算法及計算復雜性。

基于上述動機，本文首先給出了博弈系統的形式描述，提出了概型博弈系統的概念，并指明通常的混合博弈實質上是基于一個純博弈系統框架產生的擴展系統，博弈中的不合作性表現為分布之間的相互獨立性。這些有助于理解兩類系統之間的聯系，以及概率論方法在研究博弈論中的應用。基于此，概率論的工具可以用于討論更復雜的博弈系統（如：連續型博弈系統等）。其次，我們對一個典型的概型博弈系統的納什平衡的性質及其計算方法作了進一步的探討和研究。

1.博弈論基礎知識

例1 （囚犯二難問題）

設有甲、乙兩人共同犯罪，被囚于不同房間。兩人都知道獲刑規則：如果兩人都坦白，各被判2年監禁；如果兩人都保持沉默（抵賴），各被判1年監禁；如果一個坦白，另一個抵賴，坦白者可以釋放，抵賴者被判3年監禁。甲、乙之間進行博弈，如何選擇自己的策略，才能使被監禁時間最短。

乙甲C2 F2 C ( )2 1? ( )3 2,?0,?F ( )0 1? ( )1 3,?1,?

請注意：純博弈系統的納什平衡可能不存在，即使存在，也可能不唯一。

自然地，我們會提出如下兩個問題：

（1）納什平衡的存在性判定問題；（2）如果納什平衡存在，如何計算？

對于問題（1），我們建立如下判定問題：

NE問題：

2.離散概型博弈系統

在純博弈系統G=(A,T,{S1,…,Sn})的基礎上，我們考慮在策略集上引入一個概率分布，從而引入離散概型博弈。通常稱為混合博弈（參見參考文獻[1]和參考文獻[2]）。

我們在此稱為離散概型博弈，是因為在離散策略集上引入了概率分布，從如下的討論將會看到：形式上我們將以概率分布代替策略先擇，以分布下的數學期望表示支付。

例2 （囚犯二難問題對應的概型博弈）

（1）以例1中的純策略博弈系統為基礎框架。在策略集上引入概率分布。

信息表T可以改寫為：

乙甲 P2 1?P2 CF2 2 CP1 ( )2 1? ( )3 2,?0,?F1 1?P ( )0 1? ( )1 3,?1,?

A B CF2 2 C ( )b 1?, ( )d b? ? a ,?F ( )a 1? , ( )c d? ?c,?

B AP2 1?P2 CF2 2 CP1 ( )b 1?, ( )d b? ? a ,?F 1?P1 ( )a 1? , ( )c d? ?c,?

信息表T為：

乙甲 P2 1?P2 CF2 2 CP1 ( )8 1? ( )10 8,? ?2,?F1 1?P ( )2 1? ( )5 10,? ?5,?

3.雙人概型博弈系統

圖1 反應函數 R1(p2)

圖2 兩個函數合并圖

兩個函數的合并用下圖表示：

圖3 鞍點

納什平衡幾何上表現為三維空間中曲面的“鞍點”。從下圖看出："鞍點"表現為一個穩定點。

本文首先給出了博弈系統的形式描述，混合博弈實質上是基于純博弈系統框架下在策略集上引入概率分布。局中人之間的不合作性表現分布之間的獨立性。這有助于理解兩類系統之間的聯系，以及概率論方法在研究博弈論中的應用。此外，我們還對一個典型的概型博弈系統的納什平衡的性質及其計算方法作了進一步的探討和研究。

[1]張維迎.博弈論與信息經濟學[M].上海：上海三聯書店，上海人民出版社，2004.

[2]俞建.博弈論與非線性分析[M].北京：科學出版社，2008.

[3]N. Foo, T. Meyer, and G. Brewka. LPOD answer sets and Nash equilibra[M].. Avvance in Computer Science, 9thAsian Computer Science Conference, LNCS 3321: 343-351,2004.

Calculation of Nash Equilibrium

XU Dao-yun
( College of Computer Science and Technology, Guizhou University, Guiyang, Guizhou 550025, China )

This paper describes formal-description system of the game; mixed game essentially means introducing probability distribution to strategy sets based on the framework of pure game system. Non-cooperativeness among players shows the distribution independence. It gives the connection between prisoner’s dilemma scheme game system and Nash equilibrium of pure game system, and makes a discussion on the calculation of probability Nash equilibrium.

pure game system; discrete scheme game system; Nash equilibrium; payment calculation

（責任編輯 王婷婷）

TP301.5

A

1673-9639 (2010) 01-0131-08

2009-01-19

貴州省優秀科技教育人才省長基金。

許道云（1959-），男，博導，教授，主要研究領域為計算復雜性，可計算分析。