IDEAS home Printed from https://ideas.repec.org/a/spr/sochwe/v50y2018i4d10.1007_s00355-017-1102-4.html
   My bibliography  Save this article

Envy-free and budget-balanced assignment of identical objects

Author

Listed:
  • Yan Long

    (New York University Abu Dhabi)

Abstract

Strategy-proof, budget-balanced, and envy-free rank mechanisms assign q identical objects to n agents. The efficiency loss is the largest ratio of surplus loss to efficient surplus, over all profiles of non-zero valuations. The smallest efficiency loss $$\frac{n-q}{n^{2}-n}$$ n - q n 2 - n is uniquely achieved by the following simple allocation rule: assign one object to each of the $$q-1$$ q - 1 agents with the highest valuations, a large probability to the agent with the qth highest valuation, and the remaining probability to the agent with the $$(q+1)$$ ( q + 1 ) th highest valuation.

Suggested Citation

  • Yan Long, 2018. "Envy-free and budget-balanced assignment of identical objects," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 50(4), pages 705-719, April.
    • Handle: RePEc:spr:sochwe:v:50:y:2018:i:4:d:10.1007_s00355-017-1102-4
    DOI: 10.1007/s00355-017-1102-4
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s00355-017-1102-4
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s00355-017-1102-4?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. Svensson, Lars-Gunnar, 2004. "Strategy-Proof and Fair Wages," Working Papers 2004:8, Lund University, Department of Economics.
    2. Long, Yan & Mishra, Debasis & Sharma, Tridib, 2017. "Balanced ranking mechanisms," Games and Economic Behavior, Elsevier, vol. 105(C), pages 9-39.
    3. Drexl, Moritz & Kleiner, Andreas, 2015. "Optimal private good allocation: The case for a balanced budget," Games and Economic Behavior, Elsevier, vol. 94(C), pages 169-181.
    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. Cramton, Peter & Gibbons, Robert & Klemperer, Paul, 1987. "Dissolving a Partnership Efficiently," Econometrica, Econometric Society, vol. 55(3), pages 615-632, May.
    6. Moulin, Hervé, 2009. "Almost budget-balanced VCG mechanisms to assign multiple objects," Journal of Economic Theory, Elsevier, vol. 144(1), pages 96-119, January.
    7. Szilvia Pápai, 2003. "Groves sealed bid auctions of heterogeneous objects with fair prices," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 20(3), pages 371-385, June.
    8. 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.
    9. Moulin, Herve, 1992. "An Application of the Shapley Value to Fair Division with Money," Econometrica, Econometric Society, vol. 60(6), pages 1331-1349, November.
    10. Shinji Ohseto, 2006. "Characterizations of strategy-proof and fair mechanisms for allocating indivisible goods," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 29(1), pages 111-121, September.
    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. Roger B. Myerson, 1981. "Optimal Auction Design," Mathematics of Operations Research, INFORMS, vol. 6(1), pages 58-73, February.
    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. Yan Long, 2020. "Optimal budget-balanced ranking mechanisms to assign identical objects," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 70(2), pages 467-502, September.

    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. Long, Yan & Mishra, Debasis & Sharma, Tridib, 2017. "Balanced ranking mechanisms," Games and Economic Behavior, Elsevier, vol. 105(C), pages 9-39.
    2. Debasis Mishra & Tridib Sharma, 2018. "A simple budget-balanced mechanism," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 50(1), pages 147-170, January.
    3. Manea, Mihai & Maskin, Eric, 2023. "Withholding and damage in Bayesian trade mechanisms," Games and Economic Behavior, Elsevier, vol. 142(C), pages 243-265.
    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. Ranojoy Basu & Conan Mukherjee, 2024. "Characterization of maxmed mechanisms for multiple objects," Review of Economic Design, Springer;Society for Economic Design, vol. 28(2), pages 313-330, June.
    6. Yan Long, 2020. "Optimal budget-balanced ranking mechanisms to assign identical objects," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 70(2), pages 467-502, September.
    7. 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.
    8. Drexl, Moritz & Kleiner, Andreas, 2015. "Optimal private good allocation: The case for a balanced budget," Games and Economic Behavior, Elsevier, vol. 94(C), pages 169-181.
    9. Shinji Ohseto, 2021. "Strategy-proof and Pareto efficient allocation of indivisible goods: general impossibility domains," International Journal of Game Theory, Springer;Game Theory Society, vol. 50(2), pages 419-432, June.
    10. Shao, Ran & Zhou, Lin, 2016. "Optimal allocation of an indivisible good," Games and Economic Behavior, Elsevier, vol. 100(C), pages 95-112.
    11. Miki Kato & Shinji Ohseto & Shohei Tamura, 2015. "Strategy-proofness versus symmetry in economies with an indivisible good and money," International Journal of Game Theory, Springer;Game Theory Society, vol. 44(1), pages 195-207, February.
    12. Athanasiou, Efthymios, 2013. "A Solomonic solution to the problem of assigning a private indivisible good," Games and Economic Behavior, Elsevier, vol. 82(C), pages 369-387.
    13. You, Jung S., 2015. "Optimal VCG mechanisms to assign multiple bads," Games and Economic Behavior, Elsevier, vol. 92(C), pages 166-190.
    14. 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.
    15. Yengin, Duygu, 2013. "Population monotonic and strategy-proof mechanisms respecting welfare lower bounds," Journal of Mathematical Economics, Elsevier, vol. 49(5), pages 389-397.
    16. 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.
    17. Jung S. You & Ruben Juarez, 2021. "Incentive-compatible simple mechanisms," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 71(4), pages 1569-1589, June.
    18. Sambuddha Ghosh & Yan Long & Manipushpak Mitra, 2021. "Prior-free online mechanisms for queueing with arrivals," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 72(2), pages 671-700, September.
    19. Conan Mukherjee, 2020. "On group strategyproof and optimal object allocation," Economic Theory Bulletin, Springer;Society for the Advancement of Economic Theory (SAET), vol. 8(2), pages 289-304, October.
    20. Efthymios Athanasiou & Giacomo Valletta, 2021. "Undominated mechanisms and the provision of a pure public good in two agent economies," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 57(4), pages 763-795, November.

    More about this item

    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:spr:sochwe:v:50:y:2018:i:4:d:10.1007_s00355-017-1102-4. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.