マルチエージェント合意形成のための回覧板プロトコル
北村泰彦

横尾真
年月

桑原和宏
日

計算機が利用者のエージェント（代理人）として他のエージェントと様々な取引や交渉を行うエージェ
ントネットワークにおける基本機能として合意形成がある．本論文では，エージェントの効用を考慮した合意形成問題を取り上げ，エージェントの効用が他エージェントの表明により変化する場合を扱う．この問題に対処するために，表明を繰り返し行うプロトコルを提案し，エージェントの表明が収束するかどうかついて議論する．またエージェント間で一巡の表明収集を行うプロトコルとして，一極集中型，二分木集中型，同報型，回覧板型を取り上げ，他エージェントの表明参照度とデッド ロックに関して回覧板型が最適であることを示す．

はじめにインターネットをはじめとする計算機ネットワーク技術の進歩により，多様で多数の計算機が相互に結合されるようになった．計算機はもはやその計算能力だけでなく，地理的に分散している利用者の協調の道具として利用されるようになってきている．そのような場合，計算機はその利用者のエージェント（代理人）としてふるまい，必要に応じて他のエージェントと交渉するような能力が期待される．この種のエージェント はソフトウェアエージェントと呼ばれ，近年注目が集められている．さらにソフトウェアエージェントと高速ネットワークからなるエージェントネットワークを用いることにより，利用者の距離的障壁を克服する新しい共同体であるテレオーガニゼイションの研究も始められている．

合意形成はエージェントネットワークにおける基本的な機能の一つである．代表的な例としては会合スケジューリング問題があげられる．この問題において，エージェントはその利用者のスケジュールを管理しており，日時や出席者など会合に関する利用者の好み（効用）を知っている．エージェントは利用者の好みを反映するように会合スケジュールを他エージェントと調整する．
分散人工知能の分野ではマルチエージェント合意形成問題に関する多くの研究がなされてきた．交渉は合意形成のための代表的な技法である．例えば，契約ネットプ ロトコル
エージェント間の合意形成プ ロトコルと見なすことができ，スク割当，運搬問題におけるトラックの割当はタスク割当に関するに接続されたワークステーションへのタなど多くの分野に応用されている．契約ネットプ ロト

コルはタスク割当問題を対象としており，その合意はタスクを割り当てるエージェントと割り当てられる

エージェント間で行われることになる．したがって，この合意はあり，本論文で扱うエージェント間の合意（相互選択）でエージェント間での合意を扱うものではない．

分散制約充足問題は複数のエージェント間で全ての制約を満たす解を発見する問題である．非同期バッ
クトラックやマルチステージネゴシエーションプ ロトコル

は分散制約充足問題を解く代表的な手法である．分散制約充足問題では制約は満たされるかそうでないかのいずれかであり，エージェントの効用は考慮の対象とはなっていなかった．
ゲーム理論的手法は効用を含めたエージェント間の合意形成プロトコル設計のために利用されてきた．

ゲーム理論ではエージェントの効用が記された利得行列があらかじめ与えられることが前提となっている．
しかしながら，プライバシーの観点から，このような利用者の効用をあらかじめ公表するような手法は望ましいとはいえない．
本論文では，エージェントの効用を考慮したマルチエージェント合意形成問題を扱い，エージェントは合意内容に対してあらかじめ効用を公開するのではなく，必要に応じて自らの意向を表明する方法を用いる．さらにエージェントの効用が他エージェントの表明に影響される場合を扱う．例えば，会合スケジューリング問題において，あるエージェントは人以上出席の会合には出席するが，そうでない場合は出席したくないかもしれない．このような場合，従来の合意形成プロトコル機会をのように各エージェントに表明の回限りしか与えない方法では，他エージェントの表明の結果を自らの表明に反映することが困難であり，エージェントの効用を高くするような合意に至ることは難しい．そこで本論文で提案するプ ロト
コルでは各エージェントに表明の機会を繰り返し与えることにより，エージェントが他エージェントの表明の後に，自らの表明を変更することを可能にしている．このような繰り返し表明のある合意形成プ ロト
コルにおいて考察すべき課題としては第一に，合意の内容がエージェントの表明の度に変わる可能性があり，最終的に一つの合意に到達するかどうかという点がある．また第二に，エージェントの表明を収集するプ ロトコルとしてはどのようなものが適しているかという点がある．
本論文ではまず，においてマルチエージェント合意形成問題の定式化を行う．

