IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v291y2021i2p614-628.html
   My bibliography  Save this article

Complexity of finding Pareto-efficient allocations of highest welfare

Author

Listed:
  • Biró, Péter
  • Gudmundsson, Jens

Abstract

We allocate objects to agents as exemplified primarily by school choice. Welfare judgments of the object-allocating agency are encoded as edge weights in the acceptability graph. The welfare of an allocation is the sum of its edge weights. We introduce the constrained welfare-maximizing solution, which is the allocation of highest welfare among the Pareto-efficient allocations. We identify conditions under which this solution is easily determined from a computational point of view. For the unrestricted case, we formulate an integer program and find this to be viable in practice as it quickly solves a real-world instance of kindergarten allocation and large-scale simulated instances. Incentives to report preferences truthfully are discussed briefly.

Suggested Citation

  • Biró, Péter & Gudmundsson, Jens, 2021. "Complexity of finding Pareto-efficient allocations of highest welfare," European Journal of Operational Research, Elsevier, vol. 291(2), pages 614-628.
    • Handle: RePEc:eee:ejores:v:291:y:2021:i:2:p:614-628
    DOI: 10.1016/j.ejor.2020.03.018
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221720302320
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2020.03.018?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 look for a different version below or search for a different version of it.

    Other versions of this item:

    References listed on IDEAS

    as
    1. Atila Abdulkadiroğlu & Parag A. Pathak & Alvin E. Roth, 2005. "The New York City High School Match," American Economic Review, American Economic Association, vol. 95(2), pages 364-367, May.
    2. Fernández-Huertas Moraga, Jesús & Rapoport, Hillel, 2014. "Tradable immigration quotas," Journal of Public Economics, Elsevier, vol. 115(C), pages 94-108.
    3. ., 2017. "Modification and matching," Chapters, in: An Autecological Theory of the Firm and its Environment, chapter 4, Edward Elgar Publishing.
    4. Atila Abdulkadiro?lu & Yeon-Koo Che & Yosuke Yasuda, 2015. "Expanding "Choice" in School Choice," American Economic Journal: Microeconomics, American Economic Association, vol. 7(1), pages 1-42, February.
    5. 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.
    6. Eduardo M Azevedo & Eric Budish, 2019. "Strategy-proofness in the Large," The Review of Economic Studies, Review of Economic Studies Ltd, vol. 86(1), pages 81-116.
    7. Thomas Sargent & Lars Ljungqvist & Isaac Baley, 2017. "Turbulence and Unemployment in Matching Models," 2017 Meeting Papers 1391, Society for Economic Dynamics.
    8. 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.
    9. Chen, Yan & Sonmez, Tayfun, 2006. "School choice: an experimental study," Journal of Economic Theory, Elsevier, vol. 127(1), pages 202-231, March.
    10. Shengwu Li, 2017. "Obviously Strategy-Proof Mechanisms," American Economic Review, American Economic Association, vol. 107(11), pages 3257-3287, November.
    11. Atila Abdulkadiroglu & Yeon-Koo Che & Parag A. Pathak & Alvin E. Roth & Olivier Tercieux, 2017. "Minimizing Justified Envy in School Choice: The Design of New Orleans' OneApp," NBER Working Papers 23265, National Bureau of Economic Research, Inc.
    12. Roth, Alvin E, 1986. "On the Allocation of Residents to Rural Hospitals: A General Property of Two-Sided Matching Markets," Econometrica, Econometric Society, vol. 54(2), pages 425-427, March.
    13. Shapley, Lloyd & Scarf, Herbert, 1974. "On cores and indivisibility," Journal of Mathematical Economics, Elsevier, vol. 1(1), pages 23-37, March.
    14. Atila Abdulkadiroglu & Yeon-Koo Che & Yosuke Yasuda, 2011. "Resolving Conflicting Preferences in School Choice: The "Boston Mechanism" Reconsidered," American Economic Review, American Economic Association, vol. 101(1), pages 399-410, February.
    15. Aytek Erdil & Haluk Ergin, 2008. "What's the Matter with Tie-Breaking? Improving Efficiency in School Choice," American Economic Review, American Economic Association, vol. 98(3), pages 669-689, June.
    16. Kolos Csaba Ágoston & Péter Biró & Iain McBride, 2016. "Integer programming methods for special college admissions problems," Journal of Combinatorial Optimization, Springer, vol. 32(4), pages 1371-1399, November.
    17. Kolos Csaba Agoston & Peter Biro & Iain McBride, 2016. "Integer programming methods for special college admissions problems," CERS-IE WORKING PAPERS 1632, Institute of Economics, Centre for Economic and Regional Studies.
    18. Orhan Aygün & Bertan Turhan, 2017. "Large-Scale Affirmative Action in School Choice: Admissions to IITs in India," American Economic Review, American Economic Association, vol. 107(5), pages 210-213, May.
    19. Juncai Jiang & Nanda Kumar & Brian T. Ratchford, 2017. "Price-Matching Guarantees with Endogenous Consumer Search," Management Science, INFORMS, vol. 63(10), pages 3489-3513, October.
    20. of England, Bank, 2016. "Markets and operations," Bank of England Quarterly Bulletin, Bank of England, vol. 56(4), pages 212-221.
    21. Atila Abdulkadiroğlu & Parag A. Pathak & Alvin E. Roth & Tayfun Sönmez, 2005. "The Boston Public School Match," American Economic Review, American Economic Association, vol. 95(2), pages 368-371, May.
    22. Narges Ahani & Tommy Andersson & Alessandro Martinello & Alexander Teytelboym & Andrew C. Trapp, 2021. "Placement Optimization in Refugee Resettlement," Operations Research, INFORMS, vol. 69(5), pages 1468-1486, September.
    23. John William Hatfield & Paul R. Milgrom, 2005. "Matching with Contracts," American Economic Review, American Economic Association, vol. 95(4), pages 913-935, September.
    24. Itai Ashlagi & Peng Shi, 2016. "Optimal Allocation Without Money: An Engineering Approach," Management Science, INFORMS, vol. 62(4), pages 1078-1097, April.
    25. Alpern, Steve & Katrantzi, Ioanna, 2009. "Equilibria of two-sided matching games with common preferences," European Journal of Operational Research, Elsevier, vol. 196(3), pages 1214-1222, August.
    26. Roth, Alvin E. & Postlewaite, Andrew, 1977. "Weak versus strong domination in a market with indivisible goods," Journal of Mathematical Economics, Elsevier, vol. 4(2), pages 131-137, August.
    27. André Veski & Péter Biró & Kaire Põder & Triin Lauri, 2017. "Efficiency and fair access in Kindergarten allocation policy design," The Journal of Mechanism and Institution Design, Society for the Promotion of Mechanism and Institution Design, University of York, vol. 2(1), pages 57-104, December.
    28. Tayfun Sönmez & M. Bumin Yenmez, 2019. "Affirmative Action in India via Vertical and Horizontal Reservations," Boston College Working Papers in Economics 977, Boston College Department of Economics.
    29. Fırat, M. & Briskorn, D. & Laugier, A., 2016. "A Branch-and-Price algorithm for stable workforce assignments with hierarchical skills," European Journal of Operational Research, Elsevier, vol. 251(2), pages 676-685.
    30. Tamás Fleiner, 2003. "A Fixed-Point Approach to Stable Matchings and Some Applications," Mathematics of Operations Research, INFORMS, vol. 28(1), pages 103-126, February.
    31. 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.
    32. H. W. Kuhn, 1955. "The Hungarian method for the assignment problem," Naval Research Logistics Quarterly, John Wiley & Sons, vol. 2(1‐2), pages 83-97, March.
    33. Daniela Saban & Jay Sethuraman, 2015. "The Complexity of Computing the Random Priority Allocation Matrix," Mathematics of Operations Research, INFORMS, vol. 40(4), pages 1005-1014, October.
    34. Andersson, Tommy, 2017. "Refugee Matching as a Market Design Application," Working Papers 2017:16, Lund University, Department of Economics.
    35. 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.
    36. Peng Shi, 2015. "Guiding School-Choice Reform through Novel Applications of Operations Research," Interfaces, INFORMS, vol. 45(2), pages 117-132, April.
    37. Diebold, Franz & Bichler, Martin, 2017. "Matching with indifferences: A comparison of algorithms in the context of course allocation," European Journal of Operational Research, Elsevier, vol. 260(1), pages 268-282.
    38. Andersson, Tommy & Ehlers, Lars, 2016. "Assigning Refugees to Landlords in Sweden: Efficient Stable Maximum Matchings," Working Papers 2016:18, Lund University, Department of Economics, revised 27 Aug 2018.
    39. Kirk Bansak & Jens Hainmueller & Dominik Hangartner, 2017. "Europeans support a proportional allocation of asylum seekers," Nature Human Behaviour, Nature, vol. 1(7), pages 1-6, July.
    40. Cristina C B Cavalcante & Célio Maschio & Antonio Alberto Santos & Denis Schiozer & Anderson Rocha, 2017. "History matching through dynamic decision-making," PLOS ONE, Public Library of Science, vol. 12(6), pages 1-32, June.
    41. Elliott Peranson & Alvin E. Roth, 1999. "The Redesign of the Matching Market for American Physicians: Some Engineering Aspects of Economic Design," American Economic Review, American Economic Association, vol. 89(4), pages 748-780, September.
    42. Nitsan Perach & Julia Polak & Uriel Rothblum, 2008. "A stable matching model with an entrance criterion applied to the assignment of students to dormitories at the technion," International Journal of Game Theory, Springer;Game Theory Society, vol. 36(3), pages 519-535, March.
    43. Bansak, Kirk & Hainmueller, Jens & Hangartner, Dominik, 2016. "How economic, humanitarian, and religious concerns shape European attitudes toward asylum seekers," LSE Research Online Documents on Economics 67898, London School of Economics and Political Science, LSE Library.
    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. Kondratev, Aleksei Y. & Nesterov, Alexander S., 2022. "Minimal envy and popular matchings," European Journal of Operational Research, Elsevier, vol. 296(3), pages 776-787.
    2. Aziz, Haris & Huang, Xin & Mattei, Nicholas & Segal-Halevi, Erel, 2023. "Computing welfare-Maximizing fair allocations of indivisible goods," European Journal of Operational Research, Elsevier, vol. 307(2), pages 773-784.
    3. Hai Nguyen & Thành Nguyen & Alexander Teytelboym, 2021. "Stability in Matching Markets with Complex Constraints," Management Science, INFORMS, vol. 67(12), pages 7438-7454, December.
    4. 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.
    5. Eirinakis, Pavlos & Mourtos, Ioannis & Zampou, Eleni, 2022. "Random Serial Dictatorship for horizontal collaboration in logistics," Omega, Elsevier, vol. 111(C).
    6. Richárd Kicsiny & Zoltán Varga, 2023. "New algorithm for checking Pareto optimality in bimatrix games," Annals of Operations Research, Springer, vol. 320(1), pages 235-259, January.
    7. Dilek Sayedahmed, 2022. "Centralized refugee matching mechanisms with hierarchical priority classes," The Journal of Mechanism and Institution Design, Society for the Promotion of Mechanism and Institution Design, University of York, vol. 7(1), pages 71-111, December.

    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. Alvin Roth, 2008. "Deferred acceptance algorithms: history, theory, practice, and open questions," International Journal of Game Theory, Springer;Game Theory Society, vol. 36(3), pages 537-569, March.
    2. Atila Abdulkadiroglu & Tommy Andersson, 2022. "School Choice," NBER Working Papers 29822, National Bureau of Economic Research, Inc.
    3. Scott Duke Kominers & Alexander Teytelboym & Vincent P Crawford, 2017. "An invitation to market design," Oxford Review of Economic Policy, Oxford University Press and Oxford Review of Economic Policy Limited, vol. 33(4), pages 541-571.
    4. Haeringer, Guillaume & Klijn, Flip, 2009. "Constrained school choice," Journal of Economic Theory, Elsevier, vol. 144(5), pages 1921-1947, September.
    5. Atila Abdulkadiroglu & Parag A. Pathak & Alvin E. Roth & Tayfun Sönmez, 2006. "Changing the Boston School Choice Mechanism," Levine's Bibliography 122247000000001022, UCLA Department of Economics.
    6. Committee, Nobel Prize, 2012. "Alvin E. Roth and Lloyd S. Shapley: Stable allocations and the practice of market design," Nobel Prize in Economics documents 2012-1, Nobel Prize Committee.
    7. Zhu, Min, 2014. "College admissions in China: A mechanism design perspective," China Economic Review, Elsevier, vol. 30(C), pages 618-631.
    8. Atila Abdulkadiroglu & Parag A. Pathak & Alvin E. Roth, 2009. "Strategy-Proofness versus Efficiency in Matching with Indifferences: Redesigning the NYC High School Match," American Economic Review, American Economic Association, vol. 99(5), pages 1954-1978, December.
    9. Min Zhu, 2013. "College Admissions in China : A Mechanism Design Perspective," Working Papers halshs-00860931, HAL.
    10. Min Zhu, 2013. "College Admissions in China : A Mechanism Design Perspective," Working Papers 1327, Groupe d'Analyse et de Théorie Economique Lyon St-Étienne (GATE Lyon St-Étienne), Université de Lyon.
    11. Hatfield, John William & Kojima, Fuhito, 2010. "Substitutes and stability for matching with contracts," Journal of Economic Theory, Elsevier, vol. 145(5), pages 1704-1723, September.
    12. Alvin E. Roth, 2009. "What Have We Learned from Market Design?," Innovation Policy and the Economy, University of Chicago Press, vol. 9(1), pages 79-112.
    13. Fuhito Kojima & Parag A. Pathak, 2009. "Incentives and Stability in Large Two-Sided Matching Markets," American Economic Review, American Economic Association, vol. 99(3), pages 608-627, June.
    14. Ágoston, Kolos Csaba & Biró, Péter & Szántó, Richárd, 2018. "Stable project allocation under distributional constraints," Operations Research Perspectives, Elsevier, vol. 5(C), pages 59-68.
    15. Alvin E. Roth & Tayfun Sönmez & M. Utku Ünver, 2005. "Efficient Kidney Exchange: Coincidence of Wants in a Structured Market," Boston College Working Papers in Economics 621, Boston College Department of Economics.
    16. Jingsheng Yu & Jun Zhang, 2020. "Efficient and fair trading algorithms in market design environments," Papers 2005.06878, arXiv.org, revised May 2021.
    17. Kóczy Á., László, 2009. "Központi felvételi rendszerek. Taktikázás és stabilitás [Central admission systems. Stratagems and stability]," Közgazdasági Szemle (Economic Review - monthly of the Hungarian Academy of Sciences), Közgazdasági Szemle Alapítvány (Economic Review Foundation), vol. 0(5), pages 422-442.
    18. Hatfield, John William & Kojima, Fuhito & Narita, Yusuke, 2016. "Improving schools through school choice: A market design approach," Journal of Economic Theory, Elsevier, vol. 166(C), pages 186-211.
    19. Bettina Klaus & David F. Manlove & Francesca Rossi, 2014. "Matching under Preferences," Cahiers de Recherches Economiques du Département d'économie 14.07, Université de Lausanne, Faculté des HEC, Département d’économie.
    20. Ágoston, Kolos Csaba & Biró, Péter & Kováts, Endre & Jankó, Zsuzsanna, 2022. "College admissions with ties and common quotas: Integer programming approach," European Journal of Operational Research, Elsevier, vol. 299(2), pages 722-734.

    More about this item

    Keywords

    Assignment; Pareto-efficiency; Welfare-maximization; Complexity; Integer programming;
    All these keywords.

    JEL classification:

    • C6 - Mathematical and Quantitative Methods - - Mathematical Methods; Programming Models; Mathematical and Simulation Modeling
    • C78 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Bargaining Theory; Matching Theory
    • D61 - Microeconomics - - Welfare Economics - - - Allocative Efficiency; Cost-Benefit Analysis

    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:ejores:v:291:y:2021:i:2:p:614-628. 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/eor .

    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.