評価関数を用いた エージェント間の交渉 5月２８日 河目 瞬 河目　瞬 Artifical Intelligence 84(1996) 151-176 『Compromise in negotiation : exploing worth functions over states』 Gilad Zlotkin , Jeffrey S. Rosenschein

２人で野球観戦に行きたい ２人で映画を見に行きたい 話し合い エージェント１ エージェント２ どうする？

例：ミーティングの設定

・時間帯が遅くなってから行いたい。 ・自分のオフィスで行いたい。 二人はミーティングを行いたい ・時間帯が早いうちに行いたい。 エージェントA1 二人はミーティングを行いたい ・時間帯が早いうちに行いたい。 ・自分のオフィスで行いたい。 エージェントA2

価値の概念の導入 エージェントにとって、どれだけ好ま しい状態なのかを表す指標 状態に価値を与える

A１にとって、午後４時の ミーティングが最も高い価値 エージェントA1の評価関数 エージェントA1の 最も好ましい時間帯が、 午後４時であるとする ミーティングの時刻 A１にとって、午後４時の ミーティングが最も高い価値

A2にとって、午前９時の ミーティングが最も高い価値 エージェントA2の評価関数 エージェントA2の 最も好ましい時間帯が、 午前９時であるとする 価値 ミーティングの時刻 A2にとって、午前９時の ミーティングが最も高い価値

A1にとって、A1オフィスでの ミーティングが最も低いコスト エージェントA1のコスト関数 エージェントA1にとって、 自分のオフィスに近いほ ど、移動コストがかからな い A1オフィス A2オフィス ミーティングの場所 A1にとって、A1オフィスでの ミーティングが最も低いコスト

A2にとって、A２オフィスでの ミーティングが最も低いコスト エージェントA2のコスト関数 エージェントA2にとって、 自分のオフィスに近いほ ど、移動コストがかからな い コスト A2オフィス A1オフィス ミーティングの場所 A2にとって、A２オフィスでの ミーティングが最も低いコスト

ユーティリティの定義 双方のエージェントにとって、ユーティリティとは、 ユーティリティ＝価値ーコスト エージェントは、これを最大にしたい

４ｐｍ、A1オフィスでの ユーティリティが最大 エージェントA1のユーティリティ関数 エージェントA1にとって 午後４時に、 ことが最も好ましい ユーティリティ A1オフィス A2オフィス ４ｐｍ、A1オフィスでの ユーティリティが最大

９am、A2オフィスでの ユーティリティが最大 エージェントA2のユーティリティ関数 エージェントA2にとって 午前９時に、 ことが最も好ましい ユーティリティ A2オフィス A1オフィス ９am、A2オフィスでの ユーティリティが最大

２人のユーティリティの和を最大にする ２人のユーティリティの積を最大にする ２人のエージェントの話し合いの結果として・・・ ２人のユーティリティの兼ね合い が、最大になる点を結論として考 える ２人のユーティリティの和を最大にする ２人のユーティリティの積を最大にする ２つのアプローチの仕方がある

２人のユーティリティの和を最大にする 上の４つの状態が、 ミーティングの行われる状態となる ２人のユーティリティの和 が最大となる点を、 話し合いの解決とする ユーティリティの和 A2オフィス A1オフィス 上の４つの状態が、 ミーティングの行われる状態となる

２人のユーティリティの積を最大にする 上の２つの状態が、 ミーティングの行われる状態となる ２人のユーティリティの積 が最大となる点を、 話し合いの解決とする ユーティリティの積 A2オフィス A1オフィス 上の２つの状態が、 ミーティングの行われる状態となる

２人のユーティリティの積を最大にする ゲーム理論の「ナッシュの定理」に基づくもの。 「ナッシュの定理」とは？ ２人交渉問題のナッシュ解は、５つの公準を満たし、かつ、この５つの公準を満たす解は、ナッシュ解に限る。 ナッシュ解：２人のユーティリティの積を 　　　　　　　　最大にする解

５つの公準 （１）個人合理性 （２）共同合理性 （３）利得の一次変換での不変性 （４）対称性 （５）無関連な代替案からの独立性

