組合博弈(1) - 組合博弈引論

博弈論的一個關鍵問題是透過分析各玩家可能的策略組合來預測最終的遊戲局面。由於絕大多數博弈的過程受到隨機因子的干擾，或者其收益計算體系複雜，使得僅僅給定這些博弈的一個初始狀態時無法唯一確定其最終結果。但如果一類博弈的收益計算足夠簡單（比如只包括輸贏兩種收益），且其策略是確定的，那麼即使僅給出初始狀態，我們也能夠準確預測它們的結果。組合博弈就屬於這樣一類博弈。為了建立一套判斷組合博弈結果的完整理論體系，我們需要先將一些用語嚴格化。本章即致力於引入組合博弈的一些基本術語和記號，並初步探究其簡單的性質。

§1.1 組合博弈

假設兩個玩家（不妨把他們稱為左玩家和右玩家）玩一個遊戲。他們按照某個雙方都已熟知（完全資訊）的規則輪流進行操作，其中不包含任何隨機過程，並且遊戲終將結束（無法進行操作時認為遊戲結束），此時按照另一套特定的規則判定雙方的勝負，不存在平局，同時確保勝負的判定是唯一的（即勝負僅由子狀態決定），則稱這個過程為一個

組合博弈

。

將組合博弈中的任何一個局面稱為一個

狀態

。對於狀態

，我們定義集合

，

分別為左，右玩家對

操作之後所有可能狀態構成的集合，並稱它們為

的

左,右集合

，其中的元素稱為

的

(左,右)子狀態

。我們採用記號

$g=\left(G^L|G^R\right)$

。這種表示方法稱為狀態

的左右集合表示。稱狀態

和

全等

，記作

，若它們的左集合與右集合對應相等，此時它們顯然有相同的左右集合表示。

當我們用

，

中的元素表示

時，我們可以將集合的花括號略去不寫（這當然不會引起任何歧義），像是這樣：

$g=\left( G^L|G^R \right)=\left( \left\{ g_1^L,g_2^L,\dots \right\}|\left\{ g_1^R,g_2^R,\dots \right\} \right)=\left( g_1^L,g_2^L,\dots |g_1^R,g_2^R,\dots \right)$

容易看出，當

，

均非空時，狀態

的性質完全由

，

中的元素決定；而當

，

中至少有一個為空集時，遊戲有可能在狀態

時終止。

特別地，當

$G^L=G^R=\varnothing$

時，稱

為博弈的一個零點。

我們定義一個狀態的

天數

為

$\mathcal{D}$

，它由下面的表示式給出：

（1）若

為零點，則

$\mathcal{D}(g)=0$

；

（2）若

不為零點，則

$\mathcal{D}(g)=\max\left\{ \mathcal{D}(p) | p \in G^L\cup G^R \right\}+1$

。

當我們由簡單到複雜地構造出一個組合博弈的所有局面時，我們先構造出所有的零點，再由此不斷迭代構造出新的狀態，那麼

$\mathcal{D}(g)$

就是一個狀態被構造出的迭代深度。這個概念的引入，使我們得以用歸納法證明一些重要結論。如果一個狀態

有著有限的天數，則我們稱

為有限狀態，否則稱之為無限狀態。

類似地，我們定義一個狀態的複雜度為

$\mathcal{C}(x)$

，它由下面的表示式給出：

$\mathcal{C}(g)=\sum_{p∈G^L∪G^R}\mathcal{C}(p) +1$

當我們由簡單到複雜地構造出一個組合博弈的所有局面時，

$\mathcal{C}(g)$

就表達了一個狀態被構造出來時其表示式中一共含有的狀態數。對於任意博弈系統中某個等價關係

$\sim$

下的等價類

$\bar{g}$

，如果代表元

的複雜度是該等價類

$\bar{g}$

中所有元素複雜度的最小值，則稱

是該等價關係

$\sim$

