エージェントによるオークション入札支援

入札支援システム

実行例（エージェントの入札状況）
BiddingBotは，オークションへの参加を自律的に行動するエージェント に代行させることにより参加者の負担を軽減するマルチエージェントシステムで す． 本システムでは，複数のエージェントが，複数のオークションに，同時に参加・ 入札することによって，なるべく安い価格で商品を落札することを目的とし，以 下の3通りの協調方式を実行可能です． 完全自律型入札機構では，すべてのビッダーエージェントが完全に自律的に入札 を行い，一つでも商品を落札することができたら，すべてのビッダーエージェン トは入札を終了します．
スイッチング型入札機構は，同時に複数の商品を落札してしまうことを防ぐため の方式です．同時に複数の商品を落札しないためには，各時点で，一つのビッダー エージェントだけが入札している状態にすれば良いため，スイッチング型入札機 構では，落札できる可能性が最も高いビッダーエージェントのみが入札するよう にしています．
スイッチング型入札機構では，スイッチングによるタイムロスが存在するために， 各ビッダーエージェントが，適切な入札を行うタイミングを逃してしまう可能性 があります．ハイブリッド型入札機構は，スイッチング型入札機構と完全自律型 入札機構を組み合わせ，そのような欠点を補うことを試みた方式です．ハイブリッ ド型入札機構では，まず，完全自律型入札機構で入札を行い，あるビッダーエー ジェントの締めきりが近付いたら，一つのビッダーエージェントだけが入札を行 うことになっています．ハイブリッド型入札機構では，締めきり近くでの入札の 増加に対応するために，締めきり近くには一つのエージェントが集中して，その オークションに対して入札を行います．

入札戦略決定手法

オークションにおいては，財を落札するための入札戦略をどのように決定するかが問題となります．実際には，正確にオークションの結果を予測することは不可能であるため，期待効用（Expected Utility）を最大化する入札戦略を決定することが一つの問題解決方法となります．
本研究では，財に対する補完性（Complementary）／代替性（Substitutional）を表明できる複数財を処理可能なオークション方式である逐次型オークション（Sequential Auction）における入札戦略を，動的計画法（Dynamic Programming）に基づいて決定する手法に着目しました．しかし，動的計画法では解の探索空間が非常に大きくなり，そのため，計算時間も非常に大きくなってしまうという問題があります．そこで我々は新しい問題の形式化を与えることにより，動的計画法に基づいて期待効用を最大化する入札戦略を効率的に計算する手法を開発しました．

一方，オンラインオークションにおける過去の入札履歴と，入札額の推移のリア ルタイムな監視によるデータに基づいて，最適な入札戦略を計算する手法に関しても研究を進めており，BiddingBot上での実装方法を検討しています．

オークションシミュレーション
実行例（仮想オークションサービス）

MultiHammerは，複数のオークションサイトから収集した情報を用いて 仮想的なオークションサービスを利用者に提供するマルチエージェント システムです．本システムでは，複数のエージェントが複数のオークシ ョンサイトから非同期に情報を収集し，収集された情報を統一的なイン ターフェイスを通して利用者に提供することにより，オークション参加 者が財の検索や比較を行う際の負担を軽減します．また，収集した情報 を利用して仮想的なオークションサービスを提供することにより，オン ラインオークション初心者のための学習環境や，BiddingBotのようにオ ークションサイトを処理の対象としたシステムの実験環境としての役割 を果たします．

MultiHammerは，次に示す3種類のエージェントにより構成されます．

情報収集エージェントは，情報収集の対象となるサイトごとに専用の柔軟なwrapperとして機能するエージェントです．情報収集 エージェントを柔軟なwrapperとして機能させるために，個々のオークションサイトに特有な情報は専用のモジュールとして開発されています．これらのモジュールの開発には多くの時間と労力が必要になるため， モジュールの作成を支援する機構を開発し，使用しています．情報蓄積エージェントは情報収集エージェントにより収集された情報をデータベ ースに蓄積します．そして，オークションエージェントは蓄積された情報を用いて仮想的なオークションサービスを利用者に提供します．

エージェント間交渉手法

説得・根回し

説得（Persuasion）

本研究では，投票方式や集計方式などの社会的な決定方式を定めるのではなく，個々のエージェントの持つ選好順序を考える方式として，説得という方式を提案しています．我々は人間社会の様々な説得の手法からモデル化可能な手法を選びだし，エージェント間の合意形成に導入しました．エージェント間の説得の基本的な枠組は以下の通りです．エージェント間の説得において，説得する側のエージェントを説得者と呼び，説得される側のエージェントを妥協者と呼びます．説得者および妥協者の基本的な動作は以下の通りです．

