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

Fairness and efficiency in strategy-proof object allocation mechanisms

Author

Listed:
  • Nesterov, Alexander S.

Abstract

I consider the problem of allocating N indivisible objects among N agents according to their preferences when transfers are absent and an outside option may exist. I study the tradeoff between fairness and efficiency in the class of strategy-proof mechanisms. The main finding is that for strategy-proof mechanisms the following efficiency and fairness criteria are mutually incompatible: (1) ex-post efficiency and envy-freeness, (2) ordinal efficiency and weak envy-freeness, and (3) ordinal efficiency and equal division lower bound. Result 1 is the first impossibility result for this setting that uses ex-post efficiency; results 2 and 3 are more practical than similar results in the literature. In addition, for N=3, I give two characterizations of the celebrated random serial dictatorship mechanism: it is the unique strategy-proof, ex-post efficient mechanism that (4) provides agents that have the same ordinal preferences with assignments not dominated by each other (weak envy-freeness among equals), or (5) provides agents that have the same cardinal preferences with assignments of equal expected utility (symmetry). These results strengthen the characterization by Bogomolnaia and Moulin (2001); result 5 implies the impossibility result by Zhou (1990).

Suggested Citation

  • Nesterov, Alexander S., 2017. "Fairness and efficiency in strategy-proof object allocation mechanisms," Journal of Economic Theory, Elsevier, vol. 170(C), pages 145-168.
    • Handle: RePEc:eee:jetheo:v:170:y:2017:i:c:p:145-168
    DOI: 10.1016/j.jet.2017.05.004
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S002205311730056X
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.jet.2017.05.004?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. Stergios Athanassoglou & Jay Sethuraman, 2011. "House allocation with fractional endowments," International Journal of Game Theory, Springer;Game Theory Society, vol. 40(3), pages 481-513, August.
    2. Peter Coles & John Cawley & Phillip B. Levine & Muriel Niederle & Alvin E. Roth & John J. Siegfried, 2010. "The Job Market for New Economists: A Market Design Perspective," Journal of Economic Perspectives, American Economic Association, vol. 24(4), pages 187-206, Fall.
    3. Arnsperger, Christian, 1994. "Envy-Freeness and Distributive Justice," Journal of Economic Surveys, Wiley Blackwell, vol. 8(2), pages 155-186, June.
    4. Alvin E. Roth & Tayfun Sönmez & M. Utku Ünver, 2004. "Kidney Exchange," The Quarterly Journal of Economics, President and Fellows of Harvard College, vol. 119(2), pages 457-488.
    5. Zhou, Lin, 1990. "On a conjecture by gale about one-sided matching problems," Journal of Economic Theory, Elsevier, vol. 52(1), pages 123-135, October.
    6. , A. & ,, 2011. "Lotteries in student assignment: An equivalence result," Theoretical Economics, Econometric Society, vol. 6(1), January.
    7. William Thomson, 2007. "Fair Allocation Rules," RCER Working Papers 539, University of Rochester - Center for Economic Research (RCER).
    8. Abdulkadiroglu, Atila & Sonmez, Tayfun, 2003. "Ordinal efficiency and dominated sets of assignments," Journal of Economic Theory, Elsevier, vol. 112(1), pages 157-172, September.
    9. Kojima, Fuhito & Manea, Mihai, 2010. "Incentives in the probabilistic serial mechanism," Journal of Economic Theory, Elsevier, vol. 145(1), pages 106-123, January.
    10. Yeon-Koo Che & Fuhito Kojima, 2010. "Asymptotic Equivalence of Probabilistic Serial and Random Priority Mechanisms," Econometrica, Econometric Society, vol. 78(5), pages 1625-1672, September.
    11. Onur Kesten & Ayşe Yazıcı, 2012. "The Pareto-dominant strategy-proof and fair rule for problems with indivisible goods," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 50(2), pages 463-488, June.
    12. Pycia, Marek & Unver, Utku, 2017. "Incentive compatible allocation and exchange of discrete resources," Theoretical Economics, Econometric Society, vol. 12(1), January.
    13. Roth, Alvin E, 1984. "The Evolution of the Labor Market for Medical Interns and Residents: A Case Study in Game Theory," Journal of Political Economy, University of Chicago Press, vol. 92(6), pages 991-1016, December.
    14. Hylland, Aanund & Zeckhauser, Richard, 1979. "The Efficient Allocation of Individuals to Positions," Journal of Political Economy, University of Chicago Press, vol. 87(2), pages 293-314, April.
    15. Eric Budish & Yeon-Koo Che & Fuhito Kojima & Paul Milgrom, 2013. "Designing Random Allocation Mechanisms: Theory and Applications," American Economic Review, American Economic Association, vol. 103(2), pages 585-623, April.
    16. Yinghua He & Antonio Miralles & Marek Pycia & Jianye Yan, 2018. "A Pseudo-Market Approach to Allocation with Priorities," American Economic Journal: Microeconomics, American Economic Association, vol. 10(3), pages 272-314, August.
    17. Atila Abdulkadiroglu & Tayfun Sonmez, 1998. "Random Serial Dictatorship and the Core from Random Endowments in House Allocation Problems," Econometrica, Econometric Society, vol. 66(3), pages 689-702, May.
    18. Horowitz, John K. & McConnell, Kenneth E., 2002. "A Review of WTA/WTP Studies," Journal of Environmental Economics and Management, Elsevier, vol. 44(3), pages 426-447, November.
    19. Shapley, Lloyd & Scarf, Herbert, 1974. "On cores and indivisibility," Journal of Mathematical Economics, Elsevier, vol. 1(1), pages 23-37, March.
    20. Yan Chen & Tayfun Sönmez, 2002. "Improving Efficiency of On-Campus Housing: An Experimental Study," American Economic Review, American Economic Association, vol. 92(5), pages 1669-1686, December.
    21. Hashimoto, Tadashi & Hirata, Daisuke & Kesten, Onur & Kurino, Morimitsu & Unver, Utku, 2014. "Two axiomatic approaches to the probabilistic serial mechanism," Theoretical Economics, Econometric Society, vol. 9(1), January.
    22. Atila Abdulkadiroglu & Tayfun Sönmez, 2003. "School Choice: A Mechanism Design Approach," American Economic Review, American Economic Association, vol. 93(3), pages 729-747, June.
    23. Erdil, Aytek, 2014. "Strategy-proof stochastic assignment," Journal of Economic Theory, Elsevier, vol. 151(C), pages 146-162.
    24. Carroll, Gabriel, 2014. "A general equivalence theorem for allocation of indivisible objects," Journal of Mathematical Economics, Elsevier, vol. 51(C), pages 163-177.
    25. Kesten, Onur, 2009. "Why do popular mechanisms lack efficiency in random environments?," Journal of Economic Theory, Elsevier, vol. 144(5), pages 2209-2226, September.
    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. Ramezanian, Rasoul & Feizi, Mehdi, 2021. "Stepwise ordinal efficiency for the random assignment problem," Journal of Mathematical Economics, Elsevier, vol. 92(C), pages 60-65.
    2. Freeman, Rupert & Pritchard, Geoffrey & Wilson, Mark, 2021. "Order Symmetry: A New Fairness Criterion for Assignment Mechanisms," SocArXiv xt37c, Center for Open Science.
    3. Georgios Gerasimou, 2019. "Simple Preference Intensity Comparisons," Discussion Paper Series, School of Economics and Finance 201905, School of Economics and Finance, University of St Andrews, revised 27 Apr 2020.
    4. Brandt, Felix & Saile, Christian & Stricker, Christian, 2022. "Strategyproof social choice when preferences and outcomes may contain ties," Journal of Economic Theory, Elsevier, vol. 202(C).
    5. Feizi, Mehdi & Ramezanian, Rasoul, 2023. "A new impossibility result for random assignments," Journal of Mathematical Economics, Elsevier, vol. 107(C).
    6. Aziz, Haris & Brandl, Florian & Brandt, Felix & Brill, Markus, 2018. "On the tradeoff between efficiency and strategyproofness," Games and Economic Behavior, Elsevier, vol. 110(C), pages 1-18.
    7. Ramezanian, Rasoul & Feizi, Mehdi, 2022. "Robust ex-post Pareto efficiency and fairness in random assignments: Two impossibility results," Games and Economic Behavior, Elsevier, vol. 135(C), pages 356-367.
    8. Di Feng, 2023. "Efficiency in Multiple-Type Housing Markets," Papers 2308.14989, arXiv.org, revised Dec 2023.
    9. Kondratev, Aleksei Y. & Nesterov, Alexander S., 2022. "Minimal envy and popular matchings," European Journal of Operational Research, Elsevier, vol. 296(3), pages 776-787.
    10. Zhang, Jun, 2023. "Strategy-proof allocation with outside option," Games and Economic Behavior, Elsevier, vol. 137(C), pages 50-67.
    11. Zhang, Jun, 2020. "When are efficient and fair assignment mechanisms group strategy-proof?," Games and Economic Behavior, Elsevier, vol. 119(C), pages 251-266.
    12. Jun Zhang, 2023. "On wastefulness of random assignments in discrete allocation problems," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 76(1), pages 289-310, July.
    13. Basteck, Christian & Ehlers, Lars, 2023. "Strategy-proof and envy-free random assignment," Journal of Economic Theory, Elsevier, vol. 209(C).
    14. Jonathan Scarlett & Nicholas Teh & Yair Zick, 2023. "For One and All: Individual and Group Fairness in the Allocation of Indivisible Goods," Papers 2302.06958, arXiv.org.
    15. Youngsub Chun & Kiyong Yun, 2020. "Upper-contour strategy-proofness in the probabilistic assignment problem," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 54(4), pages 667-687, April.
    16. Alva, Samson & Manjunath, Vikram, 2020. "The impossibility of strategy-proof, Pareto efficient, and individually rational rules for fractional matching," Games and Economic Behavior, Elsevier, vol. 119(C), pages 15-29.
    17. Basteck, Christian & Ehlers, Lars H., 2022. "Strategy-proof and envy-free random assignment," Discussion Papers, Research Unit: Market Behavior SP II 2022-208, WZB Berlin Social Science Center.
    18. Priyanka Shende & Manish Purohit, 2020. "Strategy-proof and Envy-free Mechanisms for House Allocation," Papers 2010.16384, arXiv.org.
    19. Zhang, Jun, 2019. "Efficient and fair assignment mechanisms are strongly group manipulable," Journal of Economic Theory, Elsevier, vol. 180(C), pages 167-177.
    20. Rasoul Ramezanian & Mehdi Feizi, 2021. "Ex-post favoring ranks: a fairness notion for the random assignment problem," Review of Economic Design, Springer;Society for Economic Design, vol. 25(3), pages 157-176, September.
    21. Basteck, Christian & Ehlers, Lars, 2021. "Strategy-Proof and Envy-Free Random Assignment," Rationality and Competition Discussion Paper Series 307, CRC TRR 190 Rationality and Competition.
    22. Demeulemeester, Tom & Goossens, Dries & Hermans, Ben & Leus, Roel, 2023. "A pessimist’s approach to one-sided matching," European Journal of Operational Research, Elsevier, vol. 305(3), pages 1087-1099.
    23. Basteck, Christian, 2018. "Fair solutions to the random assignment problem," Journal of Mathematical Economics, Elsevier, vol. 79(C), pages 163-172.

    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. Alexander Nesterov, "undated". "Fairness and Efficiency in a Random Assignment: Three Impossibility Results," BDPEMS Working Papers 2014006, Berlin School of Economics.
    2. Onur Kesten & Morimitsu Kurino & Alexander S. Nesterov, 2017. "Efficient lottery design," Social Choice and Welfare, Springer;The Society for Social Choice and Welfare, vol. 48(1), pages 31-57, January.
    3. Jingsheng Yu & Jun Zhang, 2020. "Efficient and fair trading algorithms in market design environments," Papers 2005.06878, arXiv.org, revised May 2021.
    4. Hougaard, Jens Leth & Moreno-Ternero, Juan D. & Østerdal, Lars Peter, 2014. "Assigning agents to a line," Games and Economic Behavior, Elsevier, vol. 87(C), pages 539-553.
    5. Hugh-Jones, David & Kurino, Morimitsu & Vanberg, Christoph, 2014. "An experimental study on the incentives of the probabilistic serial mechanism," Games and Economic Behavior, Elsevier, vol. 87(C), pages 367-380.
    6. Mennle, Timo & Seuken, Sven, 2021. "Partial strategyproofness: Relaxing strategyproofness for the random assignment problem," Journal of Economic Theory, Elsevier, vol. 191(C).
    7. Ivan Balbuzanov & Maciej H. Kotowski, 2019. "Endowments, Exclusion, and Exchange," Econometrica, Econometric Society, vol. 87(5), pages 1663-1692, September.
    8. Patrick Harless & William Phan, 2020. "On endowments and indivisibility: partial ownership in the Shapley–Scarf model," Economic Theory, Springer;Society for the Advancement of Economic Theory (SAET), vol. 70(2), pages 411-435, September.
    9. YIlmaz, Özgür, 2010. "The probabilistic serial mechanism with private endowments," Games and Economic Behavior, Elsevier, vol. 69(2), pages 475-491, July.
    10. Che, Yeon-Koo & Tercieux, Olivier, 2018. "Payoff equivalence of efficient mechanisms in large matching markets," Theoretical Economics, Econometric Society, vol. 13(1), January.
    11. Han, Xiang, 0. "A theory of fair random allocation under priorities," Theoretical Economics, Econometric Society.
    12. Bogomolnaia, Anna & Moulin, Herve, 2015. "Size versus fairness in the assignment problem," Games and Economic Behavior, Elsevier, vol. 90(C), pages 119-127.
    13. Kesten, Onur, 2009. "Why do popular mechanisms lack efficiency in random environments?," Journal of Economic Theory, Elsevier, vol. 144(5), pages 2209-2226, September.
    14. Kesten, Onur & Unver, Utku, 2015. "A theory of school choice lotteries," Theoretical Economics, Econometric Society, vol. 10(2), May.
    15. Morimitsu Kurino, 2014. "House Allocation with Overlapping Generations," American Economic Journal: Microeconomics, American Economic Association, vol. 6(1), pages 258-289, February.
    16. Liu, Peng & Zeng, Huaxia, 2019. "Random assignments on preference domains with a tier structure," Journal of Mathematical Economics, Elsevier, vol. 84(C), pages 176-194.
    17. Ekici, Özgün, 2020. "Random mechanisms for house allocation with existing tenants," Journal of Mathematical Economics, Elsevier, vol. 89(C), pages 53-65.
    18. Hashimoto, Tadashi, 2018. "The generalized random priority mechanism with budgets," Journal of Economic Theory, Elsevier, vol. 177(C), pages 708-733.
    19. Altuntaş, Açelya & Phan, William, 2022. "Trading probabilities along cycles," Journal of Mathematical Economics, Elsevier, vol. 100(C).
    20. Anno, Hidekazu & Kurino, Morimitsu, 2016. "On the operation of multiple matching markets," Games and Economic Behavior, Elsevier, vol. 100(C), pages 166-185.

    More about this item

    Keywords

    Probabilistic assignment; Random serial dictatorship; Strategy-proofness; Ex-post efficiency; Weak envy-freeness; Equal division lower bound;
    All these keywords.

    JEL classification:

    • C78 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Bargaining Theory; Matching Theory
    • D71 - Microeconomics - - Analysis of Collective Decision-Making - - - Social Choice; Clubs; Committees; Associations
    • D78 - Microeconomics - - Analysis of Collective Decision-Making - - - Positive Analysis of Policy Formulation and Implementation

    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:eee:jetheo:v:170:y:2017:i:c:p:145-168. 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.