IDEAS home Printed from https://ideas.repec.org/a/eee/mateco/v47y2011i4p541-544.html
   My bibliography  Save this article

Inefficiency of equilibria in digital mechanisms with continuous valuations

Author

Listed:
  • Grigorieva, Elena
  • Herings, P. Jean-Jacques
  • Müller, Rudolf
  • Vermeulen, Dries

Abstract

A digital mechanism is defined as an iterative procedure in which bidders select an action, from a finite set, in each iteration. When bidders have continuous valuations and make strategic reports, we show that any ex post implementation of the Vickrey choice rule via such a mechanism needs infinitely many iterations for almost all realizations of the bidders’ valuations. Thus, when valuations are drawn from a continuous probability distribution, the Vickrey choice rule can only be used at the expense of a running time that is infinite with probability one. This infeasibility result even holds in the case of two bidders and the Vickrey choice rule only being required to be established with probability one. Establishing the efficient allocation when the n bidders’ report truthfully contrasts starkly to the previous setting: a bisection procedure has a finite running time almost always, and an expected number of reports are equal to 2n. Using a Groves payment scheme rather than Vickrey’s second price payment scheme somewhat mitigates the problem. We provide an example mechanism with a Groves payment scheme, in which the running time of the mechanism in equilibrium is finite with probability 12.