つまり ２人のユーティリティの積を最大にする解 ５つの公準を満たす唯一解である ５つの公準とは、交渉の特性を述べている 交渉問題において、適切と思われるのは、 ユーティリティの積を最大にする解である

WODの定義 （Worth Oriented Domains：価値指向領域）

WOD （Worth Oriented Domains） て、全ての状態に価値を割り当てている。 ＜ Ｓ, A , J , c ＞ Ｓ： 領域の状態 A： エージェント J： 共同プラン c : コスト関数

＜ Ｓ, A , J , c ＞ Ｓ： 全ての取り得る、領域の状態の集合 A＝｛A1,A2,・・・,An｝：エージェントリスト ｊ：S→S　　　 j∈J ｃ： コスト関数 ｃ：J→（R＋）ｎ ｃ（ｊ）i ： プラン ｊ におけるエージェント iの 活動のコスト

＜ｓ, （W1,W2,・・・Wn）＞ ｓ : 領域の初期状態 Wk : エージェント k の評価関数 さらに WOD内で問題を解くために、まずあるものとして、 ＜ｓ, （W1,W2,・・・Wn）＞ ｓ : 領域の初期状態 Wk : エージェント k の評価関数

交渉のエージェントに関する５つの仮定 (1) Utility maximizer (2) Complete knowledge 各々のエージェントは、彼の期待したユーティリティを最大にすることを望む (2) Complete knowledge 各々のエージェントは、全ての関連情報を知っている

(3) Isolated negotiation 各々のエージェントは、現在の振る舞いが将来の交 渉においてどんな影響を及ぼすか予期することがで きない。 (4) Bilateral negotiation 交渉は一度に、エージェントのペア一組の間で行われる。

(5) Symmetric abilities 全てのエージェントは、同じ活動が実行できる。 そして、活動のコストは、各エージェントにとって同じ である。

例：ブロック移動問題 　（１人のエージェントのみ）

①黒い箱をテーブル２に置きたい。ただし、 　直接テーブルの上には置かない。 ②白い箱をテーブル３にひとつだけで置 　きたい。 エージェントA1 箱を持ち上げるコスト：１ 箱を下ろすコスト：１ １ ２ ３ ４ ①のサブゴールの評価：４ ②のサブゴールの評価：６

f1 f2 f3 コスト２ サブゴール①を満たしている コスト４ サブゴール②を満たしている コスト８ 両方のサブゴールを満たしている 1 4

ｆ１の状態 　W４－C２＝U２ W：評価（価値） C：コスト U：ユーティリティ ｆ２の状態 　W６－C４＝U２ ｆ３の状態 W（４＋６）－C８＝U２ ３つの状態が皆同じユーティリティ。

ペナルティを導入 ｆ１の状態 W４－C２ーペナルティ６＝U－４ ｆ２の状態 W６－C４ーペナルティ４＝U－２ ｆ３の状態 サブゴールの不達成 に対し、負の評価を与える ペナルティを導入 ｆ１の状態 　W４－C２ーペナルティ６＝U－４ ｆ２の状態 　W６－C４ーペナルティ４＝U－２ ｆ３の状態 　W（４＋６）－C８ーペナルティ０＝U２ ｆ３の状態が、最良の状態。

例：ブロック移動問題 　（２人のエージェントによる）

混合共同プランの導入 ・混合共同プランとは？ エージェントが、確率pで共同プランj＝（j1、j2）

①の評価：１０ ②の評価：４ サブゴールの不達成による ペナルティ：①②ともにー２ 1 ２ ３ ４ ①黒い箱はテーブル１に置くが、その際、白い箱の上に置く。 ②灰色の箱はテーブル３に置く ①の評価：１０ ②の評価：４ サブゴールの不達成による ペナルティ：①②ともにー２ エージェントA2 エージェントA1 1 ２ ３ ４ ①黒い箱はテーブル１に置くが、その際、白い箱の上に置く。 ②灰色の箱はテーブル４に置く

両者が、サブゴール①を満たすには・・・ 各々コスト２ 灰色の箱を置く場所 によって２つの最終 状態がある １ ２ ３ ４

