Vol.31.No.3(2016/5)進化ゲーム(Evolutionary Games)


私のブックマーク

進化ゲーム(Evolutionary Games)

一ノ瀬 元喜(静岡大学 学術院工学領域)

はじめに

相手がある行動をとるとき,自分はどの行動をとるのが最適か,ゲーム理論では行為者の合理性を仮定した上でこれを分析します.
一方,進化ゲームでは,基本的に集団を考え,その中で時間がたった時に,結果的に点を多く稼いだ者が広まることを仮定します.これは,微分方程式を解いたり,計算機で進化のシミュレーションをすることで分析できます.
後者はエージェントベースのモデルが構築されるため,人工知能の研究者にとっても親しみやすいものではないかと思います.
ゲーム理論では均衡の分析に主眼が置かれますが,進化ゲームでは均衡だけではなく戦略の進化の過程,つまりダイナミクスにも注目することが特徴です.

以下ではまず進化ゲームを学ぶにあたって役立つ入門やレビューを紹介します.
その後,進化ゲームの研究に役立つツールなどの情報を示し,関連学会,ジャーナルと続き,最後に最近の研究動向について記します.進化ゲームに興味のある読者の方々の役に立てば幸いです.

進化ゲーム入門

まずは進化ゲームについて学べる情報の紹介です.Webサイトと動画を紹介します.
進化ゲームというのは何か,また共通する問題意識は何かというのが伝わればと思います.

Why we cooperate (1:06:00)

協力進化研究の第一人者ハーバード大学Martin Nowak博士による協力進化の講義動画です(英語).
繰り返し囚人のジレンマゲームのノイズあり環境で,よく知られたしっぺ返し戦略よりも強力なパブロフ戦略,協力して良い評判を得た人が協力されやすい間接互恵性,近所付き合いが協力を促進する空間互恵などについて詳しく解説しています.
協力の進化だけではなく最後通牒ゲームを使った公平性の進化まで幅広いトピックを扱っています.
Nowak博士による動画は他にもいくつか公開されているので勉強には便利です.

夏休み講座 進化ゲーム入門

帝京大学大浦宏邦先生による進化ゲームの入門です.進化ゲーム理論研究会(現在は活動休止)のWebサイトのコンテンツの1つです.
大浦先生の社会科学者のための進化ゲーム理論も数式を丁寧に追っており,読みやすい本です.

shorebird 進化心理学中心の書評など

進化心理学中心の書評となっていますが,国内外の進化ゲームの本,進化ゲーム関連の最新の論文の解説,進化ゲームに関連する学会やセミナーの発表などかなり詳しい情報が載っています.
日本語で読めるとても有益なWebサイトです.

Evolutionary Dynamics: Exploring the Equations of Life

Nowak博士による本格的な進化ゲームの教科書です.進化ゲームについて体系的に学べます.
同時にこれまでのNowakグループの研究の流れも分かります.
日本の数理生物の先生方が翻訳された日本語版の進化のダイナミクス 生命の謎を解き明かす方程式もあります.

教科書

定番の教科書としてはEvolutionary Game TheoryEvolutionary Games and Population Dynamicsもあります.進化ゲームと微分方程式は後者の日本語版です.

レビュー・サーベイ

進化ゲームに関するレビューやサーベイはいくつもあると思いますが,著者が最近参考にしたものを紹介します.

Five rules for the evolution of cooperation

Nowak博士は協力の進化のためのメカニズムとして血縁選択,直接互恵,間接互恵,ネットワーク(空間)互恵,グループ(マルチレベル)選択の5つのルールを挙げ,どのルールからも単純な条件で協力が進化できるかどうかを判定できることを示しました.
協力進化の研究でよく引用されている文献です.

Human cooperation

Nowak博士のところにいたイェール大学David Rand博士とNowak博士によるヒトの協力についてのレビューです.
上の5つのルールをまず紹介し,それぞれのルールに対する実証実験を詳しく解説しています.

Coevolutionary games – a mini review

スロベニア・マリボル大学のMatjaz Perc博士とハンガリー科学アカデミーのAttila Szolnoki博士は協力/裏切りの戦略と同時に他の性質(相互作用ネットワーク,繁殖能力,評判,移動性,年齢など)も同時に進化するという共進化ゲームが協力をさらに促進させると提唱し,その考えに基づく多くの結果を精力的に発表しています.
著者らもこの共進化ゲームの移動性に注目し,裏切りを感知して遠くに逃げる戦略が協力を促進することを示しました(Ichinose et al., 2013).

Evolutionary dynamics of group interactions on structured populations: a review