ではエージェントが繰り返し表明を行うプ ロトコルを提案し，第一の論点である合意の収束性について議論する．次にでは，エージェントの表明を収集するプ ロトコルとして一極集中型，二分木集中型，回覧板型を示し，表明参照度の視点からそれぞれのプ ロトコルの評価を行い，回覧板型が最適であることを示す．最後に，表明参照度の点において最適なもう一つのプ ロトコルである同報型を示し，デッド ロックにおちいらないことにおいて回覧板型が優れていることを示す．

マルチエージェント 合意形成問題
形式的にマルチエージェント合意形成問題は以下の要素から構成される．
エージェントの集合．

合意候補の集合．

ひとつの合意候補に対するエージェントの可能な表明の集合．ここでをエージェント の表明集合とする．すなわち，で，はエージェント の合意候補 に対する表明である．
エージェント間の全体的な合意を決定する合意選択関数 ．合意選択関数はエージェントの表明集合の直積上で定義され，が選択された合意となる．

である．すなわちとなるエージェントの効用の集合．

エージェントの効用に関して合意の大局的評価を行う合意評価関数 ．すなわち，で（は合意 に対するエージェント の効用を表す），全体合意はを満たすことが望ましい．
マルチエージェント合意形成問題では合意候補集合の中から複数エージェントで一つの合意を導き出す問題である．各エージェントはそれぞれの合意候補に対して自らの意志を表明し，全エージェントの表明をもとに合意選択関数を用いて全体的な合意が導かれる．さらにエージェントはそれぞれ合意に関する効用をもち，全体的な合意の評価の基礎となる．明らかに合意評価関数の値が大きくなる合意が望ましく，そのような合意を効率よく導き出す合意形成プ ロトコルを設計することがマルチエージェント合意形成問題の重要な課題となる．
例えば，エージェントのグループによる会合スケジュール問題を考えてみよう．この場合，合意候補は会合を実施する日時の候補となる．エージェントはそれぞれの日時に対して出欠の意向を表明する．もっとも単純な表明の方法はあるいはは特に断らない場合を除き，であり，その場合となる．以下の議論でとする．合意選択関数には様々なものが考えられるが，合意の方法を全員一致とするならば，となる．また多数決とするならば，となる．
また，全体的な合意はできるだけエージェントの意向に添うものであるべきであり，それを評価するために，エージェントの効用と合意評価関数を定義している．合意評価関数としても様々なものが考えられるが，エージェントの効用の平均を表すものとしてがその一つとなり，以下の議論ではこの関数を用いる．
さて，本論文ではエージェントの効用は合意候補のみに依存するのではなく，他エージェントの表明にも依存する場合を扱う．すなわち，エージェント の効用はば会合スケジューリング問題で，エージェント が出席者で表される関数となる．例え人以上の会合にしか参加したくない場合には，となる．またエージェント がある特定のエージェント との同席を好まない場合には，となる．

反復合意形成プ ロト コル
分散しているエージェント間で合意形成を行うためには，それらの間に意志表明のための明示的なプ ロトコルが定義されなければならない．基本的な合意形成の方法は合意候補のそれぞれに対して各エージェントが表明を行い，全エージェントの表明が，ある特定のホストエージェントに収集された時点で合意選択関数を用いて全体合意を決定するというものである．しかし本論文で扱うような，合意候補に対するエージェントの効用が他エージェントの表明により変化する場合には，意思表明の機会が度限りしかない合意形成プ ロトコルではエージェントの効用が高くなるような合意に到達することは難しい．そこで本論文では他エージェントの表明を参照しながらエージェントが繰り返し表明を行うプ ロトコルを提案する．その手順は以下のように帰納的に表現される．
各エージェント は巡目の表明を示し，それをホストエージェントが収集する．

ホストエージェントは 巡目の表明の結果を各エージェントに知らせる．各エージェント はその結果をもとに巡目の表明を示し，ホストエージェントがそれを収集する．

