2013年2月25日月曜日

Minority GameとCrowd-Anticrowd モデル I

今年の卒研のテーマのひとつとしてMinority Game(少数決ゲーム)を採用し、春頃から実験用サーバープログラムの開発と物理学科3年の選択科目「データ解析」の演習時間を用いた予備実験、そして北里祭での一般参加者による実験を行いました。その目的はタイトルにある、協力の創発がCrowd-anticrowdという仕組みで起きるのかを検証することでした。

Minotiry Game(少数決ゲーム)とは、2択の選択を複数の参加者で同時に行ってもらい、少数派の選択を選んだ参加者を勝ちとするものです。このゲームを同じメンバーで、毎回、過去の少数派の選択肢を周知するという情報だけをあたえて繰り返す。非常にシンプルなゲームであり、もともとはB.W. Arthurという経済学者がEl Farol Bar問題(1990)として定式化したものに由来します。人口100人の町にキャパシティー60人のEl Farolというバーがあり、人は今晩バーにいくかど家にいるかを決めるとする。バーにいって、バーの前にいる人数が60人以下ならバーにいって正解。61人を越えるなら家にいて正解。では、100人のうち60名がバーに、40名が家にという選択を実現するのはどうすればいいのか?これがEl Farol Bar問題。

経済学では人は他人の行動を含むあらゆる情報知り、すべての人が全知全能の存在として合理的に意思決定すると考える。しかし、Arthurは、人は限定合理的な存在であり、その限定合理性を「人は過去のパターンから予測し行動するものである」とモデル化しました。すると、簡単に60人がバーの前に現れるようになります。過去のバーの前の人数のパターン(昨日が48人、一昨日が72人など)に対し、今日の人数を予測するとします。その人数は0から100まで101パターンあります。100人の町の人の予想はその101パターンに「一様に分布する」ので、60人以下と予想する人は100人のうちの61/101の約60人となる。こうして均衡状態として約60人がバーの前に現れる状態が実現します。

これでEl Farol Bar問題は解決したように見えますが、そうではありません。実は、上記の解は無駄が非常に大きい。なぜなら、ある人がバーにいくかどうかは、その人の予測人数が60人以下の場合であり、確率は約60%。 人々は独立に予想するので、バーの前に現れる人数は100人が確率60%で独立にバーに現れる時の人数に等しく、期待値は60人ですが、ゆらぎは大体5名となります。つまり、毎回55名から65名がバーに現れ、5名分のキャパシティーが余ったり、バーのキャパシティーを越えたりする。つまり、60名ぴったりがバーに現れ、40名が家にいる状態には程遠いわけです。このように、バーの前に現れる人数の期待値が60名であることだけでは不十分で、ゆらぎを最小(可能ならゼロ)にすることが必要です?

そこで、こうした「ゆらぎ」まで含めてEl Farol Bar問題を考えるために導入されたのがMinority gameでした(D. Challet and Y.C. Zhang(1997))。そこでは、N人の参加者は0か1の二択を選び、選択者数が少ない選択肢を選んだら勝ちとする。また、参加者には過去M回のゲームでの少数派の選択肢の情報を与える。問題は、参加者が過去のパターンから有利なパターンを導き出しそれを利用し、参加者の中で少数派に属する人数を最大化(参加者が101人なら50人がベスト)し、ゆらぎを押さえられるかどうか、という点です。

D.Challet and Y.C.Zhan(1997)では、過去M回の少数派のパターンから次の少数派の選択肢を予想する予測モデルを各エージェントに複数持たせ、エージェントは自分の予想モデルのうち、もっとも勝数の多いものを用いるとします。この論文 以降、Minority gameの研究は爆発的に流行しました。2002年までの5年ほどの間に百以上がMinotiry gameを扱い、その結論は、エージェント数Nの集団に過去M回の少数派の選択肢の情報を与えたとき、Mが小さい場合は少数派の人数のゆらぎが大きく協力は起きない。けれど、Mを増やして2のM乗がNに近づくと、協力が起きてゆらぎが減少する。しかし、さらにMを増やすとゆらぎは増加に転じ、Mが十分大きなところではゆらぎの大きさはゲーム参加者がランダムに選んだ場合に一致するこというものでした。


左の図はN=9において、Mを増やしたときの多数派と少数派の選択者数の差の分散(ゆらぎの自乗)をNで割ったものをプロットしたものです。分散はエージェントがランダムに選択した場合Nとなり、Nで割ると1(緑の点線)になって都合がよいので、ゆらぎの大きさの目安として分散/Nを用います。図でM=1の場合、これは前回の少数派をエージェントに示した場合に対応しますが、その場合は1に近い。Mを2,3と増やしていくと分散は減少し、M=3では約0.3になっています。さらにMを増やすと分散は増加に転じ、Mが十分大きいところでは0.9程度になっています。 この結果でおもしろいのは、Mを増やすと、M=3まではエージェント間で協力が起こり、ゆらぎを抑える方向に改善しますが、あるしきい値を越えると協力が弱まり、状況が悪くなることです。

では、このゆらぎの非単調な振る舞いはどう理解すればよいのか。 Minority Gameでは、エージェントは予測モデルを持っています。可能な予測モデルの数は、過去M回の0,1の2のM乗個のパターンから0,1を出力する関数なので、2の2のM乗個であることが分かります。しかし、独立な予測モデルはそのうち2のM乗個のみであることは、予測モデル間の距離をハールメジャーで定義することで示すことができます。一方、エージェントの数はN。すると、2のM乗がNよりずっと小さい場合、似た予測モデルを持つエージェントが存在し、逆に2のM乗がNよりずっと大きい場合、N人のエージェントはお互いに異なる予測モデルを持つことになります。

後者の場合、N人のエージェントはお互いに独立に予測をするので、ランダムに選択するのと同じです。つまり、Nが2のM乗よりずっと小さい場合、分散/Nは1になります。この状態をUnder-crowded 相、ランダム相と呼びます。一方、Nが2のM乗よりずっと大きい場合、同じ予測モデルを持つエージェントが多数存在し、同じパターンには同じ予測モデルを用いるので多数のエージェントが同じ予測をしてしまいます。エージェントは極力他のエージェントと異なる予測を行って少数派になろうとするのですが、予測モデルがお互いに似すぎているため、それが不可能であり、多数派になることを避けられないのです(Crowd効果)。このとき、N人のエージェントの多数が一方の選択肢に集中し、もう一方の選択肢を選ぶエージェントがほとんどいないため、分散はNの自乗に比例した状態となります。この状態のことを Crowded 相と呼びます。



さらに、分散のM依存性は、2のM乗をNで割ったαというパラメータだけで決まります(左図参照)。Nが2のM乗よりずっと大きい場合、αは0に近く、Crowded相。分散/NはNに比例します。逆にαが大きい場合、Under-crowded相でエージェントはランダムに選択し、分散/Nは1になります。そして、この二つの相の間の変化は相転移であり、それが分散のα依存性の非解析性に反映しています。


こうして、予測モデルの空間の大きさとエージェント数Nの比αでMinotiry Gameの分散を理解することができます。では、Crowd-anticrowdモデルとはなにを説明するのか?また、人での実験結果はどうだったのか?それは次に。