如何理解多階段博弈中的 one-stage deviation principle?

01-26

讀steven的博弈論至此節，百思不得其解
書中給出如下定理：
A one-stage unimprovable strategy must be optimal.
也沒能明白其中的道理

題主的one-stage deviation principle應該是就完美信息貼現無窮重複博弈而言的。我們知道，一個參與者的behavioral strategy指的是從所有可能的歷史到她的行動空間的函數。給定其他人的策略，one-stage unimprovable strategy指的是和其他所有這類和這個函數只在一個點上取值不同的函數比，這個函數是最優的。你給出的定理是在說，不止如此，如果上述條件滿足，那麼和其他所有的這類函數比（不局限於僅僅一點上取值不同），這個函數也是最優的。

我們可以證明它的逆否命題，如果存在一個improvable strategy, 那麼就存在一個one-stage improvable strategy.

博弈參與者的集合是 $I$ 。對於參與者 $i in I$ , 她的每一個stage的行動集是 $A_i$ 。所有可能的歷史構成的集合是 $mathcal{H}:=(igcup_{k in mathbb{Z}_+} ( imes_{i in I}A_i)^k) cup {varnothing}$ , 她的策略是函數（方便起見，我們只考慮純策略）：

$sigma_i : mathcal{H} o A_i$

題主問題中的定理嚴格表達是：

給定一個strategy profile, $sigma$ , 如果存在deviation, $sigma^ast_i$ 使得 $U_i(sigma_i^ast, sigma_{-i}) > U_i(sigma_i, sigma_{-i})$ , 那麼存在one-stage deviation, $sigma^{ast ast}_i$ 使得 $U_i(sigma_i^{ast ast}, sigma_{-i}) > U_i(sigma_i, sigma_{-i})$ 並滿足：存在存在某一歷史 $h^prime in mathcal{H}$ 滿足 $sigma_i^{astast}(h) eq sigma_i(h) iff h = h^prime$

首先如果stage game的效用函數 $u_i$ 是有界的，那麼其實我們只用考慮有限個點上取值不同的策略的deviation。這裡我們需要 $U_i$ 可以表示成每一期 $u_i$ 的貼現和。也就是說太過久遠的未來的stage上的deviation，由於貼現，並不決定這個 $sigma_i^ast$ 是否profitable。

然後我們就有了一個finite-stage profitable deviation, $sigma_i^f$ 。注意到 $(sigma_i^f, sigma_{-i})$ 和 $sigma$ 兩個strategy profile產生的路徑可能是不一樣的。 $(h_1, h_2,h_3, h_4, ldots)$ 記作前者產生的路徑。路徑的不同才會導致效用的不同。找到那個最大的一期： $i_{max}:=max{i in mathbb{Z}_+ mid sigma_i^f(h_i) eq sigma_i(h_i)}$ 。構造一個新的one-stage deviation, $sigma_i^prime$ ,滿足 $sigma_i^prime(h) eq sigma_i(h) iff h = h_{i_{max}}$ 。

如果 $sigma_i^prime$ 是profitable的，那麼我們得證。如果不是那麼我們知道一個新的profitable策略 $sigma_i^{prime prime}$ ，即

$sigma_i^{prime prime}(h) = sigma^f_i(h)$ ，如果 $h = h_k$ 滿足 $k < i_{max}$ , 否則 $sigma_i^{prime prime}(h) = sigma_i(h)$ 。

注意 $sigma_i^{prime prime}$ 和 $sigma_i$ 只在 $i_{max}-1$ 個點上取值不同。按照上面的思路，如果我們不能立即得到一個新的one-stage profitable deviation, 那麼我們可以得到一個 $i_{max}-2$ -stage profitable deviation。重複下去，我們早晚可以找到一個one-stage profitable deviation。

需要強調的是重複博弈策略的遞歸結構。上述討論也可以看做在一個歷史 $h$ 下的子博弈上的討論，所以one-stage deviation principle一般表述為

給定 $sigma$ , 對於任意 $i in I$ , 如果 $sigma_i$ 是一個one-stage unimprovable strategy，那麼 $sigma$ 構成一個子博弈完美納什均衡。