巡目の表明が終了すると，ホストエージェントは合意選択関数を用いて最終的な合意を決定する．
ここでまず興味の対象になることは，表明を何度も繰り返せば表明が変化しなくなる（表明が収束する）だろうかという点である．これが明らかになれば表明の最大繰り返し回数を決定することができる．そのためにはまず基本的な前提として，エージェントが無秩序に表明を変化させないという意思表明に対するエージェントの合理性を仮定する必要がある．
仮定（エージェントの合理性）エージェントは常にその時点で効用が最大になるような表明を行う．またエージェントが表明を変化させるのは，その変化により効用が真に増加する場合のみである．
またエージェントが他のエージェントの表明が分からない場合にそれをどのように解釈するかによって楽観主義エージェントと悲観主義エージェントに区別できる．楽観主義エージェントは他のエージェントの表明が不明である場合，自らの効用が最大化するようにその表明を解釈する．逆に，楽観主義エージェ
ントは他のエージェント の表明が不明である場合，自らの効用が最小化するようにその表明を解釈する．
例えば，先に示したエージェント の効用関数を考えよう．エージェント の表明が不明であるとき，エージェント が楽観主義エージェントであるなら，と解釈して，義エージェントである場合には，となる．と解釈して，となる．また，悲観主

エージェントの合理性を前提としたとき，エージェント の表明が変化し続けるのはどのような場合であろうか．まず，合意候補の集合，表明の集合はそれぞれ有限であるのでエージェントの表明集合も有限である．したがってエージェントの効用には上限が存在し，効用を無限に増加させるために表明が変化し続けることはない．表明が変化し続けるその他の可能性としては，エージェントの効用が振動する場合である．それは，エージェントの表明の変化が他のエージェント の効用を減少させ，次の表明の機会にエージェント が他の表明に変更することにより，それがふたたびエージェント の効用の減少につながる場合である．以上の議論からエージェントの表明が収束するための一つの十分条件として以下の命題が得られる．
命題

エージェントの表明が他のエージェントの効用を減少させることがないなら，エージェントの表明は収束する．
この命題で示される条件以外にもエージェントの表明が収束する場合はありうるが，収束が保証されず，エージェントの表明が振動するような場合も少なくない．またたとえ表明が収束するとしてもそれには多数の表明の繰り返しを行わなければならない場合もある．したがってたとえ表明が収束していなくても，表明の繰り返しには上限を設けて，その時点で得られた表明をもとに最終合意を決定することが現実的であるといえる．そこで次に興味の対象になることは，いかにして少ない繰り返しでエージェントの効用を高めるかという点である．これは一巡のエージェントの表明収集を行うプ ロトコルの性質に依存する問題である．

表明収集プ ロト コル
エージェントの表明収集を行うプ ロトコルとして，一極集中型，二分木集中型，回覧板型の三つを取り上げ，その性質について考察する．まず表明を収集する過程が異なる三つのプ ロトコルを定義する．
一極集中型： 図に示すように，エージェントは直接ホストエージェントに個別的に表明を行う．他のエージェントはそのエージェント がどのような表明を行ったかは知ることができない．ホストエー
ジェントは全エージェントからの表明を受け取るとその結果を同報する．
二分木集中型： 図に示すように，トーナメント方式で表明を収集する．まずが集められ，その後そのリーダーエージェント同志でエージェント間で表明エージェントの表明がとりまとめられる．さらにそのリーダーエージェント同志がペアになり，最終的にホストエージェントに表明が集められる．
この場合，リーダーエージェントはそのグループ のエージェントの表明を参照して自らの表明を決定することができる．ホストエージェントは表明を受け取るとその結果を全エージェントに同報する．
回覧板型： 図に示すように，エージェントには表明を回覧する順序があらかじめ与えられ，その順序に従って表明をとりまとめる．この場合， 番目のエージェントは から番目のエージェントまでの表明を参照して自らの表明を決定できる．ホストエージェントは一巡してきた表明を受け取り，その結果をふたたび同じように巡回させる．
それでは以上の三つのプ ロトコルの比較してみよう．これらのプ ロトコルを評価する基準は表明が収束するまで繰り返しの回数がいかに少ないかという点である．評価の基礎となる例題を以下に示す．
例題つのエージェントにおいて会合スケジューリングが行われる．会合を行う日程は一日に決められており，各エージェントは出欠に関する意志表示を行う．各エージェントは会合出席者に関して以下のような好みがある．

すなわち，エージェント は 人以上出席する会合を好むが，そうでない場合は出席したくない．ここでエージェントは全員，悲観主義エージェントであると仮定する．
まず，この例題において表明が収束するであろうか．エージェントの効用は，出席者が増加するにつれ効用は単調に増加する．またエージェントは悲観主義であるので，エージェントの表明は出席から欠席に変わることはない．したがって，エージェントの表明の変化は他エージェントの効用を減少させることはないので，したがって命題

