バックワードインダクションで展開形ゲームを解く

完全情報展開形ゲームとその解き方であるバックワードインダクション(backward induction)について「展開形ゲームとは?ゲームの木とは?」で、ざっくりと話しました。ここではバックワードインダクションによるゲームの解き方を、もう少し詳しく説明します。

バックワードインダクションでゲームを解く

バックワードインダクションは完全情報展開形ゲームの解き方です。各プレイヤーは自分よりあとに行動するプレイヤーの行動を先読みし、自分の利得を最大にするように行動を選ぶのでした。

これを言い換えるとゲームは「時間的に後から行動するプレイヤーの行動から順番に解いてゆく」ということになります(有限時間の場合)。後から帰納的に(順番に)解くという意味でバックワードインダクションと呼ばれるのです。

バックワードインダクション(backward induction)は翻訳すると「後向き帰納法」「後向き遡及法」などと翻訳されるのですが、しっくりこないんでカタカナ語で書いたりすることが多いです。

具体的には、次のようにゲームを解いていきます。

1。最後のプレイヤー、つまり「そのプレイヤーが何を選んでもゲームが終わる」ようなプレイヤーの行動を求めます。そのプレイヤーは、自分が行動を選ぶと自分の利得が決まるので、そのプレイヤーが自分の利得を最大にする行動を決定することができます。
2。既に行動を求めたプレイヤーの直前に行動するプレイヤーの中から、<そのプレイヤー以降に行動するプレイヤーの行動がすべて決まっているプレイヤー>の行動を求めます。そのプレイヤーは、自分が行動を選ぶと、それ以降のプレイヤーの行動が決まっている(か、またはゲームが終わる)ために利得が決まるので、利得を最大にする行動を決定することができます。
3。2を繰り返して行き、一番最初のプレイヤーの行動が求められたら終わり…です。

例題

いくつかの例題を見てみましょう。説明をするためには、ゲームの木の点に名前がついていると便利ですので、そうしておきます。(正確には意思決定点にラベルを付けておきます。ゲームの木を少し詳しく説明!も参照してください。)

(例1)まず最初は「展開形ゲームとは?ゲームの木とは?」で説明した<コンビニ立地ゲーム>の例(図1)を、バックワードインダクションの手順の観点から、もう一度解いてみます。

図1:コンビニ立地ゲームの例

1。最後に行動するプレイヤーは、\(x2\),\(x3\)で行動するファミモなので、そこでの行動を決めます。 \(x_2\)では、ファミモはAを選べば利得が400、Bを選べば利得が300となのでAを選びます。 \(x_3\)では、ファミモはAを選べば利得が600、Bを選べば利得が200なのでAを選びます。こうして最後に行動するプレイヤーの行動が決まります。

2。次に、既に行動を求めたプレイヤーの直前に行動するプレイヤーは\(x_1\)で行動するセレブだけなので、そこでの行動を決めます。\(x_1\)では、セレブは、Aを選ぶと(ファミモがAを選ぶので)利得が200、Bを選ぶと(ファミモがAを選ぶので)利得が300となるのでBを選ぶ、というように行動が決定できます。これで最初のプレイヤーまで遡って行動が決まったので、おしまいです(図2)。

図2:例1のバックワードインダクション

(例2)もう少し複雑な例を考えてみましょう(図3)。今度は3人のゲームです。

図3はプレイヤー1,2,3の3人からなる、以下のようなゲームです。

図3:3人ゲーム、ゲームをプレイする順番は不規則
  • はじめにプレイヤー1が\(x_1\)で\(A\)か\(B\)を選びます。
  • もしプレイヤー1が\(A\)を選んだときは、プレイヤー3が\(x_2\)で\(C\)か\(D\)を選び、ゲームは終わります。
  • プレイヤー1が\(B\)を選んだときは、プレイヤー2が\(x_3\)で\(E\)か\(F\)を選びます。\(E\)を選ぶと、そこでゲームが終わります。
  • プレイヤー2が\(F\)を選ぶと、\(x_4\)でもう一度プレイヤー1の手番となり、プレイヤー1は\(G\)か\(H\)を選び、そこでゲームが終わります。

図3において、各点の上の数字は行動するプレイヤーを表しています。ゲームが終わったときの利得は、常に左からプレイヤー1、2、3の順になっています。

このゲームを、バックワードインダクションの手順に従い解いてみましょう。

1。最後に行動するプレイヤー(そのプレイヤーが何を選んでもゲームが終了するプレイヤー)の行動です。このゲームでは\(x_2\)で行動するプレイヤー3と、\(x_4\)で行動するプレイヤー1なので、そこでの行動を決めます。 \(x_2\)では、プレイヤー3は\(C\)を選べば利得が1、\(D\)を選べば利得が0なので\(D\)を選びます。\(x_4\)ではプレイヤー1は\(G\)を選べば利得が6、\(H\)を選べば利得が1なので\(G\)を選びます。こうして最後に行動するプレイヤーの行動が決まります。

2。次に、<そのプレイヤー以降に行動するプレイヤーの行動がすべて決まっているプレイヤー>は、\(x_2\)で行動するプレイヤー2なので、そこでの行動を決めます。\(x_2\)でプレイヤー2は、\(E\)を選ぶと利得が5、\(F\)を選ぶと(プレイヤー1がGを選ぶので)利得が4、となるので\(E\)を選ぶ、ということになります。(図4)

図4:例2のバックワードインダクション-その1

3。次に、\(x_1\)で行動するプレイヤー1の行動を決めます。\(x_1\)でプレイヤー1は、\(A\)を選ぶと(プレイヤー3が\(C\)を選ぶので) 利得が4、\(B\)を選ぶと(プレイヤー2が\(E\)を選ぶので)利得が3となるので\(E\)を選ぶ、ということになります。

図5:例2のバックワードインダクション

解と結果(均衡経路)を区別する

以上、バックワードインダクションによる完全情報ゲームの解の求め方について解説しました。このときバックワードインダクションで得られるゲームの解と、それによって予測されるゲームの結果は何であるか、について区別しなければなりません。ここで

ゲームの解とは、すべての点で各プレイヤーが何を選ぶかを、すべて明らかにしていること
ゲームの結果とは、ゲームの解によって、最初(初期点)のプレイヤーから順番にどのような行動が選ばれゲームが進行して、どの点でゲームが終わるかを示したもの

です。

例えば最初の例1を見てみましょう(図6)。

図6:ゲームの解と結果を区別する(例1)

このときゲームの解は「 \(x_1\)でセレブがBを選び、\(x_2\)と\(x_3\)でファミモはAを選ぶ」となります。このようにゲームの解はすべての点でプレイヤーが何を選ぶかを定めたものです。

これに対し、\(x_1\)でセレブがBを選べば、次に\(x_3\)でファミモがAを選んでゲームは終わり、実際には\(x_2\) は実現しません。ゲームの解によって、実際に起きる結果は解の一部です。

「すべての点(正しくは意思決定点)で何が選ばれるか」が決まると、「最初のプレイヤー(初期点)から、順番にどのプレイヤーがどの行動を選んでゲームが進行して、最後のプレイヤーの行動が決まって利得が決まるところ(終点)」まで一本の経路(path)ができます。この経路は均衡経路(equilibrium path)と呼ばれます。この均衡経路はゲームの結果であると考えられます。 この例の場合、均衡経路(=ゲームの結果)は「 \(x_1\)でセレブがBを選び、\(x_3\)で、ファミモはAを選ぶ」となります。

「すべての意思決定点で何が選ばれるか」は「戦略の組(strategy profile)」に対応するものです。またこれは1つの経路を実現すると考えても良いし、1つの終点が決まると考えても良いです。なお途中で確率による選択(混合戦略)があると、経路は1つではなく、複数の経路が確率的に決定されると考えられます。

ゲームの解において、均衡経路ではない意思決定点は均衡外経路(off-equilibrium path)と呼ばれます。 例1では\(x_2\)は均衡外経路です。このことよりゲームの解が異なってもゲームの結果が同じになることがあることに注意しましょう。

例2で、ゲームの解とゲームの結果が何であるかを練習してみましょう。


図7:ゲームの解と結果を区別する(例2)

この例2の場合は

  • ゲームの解は、プレイヤー1が\(x_1\)で\(A\)を\(x_4\)で\(G\)を選び、プレイヤー2が\(x_3\)で\(E\)を選び、プレイヤー3が\(x_2\)で\(C\)を選ぶ。
  • ゲームの結果は、プレイヤー1が\(x_1\)で\(A\)を選び、プレイヤー3が\(x_2\)で\(C\)を選ぶ。

となります。いかがでしょうか。

バックワードインダクションはゲーム理論だけではない

<後から解く>バックワードインダクションは、時間経過を伴う最適化問題である動的最適化(マクロ経済学、ファイナンス理論)、ネットワーク最適化問題にも用いられる一般的手法です。この概念を方程式に直すといわゆるベルマン方程式となります。

以下も参考にしてください。

東京都立大学 2020ゲーム理論1 オンライン講義(2020:コロナ対応)

展開形ゲームとは?ゲームの木とは?

ゲーム理論のゲームには、戦略形ゲーム(strategic form)と展開形ゲーム(extensive form)という2つの「表現」があります。戦略形ゲームは、プレイヤーは同時に行動を選ぶと考えてゲームを表します。これに対し、展開形ゲームは、先手と後手のあるゲームなど、どんなゲームでも表現できて、プレイヤーは同時に行動しなくても良いのです。

このような展開形ゲームの中でも、プレイヤーが1人ずつ順番に行動を選び(同時に行動することはなく)、各プレイヤーは自分より先に行動したプレイヤーが何を選んだかがすべて分かるゲームを完全情報(perfect information)の展開形ゲームと言います。代表的な例は、チェス、囲碁、将棋です。将棋で「自分より前に指した手が、何か分からん!」ってことはありませんよね?

完全情報ではないゲームは不完全情報(imperfect information)と呼びます、あたりまえですね。不完全情報ゲームの例としては、たとえば...「2人でじゃんけんをするとき、まず1人がグー・チョキ・パーを選んで紙に書いて相手に見えないように封筒に入れ、次にもう1人が改めてグー・チョキ・パーを選ぶ」という面倒なじゃんけんは不完全情報ゲームです.

...って、あれ?戦略形ゲームで勉強したように、これは同時に行動することと同じでした。「プレイヤーが同時に行動する戦略形ゲーム」は「不完全情報の展開形ゲーム」の典型的な例です。これはまた別の機会に。

ここでは完全情報の展開形ゲームとその解き方について学んで行きます。乱暴に言うと

  • 戦略形ゲームは利得行列で表しナッシュ均衡で解く
  • 完全情報展開形ゲームはゲームの木で表し、バックワードインダクションで解く

