IDEAS home Printed from https://ideas.repec.org/p/huj/dispap/dp540.html
   My bibliography  Save this paper

Truth and Envy in Capacitated Allocation Games

Author

Listed:
  • Edith Cohen
  • Michal Feldman
  • Amos Fiat
  • Haim Kaplan
  • Svetlana Olonetsky

Abstract

We study auctions with additive valuations where agents have a limit on the number of items they may receive. We refer to this setting as capacitated allocation games. We seek truthful and envy free mechanisms that maximize the social welfare. I.e., where agents have no incentive to lie and no agent seeks to exchange outcomes with another. In 1983, Leonard showed that VCG with Clarke Pivot payments (which is known to be truthful, individually rational, and have no positive transfers), is also an envy free mechanism for the special case of n items and n unit capacity agents. We elaborate upon this problem and show that VCG with Clarke Pivot payments is envy free if agent capacities are all equal. When agent capacities are not identical, we show that there is no truthful and envy free mechanism that maximizes social welfare if one disallows positive transfers. For the case of two agents (and arbitrary capacities) we show a VCG mechanism that is truthful, envy free, and individually rational, but has positive transfers. We conclude with a host of open problems that arise from our work.

Suggested Citation

  • Edith Cohen & Michal Feldman & Amos Fiat & Haim Kaplan & Svetlana Olonetsky, 2010. "Truth and Envy in Capacitated Allocation Games," Discussion Paper Series dp540, The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem.
    • Handle: RePEc:huj:dispap:dp540
    as

    Download full text from publisher

    File URL: http://ratio.huji.ac.il/sites/default/files/publications/dp540.pdf
    Download Restriction: no
    ---><---

    References listed on IDEAS

    as
    1. Herve Moulin, 2004. "Fair Division and Collective Welfare," MIT Press Books, The MIT Press, edition 1, volume 1, number 0262633116, April.
    2. Eric S. Maskin, 1987. "On the Fair Allocation of Indivisible Goods," Palgrave Macmillan Books, in: George R. Feiwel (ed.), Arrow and the Foundations of the Theory of Economic Policy, chapter 11, pages 341-349, Palgrave Macmillan.
    3. Claus-Jochen Haake & Matthias G. Raith & Francis Edward Su, 2002. "Bidding for envy-freeness: A procedural approach to n-player fair-division problems," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 19(4), pages 723-749.
    4. Leonard, Herman B, 1983. "Elicitation of Honest Preferences for the Assignment of Individuals to Positions," Journal of Political Economy, University of Chicago Press, vol. 91(3), pages 461-479, June.
    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. Vito Fragnelli & Maria Erminia Marina, 2009. "Strategic Manipulations and Collusions in Knaster Procedure," Czech Economic Review, Charles University Prague, Faculty of Social Sciences, Institute of Economic Studies, vol. 3(2), pages 143-153, July.
    2. Tommy Andersson & Christer Andersson, 2009. "Solving House Allocation Problems with Risk-Averse Agents," Computational Economics, Springer;Society for Computational Economics, vol. 33(4), pages 389-401, May.
    3. Azacis, Helmuts, 2008. "Double implementation in a market for indivisible goods with a price constraint," Games and Economic Behavior, Elsevier, vol. 62(1), pages 140-154, January.
    4. Ning Sun & Zaifu Yang, 2009. "Strategy Proof And Privacy Preserving Fair Allocation Mechanism," The Japanese Economic Review, Japanese Economic Association, vol. 60(2), pages 143-151, June.
    5. Lars-Gunnar Svensson, 2009. "Coalitional strategy-proofness and fairness," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 40(2), pages 227-245, August.
    6. Van Essen, Matt & Wooders, John, 2021. "Allocating positions fairly: Auctions and Shapley value," Journal of Economic Theory, Elsevier, vol. 196(C).
    7. Goko, Hiromichi & Igarashi, Ayumi & Kawase, Yasushi & Makino, Kazuhisa & Sumita, Hanna & Tamura, Akihisa & Yokoi, Yu & Yokoo, Makoto, 2024. "A fair and truthful mechanism with limited subsidy," Games and Economic Behavior, Elsevier, vol. 144(C), pages 49-70.
    8. Thomson, William, 2011. "Chapter Twenty-One - Fair Allocation Rules," 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 2, chapter 21, pages 393-506, Elsevier.
    9. Atila Abdulkadiroğlu & Tayfun Sönmez & M. Utku Ünver, 2004. "Room assignment-rent division: A market approach," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 22(3), pages 515-538, June.
    10. Edith Cohen & Michal Feldman & Amos Fiat & Haim Kaplan & Svetlana Olonetsky, 2010. "Envy-Free Makespan Approximation," Discussion Paper Series dp539, The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem.
    11. Matt Van Essen & John Wooders, 2018. "Allocating Positions Fairly: An Auction and its Relationship to the Shapley Value," Working Papers 20180019, New York University Abu Dhabi, Department of Social Science, revised Aug 2018.
    12. Johannes Brustle & Jack Dippel & Vishnu V. Narayan & Mashbat Suzuki & Adrian Vetta, 2019. "One Dollar Each Eliminates Envy," Papers 1912.02797, arXiv.org.
    13. Svensson, Lars-Gunnar, 2004. "Strategy-Proof and Fair Wages," Working Papers 2004:8, Lund University, Department of Economics.
    14. Andersson, Tommy & Andersson, Christer & Andersson, Ola, 2010. "Sealed Bid Auctions vs. Ascending Bid Auctions: An Experimental Study," Working Papers 2010:17, Lund University, Department of Economics.
    15. 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.
    16. Nunez, Marina & Rafels, Carles, 2003. "Characterization of the extreme core allocations of the assignment game," Games and Economic Behavior, Elsevier, vol. 44(2), pages 311-331, August.
    17. Frank Kelly & Peter Key & Neil Walton, 2016. "Efficient Advert Assignment," Operations Research, INFORMS, vol. 64(4), pages 822-837, August.
    18. Josué Ortega & Erel Segal-Halevi, 2022. "Obvious manipulations in cake-cutting," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 59(4), pages 969-988, November.
    19. Jens Gudmundsson & Jens Leth Hougaard & Erik Ansink, 2024. "Towards fully decentralized environmental regulation," Tinbergen Institute Discussion Papers 24-035/VIII, Tinbergen Institute.
    20. Blume, Lawrence E. & Easley, David & Kleinberg, Jon & Tardos, Éva, 2009. "Trading networks with price-setting agents," Games and Economic Behavior, Elsevier, vol. 67(1), pages 36-50, September.

    More about this item

    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:huj:dispap:dp540. 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: Michael Simkin (email available below). General contact details of provider: https://edirc.repec.org/data/crihuil.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.