ゼロ和ゲームの値（鞍点と混合戦略）

利得行列のマックスミニ値とミニマックス値を求め、一致すれば鞍点としてゲームの値を求められる。一致しない $2 \times n$ や $m \times 2$ のゲームでは、混合確率 $p$ に対する期待利得の直線の下側（上側）の包絡線を最大化（最小化）する。こうしてゲームの値 $max_{p} min_{j}$ と最適混合戦略を求められる

前提

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

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

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

説明

2 人ゼロ和ゲームで、利得行列の成分を行プレイヤー（プレイヤー 1）の利得とし、列プレイヤー（プレイヤー 2）の利得をその符号を変えたものとします。この技能を使うと、両者が最善を尽くしたときの行プレイヤーの期待利得（ゲームの値） $v$ と、それを実現する最適な戦略を求められます。まず鞍点があるかを調べ、あればそれが答えです。なければ $2 \times n$ や $m \times 2$ のゲームで混合戦略の期待利得を直線として描き、その包絡線から値を読み取ります。

なぜそうしてよいのか

行プレイヤーは利得を大きく、列プレイヤーは小さくしたいと考えます。行 $i$ を選んだ行プレイヤーが最悪の場合でも得られるのは、行の最小値 $min_{j} a_{ij}$ です。そこで行プレイヤーが純粋戦略で保証できる最大の利得は、マックスミニ値 $max_{i} min_{j} a_{ij}$ です。同じように、列プレイヤーが純粋戦略で抑えられる上限はミニマックス値 $min_{j} max_{i} a_{ij}$ です。前者は後者を超えません。両者が一致すると、その成分 $a_{i^{*} j^{*}}$ は「その列の中で最大」かつ「その行の中で最小」になります。これを鞍点といいます。 $(i^{*}, j^{*})$ はどちらのプレイヤーも一方的に変えたくない組、つまり純粋戦略ナッシュ均衡で、ゲームの値は $v = a_{i^{*} j^{*}}$ です。

一致しないときは混合戦略を考えます。 $2 \times n$ のゲームで、行プレイヤーが行 1 を確率 $p$ 、行 2 を確率 $1 - p$ で選ぶとします。列 $j$ に対する期待利得は $E_{j} (p) = a_{1 j} p + a_{2 j} (1 - p)$ で、 $p$ の 1 次式（直線）です。 $p$ を決めたとき、列プレイヤーがどんな混合をしても、期待利得は $E_{j} (p)$ たちを確率で重み付けした平均になります。平均は最小のものを下回りません。よって列プレイヤーにとって最善の応答は、純粋戦略のどれかで足ります。行プレイヤーが保証できるのは $f (p) = min_{j} E_{j} (p)$ 、すなわち直線たちの下側の包絡線です。行プレイヤーはこれを最大にする $p$ を選びます。

フォン・ノイマンのミニマックス定理により、混合戦略まで許すと $max_{p} min_{j} E_{j} (p)$ は列プレイヤー側の $min_{q} max_{i} (\dots)$ と必ず一致します。この共通の値がゲームの値 $v$ です。 $f$ は折れ線で、山形（上に凸）になります。そのため最大は端点か、直線どうしの交点で起こります。 $m \times 2$ のゲームでは役割を入れ替え、列プレイヤーの確率 $q$ について上側の包絡線を最小にします。

手順

鞍点を調べる：各行の最小値の最大（マックスミニ値）と、各列の最大値の最小（ミニマックス値）を求める。一致すれば、それがゲームの値 $v$ で、対応する純粋戦略が最適である（ここで終了）。
一致しなければ混合戦略を考える。 $2 \times n$ なら行 1 の確率を $p (0 \leq p \leq 1)$ とし、各列の期待利得の直線 $E_{j} (p) = a_{1 j} p + a_{2 j} (1 - p)$ を書く。
下側の包絡線 $f (p) = min_{j} E_{j} (p)$ を調べる。直線どうしの交点と端点 $p = 0, 1$ を候補とし、各候補で全部の直線の値を比べて、本当に包絡線上にある点を選ぶ。
$f (p)$ が最大になる $p^{*}$ と最大値 $v = f (p^{*})$ を求める。これが行プレイヤーの最適混合戦略とゲームの値である。
頂点で交わる 2 本の直線の列だけを列プレイヤーが使う（他の列は確率 0）。その 2 列について無差別の原理で列プレイヤーの確率 $q$ を求め、同じ値 $v$ が出ることを確かめる。
$m \times 2$ のゲームでは逆に、列 1 の確率を $q$ として各行の直線 $F_{i} (q)$ を書く。上側の包絡線 $max_{i} F_{i} (q)$ を最小にする $q$ と、その最小値 $v$ を求める。

例題