ということになります。乱暴すぎてかなり間違ってますが、細かいことは気にせず、ざっくり説明します。正確な定義や説明はゲーム理論のテキストなど読んでください。

完全情報展開形ゲームの例

以下の例を考えましょう。戦略形ゲームの支配戦略やナッシュ均衡の説明で使った例と同じです。今度はプレイヤーは同時に行動を選ぶのではなく、セレブ、ファミモの順に選びます。

2つのコンビニ、セレブ(セレブイレブン)とファミモ(ファミリーモール)が、A駅とB駅のどちらか一方に出店しようと考えている。コンビニを1日に利用する客はA駅が600人、B駅が300人である。セレブとファミモが違う駅を選べば利用客を独占できる。しかし同じ駅に出店すると、ファミモが人気で、ファミモはセレブの2倍の客数を獲得できる。すなわち両方がA駅に出店すると、セレブ200人、ファミモ400人。B駅に出店すると、セレブ250人、ファミモ500人である。ここで客数を利得と考える。

ここでは、まずセレブが先にどちらの駅を選ぶかを決定し、ファミモはそれを知ってから自分がどちらの駅に出店するかを決める。セレブとファミモはどちらの駅に出店するだろうか?

戦略形ゲームのように同時に行動するのではなく、プレイヤーが順番に行動をするゲームが展開形ゲームです。展開形ゲームは次のようなゲームの木で表します。

ゲームの木

ゲームの木の正確な定義は後でやろうと思いますが、ざっくりと理解したい人には、ゲームの木の説明は不要でしょう?まず最初にセレブがAかBかを選び、次にそれを知ってからファミモがAかBかを選ぶと、結果が決まるのでセレブとファミモの利得がそこに書いてある、とそんな感じです。

ゲームを解く

ではさっそく、このゲームを解いてみましょう。皆さんがセレブだったらAとBのどちらを選ぶでしょうか?セレブがAを選ぶと、うまく行けば(ファミモがBを選べば)600の利得を得られますし、Bを選ぶとヘタをすれば(ファミモがBを選べば)100の利得になってしまいますね。だから、セレブはAを選ぶことが答のように思えるかも知れません。

しかし、ゲーム理論の答ではセレブはBを選びます。

なぜでしょうか?このゲームでは、セレブだけではなく、相手プレイヤーのファミモも利得を大きくしたいと考えています。セレブは「うまく行けば」「ヘタをすると」と、自分勝手に考えるのではなく、ファミモの行動を考えて、自分の行動を選択する必要があります。このためにはセレブの次に行動するファミモの行動を先読みする必要があるわけです。

ファミモの行動を先読みしてゲームを解いてみましょう。

  • セレブがAを選ぶと、ファミモはAを選べば利得が400、Bを選べば利得が300となるなのでAを選ぶ
  • セレブがBを選ぶと、ファミモはAを選べば利得が600、Bを選べば利得が200なのでAを選ぶ

これを先読みするとセレブは、Aを選ぶと(ファミモがAを選ぶので)利得が200、Bを選ぶと(ファミモがAを選ぶので)利得が300となるのでBを選ぶ、ということになります(下図)。

ゲームは先読みで解く

結果は「セレブがBを選び、ファミモがAを選ぶ」となります。これが(完全情報)展開形ゲームの解き方です。この先読みによるゲームの解き方はバックワードインダクションと呼ばれます。

以上、とりあえず完全情報展開形ゲームについての簡単な説明と解き方でした。乱暴に言うと

  • 戦略形ゲームは利得行列で表しナッシュ均衡で解く
  • 完全情報展開形ゲームはゲームの木で表し、バックワードインダクションで解く

ということでしたね。乱暴すぎて、かなり間違ってますが、最初は細かいことは気にせず、そんな感じで覚えておけばよいでしょう。正確な定義や説明はゲーム理論のテキストなど読んでくださいね。なお。

  • バックワードインダクションによってゲームを解く方法は、「バックワードインダクションで展開形ゲームを解く」で、もう少し詳しく説明することにします。
  • ゲームの木については「ゲームの木について、ちょい詳しく」でお話します。
  • 一般の不完全情報ゲームとはどんなもので、どのように解くかは、またの機会に。お急ぎの方は「ゼミナールゲーム理論入門」で!

東京都立大学 2020ゲーム理論1 オンライン講義(2020:コロナ対応)

グリコじゃんけんの正しい解

グリコ・チョコレート・パイナップルじゃんけんについて。このゲームは勝ちと負けしかないゲームなのに、ネットなどでは3点や6点の利得を割り当て誤って計算されている例が多いです。実は拙著「ゼミナールゲーム理論入門」でも、初心者向けにと思って、そのような得点を仮定して解を求めて見せているのですが、それがそのまま本当の答えだと捉えられている傾向があり、これを正すまでは死ねないと思って書きましたよ。ぜひ、見てください! ⇒ グリコ・チョコレート・パイナップルゲームのゲーム理論による解

グリコ・チョコレート・パイナップルゲームのゲーム理論による解

グリコ(グリコじゃんけん)は「勝ち」と「負け」しかないのに、3点や6点の得点を割り当てて誤って計算されている答が多く、ゲーム理論として正しく解かれたものは(自分が知る限り)存在しない。ここでは 「グリコ・パイナップル・チョコレート」ゲームの正しい解について分析する。

このゲームは古くから知られていて、今でも子どもたちが遊んでいるのを見かける。多くの者の興味を引くようで、考察しているホームページや文献はいくつかあるが、どれも正しくない。…ということで、2019年度の渡辺ゼミの卒論で上野陽菜さんがこの問題に取り組んでくれたので、以下に発表。

本来は日本OR学会の2020年春季研究発表会で発表する予定であったが、コロナウィルス問題で学会が中止になったためここに公開。

結果の要旨を先にまとめると:

  • 相手と自分が立っている位置によって戦略は異なる。例えば、両方があと3歩でゴールできる場合は(3歩でも6歩でもゴールするので)普通のじゃんけんと同じになり、グー・チョキ・パーを1/3ずつ出すことが均衡になる。
  • 一方が他方よりゴールに近い場合、ゴールにより近い(つまり勝っている)プレイヤーは相手を6歩で勝たせる確率を少なくしようとしてチョキを多めに出す。これに対してゴールからより遠い(つまり負けている)プレイヤーはグーを出す確率を多めにして、少しずつ進む戦略を選ぶことが均衡となる。
  • 両者がスタート地点にいるとき、スタート地点が遠くなると均衡戦略は、巷でよく計算される「グー・チョキ・パーを2:2:1で出すこと」( グー、チョキ、パーを3点、6点、6点で換算した1回のゲームの均衡戦略)に近づく。

はじめに

「グリコ・パイナップル・チョコレート」はスタート地点からじゃんけんをして、グー(以下G)で勝てば「グリコ」で3歩進み、チョキ(以下C)かパー(以下P)で勝てば「チヨコレイト」「パイナツプル」で6歩進んで、先にゴールしたほうが勝ち、というゲームである。古くから知られていて、私が子供の頃、50年くらい前には既に存在していたが、今でも子どもたちが遊んでいるのを見かける。この記事では、この「グリコ・チョコレート・パイナップル」ゲームの2人のときのゲーム理論における解を解析する

もし、この2人ゲームの利得行列を図1の左側(進む歩数、進まれた歩数が利得)と考えるならば、ナッシュ均衡(零和ゲームなのでマキシミニ戦略と同じ)は「G,C,Pを2/5、2/5、1/5(2:2:1)で出す」ことが解になる。(求め方はいろいろなところに書いてある、例えばwikipedia) また右側と考えるならば「G,C,Pを1/4,1/2,1/4で出す」ことが解になる。

図1:誤った利得行列の例

ちなみに右側は拙著「ゼミナールゲーム理論入門」に載っていて、求め方も(丁寧に)解説している。初心者にゲーム理論への興味を湧かせるために、このような例を用いたのだが、いつの間にかこの例が広まってしまった。中には「この解はおかしい」という人まで現れた。いやね、おかしいのは分かってて「このような利得だと考えると」と注意をしているのに…。失敗だった。いつか、これを正しておかなければ死ねないと、ずっと思っていた。本稿を仕上げることで、やっと死ねる。

図1のようなモデル化は間違っている。誤りの1つ目の点は、このゲームは元々「先にゴールしたほうが勝ち」というルールであり結果は「勝ち」「負け」しかなく、進んだ歩数が利得ではないからである。3とか6などの数値には正確な意味がなく、勝つか負けるかしかなく、勝ちは+1、負けは-1というゲームになるはずだ。

もう1つ上記のモデルが誤っている点、見落としている点は、このゲームは相手と自分が立っている位置によって、戦略が異なるということである。これを確認するには2人ともあと三歩以内でゴールできるという状態を想定すれば良い。このときは3歩でも6歩でもゴールできるので、G,C,Pは同じ効果を持つ(与える利得は同じ)。このときのナッシュ均衡は普通のじゃんけんと同じ「G,C,Pを1/3ずつ出す」となることは明らかだ。すなわち、このゲームにおける均衡戦略は「お互いが、あと何歩でゴールできるか」という状態に依存する。

ここではゲームを「先にゴールすれば勝ち、ゴールされれば負け」と考え、「勝てば利得が1、負ければ利得が-1」の2人零和ゲームと考える。そして2人のゴールまでの距離を状態変数としたゲーム(マルコフゲーム)と捉え、定式化して分析する。

問題のモデル化

このゲームを2人零和ゲームと考え、以下のようにモデル化する。

  • 計算を単純にするため、3歩を1ステップと考える。
  • 2人のプレイヤーが、ゴールのNステップ前の距離からじゃんけんをはじめ、Gで勝つと1ステップ、C,Pで勝つと2ステップ進む。あいこだと、どちらも進まない。
  • 先にどちらかがゴールすればゲームが終了する。先にゴールした方は勝ちで利得1を獲得し、ゴールされた方は負けで利得-1とする。
  • 「行き過ぎ」は考えない。ピッタリゴールしなくても勝ちとする。例えば1ステップ前からCで2ステップ進んでも、勝利とする。
  • 時間経過による利得の割引は考えない。

プレイヤー1が、あと\(n\)ステップ、プレイヤー2があと\(m\)ステップでゴールする状態を\((n,m)\)( \(1 \leq n,m \leq N\))で表す。状態\((n,m)\)で、どちらかのプレイヤーが勝つと状態が遷移し、あいこだと同じ状態に留まる。たとえば状態\((10,9)\)のとき、プレイヤー1がパーで勝てば状態\((8,9)\)に遷移する。

状態\((n,m)\)でプレイヤーが直面するゲームのナッシュ均衡(マキシミニ戦略でもある)における、プレイヤー1の期待利得(ゲームの値)を\(v_{n,m}\)とする。

