ゲーム理論の問題

手順 1：均衡条件を言い換える。
プレイヤー $i$ の行動を変えると、隣人と「同じ」か「異なる」かがすべて入れかわるので、利得 $u$ は $2-u$ になる。
- 利得が $0$（両隣とも自分と同じ行動）のとき、行動を変えると利得は $2$ に増えるので、最適反応ではない。
- 利得が $1$ のとき、行動を変えても利得は $1$ のままなので、最適反応である。
- 利得が $2$ のとき、行動を変えると $0$ に減るので、最適反応である。

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

手順 2：条件を満たす円環上の $0/1$ 列を数える。
全員が同じ行動の列は条件を満たさないので、列は $0$ の連続部分（ブロック）と $1$ のブロックが円環上で交互に並ぶ形になる。$0$ のブロックと $1$ のブロックは同数で、その数を $r$ とする。条件より各ブロックの長さは $1$ か $2$ である。ブロックは全部で $2r$ 個、長さの合計は $6$ なので $2r\le 6\le 4r$、よって $r=2$ または $r=3$。

(i) $r=3$ のとき：$6$ 個のブロックの長さの合計が $6$ なので、すべて長さ $1$。$010101$ と $101010$ の $2$ 通り。

(ii) $r=2$ のとき：$4$ 個のブロックの長さの合計が $6$ なので、長さ $2$ が $2$ 個、長さ $1$ が $2$ 個。
- $0$ のブロックが $2,2$、$1$ のブロックが $1,1$：$001001$ を回転したもので、周期 $3$ なので $3$ 通り（$001001,010010,100100$）。
- $0$ のブロックが $1,1$、$1$ のブロックが $2,2$：同様に $3$ 通り。
- $0$ のブロックも $1$ のブロックも長さ $2$ と $1$ が $1$ 個ずつ：円環上の並びは $001101$ 型と $001011$ 型の $2$ 種類で、どちらも回転で $6$ 通りずつ異なる列が得られ、互いに重ならない。よって $6\times 2=12$ 通り。

(ii) の合計は $3+3+12=18$ 通り。

手順 3：まとめる。
和の法則より、求める個数は $2+18=20$。

プレイヤー $i$ の隣人のうち自分と異なる行動を選んだ人数を $d_i$ とする。行動を変えると利得は $2-d_i$ になる。したがって、現在の行動が最適応答であることは $d_i\ge 2-d_i$、つまり $d_i\ge 1$ と同値である。

全員がこの条件を満たすことがナッシュ均衡の条件である。これは「円周上で同じ行動が3つ連続して並ぶところがない」(巡回的に $x_{i-1}=x_i=x_{i+1}$ となる $i$ がない) ことと同じである。

長さ6の巡回的な 0/1 列で、変化の起こる辺(隣り合う2人の行動が異なる辺)の個数を $r$ とする。$r$ は偶数で、これは連の個数でもある。

• $r=0$: 全員同じ行動。同じ行動が連続するので不適。
• $r=2$: 連の長さの和は 6 だが、各連の長さは 2 以下なので和は最大 4 となり不適。
• $r=4$: 6 本の辺から変化の辺を 4 本選ぶ方法は $\left(\genfrac{}{}{0ex}{}{6}{4}\right)=15$ 通りで、残る 2 本の辺は連の内部にある。各連の長さが 2 以下になるには、この 2 本が円周上で隣り合わないことが必要である。隣り合う選び方は 6 通りなので、隣り合わない選び方は $15-6=9$ 通り。始めの値の選び方が 2 通りあるので、$9\times 2=18$ 個。
• $r=6$: 交互の列で 2 個。

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

検算: $r=4$ の例 $(0,0,1,0,0,1)$ では、各プレイヤーが少なくとも 1 人の隣人と異なる行動を選んでいるので均衡である。一方 $(0,0,0,1,0,1)$ は、プレイヤー 1 の隣人が 6 と 2 で、プレイヤー 6 は 1、プレイヤー 2 は 0 なので条件を満たすが、プレイヤー 2 の隣人 1 と 3 がともに 0 なので $d_2=0$ となり不適。これは 3 連続の 0 を含むので、上の数え上げの除外と一致する。