一歩ずつ学ぶ ゲーム理論

裳華房から2021年秋に出版された「一歩ずつ学ぶ ゲーム理論-数理で導く戦略的意思決定-」のページです。

裳華房のページへのリンク

アマゾンのページへのリンク

正誤表

本にはいくつか誤りがあり、ご迷惑をおかけしています。以下に正誤表(PDF)があります。
ご指摘いただいた方々、特に千葉大学の岸本先生とそのゼミの皆さんには感謝致します。

正誤表(2022.06.10)

演習問題解説

各章末の演習問題で、難しいと思われる問題や、詳しい説明が必要と考えられる問題についての解説(PDF)です。

演習問題の解説(ver2. 2022.02.15改訂)

なお、裳華房の本書のWebページにも同じものが掲載されています。

本の特長

  • 初めて学ぶ者も数式でゲーム理論を理解できるように、分かりやすい言葉で、省略することなく丁寧に、一歩一歩独りでも学ぶことができることを目指した教科書。
  • ゲーム理論を学ぶ本は、もはや専門書ではなく、教科書・テキストであるとの考え方に立って、さまざまな工夫をした。
  • 数式による定義は必ず言葉で言い換えて、例を使って説明し、必要なものには図解を加えるように心がけた。
  • 集合の用語や引数や述語論理の使い方など、数学に慣れた者には当たり前であっても、初学者が引っかかってしまう数学の概念には数学表現のミニノートとして解説を加えた。
  • 本書で何を学ぶのかについては最初のプロローグに示して、読者がどこまで学習したかが分かる地図を作り、各章のはじめに地図と現在の位置を示した。本文の中で重要な部分は太字にし、checkマークのアイコンを付けた。
  • 章のはじめにはキーワードを示し、終わりにはまとめを置いた。
  • 章末の演習問題を充実させて、解答をつけるのはもちろんのこと、難しい問題には(ネット上に)解説も示した(上記)。

「ゼミナールゲーム理論入門」との違い

「ゼミナールゲーム理論入門」は、図や数値例でゲーム理論の考え方を学ぶようになっていますが、概念の定義は言葉だけでなされています。また、独占やクールノー競争、オークションなど、経済学的な例をやや多く用いています。

これに対して「一歩ずつ学ぶ ゲーム理論」は、企画段階では「理工系のためのゲーム理論入門」という名前であったように、概念の定義に数式も用い、その意味を図や数値例で理解して、(まさに一歩づつ)ゲーム理論を学ぶようになっています。道路の混雑、交渉、投票、コーディネーションなど、例も盛り込んではあるものの、理論を学ぶことに重点を置いています。また「ゼミナール…」より、ややページ数を少なくしています。

オークション理論の本

