円形の隣人ゲームの純粋均衡の数え上げ

ゲームの設定。 $n$ 人（$n\ge 3$）のプレイヤー $1,2,\dots ,n$ が円形に並びます。プレイヤー $i$ の両隣は $i-1$ と $i+1$ で、番号は $n$ の次が $1$ に戻るように読みます。各人は行動 $0$ か $1$ を 1 つ選びます。各人の利得は「自分と異なる行動を取った隣人の人数」で、$0,1,2$ のどれかになります。純粋戦略ナッシュ均衡とは、全員が「他の人の行動を固定したとき、自分の行動が最適反応になっている」行動の組 $(x_1,\dots ,x_n)$ のことでした。

均衡条件の言い換え。 プレイヤー $i$ の両隣の行動を $a,b$ とし、最適反応を調べます。
- $a=b$ のとき：$a$ と違う行動を取れば利得は $2$、同じ行動なら $0$ です。したがって最適反応は「$a$ と違う行動」だけです。
- $a\ne b$ のとき：どちらを選んでも、ちょうど一方の隣人と異なるので利得は $1$ です。したがって両方とも最適反応です。

つまり $x_i$ が最適反応でないのは「両隣が同じで、しかも自分もそれと同じ」とき、すなわち $x_{i-1}=x_i=x_{i+1}$ のときだけです。言い換えると、$x_i$ が最適反応であることは「利得が $1$ 以上」、つまり「少なくとも一方の隣人と異なる」ことと同じです。よって均衡とは、円周上で同じ行動が 3 つ連続する箇所がない $0/1$ 列のことです。プレイヤーには番号がついて区別されるので、回転して重なる列も別の組として数えます。

数え方。 隣り合う 2 人ごとに $d_i=1$（$x_i\ne x_{i+1}$）または $d_i=0$（$x_i=x_{i+1}$）と記録し、円環上の列 $(d_1,\dots ,d_n)$ を作ります。$x_{i-1}=x_i=x_{i+1}$ は $d_{i-1}=d_i=0$ と同じなので、条件は「$d$ の $0$ が円周上で隣り合わない」になります。さらに、円を一周すると元の行動に戻るので、行動が変わる回数（$d$ の中の $1$ の個数）は偶数でなければなりません。逆にこの 2 条件を満たす $d$ が与えられれば、$x_1$ を $0$ か $1$ に決めるだけで残りが一通りに決まり、一周しても矛盾しません。よって均衡の個数は「条件を満たす $d$ の個数」の $2$ 倍です。

円周上で隣り合わない選び方の個数。 一直線に並んだ $m$ 個から、隣り合わないように $k$ 個選ぶ方法を考えます。選ばない $m-k$ 個を並べると、その間と両端に $m-k+1$ か所のすき間ができます。そこから $k$ か所を選んで 1 つずつ入れればよいので、方法は ${}_{m-k+1}{\mathrm{C}}_k$ 通りです。円周上の $n$ 個から隣り合わない $k$ 個を選ぶ方法は、位置 $1$ を選ぶかどうかで場合を分けます。
- 位置 $1$ を選ばない場合：残りの $2,\dots ,n$ を一直線とみて ${}_{n-k}{\mathrm{C}}_k$ 通りです。
- 位置 $1$ を選ぶ場合：位置 $2$ と $n$ は選べないので、$3,\dots ,n-1$ の $n-3$ 個から $k-1$ 個を選び、${}_{n-k-1}{\mathrm{C}}_{k-1}$ 通りです。

合わせて ${}_{n-k}{\mathrm{C}}_k+{}_{n-k-1}{\mathrm{C}}_{k-1}$ 通りです（$k=0$ のときは $1$ 通りとします）。