\(n=0,-1\)または\(m=0,-1\)の場合にはゲームが決着し値が定まっている。これが再帰的に問題を解く初期状態となる。すなわち
\( \begin{align}
v_{0,m}=v_{-1,m}=1 & v_{n,0}=v_{n,-1}=-1 \tag{1}
\end{align} \)
(\(1 \leq n,m \leq N\))とする。

このとき状態\((n,m)\)におけるゲームのプレイヤー1の利得は、以下の表となることが分かる。

状態(\(n,m\))におけるプレイヤー1の利得表

零和ゲームであることから、プレイヤー2の利得は、上記行列に-1を乗じたものとなる。

問題の解法

ゲーム\((n,m)\)のプレイヤー1の均衡戦略とゲームの値\(v_{n,m}\)を求める。なお、ここでプレイヤー2の戦略は、状態\((m,n)\) でのプレイヤー1の戦略と同じになる。

プレイヤー1が均衡において、G,C,Pを出す確率(混合戦略)を\(q_G,q_C,q_P\)とする。このときプレイヤー2がG,C,Pを出したときのプレイヤー1の期待利得を\(E_G,E_C,E_P\)とすると、
\( \begin{align}
E_G=q_Gv_{n,m}+q_Cv_{n,m-1}+q_Pv_{n-2,m} \\
E_C=q_Gv_{n-1,m}+q_Cv_{n,m}+q_Pv_{n,m-2} \\
E_P=q_Gv_{n,m-2}+q_Cv_{n-2,m}+q_Pv_{n,m}
\end{align} \)
となる。

ここでナッシュ均衡では
\[
E_G=E_C=E_P=v_{n,m} \tag{2}
\]
が成立する。

上記の理由を正確に説明すると長くなるため端折って説明する。このゲームには、純粋戦略のナッシュ均衡はない。そして、これから1つの戦略に確率0を割り当てる(つまり2つの戦略のみに確率を割り当てる)ような混合戦略を用いたナッシュ均衡が存在しないことも分かる。ナッシュ均衡は必ず存在するので、このゲームにはすべての戦略に正の確率を割り振るような混合戦略(完全混合戦略と呼ぶ)のナッシュ均衡しかないことが分かる。

このゲームは零和ゲームであるたm、\(E_G,E_C,E_P\)はプレイヤー2がG,C,Pを出したときのプレイヤー1の期待利得であると同時に、プレイヤー2の期待利得に-1をかけたものとなる。もし均衡において\(E_G=E_C=E_P\)でなければ、プレイヤー2はこの値が最も高くなる戦略(G,C,Pのどれか)に確率0を割り当てることが最適反応戦略となる(最も高くなる戦略が2つある場合は、2つに0を割り振る)。これは上記の完全混合戦略しかナッシュ均衡がないことに矛盾する。これから\(E_G=E_C=E_P\)が得られて、期待利得\(v_{n,m}\)もこれと等しくなることが分かる。これより式(2)を得る。

ナッシュ均衡において、正の確率が割り振られる純粋戦略の期待利得はすべて等しくなる説明はこちら(混合戦略なッシュ均衡の求め方)も参照。

式(2)に対して、式(1)を初期条件として用いて、\(q_G,q_C,q_P\)と\(v_{n,m}\)を求めることで、再帰的に期待利得\(v_{n,m}\)と均衡戦略を求めることができる。しかしこの方程式は\(v_{n,m}\)に関ずる非線形方程式(3次方程式)になるため、数値的に解くこととする。

なお\(q_G,q_C,q_P\)はプレイヤー2の均衡戦略であるが(ナッシュ均衡は、プレイヤー1の期待利得を考えることで、プレイヤー2の戦略が求められる、こちらを参照)、\(n\)と\(m\)を入れ替えてプレイヤー1の戦略を求める。

計算結果

まずプレイヤー1の期待利得について、基本的な確認をしてみる。

図1は、プレイヤー2のゴールまでステップ数\(m\)を横軸に取り、プレイヤー1のゴールまでのステップ数\(n\)ごとにプレイヤー1の期待利得を示したものである(\(n=1\dots,10\))。

図1:プレイヤー1の期待利得(プレイヤー1の勝つ確率と同じ)

プレイヤー1の期待利得を\(v\)とするとき、プレイヤー1の勝利確率\(p\)は
\[ p=\frac{1}{2}\left(v+1\right) \]
で与えられるので、図1はプレイヤー1が勝利確率と考えることもできる。

表1はプレイヤー1の勝利確率である。例えば自分があと1ステップ(3歩)でゴールでき、相手が2ステップ(6歩)のとき((n=1,m=2))、相手はチョキかパーで勝てば逆転勝利できる位置にあるが、自分の勝利確率は63%(2/3)、相手は37%(1/3)である。

表1:プレイヤー1の勝利確率

これらから、次のことが確認できる。

  • プレイヤー1もプレイヤー2も同じ位置にいるとき(\(n=m\))、プレイヤーの勝つ確率は同じ(期待利得は0、 勝つ確率は0.5で等しい)。
  • プレイヤー1の位置を固定すると(\(n\)のグラフを固定)、プレイヤー2の位置がゴールから遠くなればなるほど(\(m\)が増加するほど)、プレイヤー1の勝利確率は高くなり、
  • プレイヤー2の位置を固定すると(\(m\)の値を固定)、プレイヤー1の位置がゴールから遠くなればなるほど(\(n\)が増加するほど)、プレイヤー1の勝利確率は低くなる。

次に戦略について見ていこう。計算から次のようなことが分かった。

  • プレイヤー1の戦略に対し、グーとチョキを入れ替えるとプレイヤー2の戦略となる。パーの戦略は同じになる。
  • パーを出す確率は、グーやチョキよりも低い。グーとチョキのどちらが高いかは、状態によって変化する

これらはたぶん均衡を求める式を丁寧に調べると証明できるのであろうが、やっていない。

さて、図2は\(m=1\)(プレイヤー2があと1ステップでゴールするとき) の両プレイヤーの戦略を、プレイヤー1の位置\(n\)を横軸としてグラフにしたものである。このゲームの特徴がよく現れている。

図2:あと1ステップ(3歩)でプレイヤー2がゴールするとき

先に予想したとおり、2人ともあと1ステップでゴールできる場合( \(n=m=1\))では、G,C,Pを出す確率は\(1/3\)となり、普通のじゃんけんと同じになることが分かる。それ以外では、プレイヤー1はグーを出す確率が高く、プレイヤー2はチョキを出す確率が高い。プレイヤー2はあと1ステップでゴールできるので、グーよりもチョキやパーを出すことで有利にならないため、相手に2ステップ進ませることを何としても避けたい。そのためチョキを出してプレイヤー1がチョキやパーで進むことを阻止したいわけだ。プレイヤー1はそれを読み込むと、グーを出す確率を高くして、1ステップだけ進んでおこうとして、それが均衡となる。プレイヤー1の位置が2ステップのとき\(n=1,m=2\)では、それが最も顕著に現れ(プレイヤー2は1ステップでゴールできるにも関わらず、プレイヤー1に2ステップ進まれると逆転負けする)、プレイヤー1がグーを出す確率(=プレイヤー2がチョキを出す確率)は0.52にまで上昇する。

図3は\(m=5\)(プレイヤー2があと5ステップでゴールするとき) のグラフである。

図2:あと5ステップ(15歩)でプレイヤー2がゴールするとき

この例から分かるように、均衡戦略は次の2つの要因に影響される。

(1)ゴールまでの距離:プレイヤー1がゴールから離れるほど、グーを出す確率が増加しチョキを出す確率が減少する(プレイヤー2はチョキを出す確率が増加し、グーを出す確率が減少する)。 プレイヤー1がゴールから遠いとき、プレイヤー2はプレイヤー1が2ステップ進むことを避けるためチョキを出す確率を高め、それをプレイヤー1が読み込みグーを出す確率が高くなることを表している。相手がゴールより遠いときには逆転させないように1ステップづつ進ませる(自分がゴールから遠いときには1ステップづつ進む)戦略となる。同じ位置 \(n=m\) にいるときはグーとチョキを出す確率が同じになるので、基本的には勝っているときはチョキを出す確率が高く、負けているときはグーを出す確率が高くなる。

(2)奇数と偶数ステップの効果:プレイヤー1は偶数ステップではグーを出す確率が増加し、チョキを出す確率が減少する。先に見たようにプレイヤー1が残り2ステップでゴールする場合\(n=2\)、プレイヤー2はプレイヤー1が2ステップ進んで一気にゴールすることを阻止するためチョキを出す確率を高めるので、プレイヤー1はそれを読み込んでグーを出す確率を高める。これと同様の理由が再帰的に続くと考えられる。例えばプレイヤー1が残り3ステップと4ステップのときを考えると、どちらも1回ではゴールできず、少なくとも2回で勝たなければゴールできない。プレイヤー1が残り4ステップのとき、一気に2ステップ進まれると、残り1回で勝つチャンスがプレイヤー1に生まれるが、1ステップでは少なくともあと2回勝たなければダメなままである。これに対しプレイヤー1が残り3ステップのときは、1ステップ進んでも、2ステップ進んでも残り1回で勝つチャンスがプレイヤー1に生まれる。つまりプレイヤー2としては、プレイヤー1が偶数ステップのときに2ステップ進むことを阻止したいインセンティブが強くなる。それをプレイヤー1が読み込む結果だと思われる。

上記の2つの要因によって図3の戦略は解釈できると思われる。

  • \(n=m=1\)ではG,C,Pを出す確率は\(1/3\)となる。
  • \(n=m\)ではグーとチョキを出す確率が同じ。
  • \(n=m\)として、\(n,m\)を大きくすると、均衡戦略は図1の左側の利得行列のナッシュ均衡である\(2/5,2/5,1/5\)に近づくことが分かる。すなわち両者がスタート地点にいるとき、スタート地点が遠いならば「グー・チョキ・パーを2:2:1で出す」ことが均衡戦略となる。

最後の結果から、巷で言われる(?)図1の左側の利得行列の計算も、あながち間違っているわけではないと言える。

まとめ

以上、グリコ、チョコレート、パイナップルの解をゲーム理論で解析した。なおこの確率はナッシュ均衡の確率を計算したものであり、相手がナッシュ均衡に従わない場合は必勝戦略とならないことに注意したい。例えば、チョキばかり出してくる馬鹿な相手に、上記の結果のナッシュ均衡戦略で勝負するよりは、グーを出したほうが良い。