要請：
説得者は，妥協者に合意案を送信する．
妥協：
合意案を受信した妥協者はその合意案に対して妥協を試みる．
返答：
妥協の結果，提案された合意案に合意可能となったら，妥協者は説得者に合意 することを返信する．合意不可能であれば，合意を拒否することを返信する．

根回し（Ground Work）

グループで意思決定を行う時，最終的に合意を得ることはもちろん大切ですが， それと共に効率的により多くのメンバーが満足する合意を得る方法についても問題にしなければなりません．通常ある意思決定問題に関してメンバーの 価値観や評価の基準は異なるため，各メンバーの評価はまちまちで合意を得るこ とは容易ではありません．また， 合意できなかったメンバーにとって最も望ましくない合意案が導かれてしまうという結果も起こり得ます．
そこで本研究では根回し的な交渉を提案しています．本研究で提案する根回しでは，エージェントは交渉においてお互いの評価を提示し合い，相手の評価過程において反映してもらうことを試みます．根回しにより，エージェントはグループ内の様々な評価を反映した上でそれぞれの評価を決定でき，エージェント ごとにまちまちな評価を近似させていくことができます．本研究では，根回しと説得を組合わせた効率的で納得のできる合意形成プロセスの確立を目指しています．

多重交渉

エージェント間の交渉において，どのエージェントが中心になって交渉を始める かは，交渉結果に影響を与えるため，重要な問題になっています．本研究では，すべてのエージェントが交渉の中心となる機会を与えることによって，よりユーザに受け入れやすい結果を得ることを試みています．本研究室で作成し たグループ代替案選択支援システムGCDSS（Group Choice Design Support System）においても，エージェント間の交渉を２エージェント間の説得を積み上 げたトーナメント方式で行う場合，２つのエージェントの組合せにおいて説得者 と被説得者の選定をランダムに一人選定したためにグループ意思決定が説得者に依存して交渉結果が異なり，ユーザの納得の得られにくい交渉結果が導きだされることがありました．そこで，本研究ではGCDSSにおけるエージェント間の交渉 に関連してすべてのグループメンバーがそれぞれ説得者となるように複数の交渉 パターンを設定し分散実行することによって，ユーザの納得がより得られやすい 交渉結果を導き出すことを目的としています．

議論に基づく交渉

エージェントがユーザの代理となって交渉を行う場合，交渉の過程においてユー ザの好みや知識が的確に反映されることが期待されます．例えば電子商取引の分野では，エージェントが交渉することによって，リーズナブルな商取引きを成立させるために，エージェントがユーザの好みや知識を有効に活用できる交渉方式が必要とされてきています．これまでの代表的な交渉方式として，契約ネットプロトコル（Contract Net Protocol）があります．契約ネットプロトコルは，複雑な問題を複数のエージェントによって解決する際に有効ですが，エー ジェント間の相互作用の機会が少なく，ユーザの好みや知識を競合解消の際に反 映する十分な枠組みを与えていません．

２エージェント間の議論の例
エージェント間の競合解消の有望なアプローチとして，議論に基づく交渉方式が提案され，注目を集めています．議論に基づく交渉は，エージェントが互いに提 案，および逆提案を繰り返すことによって競合解消し，合意形成を行う交渉方式 です．エージェントは提案，および逆提案に，その提案を主張する理由付けを与 えることができます．本研究では，議論に基づく交渉が可能なエージェントの実 装と，エージェントによる議論のより優れた形式化を与えることを目的としてい ます．
我々は，エージェントがユーザの好みを評価するためにAHP （Analytic Hierarchy Process）を利用し，評価構造を提案として部分的に表明します．

エージェントは，受け取った提案を受理できなかった場合，これまで表明された提案と，自分が提案可能，かつ望ましい合意案を得るために有効な提案を総合的に評価し，適切な反論ができるかどうかを推論します．もし，現時点で最も望ましい合意案を得るための提案ができないならばエージェントは妥協し，より望ましい合意案を得るために再度推論します．
右の例では，最初にAgent1が評価基準C2に基づく評価を正当化として，代替案Aを合意案として主張しています．次に，Agent2が評価基準C4に基づく評価を正当化として代替案Bを合意案として主張しています．そして，再度Agent1が評価基準C3に基づく評価を正当化として代替案Aを主張しています．最終的に Agent2が妥協し，代替案Aで合意が得られます．
[G-Commerceグループ研究紹介]