行プレイヤーの利得行列が $A = (3 - 1 0421)$ である 2 人ゼロ和ゲームを考える（列プレイヤーの利得は符号を変えたもの）。ゲームの値 $v$ と、行プレイヤーが行 1 を選ぶ最適な確率 $p$ を、組 $(v, p)$ として求めよ。

例題の解答

【手順 1】行の最小値は、行 1 が $min (3, 0, 2) = 0$ 、行 2 が $min (- 1, 4, 1) = - 1$ なので、マックスミニ値は $0$ である。列の最大値は $3, 4, 2$ なので、ミニマックス値は $2$ である。 $0 \neq = 2$ だから鞍点はなく、混合戦略を考える。

【手順 2】行 1 を確率 $p$ で選ぶとき、各列に対する期待利得は次のとおり。
$E_{1} (p) = 3 p - (1 - p) = 4 p - 1$
$E_{2} (p) = 0 \cdot p + 4 (1 - p) = 4 - 4 p$
$E_{3} (p) = 2 p + (1 - p) = 1 + p$

【手順 3】交点を調べる。
・ $E_{1} = E_{2}$ のとき $p = \frac{5}{8}$ で値は $\frac{3}{2}$ 。このとき $E_{3} (\frac{5}{8}) = \frac{13}{8} > \frac{3}{2}$ なので、この点は包絡線上にある。
・ $E_{1} = E_{3}$ のとき $p = \frac{2}{3}$ で値は $\frac{5}{3}$ 。しかし $E_{2} (\frac{2}{3}) = \frac{4}{3}$ の方が小さいので、包絡線上にない。
・ $E_{2} = E_{3}$ のとき $p = \frac{3}{5}$ で値は $\frac{8}{5}$ 。しかし $E_{1} (\frac{3}{5}) = \frac{7}{5}$ の方が小さいので、包絡線上にない。
したがって $f (p)$ は、 $0 \leq p \leq \frac{5}{8}$ で $4 p - 1$ （増加）、 $\frac{5}{8} \leq p \leq 1$ で $4 - 4 p$ （減少）となる。端点では $f (0) = - 1$ 、 $f (1) = 0$ である。

【手順 4】 $f$ は $p = \frac{5}{8}$ で最大になり、 $v = f (\frac{5}{8}) = \frac{3}{2}$ である。

【手順 5】確認する。列プレイヤーは頂点で交わる列 1 と列 2 だけを使い、列 1 を確率 $q$ 、列 2 を確率 $1 - q$ で選ぶとする。行 1 の期待利得は $3 q$ 、行 2 の期待利得は $- q + 4 (1 - q) = 4 - 5 q$ である。無差別の条件 $3 q = 4 - 5 q$ から $q = \frac{1}{2}$ となり、どちらの行でも期待利得は $\frac{3}{2}$ になる。列プレイヤーも行プレイヤーの期待利得を $\frac{3}{2}$ に抑えられるので、値は $v = \frac{3}{2}$ で一致する。

答えは $(v, p) = (\frac{3}{2}, \frac{5}{8})$ 。

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

よくある誤り

鞍点を確かめずに、いきなり無差別の原理を使ってしまう誤り。例えば $(2134)$ で $2 p + (1 - p) = 3 p + 4 (1 - p)$ を解くと $p = \frac{3}{2}$ となり、確率として不適切である。正しくは、マックスミニ値 $max (2, 1) = 2$ とミニマックス値 $min (2, 4) = 2$ が一致するので、鞍点 $(1, 1)$ があり、 $v = 2$ である。
任意の 2 本の直線の交点を最大点としてしまう誤り。上の例題で $E_{1} = E_{3}$ の交点 $p = \frac{2}{3}$ から $v = \frac{5}{3}$ とするのは誤りである。その点では $E_{2} (\frac{2}{3}) = \frac{4}{3}$ の方が小さい。正しくは、各候補ですべての直線の値を比べ、下側の包絡線 $min_{j} E_{j} (p)$ の上にある点だけを比べる（例題では $v = \frac{3}{2}$ ）。
行プレイヤーについて上側の包絡線 $max_{j} E_{j} (p)$ の最小を求めてしまう誤り。列プレイヤーは行プレイヤーの利得を小さくするので、行プレイヤーに保証されるのは $min_{j} E_{j} (p)$ である。正しくは、行プレイヤー（ $2 \times n$ ）では下側の包絡線の最大、列プレイヤー（ $m \times 2$ ）では上側の包絡線の最小を求める。
マックスミニ値を「各行の最大値の最大」などと取り違える誤り。正しくは、マックスミニ値が $max_{i} min_{j} a_{ij}$ （行ごとの最小値の最大）、ミニマックス値が $min_{j} max_{i} a_{ij}$ （列ごとの最大値の最小）で、常に前者 $\leq$ 後者となる。

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

	$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$

ゼロ和ゲームの値（鞍点と混合戦略）

前提

説明

なぜそうしてよいのか

手順

例題

よくある誤り

入口の問題

この技能を使う問題