ナッシュ均衡の求め方:2人ゲームの利得行列の場合

ここではナッシュ均衡を求める方法について.「プレイヤーが2人で混合戦略(確率を用いる戦略)を考えない場合」について説明します.ゲーム理論の基本中の基本と言えます.(クールノー均衡の求め方はこちら.ナッシュ均衡とは何かはこちら,ナッシュ均衡の概念を理解するおけいこはこちら

ナッシュ均衡の求め方

ナッシュ均衡は「すべてのプレイヤーが最適反応戦略(利得が最も高くなる戦略)を選び合う戦略の組み合わせ」ですから,以下の方法で求めることができます.

  • STEP1 プレイヤー1の立場で考える.
    • 相手(プレイヤー2)のすべての戦略に対して,プレイヤー1がもっとも利得が高くなる戦略をチェックする(プレイヤー1の最適反応戦略).ここでは利得に下線を引く.
  • STEP2 プレイヤー1の立場でチェックが終わったら,プレイヤー2の立場で考える.
    • 相手(プレイヤー1)のすべての戦略に対して,プレイヤー2がもっとも利得が高くなる戦略をチェックする(プレイヤー2の最適反応戦略).ここでは利得に下線を引く.
  • STEP3 すべてのチェックが終わったら,両プレイヤーの利得に下線が引かれているのがナッシュ均衡.(利得ではなく,戦略の組であることに注意!)

例題

以下の利得行列でナッシュ均衡を求めてみましょう.

ナッシュ均衡を求めてみよう

今回は,ナッシュ均衡を求める手順を習得することが目的なので,ストーリーは特につけずに,単なる記号で利得行列を考えます.利得行列の読み方が不安,分からないって方は,こちらをご覧ください.

STEP1 まず,プレイヤー1の立場で考えます.相手(プレイヤー2)のすべての戦略に対して,プレイヤー1がもっとも利得が高くなる戦略(最適反応戦略)をチェックし,利得の下に下線を引いて行きます.

1.1 プレイヤー2がLという戦略を選んだ場合を考えます.プレイヤー1はTを選べば利得3,Bを選べば利得2です.したがってプレイヤー1はTを選びます(TがLに対する最適反応戦略).そこでTを選んだ時の利得3に下線を引きます.

プレイヤー2のLに対するプレイヤー1の最適反応戦略はT

1.2 プレイヤー2がMという戦略を選んだら?プレイヤー1はTを選べば利得0,Bを選べば利得1です.したがってプレイヤー1はBを選びます(BがMに対する最適反応戦略).そこでBの利得1に下線を引きます.

プレイヤー2のMに対するプレイヤー1の最適反応戦略はB

1.3 最後にプレイヤー2がRという戦略を選んだ場合を考えます.プレイヤー1はTを選んでも,Bを選んでも利得は2で同じです.この場合はTとBの利得2の両方に下線を引きます( TもBもRに対する最適反応戦略).

プレイヤー2のRに対するプレイヤー1の最適反応戦略はTとB

STEP2 プレイヤー1に対する検討が終わったので,次にプレイヤー2の立場で考えます.相手(プレイヤー1)のすべての戦略に対して,プレイヤー2の利得がもっとも高くなる戦略(最適反応戦略)をチェックし,利得に下線を引いて行きます.

2.1 プレイヤー1がTという戦略を選んだ場合を考えます.プレイヤー2はLを選べば利得4,Mを選べば利得2,Rを選べば利得0です.したがってプレイヤー2はLを選びます(LがTに対する最適反応戦略).そこでLの利得4に下線を引きます.

プレイヤー1のTに対するプレイヤー2の最適反応戦略はL

2.2 最後にプレイヤー1がBという戦略を選んだ場合を考えます.プレイヤー2はLを選べば利得2,Mを選べば利得3,Rを選べば利得9です.したがってプレイヤー2はRを選びます(RがBに対する最適反応戦略).そこでRの利得9の下に線を引きます.

プレイヤー1のBに対するプレイヤー2の最適反応戦略はR

STEP3これでプレイヤー1とプレイヤー2のすべてのチェックが終わりました.プレイヤーの両方の利得に下線が引かれている戦略の組がナッシュ均衡です!「

ナッシュ均衡は(T,L)と(B,R)

ナッシュ均衡は「プレイヤー1はTを選び,プレイヤー2はLを選ぶ」「プレイヤー1はBを選び,プレイヤー2はRを選ぶ」の2つです.このようにナッシュ均衡は複数出てくる場合があります(これが悩みの種).これを(T,L)と(B,R)のように,ベクトルのように書く場合もあります.

ナッシュ均衡は「戦略の組 (profile of strategies)」なので,戦略の組として答えます.「ナッシュ均衡は(3,4)と(2,9)です」などと答えては間違いです.それは利得の組ですから.「Tがナッシュ均衡」などと答えても間違いです.Tはプレイヤー1の戦略(a strategy of player 1)です.戦略の組み合わせではありません.

ナッシュ均衡:演習(1)

利得行列や数式を用いずにナッシュ均衡を理解する

ゲーム理論の解はナッシュ均衡(詳しくはこちらで説明しました)「ゲーム理論が分かった!」と思えるためには,ナッシュ均衡が理解できていなければなりません.でもよくあるゲーム理論の教え方では,ナッシュ均衡は利得行列を使って説明されるため,プレイヤーの利得が数式や数値で表されていたり,少なくとも表で与えられてなければ,ナッシュ均衡が求められないような気がします.

利得行列からナッシュ均衡を求める方法はこちら(ナッシュ均衡の求め方:2人ゲームの利得行列の場合).

しかし,それは正しいナッシュ均衡の理解ではありません.ここでは,数式や表を用いないいくつかの問題でナッシュ均衡を理解していきましょう.

まずナッシュ均衡の定義をおさらいしましょう.ナッシュ均衡とは,

どのプレイヤーも,他のプレイヤーがそのナッシュ均衡の戦略を選んでいるならば,自分はそのナッシュ均衡の戦略を選ぶことが利得がもっとも高くなる.

です.つまり,

どのプレイヤーも,他のプレイヤーがそのナッシュ均衡の戦略を選んでいるならば,自分はそのナッシュ均衡の戦略以外を選ぶと,利得が同じか低くなる(高くなることはない)

ということです.この「同じか低くなる」と言うのは1つのポイントです.相手の戦略に対して利得が最大になる戦略が1つならば「低くなる」でいいのですが,最大になる戦略が<同点>で2つ以上あるときは, 他の戦略でも利得は低くなるとは限らず,同点になることもあります.

ここで「利得が高くなる」と言うのは,プレイヤーにとって「良い」とか「好ましい」ということです.

2人ゲームの例

2人ゲームで練習してみましょう.なお以下では確率で戦略を選ぶ「混合戦略」は考えません.

練習1:アリスと文太は,禅寺かショッピングモールへ行く.アリスは文太の行動に関わらず禅寺に行くほうが,ショッピングモールに行くよりも絶対に良いと考えている.その中でどちらに行ったときも,どちらかと言えば文太に会えないよりは会える方が良いと考えている.文太はどちらに行くかよりも,アリスに会えることが会えないことより絶対に良いと考えている.その中で会えたときも会えないときも,どちらかと言えばショッピングモールのほうが禅寺よりも良い.以下から,ナッシュ均衡を選べ.複数あるときはすべて選び,ないときは「なし」と答えよ.
(A)2人とも禅寺へ行く
(B)アリスは禅寺へ,文太はショッピングモールへ行く
(C)アリスはショピングモールへ,文太は禅寺へ行く
(D)2人ともショッピングモールへ行く

正解は(A).(A)では,どちらのプレイヤーも,自分だけが行動を変えると利得が小さくなるのでナッシュ均衡です.(B)では文太は禅寺へ行ったほうが利得が高くなりますし,(C)と(D)では,アリスは禅寺へ行ったほうが利得が高くなります.したがってナッシュ均衡ではありません.

なお(C)で「文太はショッピングモールに行ったほうが利得が高くなるのでナッシュ均衡ではない」としても良いです.「ナッシュ均衡ではない」ことを示すには,選択を変えると利得が高くなるプレイヤーが1人でもいることを示せば良いので,アリスと文太の両方について言わなくても,どちらか1人で良いわけです.なお上記の場合,アリスにとって禅寺に行くことは支配戦略です.支配戦略がある場合は,ナッシュ均衡では必ずその戦略が選ばれるはずです.

次はどうでしょうか?

練習2:アリスと文太は,禅寺かショッピングモールへ行く.アリスも文太もどちらに行くかよりも,相手に会えるほうが会えない方が大切で,それが絶対良いと考えている.その中でアリスは,会えたときも会えないときも,禅寺のほうがショピングモールよりも良く,文太はショッピングモールのほうが禅寺よりも良い.以下から,ナッシュ均衡を選べ.複数あるときはすべて選び,ないときは「なし」と答えよ.
(A)2人とも禅寺へ行く
(B)アリスは禅寺へ,文太はショッピングモールへ行く
(C)アリスはショピングモールへ,文太は禅寺へ行く
(D)2人ともショッピングモールへ行く

正解は(A)か(D).2人が会えている(A)と(D)では,どちらか一方だけが行動を変えると,そのプレイヤーの利得が小さくなるのでナッシュ均衡です.(B)と(C)で,どちらか一方だけが行動を変えると,そのプレイヤーの利得が高くなるのでナッシュ均衡ではありません

さてさて,次はどうでしょうか?

練習3:アリスと文太は,禅寺かショッピングモールへ行く.アリスは文太が大好きで,行く場所よりも文太に会えることが会えないことより良い.その中で会えたときも会えないときも,禅寺のほうがショピングモールよりも良いと.文太は残念ながらアリスが嫌いで,行く場所よりもアリスに会わないほうが会えるより絶対良いと考えている.その中で,会えたときも会えないときも,禅寺よりショピングモールのほうが良いと考えている.以下から,ナッシュ均衡を選べ.複数あるときはすべて選び,ないときは「なし」と答えよ.
(A)2人とも禅寺へ行く
(B)アリスは禅寺へ,文太はショッピングモールへ行く
(C)アリスはショピングモールへ,文太は禅寺へ行く
(D)2人ともショッピングモールへ行く

この場合はナッシュ均衡は「なし」です.2人が会えている(A)と(D)では,文太が行動を変えると会えなくなって利得が高くなり,2人が会えていない(B)と(C)では,アリスが行動を変えると高くなるので,どれもナッシュ均衡ではありません.(なおこのような場合も確率で戦略を選ぶ混合戦略を用いると,ナッシュ均衡がありますが,その場合は利得を数値で表さなければ確率が計算できません).

3人以上のゲームの例

ナッシュ均衡についての理解が深まってきたでしょうか?それでは3人以上の例を考えて,練習してみましょう.まず簡単な「多数決」を考えてみましょう.

練習4:(奇数人での多数決) 5人で「海」か「山」を選ぶ. 多い人数が選んだ方を選ぶと勝ち,少ない人数が選んだ言葉を選ぶと負け.当然,勝つほうが負けるより良いとします.以下から,ナッシュ均衡を選べ.複数あるときはすべて選び,ないときは「なし」を選べ.
(A) なし
(B) 全員が「海」を選ぶ
(C) 4人が「海」,1人が「山」を選ぶ
(D)3人が「海」,2人が「山」を選ぶ
(E) 2人が「海」,3人が「山」を選ぶ
(F) 1人が「海」,4人が「山」を選ぶ
(G) 全員が「山」を選ぶ

正解は(B)と(G)です. 全員が同じ言葉を選ぶ(B)と(G)では,どの人も他者の選択はそのままで自分の選択を変えると利得が低くなるので,ナッシュ均衡です.それ以外では,少数派になっているプレイヤーは,他者の選択がそのままのときに自分の選択だけを変えると多数派となり,利得が高くなるので,ナッシュ均衡ではありません.

では,次はどうでしょう.ライアーゲームの最初に出てくる「少数決」です.少数派になったほうが勝ちです.

練習5:(奇数人の少数決) 5人で「海」か「山」を選ぶ.少ない人数が選んだ方を選ぶと勝ちで, 多い人数が選んだ方を選ぶと負け.以下から,ナッシュ均衡を選べ.複数あるときはすべて選び,ないときは「なし」を選べ.
(A) なし
(B) 全員が「海」を選ぶ
(C) 4人が「海」,1人が「山」を選ぶ
(D) 3人が「海」,2人が「山」を選ぶ
(E) 2人が「海」,3人が「山」を選ぶ
(F) 1人が「海」,4人が「山」を選ぶ
(G) 全員が「山」を選ぶ

正解は(D)と(E)です.それ以外では,多数派になっている人は,自分だけの選択を変えると少数派となり利得が高くなりますので,ナッシュ均衡ではありません.

これに対し(D)と(E)では,すべてのプレイヤーが自分だけ選択を変えても利得が高くならない(同じか低くなる)のでナッシュ均衡です.なぜかと言うと,少数派となったプレイヤーは自分の選択を変えると多数派になり利得が下がりますし,多数派のプレイヤーは自分だけが選択を変えても,やはり多数派になってしまい(多数派が変わってしまいます)利得は同じになります.

もうお腹いっぱいでしょうかね?それでは,最後の問題です.

練習6:(7人じゃんけん)7人でじゃんけんをします.もちろんすべてのプレイヤーは,勝ち,あいこ,負けの順に良い(利得が高い)とします.
(A) なし
(B) 7人ともにグーを出す
(C) 3人がグー,4人がパーを出す
(D) 1人がグー,2人がパー,4人がチョキを出す
(E) 2人がグー,2人がパー,3人がチョキを出す
(F) 3人がグー,2人がパー,2人がチョキを出す

答えは(E)と(F)です!(B)「7人ともにグーを出す」や (C)「3人がグー,4人がパーを出す」では,グーの人がパーに変えることで負けから勝ちに転じて利得が高くなります.また(D)「1人がグー,2人がパー,4人がチョキ」では,グーの人がチョキに手を変えると,アイコから勝ちに転じて利得が高くなります.したがってナッシュ均衡ではありません.しかし(E)と(F)の場合は,どの人も自分だけが手を変えても,あいこからあいこになるだけで利得は高くなりません.したがって,(E)と(F)はナッシュ均衡です.

ナッシュ均衡(ざっくりした説明)

ここではまずナッシュ均衡について,ざっくり説明します.

  • ナッシュ均衡の求め方(2人ゲームの利得行列)はこちらのページで.
  • クールノー均衡はこっち.
  • 定義などは,また後ほど.

ナッシュ均衡とは

ゲーム理論におけるナッシュ均衡とは,ざっくりいうと

どのプレイヤーも,自分だけでは,それ以上利得が大きくできない状態

です.「状態」って言い方は不正確過ぎるか.もう少し正確に言うと,ナッシュ均衡とは

どのプレイヤーも,他のプレイヤーがそのナッシュ均衡の戦略を選んでいるもとでは,その戦略が一番利得が高くなる(他の戦略では利得が同じか低くなる)

ような戦略の組です.あんまり変わんないか.

ナッシュ均衡の例

例を挙げましょう(これは支配戦略の例で,客数を変えたものです).

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

このゲームを利得行列で書くと下のようになります

ナッシュ均衡の例

例えば「セレブとファミモが共にA駅を選ぶこと」はナッシュ均衡ではありません.なぜならセレブは,ファミモがA駅を選んでいるなら,B駅に変えたほうが利得が高くなるからです.このように,他のプレイヤーの戦略が変わらないもとで,あるプレイヤーが選択を変えると利得が高くなるならば,その戦略の組はナッシュ均衡ではありません.

ナッシュ均衡ではない

これに対し,例えば「セレブがA駅,ファミモがB駅を選ぶこと」はナッシュ均衡です.なぜならセレブもファミモも,相手がそれを選んでいる限り,自分の利得をもっとも高くしているからです.つまりナッシュ均衡では,

どのプレイヤーも(相手がその戦略を選んでいるならば),それ以上利得を高くできない (他の戦略では利得が同じか低くなる)

と言うことになります.

ナッシュ均衡である

ナッシュ均衡は2つ以上あるときもある

しかしこの例では「セレブがA駅,ファミモがB駅を選ぶこと」だけではなく,
「セレブがB駅,ファミモがA駅を選ぶこと」 もナッシュ均衡になることが分かります.つまりナッシュ均衡は1つとは限らず,2つ以上ある場合もあります.このときどちらをゲーム理論の解とすべきかは難しい問題で,これは「均衡選択」と呼ばれる理論と「均衡精緻化」と呼ばれる理論で考えられています(2つの違いを説明するのはちょっと難しい)これはまた別の機会に.

ナッシュ均衡がなぜ解なのか

ナッシュ均衡以外が結果として予測されたとします.このとき,もしすべてのプレイヤーがその予測を知ったならば,少なくとも1人はその予測から違う行動を取ることで利得を高くすることができるはずです.そのプレイヤーは,ナッシュ均衡と違う行動を取るでしょうから,もはやその予測は当たりません.このことから,ゲームの結果の予測をプレイヤーが知っても結果が成り立つためには,その予測はナッシュ均衡でなければならないはずです.(「じゃんけんの必勝法と行動ファイナンス・行動経済学」も参考にしてください)

注意点と補足

  • すべてのプレイヤーが支配戦略を選んでいるときはナッシュ均衡になります.これはナッシュ均衡の特殊ケースと考えられます.したがって囚人のジレンマの結果もナッシュ均衡であると言えます.
  • 上記の点から考えると,じゃんけんにはナッシュ均衡がありませんが,確率を用いる「混合戦略」を考えるとナッシュ均衡が存在します.このような混合戦略まで考えると,すべてのn人有限ゲームにナッシュ均衡が存在します.この素晴らしい定理を誰が証明したかは,よく考えれば分かるはずである.これによって,その人はノーベル経済学賞を受賞しています.私ではありません.
  • ナッシュ均衡が分かったような気がしない?もう少し理解を深めたい?ではナッシュ均衡のおけいこ(1)で練習しましょう.
  • 2人ゲームの利得行列でのナッシュ均衡の求め方はこちら
  • クールノー均衡はこっち.

非協力ゲームと協力ゲーム

ゲーム理論は非協力ゲーム(non-cooperative game)と協力ゲーム(cooperative game)に分けられます.

ゲーム理論は経済学で大きく発展しました.近年,経済学で主に扱われているのは非協力ゲームです.このため「ゲーム理論」と言う言葉は,非協力ゲームのことを指すことも多いです.実際に,ゲーム理論の代表的なテキストTadelis(2012),Fudenberug and Tirole(1991) などでも協力ゲームは扱われていません.

これに対し,近年ゲーム理論の研究が盛んな計算機科学の分野では,協力ゲームもそれなりに扱われ,研究されているように見えます.

非協力ゲームは,プレイヤーが行動を選び,その結果が各プレイヤーにどのように好まれるか(利得)がモデルに与えられます.「プレイヤーがどのように行動するか」を明らかにすることが非協力ゲームの目的であると言えます.例えば非協力ゲームの代表的な例である「囚人のジレンマ」では:

  • プレイヤーは2人,各プレイヤーは「協力する」か「協力しない」かの2つの行動から1つを選ぶ
  • 各プレイヤーは次の順番に結果を好む
    • 自分が協力せず,相手が協力してくれること
    • 自分も相手も協力すること
    • 自分も相手も協力しないこと
    • 自分は協力して,相手が協力しないこと

というモデルです.ここではプレイヤーの行動と,その行動の帰結に対して,自分が何を好むかが与えられています.このような設定で,各プレイヤーがどのような行動を選ぶのかを明らかにすることが非協力ゲームであると言えます.

これに対し協力ゲームは,プレイヤーの提携(集合,結託,グループなどと呼ばれる)に対する利益が与えられます.例えば,

  • プレイヤーはA君,B君,C君の3人.大道芸をして稼ごうとしている.
  • A君,B君,C君は1人ずつだと1日の利益は0円.
  • A君とB君が一緒に組むと(これが「提携」)利益は1万円になる,B君とC君だと1万5千円,A君とC君だと2万円.
  • A君,B君,C君が3人で組むと,利益は3万円

と言ったモデルです.非協力ゲームと違い,プレイヤーには選ぶ「行動」がなく,提携に対する利益だけが与えられています.このような設定で「どのような提携が最終的に組まれるのか(全体提携が組まれるのか)」「そのとき利益はどのように分配されるのか」を明らかにすることが協力ゲームであると言えます.

協力ゲームでは,いかに提携の利益が発生するかが明確ではないため,その利益が本当に実現するのか,という問題が残ります.提携の利益が確実に得られる「拘束的合意」と呼ばれる合意が存在することが,前提になっているとも言われます.もともとは協力ゲームは,非協力ゲームの設定が与えられ,そこから各提携の利益が導かれるという形が出発点でした.それならば,元の非協力ゲームを分析すれば良いだろう(分析するべきだ)というのが,現在,経済学等で非協力ゲームだけが扱われる理由です.根底には「社会の状態は,個人が合理的に選択する行動の帰結として描写されるべきだ」という経済学の理論に対する考え方が現れてるとも言えましょう.

しかし目的によっては,協力ゲームのようなモデル化が便利な場合もあります.特に「どのような行動が選ばれて,どのような利益が得られるか」という「どうなるか(記述的理論)」ではなく,「提携ごとの利益から,どのように利益が各プレイヤーに配分されるべきか」という「どうあるべきか(規範的理論)」として活用できることが,協力ゲームの利点でもあります.

協力ゲームも非協力ゲームも,共にゲーム理論として発展してゆくべきだと私は考えています.