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

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

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

次回 ▶ [【ゲーム理論】第2回 - 零和ゲームと混合戦略、相関戦略について解説](https://qiita.com/inoz/items/c8922eac71c5a2ee381e)

<img width="500" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2519394/f2ed8cab-1232-1c8d-c8e3-f424b988ebf5.jpeg">

# ゲーム理論とは
ゲーム理論は、**経済学や政治学**はもちろん、**工学やコンピュータ科学**など様々な分野で幅広く活用されている、**意思決定の数学的モデルに関する理論**です。[**ノイマン**](https://ja.wikipedia.org/wiki/%E3%82%B8%E3%83%A7%E3%83%B3%E3%83%BB%E3%83%95%E3%82%A9%E3%83%B3%E3%83%BB%E3%83%8E%E3%82%A4%E3%83%9E%E3%83%B3)や[**ナッシュ**](https://ja.wikipedia.org/wiki/%E3%82%B8%E3%83%A7%E3%83%B3%E3%83%BB%E3%83%8A%E3%83%83%E3%82%B7%E3%83%A5)といった名前が有名所でしょうか。

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

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

<img width="500" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2519394/84a2defa-a3ce-f5aa-1f24-5bab0bc41346.jpeg">

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

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

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

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

## 分類の例
具体例で見ていきましょう。代表的なゲームを以上の枠組みに基づいて分類すると、以下のようになります。
<img width="500" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2519394/5ba29446-afaf-2e5d-3602-01106324665f.png">
**[チェス](https://ja.wikipedia.org/wiki/%E3%83%81%E3%82%A7%E3%82%B9)や[囲碁](https://ja.wikipedia.org/wiki/%E5%9B%B2%E7%A2%81) **は、「**現在の盤面**」と「打つ手に対して現在の**盤面がどのように変化するのか**」のいずれについても、双方のプレイヤーが同等の知識を持っています。盤面は互いが指した手のみによって変化していくのでゲームの結果は運に依存せず、これらは**確定的な完全情報ゲーム**です。

[**モノポリー**](https://ja.wikipedia.org/wiki/%E3%83%A2%E3%83%8E%E3%83%9D%E3%83%AA%E3%83%BC)は盤面や手札の状態こそ共有されていますが、**さいころ**を使っているため明らかに運の要素が含まれます。したがってこれは「**確率的な完全情報ゲーム**」です。

[**軍人将棋**](https://ja.wikipedia.org/wiki/%E8%BB%8D%E4%BA%BA%E5%B0%86%E6%A3%8B)は馴染みのない方もいるかと思いますが、極めて簡単に言えばコマを伏せた状態で行う将棋のようなものです。運の要素は含まれないものの、それぞれのプレイヤーは相手がどこにコマを配置したのかを知らないため、「**確定的な不完全情報ゲーム**」となります。

[**ポーカー**](https://ja.wikipedia.org/wiki/%E3%83%9D%E3%83%BC%E3%82%AB%E3%83%BC)は手札を伏せるとともに、どの札を引くかといった運の要素が含まれるため「**確率的な不完全情報ゲーム**」です。

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

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

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

まずはゲームに参加するプレイヤーが $n$ 人いるとします。この状況をプレイヤーの集合$P=\\{1,\\,2,\\,\\cdots,\\,n\\}$で表します。
> ここでは例として、**2人で行うじゃんけん**を考えます。2人で行うじゃんけんの場合、$P=\\{1,\\,2\\}$です。
<img width="400" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2519394/50786dd1-c518-8224-e5c7-6277c6a2f92a.png">

プレイヤーはそれぞれ、**実施できる行動の選択肢**を持っています。**それぞれのプレイヤーが取れる行動の選択肢が全員同じとは限らない**ため、$i$ 番目のプレイヤーが取れる行動の集合を$A_i$で表しましょう。集合$A_1,\\,A_2,\\,\\cdots\\,A_n$の[**直積**](https://ja.wikipedia.org/wiki/%E7%9B%B4%E7%A9%8D%E9%9B%86%E5%90%88)$A$で、**プレイヤー全員の行動の選択肢**を表すことができます。
> じゃんけんの場合はどちらのプレイヤーもグー・チョキ・パーのうちから1つを選んで出すことができるため、$A_1=A_2=\\{\\text{グー},\\,\\text{チョキ},\\,\\text{パー}\\}$です。
<img width="400" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2519394/7c188cfc-0745-76d8-dccc-21ae0dc4e6fa.png">

ここで、$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$となります。
<img width="400" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2519394/ceccbb0c-90b9-8874-74ab-d1cd3fb47d4e.png">

以上より、**標準形ゲーム**は以下の$P,\\,A,\\,U$からなる[**タプル**](https://ja.wikipedia.org/wiki/%E3%82%BF%E3%83%97%E3%83%AB)$(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)$ と表すことができます。
<img width="500" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2519394/ec293a34-86ba-3682-6b7c-ff87bc8efae7.png">

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

<img width="500" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2519394/1863e881-3412-daa0-07ac-7c01008db1c7.png">

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

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

囚人1の立場から考えてみましょう。もし**囚人2が黙秘を選ぶ**とした場合、自分が黙秘した場合の利得は $-1$ 、自分が自白した場合の利得は $0$ です。**自白の方が利得が高い**ですね。
<img width="500" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2519394/1625e29e-2418-8b99-631f-80e53557c903.png">

もし**囚人2が自白を選ぶ**とした場合、自分が黙秘した場合の利得は $-3$ 、自分が自白した場合の利得は $-2$ となります。**自白の方が利得が高い**です。
<img width="500" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2519394/8d3420d5-64ac-ed28-4103-e9d50cfb3bde.png">

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

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

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

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

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

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

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

<img width="500" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2519394/cdc222d8-e329-d263-3090-5f65cc13d389.png">

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

囚人のジレンマにおいて、（**自白, 自白**)が**ナッシュ均衡**となっていることを確かめます。「すべてのプレイヤーにとって、現在とっている戦略が他の人の戦略に対して最適な反応である」かどうかを確かめたいので、まずはプレイヤー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)$ は最適だといえるでしょうか。
<img width="500" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2519394/f8a27880-7023-c27f-3edb-4de0988a32ed.png">
表から明らかなように、（**黙秘, 黙秘**）の利得 $(-1,\\,-1)$ は明らかに(自白, 自白)の利得 $(-2,\\,-2)$ よりも良いですね。この（黙秘, 黙秘）の戦略の組が全体の中で最も良いということを説明するのが、**パレート最適**の概念です。まずは直感的な説明から入りましょう。

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

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

<img width="500" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2519394/bb49359f-e36d-2b5d-376a-6793cd837766.png">


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

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

<img width="500" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2519394/8a3e731e-0c04-651a-9608-27e9e738bfa6.png">

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

標準形ゲーム $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](https://ja.wikipedia.org/wiki/%E3%82%B2%E3%83%BC%E3%83%A0%E7%90%86%E8%AB%96)を参考に以下のように訳出しています。
| 日本語 | 英語 |
| :-: | :-: |
| 確率ゲーム | 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]: パレート最適だからといって社会的に最も望ましい状況とは限りません。