【記事更新】私のブックマーク「人工知能とゲーム理論」

私のブックマーク

人工知能とゲーム理論

櫻井　祐子（名古屋工業大学）

1．はじめに

　ゲーム理論は社会科学の一領域であり，計算機科学とは離れた分野と思われるかもしれないが，同じ祖をもつ領域と言って過言でない．John von Neumannはコンピュータの開発に大きな貢献をしたことがよく知られているが，彼はゲーム理論の成立に貢献した人物の一人でもある．人工知能分野においてゲーム理論と最も関係が深い分野はマルチエージェントシステムである．マルチエージェントシステムは複数の自律エージェント間の相互作用に関する研究分野である．1990年代後半から，マルチエージェントシステムの分析や応用にゲーム理論の概念が用いられるようになった．その後，マルチエージェントシステムではゲーム理論的アプローチや経済学的アプローチが主流となり，例えば，2010年代半ば頃のマルチエージェントシステムのトップ国際会議 International Conference on Autonomous Agents and Multiagent Systems（AAMAS）ではゲーム理論関連のセッションが最多となっていた（現在は，マルチエージェント学習のセッションが増加の一途を辿っている）．ただ，人工知能とゲーム理論の融合はマルチエージェントシステムの分野を超えた大きな広がりにならず，限定的と考えられていた時期もあった．しかしながら，近年，人工知能，特に機械学習の公平性が議論されるようになり，機械学習アルゴリズムやデータの評価に，協力ゲームにおける利得の公平配分方法（解概念）の一つであるシャプレイ値（Shapley Value）の適用が広がり，人工知能とゲーム理論の融合が進んでいる．本稿では特に，マルチエージェントシステムと機械学習に関して紹介する．
　本稿では，ゲーム理論的アプローチを検討したい人工知能関連の研究者らを主な対象として，ゲーム理論の入門から，各テーマのサーベイ，ツール，論文などを紹介する．従来と比べ，目的に応じてさまざまな情報源にアクセスすることが格段に容易になっているため，その足掛かりとなるような情報源を提示する．

2．ゲーム理論入門

　ゲーム理論について，書籍だけでなく，サーベイ論文，講義動画など，さまざまな媒体で知識を習得することができる．ここでは，マルチエージェントシステムの研究者によって執筆，作成されたリソースを主に紹介する．ゲーム理論を学ぶうえで計算機科学の側面を踏まえたもののほうが理解が進むと考える．紹介する書籍は，ゲーム理論的アプローチを取っているマルチエージェントシステムの研究者にとってバイブル的存在でもある．

2･1　書籍，オンラインセミナー（英語）
  • Multiagent Systems Algorithmic, Game-Theoretic, and Logical Foundations：マルチエージェントシステムの教科書であるため，分散制約充足や分散最適化など，マルチエージェントシステムの研究テーマも含まれているが，ゲーム理論の説明が充実している．また，ゲーム理論と関連が深い社会選択理論（Social Choice Theory）も紹介されている．著者のKevin Leyton-Brownは，彼の論文で提案したアルゴリズムを Open-Source Software Projectsとしてホームページでリスト化して公開している．
  • Algorithmic Game Theory：ゲーム理論アルゴリズムの理論解析について勉強したい人向けの書籍である．どちらかといえば，専門家向きである．著者のTim RoughgardenのAlgorithmic game theoryのLectureも勉強になるであろう．講義はスライドを使わず，黒板を使用するスタイルである．
  • Handbook of Computational Social Choice：社会選択理論についての書籍である．投票やランキングなどにおける意見集約方法などについて書かれている．著者のUlle Endrissは，国際会議でゲーム理論や社会選択理論に関するチュートリアルを行っており，ホームページにスライドが公開されている．また，彼の社会選択理論のLectureも参考になる．
  • Online Social Choice and Welfare Seminar Series：2020年より2週間に一度，社会選択理論を中心とした専門家らによってオンラインセミナーが行われている．これまでの講演動画やスライドなども公開されている．最新の研究動向を把握するのに適している．
2･2　サーベイ，オンライン講義（日本語）

3．マルチエージェントシステムとゲーム理論

　本誌 Vol.18, No.4（2003年 7月号）の「私のブックマーク」で伊藤孝行先生によるマルチエージェントシステムが掲載され，ゲーム理論についても触れられている．それから20年経過したが，いまだ，マルチエージェントシステムではゲーム理論に関する研究は主要テーマの一つである．20年前と大きく異なるのは，開発されたメカニズムやアルゴリズムの実社会応用が進んだこと，協力ゲームに関する研究が増えたこと，また，マルチエージェント（深層）強化学習の研究の活発化に伴って，ゲーム理論的アプローチを用いたマルチエージェント強化学習に広く関心をもたれるようになったことがあげられる．なお，マルチエージェント強化学習は，次章にて説明する．

