IDEAS home Printed from https://ideas.repec.org/p/ehl/lserod/87419.html
   My bibliography  Save this paper

Valuation compressions in VCG-based combinatorial auctions

Author

Listed:
  • Dütting, Paul
  • Henzinger, Monika
  • Starnberger, Martin

Abstract

The focus of classic mechanism design has been on truthful direct-revelation mechanisms. In the context of combinatorial auctions the truthful direct-revelation mechanism that maximizes social welfare is the VCG mechanism. For many valuation spaces computing the allocation and payments of the VCG mechanism, however, is a computationally hard problem. We thus study the performance of the VCG mechanism when bidders are forced to choose bids from a subspace of the valuation space for which the VCG outcome can be computed efficiently. We prove improved upper bounds on the welfare loss for restrictions to additive bids and upper and lower bounds for restrictions to non-additive bids. These bounds show that increased expressiveness can give rise to additional equilibria of poorer efficiency.

Suggested Citation

  • Dütting, Paul & Henzinger, Monika & Starnberger, Martin, 2018. "Valuation compressions in VCG-based combinatorial auctions," LSE Research Online Documents on Economics 87419, London School of Economics and Political Science, LSE Library.
    • Handle: RePEc:ehl:lserod:87419
    as

    Download full text from publisher

    File URL: http://eprints.lse.ac.uk/87419/
    File Function: Open access version.
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Sergiu Hart & Andreu Mas-Colell, 2013. "A Simple Adaptive Procedure Leading To Correlated Equilibrium," World Scientific Book Chapters, in: Simple Adaptive Strategies From Regret-Matching to Uncoupled Dynamics, chapter 2, pages 17-46, World Scientific Publishing Co. Pte. Ltd..
    2. Edward Clarke, 1971. "Multipart pricing of public goods," Public Choice, Springer, vol. 11(1), pages 17-33, September.
    3. Nisan,Noam & Roughgarden,Tim & Tardos,Eva & Vazirani,Vijay V. (ed.), 2007. "Algorithmic Game Theory," Cambridge Books, Cambridge University Press, number 9780521872829, June.
    4. D. Foster & R. Vohra, 2010. "Calibrated Learning and Correlated Equilibrium," Levine's Working Paper Archive 568, David K. Levine.
    5. Kelso, Alexander S, Jr & Crawford, Vincent P, 1982. "Job Matching, Coalition Formation, and Gross Substitutes," Econometrica, Econometric Society, vol. 50(6), pages 1483-1504, November.
    6. Milgrom, Paul, 2010. "Simplified mechanisms with an application to sponsored-search auctions," Games and Economic Behavior, Elsevier, vol. 70(1), pages 62-70, September.
    7. Foster, Dean P. & Vohra, Rakesh V., 1997. "Calibrated Learning and Correlated Equilibrium," Games and Economic Behavior, Elsevier, vol. 21(1-2), pages 40-55, October.
    8. Groves, Theodore, 1973. "Incentives in Teams," Econometrica, Econometric Society, vol. 41(4), pages 617-631, July.
    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. Paul Dütting & Felix Fischer & David C. Parkes, 2019. "Expressiveness and Robustness of First-Price Position Auctions," Mathematics of Operations Research, INFORMS, vol. 44(1), pages 196-211, February.
    2. Feldman, Michal & Shabtai, Galia, 2023. "Simultaneous 2nd price item auctions with no-underbidding," Games and Economic Behavior, Elsevier, vol. 140(C), pages 316-340.
    3. Paul Dütting & Thomas Kesselheim & Éva Tardos, 2021. "Algorithms as Mechanisms: The Price of Anarchy of Relax and Round," Mathematics of Operations Research, INFORMS, vol. 46(1), pages 317-335, February.

    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. Leshno, Jacob D. & Pradelski, Bary S.R., 2021. "The importance of memory for price discovery in decentralized markets," Games and Economic Behavior, Elsevier, vol. 125(C), pages 62-78.
    2. Eric Friedman & Scott Shenker, 1998. "Learning and Implementation on the Internet," Departmental Working Papers 199821, Rutgers University, Department of Economics.
    3. Sergiu Hart & Andreu Mas-Colell, 2013. "Stochastic Uncoupled Dynamics And Nash Equilibrium," World Scientific Book Chapters, in: Simple Adaptive Strategies From Regret-Matching to Uncoupled Dynamics, chapter 8, pages 165-189, World Scientific Publishing Co. Pte. Ltd..
    4. Fudenberg, Drew & Levine, David K., 1999. "Conditional Universal Consistency," Games and Economic Behavior, Elsevier, vol. 29(1-2), pages 104-130, October.
    5. Tom Johnston & Michael Savery & Alex Scott & Bassel Tarbush, 2023. "Game Connectivity and Adaptive Dynamics," Papers 2309.10609, arXiv.org, revised Oct 2024.
    6. 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.
    7. Chiara Scarampi & Richard Fairchild & Luca Fumarco & Alberto Palermo & Neal Hinvest, 2021. "Social Metacognition: A Correlational Device for Strategic Interactions," Working Papers 2111, Tulane University, Department of Economics.
    8. Robert Kleinberg & Bo Waggoner & E. Glen Weyl, 2016. "Descending Price Optimally Coordinates Search," Papers 1603.07682, arXiv.org, revised Dec 2016.
    9. Chun, Youngsub & Yengin, Duygu, 2017. "Welfare lower bounds and strategy-proofness in the queueing problem," Games and Economic Behavior, Elsevier, vol. 102(C), pages 462-476.
    10. Ehud Lehrer & Eilon Solan, 2007. "Learning to play partially-specified equilibrium," Levine's Working Paper Archive 122247000000001436, David K. Levine.
    11. Kalai, Ehud & Lehrer, Ehud & Smorodinsky, Rann, 1999. "Calibrated Forecasting and Merging," Games and Economic Behavior, Elsevier, vol. 29(1-2), pages 151-169, October.
    12. Michael Foley & Rory Smead & Patrick Forber & Christoph Riedl, 2021. "Avoiding the bullies: The resilience of cooperation among unequals," PLOS Computational Biology, Public Library of Science, vol. 17(4), pages 1-19, April.
    13. Karl Schlag & Andriy Zapechelnyuk, 2009. "Decision Making in Uncertain and Changing Environments," Discussion Papers 19, Kyiv School of Economics.
    14. Eddie Dekel & Yossi Feinberg, 2006. "Non-Bayesian Testing of a Stochastic Prediction," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 73(4), pages 893-906.
    15. Lehmann, Benny & Lehmann, Daniel & Nisan, Noam, 2006. "Combinatorial auctions with decreasing marginal utilities," Games and Economic Behavior, Elsevier, vol. 55(2), pages 270-296, May.
    16. Emerson Melo, 2021. "Learning in Random Utility Models Via Online Decision Problems," Papers 2112.10993, arXiv.org, revised Aug 2022.
    17. Daron Acemoglu & Asuman Ozdaglar, 2011. "Opinion Dynamics and Learning in Social Networks," Dynamic Games and Applications, Springer, vol. 1(1), pages 3-49, 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. Marden, Jason R., 2017. "Selecting efficient correlated equilibria through distributed learning," Games and Economic Behavior, Elsevier, vol. 106(C), pages 114-133.
    20. Lawrence M. Ausubel & Paul Milgrom, 2004. "Ascending Proxy Auctions," Discussion Papers 03-035, Stanford Institute for Economic Policy Research.

    More about this item

    Keywords

    algorithms; economics; theory; simplified mechanisms; combinatorial auctions with item bidding; price of anarchy;
    All these keywords.

    JEL classification:

    • J1 - Labor and Demographic Economics - - Demographic Economics

    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:ehl:lserod:87419. 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: LSERO Manager (email available below). General contact details of provider: https://edirc.repec.org/data/lsepsuk.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.