【ゲーム理論】第1回 - ナッシュ均衡とパレート最適について解説

はじめに

マルチエージェントインタラクションとゲーム理論(Multi-agent Interaction and Games, MAIG)について学習したので、備忘録も兼ねて同分野の基礎について解説します。一部の専門用語については適切な和訳を知らないため、他の文献と訳出の齟齬があるかもしれませんがあしからず。記事の内容に誤りを発見した際はご指摘ください。

本稿では始めに簡単なゲーム理論の導入を行ったあと、ゲーム理論におけるモデル化とナッシュ均衡、パレート最適について扱います。

次回 ▶ 【ゲーム理論】第2回 - 零和ゲームと混合戦略、相関戦略について解説

ゲーム理論とは

ゲーム理論は、経済学や政治学はもちろん、工学やコンピュータ科学など様々な分野で幅広く活用されている、意思決定の数学的モデルに関する理論です。ノイマンやナッシュといった名前が有名所でしょうか。

ゲーム理論を用いることで、金融市場を始めとした様々な戦略的状況¹を数学的に取り扱うことができます。さらには、軍事衝突の回避やネットワークの協調といった話題にも応用可能です。

ゲームの分類

世の中には数多のゲームがありますが、大きく2つの枠組みで分類することができます。まだゲームとは何たるかをしっかりと述べていませんが、ここではボードゲームやコンピュータゲームといった、一般的な言葉としての「ゲーム」をイメージしていただくと分かりやすいかと思います。

確率ゲーム・確定ゲーム

ゲーム中にさいころのような運の要素が含まれているかどうかで、ゲームを分類することができます。

• 確率ゲーム それぞれのプレイヤーの利得が確率的な変数に依存するゲーム。
• 確定ゲーム それぞれのプレイヤーの利得が決められた変数や、行われた行動のみに依存するゲーム。

完全情報ゲーム・不完全情報ゲーム

ゲーム中においてプレイヤーが保持している情報について考えることでも、ゲームを分類することができます。

• 完全情報ゲーム 現在のゲームの状態と、現在の行動により引き起こされる結果について、すべてのプレイヤーが同等な知識を持っているゲーム。
• 不完全情報ゲーム 現在のゲームの状態と、現在の行動により引き起こされる結果について、プレイヤーが異なる知識を持っているゲーム。

分類の例

具体例で見ていきましょう。代表的なゲームを以上の枠組みに基づいて分類すると、以下のようになります。

チェスや囲碁 は、「現在の盤面」と「打つ手に対して現在の盤面がどのように変化するのか」のいずれについても、双方のプレイヤーが同等の知識を持っています。盤面は互いが指した手のみによって変化していくのでゲームの結果は運に依存せず、これらは確定的な完全情報ゲームです。

モノポリーは盤面や手札の状態こそ共有されていますが、さいころを使っているため明らかに運の要素が含まれます。したがってこれは「確率的な完全情報ゲーム」です。

軍人将棋は馴染みのない方もいるかと思いますが、極めて簡単に言えばコマを伏せた状態で行う将棋のようなものです。運の要素は含まれないものの、それぞれのプレイヤーは相手がどこにコマを配置したのかを知らないため、「確定的な不完全情報ゲーム」となります。

ポーカーは手札を伏せるとともに、どの札を引くかといった運の要素が含まれるため「確率的な不完全情報ゲーム」です。

ここではわかりやすさのためボードゲームを中心に取り上げましたが、例えば「政治」や「恋愛」といったトピックについてもゲーム理論の枠組みで分類することができます。もっとも、現実問題の多くは確率的な不完全情報ゲームになるでしょう。

標準型ゲーム

さて、ここからゲームについて細かく見ていきましょう。

標準形ゲームとは、プレイヤーと行動、効用の3要素から定義されるゲームのことです。数式を用いて表現してみましょう。

