An approximation algorithm for multi-unit auctions: numerical and subject experiments

• Authors: TAKAHASHI Satoshi , IZUNAGA Yoichi , WATANABE Naoki
• Languages of publication: EN

Abstracts

EN

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.

Keywords

EN

multi-unit auctions; approximation algorithm; experiment

• Publisher: Politechnika Wrocławska. Oficyna Wydawnicza Politechniki Wrocławskiej
• Journal: Operations Research and Decisions
• Year: 2018
• Volume: 28
• Issue: 1
• Pages: 95-115

Contributors

author

TAKAHASHI Satoshi

• Graduate School of Informatics and Engineering, The University of Electro-Communications, Chofu, Tokyo, Japan

author

IZUNAGA Yoichi

• Faculty of Business Sciences, University of Tsukuba, Otsuka Bunkyo, Tokyo, Japan

author

WATANABE Naoki

• Graduate School of Business Administration, Keio University, 4-1-1 Hiyoshi Kohoku, Yokohama, Kanagawa 223-8526, Japan

References

• 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.

Identifiers

DOI

10.5277/ord180105