Greedyな割当手法に基づくStrategy-proofな組合せオークションプロトコルと公開競上げ式プロトコルへの拡張

伊藤 孝行  横尾 真  松原 繁夫  岩崎 敦  

誌名
電子情報通信学会論文誌 D   Vol.J89-D   No.5   pp.943-953
発行日: 2006/05/01
Online ISSN: 1881-0225
DOI: 
Print ISSN: 1880-4535
論文種別: 論文
専門分野: 分散協調とエージェント
キーワード: 
PORFプロトコル,  組合せオークション,  strategy-proof,  マルチエージェントシステム,  

本文: PDF(293.1KB)
>>論文を購入


あらまし: 
本論文では,新たな組合せオークションプロトコルとしてAM-MB(Average-Max-Minimal-Bundle)プロトコルを提案する.AM-MBプロトコルの特長を以下の(i),(ii),及び(iii)に示す:(i) strategy-proofである.すなわち,真の申告が支配戦略である.(ii)勝者決定及び支払額計算のための計算コストが小さい.これは,AM-MBプロトコルでは組合せオークションを扱うが,バンドルをグリーディな方法で割り当てることによって,組合せ最適化問題を解く必要がないためである.(iii)既存のM-MB(Max-Minimal-Bundle)プロトコルと比較して社会的余剰及び収益が大きい.既存のM-MBプロトコルは,(i)及び(ii)を満たす組合せオークションプロトコルである.更に,本論文では,AM-MBプロトコルを公開競上げ式組合せオークションプロトコルに拡張する.本公開競上げ式組合せオークションでは,正直な(straightforward)入札が事後ナッシュ均衡であることを証明する.