支配戦略の消去と支持の絞り込みによる混合均衡

$3 \times 3$ などの双行列ゲームで、次の手順で混合戦略ナッシュ均衡と期待利得を求められる。まず、強く支配される戦略（混合戦略に支配されるものを含む）を順に消去する。次に、均衡で正の確率を置く戦略（支持）の組を場合分けし、無差別条件と逸脱しない条件を確かめる

前提

混合戦略ナッシュ均衡（無差別の原理）（大学数学ゲーム理論）

この技能までの道筋（9 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

最適反応と純粋戦略ナッシュ均衡（大学数学ゲーム理論）
樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
順列・円順列・重複順列（数学A 場合の数と確率）
組合せ（数学A 場合の数と確率）
確率の定義と和事象・余事象（数学A 場合の数と確率）
期待値（数学A 場合の数と確率）
混合戦略ナッシュ均衡（無差別の原理）（大学数学ゲーム理論）

説明

$3 \times 3$ のように戦略が 3 つ以上ある双行列ゲームで、混合戦略ナッシュ均衡とそのときの期待利得を求める方法を学びます。 $2 \times 2$ の無差別の原理は、そのままでは使えません。そこで 2 段階で考えます。まず、合理的なプレイヤーが決して選ばない戦略（強く支配される戦略）を順に消してゲームを小さくします。次に、残ったゲームで「均衡で正の確率を置く戦略の組（支持）」を場合分けし、無差別条件と逸脱しない条件を確かめて均衡を確定させます。

なぜそうしてよいのか

混合戦略を使うときの期待利得は、純粋戦略の期待利得を確率で重み付けした平均です。平均は最大値を超えないので、ある混合戦略が最適反応になるのは、正の確率を置いた純粋戦略（これを支持と呼びます）がすべて最大の期待利得をとるときに限ります。支持の中に利得の小さい戦略があれば、その確率を利得の大きい戦略に移すだけで得をするからです。したがって均衡では、(i) 支持に入る戦略どうしは期待利得が等しく（無差別条件）、(ii) 支持に入らない戦略の期待利得はそれ以下（逸脱しない条件）です。逆に、両プレイヤーについて (i)(ii) が成り立てば、その組はナッシュ均衡です。

プレイヤーの戦略 $s$ が、自分の別の混合戦略 $σ$ （純粋戦略でもよい）に強く支配されるとは、相手のどの純粋戦略に対しても $σ$ の利得が $s$ の利得より真に大きいことをいいます。不等式は重み付き平均をとっても保たれるので、相手がどんな混合戦略を使っても $σ$ の期待利得は $s$ より真に大きくなります。つまり $s$ は決して最適反応にならず、どの均衡でも確率 $0$ です。だから $s$ を消しても均衡は 1 つも失われません。

さらに相手も「 $s$ は使われない」とわかるので、残った小さい表だけで考えてよくなります。すると、それまで支配されていなかった戦略が新たに支配されることがあります。これを消せなくなるまで繰り返すのが「順に消去する」ということです。純粋戦略どうしでは比べても支配関係がなくても、2 つの戦略を混ぜると支配できる場合がある点が大切です。

手順

支配を調べる：各プレイヤーについて、まず純粋戦略どうしを比べる。次に 2 つの戦略 $a, b$ の混合 $λa + (1 - λ) b$ （ $0 < λ < 1$ ）が戦略 $c$ を強く支配するかを調べる。相手の各列（各行）で $λ u (a) + (1 - λ) u (b) > u (c)$ となる $λ$ が存在するかを、不等式を解いて確かめる。
消去を繰り返す：強く支配される戦略を表から消し、小さくなった表でもう一度手順 1 を行う。どちらのプレイヤーにも消せる戦略がなくなるまで続ける。
支持の候補を場合分けする：残った表で、まず純粋戦略の組（互いに最適反応か）を調べる。次に「一方が純粋で他方が混合」「両方が混合」の組を調べる。相手の純粋戦略に対して最適反応がただ 1 つなら、自分がその相手に対して混ぜることはできないので、その場合は除外できる。
無差別条件を解く：候補の支持について、相手の確率を未知数とし、自分の支持内の戦略の期待利得が等しいという式を立てて解く。例えば $3 q = 3 (1 - q)$ のように解く。得られた確率がすべて $0$ より大きく、和が $1$ であることを確認する。
逸脱しない条件を確かめる：支持の外にある戦略（消去した戦略も含め、元の表で）の期待利得が、均衡の期待利得以下であることを確認する。
期待利得を計算する：均衡の確率で、各プレイヤーの期待利得を求める。

例題

次の双行列ゲームを考える。プレイヤー1は行 $U, M, D$ を、プレイヤー2は列 $L, C, R$ を選ぶ。各成分は（プレイヤー1の利得, プレイヤー2の利得）である。 $U M D L (3, 1) (0, 2) (1, 2) C (0, 2) (3, 0) (1, 1) R (0, 0) (0, 1) (4, 1)$ このゲームのナッシュ均衡（混合戦略を含む）はただ 1 つである。その均衡におけるプレイヤー1とプレイヤー2の期待利得を、順に組で求めよ。

例題の解答