まずはゲームに参加するプレイヤーが $n$ 人いるとします。この状況をプレイヤーの集合$P=\{1,\,2,\,\cdots,\,n\}$で表します。

ここでは例として、2人で行うじゃんけんを考えます。2人で行うじゃんけんの場合、$P=\{1,\,2\}$です。

プレイヤーはそれぞれ、実施できる行動の選択肢を持っています。それぞれのプレイヤーが取れる行動の選択肢が全員同じとは限らないため、$i$ 番目のプレイヤーが取れる行動の集合を$A_i$で表しましょう。集合$A_1,\,A_2,\,\cdots\,A_n$の直積$A$で、プレイヤー全員の行動の選択肢を表すことができます。

じゃんけんの場合はどちらのプレイヤーもグー・チョキ・パーのうちから1つを選んで出すことができるため、$A_1=A_2=\{\text{グー},\,\text{チョキ},\,\text{パー}\}$です。

ここで、$A$ や $A_i$ の要素について考えてみましょう。$A_i$ に含まれる要素を $a_i$、$A$ に含まれる要素を $a$ とすると、$a$ は $A_1,\,A_2,\,\cdots\,A_n$ から一つずつ要素を取ってくることでできる行動の組であるため、$a=(a_1,\,a_2,\,\cdots,\,a_n)$ となります。言い換えると、 $A$ の要素 $a$ にはすべてのプレイヤーの行動の情報が含まれているということです。

例えば $a$ の一例として、プレイヤー1がグー、プレイヤー2がパーを出すことを表す $a_1=(\text{グー}, \text{パー})$ などが考えられます。

プレイヤーは、ゲーム内でとった行動に応じて効用を得ることができます。それぞれのプレイヤーにとっての効用は、プレイヤー全員の行動 $a$ によって決定されます。よって $i$ 番目のプレイヤーにとっての効用は $u_i(a)$ と表すことができます。集合 $U=\{u_1,\,u_2,\,\cdots,\,u_n\}$ で全員分の効用を表すことができます。

例えばじゃんけんの効用を、勝利の場合は $1$ 、あいこの場合は $0$ 、敗北の場合は $-1$ と定めましょう。そうすると、例えば $a_1=(\text{グー}, \text{パー})$ に対応するプレイヤー1の効用 $u_1(a_1)$ は、プレイヤー１が負けることから、 $u_1(a_1)=-1$となります。

以上より、標準形ゲームは以下の$P,\,A,\,U$からなるタプル$(P,\,A,\,U)$として表現できます。

$$
\begin{align}
P &= \{1,\,2,\,\cdots,\,n\}\\
A &= A_1\times A_2\times \cdots \times A_n\\
U &= \{u_1,\,u_2,\,\cdots,\,u_n\}
\end{align}
$$

くじと選好関係

ナッシュ均衡やパレート最適の話に入る前に、まずはくじと選好関係について見ていきましょう。ここでは先程の標準形ゲームの話題は一度忘れてください。以下、$O$を起こりうるゲームの結果の集合とします。

くじ

くじとは、結果に対する確率分布です。$0$ 以上 $1$ 以下の実数 $p_1,\,p_2,\,\cdots,\,p_n$ と、ゲームの結果 $o_1,\,o_2,\,\cdots,\,o_n$ を用いて以下のように表されます。
$$
\begin{gather}
[p_1:o_1,\,p_2:o_2,\,\cdots,\,p_n:o_n]\\ \\
\left(\forall\,i:\,o_i\in O,\,0\leq p_i \leq 1,\,\sum_{i}p_i=1\right)
\end{gather}
$$
$i$ 番目の結果 $o_i$ が起こる確率が $p_i$ である、ということですね。Lotteryの頭文字をとって$L$で表されることが多いです。

選好関係