下的一個最簡式。複雜度和最簡式的概念將有助於我們標準化一些博弈系統。

給定狀態

，從任何一個玩家開始操作，都有且僅有一個玩家必勝（指有必勝策略，下同）。用命題

表示“左玩家有後手必勝策略”，

表示“右玩家有後手必勝策略”，類似地用

和

表示對應的玩家有先手必勝策略。我們有

命題 1.1

$LN(g)\Leftrightarrow\neg RP(g), RN(g)\Leftrightarrow\neg LP(g)$

證明

由定義直接得到。

將四個命題兩兩組合，我們又可以得到下面四個命題：

$L(g)\Leftrightarrow LP(g)\wedge LN(g), R(g)\Leftrightarrow RP(g)\wedge RN(g)$

$P(g)\Leftrightarrow LP(g)\wedge RP(g), N(g)\Leftrightarrow LN(g)\wedge RN(g)$

它們對應的意義分別為“左玩家必勝”“右玩家必勝”“先手必勝”和“後手必勝”。上述定義的四個命題中，每兩個之間都蘊含著一對由命題 1。1 給出的互斥命題，因而這四個命題中有且僅有一個正確，我們稱之為狀態

的結果，記為

，其取值為

中的一個。為了計算

，我們事實上只需判斷

和

兩個命題的真假。下面的命題可以幫助我們計算這兩個值。

引理 1.2

當且僅當滿足下列兩項之一時，

為真：

（1）

$G^R=\varnothing$

且由勝負判定知左玩家後手勝；

（2）

$\forall x\in G^R, LP(x).$

互換所有

可得

的判定方法，再結合命題 1。1 可得

的判定方法。

證明

$G^R=\varnothing$

的情形顯然。下證

$G^R\ne\varnothing$

的情形。

充分性：若

$\forall x\in G^R,LP(x)$

，則當右玩家將

操作成

時，左玩家只需按照

的先手必勝策略即可贏得遊戲。

必要性：若

$\exists x\in G^R, \neg LP(x)$

，則右玩家只需將

操作成

，由於

為假，故

為真，右玩家有

的後手必勝策略，因此右玩家必勝。

綜上，我們得到了

等命題的判定方法，由此我們給出

的簡單判定方法：

定理 1.3 (子狀態判別法)

若

，

均非空，則

由下面的判定給出：

$L:(\exists LN|\forall LP), R:(\exists RP|\forall RN)$

$N:(\forall RP|\forall LP), P:(\exists LN|\exists RN)$

其中，

$\exists LN$

指

$\exists x\in G^L,LN(x)$

，其餘類似。

證明

由引理1。2直接得到。

這個判定方法十分簡明，卻迴避了

，

中有空集的情況。我們不禁設想：如果把定理1。3中的“

，

均非空”的限制去掉，情況會變成怎樣呢？這將是我們在之後重點討論的一類博弈，那時我們將看到，這類博弈有許多優美的性質。

習題 1.1

1。假設

$LP(x),LP(\xi),RP(y),RP(\eta),LN(z),LN(\zeta),RN(p),RN(\pi)$

都是真命題，判斷下列狀態：

（i）

。

（ii）

$g=(y|\pi,\zeta)$

。

（iii）

$g=\left(\left( |p,x \right),(z,\eta|\pi)|(y,\eta|\xi),x\right)$

。

2。設有一博弈的勝負判定規則為：最先無法行動的一方判負。

$\theta$

是該博弈的一個零點。分別計算：

$o(\theta),o((\theta|)),o((|\theta)),o((\theta|\theta))$

3。判斷下列博弈是否為組合博弈：

（i）兩個玩家輪流從一堆排成

$6\times 6$

方陣的棋子中選一枚取走，每次選取的棋子由玩家自己決定。取完一枚棋子後，將其四周的棋子也全部取走（不再取走這些棋子四周的棋子）。最先不能行動的玩家判負。