オークション理論を勉強するために参考となる本をいくつか紹介します。

  • 「マーケットデザイン」, ギオーム・ハーリンジャー (著), 栗野盛光 (翻訳)、中央経済社、2020。
    • マーケットデザインの「テキストブック」として書かれた本。ゲーム理論やミクロ経済学の知識がない初心者であっても、マーケットデザインについての理論と現実の両方について学んでいける本。
  • Auction Theory (Second Edition), Vijay Krishna, Academic Press, 2009.
    • オークション理論の最も優れたテキスト。単一財の独立価値モデル、価値依存モデル、メカニズムデザインと最適オークション、非対称均衡の分析、複数財のオークションと必要な理論が網羅されていて、しかも確率理論の必要となる部分(特に順序統計量と確率順序)がすべて付録に書かれている。数学記号の使い方も厳密で且つ簡潔で、他分野でもこれほどよくできたテキストは珍しい。真面目に勉強したいならばこれでやりましょう。なおfirst editionは2002年に書かれており、まだ売っていてKindle版もある。あくまでも厳密な理論を学ぼうと言う人向けです。
  • 「マーケットデザイン入門」、坂井豊貴、ミネルヴァ書房、2010。
    • Krishnaの本は英語だし重厚なので、まず「日本語で簡潔にオークション理論」を学びたいというなら、これが良い。単一財、複数財のオークションのエッセンスが書かれている。著者の坂井豊貴氏はメカニズムデザインの研究者として知られ、本書もマーケットデザインの入門書として前半をオークション理論に、後半をマッチング理論に割いている。なお、あくまでも厳密な理論を学ぼうと言う人向けです。
  • 「オークションの人間行動学 最新理論からネットオークション必勝法まで」、ケン・スティグリッツ (著)、 川越敏司・佐々木俊一郎・小川一仁 (翻訳)、日経BP社、2008。
    • “Snipers, Shills, & Sharks: eBay and Human Behavior,” Ken Steiglitz, Princeton University Press, 2007の翻訳。翻訳者の中心である川越先生は実験経済学の研究者として知られ、オークション理論にも詳しい。本書も、オークション理論だけではなく、実験経済学や行動経済学の知見や、ネットオークションも盛り込まれており、付録にはオークション理論の簡潔なサーベイがあるので、これを勉強すると良い。理論は難しいな~と思う人も、何とか読めます。
  • 「オークション理論の基礎」、横尾真、東京電機大学出版局、2006。
    • 著者の横尾先生は計算機科学でのオークションとメカニズムデザインの研究者として有名。この本は、計算機科学で特に重要な複数財オークションや架空名義入札という概念を中心にして、オークション理論の考え方やゲーム理論の考え方を初歩から分かりやすく説いている本です。誰もが読むことができます。オークション理論は、不完備情報ゲームという「確率」や「均衡」の概念を用いていますが、横尾氏を中心に計算機科学分野で使われるVCGメカニズムというオークションは耐戦略性という性質を重要視していて、この性質を中心として理論を展開する場合は、確率計算をあまり必要としません。このような分野からオークションを知りたい者には、最良の本であると言えます。
  • An Introduction to Auction Theory, F. M. Menezes, P. K. Monteiro, Oxford University Press, 2008.
    • 洋書を含めてもオークション理論をきちんと説明している本は少ないが、この本はそのうちの1つである。「Krishnaを1冊読みきるのは難しいので、少ない分量で...」というならこの本はどうでしょう。変わった数値例があって面白い。でも、あくまでも理論を学ぼうと言う人向けです。
  • 「メカニズムデザイン」、坂井豊貴・藤中裕二・若山琢磨、ミネルヴァ書房、2008。
    • メカニズムデザインで知られる3人の研究者によって書かれた本で、4章にオークション理論が載っています。本書はメカニズムデザインの一般的な理論を展開し、その適用例としてオークションを捉えたもので、その点では類を見ない本です。メカニズムデザインにも興味があるという人は、先に挙げたマーケットデザイン入門とともに読むと良いでしょう。
  • “Putting Auction Theory to Work,” Paul Milgrom, Cambridge University Press, 2004.
  • オークション理論の第1人者Paul Milgromによる本なので、是非手にしたい。単一財・複数財、独立価値・依存価値など、様々な文脈におけるオークション理論の展開が上記の本とは異なる構成で書かれている。また「積分包絡線定理」という彼のもう1つの研究成果から、オークション理論を捉えようとした意欲作でもあり、彼が携わったオークションの実際の設計に関する理論の適用も書かれている。ただ、数学の記法がやや煩雑でしかも曖昧さがあり、行間が激しく飛んでいる部分もあるので、それを埋めて厳密に理解しようとすると、なかなか大変である。なお翻訳書「オークション 理論とデザイン」、Paul Milgrom (原著), 川又邦雄・奥野正寛(監訳), 計盛英一郎, 馬場弓子(翻訳) があるのもうれしい。

勝者の呪い、独立私的価値と共通価値

単一財オークション理論では、商品に対して入札者がどのような価値を持っているかによってモデル化が異なります。ここではそれと勝者の呪いについて説明します。

独立価値モデルと共通価値モデル

独立私的価値(Independent Private Value, IPV)モデルは、個人によって商品の評価額(=価値)が異なるモデル、他者と自分の評価額が独立しているモデルです。スターやアイドルの所持品や遺品、絵画や骨董品のように「他人にとっては値打ちがなくても、自分にとっては値打ちがある」と言った商品に対して適用されます。この場合、入札者の評価額は入札者自身が分かっており、他者の評価額や情報に影響を受けません。

