IDEAS home Printed from https://ideas.repec.org/a/wut/journl/v1y2018p95-115id1351.html
   My bibliography  Save this article

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

Author

Listed:
  • Satoshi Takahashi
  • Yoichi Izunaga
  • Naoki Watanabe

Abstract

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.

Suggested Citation

  • Satoshi Takahashi & Yoichi Izunaga & Naoki Watanabe, 2018. "An approximation algorithm for multi-unit auctions: numerical and subject experiments," Operations Research and Decisions, Wroclaw University of Science and Technology, Faculty of Management, vol. 28(1), pages 95-115.
    • Handle: RePEc:wut:journl:v:1:y:2018:p:95-115:id:1351
    DOI: 10.5277/ord180105
    as

    Download full text from publisher

    File URL: https://ord.pwr.edu.pl/assets/papers_archive/1351%20-%20published.pdf
    Download Restriction: no
    File URL: https://libkey.io/10.5277/ord180105?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    References listed on IDEAS

    as
    1. John H. Kagel & Alvin E. Roth, 2016. "The Handbook of Experimental Economics, Volume 2," Economics Books, Princeton University Press, edition 1, volume 2, number 10874.
    2. Kagel, John H & Levin, Dan, 2001. "Behavior in Multi-unit Demand Auctions: Experiments with Uniform Price and Dynamic Vickrey Auctions," Econometrica, Econometric Society, vol. 69(2), pages 413-454, March.
    3. Dobzinski, Shahar & Nisan, Noam, 2015. "Multi-unit auctions: Beyond Roberts," Journal of Economic Theory, Elsevier, vol. 156(C), pages 14-44.
    4. Lawrence M. Ausubel, 2004. "An Efficient Ascending-Bid Auction for Multiple Objects," American Economic Review, American Economic Association, vol. 94(5), pages 1452-1475, December.
    5. Chen, Yan & Takeuchi, Kan, 2010. "Multi-object auctions with package bidding: An experimental comparison of Vickrey and iBEA," Games and Economic Behavior, Elsevier, vol. 68(2), pages 557-579, March.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Satoshi Takahashi & Yoichi Izunaga & Naoki Watanabe, 2019. "VCG mechanism for multi-unit auctions and appearance of information: a subject experiment," Evolutionary and Institutional Economics Review, Springer, vol. 16(2), pages 357-374, December.
    2. Satoshi Takahashi & Yoichi Izunaga & Naoki Watanabe, 2022. "An experimental study of VCG mechanism for multi-unit auctions: competing with machine bidders," Evolutionary and Institutional Economics Review, Springer, vol. 19(1), pages 97-117, April.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Takehito Masuda & Ryo Mikami & Toyotaka Sakai & Shigehiro Serizawa & Takuma Wakayama, 2022. "The net effect of advice on strategy-proof mechanisms: an experiment for the Vickrey auction," Experimental Economics, Springer;Economic Science Association, vol. 25(3), pages 902-941, June.
    2. Alessandra Casella & Adam B. Cox, 2018. "A Property Rights Approach to Temporary Work Visas," The Journal of Legal Studies, University of Chicago Press, vol. 47(S1), pages 195-227.
    3. Dan Levin, 2005. "Demand Reduction in Multi-Unit Auctions: Evidence from a Sportscard Field Experiment: Comment," American Economic Review, American Economic Association, vol. 95(1), pages 467-471, March.
    4. Takehito Masuda & Ryo Mikami & Toyotaka Sakai & Shigehiro Serizawa & Takuma Wakayama, 2020. "The net effect of advice on strategy-proof mechanisms: An experiment for the Vickrey auction," ISER Discussion Paper 1109, Institute of Social and Economic Research, Osaka University.
    5. Kagel, John H. & Levin, Dan, 2009. "Implementing efficient multi-object auction institutions: An experimental study of the performance of boundedly rational agents," Games and Economic Behavior, Elsevier, vol. 66(1), pages 221-237, May.
    6. Dirk Engelmann & Veronika Grimm, 2009. "Bidding Behaviour in Multi-Unit Auctions - An Experimental Investigation," Economic Journal, Royal Economic Society, vol. 119(537), pages 855-882, April.
    7. Schnitzlein, Charles R. & Shao, Minjie, 2013. "Capacity constraints and the winner's curse in multi-unit common value auctions," The Quarterly Review of Economics and Finance, Elsevier, vol. 53(2), pages 188-201.
    8. Matt Van Essen, 2013. "Making efficient public good decisions using an augmented Ausubel auction," Economic Theory Bulletin, Springer;Society for the Advancement of Economic Theory (SAET), vol. 1(1), pages 57-68, May.
    9. Chen, Yan & Jiang, Ming & Kesten, Onur & Robin, Stéphane & Zhu, Min, 2018. "Matching in the large: An experimental study," Games and Economic Behavior, Elsevier, vol. 110(C), pages 295-317.
    10. Jarl G. Kallberg & Crocker H. Liu & Adam Nowak, 2021. "An Empirical Analysis of Double Round Auctions," Real Estate Economics, American Real Estate and Urban Economics Association, vol. 49(2), pages 531-555, June.
    11. Committee, Nobel Prize, 2020. "Improvements to auction theory and inventions of new auction formats," Nobel Prize in Economics documents 2020-2, Nobel Prize Committee.
    12. Vohra, Rakesh V., 2015. "Combinatorial Auctions," Handbook of Game Theory with Economic Applications,, Elsevier.
    13. March, Christoph, 2021. "Strategic interactions between humans and artificial intelligence: Lessons from experiments with computer players," Journal of Economic Psychology, Elsevier, vol. 87(C).
    14. Takehito Masuda & Ryo Mikami & Toyotaka Sakai & Shigehiro Serizawa & Takuma Wakayama, 2020. "The net effect of advice on strategy-proof mechanisms: An experiment for the Vickrey auction," ISER Discussion Paper 1109r, Institute of Social and Economic Research, Osaka University, revised May 2021.
    15. Dobzinski, Shahar & Lavi, Ron & Nisan, Noam, 2012. "Multi-unit auctions with budget limits," Games and Economic Behavior, Elsevier, vol. 74(2), pages 486-503.
    16. Christer Andersson & Ola Andersson & Tommy Andersson, 2013. "Sealed bid auctions versus ascending bid auctions: an experimental study," Review of Economic Design, Springer;Society for Economic Design, vol. 17(1), pages 1-16, March.
    17. Anabela Botelho & Lígia Costa Pinto & Eduarda Fernandes, 2013. "More on the dynamic Vickrey mechanism for multi-unit auctions: an experimental study on the emission permits initial auction," NIMA Working Papers 53, Núcleo de Investigação em Microeconomia Aplicada (NIMA), Universidade do Minho.
    18. Matsushima Hitoshi, 2018. "Connected Price Dynamics with Revealed Preferences and Auctioneer’s Discretion in VCG Combinatorial Auction," The B.E. Journal of Theoretical Economics, De Gruyter, vol. 18(1), pages 1-16, January.
    19. Chen, Ning & Ghosh, Arpita & Lambert, Nicolas S., 2014. "Auctions for social lending: A theoretical analysis," Games and Economic Behavior, Elsevier, vol. 86(C), pages 367-391.
    20. Hitoshi Matsushima, 2015. "Connected Price Dynamics with Revealed Preferences and Auctioneer’s Discretionin VCG Combinatorial Auction (Published in the B. E. Journal of Theoretical Economics 18 (1), 2018.)," CARF F-Series CARF-F-359, Center for Advanced Research in Finance, Faculty of Economics, The University of Tokyo.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:wut:journl:v:1:y:2018:p:95-115:id:1351. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Adam Kasperski (email available below). General contact details of provider: https://edirc.repec.org/data/iopwrpl.html .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.