ぽんすけのしがないブログ

0. 目次

0. 目次
1. まえがき
2. 戦略形ゲーム
- 2.1. 戦略形ゲームの定義
3. 囚人のジレンマは戦略形ゲーム
4. 囚人のジレンマにおける支配戦略
- 4.1. 「強支配する・される」、強支配戦略の定義
- 4.2. 「弱支配する・される」、弱支配戦略の定義
5. ナッシュ均衡の導入
8. ナッシュ均衡と支配戦略の組
7. まとめ
8. あとがき

1. まえがき

こんにちは。

最近大学でゲーム理論の講義を取ったので、復習がてら記事にしてみたいと思います。

私自身も学部2年生でまだまだ勉強中ですので、誤りや修正すべき点があった場合は遠慮せずに指摘していただけるとうれしいです。

さて、前回の記事では、ゲーム理論の導入ということで、囚人のジレンマを例に出してゲーム理論がどのような学問なのかを簡単に紹介しました。

tidbits555.hatenablog.com

今回から、いよいよ本格的にゲーム理論について学んでいきます。

最初に扱うのは、戦略形ゲームとナッシュ均衡です。

2. 戦略形ゲーム

前回の記事で、ゲーム理論では戦略的状況を分析すると学びました。

おさらいですが、戦略的状況とは、

他者の行動が自身の利益に影響する状況

を指すのでした。

そこで今回は、そのうちの戦略形ゲームという状況を考えます。

2.1. 戦略形ゲームの定義

戦略形ゲーム（strategic-form game）とは、完備情報（complete information）の仮定のもと、次の三要素を含む同時手番（simultaneous move）ゲームである。

複数人のプレイヤー $i = 1, \space \cdots, \space N$
プレイヤー $i$ の戦略 $a_i$
プレイヤー $i$ の利得 $u_i(a_1, \space \cdots, \space a_N)$

と言われてもよくわからないと思うので、少しずつかみ砕いて説明します。

同時手番（どうじてばん）とは、各プレイヤーが同時に一度だけ行動することを意味します。不自然ではありますが、一回勝負のじゃんけんは同時手番ゲームです。

プレイヤーとは、単にゲームの参加者です。一回勝負のじゃんけんにAさんとBさんが参加するとき、AさんとBさんはこのゲームのプレイヤーです。

戦略*1とは、プレイヤーが選択可能な行動です。一回勝負のじゃんけんの例でいうと、AさんとBさんはともにグー・チョキ・パーという3通りの戦略を持ちます。

利得とは、このゲームを通して各プレイヤーがどれくらい得をしたかを表す数値です。各プレイヤーの戦略 $a_1, \space \cdots, \space a_N$ を与えると、プレイヤー $i$ の利得を返す利得関数 $u_i(a_1, \space \cdots, \space a_N)$ として表されることもあります。一回勝負のじゃんけんの例でいえば、勝ちで1ポイント、あいこで0ポイント、負けで-1ポイントとすると、Aさんがグー、Bさんがパーを出した時、Aさんの利得は $u_A(a = \text{グー}, \space b = \text{パー}) = -1$ となります。

ただし、今回の一回勝負のじゃんけんのような単純なゲームの場合は、利得関数ではなく下のような利得表で表現する方が分かりやすいことがあります。

一回勝負のじゃんけんの利得表
3×3のセルで構成されており、各セルには（Aの利得, Bの利得）が表記されている

完備情報*2とは、各プレイヤーは他プレイヤーがどの戦略を選択するかだけ知らないという状態を意味します。つまり、各プレイヤーは他プレイヤーがどんな戦略を持っているかを知っており、さらには全プレイヤーがどの戦略を選択するかが定まったとき、それぞれがどのような利得を得るかを知っているということです。

3. 囚人のジレンマは戦略形ゲーム

実は、前回扱った囚人のジレンマも戦略形ゲームでした。

tidbits555.hatenablog.com