これに対し、すべての人にとって商品の本来の評価額が同じと考えるモデルを共通価値(Common Value, CV)モデルと呼びます。 ただし入札者はその評価額を正確に見積もることができず、人によって「誤差」が生じます。これは石油や鉱山の採掘権、転売を目的とした商品の入札などに当てはまるモデルです。石油の採掘権(=油田)の評価額は、そこから採掘される油田の埋蔵量☓原油価格によって一意に決まります(採掘にかかるコストを考慮するときもある)。しかし、埋蔵量がどのくらいあるのか、原油価格がどのくらいになるかの予想が人によってずれる(誤差を持つ)ため、入札者がその油田に対して持つ評価額がずれてくるわけです。また転売目的に商品を落札するときは、転売時の商品価格が評価額となるはずです。最終的にこれは一意に決まりますが、入札時の予想は人によって異なるため評価額がずれてくるわけです。

一般的には、個人の評価額は不確実で他者の評価額い依存・相関すると考える相互価値依存モデル(Interdependent Value)と呼ばれるモデルもあり、共通価値モデルはこの特殊な場合として考えることができます。

勝者の呪い

共通価値モデルにおいては、一番高く商品を評価した入札者が、落札して商品を手に入れます。しかし、一般的にその商品の「共通価値=正しい価値」は、すべての入札者の評価額の平均値に近いと考えられ、一番高く商品を評価した入札者は商品を過大に評価しています。落札価格が実際の商品の価値を上回っている可能性もあり、このとき落札者は実際の商品の価値を知ったときに、それよりも高い価格で商品を買ってしまったと後悔することが予想されます。これを勝者の呪い(winner’s curse)と言います。

私が共通価値モデルの話で思い浮かべるのは、「群衆の智慧(ジェームズ・スロウィッキー)」の冒頭に出てくる「雄牛の重さ当てコンテスト」の話です。

1906年にイギリスの科学者フランシス・ゴールドンは、イングランド西部の見本市における「雄牛の重さ当てコンテスト」で、ある調査をしました。このコンテストは、800人の参加者が「雄牛の重さ」を推測し、一番正解に近い人が商品をもらえる、というものでした。コンテストの参加者800人の予測のうち、判読不能な13人を除き787人の平均値を調べた結果、その平均値は1197ポンドでしたが(※1)、雄牛の実際の重さは1198ポンドで、ほとんど一致していたというものです。

この話は集合知=群衆の知恵の代表例として知られています。これはこれで面白くて話したいこともたくさんあるのですが、それはまた別の機会に。

さて、このコンテストが雄牛のオークションであったら、どうでしょうか? 牛肉1ポンドの価格はだいたい決まっているはずなので、 正しい雄牛の価格は牛肉1198ポンド分の「共通価値」になるはずです。そして、それは全員の予想の平均値とほぼ同じになります。しかしオークションを落札する人は、この雄牛の重さをもっとも重く予想した人になり、たぶんその人は落札後に勝者の呪いを持つことになるでしょう。

その商品の価値は一意に決まっていても不確実性があり、その価値を参加者が誤差を持って観察する場合は(ガウスを信じるなら)、参加者の評価額は以下の正規分布のように分布するはずです。

参加者の評価額の分布

もっとも高い評価額は平均値=真の評価額よりも、必ず高いところにあります。もしセカンドプライスオークションの説明で述べたように、参加者が自分の評価額を正直に入札したら、落札者は必ず勝者の呪いを起こすことになります。

共通価値モデルのセカンドプライスオークション

このことから共通価値モデルでは「セカンドプライスオークションでは、参加者が自分の評価額を正直に入札する」ということは成り立たないことが分かります。合理的な入札者は、自分が勝者になっても勝者の呪いが起きないように、自分の評価額よりも低く入札を行うという結果が得られます。

※1 ゴールドンは実際は中央値を用いていたそうです(Wallis, 2014)。

参考文献

  • James Surowiecki (2005) The Wisdom of Crowds, Anchor.(翻訳:ジェームズ・スロウィッキー (著), 小高 尚子(翻訳)、群衆の智慧、角川書店)。※この本は昔は「『みんなの意見』は案外正しい」という名前で出版されていました。こっちのほうが馴染みがありますよね。
  • Kenneth F. Wallis (2014) Revisiting Francis Galton’s Forecasting Competition, Statistical Science, Vol. 29, No. 3, 420-424.

オークション理論を知ろう(1):セカンドプライスオークションと収益等価定理をざっくり解説

