許道云

（ 貴州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，貴州 貴陽(yáng) 550025 ）

納什平衡的計(jì)算問(wèn)題

許道云

（ 貴州大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，貴州 貴陽(yáng) 550025 ）

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

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

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

我們感興趣如下問(wèn)題的研究：

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

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

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

NE問(wèn)題（Nash Equilibrium Problem）：

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

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

（4）計(jì)算納什平衡（如果存在）的有效算法及計(jì)算復(fù)雜性。

基于上述動(dòng)機(jī)，本文首先給出了博弈系統(tǒng)的形式描述，提出了概型博弈系統(tǒng)的概念，并指明通常的混合博弈實(shí)質(zhì)上是基于一個(gè)純博弈系統(tǒng)框架產(chǎn)生的擴(kuò)展系統(tǒng)，博弈中的不合作性表現(xiàn)為分布之間的相互獨(dú)立性。這些有助于理解兩類系統(tǒng)之間的聯(lián)系，以及概率論方法在研究博弈論中的應(yīng)用?；诖?，概率論的工具可以用于討論更復(fù)雜的博弈系統(tǒng)（如：連續(xù)型博弈系統(tǒng)等）。其次，我們對(duì)一個(gè)典型的概型博弈系統(tǒng)的納什平衡的性質(zhì)及其計(jì)算方法作了進(jìn)一步的探討和研究。

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

例1 （囚犯二難問(wèn)題）

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

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

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

自然地，我們會(huì)提出如下兩個(gè)問(wèn)題：

（1）納什平衡的存在性判定問(wèn)題；（2）如果納什平衡存在，如何計(jì)算？

對(duì)于問(wèn)題（1），我們建立如下判定問(wèn)題：

NE問(wèn)題：

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

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

我們?cè)诖朔Q為離散概型博弈，是因?yàn)樵陔x散策略集上引入了概率分布，從如下的討論將會(huì)看到：形式上我們將以概率分布代替策略先擇，以分布下的數(shù)學(xué)期望表示支付。

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

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

信息表T可以改寫(xiě)為：

乙甲 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 兩個(gè)函數(shù)合并圖

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

圖3 鞍點(diǎn)

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

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

[1]張維迎.博弈論與信息經(jīng)濟(jì)學(xué)[M].上海：上海三聯(lián)書(shū)店，上海人民出版社，2004.

[2]俞建.博弈論與非線性分析[M].北京：科學(xué)出版社，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

（責(zé)任編輯 王婷婷）

TP301.5

A

1673-9639 (2010) 01-0131-08

2009-01-19

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

許道云（1959-），男，博導(dǎo)，教授，主要研究領(lǐng)域?yàn)橛?jì)算復(fù)雜性，可計(jì)算分析。