IDEAS home Printed from https://ideas.repec.org/a/eee/jetheo/v144y2009i1p96-119.html
   My bibliography  Save this article

Almost budget-balanced VCG mechanisms to assign multiple objects

Author

Listed:
  • Moulin, Hervé

Abstract

Subsidy-free VCG mechanisms assign p identical objects to n agents. The efficiency loss is the largest ratio of budget surplus to efficient surplus, over all profiles of non-negative valuations. The smallest efficiency loss satisfies . If is bounded away from , converges to zero exponentially in n. Participation is voluntary in the optimal mechanism achieving if p=1, but not if p[greater-or-equal, slanted]2. Among voluntary mechanisms, the optimal efficiency loss is not significantly larger than if . But it does not converge to zero in n if .

Suggested Citation

  • Moulin, Hervé, 2009. "Almost budget-balanced VCG mechanisms to assign multiple objects," Journal of Economic Theory, Elsevier, vol. 144(1), pages 96-119, January.
    • Handle: RePEc:eee:jetheo:v:144:y:2009:i:1:p:96-119
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0022-0531(08)00062-8
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    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. Hervé Moulin & Scott Shenker, 2001. "Strategyproof sharing of submodular costs:budget balance versus efficiency," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 18(3), pages 511-533.
    2. Hervé Moulin, 2008. "The price of anarchy of serial, average and incremental cost sharing," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 36(3), pages 379-405, September.
    3. Baliga Sandeep & Vohra Rakesh, 2003. "Market Research and Market Design," The B.E. Journal of Theoretical Economics, De Gruyter, vol. 3(1), pages 1-27, August.
    4. Deb, Rajat & Ghosh, Indranil K. & Seo, Tae Kun, 2002. "Welfare asymptotics of the pivotal mechanism for excludable public goods," Mathematical Social Sciences, Elsevier, vol. 43(2), pages 209-224, March.
    5. Bailey, Martin J, 1997. "The Demand Revealing Process: To Distribute the Surplus," Public Choice, Springer, vol. 91(2), pages 107-126, April.
    6. McAfee, R. Preston, 1992. "A dominant strategy double auction," Journal of Economic Theory, Elsevier, vol. 56(2), pages 434-450, April.
    7. Rajat Deb & Tae Kun Seo, 1998. "Maximal surplus from the pivotal mechanism: a closed form solution," Review of Economic Design, Springer;Society for Economic Design, vol. 3(4), pages 347-357.
    8. Goldberg, Andrew V. & Hartline, Jason D. & Karlin, Anna R. & Saks, Michael & Wright, Andrew, 2006. "Competitive auctions," Games and Economic Behavior, Elsevier, vol. 55(2), pages 242-269, May.
    9. 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.
    10. Ruben Juarez, 2008. "The worst absolute surplus loss in the problem of commons: random priority versus average cost," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 34(1), pages 69-84, January.
    11. Gary-Bobo, Robert J. & Jaaidane, Touria, 2000. "Polling mechanisms and the demand revelation problem," Journal of Public Economics, Elsevier, vol. 76(2), pages 203-238, May.
    12. Porter, Ryan & Shoham, Yoav & Tennenholtz, Moshe, 2004. "Fair imposition," Journal of Economic Theory, Elsevier, vol. 118(2), pages 209-228, October.
    13. Murat Atlamaz & Duygu Yengin, 2008. "Fair Groves mechanisms," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 31(4), pages 573-587, December.
    14. Moulin, H., 1986. "Characterizations of the pivotal mechanism," Journal of Public Economics, Elsevier, vol. 31(1), pages 53-78, October.
    Full references (including those not matched with items on IDEAS)

    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. You, Jung S., 2015. "Optimal VCG mechanisms to assign multiple bads," Games and Economic Behavior, Elsevier, vol. 92(C), pages 166-190.
    2. Hervé Moulin, 2010. "Auctioning or assigning an object: some remarkable VCG mechanisms," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 34(2), pages 193-216, February.
    3. Ruben Juarez & Jung S. You, 2019. "Optimality of the uniform rule under single-peaked preferences," Economic Theory Bulletin, Springer;Society for the Advancement of Economic Theory (SAET), vol. 7(1), pages 27-36, May.
    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. Youngsub Chun & Manipushpak Mitra & Suresh Mutuswami, 2014. "Egalitarian equivalence and strategyproofness in the queueing problem," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 56(2), pages 425-442, June.
    6. Athanasiou, E. & Dey, S. & Valletta, G., 2012. "On sharing the benefits of communication," Research Memorandum 016, Maastricht University, Maastricht Research School of Economics of Technology and Organization (METEOR).
    7. Ruben Juarez & Rajnish Kumar, 2013. "Implementing efficient graphs in connection networks," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 54(2), pages 359-403, October.
    8. Moulin, Hervé, 2010. "An efficient and almost budget balanced cost sharing method," Games and Economic Behavior, Elsevier, vol. 70(1), pages 107-131, September.
    9. Efthymios Athanasiou & Santanu Dey & Giacomo Valletta, 2016. "Groves mechanisms and communication externalities," Review of Economic Design, Springer;Society for Economic Design, vol. 20(1), pages 1-37, March.
    10. Harless, Patrick, 2017. "Wary of the worst: Maximizing award guarantees when new claimants may arrive," Games and Economic Behavior, Elsevier, vol. 105(C), pages 316-328.
    11. Guo, Mingyu & Conitzer, Vincent, 2009. "Worst-case optimal redistribution of VCG payments in multi-unit auctions," Games and Economic Behavior, Elsevier, vol. 67(1), pages 69-98, September.
    12. Shao, Ran & Zhou, Lin, 2016. "Voting and optimal provision of a public good," Journal of Public Economics, Elsevier, vol. 134(C), pages 35-41.
    13. Nath, Swaprava & Sandholm, Tuomas, 2019. "Efficiency and budget balance in general quasi-linear domains," Games and Economic Behavior, Elsevier, vol. 113(C), pages 673-693.
    14. Loertscher, Simon & Marx, Leslie M., 2020. "Asymptotically optimal prior-free clock auctions," Journal of Economic Theory, Elsevier, vol. 187(C).
    15. Yi, Jianxin & Li, Yong, 2016. "A general impossibility theorem and its application to individual rights," Mathematical Social Sciences, Elsevier, vol. 81(C), pages 79-86.
    16. Massó, Jordi & Nicolò, Antonio & Sen, Arunava & Sharma, Tridib & Ülkü, Levent, 2015. "On cost sharing in the provision of a binary and excludable public good," Journal of Economic Theory, Elsevier, vol. 155(C), pages 30-49.
    17. Kazuhiko Hashimoto, 2015. "Strategy-Proof Rule in Probabilistic Allocation Problem of an Indivisible Good and Money," ISER Discussion Paper 0931, Institute of Social and Economic Research, Osaka University.
    18. Loertscher, Simon & Mezzetti, Claudio, 2021. "A dominant strategy, double clock auction with estimation-based tatonnement," Theoretical Economics, Econometric Society, vol. 16(3), July.
    19. Fu, Hu & Haghpanah, Nima & Hartline, Jason & Kleinberg, Robert, 2021. "Full surplus extraction from samples," Journal of Economic Theory, Elsevier, vol. 193(C).
    20. 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.

    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:jetheo:v:144:y:2009:i:1:p:96-119. 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/inca/622869 .

    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.