収益等価定理とは、どんなオークションでも、売り手に与える収益は同じになるという驚くべき定理です。ここではセカンドプライスオークション(第2価格入札)、ファーストプライスオークション(第1価格入札)、競り(イングリッシュオークション)の3つのオークションについて考え、(1)セカンドプライスオークションでは参加者が自分の評価額をそのまま入札することが良いことや、(2)収益等価定理が成り立つ理由、などについて、直観的にざっくりと説明します。

セカンドプライスオークションと収益等価定理

ゲーム理論やオークション理論を習ってまず感激するのはセカンドプライスオークション(第2価格入札)というオークションの理論です。このオークションは1番高い入札をした人に、2番めに高い入札額で財を売るというヴィックリなオークションです(これを考えたVickreyにかけました.すみません)。

「おい、そんなことをしたら、売る人が損するんじゃね?」と思うひと。ゲーム理論やメカニズムデザインを勉強しましょう!そうではないんですよ。

普通のオークションは1番高い入札をした人に、その人の値段で売りますよね(ファーストプライスオークション=第1価格入札)。すると入札者は安く買うために入札額を下げようとします。ただし下げすぎると競争に負けて落札できないので、ここで迷うことになります。

ところがセカンドプライスオークションだと、落札者が財を購入する価格は自分の入札額ではない(自分の次に高い人の入札額)ので、安く入札しようが高く入札しようが、自分が買う値段には関係ないことになり、参加者の入札額は通常のファーストプライスオークションより高くなります。

参加者が安めに入札したファーストプライスオークションの1番高い入札額と、参加者が高めに入札したセカンドプライスオークション の2番めに高い入札額…どっちが売り手にとって良いか分からん、ということになります。これが同じになるっていうのが収益等価定理なんですね。

ここからは以下の例で考えてみましょう。いま真帆とはるかという2人の参加者がオークションに参加していて、売られている財(怪しい水晶玉)の評価をそれぞれ120万円、200万円としているとしましょう(図1)。

図1 オークションの設定

セカンドプライスオークションの戦略


さてオークションがセカンドプライスオークションであるとします。 ここでセカンドプライスオークションで、はるかは、自分の評価額を正直にそのまま入札することが最適な入札となることを説明します。

  • 評価額の200万円より安い金額xを入札した場合。このように入札しても、もし落札できれば、200万円を入札したときと同じ金額で買うことになる。(相手の入札額が落札価格なので)。しかも相手がx万円以上を入札してきたときは、落札できないので評価額の200万円を入札したほうがいい。
  • 評価額の200万円より安い金額yを入札した場合。このときは相手が200万円より高い入札をしても落札できる訳だが、それでは評価額より高い金額で買うことになってしまう(赤字)。相手が200万円より安い入札をしたら200万円でも落札できるので、評価額の200万円を入札したほうがいい。
  • 図に示すと図2のようになる。
図2 第2価格入札では評価額を入札することが一番いい

この話は相手の評価額や入札額が何であっても成り立つことに注意しましょう。セカンドプライスオークションでは、相手がどんな入札をしても自分の評価額を正直に入札することが良い、ということになります(これをゲーム理論では弱支配戦略と言う)。これがセカンドプライスオークションがヴィックリオークションと呼ばれる理由です(しつこくて、すみません)。 この性質はセカンドプライスオークションの耐戦略性と呼ばれ、メカニズムデザインにおいて重要な性質と考えられています。

このようにセカンドプライスオークション では参加者は自分の評価額を正直に入札します。その結果、売り手の収益は、2番目に高い参加者の評価額になります。図1の状況では、真帆は120万円、はるかは200万円を入札し、売り手ははるかに120万円で財を売ることになります。

ファーストプライスオークション

では通常の1番高い入札をした人に、その値段で売るファーストプライスオークションでは、どうなるのでしょうか。これはセカンドプライスオークションのように「相手がどんな入札をしても…」とは行きません。相手が高く入れれば高く、低く入れれば低く入れなければならないので、相手の評価額を推測する必要があります。そこで不完備情報ゲームの理論、確率論、微分方程式、と飛び道具を使わなければなりません。ここではそうも行かないので、単純化して相手の評価額が分かっているとして考えてみましょう。

