IDEAS home Printed from https://ideas.repec.org/p/hhs/lunewp/2012_017.html
   My bibliography  Save this paper

Multi-Item Vickery-English-Dutch Auctions

Author

Listed:

Abstract

Assuming that bidders wish to acquire at most one item, this paper defines a polynomial time multiitem auction that locates the VCG prices in a finite number of iterations for any given starting prices. This auction is called the Vickrey-English-Dutch auction and it contains the Vickrey-English auction (J.K. Sankaran, Math. Soc. Sci. 28:143–150, 1994) and the Vickrey-Dutch auction (D. Mishra and D. Parkes, Games Econ. Behav. 66:326–347, 2009) as special cases. Several properties of this iterative auction are provided. It is, for example, demonstrated that the number of iterations from the starting prices to the VCG prices can be calculated using a measure based on the Chebyshev metric. By means of numerical experiments, it is showed that when the auctioneer knows the bidders’ value distributions, the Vickrey-English-Dutch auction is weakly faster than the Vickrey- English auction and the Vickrey-Dutch auction in 89 percent and 99 percent, respectively, of the investigated problems. A greedy version of the Vickrey-English-Dutch auction is demonstrated to perform even better in the simulation studies. In fact, it follows the theoretically shortest path in 63 percent of the investigated problems.

