架空名義入札に頑健なネットワークリソース割当てのモデル化と評価
【研究分野】知能情報学
【研究キーワード】
オークション / マルチエージェント / 負荷分量 / フェアネス / 資源割当て / 資源選択 / 経路探索 / ネットワーク / 負荷分散
【研究成果の概要】
本研究では,ネットワーク上の各リソースを市場原理に基づいて公平かつ効率的に割り当てるプロトコルを,その実装に向けて評価することを目的とする.
P2Pや分散センサネットワークなどのアドホックなネットワークにおけるデータ転送では,個々のノードの所有者や規格が異なる.この場合,各ノードにデータを適切に転送するための誘因(報酬)を考慮しなければならない.この報酬の決定にはしばしばオークションプロトコルが用いられる.しかし従来のプロトコルでは,あるノードが架空のノードを用いるか他ノードと共謀することで,不正に報酬を獲得できることを示した.この場合、理論的にもっとも優れているVickrey-Clarke-Grovesプロトコル(VCG)でも、不正行為は防げない。
本研究では、さらに、選択されうる経路を所有しているエージェントの数に応じたペナルティをVCGに適用し、Reserve-Costプロトコル(RC)を提案し、このプロトコルが架空名義を用いた操作の影響を受けないことを理論的に明らかにした。計算機上に再現した小世界ネットワークに対して、提案プロトコルを評価し、VCGに対して約60〜80%の効率性を達成することも示した。
また実際のネットワークでは,各ノードでオークションなど取得可能な情報に基づいてどこからデータを受ける(送る)べきかを決定する必要がある.これは,入札可能な対象(サーバなど)が複数あるときに,適切な入札箇所をある程度推定することに相当する.しかし、ネットワークの資源割当てのように非常にたくさんの要求が同時に起こり、かつ多くの地点から独立に処理をする必要がある.このような状況で資源割り当てプロトコルで見られる現象の解析も行った。それぞれが合理的に判断をすると全体の効率が落ちる現象があり、このために揺らぎや学習を導入することが一定の効果を上げることを示した。
【研究代表者】