エージェント間に外部性が存在する場合の戦略的操作不可能な割当てメカニズムの提案

櫻井 祐子  沖本 天太  横尾 真  

誌名
電子情報通信学会論文誌 D   Vol.J96-D   No.12   pp.2960-2969
発行日: 2013/12/01
Online ISSN: 1881-0225
DOI: 
Print ISSN: 1880-4535
論文種別: 特集論文 (ソフトウェアエージェントとその応用論文特集)
専門分野: 理論
キーワード: 
メカニズムデザイン,  ソーシャルネットワーク,  VCGメカニズム,  戦略的操作不可能性,  

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


あらまし: 
本論文では,エージェント間に外部性が存在する場合を対象に戦略的操作不可能な割当てメカニズムの提案を行う.検索連動広告オークションなど,エージェントらが他のエージェントに対して選好,すなわち,誰と一緒に勝者になるかによって異なる評価値をもつことが考えられる.そこで,本論文ではエージェント間の関係について,エージェントをノード,外部性を枝で表現する重み付き有向グラフ(ソーシャルネットワーク)で表現する.メカニズムを設計する上で,メカニズムが満たすべき性質が幾つか存在するが,我々は不可能性定理として,任意の評価値を表明可能な場合,どのようなメカニズムをもってしても,戦略的操作不可能性,個人合理性,パレート効率性,非損失性の四つの望ましい性質を同時に満足するメカニズムが存在しないことを示す.そこで,表明可能な評価値を限定させることで,既存のVickrey-Clarke-Groves (VCG)メカニズムが適用可能な領域が存在することを示し,その制約条件を緩和したメカニズムを提案する.更に,VCGメカニズムを改良したVCG+メカニズムの提案を行う.最後に,計算機実験によってVCGメカニズム,VCG+メカニズムの性能の評価を行う.