この状態にする プランδ１ エージェントA1が望む状態 この状態にする プランδ２ エージェントA2が望む状態

ユーティリティを計算すると・・・ UA1(δ1)＝W（１０＋４）－C（２＋２）＝１０ UA1(δ2)＝W１０ーペナルティ２ーC２＝６ UA2(δ1)＝UA1(δ2)＝６ UA2(δ2)＝UA1(δ1)＝１０ １人で完全なゴールを達 成するよりもUがいい。 コスト１０ 　U＝W（１０＋４）－C１０＝４

マルチプランdealの導入 ・マルチプランdealとは？ エージェントが、確率ｑで混合共同プランδ１を 実行し、また確率１ーｑで対称的な混合共同プラ ンδ２を実行する。

この状態にする プランδ１ エージェントA1が望む状態 確率ｑ この状態にする プランδ２ エージェントA2が望む状態 確率１－ｑ

マルチプランdealにおけるユーティリティの定義 エージェントのユーティリティ 　　　＝ｑ×（δ１でのユーティリティ） 　　　　　＋（１－ｑ）×（δ２でのユーティリティ）

A1ユーティリティ１０ A2ユーティリティ６ この状態にする プランδ１ エージェントA1が望む状態 確率０．５ A1ユーティリティ６ A2ユーティリティ１０ この状態にする プランδ２ エージェントA2が望む状態 確率０．５

UA1 ＝０．５×１０＋０．５×６＝８ UA2 ＝０．５×６＋０．５×１０＝８ UA1 × UA2 ＝ ８×８＝６４ ユーティリティを計算すると・・・ UA1 ＝０．５×１０＋０．５×６＝８ UA2 ＝０．５×６＋０．５×１０＝８ UA1 × UA2 ＝ ８×８＝６４

A1ユーティリティ１０ A2ユーティリティ６ この状態にする プランδ１ エージェントA1が望む状態 A1ユーティリティ６ A2ユーティリティ１０ この状態にする プランδ２ エージェントA2が望む状態

例：タイルワールド

２ ２ ５ ２ ５ ２ 穴（数字は、埋めた時の価値） エージェント 障害物 エージェントに よって違う価値を 当てられている穴 A２ A１ ２ ２ ５ ２ ５ エージェント 障害物 エージェントに よって違う価値を 当てられている穴 ４ ３ ２ タイル（これで穴を埋める）

１マス移動でコスト１ A ２ A A A A A

10 ０ ９ １５ ９ ０ 5 A2 A1 世界の初期状態 １ １ 5 10

10 9 １５ コスト１０ 5 エージェントA1が １人で１５の穴を塞ごうとすると・・・ １ ユーティリティ５ １ 5 10 A1 A1 A1 A1 A1 A1 A1 A1 A1 A1 コスト１０ 5 A1 エージェントA1が １人で１５の穴を塞ごうとすると・・・ １ ユーティリティ５ １ 5 10

10 9 １５ コスト１２ 5 エージェントA1が １人で９の穴を塞ごうとすると・・・ １ ユーティリティ-3 １ 5 10 A1 A1 A1 A1 A1 A1 A1 コスト１２ 5 A1 エージェントA1が １人で９の穴を塞ごうとすると・・・ １ ユーティリティ-3 １ 5 10

10 9 １５ コスト１６ 5 エージェントA1が １人で両方の穴を塞ごうとすると・・・ １ ユーティリティ８ １ 5 10 A1 A1 A1 A1 A1 A1 A1 A1 A1 A1 コスト１６ 5 A1 エージェントA1が １人で両方の穴を塞ごうとすると・・・ １ ユーティリティ８ １ 5 10

エージェントA1 １５の穴のみを塞ぐ：ユーティリティ５ ９の穴のみを塞ぐ：ユーティリティ－３ 両方の穴を塞ぐ：ユーティリティ８ A1は両方の穴を塞いで、 最大ユーティリティ８を得る。

10 １５ 9 コスト１０ 5 エージェントA2が １人で１５の穴を塞ごうとすると・・・ １ ユーティリティ５ １ 5 10 A2 A2 １５ A2 A2 A2 A2 A2 9 A2 A2 A2 A2 A2 コスト１０ 5 A2 エージェントA2が １人で１５の穴を塞ごうとすると・・・ １ ユーティリティ５ １ 5 10

