- Autor
- Takahashi Satoshi (The University of Electro-Communications, Chofu, Tokyo, Japan), Izunaga Yoichi (University of Tsukuba, Otsuka Bunkyo, Tokyo, Japan), Watanabe Naoki (Keio University, Japan)
- Tytuł
- An Approximation Algorithm for Multi-Unit Auctions : Numerical and Subject Experiments
- Źródło
- Operations Research and Decisions, 2018, vol. 28, no. 1, s. 95-115, rys., tab., bibliogr. 9 poz.
- Słowa kluczowe
- Aukcje, Algorytmy, Eksperyment badawczy
Auctions, Algorithms, Scientific experiment - Uwagi
- summ.
This research is supported by JSPS Grant-in-Aid for Young Scientists (B) 26870200 and Grant-in-Aid for Scientific Research (B) 15H02972 (Takahashi) and Japan Center for Economic Research (Watanabe) - Abstrakt
- 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. (original abstract)
- Dostępne w
- Biblioteka Główna Uniwersytetu Ekonomicznego w Krakowie
Biblioteka SGH im. Profesora Andrzeja Grodka
Biblioteka Główna Uniwersytetu Ekonomicznego w Katowicach - Pełny tekst
- Pokaż
- Bibliografia
-
- 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.
- Cytowane przez
- ISSN
- 2081-8858
- Język
- eng
- URI / DOI
- http://dx.doi.org/10.5277/ord180105
