静岡大学集中講義「社会システム工学」 講義情報

2021年9月下旬に非常勤で集中講義を予定している静岡大学工学部数理システム工学科の講義「社会システム工学」の講義情報です。ゲーム理論を講義する予定です。

以下の講義資料は,変更されることがあります。

オンデマンド学習について

完全ではありませんが,講義内容に沿った動画をオンデマンドで見ることができます.以下を参照してください.
http://nabenavi.net/gametheory/

これは文系(東京都立大学経済経営学部)向けのもので,本講義にある「数式の表記について」という部分に対応している動画はありませんが,宿題や演習には十分対応できます.以下のようなときに利用してください.

  • 通信環境が良くない場合
  • 講義時間の都合がつかない
  • 予習と復習

以下には,講義内容とURLの対応表があります。

youtube対応表

一歩ずつ学ぶ ゲーム理論

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

裳華房
https://www.shokabo.co.jp/mybooks/ISBN978-4-7853-1593-1.htm

アマゾンhttps://www.amazon.co.jp/dp/4785315938/ref=cm_sw_r_tw_dp_HWBTTC81MM20H2FSMDB5

演習問題解説

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

演習問題の解説(PDF)

なお、裳華房の本書の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ステップ進む確率を高めたほうが良いかもしれない.

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

じゃんけん研究