在之前的討論中，一場游戲只有一個智能體。而在博弈論中，智能體評估它們的決策如何與其他人的決策相互作用以產(chǎn)生不同的結(jié)果。

簡單博弈

看一個具體的博弈游戲：

image

圓圈中的數(shù)字代表一個狀態(tài)。L/R/M 代表智能體可采取的動作。葉子節(jié)點(diǎn)的數(shù)字代表智能體 A 的得分（B的得分是相反數(shù))

首先 A 做出一個選擇（動作），隨后 B 做出一個動作，然后 A 可視情況再次做出一個動作。

博弈論一個基本前提是：假設(shè)所有玩家都想最大化自己的得分，并都可以正確做出最佳動作，并都相信其他玩家也會這樣做。

這是博弈問題最簡單的一種：兩個玩家的零和有限確定性完美信息博弈。

• 兩個玩家：顧名思義，就是在這個博弈游戲中只有2個玩家（智能體）。
• 零和：兩個玩家獲得的獎勵（得分）之和是一個常量。（不一定為0）
• 有限性：顯然，這場博弈的一切元素例如：狀態(tài)、動作等都是有限的。
• 確定性：從 MDP 角度理解，即博弈中沒有隨機(jī)轉(zhuǎn)換。從某一狀態(tài)采取某一動作得到的結(jié)果是確定的。
• 完美信息：我們能夠確定當(dāng)前智能體所處的狀態(tài)。
  

STRATEGIES（策略）

在 MDP 中有個名詞叫 POLICIES （策略），它是狀態(tài)到動作的映射。博弈論中有類似的概念，稱為 STRATEGIES （策略），它是所有可能的狀態(tài)到動作的映射。

對于 A 來說 (1→L, 4→L) 就是一個策略。不難看出，在這個特定的游戲中，A 有4個策略，B 有3個策略，如下：（這種策略被稱為純策略）

A:
(1→L, 4→L)  (1→L, 4→R)
(1→R, 4→L)  (1→R, 4→R)

B:
(2→L, 3→R)  (2→M, 3→R)  (2→R, 3→R)

我們可以以表格的形式寫出這些策略，并在中間填入最后的得分。（由于B得分是A的相反數(shù)，所以這里省略B）

image

最終可以得到一個矩陣（紅框部分），這個矩陣包含了此場博弈的一切信息，即：有了它我們不再需要一開始的博弈樹了。

極小極大原理

試想這樣一個游戲過程：

A 為了最大化得分，也許會選擇策略 (L,L) 或策略 (L,R) ，也就是矩陣的前兩行。因?yàn)橹挥羞@樣才有可能得到最高分7.
然而 B 同樣希望最大化自己的得分，所以在 A 先選擇的情況下，B 自然會選擇當(dāng)前狀態(tài)下對自己最有利的。例如當(dāng) A 選擇 (L,L)，B 就會選擇 (R,R). 最后 A 得分 -1.
于是 A 沒有達(dá)到一開始的目標(biāo)。

A 總是最大化得到的分?jǐn)?shù)，而 B 總是試圖最小化 A 可以得到的分?jǐn)?shù)。所以得出這樣一個結(jié)論：A 先手時必須要考慮會遭遇 B 最嚴(yán)酷的反制策略。所以選擇 (L,L) 是非常不明智的。事實(shí)上若交換 AB 角色，結(jié)論是一樣的。

在這個結(jié)論的指導(dǎo)下，A 要選擇的并不是全局最大值，而是在 B 執(zhí)行反制策略（找到極小值）后得到盡可能大的值。也就是：極大化極小值。相反，B 要找到極小化極大值。（因?yàn)橹翟叫?B 得分越高）

所以正確的博弈過程是這樣的：

A 選擇 (L,R), B 選擇 (M,R)，最后 A 得分3.
即使是 B 先手，B 也應(yīng)該選擇 (M,R)，隨后 A 選擇 (L,R)，最終 B 得分-3. 雖然 B 依然失敗，但它已經(jīng)盡可能拿到了最高的分?jǐn)?shù)。

從這個過程可以得出一個結(jié)論：極大化極小值和極小化極大值最終的結(jié)果是一樣的。

極小極大原理也就是 Von neumann 定理（馮諾依曼定理）。

不確定性的博弈

前面所述簡單博弈具有確定性，現(xiàn)在我們?nèi)∠@一約束。看一個具體的游戲：

image

和之前很類似，但 A 在第一個狀態(tài)采取動作 L 之后，有0.5的概率獲得4分，也有0.5的概率獲得-20分。這就是不確定性。

同樣的，只需要用概率乘以得分再求和，也可以寫出一個博弈矩陣：

image

隱藏信息博弈

前面所述博弈是完美信息，現(xiàn)在我們?nèi)∠@一約束成為兩個玩家的零和有限隱藏信息博弈。

看一個具體的游戲：