この混合戦略のナッシュ均衡は、自分がナッシュ均衡に従っているならば、相手が何を出して来ようが、均衡における自分の期待確率を同じにしていることに注目したい。つまり自分が勝っているとき(相手よりも先に進んでいるとき)は均衡に従えば、相手が何を出そうが自分の有利さをそのまま保つことができる。これに対し、自分が負けているとき(相手が先に進んでいるとき)は均衡に従うと、相手が何を出しても自分の不利さをそのまま保つような戦略になってしまっている。そこで実践的な意味では、自分が先に進んでいるときは上記の確率に従い、負けているときは相手が均衡戦略から外れ、デタラメに出すことを期待して他の戦略を用いたほうが良いだろう。上記の偶数・奇数ステップでの知見を逆手に取り、自分が偶数ステップにいるときチョキの確率を高めて、2ステップ進む確率を高めたほうが良いかもしれない。

混合戦略のナッシュ均衡が何を意味しているのかは、混合戦略の項に少し記したが、私自身も理解していないことがいくつかある。これらは機会を見て、追加していきたい。

じゃんけん研究

混合戦略ナッシュ均衡の求め方

ここでは2☓2ゲーム(プレイヤーが2人で戦略が2つ)の混合戦略のナッシュ均衡の求め方について記します。通常は最適反応戦略のグラフを書いて求めますが、ここではグラフを書かずに簡便な方法を考えていこうと思います。以下の関連投稿も参照して下さい。

2☓2ゲームの混合戦略ナッシュ均衡を求める

以下の2☓2ゲームの混合戦略のナッシュ均衡を求めてみます。

図1:例題のゲーム

まず、プレイヤー1がAを選ぶ確率を\(p\)とします(Bを選ぶ確率は\(1-p\)となります)。次に、プレイヤー2がAを選ぶ確率を\(q\)とします(Bを選ぶ確率は\(1-q\)となります)。

混合戦略をp,1-p、q,1-qで表す

さて、プレイヤー1の戦略で\(p=1\)と\(p=0\)の混合戦略は、「Aを選ぶ」「Bを選ぶ」という純粋戦略と同等なので、ここでは求めるべきものから除外します。すなわちここでは「純粋戦略ではない混合戦略のナッシュ均衡」=「すべての戦略を選ぶ確率が正である混合戦略のナッシュ均衡」を求めることとします。したがって\(0<p<1\)とします。同様にプレイヤー2に対しても\(0<q<1\)とします。

\(0<p<1\)、\(0<q<1\) のように「すべての戦略を選ぶ確率が正である混合戦略」は完全混合戦略(completely mixed strategy) と呼ばれます。

ここでプレイヤー1が戦略Aを選んだときの期待利得(利得の期待値)は
\[ q \times 5+(1-q) \times 1=4q+1 \tag{1} \]
であり、戦略Bを選んだときの期待利得(利得の期待値)は
\[ q \times 2 +(1-q) \times 3=-q+3 \tag{2} \]
です。 完全混合戦略であるためには、期待利得が等しくなければならないので(理由は後述)
\[4q+1=-q+3\]
でなければなりません。これを解いて\(q=2/5\)を得ます。

利得の期待値の計算については後ほど詳しく説明しています。

同様にプレイヤー2を考えます。 プレイヤー2が戦略Aを選んだときの期待利得(利得の期待値)は\( p \times 3+(1-p) \times 1=2p+1 \)であり、戦略Bを選んだときの期待利得(利得の期待値)は\( p \times 4 +(1-p) \times 0=4p \)です。やはり期待利得が等しくなければならないので、\(2p+1=4p\)でなければならず、これを解いて\(p=1/2\)を得ます。

以上のことより、混合戦略のナッシュ均衡は

プレイヤー1はAを\(1/2\)、Bを\(1/2\)で選び、プレイヤー2はAを\(2/5\)、Bを\(3/5\)で選ぶ (*)

となります。

このように2☓2ゲームで混合戦略のナッシュ均衡を求めるには、各プレイヤーの2つの戦略を選んだときの期待利得が等しくなるようにすれば良いです。「なぜそうなるのか?」「ナッシュ均衡における期待利得は?」「そもそも期待利得の計算って、どうするの?」について、次に考えてみます。

均衡で期待利得が等しい理由

そもそも「期待利得(利得の期待値)」からつまずいていることも多いので、プレイヤー1の期待利得について、少し詳しく説明します。各プレイヤーが\(p,q\)に従って戦略を選んだときに、戦略の組\((A,A),(A,B),(B,A),(B,B)\)が実現する確率は\(pq,p(1-q),(1-p)q,(1-p)(1-q)\)で、そのときに実現する利得は\(5,1,2,3\)です。これより混合戦略を用いたときのプレイヤー1の期待利得は
\[ pq \times 5+p(1-q) \times 1+(1-p)q \times 2+(1-p)(1-q) \times 3 \]
となります。なお前の2項を\(p\)で、後の2項を\(q\)でくくると期待利得は
\[p(-4q+1)+(1-p)(-q+3) \tag{3} \]
と書くこともできます(この式は後で使います)。

次に「プレイヤー1がAを選んだときの期待利得」です。プレイヤー1がAを選ぶ(確率ではなく確実に選ぶ)と、プレイヤー2がAを選ぶ確率は\(q\)、Bを選ぶ確率は\(1-q\)で、そのときの利得はそれぞれ1と5ですから、期待利得は式(1)のように計算できて\(4q+1\)となります。同様にプレイヤー1がBを選ぶと期待利得は式(2)のように計算できて\(-q+3\)となるわけです。

さてこれと式(3)を見比べると、式(3)は
\[ p \times(Aを選んだときの期待利得)+ (1-p) \times
(Bを選んだときの期待利得)\]
となっていることが分かります。つまり自分がA、Bを選ぶときの確率を\(p,1-p\)としたときの期待値は「期待利得の期待値」になっている訳です。

「期待利得の期待値」が、もともとの「期待値」と同じになることは「複合くじに関する公理」と呼ばれる仮定です。ここが成立しないと考える研究も存在します。

ナッシュ均衡では、与えられた\(q\)に対して、プレイヤー1は期待利得(=式(3))を最大にする確率\(p\)を選びます(最適反応戦略)。このとき\(4q+1>-q+3\)だと\(p=1\) 、\(4q+1<-q+3\)だと\(p=0\)が式(3)を最大にすることが分かります。高い期待値を与える戦略を確率1で選ぶことが自分にとっては良く、低い期待値を与える戦略にの戦略に少しでも確率を割り当てると利得は低くなってしまうのです。

しかし\(0<p<1\)でなければなりませんので、\(p=0,p=1\)ではいけません。このことから完全混合戦略であるためには、Aを選んだときの期待利得とBを選んだときの期待利得は等しくなければならず、\(4q+1=-q+3\)でなければならないのです。プレイヤー2についても同様です。

ナッシュ均衡における期待利得を求める

以上でナッシュ均衡が\(p=1/2\)、\(q=2/5\)と計算できることが分かりました。ここで\(4q+1=-q+3=A\)と置いてみると、式(3)は
\[pA+(1-p)A=A \tag{4} \]
となります。これからナッシュ均衡における期待利得は\(A\)であることが分かります。つまり混合戦略を用いたときの期待利得は、本来は式(3)に\(p,q\)の値を代入して求めなければならないのですが、ここでは\(p\)は必要なく、\(-4q+1\)か\(-q+3\)のどちらか(簡単な方)に\(q=2/5\)を代入するだけで良いことが分かります。これよりナッシュ均衡におけるプレイヤー1の期待利得は\(-q+3=13/5\)となることが分かります。同様にプレイヤー2のナッシュ均衡における期待利得は\(4p=2\)となります。

相手の利得が自分の戦略を決める

この計算方法は、解法を鵜呑みにするのではなく、その意味を考えると「本当にこれで良いのか?」と考えこんでしまいます(よね??)。この計算方法では「相手が2つの戦略を選ぶ期待利得が等しくなるように、自分の戦略が決まる」からです。つまり端的には「相手の利得が自分の戦略を決める」「自分の利得は自分の混合戦略均衡を決めるために関係ない」ように見えるからです。

図3はここまでの例題とプレイヤー2の利得は同じであり、プレイヤー1の利得が定まっていないようなゲームです。この場合でも完全混合戦略があるとすれば、それは\(p=1/2\)となります。

図3:プレイヤー1の利得が分からない

ただそれは「ナッシュ均衡でプレイヤー1が選ぶ戦略に、プレイヤー1の利得が全く関係ない」と言うわけではありません。例えば\(a=b=1,c=d=0\)では、プレイヤー1の支配戦略はAとなり、ナッシュ均衡も(A,B)となります(\(p=1,q=0\))。つまり\(a,b,c,d\)が「完全混合戦略がナッシュ均衡となるような条件」(\((a-c)(b-d)<0\)) を満たさなければなりません 。

2☓2ゲームのナッシュ均衡をすべて求める

上記の方法は2☓2ゲーム(プレイヤーが2人で戦略が2つのゲーム)の完全混合戦略のナッシュ均衡を計算する方法です。しかし、この方法ではそれ以外=「完全混合戦略ではないナッシュ均衡」は求められないため改めて注意が必要です。以下の図4の2つのゲームを見てみましょう。

図4:2種類のゲームの例

図4の左側の例は図1の例題のゲームに、純粋戦略でのナッシュ均衡の求め方に従って最適反応戦略となる利得に下線を引いた図です。これから分かるように、このゲームには両プレイヤーの利得に下線が引かれる戦略の組はありません。すなわち、このゲームには、純粋戦略のナッシュ均衡がないのです。したがってこのゲームのナッシュ均衡は既に求めた完全混合戦略のナッシュ均衡が1つあるだけになります。

これに対して、図4の右側のゲームでは(A,A)(B,B)の両プレイヤーの利得に下線が引かれています。すなわちこのゲームでは(A,A)(B,B) という2つのナッシュ均衡があります。そして、さらに完全混合戦略のナッシュ均衡が1つあるのです。ここまでの方法に従って、その均衡を求めてみましょう。プレイヤー1がAを選ぶ確率を\(p\)(Bを選ぶ確率は\(1-p\))、プレイヤー2がAを選ぶ確率を\(q\)(Bを選ぶ確率は\(1-q\))とします。

プレイヤー1が戦略Aを選んだときの期待利得は\( q \times 2+(1-q) \times 0=2q\)
、戦略Bを選んだときの期待利得は\( q \times 0 +(1-q) \times 4=-4q+4\)
です。 期待利得が等しくなければならないので\(2q=-4q+4\)であることから、\(q=2/3\)を得ます。

同様にプレイヤー2を考えます。 プレイヤー2が戦略Aを選んだときの期待利得は\( p \times 3+(1-p) \times 0=3p\)で、戦略Bでは\( p \times 0 +(1-p) \times 1=1-p \)です。やはり期待利得が等しくなければならないので、\(3p=1-p\)でなければならず、これを解いて\(p=1/4\)を得ます。

これらを総合すると図4の右側のゲームのナッシュ均衡は