10 １５ 9 コスト６ 5 エージェントA2が １人で９の穴を塞ごうとすると・・・ １ ユーティリティ３ １ 5 10 A2 A2 A2 １５ A2 A2 9 A2 A2 コスト６ 5 A2 A2 A2 エージェントA2が １人で９の穴を塞ごうとすると・・・ １ ユーティリティ３ １ 5 10

10 １５ 9 コスト２２ 5 エージェントA2が １人で両方の穴を塞ごうとすると・・・ １ ユーティリティ２ １ 5 10 A2 A2 A2 １５ A2 A2 A2 A2 9 A2 A2 A2 A2 A2 A2 A2 コスト２２ 5 A2 エージェントA2が １人で両方の穴を塞ごうとすると・・・ １ ユーティリティ２ １ 5 10

エージェントA2 １５の穴のみを塞ぐ：ユーティリティ５ ９の穴のみを塞ぐ：ユーティリティ３ 両方の穴を塞ぐ：ユーティリティ２ A2は１５の穴のみを塞いで、 最大ユーティリティ５を得る。

10 １５ A1コスト８ A2コスト５ 5 ２人のエージェントが A1の両方の穴を塞ごうとすると・・・ １ A1ユーティリティ１６ ０ A1 A1 A1 ９ １５ A2 A1 A2 A1コスト８ A2 ９ A1 ０ A2 A1 A2コスト５ 5 A2 A1 A1 A1 ２人のエージェントが A1の両方の穴を塞ごうとすると・・・ １ A1ユーティリティ１６ A2ユーティリティ１０ １ 5 10

10 １５ A1コスト４ A2コスト９ 5 ２人のエージェントが A2の両方の穴を塞ごうとすると・・・ １ A1ユーティリティ１１ ０ ９ １５ A2 A2 A1コスト４ A2 ９ A1 A1 ０ A2 A1 A2コスト９ 5 A2 A2 A2 A1 ２人のエージェントが A2の両方の穴を塞ごうとすると・・・ １ A1ユーティリティ１１ A2ユーティリティ１５ １ 5 10

２人のエージェント A1の穴を両方を塞ぐ： 　　　　　　A1ユーティリティ１６ 　　　　　　A2ユーティリティ１０ １６０ A2の穴を両方を塞ぐ： 　　　　　　A1ユーティリティ１１ 　　　　　　A2ユーティリティ１５ １６５ ２人は、A2の穴を両方塞ぐ

A1の穴を両方を塞ぐ： A1ユーティリティ１６ A2ユーティリティ１０ 確率０．６ A2の穴を両方を塞ぐ： A1ユーティリティ１１ マルチプランdealを適用させる A1の穴を両方を塞ぐ： 　　　　A1ユーティリティ１６ 　　　　A2ユーティリティ１０ 確率０．６ A2の穴を両方を塞ぐ： 　　　　A1ユーティリティ１１ 　　　　A2ユーティリティ１５ 確率０．４

UA1 ＝０．６×１６＋０．４×１１＝１３ UA2 ＝０．４×１０＋０．６×１５＝１３ UA1 × UA2 ＝ １３×１３＝１６９ ユーティリティを計算すると・・・ UA1 ＝０．６×１６＋０．４×１１＝１３ UA2 ＝０．４×１０＋０．６×１５＝１３ UA1 × UA2 ＝ １３×１３＝１６９

・交渉問題を考える手法のひとつとして、WODを紹介した。 まとめ ・交渉問題を考える手法のひとつとして、WODを紹介した。 ・WODを使った例をいくつか紹介した。 参考文献 ・『新ゲーム理論』　　　　　　　　　　　　　　　　　　鈴木　光男 ・『分散人工知能：交渉と均衡化』　　桑原　和宏、石田　亨　　　　　　　　　　　　　 ・『意思決定支援のためのマルチエージェントの協調機構と、 　　その応用に関する研究』　　　　　　　　　　　　　伊藤孝行