A 摸一張卡片，可能是紅色或黑色，概率各是50%. （對于 A 來說紅色是懲罰黑色是獎勵）
A 可以選擇棄牌或保留。若棄牌則失去20元。
若 A 保留，B 可以棄權(quán)或要求亮牌。若 B 放棄則 A 獲得10元。
若 B 要求亮牌，若是紅色則 Ａ 失去40元；若是黑色 A 獲得30元。
對于一個博彩游戲，A 失去也就是意味著 B 獲得，所以是零和的。

image

因?yàn)?B 不知道 A 抽到的是什么顏色，故不知道自己處在哪一狀態(tài)，也就是隱藏信息。

同樣的可以得到一個矩陣：

image

不難看出，在這場博弈中，Von neumann 定理不再有效了，它無法在不同情況下得出一個確定的結(jié)果。

混合策略

混合策略與純策略的區(qū)別就是，需要指定選擇不同策略的概率。如此看，純策略是特殊的混合策略，其選擇某一策略的概率是100%.

令 A 選擇留牌的概率是 p，那么當(dāng) B 選擇棄權(quán)時，A 的預(yù)計收益是 .
當(dāng) B 選擇亮牌時，A 的預(yù)計收益是 .

不難看出這是2個關(guān)于p的函數(shù)，可以把它畫出來：

image

由于 B 始終希望最小化 A 的獎勵，所以 A 實(shí)際的獎勵函數(shù)應(yīng)該是取最小的部分（下圖紅色部分），也就是極大化極小值。
同樣的，黃色部分是極小化極大值。他們最終應(yīng)該選取的點(diǎn)相同。

image

非零和

前面所述博弈是零和的，現(xiàn)在我們再取消這一約束成為兩個玩家的非零和有限隱藏信息博弈。

同樣，先看一個具體的博弈：

兩個嫌疑人因搶劫被抓獲，被隔離審訊。若其中一人背叛同伙而向警方檢舉另一個人，他將獲得釋放，被檢舉的人將獲刑9個月。
若雙方同時檢舉對方，則均判刑6個月。
若雙方互相合作都不主動揭發(fā)，則均因證據(jù)不足被輕判為1個月。

類似地，可以表述為一個矩陣。但由于這里不是零和了，因此 AB 雙方的得分都需要列出。

image

囚徒困境

顯然，相互合作不揭發(fā)對于這個犯罪團(tuán)伙是最好的方案。但實(shí)際上并非那么順利。設(shè)想下面的情況：

對于 A 來講，假設(shè) B 選擇合作，那么為了最大化自己利益 A 會選擇檢舉；假設(shè) B 選擇檢舉，同樣為了最大化自己利益，A 還是會檢舉。
對于 B 來講情況是一樣的，無論 A 如何選擇 B 都會選擇檢舉。

因此最終他們會互相檢舉從而均被判刑6個月，這不是想要的最佳方案。這被稱為 囚徒困境。

NASH 均衡

NASH 均衡，英文 nash equilibrium ，也被音譯為納什均衡。

當(dāng)且僅當(dāng)對于所有的 n 個玩家，各自選擇的每一項策略都使此玩家效用最大，即為 Nash 均衡。
更好理解的解釋是：當(dāng)所有玩家都知道其他玩家的策略，任意選擇一名玩家允許他改變策略，他都沒有理由改變，因?yàn)楫?dāng)前策略可以最大化效用。

Nash 均衡的定義適用于純策略和混合策略。

嚴(yán)格控制

對于這個具體博弈，A 選擇檢舉（第二行）總是要比合作（第一行）更有利（0>-1, -6>-9）?？梢苑Q為第二行嚴(yán)格控制第一行。

這也就意味著如果選擇了第一行的任何數(shù)據(jù)，那么總是應(yīng)該傾向于選擇下一行，因?yàn)樗欣?/p>

NASH 均衡的基本定理

• 在 n 個玩家的純策略博弈中，如果淘汰所有經(jīng)過嚴(yán)格控制的策略，只留下一組策略，那么這一組策略就是唯一的 Nash 均衡。
• 任何的 Nash 均衡都將在反復(fù)刪減的嚴(yán)格劣勢策略過程中留存下來。
• 如果玩家數(shù)量(n)是有限的，對于每一組策略，該組策略也是有限的。

連續(xù)囚徒困境博弈

在囚徒困境中，整個團(tuán)體無法達(dá)成最佳策略。那么對于一個連續(xù)的囚徒困境博弈問題，是否可以通過先驅(qū)的博弈建立信任從而達(dá)到最佳呢？可惜答案也是否定的。

假設(shè)連續(xù)進(jìn)行20場博弈，對于最后一場博弈來說，可以認(rèn)為由于建立了信任，對方一定選擇合作，基于最大化自己利益，這正是檢舉對方的好時機(jī)。因?yàn)殡p方都有這種想法，于是再次落入了囚徒困境。
因?yàn)榈?0次博弈結(jié)局已知，所以第19次博弈可看做是最后一次，根據(jù)歸納法不難看出，每一次博弈都將陷入囚徒困境。