IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v57y2009i4p823-839.html
   My bibliography  Save this article

Efficiency of Scalar-Parameterized Mechanisms

Author

Listed:
  • Ramesh Johari

    (Department of Management Science and Engineering, Stanford University, Stanford, California 94305)

  • John N. Tsitsiklis

    (Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139)

Abstract

We consider the problem of allocating a fixed amount of an infinitely divisible resource among multiple competing, fully rational users. We study the efficiency guarantees that are possible when we restrict to mechanisms that satisfy certain scalability constraints motivated by large-scale communication networks; in particular, we restrict attention to mechanisms where users are restricted to one-dimensional strategy spaces. We first study the efficiency guarantees possible when the mechanism is not allowed to price differentiate. We study the worst-case efficiency loss (ratio of the utility associated with a Nash equilibrium to the maximum possible utility), and show that Kelly's proportional allocation mechanism minimizes the efficiency loss when users are price anticipating. We then turn our attention to mechanisms where price differentiation is permitted; using an adaptation of the Vickrey-Clarke-Groves class of mechanisms, we construct a class of mechanisms with one-dimensional strategy spaces where Nash equilibria are fully efficient. These mechanisms are shown to be fully efficient even in general convex environments, under reasonable assumptions. Our results highlight a fundamental insight in mechanism design: when the pricing flexibility available to the mechanism designer is limited, restricting the strategic flexibility of bidders may actually improve the efficiency guarantee.