先ほどの定義と照らし合わせて確認してみましょう。

複数のプレイヤー：AさんとBさん
各プレイヤーの戦略：Aさん、Bさんともに黙秘か自白
各プレイヤーの利得： $\text{(懲役の年数)} \times (-1)$
AさんとBさんは別の部屋で取り調べを受けているので、お互いの戦略を知らない。この状況は同時手番に等しい。*3

確かに戦略形ゲームの条件を満たしています。

4. 囚人のジレンマにおける支配戦略

前回の記事での分析の結果、AさんとBさんはともに自白を選ぶだろうということが分かりました。なぜなら、Bさんが黙秘と自白のどちらでも、Aさんは自白を選ぶ方が利得が高くなり、さらにはAさんが黙秘と自白のどちらでも、Bさんは自白を選ぶ方が利得が高くなるからでした。

実は、AさんとBさんにとっての自白のように、相手の戦略が何であっても「自分はこの戦略を選べば間違いなし！」という戦略には名前がついており、強支配戦略と呼ばれます。

以下、正確に定義します。

4.1. 「強支配する・される」、強支配戦略の定義

強支配する・強支配される

プレイヤー $i$ のある戦略 $a_i$ が、プレイヤー $i$ のある戦略 $a'_i$ を強支配するとは、他プレイヤーたちがどんな戦略組をとっても、

