Fictitious Play

例として,次の Matching Pennies ゲームを考えましょう:

$ \begin{bmatrix} 1, -1 & -1, 1 \\ -1, 1 & 1, -1 \end{bmatrix} $

行プレイヤーをプレイヤー $0$,列プレイヤーをプレイヤー $1$, またそれぞれのプレイヤーの行動を行動 $0$,行動 $1$ と呼ぶことにします.

Fictitious play は次のようなアルゴリズムからなります:

  • 各 $t$ 時点において,プレイヤー $0$ は 「プレイヤー $1$ は,確率 $1 - x_0(t)$ で行動 $0$ をとり,確率 $x_0(t)$ で行動 $1$ をとる」 と考え,自分の期待利得が最大になるような行動をとる (ただし,行動 $0, 1$ の期待利得が等しい場合は確率半々でランダムにいずれかを選ぶとする). $x_0(t)$ を「$t$ 時点における,プレイヤー $0$ の,プレイヤー $1$ の行動に関する信念 (belief)」と呼ぶことにする. (プレイヤー $1$ についても同様.)

  • プレイヤー $0$ の信念 $x_0(t)$ は次のように定まる. (プレイヤー $1$ についても同様.)

    • 初期信念 $x_0(0)$ は $[0, 1]$ 上の一様分布にしたがってランダムに与えられる.

    • 各 $t \geq 1$ 時点において,プレイヤー $1$ が過去とった行動を $a_1(0), \ldots, a_1(t-1)$ とすると,信念 $x_0(t)$ は \begin{equation} x_0(t) = \dfrac{x_0(0) + a_1(0) + \cdots + a_1(t-1)}{t + 1} \end{equation} で与えられる.

(本当は \begin{equation} x_0(t) = \dfrac{a_1(0) + \cdots + a_1(t-1)}{t} \end{equation} とすべきところですが,そうするとグラフを書いたときにかなりおもしろくないケースが出てくるので,上のようにしました.)

さて,$x_0(t)$ は \begin{align} x_0(t+1) &= \dfrac{x_0(0) + a_1(0) + \cdots + a_1(t)}{t + 2} \\ &= \dfrac{(t + 1) x_0(t) + a_1(t)}{t + 2} \\ &= x_0(t) + \dfrac{1}{t + 2} (a_1(t) - x_0(t)) \end{align} と再帰的に書くことができます.

まとめると,プレイヤー $0$ と $1$ と合わせて,次の連立1階漸化式 (差分方程式) を考えることになります: \begin{align} x_0(t+1) &= x_0(t) + \dfrac{1}{t + 2} (a_1(t) - x_0(t)), \qquad x_0(0) \sim \mathrm{Uniform}[0, 1], \\ x_1(t+1) &= x_1(t) + \dfrac{1}{t + 2} (a_0(t) - x_1(t)), \qquad x_1(0) \sim \mathrm{Uniform}[0, 1], \end{align} ただし,

  • $a_0(t)$ は $x_0(t)$ に対する最適反応

  • $a_1(t)$ は $x_1(t)$ に対する最適反応

(最適反応が複数あるときは等確率でランダムに選ぶ).

他のゲーム

$2 \times 2$ 調整ゲーム (の一例)

$ \begin{bmatrix} 4, 4 & 0, 3 \\ 3, 0 & 2, 2 \end{bmatrix} $

じゃんけんゲーム

$ \begin{bmatrix} 0, 0 & -\ell_2, w_1 & w_3, -\ell_1 \\ w_1, -\ell_2 & 0, 0 & -\ell_3, w_2 \\ -\ell_1, w_3 & w_2, -\ell_3 & 0, 0 \end{bmatrix} \qquad w_1, w_2, w_3, \ell_1, \ell_2, \ell_3 > 0 $

$3 \times 3$ 調整ゲーム (の一例) --- Young ゲーム

$ \begin{bmatrix} 6, 6 & 0, 5 & 0, 0 \\ 5, 0 & 7, 7 & 5, 5 \\ 0, 0 & 5, 5 & 8, 8 \end{bmatrix} $

Shapley ゲーム

$ \begin{bmatrix} 1, 0 & 0, 0 & 0, 1 \\ 0, 1 & 1, 0 & 0, 0 \\ 0, 0 & 0, 1 & 1, 0 \end{bmatrix} $