Perc博士らによる空間構造上での公共財ゲームの進化ダイナミクスのレビュー.
格子空間,ネットワーク,上記の共進化ゲームの条件の下で,協力がどのように進化するかを議論しています.

Evolutionary games on graphs

ハンガリー科学アカデミーのGyorgy Szabo博士Gabor Fath博士によるネットワーク上の進化ゲームの分厚いレビュー.
ゲーム理論の用語の解説から始まり,進化ゲームの進化的に安定な戦略,レプリケータ方程式の説明,そしてネットワーク上の進化ゲームへと展開しています.

Evolutionary game theory using agent-based methods

まだどこにも出版はされていないようですが,アメリカ・ミシガン州立大学のChristoph Adami博士らがエージェントベースの進化ゲームのモデルの構築方法などを書いたレビューをarXivに出しています.
微分方程式のモデルでは扱えない記憶などが入った複雑な戦略のモデル化にエージェントベースモデルは利があるとしています.

ネットワーク上の進化ゲーム(<特集>繋がりの科学)

イギリス・ブリストル大学の増田直紀先生による複雑ネットワーク上の進化ゲームの紹介記事です.
複雑ネットワーク出現以前は,空間構造と言えば正方格子空間が主に考えられてきましたが,
ネットワーク科学の発展により,スモールワールドネットワーク,スケールフリーネットワークなどが発見されると
より現実に即した「ネットワーク上の進化ゲーム」の研究が広く展開されるようになりました.
スケールフリーネットワークが協力を強力に促進するという最初のインパクトはポルトガル・リスボン大学の
Francisco Santos博士とポルトガル・ミーニョ大学のJorge Pacheco博士の論文(Santos & Pacheco, 2005)ですが,増田先生はゲーム参加(あるいはリンクを持つこと)にコストがかかる場合,スケールフリーネットワークは協力を促進しないことを示しました.その論文(Masuda, 2007)の日本語での解説もこれに載っています.

研究に役立つ情報

進化ゲームについて理解が深まったら,自分で手を動かして研究してみたくなりませんか.ここでは基本的な研究のやり方と役立つツールを紹介します.

研究手法
紙とペンとMathematica

空間構造がなく単純な戦略だけの時間変化のモデルは微分方程式だけで表現することができるでしょう.
この場合,モデルを考え,微分方程式を立て,それを解く,あるいは平衡点での安定性などを分析します.
したがって,数学が得意な人なら紙とペンだけでできるでしょう.
あるいはMathematicaに解くのを手伝ってもらいましょう.
式を解くのはBerkeley Madonnaというソフトもあります.

数値シミュレーション

微分方程式が解析的に解けない場合,数値計算の結果でも十分な場合があります.
微分方程式を数値的に解く最も単純な方法は,オイラー法です.
十分小さいΔtを使って,Δt後の時間変化をプログラムなどで逐次計算していきます.
もっと精度の良い数値計算が必要な場合には,常微分方程式の数値計算法などをご覧ください.

エージェントベースモデル(個体ベースモデル)

エージェント(プレーヤ,個体)の戦略あるいは相互作用の環境が複雑で数式に落とせない場合,エージェントベースモデルの出番です.
しかし,進化ゲームのモデルはそんなに複雑ではありません.
エージェントの戦略を定義し,他個体とゲームして得点を計算し,うまくいっている戦略を真似するというのが基本的なアルゴリズムですので,多くても数百行のコードで済むと思います.
そのためか特別なツールなどは使わず,C言語,C++,Java,Pythonなどを使って一から作る人が多いようです.
海外ではMatlabを使っている方も多い気がします.
あとは計算機で進化シミュレーションを走らせて結果を分析します.
ただし,ネットワーク上のゲームなど,空間構造を必要とする場合は,一から書くより以下のツールなどを使う方が楽です.
ツール
Dynamo

Mathematicaで得られた進化ダイナミクスの結果をきれいに可視化するためのソフトです.
論文に引用されていることも多く,使われているようです.

Python+NetworkX

上記のように進化ゲームのエージェントベースモデルは特別なツールを使わずにできることが多いのですが,“ネットワーク上の進化ゲーム”には著者はPython+NetworkXという組み合わせをやることがあります.
スケールフリーネットワークなど複雑ネットワークを生成するアルゴリズムは比較的単純ですが,それでもそれが簡単にできると楽です.たとえばBarabasi-AlbertスケールフリーネットワークをNetworkXで生成するには,barabasi_albert_graphという関数を使えば1行でできてしまいます.あとはその上で動くゲームと戦略の進化の部分をPythonで書くだけで進化モデルの出来上がりです.難点はノード数や平均次数が多いと計算に時間がかかることです.

