研究紹介

  • 担当教員: 金澤 尚史 講師  [E-mail]
  • マルチエージェントシステムのためのゲーム理論

    互いに異なる目的を持ち、相互作用しながら意思決定する複数のエージェントからなる複雑システムをマルチエージェントシステムと呼びます。複数の人々や企業、国々が相互作用する社会システムや、複数の制御器によって自律分散的に制御される分散制御系と呼ばれる工学システム等もその一種とみなすことができます。マルチエージェントシステムにおいて、エージェント間の相互作用を分析するためにゲーム理論が用いられます。ゲーム理論では、意思決定を行うエージェント「プレイヤー」、各プレイヤーのとりうる行動「戦略」、選択された戦略によって決まる結果に対する各プレイヤーの評価「利得」の3つの要素で、複数のエージェントの相互作用を数学的に記述します。このモデルを用いて、プレイヤー間の相互作用が各プレイヤーの行動に及ぼす影響を分析したり、各プレイヤーのとるべき行動を分析したりするのがゲーム理論です。本研究室では、マルチエージェントシステムの解析と制御、設計の観点から、ゲーム理論に関する以下のような研究を行っています。

    (1)複数の利得基準を持つプレイヤーによるゲーム

    ベクトル利得を持つゲームと調停に基づくゲーム

    従来のゲーム理論では、各プレイヤーは単一の利得基準に基づいて最適な戦略を選択しようとします。しかしながら、政府や企業などの組織が意思決定を行う場合、複数の下部組織(部署)の意見を考慮し、様々な利得基準に基づいて最終的な決定が行われるのが普通です。また個人における意思決定に関しても同様に、複数の利得基準を総括して意思決定を行うことが多々あります。例えば、囚人のジレンマと呼ばれる有名な例題では、2人の囚人が禁固刑の長さのみを基準にして互いに「協力」もしくは「裏切り」を決定しますが、実際には刑の重さだけでなく、自分が「裏切り」を選択することによって相手によってなされるであろう報復という異なる観点も考慮する必要があると考えられます(図3)。

    そこで本研究室では、各プレイヤーが複数の利得基準に基づいて意思決定を行う多目的ゲームと呼ばれるゲームについて研究を行っています。本研究室で扱う多目的ゲームには以下の2種類があります。

    • a)各利得基準に関する利得を要素とするベクトルを直接比較することで戦略を決定するプレイヤーによるゲーム(図3左)。
    • b)利得基準ごとに戦略を決定し、それらの戦略を調停することで最終的な戦略を決定するプレイヤーによるゲーム(図3右)。

    特にb)のゲームは本研究室の新しく提案したゲームです。これらのゲームの性質を明らかにすることによって、従来のゲーム理論によって扱われてきた問題よりも、より多様な問題を扱うことができるようになると考え、研究を進めています。

    複数の利得基準を持つプレイヤーによるゲーム

    ベクトル利得に基づくゲームにおける進化的安定性

    多数のプレイヤーからなるマルチエージェントシステムにおいて、集団内のすべてのプレイヤーがある戦略(既存戦略)をとっているときに、異なる戦略をとるプレイヤーが現れたとしても既存戦略によって淘汰されてしまうとき、この既存戦略は進化的に安定であると言います。進化的安定性は元々、生物学の自然淘汰の考え方をゲーム理論に導入したものですが、プレイヤーが試行錯誤によって戦略を選択するような社会システムやユーザが利己的に振る舞う工学システムに対しても導入され、非常に重要な概念となっています。しかし、これまでの進化的安定性の研究のほとんどは、利得基準が一つの場合を対象に行われてきました。そこで本研究室では、単一利得基準で提案された進化的安定性を、ベクトル間の順序関係を導入することで、利得基準が複数のベクトル利得に基づくゲームに対して拡張する研究を行っています。

    (2)税と補助金を用いたマルチエージェントシステムの制御

    マルチエージェントシステムにおいては、各プレイヤーが自分自身の利益のみを追求して行動することによってシステム全体としては望ましくない状態に陥ってしまうことがあります。これは、社会システムにおいて社会ジレンマとして知られる現象です。このような場合には、各プレイヤーが利己的に行動したとしてもシステム全体にとって望ましい状態が実現されるような制度設計が非常に重要となります。

    税と補助金を用いたマルチエージェントシステムの制御

    本研究室では、相互作用しながら戦略を変更していく多数のプレイヤーからなるシステムにおいて、プレイヤーの戦略分布(集団状態)の時間変化をレプリケータダイナミクスと呼ばれる微分方程式でモデル化し、各プレイヤーに税と補助金を課すことで、システム全体として望ましい状態を実現する手法について研究してきました(図4)。このプレイヤーの集団と、税と補助金を課す「政府」との関係をシステム制御の観点から見直すと、状態フィードバック制御系ととらえることができます。このシステム制御の考え方を導入することで、目標状態を実現するのに十分な税と補助金の条件について明らかにしています。

    (3)ポテンシャルゲームを用いたマルチエージェントシステムの設計

    大規模な複雑システムにおいては、システム全体の大域的な情報を収集することや、その情報を元にシステム全体を中央集権的に制御することが非常に困難となります。そこで、局所的な情報を元に複数の制御器によって自律分散的にシステムを制御する必要があります。一方、ポテンシャルゲームと呼ばれるゲームは、各プレイヤーが自身の利得が良くなるように戦略を変更すると、ポテンシャル関数と呼ばれる関数の値も大きくなるという性質を持つ特殊なゲームです。このため、システム全体の目的関数をポテンシャル関数とするポテンシャルゲームとなるようにプレイヤーの利得を設計することで、各プレイヤーが自身の利得のみを考慮して利己的に行動するだけで全体の目的が達成できる、マルチエージェントシステムを設計することができます。このため、並列処理におけるジョブスケジューリング、無線ネットワークにおけるチャンネル割り当てや干渉回避、エネルギーネットワークにおける電力配分等、様々な工学システムに対して応用されています。本研究室では、与えられた全体の目的関数からポテンシャルゲームを構成し、分散的に目的を達成するマルチエージェントシステムの設計問題について研究を進めています。

    (4)メカニズムデザインによるルール設計

    複数の企業がサーバを共有する場合や、ある工学システムの利用者の利害関係が対立する場合等、その利用方法を決める問題やリソース配分問題は、マルチエージェントシステムとしてモデル化することができます。このようなシステムにおいては、あるプレイヤーが自分自身の利益を増加させようと、必要以上にサーバを占有したり、実際に必要な量より多くのリソースを要求したりすることで、全体の利益や公平性が損なわれてしまう場合が有ります。このような場合には、各プレイヤーが嘘をついたりずるをしたとしても得することがないような、使用権付与やリソース配分のルール設計が非常に重要となります。

    プレイヤーが利己的に行動する状況において実現される状態が、システム全体にとって望ましい状態と一致するように適切なルールを設計するための理論としてメカニズムデザインがあります。2007年には、メカニズムデザインの基礎理論の確立を理由としてLeonid Hurwicz、Eric Maskin、Roger Myersonが、2012年にはメカニズムデザインの一種である安定配分の理論とマーケットデザインの実践を理由としてLloyd ShapleyとAlvin Rothが、それぞれノーベル経済学賞を受賞するなど、近年注目を集めています。特に安定配分の理論やマーケットデザインは、アメリカの高校選択や日米の研修医と研修先のマッチング等実社会で利用されていて、大きな成功を収めています。また、経済学の分野だけでなく工学の分野でも、電子商取引やネットオークション、タスクスケジューリングやネットワークの帯域割り当て等への応用研究が盛んに行われるようになってきており、本研究室でも研究に取り組み始めています。

    ページの先頭へ