結果に対して、どちらがより好ましいか、という選好関係を定義することができます。
ゲームの結果 $o_1$ と $o_2$ に対して、$o_1$ の方が $o_2$より好ましいことを
$$
\begin{gather}
o_1\succ o_2
\end{gather}
$$
で表します。また、$o_1$ と $o_2$ の好ましさが等しいことを、
$$
\begin{gather}
o_1\sim o_2
\end{gather}
$$
で表します。くじについても同様に選好関係を考えることができます。

選好関係の公理

先程定義した選好関係において、以下の公理が成り立ちます。それぞれについて簡単に見ていきましょう。

完備性

任意の $o_1,\,o_2$ について、$o_1\succ o_2,\,\, o_2\succ o_1,\,\, o_1\sim o_2$ のいずれかが成り立ちます。

推移性

$o_1,\,o_2,\,o_3$ について $o_1\succsim o_2$ と $o_2\succsim o_3$ が成り立つとき、$o_1\succsim o_3$ が成り立ちます。

代替性

$o_1\sim o_2$ のとき、結果の並び $o_3,\,o_4,\,\cdots,\,o_k$ と、確率の並び $p,\,p_3,\,p_4,\,\,\cdots,\,p_k$ に対して
$$
\begin{gather}
[p:o_1,\,p_3:o_3,\,\cdots,\,p_k:o_k]\sim [p:o_2,\,p_3:o_3,\,\cdots,\,p_k:o_k]
\end{gather}
$$
が成り立ちます。ただし $p,\,p_3,\,p_4,\,\,\cdots,\,p_k$ は
$$p+\sum_{i=3}^{k} p_i=1$$
を満たします。

分解性

くじ $l_1,\,l_2$ があるとき、任意の $o_i\in O$ について $P_{l_i}(o_i)=P_{l_2}(o_i)$ が成立するならば、$l_1\sim l_2$ が成立します。

「くじ1」と「くじ2」があるとき、くじ1とくじ2についてどの結果も等しい確率で起こるなら、くじ1とくじ2の好ましさは等しいということです。

単調性

$o_1\succ o_2$ と $p>q$ が成立するとき、
$$
\begin{gather}
[p:o_1,\,1-p:o_2]\succ [q:o_1,\,1-q:o_2]
\end{gather}
$$
が成立します。

「くじ1」と「くじ2」からはいずれも、良い結果 $o_1$ と悪い結果 $o_2$ のいずれかが出るとします。くじ1の方が良い結果 $o_1$ を出しやすい場合、くじ1はくじ2より好ましいということです。

連続性

$o_1\succ o_2,\,o_2\succ o_3$ が成立するとき、ある $p\in [0,\,1]$ で
$$
\begin{gather}
o_2\succ [p:o_1,\,1-p:o_3]
\end{gather}
$$
を満たすようなものが存在します。

良い結果 $o_1$、普通の結果 $o_2$、悪い結果 $o_3$ があり、「くじ1」からは良い結果 $o_1$ と悪い結果 $o_3$ のどちらか片方が出るとします。このとき、常に普通の結果$o_2$ を得るのと変わらないようなくじのさじ加減が存在するということです。

期待効用定理

先程紹介した6つの公理のうち、代替性を除いた以下の5つの公理が成立するとします。

• 完備性
• 推移性
• 分解性
• 単調性
• 連続性

このとき、起こりうる結果の集合 $O$ から $[0,\,1]$ への関数$u:O\mapsto[0,\,1]$ で、
$$
\begin{align}
1.\,& u(o_1)>u(o_2)\iff o_1\succ o_2\\
2.\,& u([p_1:o_1,\,p_2:o_2,\,\cdots,\,p_n:o_n])=\sum_{i=1}^{n}(p_i\cdot u(o_i))
\end{align}
$$
を満たすようなものが存在します。これが期待効用定理です。証明は大変なのでこの記事では割愛します。

囚人のジレンマ

