著者

福田 直樹 伊藤 孝行

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会論文誌. D, 情報・システム (ISSN:18804535)

巻号頁・発行日

vol.90, no.9, pp.2324-2335, 2007-09-01

被引用文献数

5

---

本論文では,10,000〜100,000を超えるような多数の入札がある組合せオークションに対して,勝者決定の近似解法を提案し,その特性を評価する.提案アルゴリズムでは,従来手法のLehmannアルゴリズムにおける入札ソート順位の決定因子に着目し,更に山登り法及びシミュレーテッドアニーリング(SA)による解の洗練を行うことで,安定して高い最適性を持った解を得る.入札数が1000程度の場合に,本提案手法では最適解に対して平均して0.997程度の総落札額が得られる解を見つけられることを示す.更に,従来の最適解探索手法と比較して十分に高速に動作し,10,000を超える入札数をもつオークションに対して数秒(入札数10,000)から数分程度(入札数100,000)の実用的な時間で計算が行えることを示す.本近似解法の限界点の一つとして,本近似解法を用いた組合せオークションが一般には真実申告最良とはならないことを,Monotonicityという条件が成り立たないことから示す.一方で,真実申告最良とはならないものの,本近似解法の一部では,解探索の過程におけるランダム性を排除し順序性を保存することで,近似解に対して特定の好ましい性質を満たすことを示す.