3.1.5

3.1.5　交渉プロトコル設計

本節では、それぞれ個別目標を達成しようとする、利己的なエージェントの合意形成について議論する。エージェントの利己性はゲーム理論などにおいて効用（utility）で表され、エージェントは自らの効用を最大化するような行動を選択する。利己的なエージェントの具体例は、電子的商取引を行うエージェントである。利用者の要望を受けたエージェントは電子マーケットにおいて他のエージェントと協調的にではなく利己的に相互作用を行い、利用者の要望を最大限に満たそうとする。

　このようなマルチエージェントシステムでは、博愛的エージェントを前提とし、その行動を明示的に操作できる分散制約充足のような競合解消機構をシステムの中に埋め込むことはできない。むしろ問題が生じたときに利己的エージェントを合意に至らしめる交渉プロトコルが必要になる。一般的にその合意点は、それ以上効用をあげようとすると他のエージェントの効用を減少させることになるパレート最適解（Pareto Optimality）となる。

　以下で述べる2つの交渉プロトコルは、交渉に関わる様々なメッセージの分類とその役割の規定に主眼がおかれている。　

A.　契約ネットプロトコル

契約ネットプロトコル（以下、契約ネットと略記）は、人間社会における契約入札の仕組みを下に、複雑なタスクを独立したここのタスクに分割して、それらを複数のエージェントに割り当てるためのプロトコルである。契約ネットでは、分割されたタスクは独立に解かれるものとして契約が結ばれる。

契約ネットは、そのプロトコルに従って通信する複数のエージェント、および問題に対応するタスクとその部分足す句集の集まりによって構成される。契約ネットは次のような手順で実行される。

まず、タスクを持つエージェント（マネージャ）は、必要であればそのタスクを部分タスクに分解し、各部分タスクに対してタスク提示メッセージを放送する。提示されたタスクを実行可能なエージェントは、そのタスクに対して入札メッセージをマネージャに送信する。マネージャは、送られてきた複数の入札メッセージを評価し、それらの中から最も適切と思われる入札を一つ洗濯して、それを送ってきたエージェントに落札メッセージを送る。この落札メッセージを得たエージェントが契約者である。マネージャは、各部分タスクの実行結果のレポートを集め、最終的には各部分タスクに対する解の統合を行う。このようにして、契約ネットでは階層的なタスク割り当て構造がトップダウンに形成される。

契約ネットの一つの特徴は相互選択制にある。つまり、契約を行う際に、マネージャと契約者が入札と落札に関して独立の価値規準を持つことが可能である。このように、契約ネットはタスクの割り当てに関して複数のエージェント間で交渉を可能にするプロトコルとなっている。

B.　マルチステージネゴシエーション

マルチステージネゴシエーション（多段階交渉）はタスク/資源割り当て問題に関して、複数エージェント間でのタスク/資源割り当てに対する帯域的な制約がある場合、つまり部分タスク間に制約がある場合に、競合を解消して制約充足を行うためのプロトコルである。

　契約ネットは各部分タスクが独立であることを仮定しているため、部分タスク間に制約（相互作用）がある場合は扱えない。マルチステージネゴシエーションでは、部分タスク間に大域的制約が存在する問題を、交渉を複数回繰り返すことによって解決しようとする。さらに、契約ネットでは、タスクの提示、入札、落札という一回のプロセスでタスク割り当てを行っているのに対して、マルチステージネゴシエーションでは、局所的な資源割り当て婦負強に関して交換した情報を下に、必要に応じて資源割り当てをやり直す。このように、大域的制約がが充足されるまで何度も交渉が繰り返される。