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

摘要

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