3･1　メカニズムデザイン（マーケットデザイン）

　メカニズムデザインとは，異なる目的をもつ複数の参加者が存在する環境において，何らかの望ましい性質をもつ社会的意思決定のルールや制度を設計することを目的とする．近年，より実践的な側面を重視する領域として，マーケットデザインが注目されている．国内では，2020年に東京大学マーケットデザインセンターが設立された．（国研）科学技術振興機構研究開発戦略センター（JST CRDS）による「研究開発の俯瞰報告書システム・情報科学技術分野（2021年）」における，2.1人工知能・ビッグデータおよび2.3.4 メカニズムデザインでは，研究動向も含めてメカニズムデザインの紹介が行われている．
　メカニズムデザインに関するサーベイは数多く存在するが，ここでは，Explainability in Mechanism Design： Recent Advances and the Road Aheadを紹介する．このサーベイでは，メカニズムデザインにおける説明可能性の目的を明らかにし，一般的な人工知能における説明可能性とメカニズムデザインにおける説明可能性の違いなどを示している．著書のSarit Krausはマルチエージェントシステムの代表的な研究者である．
　メカニズムデザインは人手で行われることがほとんどであったが，深層学習の発展に伴って，深層学習を応用した自動メカニズムデザインという技術が最近のトレンドの一つである．これまで，自動メカニズムデザイン（Automated Mechanism Design）のアイディアはTuomas Sandholmによって古くから提案されていたが，混合整数計画問題として定式化することが主流であったため，スケーラビリティに課題があった．その課題を克服する手段の一つとして，深層学習の適用が行われ，Optimal Auctions through Deep Learning，Automated Mechanism Design via Neural Networksなどが先駆けの論文として有名である．また，New Frontiers of Automated Mechanism Design for Pricing and Auctionsは，チュートリアル動画としてお薦めである．
　メカニズムデザインに特化したツールは普及していないが，社会シミュレーションの一つである NetLogoでは，ゲーム理論を用いたエージェントベースのモデルを構築することができる．ゲーム理論に関連した拡張機能やサンプルモデルも提供されている．

3･2　協力ゲーム理論

協力ゲーム理論の教科書としてお薦めしたいのは，Computational Aspects of Cooperative Game Theoryである．マルチエージェントシステムの研究者らが著者となっており，170ページ程度の分量で，協力ゲーム理論の基礎概念だけでなく，協力ゲーム理論における計算量に関する課題などが示されている．また，Cooperative Game Theory Tutorialは，この本をもとにしたチュートリアル資料であり，参考にするとよい．
　協力ゲーム理論において，マルチエージェントシステムの研究者らの最近の主な研究テーマは，エージェントをどのように分割するか（提携構造形成問題），エージェント間で財や利益，コストを公平に配分するにはどうすればよいか（公平分割問題）である．特に，近年は，公平分割問題に関する研究が盛んに行われている．提携構造形成問題に関するサーベイでは，Coalition structure generation: A surveyが有名である．一方，公平分割問題では，Online Fair Division: A Survey，Fair Division of Indivisible Goods: A Surveyなどがある．
　公平分割問題に関して，五十嵐歩美先生が NHKの番組“公平な分担って何？” 家事育児に役立つ『アプリ開発』に密着に出演し，開発された家事分担コンシェルジュなどの紹介を行っている．

4．機械学習とゲーム理論

4･1　機械学習全般

　機械学習は人工知能の各分野の中では，ゲーム理論との関連は比較的少ないとこれまでは考えられてきたが，機械学習が社会に実装されるにつれて，ゲーム理論的な考慮が必要となってきている．一つは，非協力ゲーム的な取扱いであり，複数のエージェントが相互作用をしながら学習するマルチエージェント強化学習などがある（マルチエージェント強化学習については，以下で詳しく関連リソースについて紹介する）．別の非協力ゲーム的な状況としては，敵対的な環境下における機械学習を扱う敵対的機械学習（Adversarial Machine Learning）があり，機械学習を用いたシステムのセキュリティを考えるうえで重要である．ここでは，データを正しく分類できるように学習しようとする学習者と，学習者に誤分類をさせようとする敵対者の 2プレーヤのゲームとして定式化される．敵対的ゲームにおけるゲーム理論的取扱いについてまとめたサーベイとしては，A Survey of Game Theoretic Approaches for Adversarial Machine Learning in Cybersecurity Tasksがある．もう一つは，協力ゲーム的な取扱いであり，Shapley値に代表される協力ゲームの概念が，特徴選択やデータの価値評価，連合学習，マルチエージェント強化学習などの機械学習のさまざまな場面に適用されている．機械学習におけるShapley値の利用に関する全体的なサーベイは，The Shapley Value in Machine Learningがある．また，最近活発に研究されている連合学習におけるシャプレイ値の取扱いは A Comprehensive Survey of Incentive Mechanism for Federated Learningでも紹介されており，さらにこのサーベイでは連合学習におけるオークションなどの非協力ゲームの適用についても述べられている．