PyCX

アメリカ・ニューヨーク州立大学ビンガムトン校の佐山弘樹先生が管理されているPyCXはPythonで書かれた複雑系シミュレーションのサンプルコード群です.
複雑系科学に関する様々なコードのサンプルがありますが,進化ゲームには
力学系,動的ネットワーク,エージェントベースモデルのサンプルが参考になります.
サンプルコードから改変していくことでプログラミングになれていない人でも
様々なモデルが作れます.
またその目的にも書いてある通り,複雑系科学の教育用としても使えます.
より詳細は佐山先生が書かれたPyCXの紹介記事をご覧ください.
PyCXは複雑系のモデル化と分析に関する佐山先生の教科書(公開中)でも使用されています.

NetLogo

NetLogoはエージェントベースモデルの開発環境です.
エージェントベースモデルのモデリング環境には様々なものがあります(サーベイを参照)が,
NetLogoは豊富なサンプルがあり,そのサンプル全てにコードがついているので,
それらを参考にしながら独自のモデルを作れるところにメリットがあると思います.

R+RStudio

エージェントベースモデルのシミュレーション結果に対して統計解析をするときの組み合わせの1つとしてRとRStudioのセットはいかがでしょうか.
解析用プログラムをシミュレーション本体に書く,あるいはデータを処理するシェルスクリプトを別に作るというやり方もあると思いますが,Rを使えば結果に対して高度な統計解析を施すことができます.
ネットワークの進化ゲームにおいてネットワークをRで分析したい場合はigraphというパッケージが便利です.
使い方の詳細はR+igraph – supplementary informationをご覧ください.
私のブックマーク 複雑ネットワーク(Complex network)にも紹介されています.

学会・研究会・国際会議

研究成果がまとまったら発表です.進化ゲームを主に扱う学会としては,ゲーム理論,数理生物・数理社会,複雑系科学,進化心理学などがあると思います.以下ではそれらを順に紹介します.

経済学(ゲーム理論)系
Game Theory Society

ゲーム理論の国際的な学会組織です.Conferencesのリンクから関連する国際会議の情報が見れます.
多くの国際会議で進化ゲームが中心テーマの1つとして扱われています.

ゲーム理論ワークショップ

理論経済系と理論生物系の両方から国内の著名な方々が集まるワークショップです.
毎回,進化ゲームに関する講演も多く発表されています.
「ゲーム理論」をキーワードに様々な分野の方々が集まる興味深いワークショップです.
著者自身はまだ1度も参加したことがないので,近いうちに参加したいです.
数理生物・数理社会系
Society for Mathematical Biology

数理生物の学会組織です.数理生物系は進化ゲームの研究者が多くいらっしゃいます.メーリングリストSMB Digestでも関連する国際会議の情報などが流れてきます.

日本数理生物学会

数理生物学会の国内の学会組織です.最近では上記のアメリカ,あるいは中国,韓国の数理生物学会と合同で国際学会を開いているようです.
日本には進化ゲームを精力的に研究されている方も多く,進化ゲーム関連の特別セッション/ワークショップなども学会の中で開催されています.
メーリングリストbiomath-MLは会員以外でも参加でき,進化ゲーム関連のセミナーなどの情報も多く流れてきます.

ダーウィンセミナー

協力進化の研究で顕著な業績を残しておられる総研大の大槻久先生が主宰されている
生物学を中心とした幅広い分野のセミナーです.
進化ゲーム系の講演が多く行われています.

数理社会学会

前述の進化ゲーム理論研究会の方々が多く関連している数理社会の学会組織です.
大会では進化ゲーム系の発表も行われます.

社会の数理セミナー

協力進化の研究で顕著な業績を残しておられる東工大の中丸麻由子先生が主宰されている社会に関する数理モデルやシミュレーションの話が聞けるセミナーです.
進化ゲーム系も多く発表されています.

複雑系科学,ネットワーク科学
International Society for Artificial Life

人工生命の学会組織です.
国際会議International Conference on Artificial Life (ALIFE)European Conference of Artificial Life (ECAL)を毎年交互に開催しており,エージェントベースモデルを中心にした
進化ゲームの講演が毎回発表されます.
ALIFE 13ではAdami博士による進化ゲームのチュートリアルもありました.

Complex Systems Society

複雑系全般の学会組織です.2014年まではヨーロッパで国際会議The Conference on Complex Systems (CCS)が開催されていましたが,2015年は初めてアメリカで開催されました.
2016年は再びヨーロッパで開催されます(CCS 2016).
範囲は広いですが,進化ゲームに関する発表も行われています.

NetSci