（ii）兩個玩家輪流從一堆排成

$6 \times 6$

方陣的棋子中選一枚取走，每次選取的棋子透過擲兩次骰子決定：第一次決定抽取的行，第二次決定抽取的列。最先不能按骰子給定點數抽取棋子的玩家判負。

（iii）兩個玩家輪流從一堆記有分數的棋子中選一枚取走，這些棋子分佈在一個方陣中且形成一個連通圖。從第二名玩家的第一次抽取開始，每次抽取的棋子必須與另一名玩家上次抽取的棋子相鄰。取完全部棋子後，統計每名玩家棋子上的分數和，分數更大者判勝。若兩名玩家抽取的棋子分數和相等，則判平局。

4。證明：若

，則

$\mathcal{D}(g)=\mathcal{D}(h)$

。逆命題一般不成立，請給出反例。當

$\mathcal{D}(g)$

，

$\mathcal{D}(h)$

還滿足什麼條件時，逆命題成立？

§1.2 加法和結果等價

在兩個狀態

上同時進行博弈，並規定每次只能選擇其中的一個狀態進行操作，這個規則顯然定義了一個狀態。我們定義這個運算規則為

(狀態的)加法

，由此規則生成的狀態為

與

的

和狀態

（或簡稱為它們的

和

），記作

。可以想見，

的左右集合表示應當為

需要指出的是，這裡的

指的是陪集

$\left\{ g+h|g\in G^L \right\}$

， “

”指的是這兩個陪集的並，其他記號同理。今後若無特殊說明，我們預設採用這種簡記約定。

一般地，

的左（右）集合非空，當且僅當

和

的左（右）集合都非空（證明是顯而易見的）。因此，若狀態

的左右集合均非空，我們已經能夠依據定理 1。3 判斷其結果，否則我們仍然需要引入

的勝負判定才能判斷其結果。特別地，

是零點當且僅當

都是零點。

命題 1.4

對於加法，我們有如下的定理：

（i）若

是博弈零點，則

。

（ii）

。

（iii）

。

證明

（i）對天數歸納。若

$\mathcal{D}(h)=0$

，則

是博弈零點，從而

。假設結論對小於

$\mathcal{D}(h)$

的情形成立，則

。

（ii）對天數歸納。當

$\mathcal{D}(g)+\mathcal{D}(h)=0$

時，由天數的非負性只能有

$\mathcal{D}(g)=\mathcal{D}(h)=0$

，即

和

都是博弈零點，從而

都是博弈零點，自然有

。

假設結論對小於

$\mathcal{D}(g)+\mathcal{D}(h)$

的情形成立。則由歸納假設，

從而

與

有相同的左右集合表示，故

。

（iii）對天數歸納。若

$\mathcal{D}(g)+\mathcal{D}(h)+\mathcal{D}(k)=0$

。由類似上面的討論可以證明我們的結論。假設結論對小於

$\mathcal{D}(g)+\mathcal{D}(h)+\mathcal{D}(k)$

的情形成立，則有

$\begin{aligned} (g+h)+k&=(G^L+h,g+H^L|G^R+h,g+H^R)+k\\ &=((G^L+h)+k,(g+H^L)+k,(g+h)+K^L|(G^R+h)+k,(g+H^R)+k,(g+h)+K^R) \end{aligned}$

對天數歸納可知，上面最後一個式子與

是相等的，而該式正是

的左右集合表示，從而

。

注：上述（i）（ii）（iii）與數的加法的么元，交換律和結合律很相似，但它們不是嚴格意義上的么元，交換律和結合律，這是因為我們採用的

記號的意義是全等，而狀態的相等我們尚未定義。我們甚至暫時都不能確定在可能定義的相等意義下零點的唯一性。

可以看出，狀態加法和傳統的數的加法有許多相似的性質。我們對一類特定的和狀態感興趣，即對兩個狀態

求和後得到博弈零點。假設狀態

