文章基本信息

标题：An Approach to VCG-like Approximate Allocation and Pricing for Large-scale Multi-unit Combinatorial Auctions
本地全文：下载
作者：Naoki Fukuta
期刊名称：Information and Media Technologies
电子版ISSN：1881-0896
出版年度：2013
卷号：8
期号：1
页码：25-31
DOI：10.11185/imt.8.25
出版社：Information and Media Technologies Editorial Board
摘要：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.
关键词：combinatorial auction;approximation;resource allocation;pricing algorithm