Suggested Citation

  • Ramesh Johari & John N. Tsitsiklis, 2009. "Efficiency of Scalar-Parameterized Mechanisms," Operations Research, INFORMS, vol. 57(4), pages 823-839, August.
    • Handle: RePEc:inm:oropre:v:57:y:2009:i:4:p:823-839
    DOI: 10.1287/opre.1080.0638
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.1080.0638
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.1080.0638?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. Reichelstein, Stefan & Reiter, Stanley, 1988. "Game Forms with Minimal Message Spaces," Econometrica, Econometric Society, vol. 56(3), pages 661-692, May.
    2. Shapley, Lloyd S & Shubik, Martin, 1977. "Trade Using One Commodity as a Means of Payment," Journal of Political Economy, University of Chicago Press, vol. 85(5), pages 937-968, October.
    3. Edward Clarke, 1971. "Multipart pricing of public goods," Public Choice, Springer, vol. 11(1), pages 17-33, September.
    4. Fadel, Ronald & Segal, Ilya, 2009. "The communication cost of selfishness," Journal of Economic Theory, Elsevier, vol. 144(5), pages 1895-1920, September.
    5. William Vickrey, 1961. "Counterspeculation, Auctions, And Competitive Sealed Tenders," Journal of Finance, American Finance Association, vol. 16(1), pages 8-37, March.
    6. Shenker, Scott & Clark, David & Estrin, Deborah & Herzog, Shai, 1996. "Pricing in computer networks: Reshaping the research agenda," Telecommunications Policy, Elsevier, vol. 20(3), pages 183-201, April.
    7. José R. Correa & Andreas S. Schulz & Nicolás E. Stier-Moses, 2004. "Selfish Routing in Capacitated Networks," Mathematics of Operations Research, INFORMS, vol. 29(4), pages 961-976, November.
    8. Ramesh Johari & John N. Tsitsiklis, 2004. "Efficiency Loss in a Network Resource Allocation Game," Mathematics of Operations Research, INFORMS, vol. 29(3), pages 407-435, August.
    9. Georgia Perakis & Guillaume Roels, 2007. "The Price of Anarchy in Supply Chains: Quantifying the Efficiency of Price-Only Contracts," Management Science, INFORMS, vol. 53(8), pages 1249-1268, August.
    10. Lawrence M. Ausubel, 2006. "An Efficient Dynamic Auction for Heterogeneous Commodities," American Economic Review, American Economic Association, vol. 96(3), pages 602-629, June.
    11. Klemperer, Paul D & Meyer, Margaret A, 1989. "Supply Function Equilibria in Oligopoly under Uncertainty," Econometrica, Econometric Society, vol. 57(6), pages 1243-1277, November.
    12. 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. Xupeng Wei & Achilleas Anastasopoulos, 2021. "Mechanism Design for Demand Management in Energy Communities," Games, MDPI, vol. 12(3), pages 1-34, July.
    2. Meng Zhang & Deepanshu Vasal, 2020. "Mechanism Design for Large Scale Network Utility Maximization," Papers 2003.04263, arXiv.org, revised Jan 2021.
    3. Frank Kelly & Peter Key & Neil Walton, 2016. "Efficient Advert Assignment," Operations Research, INFORMS, vol. 64(4), pages 822-837, August.
    4. Ioannis Caragiannis & Alexandros A. Voudouris, 2021. "The Efficiency of Resource Allocation Mechanisms for Budget-Constrained Users," Mathematics of Operations Research, INFORMS, vol. 46(2), pages 503-523, May.
    5. Harks, Tobias & von Falkenhausen, Philipp, 2014. "Optimal cost sharing for capacitated facility location games," European Journal of Operational Research, Elsevier, vol. 239(1), pages 187-198.
    6. Thirumulanathan, D. & Vinay, H. & Bhashyam, Srikrishna & Sundaresan, Rajesh, 2017. "Almost budget balanced mechanisms with scalar bids for allocation of a divisible good," European Journal of Operational Research, Elsevier, vol. 262(3), pages 1196-1207.
    7. Sreekumaran, Harikrishnan & Hota, Ashish R. & Liu, Andrew L. & Uhan, Nelson A. & Sundaram, Shreyas, 2021. "Equilibrium strategies for multiple interdictors on a common network," European Journal of Operational Research, Elsevier, vol. 288(2), pages 523-538.
    8. Tobias Harks & Konstantin Miller, 2011. "The Worst-Case Efficiency of Cost Sharing Methods in Resource Allocation Games," Operations Research, INFORMS, vol. 59(6), pages 1491-1503, December.
    9. Ramesh Johari & John N. Tsitsiklis, 2011. "Parameterized Supply Function Bidding: Equilibrium and Efficiency," Operations Research, INFORMS, vol. 59(5), pages 1079-1089, October.
    10. Eitan Altman & Manjesh Kumar Hanawal & Rajesh Sundaresan, 2016. "Generalising diagonal strict concavity property for uniqueness of Nash equilibrium," Indian Journal of Pure and Applied Mathematics, Springer, vol. 47(2), pages 213-228, June.
    11. Philipp von Falkenhausen & Tobias Harks, 2013. "Optimal Cost Sharing for Resource Selection Games," Mathematics of Operations Research, INFORMS, vol. 38(1), pages 184-208, 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. Ramesh Johari & John N. Tsitsiklis, 2011. "Parameterized Supply Function Bidding: Equilibrium and Efficiency," Operations Research, INFORMS, vol. 59(5), pages 1079-1089, October.
    2. Thirumulanathan, D. & Vinay, H. & Bhashyam, Srikrishna & Sundaresan, Rajesh, 2017. "Almost budget balanced mechanisms with scalar bids for allocation of a divisible good," European Journal of Operational Research, Elsevier, vol. 262(3), pages 1196-1207.
    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. William H. Sandholm, 2005. "Negative Externalities and Evolutionary Implementation," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 72(3), pages 885-915.
    5. Pär Holmberg, 2017. "Pro‐competitive Rationing in Multi‐unit Auctions," Economic Journal, Royal Economic Society, vol. 127(605), pages 372-395, October.
    6. Maskin, Eric & Sjostrom, Tomas, 2002. "Implementation theory," Handbook of Social Choice and Welfare,in: K. J. Arrow & A. K. Sen & K. Suzumura (ed.), Handbook of Social Choice and Welfare, edition 1, volume 1, chapter 5, pages 237-288 Elsevier.
    7. 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.
    8. 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.
    9. William H. Sandholm, 2002. "Evolutionary Implementation and Congestion Pricing," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 69(3), pages 667-689.
    10. Aristotelis Boukouras & Kostas Koufopoulos, 2017. "Efficient allocations in economies with asymmetric information when the realized frequency of types is common knowledge," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 64(1), pages 75-98, June.
    11. Ollikka, Kimmo & Tukiainen, Janne, 2013. "Central bank liquidity auction mechanism design and the interbank market," Bank of Finland Research Discussion Papers 21/2013, Bank of Finland.
    12. Andersson, Tommy & Erlanson, Albin, 2013. "Multi-item Vickrey–English–Dutch auctions," Games and Economic Behavior, Elsevier, vol. 81(C), pages 116-129.
    13. Samuel Antill & Darrell Duffie, 2017. "Augmenting Markets with Mechanisms," NBER Working Papers 24146, National Bureau of Economic Research, Inc.
    14. Michael H. Rothkopf, 2007. "Thirteen Reasons Why the Vickrey-Clarke-Groves Process Is Not Practical," Operations Research, INFORMS, vol. 55(2), pages 191-197, April.
    15. 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.
    16. Jawad Abrache & Teodor Crainic & Michel Gendreau & Monia Rekik, 2007. "Combinatorial auctions," Annals of Operations Research, Springer, vol. 153(1), pages 131-164, September.
    17. Fabrizio Barca, 2008. "An Agenda for a Reformed Cohesion Policy A place-based approach to meeting European Union challenges and expectations," EERI Research Paper Series EERI_RP_2008_06, Economics and Econometrics Research Institute (EERI), Brussels.
    18. Aristotelis Boukouras & Kostas Koufopoulos, 2015. "Efficient Allocations in Economies with Asymmetric Information when the Realized Frequency of Types is Common Knowledge," Discussion Papers in Economics 15/04, Division of Economics, School of Business, University of Leicester.
    19. Hitoshi Matsushima, 2010. "Auctioneer's Discretion in Combinatorial Auctions," CARF F-Series CARF-F-293, Center for Advanced Research in Finance, Faculty of Economics, The University of Tokyo, revised Sep 2012.
    20. Ollikka, Kimmo & Tukiainen, Janne, 2013. "Central bank liquidity auction mechanism design and the interbank market," Research Discussion Papers 21/2013, Bank of Finland.

    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:inm:oropre:v:57:y:2009:i:4:p:823-839. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.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.