長澤雅美的回答的通俗版

我猜題主問的問題是這個定理：在discounted payoff無限重複博弈中，一個策略是subgame perfect當且僅當不存在profitable one shot deviation。證明如下：

首先觀察到，subgame perfect當且僅當no profitable deviation，因此只需證明no profitable deviation當且僅當no profitable one shot deviation。

前者推出後者是顯然的，因為one shot deviation是deviation的一個特例。

後者推出前者：首先注意當payoff存在discount的時候，極遠期的payoff對於當前的價值是可以忽略不計的；因此對於任何大於零的profitable deviation，至少有一步發生在（足夠大的）有限期之內。於是問題轉化成了「在有限期重複博弈中，no profitable one shot deviation推出no profitable deviation」。這個結論是容易證明的。

ps：在dynamic programming中有一個著名的「A one-stage unimprovable strategy must be optimal」結論，可以參考David Kreps (2012), Microeconomic Foundations I附錄中的dynamic programming部分。

在理解**單階段脫離原則**之前，我們先回顧一些背景知識：

- 每個博弈都存在至少一個納什均衡。

- 在有限多階段博弈中，如果每個階段博弈都有唯一的納什均衡，則多階段博弈的最優結果就是這些納什均衡的組合（的路徑）。

- 在有限多階段博弈中，如果至少有一個階段博弈有多個的納什均衡，則多階段博弈的最優策略組合可能會脫離階段博弈的納什均衡。

那麼在多階段博弈中，在多階段博弈的擴展形式博弈樹(extensive-form game tree)上，一條路徑的收益是容易得到的，只要求出每個階段博弈的收益總和就可以了。

這樣，我們也可以比較容易計算兩條路徑中，哪個更優（一般和折扣率有關）。

問題是：對於玩家i來說，當其他玩家的策略組合 $sigma_i$ 給定的時，如何找到玩家i的最佳反應(best response)？

_註：這裡的策略可以是任何策略，比如純策略，混合策略，條件策略等。_

這裡邊，一個比較麻煩的問題是路徑太多。比如：考慮一下一個有五個階段的博弈。

幸運的是，上面這個駭人的問題可以被簡化- 這就是單階段脫離原則。

**單階段脫離原則**的含義是，當其他玩家的策略組合 $sigma_i$ 給定的時，判斷玩家i的一條路徑是否最優，只要看這個路徑（策略）是不是單點不可改善(one-shot unimprovable)。

因此只要檢測和它有**一個信息集不同**的那些路徑就可以了。

比如：如果一個階段博弈有A和B兩個行動，在一個三階段的重複博弈中，判斷一條玩家的路徑（策略）AAA是否是不可改善，只需要對比BAA，ABA和AAB就可以了。

很明顯，這個原則只適合於有限多階段博弈。

其實原書中，對於Prisoner-Revenge Game，計算折扣率，可以看成對**單階段脫離原則**的過程描述，只不過只是比較兩個路徑。

下面加上書中的定義和定理，以供參考。

單階段脫離原則表述如下:

&> 一個階段的不可改善策略必定是最優的。

這意味著，如果在一個階段博弈中，存在一個**單階段不可改善策略**，則不會發生脫離，也就是不存在非納什均衡的最優策略。

反之，則一定會發生脫離的情況。

**單階段不可改善策略**的定義如下：

&> 一個策略 $sigma_i$ 是單階段不可改善的，則:

&> 不存在信息集 $h_i$ 和行動 $a in A_i(h_i)$ 和對應的策略 $sigma_i^{a, h_i}$ （其為除了信息集 $h_i$ 以外，和 $sigma_i$ 都一致的策略），有 $sigma_i^{a, h_i} > v_i(sigma_i, h_i)$ 。

參照見[One-shot deviation principle](https://en.wikipedia.org/wiki/One-shot_deviation_principle)

眼瞅著就要博資考了看著這種問題突然發現這個概念的證明我還沒有背，我非常感謝提這個問題的人……

先佔著坑吧，以後有時間可以說說……

請先摺疊……

完全看不懂1樓在說啥。但是我覺得很有道理。