ゲーム理論の問題

手順 1：均衡条件を言い換える。

プレイヤー $i$ に注目し、隣人 2 人の行動を固定する。

• 隣人 2 人とも自分と同じ行動のとき、利得は $0$。行動を変えると 2 人とも異なる行動になり利得は $2$ に増えるので、最適反応ではない。
• 隣人のちょうど 1 人が自分と異なるとき、利得は $1$。行動を変えても異なる隣人はやはり 1 人で利得は $1$ のままなので、増やせない。
• 隣人 2 人とも異なるとき、利得は $2$ で最大。

よって、行動の組が純粋戦略ナッシュ均衡である条件は
$$\text{すべての }i\text{ について利得が }1\text{ 以上（少なくとも一方の隣人と異なる行動）}$$
であり、これは「円環上で同じ行動が $3$ つ以上連続しない」ことと同じである。

手順 2：隣り合う組に注目して数える。

円形に隣り合う組（辺）は $\{1,2\},\{2,3\},\dots ,\{6,1\}$ の $6$ 本ある。各辺について、両端の行動が「同じ」か「異なる」かを考える。

• 同じ行動が 3 つ連続するのは、「同じ」辺が 2 本隣り合うときである。よって条件は「『同じ』辺どうしが隣り合わない」こと。
• 円を 1 周すると行動は元に戻るので、「異なる」辺の本数は偶数でなければならない。$6$ 本のうち「異なる」辺が偶数本なので、「同じ」辺の本数も偶数（$0,2,4,6$ 本）。
• 「同じ」辺が互いに隣り合わないように円上の 6 本から選べるのは高々 $3$ 本なので、「同じ」辺は $0$ 本か $2$ 本である。

「同じ」辺が $0$ 本：$1$ 通り。

「同じ」辺が $2$ 本：$6$ 本から $2$ 本選ぶ ${}_6{\mathrm{C}}_2=15$ 通りから、隣り合う 2 本の選び方 $6$ 通りを除いて $15-6=9$ 通り。

手順 3：行動の組に戻す。

「同じ／異なる」の辺の決め方を 1 つ固定すると、プレイヤー 1 の行動（$0$ か $1$ の $2$ 通り）を決めれば、残りのプレイヤーの行動は順に 1 通りに決まる（「異なる」辺の本数が偶数なので 1 周しても矛盾しない）。

したがって均衡の個数は
$$2\times (1+9)=20$$

（確認：「同じ」辺 0 本は $010101,101010$ の 2 通り、「同じ」辺 2 本は例えば $001011$ のような 18 通りである。）

答え：$20$

プレイヤー $i$ の利得は、両隣人が同じ行動 $a$ のときは、自分が $1-a$ を選べば $2$、$a$ を選べば $0$ である。隣人が異なる行動のときは、自分の行動によらず利得は $1$ である。したがって、均衡であることは次と同値である。

• 隣人が同じ行動 $a$ のとき、自分は $1-a$ を選んでいる。
• 隣人が異なるときは条件なし。

つまり、どの $i$ についても $x_{i-1}=x_i=x_{i+1}$ とならないこと（円形に並んだ長さ $6$ の $0/1$ 列で、同じ値が $3$ つ連続しない）が均衡の条件である。

数え上げ：同じ値が連続する部分（連）の長さがすべて $1$ か $2$ であるような円形の列を数える。連の個数は偶数である。
- 連が $6$ 個（すべて長さ $1$）: $010101,101010$ の $2$ 通り。
- 連が $4$ 個（長さ $2,2,1,1$）:
- 長さ $2$ の連が隣り合う場合は、$001101$ とその回転 $6$ 通りと、補色 $6$ 通りで $12$ 通り。
- 長さ $2$ の連が向かい合う場合は、$001001$ 型で周期 $3$ なので回転 $3$ 通りと補色 $3$ 通りで $6$ 通り。
- 連が $2$ 個では、長さの和 $6$ を作るのに長さ $3$ 以上の連が必要になるため不可。

合計 $2+12+6=20$。

検算：遷移行列（状態は隣接する $2$ つの行動の組で、$aab\to$ 連続 $3$ つ同じを禁止）の特性多項式は ${\lambda }^4-{\lambda }^2-2\lambda -1$ である。ニュートンの恒等式でべき和を求めると $p_2=2,p_3=6,p_4=6,p_5=10,p_6=20$ となり、$\mathrm{tr}(M^6)=20$ で一致する。