(1)プレイヤー1がA、プレイヤー2がAを選ぶ。(\(p=1,q=1\)に相当する )
(2)プレイヤー1がAを1/4、Bを3/4で選び、プレイヤー2がAを2/3、Bを1/3で選ぶ。
(\(p=1/4,q=2/3\)に相当する )
(3)プレイヤー1がB,プレイヤー2がBを選ぶ。(\(p=1,q=1\)に相当する )

と3つあることになります。

2☓2ゲームのほとんどのゲーム(特殊な場合を除く)は、以下の4タイプに分けることができます。

(1)2人のプレイヤーとも、支配戦略がある(囚人のジレンマなど)
(2)1人のプレイヤーだけに支配戦略がある(合理的な豚など)
(3)プレイヤーに支配戦略がなく、純粋戦略のナッシュ均衡がある(調整ゲームチキンゲームなど。図4の右側のゲームがこれ)
(4) プレイヤーに支配戦略がなく、純粋戦略のナッシュ均衡もない(マッチングペニー、サッカーのPKのゲームなど。図1(図4左側)のゲームがこれ)

(1)と(2)には完全混合戦略のナッシュ均衡はなく、プレイヤーが支配戦略を使う純粋戦略のナッシュ均衡が1つあるだけです。ちなみにこれに対して上記の混合戦略のナッシュ均衡の求め方を用いると\(p\)や\(q\)が負になったり、1を超えたりします。上記の求め方で0や1を超える値が出たときは、支配戦略がないかもう一度チェックする必要があります。既に見たように(3)では3個、(4)では1個のナッシュ均衡があります。

したがってナッシュ均衡をすべて求めるためには(1)-(4)に留意して求める必要があります。2☓2のナッシュ均衡の解を求める、ここで述べた方法ではなく、最適反応戦略のグラフを書く方法が一般的で、その方法を使うと(1)-(4)まで包括的(?)に求めることができます。拙著ゼミナールゲーム理論入門などを参照して下さい。

すでに話したように「混合戦略まで含めると、ナッシュ均衡は必ず存在する」という定理がありますが、さらに加えて、ほとんどの場合にナッシュ均衡は奇数個であることも証明されています。「ほとんどの場合」というのは、例えば利得が全部同じ数だったりすると、あらゆる混合戦略がナッシュ均衡になったりするわけで、そういう特殊な場合を除く、ということです。「2次方程式の解は、ほとんどの場合2個である」というのと同じような意味です(重根の場合を除いている)。

まとめ

まとめると2☓2のナッシュ均衡を求めるには

STEP.1 まず純粋戦略のナッシュ均衡を求める。
STEP.2 (1)か(2)のタイプ、すなわち支配戦略がある場合は、それで終わり。完全混合戦略のナッシュ均衡はない。
STEP.3 (3)か(4)のタイプの場合は完全混合戦略のナッシュ均衡があるので、各プレイヤーが一方の戦略を選ぶ確率を\(p,q\)とそれぞれ置き、各プレイヤーが2つの純粋戦略を選んだときの期待利得を求める。
STEP.4 上記で求めた、各プレイヤーが2つの純粋戦略を選んだときの期待利得が等しくなるように\(p,q\)を定める。相手の期待利得が等しくなるように自分の混合戦略が決まることに注意する。

となります。以上、2☓2ゲームの混合戦略のナッシュ均衡の求め方について記してみました。こうしてみると、混合戦略のナッシュ均衡とは何なのか?と考える方も多いと思います。混合戦略のページに少しそれについて書きました。

注意点

  • 式(4)から分かることをもう1つ。ナッシュ均衡では、プレイヤー1はどんなpを選んでも期待利得はAになります。これはナッシュ均衡では、プレイヤー1は何を選んでも最適反応戦略(利得を最大にする戦略)になるので、果たしてナッシュ均衡戦略\((p=1/2)\)を選ぶインセンティブがあるのか?という問題が起こります。これを論じたハルサニのpurification theoremという定理があります。これは完備情報の混合戦略ナッシュ均衡は、不完備情報の純粋戦略ナッシュ均衡の極限として表現できるという定理ですが、ここでは触れていません。

参考文献

  • Harsanyi, J.C. Games with randomly disturbed payoffs: A new rationale for mixed-strategy equilibrium points. Int J Game Theory 2, 1–23 (1973). https://doi.org/10.1007/BF01737554

東京都立大学 2020ゲーム理論1 オンライン講義(2020:コロナ対応)

ゲーム理論における混合戦略

ここでは混合戦略とは何か、混合戦略のナッシュ均衡とは何かについて記していきます。計算方法は、ここではありません。必要ならば、以下も参照してみて下さい。

ナッシュ均衡のないゲーム?

戦略形ゲームの解であるナッシュ均衡について、その考え方と2人ゲームでの求め方について書きました。しかし2人の「じゃんけん」に対してナッシュ均衡を求めると、ナッシュ均衡が存在しないように見えます。

じゃんけんの利得行列(勝ちは+1、負けは-1、あいこを0としている)

ナッシュ均衡は「お互いが利得を最大にしている戦略の組」です。じゃんけんでは「相手がグーなら自分はパーが良い(利得を最大にする)」「自分がパーなら、相手はチョキが良い」「相手がチョキなら自分はグーが…」と循環してしまい、お互いが利得を最大にしている戦略の組はないことが分かります。(循環するからダメなわけではないんですけど、正確には…)

確認するために、ナッシュ均衡の求め方にしたがい最適反応戦略(利得を最大にする戦略)となる利得に下線を引くと以下の図になり、両プレイヤーの利得に共に下線が引かれている戦略の組はないことが分かります。

じゃんけんの最適反応戦略とナッシュ均衡

じゃんけんには戦略が3つありますが、戦略が2つであってもこのような(一見すると)ナッシュ均衡がないゲームはあります。以下のゲームは、その典型例として、よく用いられます。

(マッチングペニー)2人のプレイヤーAとBが、それぞれ表(Head)か裏(Tail)を選ぶ。2人が同じものを選べばAの勝ち、違うものを選べばBの勝ち。

このゲームは「1セント硬貨(ペニー)をお互いに持ち、同時に表か裏かを出す」というゲームから由来していることから、マッチングペニー(matching pennies。 penniesって複数形なんだ…)と呼ばれています。

マッチングペニー

脱線しますが、日本人だと2人で順番を決めたり、勝ち負けを決めたりするときはじゃんけんをします。あっち(欧米)だとじゃんけんがなく、そのような状況では「表か裏を選ぶ」という方法を考えるのが定番のようで、ゲーム理論をやっていると頻繁に「表」「裏」を選ぶという状況が登場します。マッチングペニーが実際に行われているかどうか、私は知らないのですが(誰か教えて下さい)、テニスの試合なんかだと最初にサーブを取るかコートを選ぶかを決めるときに、一方の選手がラケットを地面に立ててぐるぐる回して放し、もう一方が落ちるラケットの上面が表か裏かを言い当てるという方法を使います(私のようなド素人だと、ラケットの表と裏が分からなくて、そこでつまづきます)。マッチングペニーに近いですが、ラケットを回すほうは自分の意志で表か裏を選択しているわけではないので「ゲーム」ではないですね。ちなみにテニスの大きな試合( サッカー・アメフトなんかもそう)では審判がコイントスをして決めますが、これも第3者が決めているので「ゲーム」ではありません。くじと一緒です。

マッチングペニーでは、出したコインの表と裏が一致したときに、勝つプレイヤーと負けるプレイヤーをあらかじめ決めておく必要があります。これはマッチングペニーのルールがプレイヤーに対して非対称であることによります。ワタナベじゃんけんも同じで、どのような場合に誰が勝つかという、結果とプレイヤーを予め結びつけておく必要があります。戦略が2つだと対称で等確率に勝負がつくゲームは作れないのです。じゃんけんは、どのプレイヤーも勝ちの場合と負ける場合のルールが対称になっているゲーム(対称ゲーム)で、あらかじめ結果と勝者とを結びつけておく必要がありません。しかし戦略が3つ必要になります。どちらが好みでしょうか。日本人の私はじゃんけんのほうが好きですが(ラケットやペニーのような「道具」も必要なく、最初にどのようなときに誰が勝つかというプレイヤーを特定する必要もない)。じゃんけんは「あいこ」があるため勝負に時間がかかることがあります。戦略の数、必要とする道具、対称性、あいこと勝負の決定性、などを考慮するとどちらが良いかは好みで分かれるでしょう。

混合戦略

脱線してしまいましたが話を元に戻すと、マッチングペニーもじゃんけんと同様にナッシュ均衡がないように見えます。このような一見すると均衡がないゲームも、プレイヤーが確率を使って戦略や行動を選択すると考えるとナッシュ均衡が存在します。これはゲーム理論の出発点とも言える部分で、歴史的にはゲーム理論のキモと言うか核と言うか、そんな考え方なんです。

ゲーム理論では、プレイヤーが確率を用いて行動や戦略を選択することを1つの戦略とみなし、それを混合戦略(mixed strategy)と呼びます。もともと考えていた戦略を混合戦略と区別したいときは純粋戦略(pure strategy)と呼びます。純粋戦略は、確率1でそれを選ぶ混合戦略と同じと考えられるため、混合戦略は純粋戦略を含んだ考え方であると言えます(混合戦略は純粋戦略の拡張と言う方が数学的には正しいかな)。

「確率で戦略や行動を選ぶ」と言うと、「難しそうだ」「実際にそんなことあるのか」と言われそうですが、じゃんけんだと各プレイヤーが「グー・チョキ・パーを1/3ずつで選ぶ」というのが混合戦略のナッシュ均衡になります。マッチングペニーだと各プレイヤーが「表と裏を1/2ずつ選ぶ」というのがナッシュ均衡となります。そう考えると「確かに確率的に戦略を選ぶという考え方は分からないでもないな…」と思いませんか?

しかし、この混合戦略とナッシュ均衡の考え方は、なかなかの曲者で、正しく理解しにくいのです。以下では、これについて話していきます。

等確率でない場合

「確率で選ぶ」ということは「等確率で選ぶ」ことと同じではありません。以下の例を考えてみましょう。

(サッカーのPK戦のゲーム)サッカーのPK戦を簡便にしたモデルを考える。 キッカーは(キーパーから見て)ボールを左か右かのどちらかに蹴り、 キーパーは(自分から見て)左か右に飛んでゴールを阻止するとする(以下の図)。

PK戦のゲーム

これをお互いが同時に右か左かを選ぶ戦略形ゲームと考える。 キッカーとキーパーは、違う方向に飛べばゴールの成功率は高く、同じ方向に飛べば低くなる。またキッカーは左に蹴る方が得意であり、 左のほうが成功率が高い。キッカーの利得は、ゴールの成功率、キーパーの利得は失敗率(1からゴールの成功率を引いたもの)とし、各成功率は以下のような利得行列で与えられているとする。

PKゲームの利得行列

このようなゲームの解はどうなるだろう?