さて、ここからはいよいよナッシュ均衡やパレート最適に向けて、具体的なゲームの分析に入っていきましょう。ここでは説明のための例として、ゲーム理論の導入で必ず出てくる囚人のジレンマについて説明します。

ある刑務所には、二人の囚人である「囚人1」「囚人2」がいます。二人にはそれぞれ「自白」か「黙秘」の選択肢が与えられます。そして、二人の刑期はそれぞれの選択に応じて、以下のように決定されます。

• 自分だけ自白して相手が黙秘した場合、懲役0年（無罪放免）
• 相手だけ自白して自分が黙秘した場合、懲役3年
• 自分と相手がともに自白した場合、懲役2年
• 自分と相手がともに自白した場合、懲役1年

例えば囚人1が黙秘して囚人2が自白した場合、囚人1は懲役3年、囚人2は無罪放免となります。懲役は一般的に短ければ短いほど良いので、懲役 $n$ 年の利得を $-n$ で表しましょう。

利得を二人分をまとめて、(囚人1の利得, 囚人2の利得)という形式で表すことにします。すると、囚人1が黙秘して囚人2が自白するケースの利得は $(-3,\,0)$ と表すことができます。

これを全ケースについて考えると、以下の表が完成します。

さて、この場合に「それぞれのプレイヤーにとって最も望ましい戦略は何か？」、あるいは「最も二人にとって望ましいケースは何か？」というのがここからの問いになります。

支配戦略均衡

もしあなたが囚人1であったなら、どのような戦略を取るでしょうか。

囚人1の立場から考えてみましょう。もし囚人2が黙秘を選ぶとした場合、自分が黙秘した場合の利得は $-1$ 、自分が自白した場合の利得は $0$ です。自白の方が利得が高いですね。

もし囚人2が自白を選ぶとした場合、自分が黙秘した場合の利得は $-3$ 、自分が自白した場合の利得は $-2$ となります。自白の方が利得が高いです。

したがって、囚人2が何を選ぶかに関わらず、囚人1にとっては常に「自白」する方が「黙秘」よりも利得が高くなります。このような場合、囚人1にとって「自白」は「黙秘」に対して支配的である、といいます。

同様に、囚人2にとっても「自白」は「黙秘」に対して支配的です²。

以上より、(自白, 自白)という戦略の組は他の戦略に対して支配的です。このような戦略の組のことを支配戦略均衡といいます。

ナッシュ均衡

ナッシュ均衡は、ゲーム理論に登場する概念の中で最も有名なものの一つです。まずはナッシュ均衡について直感的な説明を行い、その後ナッシュ均衡の定義を紹介します。

直感的な説明

それぞれのプレイヤーの戦略の組 $(a_1,\,a_2,\,\cdots,\,a_n)$ について考えます。例えば囚人のジレンマにおいて、囚人1と囚人2がともに自白を選択する戦略の組(自白, 自白)について考えてみましょう。

先述したように、囚人2が自白を選択するとわかっている場合、囚人1は自白を選択したほうが利得は高いです。同様に、囚人1が自白を選択するとわかっている場合、囚人2にとっては自白を選択したほうが利得が高くなります。

このように、すべてのプレイヤーにとって、現在とっている戦略が他の人の戦略に対して最適な反応である場合、そのような戦略の組は「ナッシュ均衡である」と呼ばれます。つまり、ナッシュ均衡のもとで誰か一人だけが現在の戦略を変更しようとすると、その人の利得は必ず低下する³ということです。

少し丁寧に考えてみましょう。ここまでの説明で理解できた人は、ナッシュ均衡の定義に進んでいただいて構いません。

囚人のジレンマにおいて、（自白, 自白)がナッシュ均衡となっていることを確かめます。「すべてのプレイヤーにとって、現在とっている戦略が他の人の戦略に対して最適な反応である」かどうかを確かめたいので、まずはプレイヤー1について確かめてみましょう。