已給定，我們來先從直觀的博弈角度來”猜測”狀態

的左右集合表示應當具有的形式。

由於

與

求和應形成博弈零點，那麼

和

的局面應該是關於左右玩家對稱的，或者說，是對偶的。對於右玩家在狀態

下可能採取的任一策略，左玩家應當在狀態

下能找到一個對應策略來與之”抵消”，這樣的策略必然與右玩家的策略是對偶的。由右玩家策略選取的任意性，整個

和整個

應該是對偶的。同理，

和

也應當是對偶的。這意味著，一旦和狀態為博弈零點的兩個狀態

的關係被確定，那麼其中一個狀態左集合中的每個元素必然與另一個狀態右集合中的元素一一對應地同樣擁有這種關係。以這樣的直觀印象為基礎，我們給出下面的定義：稱

為

的對偶狀態（或簡稱對偶）。狀態

和

的減法，是指狀態

和

的加法，其產生的狀態稱為

對

的差狀態（或簡稱為

和

的差），記作

。由上面的定義馬上知道

。與加法類似，我們也顯然有

是零點當且僅當

是零點。

作為本節的結束，我們給出以下關於對偶和減法的簡單命題：

命題 1.5

對於對偶和減法，我們有下面的定理：

（i）

。

（ii）

。

（iii）若

，則

；若

，則

；其餘情況下

。

證明

（i）對天數歸納，當

$\mathcal{D}(g)=0$

時，

是零點，故

和

也都是零點，從而

。若結論對小於

$\mathcal{D}(g)$

的情形都成立，則

$\begin{aligned} -g&=(-G^R|-G^L)\\ -(-g)&=(-(-G^L)|-(-G^R)) \end{aligned}$

由歸納假設，

，故

成立。

（ii）這個證明留給讀者。

（iii）顯見該結論等價於：

$LN(g)\Leftrightarrow RN(-g),LP(g)\Leftrightarrow RP(-g)$

。由簡單的歸納知

$\mathcal{D}(g)=\mathcal{D}(-g)$

，因此我們可以對天數進行歸納，當

$\mathcal{D}(g)=0$

時，結論自然成立；假設結論對小於

$\mathcal{D}(g)$

的情形成立，則

$LP(g)\Leftrightarrow\exists x\in G^L,LN(x)$

，從而由歸納假設，

為真。又由於

$-x\in (-g)^R$

，故

為真。而

$LN(g)\Leftrightarrow RN(-g)$

是上述命題的逆否命題，自然也成立。

上述命題無疑是刻畫出了博弈系統中的減法性質，但應當指出，對於狀態

，

一般不是博弈零點。為了彌補這個缺憾，我們將會定義一種比全等條件弱的等價關係。在下一節中我們會給出它的一種定義。

給定狀態

和

，若對於任何狀態

有

，則稱

結果等價，記為

$g\equiv h$

。我們有下面的命題：

命題 1.6

對於結果等價，我們有下面的結論：

（i）

$g=h\Rightarrow g\equiv h$

。

（ii）

$\equiv$

是等價關係。

（iii）

$g\equiv h\Leftrightarrow g+k\equiv h+k$

。

證明

（i）由 §1。1 中勝負判定的唯一性可知結論成立。

（ii）自反性：由（i）可知。

對稱性：

$g\equiv h\Rightarrow\forall k,o(g+k)=o(h+k)\Rightarrow h\equiv g$

。

傳遞性：

$g\equiv h,h\equiv k\Rightarrow\forall t,o(g+t)=o(h+t)=o(k+t)\Rightarrow g\equiv k$

。

（iii）

$g\equiv h\Leftrightarrow\forall k,t,o(g+k+t)=o(h+k+t)\Leftrightarrow g+k\equiv h+k$

。

推論

$a\equiv b,g\equiv h\Rightarrow a+g\equiv b+h$

。

命題 1。4 自然地給出了任何博弈系統