Suggested Citation

  • Grigorieva, Elena & Herings, P. Jean-Jacques & Müller, Rudolf & Vermeulen, Dries, 2011. "Inefficiency of equilibria in digital mechanisms with continuous valuations," Journal of Mathematical Economics, Elsevier, vol. 47(4-5), pages 541-544.
    • Handle: RePEc:eee:mateco:v:47:y:2011:i:4:p:541-544
    DOI: 10.1016/j.jmateco.2011.06.002
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0304406811000565
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.jmateco.2011.06.002?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
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Green, Jerry & Laffont, Jean-Jacques, 1977. "Characterization of Satisfactory Mechanisms for the Revelation of Preferences for Public Goods," Econometrica, Econometric Society, vol. 45(2), pages 427-438, March.
    2. Fadel, Ronald & Segal, Ilya, 2009. "The communication cost of selfishness," Journal of Economic Theory, Elsevier, vol. 144(5), pages 1895-1920, September.
    3. Green, Jerry & Laffont, Jean-Jacques, 1977. "On the revelation of preferences for public goods," Journal of Public Economics, Elsevier, vol. 8(1), pages 79-93, August.
    4. William Vickrey, 1961. "Counterspeculation, Auctions, And Competitive Sealed Tenders," Journal of Finance, American Finance Association, vol. 16(1), pages 8-37, March.
    5. Grigorieva, Elena & Jean-Jacques Herings, P. & Müller, Rudolf & Vermeulen, Dries, 2012. "Fraction auctions: The tradeoff between efficiency and running time," European Journal of Operational Research, Elsevier, vol. 220(2), pages 577-587.
    6. Rothkopf, Michael H. & Harstad, Ronald M., 1994. "On the role of discrete bid levels in oral auctions," European Journal of Operational Research, Elsevier, vol. 74(3), pages 572-581, May.
    7. 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. Grigorieva, Elena & Jean-Jacques Herings, P. & Müller, Rudolf & Vermeulen, Dries, 2012. "Fraction auctions: The tradeoff between efficiency and running time," European Journal of Operational Research, Elsevier, vol. 220(2), pages 577-587.

    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. Grigorieva,Elena & Herings,Jean-Jacques & Müller,Rudolf & Vermeulen,Dries, 2004. "The communication complexity of private value single item auctions," Research Memorandum 052, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    2. Tommy Andersson & Lars Ehlers & Lars-Gunnar Svensson & Ryan Tierney, 2022. "Gale’s Fixed Tax for Exchanging Houses," Mathematics of Operations Research, INFORMS, vol. 47(4), pages 3110-3128, November.
    3. 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.
    4. Sprumont, Yves, 2013. "Constrained-optimal strategy-proof assignment: Beyond the Groves mechanisms," Journal of Economic Theory, Elsevier, vol. 148(3), pages 1102-1121.
    5. Hiroki Saitoh & Shigehiro Serizawa, 2008. "Vickrey allocation rule with income effect," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 35(2), pages 391-401, May.
    6. Takashi Kunimoto & Cuiling Zhang, 2021. "On incentive compatible, individually rational public good provision mechanisms," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 57(2), pages 431-468, August.
    7. Marek Pycia & Peter Troyan, 2023. "A Theory of Simplicity in Games and Mechanism Design," Econometrica, Econometric Society, vol. 91(4), pages 1495-1526, July.
    8. Matsushima, Hitoshi & Noda, Shunya, 2023. "Mechanism design with general ex-ante investments," Journal of Mathematical Economics, Elsevier, vol. 106(C).
    9. Schnizler, Bjorn & Neumann, Dirk & Veit, Daniel & Weinhardt, Christof, 2008. "Trading grid services - a multi-attribute combinatorial approach," European Journal of Operational Research, Elsevier, vol. 187(3), pages 943-961, June.
    10. Ryuji Sano, 2021. "Dynamic communication mechanism design," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 57(1), pages 163-180, July.
    11. Ledyard, John O., "undated". "Public Goods: A Survey of Experimental Research," Working Papers 861, California Institute of Technology, Division of the Humanities and Social Sciences.
    12. Paula Jaramillo & Çaǧatay Kayı & Flip Klijn, 2014. "Asymmetrically fair rules for an indivisible good problem with a budget constraint," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 43(3), pages 603-633, October.
    13. Baliga, Sandeep & Maskin, Eric, 2003. "Mechanism design for the environment," Handbook of Environmental Economics, in: K. G. Mäler & J. R. Vincent (ed.), Handbook of Environmental Economics, edition 1, volume 1, chapter 7, pages 305-324, Elsevier.
    14. Jackson, M.O.Matthew O. & Nicolo, Antonio, 2004. "The strategy-proof provision of public goods under congestion and crowding preferences," Journal of Economic Theory, Elsevier, vol. 115(2), pages 278-308, April.
    15. Miller, Nolan H. & Pratt, John W. & Zeckhauser, Richard J. & Johnson, Scott, 2007. "Mechanism design with multidimensional, continuous types and interdependent valuations," Journal of Economic Theory, Elsevier, vol. 136(1), pages 476-496, September.
    16. Viauroux, Christelle, 2011. "Pricing urban congestion: A structural random utility model with traffic anticipation," European Economic Review, Elsevier, vol. 55(7), pages 877-902.
    17. Grigorieva, E. & Herings, P.J.J. & Müller, R.J. & Vermeulen, A.J., 2006. "Inefficiency of equilibria in query auctions with continuous valuations," Research Memorandum 017, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    18. Hitoshi Matsushima & Shunya Noda, 2019. "Mechanism Design with General Ex-Ante Investments (Revised version of F415 )," CARF F-Series CARF-F-464, Center for Advanced Research in Finance, Faculty of Economics, The University of Tokyo.
    19. Atila Abdulkadiroglu & Parag A. Pathak & Alvin E. Roth & Tayfun Sönmez, 2006. "Changing the Boston School Choice Mechanism," Boston College Working Papers in Economics 639, Boston College Department of Economics.
    20. Rica Gonen & Anat Lerner, 2013. "The Incompatibility of Pareto Optimality and Dominant-Strategy Incentive Compatibility in Sufficiently-Anonymous Budget-Constrained Quasilinear Settings," Games, MDPI, vol. 4(4), pages 1-21, November.

    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:eee:mateco:v:47:y:2011:i:4:p:541-544. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/jmateco .

    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.