プレイヤー1は現在自白しています。これは、囚人2が自白するという状況のもとで、最適な反応といえるでしょうか。再三述べているように、囚人2が自白する場合、囚人1の利得が高くなる戦略は自白です。プレイヤー1については確かに現在の戦略が最適な反応ですね。

プレイヤー2についてはどうでしょうか。プレイヤー2も現在自白していますが、これは囚人1が自白するという状況のもとで、最も利得が高くなる反応です。プレイヤー2についても、他の人が取っている戦略に対して「自白」は最適だといえます。

したがって、「すべてのプレイヤーにとって、現在とっている戦略が他の人の戦略に対して最適な反応である」ことが確かめられたので、囚人のジレンマにおいて（自白, 自白)は確かにナッシュ均衡となっています。

ナッシュ均衡の定義

もう少し厳密に定義してみましょう。標準形ゲーム$G$は、

• プレイヤーを表す集合 $P={1,\,2,\,\cdots,\,n}$
• それぞれのプレイヤー $i$ が取れる行動を表す集合$A_i$の直積$A=A_1\times A_2\times \cdots \times A_n$
• $A$から、プレイヤー $i$ にとっての効用への関数$u_i(a)$を並べた集合$U={u_1,\,u_2,\,\cdots,\,u_n}$

のタプル $G\,(P,\,A,\,U)$で表されたのでした。
このゲーム $G$ において戦略の組 $a=(a_1,\,a_2,\,\cdots,\,a_n)$ がナッシュ均衡であるとは、
$$
\begin{gather}
\forall i\in P,\,\forall a'_i\in A_i,\quad u_i(a)\geqq u_i(a^*_{-i})\\
(a^*_{-i}=(a_1,\,a_2,\,\cdots,\,a'_i,\,\,\cdots,\,a_n))
\end{gather}
$$
が成立することをいいます。
特に
$$
\begin{gather}
\forall i\in P,\,\forall a'_i\in A_i\setminus\{a_i\},\quad u_i(a)> u_i(a^*_{-i})\\
(a^*_{-i}=(a_1,\,a_2,\,\cdots,\,a'_i,\,\,\cdots,\,a_n))
\end{gather}
$$
となるとき、強いナッシュ均衡と呼びます。すなわち、すべてのプレイヤーが、自分以外の戦略に対して唯一最適となる選択をしているとき、それは強いナッシュ均衡です。

強いナッシュ均衡でないナッシュ均衡を、弱いナッシュ均衡と呼びます。

また、薄々感づいている方もいらっしゃるかもしれませんが、支配戦略均衡はナッシュ均衡となります。一方、ナッシュ均衡だからといって支配戦略均衡になるとは限りません。

囚人のジレンマの場合はたまたま、(自白, 自白)という戦略の組が支配戦略均衡でもあり、ナッシュ均衡でもあります。

パレート最適

ナッシュ均衡は、ある意味それぞれのプレイヤーが合理的な選択をした結果だといえます。しかし全体を俯瞰したとき、（自白, 自白）の利得 $(-2,\,-2)$ は最適だといえるでしょうか。

表から明らかなように、（黙秘, 黙秘）の利得 $(-1,\,-1)$ は明らかに(自白, 自白)の利得 $(-2,\,-2)$ よりも良いですね。この（黙秘, 黙秘）の戦略の組が全体の中で最も良いということを説明するのが、パレート最適の概念です。まずは直感的な説明から入りましょう。

直感的な説明

ナッシュ均衡のときと同様に、戦略の組 $(a_1,\,a_2,\,\cdots,\,a_n)$ について考えてみましょう。例えば囚人のジレンマにおいて、双方が共に黙秘を選択する戦略の組（黙秘, 黙秘）について考えます。

囚人1の利得をこれ以上よくするにはどうすればよいでしょうか。囚人1の利得が $-1$ よりも高くなるのは、囚人1のみが自白して囚人2は黙秘する(自白, 黙秘)のみですね。このとき、囚人1の利得は $-1$ から $0$ に改善されますが、囚人2の利得は $-1$ から $-3$ へと低下します。

以上からわかるように、(黙秘, 黙秘)が選択されている場合、囚人1の利得をこれ以上よくするためには囚人2の利得を低下させる必要があります。同様に、囚人2の利得をこれ以上よくするためには囚人1の利得を低下させることが必要です。

このように、誰かの利得を改善するためには誰かの利得を低下させなければならないような状況となっている戦略の組のことを、パレート最適と呼びます。社会的に最も望ましいとされる状況は、必ずパレート最適です⁴。

パレート支配

ここからは、数式を用いてパレート最適を定義していきましょう。まずはパレート支配についての説明です。

標準形ゲーム $G(P,\,A,\,U)$ を考えます。
戦略の組 $s$ が戦略の組 $s'$ をパレート支配するということは、
$$
\begin{gather}
\forall i\in P,\quad u_i(s)\geqq u_i(s')\\
\exists i\in P,\quad u_i(s)> u_i(s')
\end{gather}
$$
が満たされることをいいます。

日本語にすれば、「すべてのプレイヤーにとって $s$ の利得は $s'$ の利得より悪くなく、しかも誰かの利得は $s$ の方が $s'$ よりも良い」とき、$s$ は $s'$ をパレート支配するということです。

パレート最適の定義

戦略の組 $s$ がパレート最適であるとは、$\forall s'\in A$ に対して、$s$ をパレート支配するような $s'$ が存在しないということです。

すなわち、他のどの戦略の組にもパレート支配されない戦略の組のことを、パレート最適といいます。

まとめ

今回はゲーム理論への導入として、主に以下のトピックについて扱いました。

• 標準形ゲーム
• くじと選好関係
• 支配戦略均衡
• ナッシュ均衡
• パレート最適

いずれもゲーム理論で必ず出てくる重要なトピックです。次回は混合戦略と相関戦略などについて扱っていこうと思います。

訳出について

専門用語は、Wikipediaを参考に以下のように訳出しています。

日本語	英語
確率ゲーム	Stochastic Game
確定ゲーム	Deterministic Game
完全情報ゲーム	Perfect Information Game
不完全情報ゲーム	Imperfect Information Game
標準型ゲーム	Normal Form Game
利得	payoff
効用	utility
選好関係	Preference Relation
期待効用定理	Utility Theorem
戦略の組	Strategy Profile
支配戦略	Dominant Strategy
支配戦略均衡	Dominant Strategy Equilibrium
ナッシュ均衡	Nash Equilibrium
強いナッシュ均衡	Strong(Strict) Nash Equilibrium
弱いナッシュ均衡	Weak Nash Equilibrium
パレート最適	Pareto Optimum
パレート支配	Pareto Domination

参考文献

1. Yoav Shoham and Kevin Leyton-Brown, "Multi-Agent Systems", Cambridge University Press(2009)
2. 野村證券, "証券用語解説集　ゲーム理論", https://www.nomura.co.jp/terms/japan/ke/A01891.html, 最終閲覧2022/11/02
3. Wikipedia, "ゲーム理論", https://ja.wikipedia.org/wiki/%E3%82%B2%E3%83%BC%E3%83%A0%E7%90%86%E8%AB%96, 最終閲覧2022/11/02
4. 画像素材: Unsplash, https://unsplash.com/ja, 最終閲覧2022/11/02

なお、内容の説明にはLeibniz Universität HannoverのDaniel Kudenko先生の講義を参考にしています。

1. 自分の利益が、自分の行動のみならず、他者の行動にも影響される状況をいいます。 ↩

2. 対称性より自明ですが、自分で確認してみるとよいかもしれません。 ↩

3. 変わらないときもあります。定義を参照してください。 ↩

4. パレート最適だからといって社会的に最も望ましい状況とは限りません。 ↩