ゲーム理論

扱うテーマ: 純粋戦略のナッシュ均衡の個数、混合戦略のナッシュ均衡と期待利得、ゼロ和ゲームのゲームの値（ミニマックス）、展開形ゲームの部分ゲーム完全均衡、協力ゲームのシャープレイ値・コア、組合せゲーム（ニム）のグランディ数

難易度の目安（大学数学）

難易度 1 教科書の例題レベル
難易度 2 教科書の演習問題レベル
難易度 3 期末試験の応用レベル
難易度 4 大学院入試の標準レベル
難易度 5 大学院入試の難問・数学コンテストレベル

キーワードで探す →

難易度 1（教科書の例題レベル）
プレイヤー $1$ は戦略 $U, M, D$ のどれか $1$ つを、プレイヤー $2$ は戦略 $L, C, R$ のどれか $1$ つを、互いの選択を知らずに同時に $1$ 回だけ選ぶ。利得は次の表のとおりである。各欄の $(a, b)$ は、 $a$ がプレイヤー $1$ の利得、 $b$ がプレイヤー $2$ の利得を表す。
$U M D L (3, 2) (1, 0) (2, 3) C (0, 1) (2, 4) (1, 0) R (1, 3) (0, 1) (2, 4)$
各プレイヤーは自分の利得を最大にしようとする。このゲームの純粋戦略ナッシュ均衡の個数を求めよ。
難易度 1（教科書の例題レベル）
プレイヤー $1$ は戦略 $U, M, D$ のうち $1$ つを、プレイヤー $2$ は戦略 $L, C, R$ のうち $1$ つを、互いの選択を知らずに同時に $1$ 回だけ選ぶ。利得は次の表のとおりである。各欄の $(a, b)$ は、 $a$ がプレイヤー $1$ の利得、 $b$ がプレイヤー $2$ の利得を表す。
$U M D L (3, 2) (1, 0) (2, 3) C (0, 1) (2, 2) (1, 0) R (2, 3) (1, 1) (0, 2)$
各プレイヤーは自分の利得を最大にしようとする。このゲームの純粋戦略ナッシュ均衡の個数を求めよ。
難易度 1（教科書の例題レベル）
プレイヤー $1$ は戦略 $U, M, D$ のうち 1 つを、プレイヤー $2$ は戦略 $L, C, R$ のうち 1 つを、互いの選択を知らずに同時に 1 回だけ選ぶ。利得は次の表のとおりである。各欄の $(a, b)$ は、 $a$ がプレイヤー $1$ の利得、 $b$ がプレイヤー $2$ の利得を表す。
$U M D L (3, 2) (1, 1) (2, 0) C (0, 1) (2, 3) (1, 2) R (1, 0) (0, 2) (3, 1)$
各プレイヤーは自分の利得をできるだけ大きくしようとする。このゲームの純粋戦略ナッシュ均衡の個数を求めよ。
難易度 1（教科書の例題レベル）
プレイヤー集合 $N = {1, 2, 3}$ の提携形ゲーム（特性関数形ゲーム） $v$ が次で与えられている。
$v (\emptyset) = 0, v ({1}) = 1, v ({2}) = 2, v ({3}) = 3,$
$v ({1, 2}) = 6, v ({1, 3}) = 7, v ({2, 3}) = 8, v ({1, 2, 3}) = 12.$
このゲームにおけるプレイヤー $1$ のシャープレイ値 $φ_{1}$ を求めよ。
難易度 1（教科書の例題レベル）
$3$ 人の職人 $1, 2, 3$ が、協力して作品を作って販売する。協力する職人の集合 $S$ が得られる利益（単位：万円）を $v (S)$ とし、プレイヤー集合 $N = {1, 2, 3}$ の提携形ゲーム（特性関数形ゲーム） $v$ が次で与えられている。
$v (\emptyset) = 0, v ({1}) = 2, v ({2}) = 1, v ({3}) = 0,$
$v ({1, 2}) = 5, v ({1, 3}) = 4, v ({2, 3}) = 3, v ({1, 2, 3}) = 9.$
このゲームにおける職人 $1$ のシャープレイ値 $φ_{1}$ を求めよ。
難易度 1（教科書の例題レベル）
$3$ 人の職人 $1, 2, 3$ が共同で作品を作って売ることを考える。参加する職人の集合（提携） $S$ が得られる利益を $v (S)$ （単位：万円）とし、プレイヤー集合 $N = {1, 2, 3}$ の提携形ゲーム（特性関数形ゲーム） $v$ が次で与えられているとする。
$v (\emptyset) = 0, v ({1}) = 1, v ({2}) = 2, v ({3}) = 3,$
$v ({1, 2}) = 5, v ({1, 3}) = 6, v ({2, 3}) = 7, v ({1, 2, 3}) = 12.$
このゲームにおける職人 $1$ のシャープレイ値 $φ_{1}$ を求めよ。
難易度 1（教科書の例題レベル）
プレイヤー全体の集合を $N = {1, 2, 3}$ とする提携形（特性関数形）ゲーム $(N, v)$ を考える。特性関数 $v$ は次で与えられる。
$v ({1}) = v ({2}) = v ({3}) = 0, v ({1, 2}) = 8, v ({1, 3}) = 6, v ({2, 3}) = 5, v (N) = 12$
配分 $(x_{1}, x_{2}, x_{3})$ （ $x_{1}, x_{2}, x_{3}$ は実数）がコアに属するとは、全体合理性 $x_{1} + x_{2} + x_{3} = v (N)$ と、空でないすべての提携 $S ⊊ N$ に対する提携合理性 $\sum_{i \in S} x_{i} \geq v (S)$ をみたすことをいう。コアに属する配分全体を考えるとき、プレイヤー $1$ の取り分 $x_{1}$ の最小値と最大値をこの順に求めよ。
難易度 1（教科書の例題レベル）
プレイヤー全体の集合を $N = {1, 2, 3}$ とする提携形（特性関数形）ゲーム $(N, v)$ を考える。特性関数 $v$ は次で与えられる（ $v (\emptyset) = 0$ とする）。
$v ({1}) = v ({2}) = v ({3}) = 0, v ({1, 2}) = 6, v ({1, 3}) = 8, v ({2, 3}) = 10, v (N) = 12$
配分 $(x_{1}, x_{2}, x_{3})$ （ $x_{1}, x_{2}, x_{3}$ は実数）がコアに属するとは、次の 2 つを満たすことである。
- 全体合理性： $x_{1} + x_{2} + x_{3} = v (N)$
- 提携合理性：空でないすべての提携 $S \subseteq N$ に対して $\sum_{i \in S} x_{i} \geq v (S)$
このゲームのコアはただ 1 つの配分からなる。その配分 $(x_{1}, x_{2}, x_{3})$ を求めよ。
難易度 1（教科書の例題レベル）
プレイヤー全体の集合を $N = {1, 2, 3}$ とする提携形（特性関数形）ゲーム $(N, v)$ を考える。特性関数 $v$ は次で与えられる。
$v ({1}) = v ({2}) = v ({3}) = 0, v ({1, 2}) = 6, v ({1, 3}) = 8, v ({2, 3}) = 10, v (N) = 12$
利得ベクトル $(x_{1}, x_{2}, x_{3})$ （ $x_{1}, x_{2}, x_{3}$ は実数）がコアに属するのは、全体合理性 $x_{1} + x_{2} + x_{3} = v (N)$ と、すべての提携 $S \subseteq N$ （ $S \neq = \emptyset$ ）に対する提携合理性 $\sum_{i \in S} x_{i} \geq v (S)$ を満たすときである。このゲームのコアはただ 1 点からなる。その点 $(x_{1}, x_{2}, x_{3})$ を求めよ。
難易度 1（教科書の例題レベル）
石の山が $3$ つあり、石の個数はそれぞれ $6$ 個、 $9$ 個、 $13$ 個である。2 人のプレイヤーが交互に、どれか $1$ つの山を選び、その山から $1$ 個以上の好きな個数の石を取り除く（山にある個数まで取ってよい）。最後の石を取ったプレイヤーの勝ちとする（通常のニム）。
この局面で先手が必ず勝つための最初の手は、ちょうど $1$ 通りある。その手で選ぶ山の（取る前の）石の個数と、取り除く石の個数を、この順に組 $(山の石の個数, 取る個数)$ で答えよ。
難易度 1（教科書の例題レベル）
石の山が $3$ つあり、山 A には $3$ 個、山 B には $6$ 個、山 C には $10$ 個の石がある。2 人のプレイヤーが交互に、どれか $1$ つの山を選び、その山から $1$ 個以上の好きな個数の石を取り除く（山にある個数まで取れる）。最後の石を取ったプレイヤーの勝ちとする（動かせなくなったプレイヤーの負け）。
この局面で先手が必勝となる最初の手はただ $1$ 通りである。その手を打った直後の山 A、山 B、山 C の石の個数を、この順に組で答えよ。
難易度 1（教科書の例題レベル）
石の山が $3$ つあり、山 A, B, C の石の個数はそれぞれ $6$ 個、 $9$ 個、 $13$ 個である。2 人のプレイヤーが交互に、どれか $1$ つの山を選び、その山から $1$ 個以上の好きな個数の石を取り除く。最後の石を取ったプレイヤーの勝ちとする（通常のニム）。
この状態から先手が必ず勝てるような最初の手は、ただ $1$ 通りである。その手を打った直後の山 A, B, C の石の個数を、組 $(a, b, c)$ の形でこの順に答えよ。
難易度 1（教科書の例題レベル）
石が $n$ 個ある 1 つの山を使って、2 人のプレイヤーが交互に次の操作を行う。
操作：山から石をちょうど $2$ 個または $3$ 個取り除く（山にある石の個数より多くは取れない）。
操作できなくなったプレイヤーの負けとする。石が $n$ 個の山（ $n$ は $0$ 以上の整数）のグランディ数を $g (n)$ とする。 $g (n)$ は、1 手で移れる局面のグランディ数の集合の mex（その集合に含まれない最小の $0$ 以上の整数）として定める。ただし、1 手も動かせない局面では集合が空なので、グランディ数は $0$ とする。 $g (24)$ を求めよ。
難易度 1（教科書の例題レベル）
石が $1$ つの山に積まれている。2 人のプレイヤーが交互に、この山から石をちょうど $2$ 個または $3$ 個取り除く（山にある石の個数より多くは取れない）。動かせなくなったプレイヤーの負けとする。石が $n$ 個（ $n$ は $0$ 以上の整数）の山のグランディ数を $g (n)$ とする。ただし、集合 $S$ （ $0$ 以上の整数からなる有限集合）に対して $mex S$ を「 $S$ に含まれない最小の $0$ 以上の整数」とし、 $g (n) = mex {g (m) ∣ n 個の山から 1 手で m 個の山に移れる}$ （移れる局面がないときは $mex \emptyset = 0$ ）と定める。 $g (23)$ を求めよ。
難易度 1（教科書の例題レベル）
石が $n$ 個ある 1 つの山がある（ $n$ は 0 以上の整数）。2 人のプレイヤーが交互に、この山から石をちょうど $2$ 個または $3$ 個取り除く（山にある石の個数より多くは取れない）。手番で石を取れなくなったプレイヤーの負けとする。
石が $n$ 個の局面のグランディ数 $g (n)$ を、1 手で移れる局面のグランディ数の集合の mex（その集合に含まれない最小の 0 以上の整数）として定める。1 手も動かせない局面のグランディ数は $0$ とする。
$g (24)$ を求めよ。
難易度 1（教科書の例題レベル）
2 つの企業 $1, 2$ が同じ商品を生産し、生産量を同時に 1 回だけ選ぶ。企業 $1$ の生産量を $x$ 、企業 $2$ の生産量を $y$ とし、 $x, y$ はどちらも $0$ 以上の実数とする。
商品の価格は $p = 14 - x - y$ で決まる（この式が負になる場合もそのまま用いる）。1 単位あたりの生産費用は、企業 $1$ が $2$ 、企業 $2$ が $5$ である。各企業の利得は利潤
$u_{1} (x, y) = x (14 - x - y) - 2 x, u_{2} (x, y) = y (14 - x - y) - 5 y$
とする。
このゲームの純粋戦略ナッシュ均衡 $(x, y)$ を求めよ。
難易度 1（教科書の例題レベル）
2 つの企業 $1, 2$ が同じ商品の生産量を同時に 1 回だけ選ぶ。企業 $1$ の生産量を $x$ 、企業 $2$ の生産量を $y$ とし、 $x, y$ はどちらも $0 ≦ x ≦ 6, 0 ≦ y ≦ 6$ の範囲の実数から選ぶ（生産能力の上限が $6$ である）。両企業の利得（利潤）はそれぞれ
$u_{1} (x, y) = x (12 - x - y), u_{2} (x, y) = y (9 - x - y)$
で与えられる。企業 $1$ の最適反応 $B R_{1} (y)$ と企業 $2$ の最適反応 $B R_{2} (x)$ を求め、純粋戦略ナッシュ均衡 $(x, y)$ を求めよ。答えは組 $(x, y)$ の形で答えよ。
難易度 1（教科書の例題レベル）
2 つの企業 $1, 2$ が、同じ商品の生産量を同時に 1 回だけ選ぶ。企業 $1$ の生産量を $x$ 、企業 $2$ の生産量を $y$ とし、 $x, y$ はどちらも $0 ≦ x ≦ 10$ 、 $0 ≦ y ≦ 10$ の範囲の実数から選ぶ。各企業の利得（利潤）は
$u_{1} (x, y) = x (14 - x - y), u_{2} (x, y) = y (10 - x - y)$
で与えられ、各企業は自分の利得を最大にしようとする。このゲームの純粋戦略ナッシュ均衡はただ 1 つ存在する。その均衡 $(x, y)$ を求めよ。
難易度 1（教科書の例題レベル）
区別のできる $5$ 台の配送トラック $1, 2, 3, 4, 5$ が、倉庫から配送センターへ向かう道路を、互いに相談せずに同時に $1$ 本ずつ選ぶ。道路は $P, Q, R$ の $3$ 本である。ある道路を選んだトラックの台数が $k$ 台のとき、その道路を選んだ各トラックの所要時間は
$P : 10 k 分, Q : (10 k + 10) 分, R : 20 k 分$
である。各トラックは自分の所要時間をできるだけ短くしたい。どのトラックも、自分だけ別の道路に移ったときに所要時間が真に短くならないような道路の選び方（各トラックがどの道路を選ぶかの割り当て）を純粋戦略ナッシュ均衡とよぶ。純粋戦略ナッシュ均衡の個数を求めよ。
難易度 1（教科書の例題レベル）
区別のできる $5$ 人の通勤者 $1, 2, 3, 4, 5$ が、駅から会社へ向かう道として、道 $A, B, C$ のうちちょうど $1$ つを同時に選ぶ。道 $A, B, C$ を選んだ人数をそれぞれ $a, b, c$ （ $a, b, c$ は $0$ 以上の整数で $a + b + c = 5$ ）とするとき、各道を選んだ人が負担する費用（所要時間）は
$道 A : a, 道 B : b + 1, 道 C : 2 c$
であり、各通勤者は自分の費用をできるだけ小さくしたい。どの通勤者も、自分だけが別の道に移ったときに費用が真に小さくならないような選び方の組（誰がどの道を選ぶかの割り当て）を純粋戦略ナッシュ均衡とよぶ。純粋戦略ナッシュ均衡の個数を求めよ。
難易度 1（教科書の例題レベル）
区別のできる $5$ 台の配送トラック $1, 2, 3, 4, 5$ が、倉庫から配送センターへ向かう道路を、互いに相談せずに同時に $1$ 本ずつ選ぶ。道路は $A, B, C$ の $3$ 本である。ある道路を選んだトラックの台数が $k$ 台のとき、その道路を選んだ各トラックの所要時間（費用）は、次のように決まる。
$c_{A} (k) = k, c_{B} (k) = k + 1, c_{C} (k) = 2 k$
各トラックは自分の所要時間をできるだけ小さくしたい。どのトラックも、自分だけ別の道路に変えても所要時間が真に小さくならないような道路の選び方（ $5$ 台それぞれがどの道路を選ぶかの割り当て）を純粋戦略ナッシュ均衡とよぶ。純粋戦略ナッシュ均衡は全部で何通りあるか求めよ。
難易度 1（教科書の例題レベル）
$6$ 人のプレイヤー $1, 2, \dots, 6$ が円形に並んでいる。プレイヤー $i$ の隣人はプレイヤー $i - 1$ と $i + 1$ の $2$ 人である（添字は $6$ を法として考え、プレイヤー $0$ はプレイヤー $6$ 、プレイヤー $7$ はプレイヤー $1$ とする）。各プレイヤー $i$ は同時に行動 $x_{i} \in {0, 1}$ を $1$ つ選ぶ。プレイヤー $i$ の利得は、 $2$ 人の隣人のうち自分と異なる行動を選んだ人の数（ $0, 1, 2$ のいずれか）とする。
行動の組 $(x_{1}, x_{2}, \dots, x_{6})$ のうち、純粋戦略ナッシュ均衡であるものの個数を求めよ。
難易度 1（教科書の例題レベル）
$6$ 人のプレイヤー $1, 2, \dots, 6$ が円形に並んでいる。プレイヤー $i$ の隣人はプレイヤー $i - 1$ と $i + 1$ である（添字は $6$ を法として考え、プレイヤー $0$ はプレイヤー $6$ 、プレイヤー $7$ はプレイヤー $1$ とする）。各プレイヤーは同時に行動 $0$ または $1$ のどちらか一方を選ぶ。各プレイヤーの利得は「自分と異なる行動を選んだ隣人の人数」（ $0, 1, 2$ のいずれか）とする。
このゲームの純粋戦略ナッシュ均衡、すなわち 6 人の行動の組 $(x_{1}, x_{2}, \dots, x_{6}) \in {0, 1}^{6}$ であって、どのプレイヤーも自分だけ行動を変えて利得を真に増やすことができないものの個数を求めよ。ただし、プレイヤーは区別し、行動の組が異なれば別の均衡として数える。
難易度 1（教科書の例題レベル）
$6$ 人のプレイヤー $1, 2, \dots, 6$ が円形に並んでいる。プレイヤー $i$ の隣人はプレイヤー $i - 1$ と $i + 1$ である（添字は $6$ を法として考え、プレイヤー $0$ はプレイヤー $6$ 、プレイヤー $7$ はプレイヤー $1$ とする）。各プレイヤーは行動 $0$ または $1$ のどちらか一方を同時に選ぶ。プレイヤー $i$ の利得は、 $2$ 人の隣人のうち自分と異なる行動を選んだ人の人数（ $0$ , $1$ , $2$ のいずれか）とする。
全員の行動の組 $(x_{1}, x_{2}, \dots, x_{6})$ （各 $x_{i} \in {0, 1}$ ）のうち、純粋戦略ナッシュ均衡になっているものの個数を求めよ。
難易度 1（教科書の例題レベル）
プレイヤー 1 は戦略 $U$ か $D$ を、プレイヤー 2 は戦略 $L$ か $R$ を、互いの選択を知らずに同時に 1 回だけ選ぶ。利得は次の表のとおりである。各欄は（プレイヤー 1 の利得, プレイヤー 2 の利得）を表す。
$L$ $R$
$U$ $(1, 3)$ $(4, 0)$
$D$ $(3, 1)$ $(2, 2)$
このゲームには純粋戦略ナッシュ均衡がなく、混合戦略ナッシュ均衡がただ 1 つある。その均衡で、プレイヤー 1 が $U$ を選ぶ確率を $p$ 、プレイヤー 2 が $L$ を選ぶ確率を $q$ とする。 $(p, q)$ をこの順に求めよ。
難易度 1（教科書の例題レベル）
サッカーのペナルティキックで、キッカー（プレイヤー 1）はシュートを「左（ $L$ ）」か「右（ $R$ ）」に蹴り、ゴールキーパー（プレイヤー 2）は「左（ $L$ ）」か「右（ $R$ ）」に跳ぶ。2 人は互いの選択を知らずに同時に 1 回だけ選ぶ。利得は次の表のとおりで、各欄は（キッカーの利得, キーパーの利得）を表す。
キーパー $L$ キーパー $R$
キッカー $L$ $(1, 4)$ $(4, 1)$
キッカー $R$ $(3, 2)$ $(2, 3)$
このゲームには純粋戦略ナッシュ均衡がなく、混合戦略ナッシュ均衡がただ 1 つある。その混合戦略ナッシュ均衡で、キッカーが $L$ を選ぶ確率を $p$ 、キーパーが $L$ を選ぶ確率を $q$ とする。 $(p, q)$ をこの順に求めよ。
難易度 1（教科書の例題レベル）
プレイヤー 1 は戦略 $U$ か $D$ を、プレイヤー 2 は戦略 $L$ か $R$ を、互いの選択を知らずに同時に 1 回だけ選ぶ。利得は次の表のとおりである。各欄の $(a, b)$ は、 $a$ がプレイヤー 1 の利得、 $b$ がプレイヤー 2 の利得を表す。
$L$ $R$
$U$ $(3, 1)$ $(0, 2)$
$D$ $(1, 3)$ $(2, 0)$
このゲームには純粋戦略ナッシュ均衡がなく、混合戦略ナッシュ均衡がただ 1 つ存在する。その均衡で、プレイヤー 1 が $U$ を選ぶ確率を $p$ 、プレイヤー 2 が $L$ を選ぶ確率を $q$ とする。 $(p, q)$ をこの順に組で求めよ。
難易度 1（教科書の例題レベル）
プレイヤー $1, 2$ が、次の完全情報の展開形ゲームを行う。各プレイヤーは手番が来たとき、それまでの行動をすべて知っている。利得は（プレイヤー $1$ の利得, プレイヤー $2$ の利得）の順に書く。
- 第 $1$ 手番：プレイヤー $1$ が「止める $T$ 」か「続ける $C$ 」を選ぶ。 $T$ ならゲームは終わり、利得は $(2, 0)$ である。 $C$ なら第 $2$ 手番へ進む。
- 第 $2$ 手番：プレイヤー $2$ が $T$ か $C$ を選ぶ。 $T$ ならゲームは終わり、利得は $(1, 3)$ である。 $C$ なら第 $3$ 手番へ進む。
- 第 $3$ 手番：プレイヤー $1$ が $T$ か $C$ を選ぶ。 $T$ なら利得は $(4, 2)$ 、 $C$ なら利得は $(3, 5)$ でゲームは終わる。
各プレイヤーは自分の利得を最大にするように行動する。このゲームの部分ゲーム完全均衡において実現する利得の組を、（プレイヤー $1$ の利得, プレイヤー $2$ の利得）の順に求めよ。
難易度 1（教科書の例題レベル）
プレイヤー 1, 2 による次の完全情報の展開形ゲームを考える。各手番では「やめる（ $S$ ）」か「続ける（ $C$ ）」のどちらかを選ぶ。利得は（プレイヤー 1 の利得, プレイヤー 2 の利得）の順に書く。
- 手番 1：プレイヤー 1 が選ぶ。 $S$ ならゲームは終わり、利得は $(2, 1)$ 。 $C$ なら手番 2 へ進む。
- 手番 2：プレイヤー 2 が選ぶ。 $S$ ならゲームは終わり、利得は $(1, 2)$ 。 $C$ なら手番 3 へ進む。
- 手番 3：プレイヤー 1 が選ぶ。 $S$ なら利得は $(5, 3)$ 、 $C$ なら利得は $(4, 6)$ でゲームは終わる。
それぞれの手番で選ぶプレイヤーは、それまでの選択をすべて知っている。後ろ向き帰納法によって部分ゲーム完全均衡を求め、その均衡で実現する利得の組を（プレイヤー 1 の利得, プレイヤー 2 の利得）の形で求めよ。
難易度 1（教科書の例題レベル）
プレイヤー $1$ , $2$ が、テーブルの上のお金をめぐって次の完全情報の展開形ゲームを行う。各プレイヤーはそれまでの行動をすべて観察してから行動を選ぶ。利得は（プレイヤー $1$ の利得, プレイヤー $2$ の利得）の順に書く。
- 第 $1$ 手番：プレイヤー $1$ が「取る」か「渡す」を選ぶ。「取る」ならゲームは終わり、利得は $(2, 0)$ である。
- 第 $2$ 手番（第 $1$ 手番で「渡す」が選ばれたとき）：プレイヤー $2$ が「取る」か「渡す」を選ぶ。「取る」ならゲームは終わり、利得は $(1, 3)$ である。
- 第 $3$ 手番（第 $2$ 手番で「渡す」が選ばれたとき）：プレイヤー $1$ が「取る」か「渡す」を選ぶ。「取る」なら利得は $(4, 2)$ 、「渡す」なら利得は $(3, 5)$ でゲームは終わる。
各プレイヤーは自分の利得を最大にするように行動する。このゲームの部分ゲーム完全均衡で実現する利得の組を（プレイヤー $1$ の利得, プレイヤー $2$ の利得）の形で求めよ。
難易度 1（教科書の例題レベル）
石の山がいくつかある。2 人のプレイヤーが交互に次の操作を行う。
- どれか 1 つの山を選び、それをどちらも $2$ 個以上の石を含む 2 つの山に分ける（2 つの山の個数は等しくてもよい）。
操作できなくなったプレイヤーが負けである。たとえば $6$ 個の山は「 $2$ 個と $4$ 個」または「 $3$ 個と $3$ 個」に分けられる。 $1$ 個、 $2$ 個、 $3$ 個の山は分けられない。
石が $8$ 個の山 1 つだけの局面のグランディ数を求めよ。
難易度 1（教科書の例題レベル）
石の山がいくつかある。2 人のプレイヤーが交互に次の操作を行う。
- どれか 1 つの山を選び、それをどちらも $2$ 個以上の石からなる 2 つの山に分ける（2 つの山の個数は等しくてもよい）。たとえば $6$ 個の山は「 $2$ 個と $4$ 個」または「 $3$ 個と $3$ 個」に分けられる。
操作ができなくなったプレイヤーの負けとする。石が $8$ 個の山 1 つだけからなる局面のグランディ数を求めよ。
難易度 1（教科書の例題レベル）
いくつかの石の山がある。2 人のプレイヤーが交互に次の操作を行う。
- どれか 1 つの山を選び、それを 2 つの山に分ける。ただし、分けた後の 2 つの山は、どちらも石が $2$ 個以上でなければならない（たとえば $6$ 個の山は $2$ 個と $4$ 個、または $3$ 個と $3$ 個に分けられる）。
操作ができなくなったプレイヤーが負けとする。石が $n$ 個の山 1 つだけからなる局面のグランディ数を $g (n)$ とする（ $n$ は正の整数）。 $g (8)$ を求めよ。
難易度 1（教科書の例題レベル）
石の山が $4$ つあり、石の個数はそれぞれ $4$ 個、 $6$ 個、 $8$ 個、 $9$ 個である。2 人のプレイヤーが交互に、どれか 1 つの山を選び、その山から石をちょうど $2$ 個または $3$ 個取り除く（山にある石の個数より多くは取れない）。動かせなくなったプレイヤーの負けとする。
この局面から先手が打てる手のうち、移った先の局面のグランディ数が $0$ になる手（勝ちにつながる手）は何通りあるか求めよ。ただし、手は「どの山から何個取るか」の組で区別する。
難易度 1（教科書の例題レベル）
石の山が $3$ つあり、石の個数はそれぞれ $5$ 個、 $7$ 個、 $9$ 個である。2 人のプレイヤーが交互に、どれか $1$ つの山を選び、その山から石をちょうど $1$ 個、 $2$ 個、 $4$ 個のいずれかの個数だけ取り除く（山にある石の個数より多くは取れない）。動かせなくなったプレイヤーの負けとする。
この局面で先手が打てる手のうち、勝ちにつながる手（相手にグランディ数 $0$ の局面を渡す手）は何通りあるか。ただし、手は「どの山から何個取るか」の組で区別する。
難易度 1（教科書の例題レベル）
石の山が $3$ つあり、石の個数はそれぞれ $4$ 個、 $8$ 個、 $9$ 個である。2 人のプレイヤーが交互に次の操作を行う。
- どれか $1$ つの山を選び、その山から石をちょうど $1$ 個、 $2$ 個、 $4$ 個のいずれかの個数だけ取り除く（山にある石の個数より多くは取れない）。
操作ができなくなったプレイヤーの負けとする。先手の最初の手のうち、手のあとの局面全体のグランディ数が $0$ になるもの（勝ちにつながる手）は何通りあるか。ただし、選ぶ山または取る個数が異なる手は、異なる手として数える。
難易度 1（教科書の例題レベル）
プレイヤー 1 は戦略 $U, M, D$ のどれかを、プレイヤー 2 は戦略 $X, Y, Z$ のどれかを、互いの選択を知らずに同時に選ぶ 2 人ゲーム（双行列ゲーム）を考える。各欄は（プレイヤー 1 の利得, プレイヤー 2 の利得）を表す。
$U M D X (3, 0) (0, 3) (1, 2) Y (0, 2) (2, 1) (1, 3) Z (0, 1) (1, 0) (4, 1)$
各プレイヤーは混合戦略を用いてよく、期待利得の最大化を目指すものとする。このゲームのナッシュ均衡（混合戦略によるものを含む）はただ 1 つである。強く支配される戦略を順に消去してから、その均衡を求め、均衡におけるプレイヤー 1 の期待利得とプレイヤー 2 の期待利得を、この順に組で答えよ。
難易度 1（教科書の例題レベル）
プレイヤー 1 は戦略 $U, M, D$ の中から、プレイヤー 2 は戦略 $X, Y, Z$ の中から、互いの選択を知らずに同時に 1 つを選ぶ 2 人の双行列ゲームを考える。利得は次の表のとおりで、各欄は（プレイヤー 1 の利得, プレイヤー 2 の利得）を表す。
$U M D X (3, 1) (0, 3) (1, 2) Y (0, 3) (2, 0) (1, 2) Z (2, 0) (1, 1) (0, 0)$
各プレイヤーは混合戦略を使ってよく、自分の期待利得を最大にしようとする。このゲームのナッシュ均衡はただ 1 つである。強く支配される戦略を順に消去してから、その均衡におけるプレイヤー 1 の期待利得とプレイヤー 2 の期待利得を求め、この順に組で答えよ。
難易度 1（教科書の例題レベル）
プレイヤー 1 は戦略 $a_{1}, a_{2}, a_{3}$ の中から、プレイヤー 2 は戦略 $b_{1}, b_{2}, b_{3}$ の中から、互いの選択を知らずに同時に 1 つを選ぶ双行列ゲームを考える。各欄は（プレイヤー 1 の利得, プレイヤー 2 の利得）を表す。
$a_{1} a_{2} a_{3} b_{1} (3, 1) (1, 4) (1, 3) b_{2} (0, 2) (2, 0) (0, 2) b_{3} (1, 0) (1, 2) (4, 1)$
このゲームのナッシュ均衡（混合戦略を含む）はただ 1 つである。強く支配される戦略を順に消去したうえで、その均衡を求めよ。答えとして、均衡におけるプレイヤー 1 の期待利得とプレイヤー 2 の期待利得を、この順に組で答えよ。
難易度 1（教科書の例題レベル）
プレイヤー 1 は行 $U, D$ のどちらかを、プレイヤー 2 は列 $L, R$ のどちらかを、互いの選択を知らずに同時に選ぶ 2 人ゼロ和ゲームを考える。プレイヤー 1 が受け取る利得（プレイヤー 2 が支払う額）は次の利得行列で与えられる。
$U D L 3 - 2 R - 1 4$
両プレイヤーは混合戦略を使ってよいものとする。このゲームの値（プレイヤー 1 の期待利得の $max_{p} min$ の値）を求めよ。
難易度 1（教科書の例題レベル）
テニスの試合で、サーバー（プレイヤー 1）はサーブの方向を「左 $L$ 」「右 $R$ 」のどちらかに決めます。レシーバー（プレイヤー 2）は、どちらに備えるかを「左に備える $l$ 」「右に備える $r$ 」のどちらかに決めます。2 人は互いの選択を知らずに同時に選びます。これを 2 人ゼロ和ゲームと考えます。サーバーが受け取る得点（レシーバーが失う得点）は次の利得行列で与えられます（行がサーバーの選択、列がレシーバーの選択）。
$L R l - 2 2 r 3 - 1$
2 人とも混合戦略を使ってよいものとします。このゲームの値（サーバーが保証できる期待得点の最大値）を求めなさい。
難易度 1（教科書の例題レベル）
2 つの店 $A$ , $B$ が、来週のセールの方法をそれぞれ $3$ 通りの中から 1 つずつ、互いの選択を知らずに同時に選ぶ。店 $A$ の方法を $x_{1}, x_{2}, x_{3}$ 、店 $B$ の方法を $y_{1}, y_{2}, y_{3}$ とする。来週、店 $B$ から店 $A$ に移る客の数（単位は百人。負の値は店 $A$ から店 $B$ に移ることを表す）は次の表のとおりで、店 $A$ はこれを大きく、店 $B$ はこれを小さくしたい。これを、店 $A$ がプレイヤー 1、店 $B$ がプレイヤー 2 で、店 $A$ の利得が表の値である 2 人ゼロ和ゲームとみなす。
$y_{1}$ $y_{2}$ $y_{3}$
$x_{1}$ $3$ $- 1$ $2$
$x_{2}$ $4$ $2$ $5$
$x_{3}$ $- 2$ $1$ $6$
このゲームの値を求めよ。
難易度 1（教科書の例題レベル）
プレイヤー 1, 2 が $120$ 万円の分け方を、最大 $3$ ラウンドの交互提案で交渉する。
- ラウンド $t = 1, 3$ ではプレイヤー 1 が、ラウンド $t = 2$ ではプレイヤー 2 が提案者となり、分配 $(x_{1}, x_{2})$ （ $x_{1} + x_{2} = 120$ 、 $x_{1} \geq 0$ 、 $x_{2} \geq 0$ の実数）を提案する。もう一方のプレイヤー（応答者）は受諾か拒否を選ぶ。
- 受諾されればその分配で交渉は終わる。拒否されれば次のラウンドに進む。ラウンド $3$ の提案も拒否された場合は、両者の取り分はともに $0$ になる。
- ラウンド $t$ で分配 $(x_{1}, x_{2})$ に合意したとき、プレイヤー $i$ の利得は $δ_{i}^{t - 1} x_{i}$ である。ここで割引因子は $δ_{1} = \frac{1}{2}$ 、 $δ_{2} = \frac{2}{3}$ とする。
- 応答者は、受諾しても拒否しても利得が等しいときは受諾するものとする。
このゲームの部分ゲーム完全均衡におけるプレイヤー 1 の利得 $u_{1}$ とプレイヤー 2 の利得 $u_{2}$ を、組 $(u_{1}, u_{2})$ の形で求めよ（単位は万円）。
難易度 1（教科書の例題レベル）
プレイヤー 1, 2 が、賞金 $90$ 万円の分け方を次の交互提案の交渉で決める。交渉は最大 $3$ ラウンドである。
- ラウンド $1$ とラウンド $3$ ではプレイヤー 1 が、ラウンド $2$ ではプレイヤー 2 が提案者になり、分配 $(x_{1}, x_{2})$ （ $x_{1} \geq 0, x_{2} \geq 0, x_{1} + x_{2} = 90$ 、単位は万円）を提案する。もう一方のプレイヤーは受諾か拒否を選ぶ。
- 受諾されればその分配で交渉は終わる。拒否されれば次のラウンドに進む。ラウンド $3$ の提案も拒否されたら、両者とも $0$ 万円を得る。
- ラウンド $t$ で分配 $(x_{1}, x_{2})$ が受諾されたとき、プレイヤー $i$ の利得は $δ_{i}^{t - 1} x_{i}$ とする。ここで割引因子は $δ_{1} = \frac{1}{2}$ , $δ_{2} = \frac{2}{3}$ である。
- 受諾と拒否で利得が等しいとき、応答者は受諾するものとする。
このゲームの部分ゲーム完全均衡におけるプレイヤー 1 の利得とプレイヤー 2 の利得を、この順に組 $(u_{1}, u_{2})$ で答えよ。
難易度 1（教科書の例題レベル）
プレイヤー 1, 2 が、 $9000$ 円を 2 人でどう分けるかを、最大 $3$ ラウンドの交互提案の交渉で決める。
- ラウンド $1$ と $3$ ではプレイヤー 1 が、ラウンド $2$ ではプレイヤー 2 が提案者になる。提案者は分け方 $(x_{1}, x_{2})$ （ $x_{1} + x_{2} = 9000$ , $x_{1} \geq 0$ , $x_{2} \geq 0$ 、 $x_{i}$ はプレイヤー $i$ の取り分で実数）を提案し、もう一方のプレイヤー（応答者）が受諾するか拒否するかを選ぶ。
- 受諾されればその分け方で交渉は終わる。拒否されれば次のラウンドに進む。ラウンド $3$ の提案が拒否された場合は、2 人とも $0$ 円を受け取る。
- ラウンド $t$ で分け方 $(x_{1}, x_{2})$ が合意されたとき、プレイヤー $i$ の利得は $δ_{i}^{t - 1} x_{i}$ とする。割引因子は $δ_{1} = \frac{1}{2}$ , $δ_{2} = \frac{2}{3}$ である。
- 応答者は、受諾と拒否で利得が等しいときは受諾する。
このゲームの部分ゲーム完全均衡における、プレイヤー 1 の利得とプレイヤー 2 の利得を、この順に組で求めよ。
難易度 2（教科書の演習問題レベル）
いくつかの石の山がある。2 人のプレイヤーが交互に、どれか 1 つの山を選び、その山から石をちょうど $1$ 個、 $3$ 個、 $4$ 個のいずれかの個数だけ取り除く（山にある石の個数より多くは取れない）。動かせなくなったプレイヤーの負けとする（正規形）。
石が $5$ 個、 $6$ 個、 $11$ 個の 3 つの山からなる局面のグランディ数（スプレイグ・グランディ数）を求めよ。
難易度 2（教科書の演習問題レベル）
2 つの企業 1, 2 が、同じ商品の生産量をそれぞれ同時に 1 回だけ選ぶ。企業 1 の生産量を $x$ 、企業 2 の生産量を $y$ とし、 $x, y$ はどちらも ${0, 1, 2, \dots, 10}$ の中から選ぶ（整数値しか選べない）。各企業の利得は
$u_{1} (x, y) = x (10 - x - y), u_{2} (x, y) = y (10 - x - y)$
で与えられる（値が負になることもある）。各企業は自分の利得を最大にしようとする。
この 2 人ゲームの純粋戦略のナッシュ均衡 $(x, y)$ の個数を求めよ。
難易度 2（教科書の演習問題レベル）
プレイヤー 1, 2 による次の完全情報の展開形ゲームを考える。利得は（プレイヤー 1 の利得, プレイヤー 2 の利得）の順に書く。
- まずプレイヤー 1 が $L$ または $R$ を選ぶ。
- $L$ が選ばれたとき、プレイヤー 2 が $ℓ_{1}$ または $ℓ_{2}$ を選ぶ。 $ℓ_{1}$ ならゲームは終わり利得は $(2, 3)$ 、 $ℓ_{2}$ なら利得は $(5, 1)$ である。
- $R$ が選ばれたとき、プレイヤー 2 が $r_{1}$ または $r_{2}$ を選ぶ。 $r_{1}$ ならゲームは終わり利得は $(3, 1)$ である。
- $R$ のあと $r_{2}$ が選ばれたとき、プレイヤー 1 が $x$ または $y$ を選ぶ。 $x$ なら利得は $(6, 2)$ 、 $y$ なら利得は $(3, 5)$ である。
このゲームの部分ゲーム完全均衡において実現する利得を、（プレイヤー 1 の利得, プレイヤー 2 の利得）の組で求めよ。
難易度 2（教科書の演習問題レベル）
プレイヤー 1 は行 $I, II$ のどちらかを、プレイヤー 2 は列 $a, b, c$ のどれかを同時に選ぶ 2 人ゼロ和ゲームを考える。プレイヤー 1 が受け取る利得（プレイヤー 2 が支払う額）は次の行列で与えられる。
$a$ $b$ $c$
$I$ $4$ $1$ $2$
$II$ $0$ $3$ $1$
両プレイヤーとも混合戦略を用いることができるとき、このゲームの値（プレイヤー 1 の期待利得のマックスミニ値）を求めよ。
難易度 2（教科書の演習問題レベル）
いくつかの石の山がある。2 人のプレイヤーが交互に、どれか 1 つの山を選び、その山から石を取り除く。ただし、石が $n$ 個ある山から取り除ける個数 $k$ は $1 \leq k \leq ⌊ \frac{n}{2} ⌋$ を満たす整数に限る（つまり、山の石の半分以下しか取れない）。どの山からも石を取れなくなったプレイヤーの負けとする。
石の個数が $9$ 個、 $12$ 個、 $13$ 個の 3 つの山からなる局面のグランディ数を求めよ。
難易度 2（教科書の演習問題レベル）
2 人の友人 A, B が、週末に出かける場所を相談せずに同時に選ぶ。A は「美術館」か「スタジアム」のどちらかを、B も「美術館」か「スタジアム」のどちらかを選ぶ。2 人とも同じ場所を選べば会えるが、違う場所を選ぶと会えない。利得は次のとおりで、各組は（A の利得, B の利得）の順に書く。
- 2 人とも美術館: $(3, 1)$
- 2 人ともスタジアム: $(1, 4)$
- A が美術館、B がスタジアム: $(0, 0)$
- A がスタジアム、B が美術館: $(0, 0)$
このゲームには、2 人とも両方の場所を正の確率で選ぶ混合戦略のナッシュ均衡がただ 1 つある。この均衡における A の期待利得と B の期待利得を、この順に組で求めよ。
難易度 2（教科書の演習問題レベル）
プレイヤー 1 は $1$ 枚の硬貨を箱 $A$ 、箱 $B$ のどちらかに隠し、プレイヤー 2 は硬貨がどちらの箱にあるかを当てる。2 人は互いの選択を知らずに同時に選ぶ。お金のやりとりは次のとおりとする。
- 硬貨が $A$ にあり、プレイヤー 2 が $A$ と答えた（当たり）: プレイヤー 1 がプレイヤー 2 に $3$ 円払う。
- 硬貨が $A$ にあり、プレイヤー 2 が $B$ と答えた（はずれ）: プレイヤー 2 がプレイヤー 1 に $2$ 円払う。
- 硬貨が $B$ にあり、プレイヤー 2 が $A$ と答えた（はずれ）: プレイヤー 2 がプレイヤー 1 に $1$ 円払う。
- 硬貨が $B$ にあり、プレイヤー 2 が $B$ と答えた（当たり）: プレイヤー 1 がプレイヤー 2 に $1$ 円払う。
これをプレイヤー 1 の利得（円）を成分とする 2 人ゼロ和ゲームとみなし、両プレイヤーが混合戦略を使えるとする。このゲームの値（プレイヤー 1 の利得の期待値に関するミニマックス値）を求めよ。
難易度 2（教科書の演習問題レベル）
$4$ 人のプレイヤー $1, 2, 3, 4$ が、共同の設備を作るために、それぞれ同時に「出資する（ $C$ ）」か「出資しない（ $D$ ）」かを 1 回だけ選ぶ。出資したプレイヤーの人数を $k$ （ $0 \leq k \leq 4$ ）とする。
- $k \geq 2$ のとき設備が完成し、 $4$ 人全員がそれぞれ $3$ の便益を得る。 $k \leq 1$ のときは設備は完成せず、便益は $0$ である。
- 出資したプレイヤーは、設備が完成するかどうかにかかわらず費用 $2$ を負担する。
各プレイヤーの利得は（便益） $-$ （自分が負担した費用）とする。このゲームの純粋戦略ナッシュ均衡（4 人の戦略の組）の個数を求めよ。
難易度 2（教科書の演習問題レベル）
プレイヤー 1 は行 $R_{1}, R_{2}, R_{3}$ のどれかを、プレイヤー 2 は列 $C_{1}, C_{2}$ のどちらかを、互いの選択を知らずに同時に選ぶ 2 人ゼロ和ゲームを考える。プレイヤー 1 が受け取る利得（プレイヤー 2 が支払う額）は次の表のとおりである。
$C_{1}$ $C_{2}$
$R_{1}$ $3$ $- 1$
$R_{2}$ $- 2$ $4$
$R_{3}$ $1$ $0$
両プレイヤーが混合戦略を使えるとき、このゲームの値（プレイヤー 1 の期待利得のマックスミニ値）を求めよ。
難易度 2（教科書の演習問題レベル）
$n$ を $2$ 以上の整数、 $c$ を $1 < c < n$ をみたす実数とする。プレイヤー $1, 2, \dots, n$ の $n$ 人が、それぞれ戦略 $s_{i} \in {0, 1}$ を同時に選ぶ（ $s_{i} = 1$ は「参加する」、 $s_{i} = 0$ は「参加しない」を表す）。戦略の組 $s = (s_{1}, \dots, s_{n})$ に対し、参加者の人数を $m (s) = s_{1} + s_{2} + \dots + s_{n}$ とし、プレイヤー $i$ の利得を
$u_{i} (s) = {m (s) - c 0 (s_{i} = 1) (s_{i} = 0)$
と定める。ここで、戦略の組 $s$ が純粋戦略のナッシュ均衡であるとは、どのプレイヤー $i$ についても、他のプレイヤーの戦略を固定したまま $s_{i}$ を別の戦略に変えても $u_{i}$ が真に増加しないことをいう。
このゲームの純粋戦略のナッシュ均衡は、全員が参加しない組 $(0, 0, \dots, 0)$ と全員が参加する組 $(1, 1, \dots, 1)$ のちょうど $2$ 個であることを証明せよ。
難易度 2（教科書の演習問題レベル）
石の山が 1 つあり、2 人のプレイヤーが交互に、山から石を $1$ 個、 $2$ 個、 $5$ 個のいずれかの個数だけ取り除く（山にある石より多くは取れない）。石の個数が $n$ （ $n$ は $0$ 以上の整数）の局面のグランディ数 $g (n)$ を
$g (n) = mex {g (n - k) ∣ k \in {1, 2, 5}, k \leq n}$
で定める。ここで、 $0$ 以上の整数からなる有限集合 $A$ に対し、 $mex A$ は $A$ に属さない最小の $0$ 以上の整数を表す（特に $mex \emptyset = 0$ ）。
すべての $0$ 以上の整数 $n$ について、 $g (n)$ は $n$ を $3$ で割った余りに等しいことを証明せよ。
難易度 2（教科書の演習問題レベル）
$a, b, c, d$ を正の実数とする。プレイヤー 1 は戦略 $U, D$ のどちらかを、プレイヤー 2 は戦略 $L, R$ のどちらかを同時に選ぶ 2 人ゲームを考える。各戦略の組での利得（プレイヤー 1 の利得, プレイヤー 2 の利得）は次のとおりである。
$(U, L) : (a, 0), (U, R) : (0, c), (D, L) : (0, d), (D, R) : (b, 0)$
プレイヤー 1 が確率 $p$ で $U$ 、確率 $1 - p$ で $D$ を選び、プレイヤー 2 が確率 $q$ で $L$ 、確率 $1 - q$ で $R$ を選ぶ混合戦略の組を $(p, q) \in [0, 1]^{2}$ で表し、2 人は独立に戦略を選ぶとする。 $(p, q)$ が混合戦略のナッシュ均衡であるとは、 $p$ が $q$ に対してプレイヤー 1 の期待利得を最大にし（ $[0, 1]$ の中で）、かつ $q$ が $p$ に対してプレイヤー 2 の期待利得を最大にすることをいう。
このゲームの混合戦略のナッシュ均衡はただ 1 つであり、その均衡におけるプレイヤー 1 の期待利得は $\frac{ab}{a + b}$ であることを証明せよ。
難易度 2（教科書の演習問題レベル）
3 つの企業 $1, 2, 3$ が同じ商品を生産し、次の順番で生産量を決める。
- まず企業 $1$ が生産量 $q_{1} (q_{1} \geq 0)$ を選ぶ。
- 企業 $2$ は $q_{1}$ を観察したうえで生産量 $q_{2} (q_{2} \geq 0)$ を選ぶ。
- 企業 $3$ は $q_{1}, q_{2}$ を観察したうえで生産量 $q_{3} (q_{3} \geq 0)$ を選ぶ。
生産量はいずれも実数値をとれるものとする。総生産量を $Q = q_{1} + q_{2} + q_{3}$ とすると、商品の価格は $P = 36 - Q$ で決まり、どの企業も 1 単位あたりの生産費用は $4$ である。したがって企業 $i$ の利得（利潤）は
$π_{i} = (36 - Q) q_{i} - 4 q_{i} = (32 - Q) q_{i} (i = 1, 2, 3)$
である。この完全情報の展開形ゲームの部分ゲーム完全均衡において、均衡経路上で実現する利潤の組 $(π_{1}, π_{2}, π_{3})$ を求めよ。
難易度 2（教科書の演習問題レベル）
$4$ つの航空会社 $1, 2, 3, 4$ が、共同で $1$ 本の滑走路を建設する。会社 $i$ が使う機体に必要な長さの滑走路を単独で建設すると、その費用は $c_{i}$ （単位：億円）で、
$c_{1} = 8, c_{2} = 20, c_{3} = 32, c_{4} = 50$
である。長い滑走路は短い滑走路の用途も兼ねる。そのため、会社の集合 $S \subseteq N = {1, 2, 3, 4}$ が共同で建設するときの費用は
$C (S) = i \in S max c_{i} (S \neq = \emptyset), C (\emptyset) = 0$
とする。
この費用ゲーム $(N, C)$ のシャープレイ値 $(φ_{1}, φ_{2}, φ_{3}, φ_{4})$ を求めよ。ただし、各会社 $i$ のシャープレイ値は
$φ_{i} = S \subseteq N ∖ {i} \sum \frac{∣ S ∣ ! ( 4 - ∣ S ∣ - 1 )!}{4 !} (C (S \cup {i}) - C (S))$
で定める（各会社の費用負担額を表す）。答えは $(φ_{1}, φ_{2}, φ_{3}, φ_{4})$ の順の組で答えよ。
難易度 2（教科書の演習問題レベル）
ある職場で、従業員（プレイヤー 1）は「働く（ $W$ ）」か「怠ける（ $S$ ）」かを、管理者（プレイヤー 2）は「検査する（ $I$ ）」か「検査しない（ $N$ ）」かを、互いの選択を知らずに同時に 1 回だけ選ぶ。利得は次の表のとおりである。各欄の左が従業員の利得、右が管理者の利得である。
$W S I (6, - 1) (0, - 3) N (6, 2) (10, - 10)$
このゲームのナッシュ均衡（混合戦略まで含める）はただ 1 つ存在する。この均衡における従業員の期待利得と管理者の期待利得を、この順に組で求めよ。
難易度 2（教科書の演習問題レベル）
サッカーの PK で、キッカー（プレイヤー 1）はシュートの方向を「左 $L$ 」「中央 $C$ 」「右 $R$ 」から 1 つ選ぶ。ゴールキーパー（プレイヤー 2）は守る位置を「左 $L$ 」「中央 $C$ 」「右 $R$ 」から 1 つ選ぶ。2 人は互いの選択を知らずに同時に選ぶ。それぞれの組合せでゴールが決まる確率は次の表のとおりである（行がキッカーの選択、列がキーパーの選択）。
$L C R L 0.5 0.8 0.9 C 0.9 0.2 0.9 R 0.9 0.8 0.6$
キッカーはゴールが決まる確率を最大にしたく、キーパーはそれを最小にしたい。この状況を、キッカーの利得がゴールの決まる確率であり、キーパーの利得がその符号を変えたものである 2 人ゼロ和ゲームとみなす。両者とも混合戦略を用いてよいとき、このゲームの値を求めよ。
難易度 3（期末試験の応用レベル）
プレイヤー集合 $N = {1, 2, 3}$ の提携形ゲーム（特性関数形ゲーム） $v$ が
$v (\emptyset) = 0, v ({1}) = v ({2}) = v ({3}) = 0,$
$v ({1, 2}) = 6, v ({1, 3}) = 8, v ({2, 3}) = 4, v ({1, 2, 3}) = 12$
で与えられている。このゲームのシャープレイ値 $(φ_{1}, φ_{2}, φ_{3})$ を、この順に組で求めよ。
難易度 3（期末試験の応用レベル）
売り手のプレイヤー $1$ が品物を $1$ 個だけ持っており、プレイヤー $1$ 自身にとってこの品物の価値は $0$ である。買い手のプレイヤー $2, 3, 4$ はそれぞれこの品物を高々 $1$ 個欲しがっており、品物を手に入れたときの価値はそれぞれ $4, 7, 10$ である。この状況を、プレイヤー集合 $N = {1, 2, 3, 4}$ の提携形ゲーム（特性関数形ゲーム） $v$ として次のように表す。各提携 $S \subseteq N$ に対し、 $v (S) = {max {b_{j} ∣ j \in S, j \neq = 1} 0 (1 \in S かつ S \neq = {1}) (それ以外)$ とする。ここで $b_{2} = 4, b_{3} = 7, b_{4} = 10$ である（ $v (\emptyset) = 0$ ）。このゲームのシャープレイ値を $(φ_{1}, φ_{2}, φ_{3}, φ_{4})$ とするとき、この組を求めよ。
難易度 3（期末試験の応用レベル）
プレイヤー 1, 2 が、大きさ $1$ のケーキの分け方を次の交互提案の交渉で決める。交渉は最大 $4$ ラウンドで、ラウンド $1, 3$ ではプレイヤー 1 が、ラウンド $2, 4$ ではプレイヤー 2 が提案者になる。
- 各ラウンドで、提案者はプレイヤー 1 の取り分 $x$ とプレイヤー 2 の取り分 $1 - x$ （ $0 \leq x \leq 1$ の実数）を提案する。
- もう一方のプレイヤー（応答者）は、それを見てから受諾するか拒否するかを選ぶ。受諾すればその分け方で交渉は終わる。拒否すれば次のラウンドに進む。
- ラウンド $4$ の提案も拒否された場合、2 人の利得はともに $0$ である。
- ラウンド $t (t = 1, 2, 3, 4)$ で分け方 $(x, 1 - x)$ が受諾されたとき、プレイヤー 1 の利得は $(\frac{3}{5})^{t - 1} x$ 、プレイヤー 2 の利得は $(\frac{4}{5})^{t - 1} (1 - x)$ である。
このゲームを完全情報の展開形ゲームとみなし、応答者は受諾と拒否が無差別なときは受諾するものとする。このとき部分ゲーム完全均衡はただ 1 つに定まる。部分ゲーム完全均衡におけるプレイヤー 1 の利得を求めよ。
難易度 3（期末試験の応用レベル）
いくつかの石の山がある。2 人のプレイヤーが交互に次の操作を行う。
- どれか 1 つの山を選び、それを石の個数が異なる 2 つの空でない山に分ける（たとえば $7$ 個の山は $1$ 個と $6$ 個、 $2$ 個と $5$ 個、 $3$ 個と $4$ 個のいずれかに分けられる。 $6$ 個の山を $3$ 個と $3$ 個に分けることはできない）。
操作ができなくなったプレイヤーの負けとする（石が $1$ 個または $2$ 個の山はもう分けられない）。
最初に石が $8$ 個、 $11$ 個、 $13$ 個の $3$ つの山があり、先手から始める。先手の最初の操作のうち、その後の後手の操作によらず先手が必ず勝てるようにする操作（勝ちにつながる手）は何通りあるか。ただし、操作は「どの山を選ぶか」と「どの 2 つの個数に分けるか」の組で区別し、分けてできる 2 つの山の順序は区別しない。
難易度 3（期末試験の応用レベル）
ある委員会には $4$ 人の委員 $1, 2, 3, 4$ がおり、それぞれ $4$ 票、 $3$ 票、 $2$ 票、 $1$ 票の票数を持つ（合計 $10$ 票）。議案は、賛成する委員の票数の合計が $6$ 票以上のときに可決される。
プレイヤー集合 $N = {1, 2, 3, 4}$ の提携形ゲーム $v$ を、提携 $S \subseteq N$ に属する委員の票数の合計を $w (S)$ （ $w (\emptyset) = 0$ ）として
$v (S) = {10 (w (S) \geq 6) (w (S) < 6)$
で定める。このゲームにおける委員 $1, 2, 3, 4$ のシャープレイ値 $ϕ_{1}, ϕ_{2}, ϕ_{3}, ϕ_{4}$ を求め、組 $(ϕ_{1}, ϕ_{2}, ϕ_{3}, ϕ_{4})$ の形で答えよ。
難易度 3（期末試験の応用レベル）
プレイヤー 1, 2 が大きさ $1$ のパイの分け方を、最大 $4$ ラウンドの交互提案で交渉する。
- ラウンド $t = 1, 3$ ではプレイヤー 1 が、ラウンド $t = 2, 4$ ではプレイヤー 2 が分配 $(x_{1}, x_{2})$ （ $x_{1} \geq 0, x_{2} \geq 0, x_{1} + x_{2} = 1$ 、 $x_{i}$ はプレイヤー $i$ の取り分で実数）を提案する。
- 提案されなかった側のプレイヤーは、その提案を受け入れるか拒否するかを選ぶ。受け入れればその分配で交渉は終わる。拒否すれば次のラウンドに進む。
- ラウンド $4$ の提案も拒否された場合、2 人の利得はともに $0$ である。
- ラウンド $t$ で分配 $(x_{1}, x_{2})$ に合意したとき、プレイヤー $i$ の利得は $δ_{i}^{t - 1} x_{i}$ である。ここで $δ_{1} = \frac{2}{3}, δ_{2} = \frac{1}{2}$ とする。
各プレイヤーは、受け入れても拒否しても利得が等しいときは受け入れるものとする。このゲームの部分ゲーム完全均衡において、ラウンド $1$ で合意される分配 $(x_{1}, x_{2})$ を求めよ。
難易度 3（期末試験の応用レベル）
ある商品の市場に、既存企業 $1$ と参入を検討している企業 $2$ がいる。次の展開形ゲームを考える。
1. まず企業 $1$ が生産量 $q_{1} (q_{1} \geq 0)$ を選ぶ。
2. 企業 $2$ は $q_{1}$ を観察したうえで、「参入しない」か「参入する」かを選ぶ。参入する場合は、同時に生産量 $q_{2} (q_{2} \geq 0)$ を選ぶ。
市場価格は総生産量 $Q$ （企業 $2$ が参入しないときは $Q = q_{1}$ 、参入するときは $Q = q_{1} + q_{2}$ ）に対して $P = max {12 - Q, 0}$ で決まる。どちらの企業も生産費用は $0$ である。企業 $2$ が参入するときは、生産量によらず参入費用 $4$ がかかる。各企業の利得は利潤であり、企業 $1$ の利潤は $P q_{1}$ 、企業 $2$ の利潤は参入しないとき $0$ 、参入するとき $P q_{2} - 4$ である。また、企業 $2$ は、参入しても参入しなくても利潤が等しくなるときは参入しないものとする。
このゲームの部分ゲーム完全均衡における企業 $1$ の生産量 $q_{1}$ と企業 $1$ の利潤を、この順に組で求めよ。
難易度 3（期末試験の応用レベル）
$2$ 人のプレイヤー $1, 2$ が、 $10$ 万円の賞金の分け方を次の規則で決める。プレイヤー $1$ は要求額 $x$ 、プレイヤー $2$ は要求額 $y$ （単位は万円）を、互いの選択を知らずに同時に $1$ 回だけ選ぶ。 $x, y$ はどちらも ${0, 1, 2, \dots, 10}$ の中から選ぶ。
- $x + y \leq 10$ のとき、プレイヤー $1$ は $x$ 、プレイヤー $2$ は $y$ を受け取る（余りは誰も受け取らない）。
- $x + y > 10$ のとき、 $2$ 人とも $0$ を受け取る。
各プレイヤーの利得は受け取る金額である。このゲームの純粋戦略ナッシュ均衡 $(x, y)$ の個数を求めよ。
難易度 3（期末試験の応用レベル）
プレイヤー 1 は行 $T, B$ のどちらかを、プレイヤー 2 は列 $L, C, R$ のどれかを、互いの選択を知らずに同時に選ぶ 2 人ゲーム（非ゼロ和）を考える。各組の利得は次の表のとおりで、各成分は (プレイヤー 1 の利得, プレイヤー 2 の利得) を表す。
$T B L (1, 4) (2, 0) C (3, 0) (0, 4) R (0, 3) (2, 2)$
両プレイヤーは混合戦略を用いることができ、各プレイヤーは自分の期待利得を最大にしようとする。このゲームの混合戦略まで含めたナッシュ均衡はただ 1 つである。その均衡におけるプレイヤー 1 の期待利得とプレイヤー 2 の期待利得を、この順に組で求めよ。
難易度 3（期末試験の応用レベル）
2 人のプレイヤー 1, 2 が、2 つの拠点 $A$ , $B$ を争う次の 2 人ゼロ和ゲームを考える。
- プレイヤー 1 は $4$ 部隊、プレイヤー 2 は $3$ 部隊を持ち、それぞれ自分の全部隊を拠点 $A$ , $B$ に分けて配置する。各拠点に置く部隊数は $0$ 以上の整数とする。2 人は互いの配置を知らずに同時に $1$ 回だけ配置を決める。
- 各拠点で、置いた部隊数が多いほうがその拠点を獲得し、相手からその拠点の価値に等しい額を受け取る。拠点 $A$ の価値は $2$ 、拠点 $B$ の価値は $1$ である。部隊数が等しい拠点では支払いは生じない。
プレイヤー 1 が受け取る総額（負の値は支払いを表す）をプレイヤー 1 の利得とし、プレイヤー 2 の利得はその符号を変えたものとする。両プレイヤーとも混合戦略を用いてよいとき、このゲームの値（プレイヤー 1 の期待利得のマックスミニ値、すなわちミニマックス値）を求めよ。
難易度 3（期末試験の応用レベル）
区別のできる $6$ 人のドライバー $1, 2, \dots, 6$ が、出発地から目的地へ向かう経路を、互いに相談せずに同時に $1$ つずつ選ぶ。経路は $A, B, C$ の $3$ 本である。ある経路を選んだドライバーの人数が $k$ 人（ $k$ は正の整数）のとき、その経路を選んだ各ドライバーの所要時間（分）は
$c_{A} (k) = 3 k, c_{B} (k) = 2 k + 2, c_{C} (k) = k + 6$
である。各ドライバーは自分の所要時間を小さくしたい（利得は所要時間に $- 1$ を掛けたもの）とする。
戦略の組（ $6$ 人それぞれがどの経路を選ぶかの割り当て、全部で $3^{6}$ 通り）のうち、どのドライバーも自分だけ経路を変えることで所要時間を真に短くできないもの、すなわち純粋戦略のナッシュ均衡の個数を求めよ。
難易度 3（期末試験の応用レベル）
横一列に並んだマス目からなる細長い盤が $3$ 枚あり、マスの個数はそれぞれ $6$ 個、 $10$ 個、 $13$ 個である。はじめはすべてのマスが空いている。2 人のプレイヤーが交互に、どれか $1$ 枚の盤を選び、その盤の隣り合う $2$ つの空きマスにドミノを $1$ 枚置く（置いたドミノは以後動かさない。ドミノは盤をまたいで置けない）。自分の手番でドミノを置けなくなったプレイヤーの負けとする。
この初期局面で先手が必勝であることが知られている。先手の最初の手のうち、その手を打った後も先手が必勝であり続ける手（必勝手）は何通りあるか。ただし、ドミノが覆う $2$ マスの組が異なる置き方は、異なる手として数える。
難易度 3（期末試験の応用レベル）
プレイヤー全体の集合を $N = {1, 2, 3, 4}$ とする提携形（特性関数形）ゲーム $(N, v)$ を考える。 $t$ は $0 \leq t \leq 12$ を満たす実数の定数とする。 $j, k$ は $2, 3, 4$ のうちの互いに異なるものを表し、特性関数 $v$ は次で与えられる。
- $v (\emptyset) = 0$ 、 $v ({i}) = 0 (i = 1, 2, 3, 4)$
- $v ({1, j}) = 6$ 、 $v ({j, k}) = 0$
- $v ({1, j, k}) = 9$ 、 $v ({2, 3, 4}) = t$
- $v (N) = 12$
このゲームのコア $C (v)$ を、
$i \in N \sum x_{i} = v (N)$
を満たし、かつすべての提携 $S \subseteq N$ について
$i \in S \sum x_{i} \geq v (S)$
を満たす $x = (x_{1}, x_{2}, x_{3}, x_{4}) \in R^{4}$ 全体の集合と定める。
コア $C (v)$ が空でないような $t$ の最大値を $t_{1}$ 、シャープレイ値 $(ϕ_{1}, ϕ_{2}, ϕ_{3}, ϕ_{4})$ が $C (v)$ に属するような $t$ の最大値を $t_{2}$ とする。 $t_{1}, t_{2}$ をこの順に組 $(t_{1}, t_{2})$ で求めよ。
難易度 4（大学院入試の標準レベル）
区別のできる $7$ 人のプレイヤー $1, 2, \dots, 7$ が、同時に経路 $A, B, C$ のうちちょうど 1 つを選ぶ。経路 $A, B, C$ を選んだ人数をそれぞれ $a, b, c$ （ $a + b + c = 7$ ）とするとき、各プレイヤーの費用は
- 経路 $A$ を選んだプレイヤー: $a$
- 経路 $B$ を選んだプレイヤー: $2 b$
- 経路 $C$ を選んだプレイヤー: $c + 3$
であり、各プレイヤーは自分の費用を最小にしたい。
このゲームの純粋戦略ナッシュ均衡（7 人それぞれがどの経路を選ぶかの組）の個数を求めよ。
難易度 4（大学院入試の標準レベル）
プレイヤー 1 は戦略 $T, M, B$ の中から、プレイヤー 2 は戦略 $L, C, R$ の中から、それぞれ同時に 1 つを選ぶ 2 人の戦略形ゲーム（双行列ゲーム）を考える。利得は次の表のとおりで、各欄は（プレイヤー 1 の利得, プレイヤー 2 の利得）の順に書いてある。
$L$ $C$ $R$
$T$ $(3, 0)$ $(0, 6)$ $(2, 3)$
$M$ $(1, 5)$ $(1, 1)$ $(1, 0)$
$B$ $(0, 4)$ $(3, 0)$ $(1, 3)$
各プレイヤーは混合戦略（純粋戦略上の確率分布）を用いることができ、期待利得を最大化するものとする。このゲームの混合戦略の範囲でのナッシュ均衡はただ 1 つである。その均衡におけるプレイヤー 1 の期待利得とプレイヤー 2 の期待利得を、この順に組で求めよ。
難易度 4（大学院入試の標準レベル）
プレイヤー集合 $N = {1, 2, 3, 4, 5}$ の提携形ゲーム（特性関数形ゲーム）を考える。プレイヤー $1, 2$ はそれぞれ左手用の手袋を $1$ 枚ずつ、プレイヤー $3, 4, 5$ はそれぞれ右手用の手袋を $1$ 枚ずつ持っており、左右 $1$ 枚ずつの組が $1$ つできるごとに価値 $1$ が生まれる。すなわち提携 $S \subseteq N$ に対し、 $S$ に含まれる ${1, 2}$ のプレイヤーの人数を $ℓ (S)$ 、 ${3, 4, 5}$ のプレイヤーの人数を $r (S)$ として
$v (S) = min {ℓ (S), r (S)}$
と定める（ $v (\emptyset) = 0$ ）。
配分 $x = (x_{1}, \dots, x_{5}) \in R^{5}$ のうち、 $\sum_{i \in N} x_{i} = v (N)$ かつすべての提携 $S \subseteq N$ について $\sum_{i \in S} x_{i} \geq v (S)$ を満たすもの全体をコアという。このゲームのコアはただ 1 点からなる。そのコアの点の第 1 成分を $c_{1}$ 、プレイヤー $1$ のシャープレイ値を $φ_{1}$ とするとき、 $c_{1} - φ_{1}$ を求めよ。
難易度 4（大学院入試の標準レベル）
$10$ 人のプレイヤー $1, 2, \dots, 10$ が円形に並んでおり、プレイヤー $i$ の隣人はプレイヤー $i - 1$ と $i + 1$ である（添字は $10$ を法として考え、プレイヤー $0$ はプレイヤー $10$ 、プレイヤー $11$ はプレイヤー $1$ を表す）。各プレイヤー $i$ は同時に $1$ 回だけ、行動 $x_{i} \in {0, 1}$ を選ぶ。プレイヤー $i$ の利得は、2 人の隣人のうち自分と異なる行動を選んだ人数とする。すなわち
$u_{i} (x_{1}, \dots, x_{10}) = ∣ x_{i} - x_{i - 1} ∣ + ∣ x_{i} - x_{i + 1} ∣$
である。この $10$ 人ゲームの純粋戦略のナッシュ均衡（行動の組 $(x_{1}, \dots, x_{10})$ ）の個数を求めよ。
難易度 4（大学院入試の標準レベル）
2 人のプレイヤー 1, 2 が、それぞれ弾を 1 発だけ持って決闘する（音の聞こえる決闘）。時刻 $0$ に離れた位置から互いに近づき始め、時刻 $1$ に同じ地点に着く。時刻 $t (0 \leq t \leq 1)$ に撃ったとき命中する確率は、プレイヤー 1 が $t$ 、プレイヤー 2 が $t^{2}$ である。撃った音は相手に聞こえるので、先に撃って外した側は、相手が時刻 $1$ まで待って確実に命中させるとする。
プレイヤー 1 は撃つ時刻 $x \in [0, 1]$ を、プレイヤー 2 は撃つ時刻 $y \in [0, 1]$ を、あらかじめ同時に選ぶ。命中させた側の利得を $1$ 、命中された側の利得を $- 1$ とすると、プレイヤー 1 の期待利得（プレイヤー 2 の期待損失）は次の関数 $K (x, y)$ で表される 2 人ゼロ和ゲームになる。
$K (x, y) = ⎩ ⎨ ⎧ 2 x - 1 x - x^{2} 1 - 2 y^{2} (x < y) (x = y) (x > y)$
（ $x < y$ のときは、プレイヤー 1 が先に撃ち、確率 $x$ で命中して利得 $1$ 、外れると時刻 $1$ にプレイヤー 2 に撃たれて利得 $- 1$ となる。 $x > y$ のときも同様。 $x = y$ のときは $x < y$ と $x > y$ の式の平均とする。）
このゲームは純粋戦略の範囲で値をもつ。すなわち
$x \in [0, 1] sup y \in [0, 1] in f K (x, y) = y \in [0, 1] in f x \in [0, 1] sup K (x, y)$
が成り立つ。この共通の値（ゲームの値）を求めよ。
難易度 4（大学院入試の標準レベル）
区別のできる $9$ 人のプレイヤー $1, 2, \dots, 9$ が、ある共同プロジェクトに「出資する」か「出資しない」かを同時に 1 回だけ選ぶ（クラウドファンディングのような、返金保証のある閾値型の公共財ゲーム）。出資した人数を $k$ とする。
- $k \geq 4$ のときプロジェクトは成立し、全員（出資しなかったプレイヤーも含む）が便益 $10$ を受け取る。このとき出資したプレイヤー $i$ は費用 $c_{i}$ を支払う。
- $k \leq 3$ のときプロジェクトは不成立で、出資金は全額返金される。このとき全員の利得は $0$ である。
すなわちプレイヤー $i$ の利得は、成立したとき出資していれば $10 - c_{i}$ 、出資していなければ $10$ 、不成立のときは出資の有無によらず $0$ である。費用は
$c_{1} = c_{2} = c_{3} = c_{4} = c_{5} = 3, c_{6} = c_{7} = c_{8} = c_{9} = 12$
とする。
この $9$ 人の戦略形ゲームにおいて、純粋戦略のナッシュ均衡（ $2^{9}$ 通りの戦略の組のうち、どのプレイヤーも 1 人だけ戦略を変えて利得を真に増やすことができないもの）の個数を求めよ。
難易度 4（大学院入試の標準レベル）
$n$ を $2$ 以上の整数とし、プレイヤーの集合を $N = {1, 2, \dots, n}$ とする。関数 $f : {0, 1, \dots, n} \to R$ は $f (0) = 0$ をみたすとし、提携 $S \subseteq N$ の値を $v (S) = f (∣ S ∣)$ で定める特性関数形ゲーム $(N, v)$ を考える（ $∣ S ∣$ は $S$ の要素の個数）。
ベクトル $x = (x_{1}, \dots, x_{n}) \in R^{n}$ と $S \subseteq N$ に対し $x (S) = \sum_{i \in S} x_{i}$ （ $x (\emptyset) = 0$ ）とおく。 $(N, v)$ のコアを
$C (v) = {x \in R^{n} ∣ x (N) = v (N), and x (S) \geq v (S) for all S \subseteq N}$
と定め、シャープレイ値 $φ (v) = (φ_{1}, \dots, φ_{n})$ を
$φ_{i} = S \subseteq N ∖ {i} \sum \frac{∣ S ∣ ! ( n - ∣ S ∣ - 1 )!}{n !} (v (S \cup {i}) - v (S)) (i \in N)$
で定める。
このとき、コア $C (v)$ が空でないことと、シャープレイ値 $φ (v)$ が $C (v)$ に属することは同値であることを証明せよ。
難易度 4（大学院入試の標準レベル）
$n$ を $2$ 以上の整数とし、 $A$ を $(i, j)$ 成分が $∣ i - j ∣$ （ $i, j = 1, \dots, n$ ）の $n$ 次正方行列とする。プレイヤー 1 が行 $i$ 、プレイヤー 2 が列 $j$ を選んだとき、プレイヤー 2 がプレイヤー 1 に $A$ の $(i, j)$ 成分 $∣ i - j ∣$ を支払う 2 人ゼロ和ゲームを考える（直線上の地点 $1, \dots, n$ のどれかを互いに選び、離れているほどプレイヤー 1 が得をするゲームである）。
混合戦略の集合を $Δ = {x \in R^{n} ∣ x_{k} \geq 0 (k = 1, \dots, n), x_{1} + \dots + x_{n} = 1}$ とし、プレイヤー 1 が $x \in Δ$ 、プレイヤー 2 が $y \in Δ$ を独立に用いるときのプレイヤー 1 の期待利得を $x^{⊤} A y$ とする。
$v = x \in Δ max y \in Δ min x^{⊤} A y, v = y \in Δ min x \in Δ max x^{⊤} A y$
とおき（これらの最大値・最小値が存在することは用いてよい）、 $v = v$ のときこの共通の値をゲームの値という。また、 $min_{y \in Δ} x^{⊤} A y = v$ をみたす $x \in Δ$ をプレイヤー 1 の最適戦略、 $max_{x \in Δ} x^{⊤} A y = v$ をみたす $y \in Δ$ をプレイヤー 2 の最適戦略という。
次の 3 つがすべて成り立つことを証明せよ。
- このゲームの値が存在して $\frac{n - 1}{2}$ に等しい。
- プレイヤー 1 の最適戦略は、 $x_{1} = x_{n} = \frac{1}{2}$ 、それ以外の成分が $0$ である $x$ ただ 1 つである。
- $y \in Δ$ がプレイヤー 2 の最適戦略であるための必要十分条件は $j = 1 \sum n j y_{j} = \frac{n + 1}{2}$ である。
難易度 4（大学院入試の標準レベル）
ある商品の市場に既存企業 $1$ と参入を検討している企業 $2$ がいる。次の $3$ 段階の展開形ゲームを考える。各段階で、それまでの行動はすべて両企業に観察される。
1. 企業 $1$ が費用削減のための投資水準 $x (0 \leq x \leq 4)$ を選ぶ。投資費用は $2 x^{2}$ で、投資後の企業 $1$ の限界費用（一定）は $4 - x$ になる。
2. 企業 $2$ は $x$ を観察したうえで、参入するかしないかを選ぶ。参入するときは固定費用 $\frac{9}{4}$ がかかり、限界費用（一定）は $4$ である。参入しないときの企業 $2$ の利得は $0$ である。
3. 企業 $2$ が参入した場合、両企業は生産量 $q_{1} \geq 0, q_{2} \geq 0$ を同時に選ぶ（クールノー競争）。参入しなかった場合、企業 $1$ が単独で生産量 $q_{1} \geq 0$ を選ぶ。
総生産量を $Q$ とすると価格は $p = max {12 - Q, 0}$ である。企業 $1$ の利得は $p q_{1} - (4 - x) q_{1} - 2 x^{2}$ 、参入した企業 $2$ の利得は $p q_{2} - 4 q_{2} - \frac{9}{4}$ とする。また、企業 $2$ は参入した場合の利得が $0$ より真に大きいときに限り参入する（利得が $0$ のときは参入しない）。
このゲームの部分ゲーム完全均衡において、企業 $1$ が選ぶ投資水準 $x$ と、均衡における企業 $1$ の利得を、この順に組 $(x, 企業 1 の利得)$ で求めよ。

	キーパー $L$	キーパー $R$
キッカー $L$	$(1, 4)$	$(4, 1)$
キッカー $R$	$(3, 2)$	$(2, 3)$

	$L$	$C$	$R$
$T$	$(3, 0)$	$(0, 6)$	$(2, 3)$
$M$	$(1, 5)$	$(1, 1)$	$(1, 0)$
$B$	$(0, 4)$	$(3, 0)$	$(1, 3)$

	$y_{1}$	$y_{2}$	$y_{3}$
$x_{1}$	$3$	$- 1$	$2$
$x_{2}$	$4$	$2$	$5$
$x_{3}$	$- 2$	$1$	$6$

	$a$	$b$	$c$
$I$	$4$	$1$	$2$
$II$	$0$	$3$	$1$

	$C_{1}$	$C_{2}$
$R_{1}$	$3$	$- 1$
$R_{2}$	$- 2$	$4$
$R_{3}$	$1$	$0$