ゲーム理論(game theory)とは、複数の参加者の利得が全員の選択で決まる状況を数学のモデルにして、合理的な選択とその結果を調べる分野である。中心の概念である Nash 均衡は、誰も 1 人だけ戦略を変えて得をしない状態で、有限ゲームには混合戦略の均衡が必ずある。2 人ゼロ和ゲームでは最大最小と最小最大が一致する。均衡は全員にとっての最善とは限らず、囚人のジレンマがその例である。
前提知識: 線形計画法, 期待値, Brouwerの不動点定理
ゲーム理論(game theory)は、複数の参加者の利得が全員の選択によって決まる状況を数学のモデルにして、合理的な選択と結果の性質を調べる分野である。von Neumann が 1928 年の論文で 2 人ゼロ和ゲームの最小最大定理を示し、von Neumann と Morgenstern の本がその基礎を固めた(KP17 Chapter 2 の注)。
中心の問いは 3 つある。各参加者が自分の利得だけを考えるとき、どんな状態が安定か。その状態は全員にとってよいのか。望ましい結果を生むように規則を設計できるか。この記事は、それぞれの問いに入る記事と文献への地図である。
有限の戦略形ゲーム は、参加者の集合 $\{1,\dots,k\}$、各参加者 $i$ の有限な純粋戦略の集合 $S_i$、利得関数 $u_i\colon S_1\times\dots\times S_k\to\mathbb{R}$ からなる。$S_i$ 上の確率分布を 混合戦略 といい、$\sigma=(\sigma_1,\dots,\sigma_k)$ の利得は、各参加者が独立に $\sigma_i$ に従って戦略を選ぶときの $u_i$ の期待値 $U_i(\sigma)$ とする。
すべての $i$ と $i$ のすべての混合戦略 $\tau_i$ について $U_i(\tau_i,\sigma_{-i})\le U_i(\sigma)$ となるとき、$\sigma$ を Nash 均衡 という。ここで $\sigma_{-i}$ は $i$ 以外の戦略の組である。
Nash均衡 とは、ほかの参加者の戦略が変わらないかぎり、誰も 1 人だけ戦略を変えて得をしない状態である。
$k=2$ で $u_1+u_2=0$ のゲームを 2 人ゼロ和ゲーム という。参加者 1 の利得を行列 $A$ で表すと、最小最大定理により
$$
\max_x\min_yx^{\mathsf T}Ay=\min_y\max_xx^{\mathsf T}Ay
$$
が成り立つ($x,y$ は混合戦略)。この共通の値をゲームの 値 という。
定理の番号は KP17 のもので、記事のないものはこの記事では証明しない。
| 問い | 代表的な結果 | 入る記事・所在 |
|---|---|---|
| ゼロ和ゲームの解は何か | 混合戦略を許すと最大最小と最小最大が一致する(von Neumann) | 線形計画法, 角谷の不動点定理 |
| 一般のゲームに均衡はあるか | 有限ゲームには混合戦略の Nash 均衡がある(Nash) | Nash均衡, 角谷の不動点定理, Brouwerの不動点定理 |
| 手番が順に回るゲームでは | 完全情報の有限展開形ゲームには、後ろ向き帰納法で求まる部分ゲーム完全な純粋 Nash 均衡がある | KP17 Theorem 6.1.7 |
| 交互に打つ 2 人の勝敗ゲームでは | 不偏ゲームは Nim の山と同値である(Sprague–Grundy) | 組合せゲーム理論, Nim |
| 無限の手順のゲームでは | 集合の正則性と戦略の存在が結びつく | 決定性公理, Banach–Mazurゲーム |
| 論理の同値はゲームで測れるか | 有限の言語の構造の初等同値がゲームの必勝戦略で特徴づけられる | Ehrenfeucht–Fraïsséゲーム |
| 繰り返すと協調は実現するか | 無限回の繰り返しの平均利得では、実現可能で個人合理的な利得の組が均衡で実現する(Folk 定理) | KP17 Theorem 6.4.10 |
| 2 つの側を組み合わせる安定な方法は | 男女の数が等しければ、受け入れ保留方式で安定マッチングが得られる(Gale–Shapley) | thm-gt-gale-shapley |
| 協力の利益をどう分けるか | 4 つの公理を満たす配分は Shapley値に限る | KP17 Theorem 12.3.5 |
| 公平な順位の集計は可能か | 候補が 3 つ以上のとき、全員一致性と無関係な選択肢からの独立性をもつ順位の決め方は独裁に限る(Arrow) | KP17 Theorem 13.3.1 |
| 正直な申告を引き出せるか | 第 2 価格の競売では、真の評価額を入札することが最適である。結果が有限個で効用が準線形な一般の選択の問題でも、VCG メカニズムでは真の評価を申告することが支配戦略になる | メカニズムデザイン、KP17 Theorem 14.2.3 |
ゲーム理論の結果は、モデルの違いによって次のように分けて見るとよい。
非協力ゲームは、各参加者が独立に戦略を選ぶモデルである。2 人ゼロ和の場合には均衡の値が 1 つに決まり、線形計画法 の双対定理から導ける。一般の和の場合には均衡が複数ありうるので、均衡の存在は言えても、どの均衡が実現するかは別の問題である。
展開形ゲームは、手番の順序と各時点の情報をモデルに含める。完全情報なら、終わりから逆にたどって最適な手を決められる。チェスのような有限のゲームの必勝法の議論もこの形である。
協力ゲームは、参加者の集団が得る価値を与え、その分け方を公理で定める。
制度の設計は、問いを逆にする。ゲームが与えられて均衡を調べるのでなく、望ましい結果が均衡になるように規則を作る。安定マッチング、投票、競売がこれにあたる。Arrowの不可能性定理は、順位の集計にはこの設計の限界があることを示す。
$A=\begin{pmatrix}2&-1\\-1&1\end{pmatrix}$ を参加者 1(行を選ぶ)の利得とする。純粋戦略だけなら、行の最小値の最大は $-1$、列の最大値の最小は $1$ で一致しない。
参加者 1 が確率 $x$ で第 1 行を選ぶと、第 1 列に対する利得は $2x-(1-x)=3x-1$、第 2 列に対する利得は $-x+(1-x)=1-2x$ である。両者が等しいのは $x=\frac25$ のときで、値は $\frac15$ である。$A$ は対称なので、参加者 2 も確率 $\frac25$ で第 1 列を選べば、参加者 1 の利得はどの行でも $\frac15$ になる。よって参加者 1 は $\frac15$ 以上を確保でき、参加者 2 は $\frac15$ 以下に抑えられるので、ゲームの値は $\frac15$ である。
この計算の「相手の利得を等しくする」という手順には理由がある。Nash 均衡で参加者が正の確率を置く純粋戦略は、どれも同じ利得を与える。もし利得の小さい純粋戦略に正の確率があれば、その確率を利得の大きい純粋戦略に移すことで、全体の利得が増えるからである。
2 人がそれぞれ協調 C か裏切り D を選び、利得の組が次の表で与えられるとする(左が行の参加者、右が列の参加者)。
| C | D | |
|---|---|---|
| C | $(3,3)$ | $(0,5)$ |
| D | $(5,0)$ | $(1,1)$ |
相手の選択によらず D の利得の方が大きい($5>3$、$1>0$)。よって混合戦略で C に正の確率を置くと利得が真に減り、Nash 均衡は $(\mathrm{D},\mathrm{D})$ だけである。その利得 $(1,1)$ は、$(\mathrm{C},\mathrm{C})$ の $(3,3)$ より両者にとって小さい。Nash 均衡は安定性の条件であり、全員にとっての最善を意味しない。
$n$ 人の男性と $n$ 人の女性がいて、各人が異性全員に狭義の順位を付けているとする。全員を 1 対 1 に組にしたものを マッチング といい、組になっていない男女で、互いに今の相手より相手を好む組があるとき、そのマッチングは 不安定 という。不安定でないものを 安定 という。
受け入れ保留方式 は次の手順である。各回で、どの女性にも保留されていない各男性が、まだ断られていない女性のうち最も好む人に申し込む。各女性は、申し込みと保留中の相手のうち最も好む 1 人を保留し、残りを断る。誰も断られなくなったら、保留の組を確定する。
受け入れ保留方式は有限回で止まり、結果は安定マッチングである。とくに安定マッチングは必ず存在する。
1 回の断りごとに、ある男性の「まだ断られていない女性」が 1 人減る。断りの総数は $n^2$ 以下なので、手順は有限回で止まる。
一度申し込まれた女性は、以後つねに誰かを保留し、その相手は順位の上で下がらない。手順が止まったとき保留されていない男性がいるとすると、その男性はすべての女性に断られている。すると $n$ 人の女性全員が申し込まれたので全員が誰かを保留しており、$n$ 人の男性全員が保留されていることになって矛盾する。よって、止まったとき全員が組になっている。
安定性を示す。男性 $m$ と女性 $w$ が組でなく、$m$ が結果の相手より $w$ を好むとする。$m$ は好む順に申し込むので $w$ に申し込み、断られている。そのとき $w$ は $m$ より好む人を保留しており、その後の保留はさらに下がらない。よって $w$ は結果の相手を $m$ より好むので、$(m,w)$ は互いに好む組ではない。$\square$
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 混合戦略を許すこと | 角谷の不動点定理 でも扱うコイン合わせ | 純粋戦略だけでは Nash 均衡がない |
| 戦略の集合が有限であること | 1 人のゲームで $S=\{1,2,\dots\}$、$u(n)=1-\frac1n$ | どの混合戦略の利得も $1$ より小さく、$n$ を十分大きくとった純粋戦略の方が利得が大きい。Nash 均衡がない |
| 2 つの側に分かれていること | 4 人 $a,b,c,d$ の組分けで、$a$ は $b,c,d$ の順、$b$ は $c,a,d$ の順、$c$ は $a,b,d$ の順に好み、$d$ の順位は任意 | どの組分けでも $d$ の相手を含む不安定な組がある。安定な組分けがない |
3 行目を確かめる。$d$ の相手が $a$ なら $b,c$ が組で、$c$ は $b$ より $a$ を好み、$a$ は $d$ より $c$ を好むので $(a,c)$ が不安定な組である。$d$ の相手が $b$ なら $a,c$ が組で、$(a,b)$ が不安定な組である($a$ は $c$ より $b$ を、$b$ は $d$ より $a$ を好む)。$d$ の相手が $c$ なら $a,b$ が組で、$(b,c)$ が不安定な組である($b$ は $a$ より $c$ を、$c$ は $d$ より $b$ を好む)。
| 段階 | 読むもの | 得られること |
|---|---|---|
| 1. ゼロ和ゲーム | 線形計画法 の最小最大定理の節 | 双対定理と値 |
| 2. 均衡の存在 | Brouwerの不動点定理, 角谷の不動点定理 | Nash 均衡の存在 |
| 3. 交互に打つゲーム | Nim, 組合せゲーム理論 | Grundy 数 |
| 4. 組合せの最適化 | マッチング、この記事の thm-gt-gale-shapley | 安定性 |
| 5. 無限のゲーム | Banach–Mazurゲーム, 決定性公理 | 集合論との関係 |
Nash 均衡の存在定理は不動点定理による証明で、均衡を効率よく求める方法を与えない。2 人の有限ゲームの Nash 均衡を求める問題は計算量のクラス PPAD で完全である(CDT09)。したがって、PPAD のすべての問題が多項式時間で解けるのでないかぎり、この問題を解く多項式時間の算法はない。PPAD のすべての問題が多項式時間で解けるかどうかは、CDT09 の時点で未解決である。
Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する