FIT2015第14回情報科学技術フォーラム 開催日:2015年9月15日(火)~17日(木) 会場:愛媛大学城北キャンパス
抄録
RF-005
外部性を考慮した複数枠入札に対応可能なスポンサードサーチオークション
今田隆資・藤田桂英(農工大)
スポンサードサーチオークションにおいて,外部性の考慮が重要であるとわかっている.本論文では,従来の入札者1人につき広告1つに限定されず,複数の広告入札を考慮した外部性を用いる近似アルゴリズムを提案する.複数の広告入札が可能になることで,入札者の持つ枠数に対する価値を直接反映させることができる.本提案手法では,組み合わせオークションの考え方を用いて複数入札に対応させ,動的計画法を用いて多項式時間で近似解を発見できる.さらに,提案したアルゴリズムについて,計算量や近似率の証明を行い,シミュレーション実験を行った.実験の結果,全探索では計算できない場合でも,近似解を発見できることを示した.