Suggested Citation

  • Andersson, Tommy & Erlanson, Albin, 2012. "Multi-Item Vickery-English-Dutch Auctions," Working Papers 2012:17, Lund University, Department of Economics, revised 15 Jan 2013.
    • Handle: RePEc:hhs:lunewp:2012_017
    as

    Download full text from publisher

    File URL: http://project.nek.lu.se/publications/workpap/papers/WP12_17.pdf
    Download Restriction: no
    ---><---

    Other versions of this item:

    References listed on IDEAS

    as
    1. Tommy Andersson & Christer Andersson, 2012. "Properties of the DGS-Auction Algorithm," Computational Economics, Springer;Society for Computational Economics, vol. 39(2), pages 113-133, February.
    2. Ning Sun & Zaifu Yang, 2009. "Strategy Proof And Privacy Preserving Fair Allocation Mechanism," The Japanese Economic Review, Japanese Economic Association, vol. 60(2), pages 143-151, June.
    3. de Vries, Sven & Schummer, James & Vohra, Rakesh V., 2007. "On ascending Vickrey auctions for heterogeneous objects," Journal of Economic Theory, Elsevier, vol. 132(1), pages 95-118, January.
    4. Demange, Gabrielle & Gale, David, 1985. "The Strategy Structure of Two-sided Matching Markets," Econometrica, Econometric Society, vol. 53(4), pages 873-888, July.
    5. Mishra, Debasis & Talman, Dolf, 2010. "Characterization of the Walrasian equilibria of the assignment model," Journal of Mathematical Economics, Elsevier, vol. 46(1), pages 6-20, January.
    6. Ausubel Lawrence M & Milgrom Paul R, 2002. "Ascending Auctions with Package Bidding," The B.E. Journal of Theoretical Economics, De Gruyter, vol. 1(1), pages 1-44, August.
    7. Cramton, Peter, 1998. "Ascending auctions," European Economic Review, Elsevier, vol. 42(3-5), pages 745-756, May.
    8. Bikhchandani, Sushil & Ostroy, Joseph M., 2002. "The Package Assignment Model," Journal of Economic Theory, Elsevier, vol. 107(2), pages 377-406, December.
    9. Gul, Faruk & Stacchetti, Ennio, 2000. "The English Auction with Differentiated Commodities," Journal of Economic Theory, Elsevier, vol. 92(1), pages 66-95, May.
    10. Andersson, T.D. & Andersson, C. & Talman, A.J.J., 2010. "Sets in Excess Demand in Ascending Auctions with Unit-Demand Bidders," Other publications TiSEM c7482a22-cb73-428b-9cc0-e, Tilburg University, School of Economics and Management.
    11. Edward Clarke, 1971. "Multipart pricing of public goods," Public Choice, Springer, vol. 11(1), pages 17-33, September.
    12. Elena Grigorieva & P. Herings & Rudolf Müller & Dries Vermeulen, 2007. "The private value single item bisection auction," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 30(1), pages 107-118, January.
    13. Mishra, Debasis & Parkes, David C., 2007. "Ascending price Vickrey auctions for general valuations," Journal of Economic Theory, Elsevier, vol. 132(1), pages 335-366, January.
    14. Engelbrecht-Wiggans, Richard & Kahn, Charles M., 1991. "Protecting the winner : Second-price versus oral auctions," Economics Letters, Elsevier, vol. 35(3), pages 243-248, March.
    15. Demange, Gabrielle & Gale, David & Sotomayor, Marilda, 1986. "Multi-Item Auctions," Journal of Political Economy, University of Chicago Press, vol. 94(4), pages 863-872, August.
    16. Motty Perry & Philip J. Reny, 2005. "An Efficient Multi-Unit Ascending Auction," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 72(2), pages 567-592.
    17. William Vickrey, 1961. "Counterspeculation, Auctions, And Competitive Sealed Tenders," Journal of Finance, American Finance Association, vol. 16(1), pages 8-37, March.
    18. Lawrence M. Ausubel, 2006. "An Efficient Dynamic Auction for Heterogeneous Commodities," American Economic Review, American Economic Association, vol. 96(3), pages 602-629, June.
    19. Sushil Bikhchandani & Sven de Vries & James Schummer & Rakesh V. Vohra, 2011. "An Ascending Vickrey Auction for Selling Bases of a Matroid," Operations Research, INFORMS, vol. 59(2), pages 400-413, April.
    20. 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.
    21. Mishra, Debasis & Parkes, David C., 2009. "Multi-item Vickrey-Dutch auctions," Games and Economic Behavior, Elsevier, vol. 66(1), pages 326-347, May.
    22. Muysken, J. & Rutten, T., 2002. "Disability in the Netherlands: another dutch disease?," Research Memorandum 051, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    23. Leonard, Herman B, 1983. "Elicitation of Honest Preferences for the Assignment of Individuals to Positions," Journal of Political Economy, University of Chicago Press, vol. 91(3), pages 461-479, June.
    24. Groves, Theodore, 1973. "Incentives in Teams," Econometrica, Econometric Society, vol. 41(4), pages 617-631, July.
    25. Sankaran, Jayaram K., 1994. "On a dynamic auction mechanism for a bilateral assignment problem," Mathematical Social Sciences, Elsevier, vol. 28(2), pages 143-150, October.
    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. Zhou, Yu & Serizawa, Shigehiro, 2023. "Multi-object auction design beyond quasi-linearity: Leading examples," Games and Economic Behavior, Elsevier, vol. 140(C), pages 210-228.
    2. Ingebretsen Carlson, Jim, 2015. "An Approximate Auction," Working Papers 2015:19, Lund University, Department of Economics.
    3. Isa Hafalir & Onur Kesten & Katerina Sherstyuk & Cong Tao, 2023. "When Speed is of Essence: Perishable Goods Auctions," Working Papers 202310, University of Hawaii at Manoa, Department of Economics.
    4. Jim Ingebretsen Carlson, 2020. "A speedy auction using approximated bidders’ preferences," Annals of Operations Research, Springer, vol. 288(1), pages 65-93, May.
    5. Akiyoshi Shioura, 2017. "On the Partnership formation problem," The Journal of Mechanism and Institution Design, Society for the Promotion of Mechanism and Institution Design, University of York, vol. 2(1), pages 105-140, December.
    6. Kazuo Murota & Akiyoshi Shioura & Zaifu Yang, 2014. "Time Bounds for Iterative Auctions: A Unified Approach by Discrete Convex Analysis," Discussion Papers 14/27, Department of Economics, University of York.
    7. A. Talman & Zaifu Yang, 2015. "An efficient multi-item dynamic auction with budget constrained bidders," International Journal of Game Theory, Springer;Game Theory Society, vol. 44(3), pages 769-784, August.
    8. Gerard van der Laan & Dolf Talman & Zaifu Yang, 2018. "Equilibrium in the Assignment Market under Budget Constraints," Discussion Papers 18/17, Department of Economics, University of York.
    9. Isa Hafalir & Donglai Luo & Cong Tao, 2024. "Istanbul Flower Auction: The Need for Speed," Papers 2404.08288, arXiv.org.
    10. Ingebretsen Carlson, Jim, 2016. "An Auction with Approximated Bidder Preferences - When an Auction has to be Quick," Working Papers 2016:12, Lund University, Department of Economics.
    11. Andersson, Tommy & Gudmundsson, Jens & Talman, Dolf & Yang, Zaifu, 2014. "A competitive partnership formation process," Games and Economic Behavior, Elsevier, vol. 86(C), pages 165-177.
    12. Cerezo Sánchez, David, 2017. "An Optimal ICO Mechanism," MPRA Paper 81285, University Library of Munich, Germany.
    13. Fuqiang Lu & Yanli Hu & Hualing Bi & Min Huang & Meng Zhao, 2018. "An Auction Approach for Cost and Schedule Management of IT Outsourcing Project," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 35(05), pages 1-23, October.
    14. Tierney, Ryan, 2019. "The problem of multiple commons: A market design approach," Games and Economic Behavior, Elsevier, vol. 114(C), pages 1-27.
    15. Kazuo Murota, 2016. "Discrete convex analysis: A tool for economics and game theory," The Journal of Mechanism and Institution Design, Society for the Promotion of Mechanism and Institution Design, University of York, vol. 1(1), pages 151-273, December.
    16. Zaifu Yang & Jingsheng Yu, 2018. "Efficient Ascending Menu Auctions with Budget Constrained Bidders," Discussion Papers 18/09, Department of Economics, University of York.

    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. Mishra, Debasis & Parkes, David C., 2007. "Ascending price Vickrey auctions for general valuations," Journal of Economic Theory, Elsevier, vol. 132(1), pages 335-366, January.
    2. Mishra, Debasis & Parkes, David C., 2009. "Multi-item Vickrey-Dutch auctions," Games and Economic Behavior, Elsevier, vol. 66(1), pages 326-347, May.
    3. Sushil Bikhchandani & Sven de Vries & James Schummer & Rakesh V. Vohra, 2011. "An Ascending Vickrey Auction for Selling Bases of a Matroid," Operations Research, INFORMS, vol. 59(2), pages 400-413, April.
    4. Tomoya Kazumura & Shigehiro Serizawa, 2016. "Efficiency and strategy-proofness in object assignment problems with multi-demand preferences," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 47(3), pages 633-663, October.
    5. Mishra, Debasis & Talman, Dolf, 2010. "Characterization of the Walrasian equilibria of the assignment model," Journal of Mathematical Economics, Elsevier, vol. 46(1), pages 6-20, January.
    6. Ingebretsen Carlson, Jim, 2016. "An Auction with Approximated Bidder Preferences - When an Auction has to be Quick," Working Papers 2016:12, Lund University, Department of Economics.
    7. De Liu & Adib Bagh, 2020. "Preserving Bidder Privacy in Assignment Auctions: Design and Measurement," Management Science, INFORMS, vol. 66(7), pages 3162-3182, July.
    8. Xu, Su Xiu & Huang, George Q., 2014. "Efficient auctions for distributed transportation procurement," Transportation Research Part B: Methodological, Elsevier, vol. 65(C), pages 47-64.
    9. Albin Erlanson, 2014. "The Duo-Item Bisection Auction," Computational Economics, Springer;Society for Computational Economics, vol. 43(1), pages 15-31, January.
    10. Baranov, Oleg, 2018. "An efficient ascending auction for private valuations," Journal of Economic Theory, Elsevier, vol. 177(C), pages 495-517.
    11. , & ,, 2015. "Strategy-proofness and efficiency with non-quasi-linear preferences: a characterization of minimum price Walrasian rule," Theoretical Economics, Econometric Society, vol. 10(2), May.
    12. Zhou, Yu & Serizawa, Shigehiro, 2023. "Multi-object auction design beyond quasi-linearity: Leading examples," Games and Economic Behavior, Elsevier, vol. 140(C), pages 210-228.
    13. Jawad Abrache & Teodor Crainic & Michel Gendreau & Monia Rekik, 2007. "Combinatorial auctions," Annals of Operations Research, Springer, vol. 153(1), pages 131-164, September.
    14. Tommy Andersson & Christer Andersson, 2012. "Properties of the DGS-Auction Algorithm," Computational Economics, Springer;Society for Computational Economics, vol. 39(2), pages 113-133, February.
    15. Laurent Lamy, 2009. "Ascending auctions: some impossibility results and their resolutions with final price discounts," PSE Working Papers halshs-00575076, HAL.
    16. Jagadeesan, Ravi & Kominers, Scott Duke & Rheingans-Yoo, Ross, 2018. "Strategy-proofness of worker-optimal matching with continuously transferable utility," Games and Economic Behavior, Elsevier, vol. 108(C), pages 287-294.
    17. Lawrence M. Ausubel, 2006. "An Efficient Dynamic Auction for Heterogeneous Commodities," American Economic Review, American Economic Association, vol. 96(3), pages 602-629, June.
    18. Andersson, Tommy & Andersson, Christer & Talman, Adolphus Johannes Jan, 2010. "Sets in Excess Demand in Ascending Auctions with Unit-Demand Bidders," Working Papers 2010:15, Lund University, Department of Economics, revised 28 Jun 2012.
    19. T. Andersson & C. Andersson & A. Talman, 2013. "Sets in excess demand in simple ascending auctions with unit-demand bidders," Annals of Operations Research, Springer, vol. 211(1), pages 27-36, December.
    20. Andersson, Tommy & Svensson, Lars-Gunnar, 2018. "Sequential rules for house allocation with price restrictions," Games and Economic Behavior, Elsevier, vol. 107(C), pages 41-59.

    More about this item

    Keywords

    Polynomial time algorithms; Multi-item auctions; Unit-demand bidders; Iterations;
    All these keywords.

    JEL classification:

    • C72 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Noncooperative Games
    • D44 - Microeconomics - - Market Structure, Pricing, and Design - - - Auctions

    NEP fields

    This paper has been announced in the following NEP Reports:

    Statistics

    Access and download statistics

    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:hhs:lunewp:2012_017. 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: Iker Arregui Alegria (email available below). General contact details of provider: https://edirc.repec.org/data/delunse.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.