4･2　マルチエージェント（深層）強化学習

　強化学習の研究の多くはシングルエージェント環境を対象としているため，強化学習の教科書でゲーム理論について触れられているものは数少ない．その中で，Reinforcement Learning State-of-the-Artの 14章 Game Theory and Multi-agent Reinforcement Learningでは，ゲーム理論に基づいた基本的な学習フレームワークの紹介など，基礎的な事項から紹介されている．Q学習とゲーム理論の概念を組み合わせた，基本的な学習アルゴリズムとして，Max-Min戦略を用いたMax-Min Q-learning，ナッシュ均衡を用いたNash Q-learningがある．MaxMin／ナッシュ均衡を見つけることを目的として，それぞれの戦略の原理に基づいてQ値を更新していく．また，最近のものとして，Handbook of Reinforcement Learning and ControlのMulti-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithmsで，ゲーム理論的アプローチが詳しく説明されている．
　マルチエージェント（深層）強化学習のサーベイからひも解くのもよい．A survey and critique of multiagent deep reinforcement learningは，350件超の文献を引用し，ゲーム理論的アプローチだけでなく，最近のマルチエージェント（深層）強化学習に関する研究動向を紹介している．ゲーム理論的アプローチのサーベイとしては，An Overview of Multi-Agent Reinforcement Learning from Game Theoretical Perspectiveがある．
　マルチエージェント強化学習が世間で注目されるようになったエポックメーキングな出来事は，AlphaGoやポーカーといったゲームで人間に勝利したことであろう．ポーカーについて，Scienceの記事 Superhuman AI for multiplayer pokerが読みやすいかと思う．ここ数年，マルチエージェント（深層）強化学習に関する論文が多数発表されているが，新たな興味深い方向性を示す論文の一つとして，DeepMindの研究者らによる Multi-agent Reinforcement Learning in Sequential Social Dilemmasを紹介したい．ここでは，社会的ジレンマはエージェントの行動選択が時間的に広がりをもつことに着目し，ジレンマの概念をマルコフゲームに拡張している．社会的ジレンマは，ゲーム理論で「囚人のジレンマ」や「共有地の悲劇」などのゲームで表現され，分析されている．マルチエージェント強化学習においても長年の研究対象である．
　代表的な強化学習のベンチマークは OpenAI Gymであるが，残念ながらシングルエージェントがメインである．マルチエージェント強化学習のベンチマークは研究の加速に従って，ここ最近，増えてきている．例えば，PettingZooは，OpenAI Gymの多くの機能を継承しつつ，マルチエージェント環境を提供している．詳しくは PettingZoo: Gym for Multi-Agent Reinforcement Learningを参照されたい．
　DeepMindによる Melting Potは，社会的ジレンマ，リソース共有，タスク分割などのシナリオを提供するマルチエージェント環境を提供している．こちらは，Scalable Evaluation of Multi-Agent Reinforcement Learning with Melting Potに詳しく紹介されている．また，Hanabi Learning Environmentも有用なベンチマークの一つである．Hanabiに関して，本誌 Vol.35, No.3（2020年 5月号）「Hanabi コンペティション─不完全情報下における相互協力─」の記事が興味深いので一読されるとよい．

5．国際会議・国内研究会

　これまでも，Association for the Advancement of Artificial Intelligence（AAAI），International JointConferences on Artificial Intelligence（IJCAI），European Conference on Artificial Intelligence（ECAI），The Pacific Rim International Conference on Artificial Intelligence（PRICAI）といった人工知能全般を対象とする国際会議では，マルチエージェントシステムのセッション以外でもゲーム理論の概念を応用した論文発表があったが，ここ数年，Neural Information Processing Systems（NeurIPS），International Conference on Machine Learning（ICML）などの機械学習の国際会議でゲーム理論や社会選択理論に関する論文が増えている．一方で，マルチエージェントシステムの国際会議では，機械学習とゲーム理論を融合した論文が増えている．ここでは，マルチエージェントシステムを中心として，関連する国際会議について紹介する．

5･1　国際会議
5･2　国内研究会

6．おわりに

　機械学習技術の発展に伴い，人工知能分野でこれまで遠い関係と思われていた技術の間で融合が行われている．ゲーム理論も人工知能技術との関係がよりいっそう深まると考える．本稿が，ゲーム理論的アプローチに興味をもつ人工知能の研究者にとってゲーム理論への入口となれば幸いである．

謝　辞

本稿を執筆するにあたり，理化学研究所の波多野大督研究員，名古屋工業大学の森山甲一准教授に多大なるご協力をいただきました．感謝いたします．