より，この例題においてエージェントの表明は必ず収束する．もちろん，この収束値は全員出席であり，そのときの合意評価関数の値はである．

次に，この収束値に至るまで，それぞれのプ ロトコルで何回の繰り返しが行われるであろうか．その結果をの値とともに表 に示すが，回覧板型は回，二分木集中型は回，一極集中型はが行われる．この例題においては明らかに回覧板型が他のプロトコルに勝っている．

回の繰り返し88 884 442 21121314151617111231778 86 61 15 52 24 433

図表明収集プ ロトコル

回数
回覧板型
二分木集中型

一極集中型

表プ ロトコルの比較

86 245168718この違いの原因は何であろうか．この違いは，エージェントが自分の表明を決定する際にどれだけ他エージェントの表明を参照できるかによっている．ここでそのような度合いを定量的に示す概念として表明参照度を定義しよう．表明参照度はエージェントが表明を決定する際に表明を参照した（自らを含めた）エージェント数であり， から （全エージェント数）の値を取る．表明参照度に関しては以下の補題が成立する．
補題

任意の表明収集プ ロトコルにおいてエージェント が 番目に表明する場合，エージェント の表明参照度はが成り立つ．

（証明）エージェント 以前にはのエージェントしか表明を行っておらず， より多くのエージェントの表明を参照することはできないので，明らかである．□
それぞれのプ ロトコルにおける表明参照度は図 に示されている．この平均を取ると回覧板型で分木集中型で，一極集中型で，二であり，回覧板型が表明参照度の点において優れていることが分かる．表明参照度に関して以下の定理が成立する．
定理

回覧板型が表明参照度の点において最適である．
で（証明） のエージェントが存在する場合，回覧板型の表明参照度の和はある．さてここで回覧板型よりも表明参照度の点で優れたプロトコル
そのプロトコルの表明参照度の和はト順に識別子を与えよう．回覧板型では，プロトコルとする．回覧板型における表明参照度は補題

ではである．ここでから昇順にその大きさを比較していこう．プ ロトコルも大きいので，が存在すると仮定しよう．その場合よりも大きくなるはずである．ここで表明を行うエージェンとを順にの表明参照度の和は回覧板型のものよりとなる が存在する．このときであるが，これはと矛盾する．したがって回覧板型が表明参照度の点において最適である．□

もちろん，繰り返しの回数は表明参照度だけでなく，表明の順序に大きく依存する．例えば次の例題を考えてみよう．
例題

以下に示すエージェントの効用以外は例題 と同様である．

この場合，繰り返しの回数は全てのプロトコルで回となる．この例題において，エージェントをホストエージェントとするように表明の順序を逆順にすれば，例題１と全く同じ回数になるわけで，表明の順序は繰り返し回数を決定する大きな要因であることがわかる．回覧板型においてこのような順序の問題に対処する一つの改良は偶数巡目の表明の順序を奇数巡目とは逆にこの改良により例題においてもの順に行うことである．

回の繰り返しで表明が収束する．しかしながら，現実の問題において表明の順序までを含めて繰り返し回数を最適化するには，エージェントの効用が明らかでなければならず，このような効用関数の公開は先にも述べたようにプライバシーの観点からは望ましくない．
最後に新たな表明プ ロトコルとして以下のような同報型と，回覧板型との比較をしてみよう．
同報型： エージェントは自発的に表明を他エージェントに同報する．エージェントは先に表明を行ったエージェントの表明を参照して自らの表明を決定する．全エージェントが表明を終えるとホストエージェ
ントはその結果を全エージェントに同報する．
同報型の表明参照度は回覧板型と等価であり，最適な表明収集プロトコルといえる．回覧板型との違いは表明の順序があらかじめ固定されているかどうかという点であるが，同報型では各エージェントが他のエージェントの表明を待つ日和見によりプロトコルはデッド ロックにおちいる可能性があるという問題点がある．

まとめ
エージェントの効用を考慮したマルチエージェント合意形成問題を取り上げ，エージェントの効用が他エージェントの表明により変化する場合に対処する手法として，表明を繰り返し行うプロトコルを提案し，表明の収束性について議論した．また一巡の表明収集を行うプ ロトコルとして，一極集中型，二分木集中型，回覧板型を取り上げ，回覧板型が優れていることを示した．表明参照度の点において回覧板型は最適であることも示した．さらに表明参照度において最適なもう一つのプ ロトコルである同報型に対しても，デッド ロックの点から回覧板型が優れていることを示した．

参考文献