ゲーム理論

同義語:game theory

概要

ゲーム理論(game theory)とは、複数の参加者の利得が全員の選択で決まる状況を数学のモデルにして、合理的な選択とその結果を調べる分野である。中心の概念である Nash 均衡は、誰も 1 人だけ戦略を変えて得をしない状態で、有限ゲームには混合戦略の均衡が必ずある。2 人ゼロ和ゲームでは最大最小と最小最大が一致する。均衡は全員にとっての最善とは限らず、囚人のジレンマがその例である。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{div}[0]{\mathbin{÷}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: 線形計画法, 期待値, Brouwerの不動点定理

ゲーム理論(game theory)は、複数の参加者の利得が全員の選択によって決まる状況を数学のモデルにして、合理的な選択と結果の性質を調べる分野である。von Neumann が 1928 年の論文で 2 人ゼロ和ゲームの最小最大定理を示し、von Neumann と Morgenstern の本がその基礎を固めた(KP17 Chapter 2 の注)。
中心の問いは 3 つある。各参加者が自分の利得だけを考えるとき、どんな状態が安定か。その状態は全員にとってよいのか。望ましい結果を生むように規則を設計できるか。この記事は、それぞれの問いに入る記事と文献への地図である。

定義

戦略形ゲームと Nash 均衡

有限の戦略形ゲーム は、参加者の集合 $\{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の不可能性定理は、順位の集計にはこの設計の限界があることを示す。

具体例

行列ゲームを解く

純粋戦略の鞍点がない $2\times2$ ゲーム

$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 を選び、利得の組が次の表で与えられるとする(左が行の参加者、右が列の参加者)。

CD
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 人を保留し、残りを断る。誰も断られなくなったら、保留の組を確定する。

Gale–Shapley の定理

受け入れ保留方式は有限回で止まり、結果は安定マッチングである。とくに安定マッチングは必ず存在する。

女性の保留は良くなる一方である

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 の時点で未解決である。

関連項目

参考文献

[1]
Anna R. Karlin, Yuval Peres, Game Theory, Alive, American Mathematical Society, 2017, 著者公開版(2016 年 12 月 13 日)の番号:Theorem 2.3.1, Theorem 4.3.6, Theorem 6.1.7, Theorem 6.4.10, Theorem 10.2.3, Theorem 12.3.5, Theorem 13.3.1, Theorem 14.2.3
[2]
Xi Chen, Xiaotie Deng, Shang-Hua Teng, Settling the complexity of computing two-player Nash equilibria, Journal of the ACM 56 (2009), no. 3, Article 14; arXiv:0704.1678, 2009

Mathpediaは寄付と、参考文献の書籍リンク(Amazonアソシエイト)の紹介料で運営されています。 支援について / 寄付する