【手順1】プレイヤー2の $R$ と $L$ を比べる。行 $U, M, D$ でそれぞれ $0 < 1$ , $1 < 2$ , $1 < 2$ なので、 $R$ は $L$ に強く支配される。一方、元の表ではプレイヤー1の $D$ は列 $R$ で $4$ を得て $U, M$ の $0$ より大きいので、まだ支配されない。

【手順2】 $R$ を消すと、プレイヤー1の利得は列 $L, C$ に対して $U : (3, 0)$ , $M : (0, 3)$ , $D : (1, 1)$ となる。
- $U$ は列 $C$ で $0 < 1$ なので $D$ を支配しない。 $M$ も列 $L$ で $0 < 1$ なので支配しない。
- 混合 $λ U + (1 - λ) M$ の利得は $(3 λ, 3 - 3 λ)$ である。これが $(1, 1)$ より真に大きいのは $\frac{1}{3} < λ < \frac{2}{3}$ のときで、例えば $λ = \frac{1}{2}$ なら $(\frac{3}{2}, \frac{3}{2})$ となる。よって $D$ は混合戦略に強く支配されるので消す。
- 残った $2 \times 2$ では、プレイヤー2の $L$ は $(1, 2)$ 、 $C$ は $(2, 0)$ で、支配関係はない。プレイヤー1の $U : (3, 0)$ , $M : (0, 3)$ にも支配関係はない。ここで消去を終える。

【手順3】最適反応を調べる。
- プレイヤー1： $L$ に対しては $U$ だけ、 $C$ に対しては $M$ だけが最適反応。
- プレイヤー2： $U$ に対しては $C$ だけ、 $M$ に対しては $L$ だけが最適反応。
互いに最適反応となる純粋戦略の組はない。また、相手の純粋戦略に対する最適反応がどれもただ 1 つなので、「一方が純粋で他方が混合」も起こらない。よって支持は両者とも 2 つの戦略すべてである。

【手順4】プレイヤー2が $L$ を確率 $q$ 、 $C$ を確率 $1 - q$ で選ぶとする。プレイヤー1の無差別条件は $3 q = 3 (1 - q)$ で、 $q = \frac{1}{2}$ 。プレイヤー1が $U$ を確率 $p$ 、 $M$ を確率 $1 - p$ で選ぶとする。プレイヤー2の無差別条件は、 $L$ の期待利得 $p + 2 (1 - p) = 2 - p$ と $C$ の期待利得 $2 p$ が等しいことで、 $p = \frac{2}{3}$ 。どちらも $0$ と $1$ の間にある。

【手順5】元の表で逸脱を確かめる。
- プレイヤー1の $D$ ： $1 \cdot \frac{1}{2} + 1 \cdot \frac{1}{2} + 4 \cdot 0 = 1$ 。これは $U, M$ の期待利得 $\frac{3}{2}$ より小さい。
- プレイヤー2の $R$ ： $0 \cdot \frac{2}{3} + 1 \cdot \frac{1}{3} + 1 \cdot 0 = \frac{1}{3}$ 。これは $L, C$ の期待利得 $\frac{4}{3}$ より小さい。
よってこれは均衡である。消去した戦略はどの均衡でも使われず、残った表の均衡はこれだけなので、ただ 1 つの均衡でもある。

【手順6】プレイヤー1の期待利得は $3 q = \frac{3}{2}$ 、プレイヤー2の期待利得は $2 p = \frac{4}{3}$ 。

答え: $(\frac{3}{2}, \frac{4}{3})$

よくある誤り

純粋戦略どうしだけを比べて「支配される戦略はない」としてしまう誤り。例題の $D : (1, 1)$ は $U : (3, 0)$ にも $M : (0, 3)$ にも支配されない。しかし $\frac{1}{2} U + \frac{1}{2} M$ の $(\frac{3}{2}, \frac{3}{2})$ には強く支配される。正しくは、2 つの戦略の混合 $λa + (1 - λ) b$ による支配も不等式で調べる。
無差別条件で、自分の確率を自分の利得から求めてしまう誤り。正しくは、プレイヤー1の確率 $p$ は「プレイヤー2の $L$ と $C$ の期待利得が等しい」という式 $2 - p = 2 p$ から決まる。プレイヤー2の確率 $q$ は、プレイヤー1の式 $3 q = 3 (1 - q)$ から決まる。
等号を含む弱い支配で戦略を消してしまう誤り。例えばプレイヤー1の利得が $T : (1, 0)$ , $B : (1, 1)$ で、プレイヤー2の利得がすべて $0$ のとき、 $(T, L)$ は均衡である。しかし弱く支配される $T$ を消すと、この均衡が失われる。正しくは、すべての列で真に大きい（ $>$ ）ときだけ消す。
無差別条件を解いただけで均衡と決めてしまう誤り。解の確率が $0$ 以下や $1$ 以上になる場合、その支持の組は均衡にならない。また、支持の外の戦略（元の表で消した戦略も含む）の期待利得が均衡の期待利得を超えないことも確かめる。例題では $D$ の $1 \leq \frac{3}{2}$ 、 $R$ の $\frac{1}{3} \leq \frac{4}{3}$ を確認した。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

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

支配戦略の消去と支持の絞り込みによる混合均衡

前提

説明

なぜそうしてよいのか

手順

例題

よくある誤り

入口の問題

この技能を使う問題