自動メカニズムデザインを利用した組合せオークションのルール抽出アルゴリズムの提案

• Item type: Journal(1)
• 公開日: 2012-08-15
• タイトル: 自動メカニズムデザインを利用した組合せオークションのルール抽出アルゴリズムの提案
• タイトル / 言語: en
• タイトル: A Rule Extraction Algorithm for Combinatorial Auctions with Automated Mechanisms Design
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: [一般論文] 組合せオークション，ゲーム理論，メカニズムデザイン，架空名義入札，最適化
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 九州大学大学院システム情報科学府情報学専攻
• 著者所属: 九州大学大学院システム情報科学府情報学専攻
• 著者所属: 九州大学大学院システム情報科学府情報学専攻
• 著者所属: 九州大学大学院システム情報科学府情報学専攻
• 著者所属: 九州大学大学院システム情報科学府情報学専攻
• 著者所属(英): en
• 著者所属(英): Graduate School of ISEE, Kyushu University
• 著者所属(英): en
• 著者所属(英): Graduate School of ISEE, Kyushu University
• 著者所属(英): en
• 著者所属(英): Graduate School of ISEE, Kyushu University
• 著者所属(英): en
• 著者所属(英): Graduate School of ISEE, Kyushu University
• 著者所属(英): en
• 著者所属(英): Graduate School of ISEE, Kyushu University
• 著者名: 毛利, 貴之; 杉町, 勇和; 東藤, 大樹; 岩崎, 敦; 横尾, 真
• 著者名(英): Takayuki, Mouri; Toshikazu, Sugimachi; Taiki, Todo; Atsushi, Iwasaki; Makoto, Yokoo
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 一般に組合せオークションのためのメカニズムは割当て規則と支払い規則の2つの関数によって構成される．メカニズムに関する著名な研究成果として，理論的に優れた性質を持つVickrey-Clarke-Groves（VCG）メカニズムが知られている．しかしながら，VCGメカニズムにはいくつかの問題点があると近年指摘されている．これまでに，その問題に対して頑健性が保証されるメカニズムがいくつか提案されている．従来，これらの関数は人手で設計されてきたが，多大な時間と労力がかかる．そこで近年，整数計画法を利用した自動設計の手法（自動メカニズムデザイン）が提案されている．しかしながら，自動メカニズムデザインは小規模な問題にしか対応できず，現実の問題サイズを扱うことができない．そのため従来研究では，小規模な問題を解き，出力された結果の中から特徴的な結果を抽出し，一般に適用可能なルールを求めようとしている．それでも一般的なルールを得るには人手による部分がまだまだ多い．また，得られたルールが必ずしも適切だとは限らず，別途検証する必要がある．本論文では，自動メカニズムデザインの出力結果から一般的なルールを抽出するアルゴリズムを提案する．具体的には商品の割当て方法や支払額を決定する関数は，あるしきい値を超えているかどうかで勝敗が決まるとし，そのしきい値を出力するアルゴリズムである．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Automated mechanism design (AMD) provides a novel scheme to design social choice rules (e.g., combinatorial auction mechanisms) by using mathematical programming technique. However, it only returns a discretized set of outcomes, i.e., allocations and the associated payments given possible type profiles. Therefore, for large combinatorial auction problems, there has been no scheme to effectively generalize a social choice rule for a continuous set of outcomes in the literature of mechanism design. In this paper, we formalize the problem as a rule extraction problem. We then propose a new algorithm to automatically extract a payment rule of a combinatorial auction mechanism from the discretized set of outcomes obtained from AMD. Our experiments reveal that the proposed algorithm successfully extracts payment rules of two existing combinatorial auction mechanisms that is either strategy-proof or false-name-proof.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN00116647
• 書誌情報: 情報処理学会論文誌; 巻 53, 号 8, p. 2006-2017, 発行日 2012-08-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7764