ゲーム理論の問題
人のプレイヤー が円形に並んでおり、プレイヤー の隣人はプレイヤー と である（添字は を法として考え、プレイヤー はプレイヤー 、プレイヤー はプレイヤー を表す）。各プレイヤー は同時に 回だけ、行動 を選ぶ。プレイヤー の利得は、2 人の隣人のうち自分と異なる行動を選んだ人数とする。すなわち
である。この 人ゲームの純粋戦略のナッシュ均衡（行動の組 ）の個数を求めよ。
この問題で使うもの
- 円形の隣人ゲームの純粋均衡の数え上げ（説明と入口の問題）
- 最適反応と純粋戦略ナッシュ均衡（説明と入口の問題）
- 組合せ（説明と入口の問題）
- 和の法則・積の法則と樹形図（説明と入口の問題）
この問題を解けるようになるまで（7 技能）
読み込み中…
右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。
ヒント
行き詰まったら、上から順に 1 つずつ開いてください。
ヒント 1
各プレイヤーの最適反応を、両隣の行動が同じ場合と異なる場合に分けて調べ、均衡の条件を行動の列の言葉で表してみよう。
ヒント 2
均衡の条件は「円周上で同じ値が 3 つ以上続かない」こと。隣どうしの差 を考えると、「 が円周上で隣り合わない」かつ「 の個数が偶数」という条件に言い換えられる。
ヒント 3
は の値と差の列 で決まるので、個数は 。 の の個数 は偶数で の場合があり、それぞれ 通り、 通り、…と数える。
答えと解説
答えを見る
どこでつまずきましたか？（選ぶと、戻る場所を案内します）
解説を読む
均衡の条件 プレイヤー の両隣の行動を固定して考える。
- 両隣が同じ行動 のとき： なら利得 、 なら利得 なので、最適反応は のみである。
- 両隣の行動が異なるとき： が のどちらでも利得は なので、どちらも最適反応である。
よって行動の組がナッシュ均衡であるための必要十分条件は、
こと、つまり円形の列 に同じ値が（円周上で） つ以上連続しないことである。
差の列への言い換え とおく。条件「 でない」は「 でない」と同値なので、条件は「円形の列 で が隣り合わない」となる。
また、 を 周たどると元に戻るので、 となる の個数（値が変わる回数）は偶数である。逆に の個数が偶数の が与えられれば、 を か に決めると がちょうど つ定まる。したがって と は 対 に対応し、
である。
の数え上げ の の個数を とすると、 の個数 が偶数なので は偶数である。円周上の か所から、どの つも隣り合わない か所を選ぶ方法の数は （）である。
- ： 通り
- ： 通り（隣り合う か所の組 通りを除く）。公式でも
- ： 通り
- ： か所以上を互いに隣り合わないように選ぶことは か所の円周ではできない（最大 か所）ので 通り
合計 通り。
（ の確認： か所を選ぶとき、ある特定の位置 を選ぶ場合は位置 を除いた か所の直線上から隣り合わない か所で 通り、位置 を選ばない場合は位置 の か所の直線上から隣り合わない か所で 通り、計 通り。）
答え 均衡の個数は である。
別解
プレイヤー の隣人が同じ行動 のとき、 なら利得 2、 なら利得 0。隣人の行動が異なるときは、 がどちらでも利得は 1 で変わらない。したがって純粋戦略のナッシュ均衡であるための条件は、すべての について「 ならば 」であり、これは円環上に同じ値が 3 個連続する箇所がない（ がどの でも起こらない）ことと同値である。
よって、長さ 10 の 0/1 の円環状の列で、同じ値の連続（ラン）の長さがすべて 1 か 2 であるものを数える（位置 は区別する）。円環では ラン の個数 は偶数（0 と 1 が交互に現れる）。ランの長さが 1 か 2 で合計 10 になる個数 の列（順序つき）の数は、2 のランが 個なので 。
「列」と「ランの開始位置の一つ（その位置と色）」の組を数える。開始位置 10 通り、その色 2 通り、ランの長さの列 通りで組は 個。1 つの列は 個のランの開始位置をもつので、ランが 個の列の数は 。
- :
- :
- :
- は なので 0（ だと最大長 8 < 10）
合計 。
検算: 同じ方法を に使うと のみで で、直接数えた （000, 111 を除く）と一致する。