ネットワーク科学の国際的な学会組織です.ネットワーク上の進化ゲームの発表などが行われます.

ネットワーク科学国内

日本ソフトウェア科学会のネットワークが創発する知能研究会情報処理学会のネットワーク生態学研究会でネットワーク上の進化ゲームの発表が行われます.
進化心理学系
Human Behavior and Evolution Society

進化心理学の国際的な学会組織です.心理実験だけでなく,ヒトを対象とした進化ゲームの発表もされます.
HBES conferenceが年次会議です.

日本人間行動進化学会

進化心理学の日本の学会組織です.HBESと同じく心理実験だけでなく,ヒトを対象とした進化ゲームの発表もされます.

ジャーナル

最後の仕上げは論文投稿です.
進化ゲームが取り上げられるジャーナルは数多くあると思いますが,著者が知る代表的なジャーナルをあげます.
様々な分野に広がっているのが特徴です.

ゲーム理論系
Games and Economic Behavior

Dynamic Games and Applications
理論物理・生物系
Physical Review E

New Journal of Physics

EPL

Physica A

Proceedings of the Royal Society of London B

Journal of Theoretical Biology

Theoretical Population Biology

PLOS Computational Biology
複雑系
Artificial Life

BioSystems

JASSS
進化心理学系
Evolution and Human Behavior

研究動向

最後に進化ゲームの研究動向について触れておきます.
繰り返し囚人のジレンマゲーム(IPD)においては2012年に発見されたzero determinant(ZD)戦略(Press & Dyson, 2012)が契機となり,盛んに研究されています.
ZD戦略を用いるとIPDにおいて相手の戦略に関わらず相手の利得の期待値が決定できる戦略を選ぶことができます.
ZD戦略が進化的に強いのかは進化ゲームで研究されています(Hilbe et al., 2013Stewart & Plotkin, 2013Adami & Hintze, 2013など).

進化ゲームは協力の進化だけではなく最後通牒ゲームを用いた公平性の進化(Nowak et al., 2000など),ワクチン接種ゲーム(Fu et al., 2010など),気候変動のジレンマ(Pachecoらによるレビュー)にも応用されています.
公平性進化で不平等回避行動が脳の報酬系に影響を与えることが知られており(Tricomi, 2010),今後神経科学との結びつきも強まっていくでしょう.

一方で,Rand博士は協力の進化について進化ゲームのモデルベースと実証実験を組み合わせて精力的に研究しています.実証実験は低コストで大規模な実験ができるAmazon Mechanical Turk(AMT)などを使ったオンライン実験を勧めています.

Rand博士によるAMTを使ったオンライン実験紹介の音声動画(3:51)

Rand博士によるAMTを使ったオンライン実験紹介の紹介論文(J. Theor. Biol.)

スペインのマドリード・カルロス3世大学のAngel Sanchez博士らもヒトを使った実証実験などとモデルベースの研究を組み合わせています.
またサイバーエージェントの高野雅典さんはソーシャルゲームでいかに協力が成立するかをビッグデータ解析により調べています.
このように,今後は理論だけではなく実証の結果と比較することで,実際の人間社会で協力を促進する本当に重要な要素は何かが明らかになってくると考えられます.

その他の応用としてはメカニズムデザインで考えている資源配分の制度設計なども考えられるでしょう.
ゲーム理論は与えられたルールの中での行動を分析しますが,メカニズムデザインではそのルール自体を設計します.
ルールを与えれば,それにより協力的な社会が生まれるかどうかが進化ゲームにより明らかになるため,
理論上は様々なルールを考えて試すことができます.
今後このような研究が増えてくるかもしれません.
メカニズムデザインの入門は以下が参考になります.

メカニズムデザイン(基礎編)

名古屋大学の有田隆也先生鈴木麗璽先生の研究室はゲーミフィケーションに基づき,ポイント制と評判を結び付け,間接互恵を促進するシステムを提案するなど,ゲーム論的な知見や概念を実世界に生かす取り組みをしています(大門ら, 2014).

おわりに

進化ゲームに関する関連情報を紹介しました.
ここに挙げた情報は私の専門分野に起因して偏りがあり,
他の分野から進化ゲームに取り組んでいる方から見れば,カバーできていない部分も多いと思います.
その辺りはご容赦ください.
既に卓越した研究を行われている日本人が多くいらっしゃいますが,本記事が日本でのさらなる進化ゲーム研究者人口の増加の一助になれば幸いです.

謝辞

本稿執筆にあたりコメントをいただきました伊東啓氏,里谷佳紀氏,佐山弘樹氏,鈴木真介氏,鈴木麗璽氏,高野雅典氏,守田智氏に深く感謝いたします.