ゲーム理論の問題

手順 1：均衡条件を言い換える。
プレイヤー $i$ 以外の行動を固定して、$i$ が行動を変えたときの利得を比べる。
- 両隣がともに自分と同じ行動のとき：利得は $0$。行動を変えると両隣と異なるので利得 $2$。よって最適反応ではない。
- 片方の隣人だけが自分と異なるとき：利得は $1$。行動を変えても、今度はもう片方の隣人とだけ異なるので利得 $1$。よって最適反応である。
- 両隣がともに自分と異なるとき：利得は $2$ で最大。最適反応である。

したがって、$(x_1,\dots ,x_6)$ が純粋戦略ナッシュ均衡である条件は、「すべての $i$ について利得が $1$ 以上、すなわち少なくとも一方の隣人と異なる行動をとる」ことであり、これは「円環上で同じ行動が $3$ つ以上連続しない」ことと同じである。

手順 2：隣り合う組に注目して数える。
円環上の隣り合う $6$ 組 $(x_1,x_2),(x_2,x_3),\dots ,(x_6,x_1)$ のそれぞれに、値が等しければ「同」、異なれば「異」と印をつける。
- 同じ行動が $3$ つ連続することは、隣り合う $2$ 組が両方とも「同」になることと同じである。よって条件は「『同』の組どうしが円環上で隣り合わない」こと。
- 円を一周すると元の値に戻るので、値が変わる回数、すなわち「異」の個数は偶数である。$6$ 組あるので「同」の個数も偶数。
- 逆に、条件を満たす印のつけ方と $x_1$ の値（$2$ 通り）を決めれば、列はただ $1$ つに定まる。

「同」の個数で分ける。
- 「同」が $0$ 個：$1$ 通り（$010101$ 型）。
- 「同」が $2$ 個：$6$ 組から $2$ 組を選ぶ ${}_6{\mathrm{C}}_2=15$ 通りから、隣り合う $2$ 組を選ぶ $6$ 通りを除いて $15-6=9$ 通り。
- 「同」が $4$ 個以上：$6$ 組の円環で互いに隣り合わない組は最大 $3$ 個までなので不可能。

よって印のつけ方は $1+9=10$ 通りで、$x_1$ の選び方 $2$ 通りをかけて
$$10\times 2=20$$

（確認例：$001101$ は円環上で $3$ つ連続する同じ値がなく、均衡である。）

答え：$20$ 個

プレイヤー $i$ の隣人の行動が $x_{i-1}=x_{i+1}$ のとき、$x_i$ をそれと異なる値にすれば利得 $2$ を得られ、同じ値にすれば $0$ になる。隣人の行動が異なるとき ($x_{i-1}\ne x_{i+1}$) は、どちらを選んでも利得は $1$ で変わらない。

したがって純粋戦略ナッシュ均衡の条件は、どの $i$ についても $x_{i-1}=x_i=x_{i+1}$ とならないこと、すなわち円環上で同じ値が $3$ つ連続しないことである。

円環上の同じ値の連続部分（ラン）の長さはすべて $1$ か $2$ で、ランの個数は偶数である。ランの長さの合計が $6$ なので、ランの個数は $4$ か $6$ に限られる。

• ランが $6$ 個のとき、長さはすべて $1$ で、交互列 $010101$ と $101010$ の $2$ 個。
• ランが $4$ 個のとき、長さは $2,2,1,1$ の並びで、その並べ方は $\left(\genfrac{}{}{0ex}{}{4}{2}\right)=6$ 通り。「文字列と、ランの開始位置の $1$ つ」の組を数えると、開始位置が $6$ 通り、並べ方が $6$ 通り、先頭のランの値が $2$ 通りで $6\cdot 6\cdot 2=72$ 組。各文字列は開始位置を $4$ 個もつので、文字列の数は $72/4=18$。

合計は $2+18=20$ 個。

検算として、$000$ と $111$ を禁止する遷移行列を状態 $(x_i,x_{i+1})$ で考える方法がある。この行列の $6$ 乗のトレースが閉路の個数を与え、直接数えた結果と一致する想定である。ただしトレースの値そのものは計算しておらず、検算は未完了。