An approximation algorithm for multi-unit auctions: numerical and subject experiments
Languages of publication
In multi-unit auctions for a single item, the Vickrey–Clarke–Groves mechanism (VCG) attains allocative efficiency but suffers from its computational complexity. Takahashi and Shigeno thus proposed a greedy based approximation algorithm (GBA). In a subject experiment there was truly a difference in efficiency rate but no significant difference in seller’s revenue between GBA and VCG. It is not clear in theory whether each bidder will submit his or her true unit valuations in GBA. We show, however, that in a subject experiment there was no significant difference in the number of bids that obey “almost” truth-telling between GBA and VCG. As for individual bidding behavior, GBA and VCG show a sharp contrast when a human bidder competes against machine bidders; underbidding was observed in GBA, while overbidding was observed in VCG. Some results in a numerical experiment are also provided prior to reporting those observations.
- Graduate School of Informatics and Engineering, The University of Electro-Communications, Chofu, Tokyo, Japan
- Faculty of Business Sciences, University of Tsukuba, Otsuka Bunkyo, Tokyo, Japan
- Graduate School of Business Administration, Keio University, 4-1-1 Hiyoshi Kohoku, Yokohama, Kanagawa 223-8526, Japan
- AUSUBEL L.M., An efficient ascending-bid auction for multiple objects, Am. Econ. Rev., 2004, 9, 1452–1475.
- CHEN Y., TAKEUCHI K., Multi-object auctions with package bidding: An experimental comparison of iBEA and Vickrey, Games Econ. Behav., 2010, 68, 557–569.
- DOBZINSKI S., NISAN N., Multi-unit auctions. Beyond Roberts, J. Econ. Theory, 2015, 156, 14–44.
- DYER M.E., An O(n) algorithm for the multiple-choice knapsack linear program, Math. Progr., 1984, 29, 57–63.
- KAGEL J.H., LEVIN D., Behavior in multi-unit demand auctions. Experiments with uniform price and dynamic Vickrey auctions, Econometrica, 2001, 69, 413–451.
- KAGEL J.H., KINROSS S., LEVIN D., Comparing efficient multi-object auction institutions, Mimeo, Ohio State University, 2001.
- KAGEL J.H., LEVIN D., Auctions. A survey of experimental research, [In:] J.H. Kagel, A.E. Roth (Eds.), Handbook of Experimental Economics, Vol. II, Princeton University Press, 2016, 563–637.
- KOTHARI A., PARKES D.C., SURI S., Approximately-strategy proof and tractable multi-unit auctions, Dec. Supp. Syst., 2005, 39, 105–121.
- TAKAHASHI S., SHIGENO M., Approximation algorithms for a winner determination problem of singleitem multi-unit auctions, JSIAM Letters, 2011, 3, 29–32.
Publication order reference