An Approach to VCG-like Approximate Allocation and Pricing for Large-scale Multi-unit Combinatorial Auctions

• Item type: JInfP(1)
• 公開日: 2013-01-15
• タイトル: An Approach to VCG-like Approximate Allocation and Pricing for Large-scale Multi-unit Combinatorial Auctions
• タイトル / 言語: en
• タイトル: An Approach to VCG-like Approximate Allocation and Pricing for Large-scale Multi-unit Combinatorial Auctions
• 言語: eng
• キーワード / 主題Scheme: Other
• キーワード / 主題: [Special Issue on Theory and Application of Agent Research] combinatorial auction, approximation, resource allocation, pricing algorithm
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: Faculty of Informatics, Shizuoka University Hamamatsu
• 著者所属(英): en
• 著者所属(英): Faculty of Informatics, Shizuoka University Hamamatsu
• 著者名: Naoki, Fukuta
• 著者名(英): Naoki, Fukuta
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: A multi-unit combinatorial auction is a combinatorial auction that has some items that can be seen as indistinguishable. Although the mechanism can be applied to dynamic electricity auctions and various purposes, it is difficult to apply to large-scale auction problems due to its computational intractability. In this paper, I present an idea and an analysis about an approximate allocation and pricing algorithm that is capable of handling multi-unit auctions. The analysis shows that the algorithm effectively produces approximation allocations that are necessary in pricing. Furthermore, the algorithm can be seen as an approximation of VCG (Vickrey-Clarke-Groves) mechanism satisfying budget balance condition and bidders' individual rationality without having unrealistic assumptions on bidders' behaviors. I show that the proposed allocation algorithm successfully produced good allocations for those problems that could not be easily solved by ordinary LP solvers due to hard time constraints.
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: A multi-unit combinatorial auction is a combinatorial auction that has some items that can be seen as indistinguishable. Although the mechanism can be applied to dynamic electricity auctions and various purposes, it is difficult to apply to large-scale auction problems due to its computational intractability. In this paper, I present an idea and an analysis about an approximate allocation and pricing algorithm that is capable of handling multi-unit auctions. The analysis shows that the algorithm effectively produces approximation allocations that are necessary in pricing. Furthermore, the algorithm can be seen as an approximation of VCG (Vickrey-Clarke-Groves) mechanism satisfying budget balance condition and bidders' individual rationality without having unrealistic assumptions on bidders' behaviors. I show that the proposed allocation algorithm successfully produced good allocations for those problems that could not be easily solved by ordinary LP solvers due to hard time constraints.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA00700121
• 書誌情報: Journal of information processing; 巻 21, 号 1, p. 9-15, 発行日 2013-01-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-6652
• 出版者 / 言語: ja
• 出版者: 情報処理学会