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

• Autorzy: Takahashi S. , Izunaga Y. , Watanabe N.

Identyfikatory

DOI

10.5277/ord180105

• Języki publikacji: EN

Abstrakty

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.

Słowa kluczowe

EN

multi-unit auctions; approximation algorithm; experiment

PL

algorytm aproksymacyjny; eksperyment

• Wydawca: Oficyna Wydawnicza Politechniki Wrocławskiej
• Czasopismo: Operations Research and Decisions
• Rocznik: 2018
• Tom: Vol. 28, No. 1
• Strony: 95--115
• Opis fizyczny: Bibliogr. 9 poz., rys.

Twórcy

autor

Takahashi S.

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

autor

Izunaga Y.

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

autor

Watanabe N.

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

Bibliografia

• [1] AUSUBEL L.M., An efficient ascending-bid auction for multiple objects, Am. Econ. Rev., 2004, 9, 1452 –1475.
• [2] CHEN Y., TAKEUCHI K., Multi-object auctions with package bidding: An experimental comparison of iBEA and Vickrey, Games Econ. Behav., 2010, 68, 557–569.
• [3] DOBZINSKI S., NISAN N., Multi-unit auctions. Beyond Roberts, J. Econ. Theory, 2015, 156, 14–44.
• [4] DYER M.E., An O(n) algorithm for the multiple-choice knapsack linear program, Math. Progr., 1984, 29, 57–63.
• [5] KAGEL J.H., LEVIN D., Behavior in multi-unit demand auctions. Experiments with uniform price and dynamic Vickrey auctions, Econometrica, 2001, 69, 413–451.
• [6] KAGEL J.H., KINROSS S., LEVIN D., Comparing efficient multi-object auction institutions, Mimeo, Ohio State University, 2001.
• [7] 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.
• [8] KOTHARI A., PARKES D.C., SURI S., Approximately-strategy proof and tractable multi-unit auctions, Dec. Supp. Syst., 2005, 39, 105–121.
• [9] TAKAHASHI S., SHIGENO M., Approximation algorithms for a winner determination problem of singleitem multi-unit auctions, JSIAM Letters, 2011, 3, 29–32.

Uwagi

PL

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).