図1の状況で、皆さんが「はるか」だったらいくらを入札するでしょうか?はるかは競争相手の真帆の評価額が120万円であることを知っているとしています。真帆が90万円くらい入札するなら、安く91万円くらいで買いたいところですが、はるかは真帆の評価額が分かっても入札額は分かりません。しかし真帆は120万円以上は絶対に入札してこないはずです。したがってはるかは120万円を超えるできるだけ安い価格を、可能であれば120万1円とかを入札すれば良いはずです。

つまりファーストプライスオークションでは、評価額が1番高い参加者は2番めに高い参加者の評価額の僅かに上を入札すれば良いわけです.「僅かに上」は無視できるとして、ファーストプライスオークションでは評価額が1番高い参加者が2番目に高い参加者の評価額を入札すると考えることができます。その結果、売り手の収益はやはり2番目に高い参加者の評価額になります。図1の状況では、真帆は120万円以下を、はるかはほぼ120万円を入札し、売り手はほぼ120万円で財を売ることになります。

競り

収益等価定理は競りにも適用できます。図1の状況で、30万円、40万円、50万円…と価格が競り上がっていく状況を考えましょう。このとき真帆やはるかはどうするでしょうか?

図3:評価額までは競りに参加する

参加者は、自分の評価額を超えるまで、真帆は120万円まで、はるかは200万円まで競りに参加して、頑張るでしょう。しかし評価額になると、競りから降ります。その結果、真帆が120万円で落札することになります。

図4:評価額を超えると競りから降りる

このように競りでは、評価額の2番めに高い参加者が降りた時点で、評価額の1番高い参加者が落札することになります。落札額は参加者の2番目に高い評価額になります。1番高い評価額には関係ないことに注意です、図の状況でたとえはるかが1億円まで出すつもりがあっても、真帆が120万円以上出す気がないなら、120万円で落札するわけです。その結果、競りでも売り手の収益はやはり2番目に高い参加者の評価額になります。

ちなみに競りで参加者は、相手の評価額を予想する必要はなく、自分の評価額まで競りに参加し、自分の評価額を超えれば競りから降りることが一番良いということが明らか(obvious)です。明らか均衡です。このことからセカンドプライスオークションと競りは、同等であるとも言えそうです。

収益等価定理

以上から、ファーストプライスオークション、セカンドプライスオークション、競りは、売り手に同じ収益を与え、それは参加者の2番めに高い評価額になるということが、ざっくりと分かりました。セカンドプライスオークションと競りでは相手の入札額に関係なく、このことが成り立つのですが、ファーストプライスオークションをはじめとする他の入札では、相手の評価額を確率に従って予測しなければなりません。結果としては、ある条件(後述)においては、どんなオークション(サードプライスオークションとか、一番安い入札額で売るとか、第1価格と第2価格の平均値で売るとか)でも、売り手の収益は2番目に高い参加者の評価額の期待値になる、というのが収益等価定理です。

定理の説明の補足、私的価値と相互依存価値

セカンドプライスオークションで評価額を正直に入札すれば良いという性質や、収益等価定理は入札者の評価額が他者の評価額に依存せず決まっている私的価値(private value)モデルについて成り立ちます。参加者が財に対して持つ価値が他者に依存する相互依存価値モデル(interdependent value)モデルでは、セカンドプライスオークションでも現在の評価額を正直に入札すれば良い、とは言えなくなります。

収益等価定理が成立するには(1)オークションで販売される財の価値に対して参加者が持つ価値は、他者とは独立に決まること (IPV:Independent Private Value)という条件以外にも、(2)その価値は事前には同一で独立の確率分布に従っていること、(3)参加者の行動は対称的(同じ価値であれば同じ入札額になるという感じ)であること、(4)参加者はリスク中立的であること、などが必要です。これらの条件が成立しない場合は、オークション形式により、売り手に与える期待収益は異なります。

定理を正しく理解するには、(1)ゲーム理論の不完備情報ゲームを修得し、(2)確率に対する知識を持ち、その中でも順序統計量という理論を理解し、なおかつ(3)微分方程式が解けなければならない、というもので意外と(かなり?)手強いです。なので、セカンドプライスオークション、競り、ファーストプライスオークションの3つのオークションについて、収益等価定理が成り立つ理由について、かなりいい加減ですが、直観的な説明をしました。

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

完全情報展開形ゲームとその解き方であるバックワードインダクション(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:コロナ対応)