Coevolutionary games—A mini review(共進化ゲーム), BioSystems 99, 2010のまとめ
Abstract
協力は不利なのになぜ進化するのか?
進化ゲームはこの問題を解決する理論的枠組み
この場合,戦略の進化のみでは協力の進化に不十分な面がある
戦略と"他の性質"が同時に進化するという共進化ゲーム(共進化ルール)により協力がより進化する
他の性質とは,相互作用ネットワーク,繁殖能力,評判,移動性,年齢など
進化ゲームに共進化ルールを入れた最近の研究をレビューする
1. Introduction
協力は不利なのになぜ進化するのか?
進化ゲームはこの問題を解決する理論的枠組み
その際,囚人のジレンマゲームがよく使われる.そして,混合集団では協力は進化しない.
(その他,スノードリフト,タカハト,スタグハントを混合集団でやるとどういうふうに進化するかの説明)
話は協力の進化に戻り,空間構造(構造化集団)があると,混合集団の時の結果とは大きく異なり,協力はクラスターをつくって生き残る事ができる.Nowak and May, 1992
空間構造が重要なことは実際の生物を使って実験的にも知られている.Kerr et al., 2002
(ただし,スノードリフトの場合は空間構造があると良くないよ.Hauert and Doebeli, 2004)
で,空間構造は現実的な妥当性の面から,規則格子上の進化ゲーム→複雑ネットワーク上の進化ゲームにシフトしてきた.Szabó and Fáth, 2007はネットワーク上の進化ゲームの良いレビュー.
で,Santos and Pacheco, 2005がスケールフリーネットワークで協力が強力なことを発見.ハブの協力者はめちゃくちゃ強いから.
(その後,スケールフリーネットワーク上の協力の進化について,異なる面からいろいろ研究がやられた.本当にいろいろあるけど,例えばMasuda, 2007はリンクを持つことが"コスト"になる場合は,スケールフリーネットワークで協力は進化しない(ハブの協力者が弱くなるから)ことを発見.またRong, 2007はスケールフリーネットワークのmixing pattern(ハブがハブと繋がりやすいと正の相関,ハブが次数が低いノードと繋がりやすいと負の相関,なにも傾向がなければ無相関)で,最も協力が進化するのは無相関の時を発見.また,Perc, 2009はネットワークが攻撃を受ける(ハブが取り除かれるかランダムにノードが取り除かれる)場合,ハブの除去に対して協力が脆弱なことを発見.)
その後,スケールフリーネットワークだけじゃなく,いろんなネットワークでの協力の進化が調べられた.Ohtsuki et al., 2006は様々なネットワークにおいて,協力による利益と協力にかかるコスト,さらに平均次数が分かれば協力が進化するかどうかある程度予測できることを発見.
話は変わって,協力進化のその他の理論が簡潔に説明される.血縁選択(Hamilton, 1964など),直接互恵(Axelrod and Hamilton, 1981など),間接互恵(Nowak and Sigmund, 1998など),グループ選択(マルチレベル選択)(Dugatkin and Mesterton-Gibbons, 1996など).レビューはNowak, 2006を参照.
その他,任意のゲームへの参加(Hauert et al., 2002など),社会的多様性(Perc and Szolnoki, 2008など)なども協力を進化させることが知られている.
他にもタイムスケール(Pacheco et al., 2006など),有限集団(Nowak et al., 2004など),ノイズ(Nowak et al., 1995など)も協力の進化に影響を与える.
このレビューでは,共進化ゲーム(進化ゲーム+共進化ルール)に焦点をあてる.これは協力を進化させる新しいメカニズム.
共進化ゲームは進化ゲームの自然な拡張で,戦略の進化だけでなく,環境など他の要因も同時に進化することをいう.
例えば,動的ネットワーク(リンクを作ったり切ったり),ネットワークのサイズ,教える能力(または繁殖能力),プレーヤーの移動性,年齢など.
2. Evolutionary Games
通常,囚人のジレンマ,スノードリフト,スタグハントのどれかが社会ジレンマを表現する個体間相互作用として用いられる.
プレーヤは協力か裏切りの戦略のどちらかをとる.場合によっては,孤立者(ゲームに参加しない)あるいは罰する人が用意されることもある.
自分と相手の戦略によって,プレーヤはT, R, P, Sのいずれかの利得を得る.この利得の大小を変えることで先の3つのゲームを表せる.もっとシンプルにしてR, P, Sの値は固定し,Tだけをフリーパラメータとすることが多い.
初期設定としてはプレーヤに協力と裏切りを半々の確率で割り振り,ネットワークのノードにセットする(プレーヤ=ノード).
各プレーヤは近傍(リンクでつながっている他の個体)とゲームを行って利得をためる.そして,式(1)のフェルミ関数に基づいて,自分(x)の戦略を近傍からランダムに選んだ個体(y)に強制する(xの戦略によってyの戦略が置き換えられる).戦略更新は非同期(ランダムに選んだ個体)の場合と同期(全個体が同時)の場合がある.ノイズの大きさはフェルミ関数のKの値によって制御する.
フェルミ関数は次数に影響されてしまうので,もしスケールフリーネットワークのように次数にばらつきがある場合は式(2)を用いる.他にもベストな戦略を真似するなど,戦略更新の方法はいろいろある.
3. Coevolutionary Rules
戦略だけでなく個体の特性や環境が時間とともに進化するということは明らか.
混合集団から空間格子や複雑ネットワークに移行したことは協力を進化させるが,それはまたさらなる理論の拡張を呼び起こす.そして共進化ルールはその次のステップとなるだろう.
個体のまわりのいろいろなものが変わっていくが,共進化ルールはそれらのプロセスを進化ゲームの枠組みに入れることを目的としている.
ただし,あまりやりすぎは良くない.例えば協力者が協力者のみを選んでつながると協力が進化するのは当たり前なので.なので,もっと"わざとらしくないもの"が求められている.
以下の章では共進化ルールがどのように影響するかレビューする.3.1では個体間相互作用,3.2では集団の成長,3.3では教える能力,3.4では移動性,3.5では年齢,3.6ではその他のアプローチについて.
3.1 Dynamical Interactions
動的ネットワークの話.満足していないプレーヤはリンクを切って,他のパートナーと有益な相互作用を探そうとする.
ネットワークサイズは固定.
最初,動的ネットワークでの進化ゲームはZimmermann et al., 2001やEbel and Bornholdt, 2002bによって提案された.
ネットワーク改変に対して戦略が独立なもの(Szolnoki et al., 2008など),戦略や利得が改変に影響を与えるもの(Ebel and Bornholdt, 2002bなど)様々ある.
ネットワーク改変に対して戦略や利得が影響を与えるものは図2にあるように3つのタイプに分けることができる.タイプA:戦略に依存して切ったりつないだり.例えばD-Dリンクはどちらにも不利なので切られる,C-Cリンクはどちらにも有益なので保たれる.タイプB:実際の利得を計算して,不利なものを切り有利になるようにつなぐ.タイプC:戦略の更新が優先して行われ,それに基づいてどのリンクを切り,どのリンクを残すかが決まる(ちょっと良くわからないが,図2のCを見るとCからDへの戦略の変化が起きた個体の元々持っていたリンクが切断されているようだ).
動的ネットワークのモデルでは,戦略の更新とネットワーク改変のタイムスケール(のバランス)も重要で,これは共進化ゲームの結果に大きな影響を与える(Santos et al., 2006aなど).
以降は動的ネットワーク上の進化ゲームの研究をその時間の流れに沿って個々に紹介.Ebal and Bornholdt, 2002bはランダムに選んだ個体xがランダムに選んだ個体にリンクをつなごうとする状況を想定.もしそのリンクがxの平均利得を上昇させるならつながれ,その代わりに近傍の中で相性が悪い(その相手から得る得点が最低)個体とのリンクを切る.次にZimmermann et al. 2004がD-Dリンクが切断されるモデルを考える.その後,Pacheco et al., 2006a,bがactive linking(戦略に基づいて各セットのつなぐ確率を設定する,また各リンクは一定時間後に消滅する)というモデルを提唱.この中で戦略更新とネットワーク改変のタイムスケールが協力進化に大きな影響を与えることを示した.またSantos et al., 2006aも利得に基づいてリンクを改編する(タイプB)モデルでタイムスケールの影響を調べた.これに似たモデルでFu et al., 2009bは協力者のみが裏切り者とのリンクを切って新たにリンクをつなぐ相手をランダムに選ぶモデルを考え,このような改変モデルにおいて最適なタイムスケールがあることを発見.
タイプCのモデルはSzolnoki and Perc 2009cによって提案された.このモデルでは相手の戦略を受け入れた個体は,その相手以外との全ての既存のリンクを切断する(図3aからbへの変化).その後,ランダムにリンクがつながれ(図3c),また戦略の変化(この場合DからC)が起こって,そのDが持っていたリンクが全て切られる(図3d).こうしてマルチレベル選択に必要な協力者のグループ(クラスタ)が形成される.
タイプCのモデルはSzolnoki et al., 2008aでも使われている.これは成功している個体が近傍を増やしていくモデルで,最大の近傍数が適度(過大)なときには協力が進化(衰退)することが示された(図4).
この近傍数が適度が協力にとって良いというのはPerc et al., 2008の社会格差を入れ込んだモデルで影響力のある個体同士の情報交換があまり頻繁ではなく適度に行われることが協力にとって良いという結果に似ている.
3.2 Population Growth
動的ネットワークの共進化モデルと比べて人口が増加する共進化モデル(ネットワーク成長モデル)は3つしかない.Ren et al., 2006, Poncela et al., 2008, 2009.
Ren et al., 2006はスノードリフトゲームを用いて利得ベースの優先選択モデルを考えた.これはスケールフリーネットワークを作り出し,協力を強力に進化させた.
Poncela et al., 2008も囚人のジレンマゲームを用いて利得ベースの優先選択モデルを考えた.新規ノードはεというパラメータで利得に基づいて優先的にリンクをはるかどうかが調節される.またタイムスケールも考慮され,ネットワークの成長は戦略の更新よりもはやいスピードで起こることが想定されている.εが1の極限でスケールフリーネットワークが生み出され協力が促進されることを示した.
静的ネットワークでも動的ネットワークでもネットワークが非均一(スケールフリーなど次数の多様性が高い)の時に高い協力レベルが得られるが,そのようなトポロジーだけではなくネットワークの成長プロセスも協力レベルに影響することが分かった(Poncela et al., 2009).
3.3 Evolving Teaching Activity
プレーヤの非均一性は様々な形で協力の進化にとって良い.
プレーヤが集団の中で同一ではないということは自然で,例えばある個体は高い評判や強い影響力を持ったりということが考えられる.
これらの非均一性は戦略の採用の傾向の違いとして表現できる.例えば評判が高い個体は自身の戦略をそうでない個体よりまわりに広めることができるだろう.
別の言い方をすれば,そういう個体が新しい戦略を近傍に教える能力は高い.
Szolnoki and Szabo, 2007は,そういう教える能力が協力の進化に効果的に働くことを示した.
教える能力は,Szolnoki et al., 2008のように影響率や繁殖率としても考えることができる.
教える能力(or 影響率 or 繁殖力)は,通常,戦略更新ルールのフェルミ関数を式4のように変更することで導入できる.
ここでw_xというのがプレーヤxの影響力の強さを特徴付ける.
w_x=1の場合は通常の式1と同じになる(プレーヤの影響力に差はない).
w_xが分布している(ただし,値は固定)と,例え単なる2次元格子空間であっても協力を進化させるかもしれない(Szolnoki and Szabo, 2007).
そもそも戦略の採用(戦略更新)は,より成功している個体を学ぶことであると考えられる.
この見方を採用すると,高い評判を持っていたり,高い教える能力を持っていたりするプレーヤが自身の戦略を周りに伝えることができると考えることは自然である.
そこで,Szolnoki and Perc, 2008ではプレーヤxが自身の戦略を伝えられた時,w_xが一定の値(delta w)増加することを考えた(図6).
delta wが0.07あたりが協力を進化に最適な値だった.こういう値の時にのみ最終的にw_xは非均一な分布になる(図7).
また戦略採用時のノイズKの値を増やすとこの共進化ルールの有効性は増加した.
Szolnoki and Perc, 2009bではモデルの拡張を行った.
タイムスケールのバランスはこの教える能力についても協力の進化に影響する(Szolnoki et al., 2008a).
まとめ.教える能力に影響を与える共進化モデルは,単純な「成功者がさらに成功者になる」という原理がプレーヤの性質の非均一性を生み出し,それによって協力の進化に最適な状況が保証されるということを明らかにした.
3.4 Mobility of Players
Majeski et al., 1999によって悪い状況にいる個体がその場から移動するということが考えられた.
この移動(移住)も共進化プロセスと考えられる.なぜなら戦略と場所の変更は究極的にはプレーヤの環境を決定するから.
空間囚人のジレンマ(空のサイトあり)での拡散の効果はVainstein and Arenzon, 2001, Vainstein et al., 2007が調べた.移動の仕方はランダム.基本的には弱い拡散(移動率が低い)が協力の進化にとって有益.なぜなら協力が固まっていられるから.ただし,移動の協力への効果はそんなに明らかではなかった.
そこで,移動がランダムではなく,個体の好みに基づいて行われることが考えられた.
その中で,Helbing and Yu, 2009はsuccess-driven migrationというのを導入した.これは,個体が近傍に移った場合に期待できる利得を計算して,それが現在地で得られる利得より高いなら,もっとも高い利得が得られるところに移動できるというものである.反対に今の場所が最も高い利得を得られるならその場所から動かない.これは(例えノイズがあっても)強力に協力を促進することがわかった.
最近は,移動は協力を促進するとして注目を集めている.Droz et al., 2009やMeloni et al., 2009など.
Droz et al., 2009のモデルでは2つのタイプ(影響力がある人とない人)のプレーヤがいて,影響力のある人が移動できる場合,協力を促進することを示した.またこの時,移動率は中間の値が最も協力を進化させた.
3.5 Aging of Players
最後に考える共進化プロセスは老化.
とても自然なプロセスなのにこれまであまり研究されてこなかった.
最近,McNamara et al., 2008は寿命が協力の進化に重要な役割を果たす可能性を示した(ただし,彼らの主要な興味は好き嫌いの共進化だったが).
さらに,老化に似た概念は投票のモデルにも導入され(Startk et al., 2008a,b),年齢と記憶に依存した遷移率が意見の一致に良い効果があることを示した.
老化が進化ゲームに取り入れられたのはSzolnoki et al., 2009の研究である.
老化は,知識と知恵に関連していて,個体は時間の経過とともにそれを蓄積することができる.
したがって,これは3.3で取り上げた教える能力に対して老化をマッピングした関数を考えることで導入できる.
正確に言うと,式4のw_xをe_x(年齢,整数値)の関数で置き換えれば良い.つまり,年齢が増えると教える能力が上がっていく.w_x=(e_x/e_max)^αと定義し,αは年齢による非対称性を調節するパラメータ.
戦略更新が起こった時も年齢は変わらないままにするルール(ルールA)と,戦略更新が起こった時に年齢をリセットする(e_x=0)ルール(ルールB)が考えられる.
ルールAは社会システムのモデルで,ルールBは生物システムのモデルとみなすことができる(ただし,新しい個体は低い評判を持つと考えればルールBを社会システムを適用することもできる).
2つのルールの違いは小さいように思えるが協力の進化に与える影響は大きいかもしれない.
実際,ルールBがルールAより顕著に協力を促進することがわかった.
これはルールBでは新しい裏切り個体は影響力がない(年齢が若い)ので戦略を広めることができないのに対して,新しい協力の個体は協力-協力リンクによって影響力を増加させる(年齢を増やす)ことができて,協力を保つことができるからである.
3. 6 Related Approaches
その他の上記の枠組みに分類できない共進化ルールはたくさんある.
Kirckkamp, 1999は学習ルールと戦略の共進化を研究した.
Szabó e tl., 2009は戦略更新のフェルミ関数の進化を考えた.
また社会規範との共進化なども考えられている.
Hatzopoulos and Jensen, 2008は非成長ネットワークでの死-生ダイナミクスのモデル,Hamilton and Taborsky, 2005やRankin and Taborsky, 2009らは(ネットワークではなく)グループ構造の共進化,Fort, 2008aは非対称ゲームの進化などを考えた.
4. Conclusions and Outlook
これまで見てきたように戦略だけでなく環境も時間とともに進化するというのは極めて妥当.
中には共進化プロセスの時間が短くて進化の結果に影響を与えないものもあるだろうが,そうでないものももちろんある.
どれか単一の共進化ルールが大事なのではなく,それらの相互作用が協力の進化に重要なのだろう.
そして,共進化ルールの中で結局一時的にしか続かないもの,あるいは永遠につづくものを見極めることも大事.
進化ゲームの応用はRNAウィルス,ATP合成過程,生化学システム,渋滞,気候変動などにも拡張できる.
この意味で共進化ゲームはもっと広い意味で進化ゲームに応用されるべき.
また共進化ルールは社会ジレンマ以外の様々なゲームにも応用されるべき.