このゲームもナッシュ均衡を求めてみると、やはり(純粋戦略の)ナッシュ均衡はないことが分かります。そこで混合戦略のナッシュ均衡を求めると、

キッカーは右を5/8、左を3/8で選び、キーパーは右を7/8、左を1/8で選ぶ

となります。キッカーもキーパーも右と左を等確率で選ぶわけではありません。

どうやってこれを求めるのか?混合戦略のナッシュ均衡を求めることは、ゲーム理論の試験問題の定番です。いろんな大学のゲーム理論の講義の宿題や試験、さらには公務員試験などで出題されていて、ここを訪れた皆さんならやったことがあるか、もしくはそれを知りたくてここに来たのかもしれません。求め方は大切ですし、面白いのですけど、それは別に記すことにしましょう。

このページでは求め方ではなく、考え方について記していきますが、その前に、まず1つ重要な事実をお伝えします。上記のように一見するとナッシュ均衡がないように見えるじゃんけん、マッチングペニー、サッカーのPK問題でも混合戦略というものを考えるとナッシュ均衡がありました。実は

プレイヤーが何人いても、戦略がいくつあっても、混合戦略まで考えれば必ずナッシュ均衡は存在する

という数学の定理があるのです。凄い!凄すぎる!ナッシュ均衡は必ずあるんです(←ジョン・カビラさん風に読んで下さい、川平慈英さんでも可!)。これはゲーム理論において、たぶんいちばん重要な定理です。

この定理を証明した人は誰でしょう?賢明なあなたなら、それはもうお分かりだと思います。その人は、その功績を認められて1994年にノーベル経済学賞を取りました。

混合戦略のナッシュ均衡とは何なのか?

さてここでは求め方ではなく、上で求めた確率は「いったい何なんなのか?何の意味があるのか?」ということについて述べてみます。

専門家は、これについてハルサニーのpurification theorem(Harsanyi(1973))を考えると思いますが、ここではもう少し初心者向けの話をしてみます。

「何なんだと言われても、ナッシュ均衡でしょ?としか言いようがない!」というかもしれません。それでは以下の考え方は正しいでしょうか?

  • (疑問1)キッカーは右を5/8、左を3/8で選ぶことが最適で、これに従うことが一番良いのだろうか?もし実際に自分が上のようなゲームに直面し、キッカーだったら、右を5/8で蹴ると一番良いのだろうか?

この「混合戦略のナッシュ均衡の戦略はゲームの必勝戦略で、それを出すことがプレイヤーにとっては一番いいんだ!」という考え方は正しいのでしょうか?

また、必勝戦略であるかどうかの前に、

  • (疑問2)もしあなたがキッカーで5/8の確率で右に3/8の確率で蹴ろうとすると、どうやってボールを蹴るのだろうか?

という疑問もあります。疑問2は専門家には簡単なことなのでしょうが、学生に投げかけてみると、ほとんど答えられないようです。疑問1くらいだとさっぱり分かりません。

混合戦略のナッシュ均衡は求められるのに、それが何なのか分かっていないことが多い人が何と多いことか。私も成績をつける都合で宿題や試験に出しているんだということを正直に告白しなければなりません。 教員は、それに何の意味があるのか分かっていないものを、学生に求めさせていることを大いに反省しなければなりません。はい、いつか話そうと思っていました。なので、今回のこの記事は、スゴーク長くなっているのです。

まず疑問2について答えてみます。混合戦略は「確率で戦略を決定する」のですから、忠実に再現するには、何らかの「くじ」や「サイコロ」のような確率を発生させる仕組みが必要です。ゲーム理論の専門家は、これをランダムデバイス(random device)と呼びます。もし「右を5/6、左を1/6で選べ」と言われたら、「サイコロを振って1の目が出たら左、それ以外は右」を選びます。では「右を5/8、左を3/8で選べ」だと、どうすれば良いのでしょうか?このページの最後に答を記すので、皆さんで考えてみて下さい。

混合戦略のナッシュ均衡は必勝法か?

さていよいよ疑問1の「現実にゲームに直面したときに、混合戦略のナッシュ均衡に従うことは自分にとって最適なのか」ということについて考えてみます。実はこれはよく分からないんです。状況は零和ゲームか、非零和ゲームかで変わってきます。しかし私は「ざっくり言うと、必ずしもそうではない」と考えています。

それはまずじゃんけんについて考えると、分かりやすくなります。

2人じゃんけんのナッシュ均衡の戦略は「グー・チョキ・パーを1/3ずつ出す」という戦略になります。お互いに、この戦略を選んでいると、勝ち・負け・引き分けの確率は共にに1/3となります。

では仮に相手が「グーしか出さないやつ」で、そしてそれをあなたが知っていたら、あなたはどうします?このときはパーを出すことが最適です。当たり前です。そして、そうすれば、あなたは100%勝つことができます。しかし、もしあなたがナッシュ均衡の戦略である「グー・チョキ・パーを1/3ずつ出す」という戦略を選ぶとどうなるでしょう。このとき、あなたの勝つ確率は1/3になってしまいます。相手がグーしか出さないやつなのに、 あなたと相手の勝つ確率は、同じになってしまいます!

じゃんけんにおいて「グー・チョキ・パーを1/3ずつ出す」ということは最適戦略ではありません。これはナッシュ均衡の戦略でしかないのです。よくナッシュ均衡の戦略を「最適戦略」と書いている文章を見かけますが(学会発表などでもよく見られます…実は自分もそう書いてしまうことがあるのですが)、「最適」という言葉は相手の戦略が所与の場合でしか使えません。最適戦略と書かないで下さい、均衡の戦略と書いて下さい。

で?結局のところ「何なんだと言われても、ナッシュ均衡でしょ?としか言いようがない」っという所に戻って来てしまいます。つまり「混合戦略のナッシュ均衡は何を意味しているか」という問題は、そもそもの「ナッシュ均衡とは何か」という問題に立ち返ることになります。

ゲーム理論のナッシュ均衡には、いくつかの解釈があります。1つ目は「合理的なプレイヤーが、お互いがよく考えて行動を選択するとナッシュ均衡になるだろう」という考え方(伝統的なゲーム理論、合理的プレイヤーのゲーム理論)、2つ目は「プレイヤーの中で高い利得を獲得したプレイヤーだけが生き残り、そうでないプレイヤーが淘汰されるような環境で生き残っていく戦略はナッシュ均衡になるだろう」という考え方(進化ゲーム的解釈)。他に「第3者がプレイヤーにそれを推薦すると、プレイヤーはそれを選ぶだろう。それによって第3者は、自分やプレイヤー達を良い結果に導くことができる、と言う考え方もあると思いますが(メカニズムデザインなど)、あまり中心的ではないので、ここでは1つ目と2つ目の考え方に立ってみます。

1つ目と2つ目の の立場に立っても、ナッシュ均衡の戦略とは「あなたはそうすると良い、これが必勝法だ」というよりは、むしろ「プレイヤーは達はそう行動するだろうという予測」を述べているのに近いはずです。

混合戦略は確率的に行動を選択する戦略なので「プレイヤーは達はそう行動するだろうという予測」 と言っても、 1回のゲームの結果では当たっているかどうかは分かりません。サイコロで1の目が出る確率は1/6ですが、1回だけサイコロを振って出た目を見ても、その予測が正しいかどうか分からないのと同じことですよね。しかし何回も同じようなゲームが試行された場合、ナッシュ均衡の予測が当たっているかどうかを検証することができます。これについては

  • 実験経済学における混合戦略の実験
  • テニスやサッカーなどのスポーツの試合における実証

などがあり、いずれも混合戦略による予測は、それほど悪くはないという結果が導かれています。

まとめ

うーんかなり疲れてきたので、このへんで終わりにします。まとめると

  • ナッシュ均衡がないように見えるゲームも、混合戦略のナッシュ均衡がある。必ずある。それを証明したすごい人がいる。
  • 混合戦略のナッシュ均衡は最適戦略ではない。あくまでも均衡である。
  • ナッシュ均衡は「そのようにプレイすることが良い」とは必ずしも言っておらず(注)、「人々はナッシュ均衡のようにプレイするだろう」と言っている。

そうは言ってもゲームにおいて「勝つために混合戦略のナッシュ均衡をうまく活用」する方法はあるはずです。 これについては、また別の機会に考えてみます。

混合戦略については、どのゲーム理論のテキストにも載っていますが、それが一体何なんだということについて書いてある本は、ほとんどないように見えます。この混合戦略のナッシュ均衡の解釈はかなり難しいからです。しかし東大の神取道宏先生は、一般向けの本などで(例えば神取(2014))このことについて言及されていて、さすがだなーと思います。

なお3/8で右、5/8で左に蹴るには、コインを3枚投げて、1枚だけ表が出たら右、それ以外(2枚表が出るか、全部表が出るか、全部裏が出る)だったら左に蹴るというのが正解です。「8本のあみだくじを引く」「八面体のサイコロを使う」なども正解でしょう。

注意点

ゲーム理論の研究者間だと混合戦略のナッシュ均衡は「ゲームの情報に僅かに不完備性があるゲームの純粋戦略均衡を考え、その不完備性がゼロに近づいたときの極限における均衡」と考えることもあります(Harsanyi (1973))。初心者向けのここではそれについては触れませんでした。

参考文献

  • 神取道宏 (2014)、ミクロ経済学の力、日本評論社。
  • Harsanyi, J. C.(1973) Games with randomly disturbed payoffs: A new rationale for mixed-strategy equilibrium points. Int J Game Theory 2, 1–23 . https://doi.org/10.1007/BF01737554

東京都立大学 2020ゲーム理論1 オンライン講義(2020:コロナ対応)

チキンゲーム

チキンゲーム(chicken game)は、2人のプレイヤーがそれぞれ「強気(Bull)」と「弱気(chicken)」のどちらかを選び
(1)相手が「弱気」なら、自分は「強気」の方が「弱気」より良い
(2)しかし両方が「強気」を選ぶと、2人にとって最悪な結果となる
というゲームです。

チキンゲームの例

以下の例を考えてみます。

(チキンゲームの例)2人のプレイヤー1と2はこれから共同でプロジェクトを行う予定であり、契約の前に獲得予定の利益100万円の分配について交渉をしている。2人はそれぞれ「強硬」か「妥協」のどちらかを選ぶ。両方が妥協すれば50万円ずつ折半となるが、一方が「強硬」に出て一方が「妥協」すると、強硬に出た方は75万、妥協した方は25万と利益を分ける。両方が強硬に出ると交渉は決裂してプロジェクトは行われず、双方の利益は0になる。

この状況を利得行列にすると、以下のようになります。

チキンゲームの例(100万円を分ける交渉)

この状況では、各プレイヤー(1と2)はそれぞれ
(1)相手が妥協を選ぶなら、自分は妥協より強硬が良い
(2)両方が強硬を選ぶなら二人にとって最悪な結果となる
ことが分かります。これがチキンゲームです。

