Tuesday, 15:45 - 16:10 h, Room: H 3027


Takahashi Satoshi
2-approximation algorithms for the winner determination problem in VCG based single-item multi-unit auctions

Coauthors: Yoichi Izunaga, Maiko Shigeno, Satoshi Takahashi, Naoki Watanabe


This paper studies the winner determination problem in Vickrey-Clarke-Groves (VCG) based single-item multi-unit auctions: given a set of bids in such an auction, find an allocation of units of an item to bidders that maximizes the seller's revenue. (The seller can keep some units of the item.) This problem is known to be NP-hard. We thus propose two simple 2-approximation algorithms for the problem. One is a linear time algorithm and the other is a greedy algorithm.
Numerical experiments and human subject experiments were conducted to evaluate the computational efficiency and economic efficiency of these approximation algorithms.
Our results are as follows. (1) Approximate ratios of the algorithms are at least 95% in numerical experiments. (2) Under-bidding was observed in human subject experiments although the VCG mechanism theoretically induces bidders to tell their valuation truthfully.


Talk 2 of the contributed session Tue.3.H 3027
"Applications and algorithms" [...]
Cluster 7
"Finance & economics" [...]


  There are three major facts that should be watched out for in all payday loans in the United States. Since its introduction in the market buying Cialis can be exclusively in pharmacy chains with a prescription from a doctor. I agree that this is very inconvenient and takes a lot of time and effort.