納什平衡的計算問題

許道云

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

納什平衡的計算問題

許道云

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

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

純博弈系統(tǒng)； 離散概型博弈系統(tǒng)； 納什平衡； 支付計算

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

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

（1）博弈論中的一些思想和結(jié)論在布爾公式可滿足性問題（SAT問題）、以及在一般約束可滿足性問題（CSP問題）中的聯(lián)系和應(yīng)用。

（2）弱納什平衡問題?；旌喜┺模ū疚姆Q概型博弈）的納什平衡總是存在的。但是，純博弈的納什平衡不一定存在。而由一個純博弈系統(tǒng)可以誘導出一個概型博弈系統(tǒng)。一種自然的想法是：如果一個純博弈系統(tǒng)的納什平衡不存在，如何從對應(yīng)的概型博弈系統(tǒng)的納什平衡近似決定原系統(tǒng)的近似納什平衡（稱為弱納什平衡問題）。

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

NE問題（Nash Equilibrium Problem）：

NE問題應(yīng)該是一個NP-完全問題。

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

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

基于上述動機，本文首先給出了博弈系統(tǒng)的形式描述，提出了概型博弈系統(tǒng)的概念，并指明通常的混合博弈實質(zhì)上是基于一個純博弈系統(tǒng)框架產(chǎn)生的擴展系統(tǒng)，博弈中的不合作性表現(xiàn)為分布之間的相互獨立性。這些有助于理解兩類系統(tǒng)之間的聯(lián)系，以及概率論方法在研究博弈論中的應(yīng)用?；诖耍怕收摰墓ぞ呖梢杂糜谟懻摳鼜碗s的博弈系統(tǒng)（如：連續(xù)型博弈系統(tǒng)等）。其次，我們對一個典型的概型博弈系統(tǒng)的納什平衡的性質(zhì)及其計算方法作了進一步的探討和研究。

1.博弈論基礎(chǔ)知識

例1 （囚犯二難問題）

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

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

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

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

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

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

NE問題：

2.離散概型博弈系統(tǒng)

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

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

例2 （囚犯二難問題對應(yīng)的概型博弈）

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

信息表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.雙人概型博弈系統(tǒng)

圖1 反應(yīng)函數(shù) R1(p2)

圖2 兩個函數(shù)合并圖

兩個函數(shù)的合并用下圖表示：

圖3 鞍點

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

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

[1]張維迎.博弈論與信息經(jīng)濟學[M].上海：上海三聯(lián)書店，上海人民出版社，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

貴州省優(yōu)秀科技教育人才省長基金。

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