$\displaystyle (\text{プレイヤー} i \text{が} a_i \text{を選んだ時のプレイヤー} i \text{の利得}) \gt (\text{プレイヤー} i \text{が} a'_i \text{を選んだ時のプレイヤー} i \text{の利得})$

が成立することである。

また、このとき戦略 $a'_i$ を、戦略 $a_i$ に強支配される戦略という。

強支配戦略

戦略 $a_i$ が $\forall a'_i \in A_i \setminus \{a_i\}$ を強支配するとき、戦略 $a_i$ を強支配戦略という。

簡単にいうと、プレイヤー $i$ にとってベストな戦略が強支配戦略。

（ $A_i$ とはプレイヤー $i$ の戦略の集合を意味し、 $A_i \setminus \{ a_i \}$ でプレイヤー $i$ の $a_i$ 以外の戦略全体を意味しています。）

強支配があるので、当然弱支配もあります。

以下、弱支配について定義します。

4.2. 「弱支配する・される」、弱支配戦略の定義

弱支配する・弱支配される

プレイヤー $i$ のある戦略 $a_i$ が、プレイヤー $i$ のある戦略 $a'_i$ を弱支配するとは、他プレイヤーたちがどんな戦略組をとっても、

$\displaystyle (\text{プレイヤー} i \text{が} a_i \text{を選んだ時のプレイヤー} i \text{の利得}) \geq (\text{プレイヤー} i \text{が} a'_i \text{を選んだ時のプレイヤー} i \text{の利得})$

が成立し、かつ、他プレイヤーたちのある戦略組に対しては、

が成立することである。

また、このとき戦略 $a'_i$ を、戦略 $a_i$ に弱支配される戦略という。

弱支配戦略

戦略 $a_i$ が $\forall a'_i \in A_i \setminus \{a_i\}$ を弱支配するとき、戦略 $a_i$ を弱支配戦略という。

簡単に言うと、他プレイヤーたちの戦略組にかかわらず常に単独1位であるわけではないものの、これにしておけば間違いない戦略が弱支配戦略。

5. ナッシュ均衡の導入

5.1. 支配戦略のないゲーム

これから先、2人の戦略組を（Aさんの戦略, Bさんの戦略）と表すこととします。例えば、Aさんが自白、Bさんが黙秘を選択するという戦略組は（自白, 黙秘）と表現します。

さて、囚人のジレンマでは、強支配戦略の組である（自白, 自白）が選ばれるだろうと分析しました。なぜなら、AさんとBさんにとって自白がベストな選択だからです。

では、次のような戦略形ゲームではどうでしょうか。

AさんとBさんは家族で、スマホの機種変更をしようとしている
AさんBさんともに、選択肢はiPhoneかAndroidの2通りである
2人ともiPhoneを選ぶと、AirDropが使えたり、iCloudのファミリープランをお得に使えたりするので、とてもうれしい
2人ともAndroidを選ぶと、機種が同じということで操作が分からなくてもお互いに聞きあうことができるので、まあまあうれしい
一方がiPhone、もう一方がAndroidを選ぶと、不便なことが多いのであまりうれしくない
利得表は以下の通り

この戦略形ゲームに支配戦略の組はあるでしょうか。確認してみましょう。

Aさん

BさんがiPhoneを選ぶ時は、AさんもiPhoneを選ぶのが良い

BさんがAndroidを選ぶ時は、AさんもAndroidを選ぶのが良い

→ Aさんに支配戦略はない。

Bさん

AさんがiPhoneを選ぶ時は、BさんもiPhoneを選ぶのが良い

AさんがAndroidを選ぶ時は、BさんもAndroidを選ぶのが良い

→ Bさんに支配戦略はない。

どうやらこのゲームには、支配戦略の組はないようです。

万事休す…

というわけではありません。

ここで、ナッシュ均衡という新しい概念を導入してみましょう。

その前に、最適反応という概念の導入が必要なので、最適反応から説明します。

5.2. 最適反応の定義

最適反応

プレイヤーが $N$ 人参加するゲームを考える。

プレイヤー $i$ の戦略を $a_i$ と表し、プレイヤー $i$ 以外の $N-1$ 人のプレイヤーの戦略組を $a_{-i}$ と表すこととする。

このとき、プレイヤー $i$ の戦略 $a_i$ が、プレイヤー $i$ 以外の $N-1$ 人のプレイヤーのある戦略組 $a_{-i}$ に対する最適反応であるとは、次が成り立つことである。

$\displaystyle \forall a'_i \in A_i \setminus \{a_i\}, \quad u_i(a_i, \space a_{-i}) \geq u_i(a'_i, \space a_{-i})$

では、機種変更のゲームで最適反応を具体的に考えてみましょう。

5.3. 機種変更のゲームにおける最適反応

Bさんの戦略に対するAさんの最適反応

BさんがiPhoneという戦略をとるとき、

AさんがiPhoneを選ぶと、Aさんの利得は5
AさんがAndroidを選ぶと、Aさんの利得は1

よって、BさんのiPhoneという戦略に対するAさんの最適反応はiPhoneです。

BさんがAndroidという戦略をとるとき、

AさんがiPhoneを選ぶと、Aさんの利得は1
AさんがAndroidを選ぶと、Aさんの利得は3

よって、BさんのAndroidという戦略に対するAさんの最適反応はAndroidです。

わかりやすくするために、Bさんのそれぞれの戦略に対するAさんの最適反応の利得に赤で丸を付けておきましょう。

すると、利得表は下のようになります。

Aさんの戦略に対するBさんの最適反応

AさんがiPhoneという戦略をとるとき、

BさんがiPhoneを選ぶと、Bさんの利得は5
BさんがAndroidを選ぶと、Bさんの利得は1

よって、AさんのiPhoneという戦略に対するBさんの最適反応はiPhoneです。

AさんがAndroidという戦略をとるとき、

BさんがiPhoneを選ぶと、Bさんの利得は1
BさんがAndroidを選ぶと、Bさんの利得は5

よって、AさんのAndroidという戦略に対するBさんの最適反応はAndroidです。

今度は、Bさんの最適反応に青で丸を付けると、次のようになります。

続いて、ナッシュ均衡を定義します。

5.3. ナッシュ均衡の定義

ナッシュ均衡

ある戦略組 ${ S = (a^*_1, \space a^*_2, \space \cdots, \space a^*_N) }$ がナッシュ均衡であるとは、任意の ${ i \space (1 \leq i \leq N) }$ に対して、 $a^*_i$ が $a^*_{-i}$ の最適反応となっていることである。

特にプレイヤーが2人のとき、ある戦略組 $(a^*_1, \space a^*_2)$ がナッシュ均衡であるとは、 $a^*_1$ は $a^*_2$ に対する最適反応、かつ、 $a^*_2$ は $a^*_1$ に対する最適反応となっていることである。

簡単に言うと、最適反応の組がナッシュ均衡です。

では、機種変更のゲームでナッシュ均衡を求めてみましょう。

5.4. 機種変更のゲームにおけるナッシュ均衡

ナッシュ均衡は、最適反応の組でした。

これまでに求めた最適反応についてまとめなおしましょう。

BさんのiPhoneに対する、Aさんの最適反応：iPhone

BさんのAndroidに対する、Aさんの最適反応：Android

AさんのiPhoneに対する、Bさんの最適反応：iPhone

AさんのAndroidに対する、Bさんの最適反応：Android

すると、（iPhone, iPhone）と（Android, Android）の戦略組が最適反応の組になっていることが分かります。

AさんのiPhoneはBさんのiPhoneに対する最適反応ですし、逆にBさんのiPhoneはAさんのiPhoneに対する最適反応ですよね。（Android, Android）についても同様です。

したがって、機種変更のゲームにおけるナッシュ均衡は、

（iPhone, iPhone）、（Android, Android）

となります。

今回のゲームのように、プレイヤーが2人の場合は、利得表を用いてより簡単にナッシュ均衡を求めることができます。

最適反応を求める際に、利得表に赤と青で丸を付けたと思いますが、その丸が二つそろっている戦略がナッシュ均衡となります。

利得表を利用した場合も、（iPhone, iPhone）、（Android, Android）がナッシュ均衡であると導けました。

このように、ナッシュ均衡が一つのゲームに複数存在することもあります。

その場合、ゲームの結果がどのナッシュ均衡になるかはわかりません。機種変更のゲームを例に挙げると、AさんとBさんがiPhoneユーザーの多い集団内にいれば（iPhone, iPhone）になるでしょうし、逆にAndroidユーザーの多い集団内にいれば（Android, Android）になるでしょう。

8. ナッシュ均衡と支配戦略の組

支配戦略の組が存在するならば、支配戦略の組はそのゲームで唯一のナッシュ均衡です。

支配戦略の組が存在した囚人のジレンマで確かめてみましょう。

確かに支配戦略の組である（自白, 自白）がナッシュ均衡になっています。

7. まとめ

これまで、戦略形ゲームとナッシュ均衡について学んできました。

戦略形ゲームとは、「複数プレイヤー・戦略・利得」の三要素をもった同時手番ゲームでした。
戦略形ゲームにおける均衡を考える際に、支配戦略の組がある場合は、ゲームの結果はその支配戦略の組になると考えられますが、支配戦略がないゲームでも分析ができるようにナッシュ均衡というものを導入しました。ナッシュ均衡とは、最適反応の組でした。

8. あとがき

いかがでしたか？

かなり長文になってしまいました。

最初はなかなかとっつきにくい概念が多いかもしれませんが、学習を進めるにつれてだんだん慣れていくでしょう。

次回もお楽しみに！

*1:戦略形ゲームという文脈においては問題ありませんが、展開形ゲーム（別の記事で扱います）においては戦略と行動は異なるので注意が必要です。

*2:完全情報（perfect information）とは異なる概念です。似ているので注意が必要です。

*3:別の部屋で取り調べを受けているので、相手が黙秘と自白のどちらを選んだかを知ることはできません。同時手番では2人が別の部屋に分かれているという制約はないものの、戦略を決定するのが同時であるため、戦略を決定し宣言するその瞬間まで、相手が黙秘と自白のどちらかを選んだかを知ることはできません。この点において、これら二つの状況は等しいといえます。