{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T06:35:13Z","timestamp":1771050913364,"version":"3.50.1"},"reference-count":63,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2021,10,16]],"date-time":"2021-10-16T00:00:00Z","timestamp":1634342400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"ANR","award":["14-CE24-0007-01-Cocorico-CoDec"],"award-info":[{"award-number":["14-CE24-0007-01-Cocorico-CoDec"]}]},{"name":"MOE","award":["R-252-000-625-133"],"award-info":[{"award-number":["R-252-000-625-133"]}]},{"name":"Singapore NRF Research Fellowship","award":["R-252-000-750-733"],"award-info":[{"award-number":["R-252-000-750-733"]}]},{"name":"KAKENHI Grant-in-Aid for JSPS Fellows","award":["18J00997"],"award-info":[{"award-number":["18J00997"]}]},{"name":"JST, ACT-X, and JST, PRESTO","award":["JPMJPR20C1"],"award-info":[{"award-number":["JPMJPR20C1"]}]},{"name":"Singapore MOE","award":["R-252-000-625-133"],"award-info":[{"award-number":["R-252-000-625-133"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2021,12,31]]},"abstract":"<jats:p>\n            In this article, we present new results on the fair and efficient allocation of indivisible goods to agents whose preferences correspond to\n            <jats:italic>matroid rank functions<\/jats:italic>\n            . This is a versatile valuation class with several desirable properties (such as monotonicity and submodularity), which naturally lends itself to a number of real-world domains. We use these properties to our advantage; first, we show that when agent valuations are matroid rank functions, a socially optimal (i.e., utilitarian social welfare-maximizing) allocation that achieves envy-freeness up to one item (EF1) exists and is computationally tractable. We also prove that the Nash welfare-maximizing and the leximin allocations both exhibit this fairness\/efficiency combination by showing that they can be achieved by minimizing any symmetric strictly convex function over utilitarian optimal outcomes. To the best of our knowledge, this is the first valuation function class not subsumed by additive valuations for which it has been established that an allocation maximizing Nash welfare is EF1. Moreover, for a subclass of these valuation functions based on maximum (unweighted) bipartite matching, we show that a leximin allocation can be computed in polynomial time. Additionally, we explore possible extensions of our results to fairness criteria other than EF1 as well as to generalizations of the above valuation classes.\n          <\/jats:p>","DOI":"10.1145\/3485006","type":"journal-article","created":{"date-parts":[[2021,10,17]],"date-time":"2021-10-17T02:06:47Z","timestamp":1634436407000},"page":"1-41","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["Finding Fair and Efficient Allocations for Matroid Rank Valuations"],"prefix":"10.1145","volume":"9","author":[{"given":"Nawal","family":"Benabbou","sequence":"first","affiliation":[{"name":"Sorbonne Universit\u00e9, Paris, France"}]},{"given":"Mithun","family":"Chakraborty","sequence":"additional","affiliation":[{"name":"University of Michigan, Ann Arbor, MI, USA"}]},{"given":"Ayumi","family":"Igarashi","sequence":"additional","affiliation":[{"name":"National Institute of Informatics, Tokyo, Japan"}]},{"given":"Yair","family":"Zick","sequence":"additional","affiliation":[{"name":"University of Massachusetts, Amherst, MA, USA"}]}],"member":"320","published-online":{"date-parts":[[2021,10,16]]},"reference":[{"key":"e_1_3_4_2_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2017\/6"},{"key":"e_1_3_4_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/3306127.3331717"},{"key":"e_1_3_4_4_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2020\/6"},{"key":"e_1_3_4_5_1","unstructured":"Moshe Babaioff Tomer Ezra and Uriel Feige. 2020. Fair and Truthful Mechanisms for Dichotomous Valuations. arXiv:cs.GT\/2002.10704 https:\/\/arxiv.org\/abs\/2002.10704."},{"key":"e_1_3_4_6_1","first-page":"4\u20131","volume-title":"Proceedings of the Conference on Learning Theory","author":"Balcan Maria Florina","year":"2012","unstructured":"Maria Florina Balcan, Florin Constantin, Satoru Iwata, and Lei Wang. 2012. Learning valuation functions. In Proceedings of the Conference on Learning Theory. 4\u20131."},{"key":"e_1_3_4_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/3306127.3331927"},{"key":"e_1_3_4_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219166.3219176"},{"key":"e_1_3_4_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/3237383.3237392"},{"key":"e_1_3_4_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/3367032.3367047"},{"key":"e_1_3_4_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3411513"},{"key":"e_1_3_4_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1120680.1120683"},{"key":"e_1_3_4_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/3304415.3304430"},{"key":"e_1_3_4_14_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107446984.013"},{"key":"e_1_3_4_15_1","doi-asserted-by":"publisher","DOI":"10.5555\/1622673.1622686"},{"key":"e_1_3_4_16_1","doi-asserted-by":"publisher","DOI":"10.1086\/664613"},{"key":"e_1_3_4_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3328526.3329574"},{"key":"e_1_3_4_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3355902"},{"key":"e_1_3_4_19_1","unstructured":"L. Elisa Celis Amit Deshpande Tarun Kathuria and Nisheeth K. Vishnoi. 2016. How to be Fair and Diverse? arXiv:cs.LG\/1610.07183 https:\/\/arxiv.org\/abs\/1610.07183."},{"key":"e_1_3_4_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975994.162"},{"key":"e_1_3_4_21_1","volume-title":"Chicago Public Schools Policy Manual: Admissions Policy for Magnet, Selective Enrollment and Other Options for Knowledge Schools and Programs.","author":"Schools Chicago Public","year":"2017","unstructured":"Chicago Public Schools. 2017. Chicago Public Schools Policy Manual: Admissions Policy for Magnet, Selective Enrollment and Other Options for Knowledge Schools and Programs. (26 April 2017). Section 202.2. Board Report 17-0426-PO2. Retrieved from http:\/\/policy.cps.edu\/Policies.aspx."},{"issue":"4","key":"e_1_3_4_22_1","first-page":"343","article-title":"Race relations and public housing policy in Singapore","volume":"8","author":"Chua Beng-Huat","year":"1991","unstructured":"Beng-Huat Chua. 1991. Race relations and public housing policy in Singapore. J. Arch. Plan. Res. 8, 4 (1991), 343\u2013354.","journal-title":"J. Arch. Plan. Res."},{"key":"e_1_3_4_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejor.2015.05.071"},{"key":"e_1_3_4_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-41622-4_7"},{"key":"e_1_3_4_25_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33011877"},{"key":"e_1_3_4_26_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-5060(08)70817-3"},{"key":"e_1_3_4_27_1","doi-asserted-by":"publisher","DOI":"10.1214\/aoms\/1177706369"},{"key":"e_1_3_4_28_1","first-page":"45","article-title":"Resource allocation and the public sector.","author":"Foley Duncan","year":"1967","unstructured":"Duncan Foley. 1967. Resource allocation and the public sector. Yale Econ. Essays 7 (1967), 45\u201398.","journal-title":"Yale Econ. Essays 7"},{"key":"e_1_3_4_29_1","unstructured":"Andr\u00e1s Frank and Kazuo Murota. 2018. Discrete Decreasing Minimization Part I: Base-polyhedra with Applications in Network Optimization. arXiv:math.CO\/1808.07600v3 https:\/\/arxiv.org\/abs\/1808.07600v3."},{"key":"e_1_3_4_30_1","unstructured":"Andr\u00e1s Frank and Kazuo Murota. 2019. Discrete Decreasing Minimization Part III: Network Flows. arXiv:math.CO\/ 1907.02673v2 https:\/\/arxiv.org\/abs\/1907.02673v2."},{"key":"e_1_3_4_31_1","doi-asserted-by":"publisher","DOI":"10.5555\/3367032.3367073"},{"key":"e_1_3_4_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219166.3219238"},{"key":"e_1_3_4_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-57586-5_26"},{"key":"e_1_3_4_34_1","doi-asserted-by":"publisher","DOI":"10.1006\/jeth.1999.2531"},{"key":"e_1_3_4_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-64946-3_26"},{"key":"e_1_3_4_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2827872"},{"key":"e_1_3_4_37_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.2006.0030-1299.14714.x"},{"key":"e_1_3_4_38_1","doi-asserted-by":"publisher","DOI":"10.2307\/1913392"},{"key":"e_1_3_4_39_1","series-title":"(Algorithms and Combinatorics","volume-title":"Combinatorial Optimization: Theory and Algorithms","author":"Korte Bernhard","year":"2006","unstructured":"Bernhard Korte and Jens Vygen. 2006. Combinatorial Optimization: Theory and Algorithms(Algorithms and Combinatorics, Vol. 3). Springer-Verlag Berlin."},{"key":"e_1_3_4_40_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2020.07.008"},{"key":"e_1_3_4_41_1","unstructured":"Martin Lackner and Piotr Skowron. 2020. Approval-Based Committee Voting: Axioms Algorithms and Applications. arXiv:cs.GT\/2007.01795 https:\/\/arxiv.org\/abs\/2007.01795."},{"key":"e_1_3_4_42_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v30i1.10024"},{"key":"e_1_3_4_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2005.02.006"},{"key":"e_1_3_4_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.geb.2017.10.016"},{"key":"e_1_3_4_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/988772.988792"},{"key":"e_1_3_4_46_1","first-page":"231","volume-title":"Trends in Computational Social Choice","author":"Markakis Evangelos","year":"2017","unstructured":"Evangelos Markakis. 2017. Approximation algorithms and hardness results for fair division with indivisible goods. In Trends in Computational Social Choice, Ulle Endriss (Ed.). AI Access, 231\u2013247."},{"key":"e_1_3_4_47_1","volume-title":"Fair Division and Collective Welfare","author":"Moulin Herv\u00e9","year":"2004","unstructured":"Herv\u00e9 Moulin. 2004. Fair Division and Collective Welfare. The MIT Press."},{"key":"e_1_3_4_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/0105003"},{"key":"e_1_3_4_49_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10458-013-9224-2"},{"key":"e_1_3_4_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10472-012-9328-4"},{"key":"e_1_3_4_51_1","doi-asserted-by":"publisher","DOI":"10.1093\/acprof:oso\/9780198566946.001.0001"},{"key":"e_1_3_4_52_1","volume-title":"Better Racial Mix in HDB Housing Estates.","author":"Singapore. Parliament of","year":"1989","unstructured":"Parliament of Singapore.1989. Better Racial Mix in HDB Housing Estates. Parliament Debates: Official Report (16 February 1989). Vol. 52, 650\u2013668."},{"key":"e_1_3_4_53_1","first-page":"123","article-title":"Singapore\u2019s housing policies: 1960\u20132013","author":"Phang Sock Yong","year":"2013","unstructured":"Sock Yong Phang and Kyunghwan Kim. 2013. Singapore\u2019s housing policies: 1960\u20132013. Front. Devel. Polic.: Innov. Devel. Case Stud. (2013), 123\u2013153.","journal-title":"Front. Devel. Polic.: Innov. Devel. Case Stud."},{"key":"e_1_3_4_54_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975031.165"},{"key":"e_1_3_4_55_1","volume-title":"Chicago Public Schools: Ensuring Diversity in Selective Enrollment and Magnet Schools.","author":"Quick Kimberly","year":"2016","unstructured":"Kimberly Quick. 2016. Chicago Public Schools: Ensuring Diversity in Selective Enrollment and Magnet Schools. (14 Oct. 2016). The Century Foundation. Retrieved from https:\/\/tcf.org\/content\/report\/chicago-public-schools."},{"key":"e_1_3_4_56_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15117-0_9"},{"key":"e_1_3_4_57_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2019.103167"},{"key":"e_1_3_4_58_1","volume-title":"Collective Choice and Social Welfare","author":"Sen Amartya","year":"1970","unstructured":"Amartya Sen. 1970. Collective Choice and Social Welfare. Holden Day, San Francisco."},{"key":"e_1_3_4_59_1","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800090106"},{"key":"e_1_3_4_60_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0197-3975(02)00050-4"},{"key":"e_1_3_4_61_1","doi-asserted-by":"publisher","DOI":"10.5555\/3237383.3237398"},{"key":"e_1_3_4_62_1","volume-title":"Improving Outcomes for All Students: Strategies and Considerations to Increase Student Diversity.","author":"Education U.S. Department of Education, Office of Elementary and Secondary","year":"2017","unstructured":"U.S. Department of Education, Office of Elementary and Secondary Education. 2017. Improving Outcomes for All Students: Strategies and Considerations to Increase Student Diversity. (19 Jan. 2017). Washington, D.C. Retrieved from https:\/\/www.ed.gov\/diversity-opportunity."},{"key":"e_1_3_4_63_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0531(74)90075-1"},{"key":"e_1_3_4_64_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jpubeco.2014.04.006"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3485006","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3485006","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:17:15Z","timestamp":1750191435000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3485006"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,10,16]]},"references-count":63,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2021,12,31]]}},"alternative-id":["10.1145\/3485006"],"URL":"https:\/\/doi.org\/10.1145\/3485006","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"value":"2167-8375","type":"print"},{"value":"2167-8383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,10,16]]},"assertion":[{"value":"2020-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-04-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-10-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}