チキンゲームの解

チキンゲームの条件(2)は以下の(2*)と(3)ように書き直せるため、チキンゲームは以下の3条件に書き直すことができます。

(1)相手が「弱気」なら、自分は「強気」のほうが「弱気」より良い
(2*)相手が「強気」なら、自分は「弱気」のほうが「強気」より良い
(3)両方が「強気」より、両方が「弱気」のほうが2人にとって良い

(1)と(2*)からこのゲームの解(ナッシュ均衡)は、

一方のプレイヤーが「強気」を選び、一方のプレイヤーが「弱気」を選ぶ

であることが分かります。上述の100万円を分ける交渉の例だと

(A)プレイヤー1が「強気」、プレイヤー2が「弱気」を選ぶ
(B)プレイヤー1が「弱気」、プレイヤー2が「強気」を選ぶ

という2つの解が存在します(実は他に確率で選択を行う混合戦略のナッシュ均衡が1つある)。実際にナッシュ均衡の求め方に従って、利得に下線を引くと以下の図となり、両プレイヤーの利得に下線が引いてある戦略の組は、上記の(A)と(B)であることが分かります。

チキンゲームのナッシュ均衡

この(A)と(B)のナッシュ均衡のどちらが解になるのか、という問題は調整ゲームと同じで難しい問題です。調整ゲームと同じように、それまでの慣習などで「フォーカルポイント」が存在すればそれが解になりえますが、そのようなものがない場合はナッシュ均衡が実現するかどうかも難しい可能性があります。(調整ゲームとの関連は後述)

囚人のジレンマと間違えないで!

よくチキンゲームと囚人ジレンマは混同されます。上記の条件(1)(2*)(3)を見ると、(1)と(3)は囚人のジレンマと同じです。囚人のジレンマを

相手が協力するならば、自分は協力しない方が良い。しかし2人が共に協力しないよりは、2人が共に協力したほうが良い。

とだけ説明すると、これは囚人のジレンマか、チキンゲームか分かりません(相手が協力しないときに、自分は協力したほうが良いのか、協力しないほうが良いのかが分からないですよ)。囚人のジレンマと混同しないように注意しましょう。

調整ゲームとの関連は?

既に見たようにチキンゲームは調整ゲームと同じ構造を持っているようにも見えます。上述の100万円を分ける交渉において、各プレイヤーはAかBの「ラベル」を選ぶこととし、プレイヤー1はAならば「強気」をBならば「弱気」を選ぶことを意味しているとし、プレイヤー2はAならば「弱気」をBならば「強気」を選ぶことを意味しているとし、ゲームを置き換えるとしましょう。このゲームは以下のような利得行列に書き換えることができます。

調整ゲームに書き換えられたチキンゲーム

このゲームは、相手と同じものを選んだほうが良い「調整ゲーム」であることが分かります。チキンゲームはこのように「2人だけの」「1回だけの」ゲームだと考えれば広義の調整ゲームであるとみなすことができ、分析上は区別する必要はありません。

しかしゲーム理論においては、
*多人数のプレイヤーがいて、各プレイヤーは「強気」か「弱気」のどちらかを選ぶようなプレイヤーであるとする(戦略がある程度「固定」されている)。
*それらのプレイヤーが、2人ずつ出会ってゲームを行う
*プレイヤーの戦略は「進化」や「学習」によって更新される
と考える文脈(進化と学習のゲーム理論)もあります。この枠組みでは、上記のラベルの入れ替えはできません。この文脈では、チキンゲームと調整ゲームは異なるものと考えられます。実際に多くの進化や学習のゲームでは、調整ゲームはすべてのプレイヤーが同じ行動を選ぶ(上述のAとBを選ぶゲームでは全員がAを選ぶか、全員がBを選ぶかという結果になる)ことが解になるのに対し、チキンゲームはプレイヤーが棲み分けを行う(上述のチキンゲームでは、強気と弱気を選ぶプレイヤーが50%ずつに分かれる)ことが解になります。

このような進化や学習のようなモデルでは、チキンゲームは調整ゲームよりはむしろ混雑ゲームと似た構造になっていると考えられます。

東京都立大学 2020ゲーム理論1 オンライン講義(2020:コロナ対応)

調整ゲーム

調整ゲームはコーディネーションゲーム(coordination game)の翻訳で、協調ゲームと訳されることもあります。ざっくり言うと「他人と同じ行動を選ぶことが良い」ようなゲームです。結果となるナッシュ均衡は「全員が同じ行動を選ぶ」となるので(確率を用いる混合戦略を除く)、結果の候補が複数あることになります(複数均衡)。

女と男の戦い

ゲーム理論で最初に習う2人調整ゲームは、 以下のストーリーで表される女と男の戦い(battle of sexes)です(変な名前!でも昔は「両性の戦い」と訳されていました。これだとさらに意味不明です)。

アリスと文太は、禅寺かショッピングセンターに行く。2人は相手の行動を知らずに、どちらに行くかを選ぶ。アリスと文太は、お互いが好意を抱いているので同じ場所を選べば利得1を獲得し、さらにそれが自分が好きな場所ならば利得にもう1点が加わり2になる。違う場所を選んでしまうと(たとえ好きな場所に行ったとしても)利得は0である。

「女と男がいて、お互い同じ場所に行きたい。できれば自分の行きたいところがいい!」というそれだけのゲームです。男女が武闘しているわけではありません。この状況を利得行列にすると、以下のようになります。

女と男の戦い(battle of sexes)

この状況では、各プレイヤー(アリスと文太)はそれぞれ
(1)相手が禅を選ぶなら自分も禅を選ぶほうが良く
(2)相手がショッピングを選ぶなら、自分もショッピングを選んだほうが良い
となり、「相手と同じ行動を選ぶことが良い」となります。これが調整ゲームです。