$\mathbb{P}$

（即特定規則下所有可能狀態構成的代數系統）的一個么半群

$(\mathbb{P},+)$

。而命題 1。6 則指出該么半群商掉結果等價後仍然是么半群。倘若上一節最後的問題在結果等價的意義上得以解決（即證明任何狀態與其對偶的和結果等價於博弈零點），則它還是一個群。組合博弈的本質事實上就是研究上述（半）群及它們的子（半）群滿足的性質。我們會在後面的章節中討論它上面更為精細的代數結構。

習題 1.2

定義

個

的和狀態為

。證明：

。

證明命題 1。5（ii）。

設有一博弈的勝負判定規則為：最先無法行動的一方為勝者。

$\theta$

是該博弈的一個零點，且定義

$\delta=(\theta|\theta)$

。證明：當

為奇數時，

$n\delta\equiv\delta$

；當

為偶數時，

$n\delta\equiv\theta$

。

1.25 更新：回答一些提問

問題1: 如何理解 P,N,L,R 四個字母?

一般來說對於 L（Left，左玩家）和 R（Right，右玩家）大家都不會有什麼誤會。不過有關 P 和 N 大家的想法就比較多樣了。有人會認為是 Positive 和 Negative。這麼理解當然沒有問題，但是我這裡參考的是 Conway 的表示方法，即用 Previous 表示先手， Next 表示後手。順便說一句，在後面的某個地方我還會將 P，N 作為正和負的 neta 用起來的。（笑）

一開始的文章中可能有一些地方因為筆誤寫反了，這裡向大家表示萬分抱歉！

問題2: 博弈的左右集合能包含博弈狀態本身嗎? 如果出現了可能導致局面復原的情形, 如圍棋的打劫, 這還能算組合博弈嗎?

第一個問題的答案是不行。這是集合論告訴我們的事情。局面復位也違背了“遊戲終將結束”的假設。但是根據圍棋規則，打劫是不能立即提回的。也就是說，打劫的局面是帶狀態的（即此時能否提回），即使局面復位了，只要狀態不同也應該算作不同的博弈局面。不過嚴格地說的話，如果存在三劫連環的局面，這就是真正能復位的情形了。在圍棋史上，的確有過因為三劫連環而判平局的例子，這違背了組合博弈“不存在平局”的假定。因此如果不限制三劫連環的話，圍棋是不能算作組合博弈的。

順便說一下， “遊戲終將結束”不代表“遊戲在有限步”終將結束。就像“不存在包含自己的集合”不代表“不存在深度為無窮的集合”一樣。

問題3: 如何理解天數和複雜度的概念? 這兩個概念的意義何在?

Knuth 有一本書名叫《數學之美》，講的是一男一女在一個孤島上發現了幾塊寫有數學公理的石板，從而開啟了研究之路（然後幸福地生活在了一起）的故事。而這些公理本身就是 Conway 發現的，我的“天數”一詞也由此而來。想象一位神正在創造數學。每一天他都把之前出現過的所有數構成的集合的子集用來造數，如果兩個子集中含有昨天才出現的數，那麼它是今天才出現的，否則之前就已經被創造過了。這便是天數的直觀理解。

複雜度的概念遠遠沒有天數重要。它的意義僅僅是讓我們在尋找數的某種形式時提供一種參考。當我們把數按照某種等價關係分成多個類時，如果可以證明每個類中存在唯一的數具有最小的複雜度，那麼將這個數作為代表元就是很好理解的了。

下一期：

小蜜蜂問答

小蜜蜂問答

組合博弈(1) - 組合博弈引論

推薦文章

小蜜蜂問答

小蜜蜂問答

組合博弈(1) - 組合博弈引論

相關文章

新麥醒發箱怎樣設定醒發時間？

顯著和顯然的區別？

黃海高程與正負零怎樣換算

校園外賣存在的利與弊，現在該朝哪個方向發展？

推薦文章