調整ゲームの例

  • どのSNSに参加するか、という問題。自分の友人が皆んなFaceBookを選んでいるならばFBを、インスタグラムを選んでいるならインスタを選ぶことが良い。このように商品に正の外部性(自分が購入する財から得る効用は、他の消費者がそれを多く選んでいるほど高くなる)があるときの消費者の選択は調整ゲームになります。
  • 技術規格のデファクトスタンダード問題。かつてビデオデッキの開発において、各企業はVHS方式とベータ方式のどちらの規格を選ぶかという問題に直面しました。企業の選択は、多くの企業が選択するものと同じ規格を選択したほうが有利になります(wikipedia デファクトスタンダード
  • 同窓会の参加。皆んなが参加するならば、自分も参加したほうが良いけど、皆んなが参加しないなら、自分も参加しないほうが良い。
  • 右側通行か左側通行か。細い道を車ですれ違うとき、右に避けるか左に避けるか。お互いに右か左か同じルールを選ばないと衝突してしまう。

調整ゲームのバリエーション

先ほどの「女と男の戦い」では、相手と同じ行動を選ぶことが良いわけですが、各プレイヤーは、どの結果が最良であるかが異なっています。アリスにとっては2人が禅を選ぶことが、文太には2人がショッピングを選ぶことが良いわけです。このような調整ゲームは非対称(asymmetric)であると言われます。これに対して「どの結果でも、2人が会えさえすれば同じ(1点)」のように、結果に差がなく、行動が一致さえすれば良いゲームは対称(symmetric)な調整ゲーム、純粋調整ゲーム(pure coordination game)、またはマッチングゲーム(matching game)と呼ばれます(Camerar 2003)。

2人とも買い物が好きで、禅寺で会えれば1点、ショッピング・センターで会えれば2点、のようなゲームも考えられます。このゲームでは、行動が一致しないより一致したほうが良いのですが、一致したときに皆にとって利得が高い場合と低い場合があります。このようなゲームには、定着した呼び名はありません。ここではTremblay and Horton(2012)に従いパレート調整ゲーム(Pareto coordination game)と呼んでおきます。

調整ゲームのバリエーション

調整ゲームの解

調整ゲームでは、すべてのプレイヤーが同じ行動を選択することがゲームの解であるナッシュ均衡になります(他に確率を用いて選択を行う混合戦略のナッシュ均衡もあります)。例えば上述の女と男の戦いでは

(A)アリスも文太も禅寺に行く
(B)アリスも文太もショッピングに行く

という2つのナッシュ均衡があります(他に混合戦略のナッシュ均衡がある⇒最後の「注意点」を参照せよ)。実際にナッシュ均衡の求め方にしたがって利得に下線を引くと以下の図となり、両プレイヤーの利得に下線が引いてある戦略の組は、上記の(A)と(B)であることが分かります。

女と男の戦いのナッシュ均衡

このように調整ゲームでは複数のナッシュ均衡が存在し、その中でどれを起こりうる結果である「ゲームの解」とするのか、という問題が起きます。この問題は均衡選択の問題と呼ばれ、ゲーム理論の大きな研究テーマです。

このときその中の1つのナッシュ均衡が起きるとすべてのプレイヤーが共通な認識で予測できるような理由があるならば、それは解となりえます。このような皆が共通して結果として予測できるような点はフォーカルポイントと呼ばれます(Schelling (1960))。フォーカルポイントは、「社会慣習」や「これまで繰り返しプレイされてきて培われた経験」などによって形成されると言えます。

例えば上記の男と女の戦いでは、2人はいつも禅に行くことになっている(という慣習や経験があれば、2人は迷うことなく禅を選ぶでしょう。また、そのような経験がなくても「レディファースト」 (アリスに文太が譲る)という慣習があれば、やはり2人は禅を選ぶことになります。文太は、本当は2人でショッピングに行ったほうが良いのですが、アリスが禅に行くと予測するなら、ショッピングよりは禅が良い選択であり、アリスも文太が禅に行くと予測できるなら禅に行くことが良い選択です。つまりナッシュ均衡の定義である 「相手がそのナッシュ均衡の行動を選ぶなら、自分もそのナッシュ均衡の行動を選ぶことが一番良い」という条件を満たすことになります。

これに対して、上記のように2人が共通して予測できるフォーカルポイントがなければ、ナッシュ均衡は実現できるとは限りません。上記のようなゲームを実験室でやらせるとお互いが異なる行動を選び0点を食らってしまう結果も多く見られます。私も講義中にこの実験をやらせてみますが、うまくコーディネイトできるときもあれば、そうでない場合も多いです。うまくコーディネイトできない場合には、(当然ですが) 次の2つのパターンがあります:
・お互いに、自分が高い得点(2点)を選び合ってしまう。アリスが禅を、文太がショッピングを選び、お互いに0点を食らってしまう。
・お互いに、相手に高い得点を取らせようと譲ってしまう。アリスがショッピングを、文太が禅を選び、お互いに0点を食らってしまう。(私は「賢者の贈り物」パターンと呼んでいます。)

パレート調整ゲームでは、一般的にはプレイヤーにとって利得が高い<良い>ナッシュ均衡(パレート優位な均衡と呼ばれる) が望ましく、単純に考えるとそれが実現されると予想されますが、何らかの理由で両者にとって利得が低い<悪い>ナッシュ均衡が実現することも、十分あり得ます。先ほどの例2だと、2人ともショッピングに行くことで利得2が達成できるためこれが<良い>ナッシュ均衡ですが、例えば2人とも毎週毎週ずーっと禅寺に行っていることが定着していて、「相手は禅寺に行く」「相手は自分も禅寺に行くと予想するだろう」と考えれば(2人ともショッピングに行くほうが楽しいと分かっていても)禅寺に行くと考えられます。

調整ゲームにおいて、ナッシュ均衡が実現しない問題、ナッシュ均衡が実現してもパレート優位なナッシュ均衡が実現しない問題は、調整の失敗(coordination failure)と呼ばれます。

フォーカルポイントの例

単純なマッチングゲームでは、さまざまなフォーカルポイントがあると予想されますSchelling(1960)は、以下のようなゲームを(インフォーマルに)実験したようです。

  • 表(head)か裏(tail)のどちらかを選べ。2人が同じものを選んだら賞金をあげよう。
  • 好きな正の番号を選べ。2人が同じものを選んだら賞金をあげよう。
  • ニューヨークのどこかで待ち合わせをする。どこで待ち合わせをするか選べ。

何を選んでも良いのですが、お互いに同じものを選ぶと良いので「調整ゲーム」であることが分かります。賞金に差もなく個人で選ぶと良いものに違いもないので、マッチングゲームですね。

Schelling(1960)によると最初のゲームでは42人中36人がheadを、2番めのゲームでは40%が「1」を選んだといいいます。3番めの質問では多数がGrand Central StationのInformation boothだとされています。

Mehta, Starmer and Sugden (1994)は、このような実験を精緻に行っています。この研究では被験者は2つのグループに分けられ、1つのグループC (Coordination)では「(ランダムに選ばれた)相手と同じものを選んだら賞金を与える」とされ、もう1つのグループP(Picking)では「何を選んでも賞金を与えるので、好きなものを選べ」としています。上記の最初の質問では、グループCでは87%、グループPでは76%がheadを選びそれほど差がないのに対して、2番めの質問では、グループCで選ばれたのは「1」が40%に選ばれて一番多く(「7」が2番めで14%)、グループPでは「7」が一番多く11%になっています。このことからある種の質問に対して、「自分が好きなもの」を選ぶのではなく「相手と同じものを選ぶためには何が良いか」を考えてそれを選ぶというフォーカルポイントが存在するということが分かります。

SchellingやMehta達は言及していないのですが、実験結果のデータを見て私が感じたのは「皆が同じものを選ぶと賞金をあげる」と言っているのに、自分が好きな数や場所を選ぶ被験者は、少数ながら必ずいるんだな…ということです。ルールが理解できていないのか、それとも何か意図があるのか.「フォーカルポイントに従う」という行動は、「大勢」や「傾向」ではありますが、それに逆らう(理解できない?従わない?)個の存在も無視できず、それはやはり「少数」や「個性」や「多様性」と言う社会科学の重要なテーマに繋がるのだな、と思いました。

注意点

  • ここでは2人ゲームと多人数のゲームを曖昧に扱ってきましたが、厳密には分けて考えることが必要です。
  • ここでは確率を使わない行動の選択(純粋戦略)のみを考えましたが、調整ゲームには各プレイヤーが確率を使って行動を選択する混合戦略を用いたナッシュ均衡もあります。例えば女と男の戦いの例だと「アリスは禅を2/3、ショッピングを1/3で選び、文太は禅を1/3、ショッピングを2/3で選ぶ」というナッシュ均衡があります。例1のマッチングゲームだと「アリスも文太も、禅とショッピングを1/2ずつ選ぶ」というナッシュ均衡があります。
  • 相手と異なる行動を選ぶことが良いゲーム(チキンゲーム・混雑ゲーム)も広義の調整ゲームとみなされる場合があります。これはゲームの文脈を1回限りの2人のゲームと見做すか、多人数で長期間に渡って行われるゲームと考えるかで異なってきます。
  • 調整ゲームにおいて「複数の均衡の中でどれが起きるか」という問題は、ゲーム理論における均衡選択という理論によって分析されており、リスク支配という概念によって起きる結果が選ばれます。

参考文献

  • Camerar (2003), Behavioral Game Theory: Experiments in Strategic Interaction, Princeton Univercity Press.
  • Mehta, Starmer, Sugden (1994), The nature of salience: An experimental investigation of pure coordination games, The American Economic Review, Vol.84, No.3, pp.658-673.
  • Schelling(1960), The strategy of conflict, Harvard Univercity Press.
  • Tremblay and Tremblay (2012), New Perspectives on Industrial Organization: With Contributions from Behavioral Economics and Game Theory, Springer.

以下も参考にしてください。

東京都立大学 2020ゲーム理論1 オンライン講義(2020:コロナ対応)

クールノー競争とベルトラン競争関連のページ

クールノー競争とベルトラン競争に関して来られる方が多いので、関連する資料をまとめておきます。

初歩から学ぶゲーム理論-web講義:関連ページ

オンライン講義

2020年東京都立大学「ゲーム理論1」オンライン講義(youtube):コロナ対応

講義資料(ゼミナールゲーム理論入門:第5章)

首都大学東京「ゲーム理論1」の講義資料から、テキストである「ゼミナールゲーム理論入門」の第5章講義する部分のスライドです。テキストの内容に沿っています。クールノー競争、ベルトラン競争、シュタッケルベルグ競争に相当する部分です。
数値例と演習になります。文字式による一般的な計算はORセミナーのスライドのほうがいいです。

講義資料(ORセミナー)

「技術者のためのゲーム理論の基礎(2)-初歩から学ぶクールノー競争とベルトラン競争」スライド

  • 2015年のORセミナーでの講演を修正したものです。理系の技術者を対象にクールノー競争やベルトラン競争を講義し、そこから経営戦略論や産業組織論を学ぶことにつなげようというねらいです。ORセミナー2014年「技術者のためのゲーム理論の基礎(1)」のゲーム理論入門はこちらにあります。

クールノー競争とベルトラン競争入門(4):図と最適反応関数で理解するクールノー競争

クールノー競争の価格・生産量と社会的総余剰では、2社のクールノー競争におけるクールノー均衡を求める方法を説明しました。ここではそれを「最適反応曲線」(反応曲線、最適反応関数)と呼ばれる図で説明し、ナッシュ均衡との関連をより明確にします。

モデルの設定(再掲)

クールノー競争の価格・生産量と社会的総余剰で説明した設定を再掲します。そこから読んでいる方は、ここは飛ばして構いません。

  • 同じ製品を販売している企業AとB。
  • AとBの生産量をそれぞれ\(x_A,x_B\)とする。
  • 市場全体の生産量を\(x=x_A+x_B\)とし、その価格\(p\)は$$p=a-bx$$で与えられるとする。
  • 製品1単位の費用(限界費用)はAもBも\(c\)で同じとする。
  • 企業Aの利益を\(\pi_A\)とおく。$$\pi_A=px_A-cx_A$$。
  • 企業Aの利益\(\pi_A\)を最大にする\(x_A\)を考える。\(p=a-bx\)を代入し、\(x=x_A+x_B\)に注意すると\[ \begin{align} \pi_A &=\{a-b(x_A+x_B)\}x_A-cx_A\\&=-bx_A^2-bx_Ax_B+(a-c)x_A \tag{1} \end{align}\]とる。
  • 式(1)を最大にする\(x_A\)を求めるため、\(x_A\)で微分して0になるところを求める。(1)を\(x_A\)で微分すると、\(-2bx_A-bx_B+(a-c)\)。したがって\[-2bx_A-bx_B+(a-c)=0\]を解けば良く、これより\[x_A=-\frac{1}{2}x_B+\frac{a-c}{2b} \tag{2}\]となる。
  • 企業Bの利益を\(\pi_B\)とおく。$$\pi_B=px_B-cx_B$$。
  • 企業Bの利益\(\pi_B\)を最大にする\(x_B\)を求めると、\[x_B=-\frac{1}{2}x_A+\frac{a-c}{2b} \tag{3}\]となる。
  • 式(2)と式(3)を、それぞれ「企業Aの最適反応関数」「企業Bの最適反応関数」と呼びます。
  • 式(2)は企業Bの生産量\(x_B)\が与えられたときに、企業Aの利益を最大にする企業Aの生産量を表しています。
  • 式(3)は企業Aの生産量\(x_A)\が与えられたときに、企業Bの利益を最大にする企業Bの生産量を表しています。

最適反応関数を図で書く-最適反応曲線

上記の最適反応関数を横軸に(x_A)、縦軸に(x_B)にした図(グラフ)に描いてみます。まず式(3)の企業Bの最適反応関数から考えてみます(⇒なぜなら、左辺は縦軸、右辺は横軸のグラフに慣れている人が多いからです)。式(3)のグラフを書いてみると、以下のようになります。

企業Bの最適反応曲線

この式は切片が\(\frac{a-c}{2}\}で、傾きが-1/2の右下がりの直線になります。これは企業Aの生産量が与えられると、そのとき企業Bの利益が最大になる生産量がいくつであるかを示す曲線になるわけです。企業Bは、もし企業Aの生産量が決まれば、自分がもっとも利益が高くなる生産量が分かるわけですが、企業Aの生産量は決まっていません。そこでこれに式(2)の企業Aの最適反応曲線を描き、重ねてみます。

 

企業Aと企業Bの最適反応曲線

企業Aは、企業Bと縦軸と横軸が逆になりますね。切片と傾きは同じです。企業Aは、もし企業Bの生産量が決まれば、自分の利益を最大にする生産量が分かるわけですが、企業Bの生産量は決まっていません。

企業Bの生産量が決まらないと企業Aの生産量が決まらず、企業Aの生産量が決まらないと企業Bの生産量が決まらない。そこで「お互いが最適反応となる生産量の組」を選び合うことが答となると考えます。これがナッシュ均衡、またはクールノー均衡(またはクールノー=ナッシュ均衡)と呼ばれるものです。

ナッシュ均衡は20世紀半ばにゲーム理論で考えられたものですが、寡占市場の分析に限ると、それより100年以上も前にクールノーが上記の解を考えていたことによるため、このように呼ばれます。

お互いが最適反応となる生産量の組は、両方の直線が交わった点です(次の図)。この点は、式(2)と式(3)の連立方程式を解くことによって求められます。これを求めると、\[x_A=x_B=\frac{a-c}{3}\]となります。

 

クールノー均衡

以下も参考にして下さい。