{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,27]],"date-time":"2026-01-27T11:32:40Z","timestamp":1769513560858,"version":"3.49.0"},"reference-count":50,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2021,8,16]],"date-time":"2021-08-16T00:00:00Z","timestamp":1629072000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Singapore NRF Research Fellowship","award":["R-252-000-750-733"],"award-info":[{"award-number":["R-252-000-750-733"]}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["639945"],"award-info":[{"award-number":["639945"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"name":"KAKENHI Grant-in-Aid for JSPS Fellows","award":["18J00997"],"award-info":[{"award-number":["18J00997"]}]},{"name":"JST, ACT-X"},{"DOI":"10.13039\/501100001459","name":"Singapore Ministry of Education","doi-asserted-by":"crossref","award":["R-252-000-625-133"],"award-info":[{"award-number":["R-252-000-625-133"]}],"id":[{"id":"10.13039\/501100001459","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Econ. Comput."],"published-print":{"date-parts":[[2021,9,30]]},"abstract":"<jats:p>\n            We introduce and analyze new envy-based fairness concepts for agents with\n            <jats:italic>weights<\/jats:italic>\n            that quantify their entitlements in the allocation of indivisible items. We propose two variants of weighted envy-freeness up to one item (WEF1):\n            <jats:italic>strong<\/jats:italic>\n            , where envy can be eliminated by removing an item from the envied agent\u2019s bundle, and\n            <jats:italic>weak<\/jats:italic>\n            , where envy can be eliminated either by removing an item (as in the strong version) or by replicating an item from the envied agent\u2019s bundle in the envying agent\u2019s bundle. We show that for additive valuations, an allocation that is both Pareto optimal and strongly WEF1 always exists and can be computed in pseudo-polynomial time; moreover, an allocation that maximizes the weighted Nash social welfare may not be strongly WEF1, but it always satisfies the weak version of the property. Moreover, we establish that a generalization of the round-robin picking sequence algorithm produces in polynomial time a strongly WEF1 allocation for an arbitrary number of agents; for two agents, we can efficiently achieve both strong WEF1 and Pareto optimality by adapting the adjusted winner procedure. Our work highlights several aspects in which weighted fair division is richer and more challenging than its unweighted counterpart.\n          <\/jats:p>","DOI":"10.1145\/3457166","type":"journal-article","created":{"date-parts":[[2021,8,16]],"date-time":"2021-08-16T17:02:19Z","timestamp":1629133339000},"page":"1-39","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":32,"title":["Weighted Envy-freeness in Indivisible Item Allocation"],"prefix":"10.1145","volume":"9","author":[{"given":"Mithun","family":"Chakraborty","sequence":"first","affiliation":[{"name":"University of Michigan, Ann Arbor, MI, USA"}]},{"given":"Ayumi","family":"Igarashi","sequence":"additional","affiliation":[{"name":"National Institute of Informatics, Chiyoda-ku, Tokyo, Japan"}]},{"given":"Warut","family":"Suksompong","sequence":"additional","affiliation":[{"name":"National University of Singapore, Singapore"}]},{"given":"Yair","family":"Zick","sequence":"additional","affiliation":[{"name":"University of Massachusetts, Amherst, MA, USA"}]}],"member":"320","published-online":{"date-parts":[[2021,8,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/3304415.3304423"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/3367032.3367041"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/3367032.3367040"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.orl.2020.07.005"},{"key":"e_1_2_1_5_1","unstructured":"Moshe Babaioff Tomer Ezra and Uriel Feige. 2020. Fair and truthful mechanisms for dichotomous valuations. Retrieved from https:\/\/arXiv:2002.10704.  Moshe Babaioff Tomer Ezra and Uriel Feige. 2020. Fair and truthful mechanisms for dichotomous valuations. Retrieved from https:\/\/arXiv:2002.10704."},{"key":"e_1_2_1_6_1","volume-title":"Proceedings of the 2nd ACM Conference on Fairness, Accountability, and Transparency (ACM FAT\u201919)","author":"Babaioff Moshe","year":"2019","unstructured":"Moshe Babaioff , Noam Nisan , and Inbal Talgam-Cohen . 2019 . Fair allocation through competitive equilibrium from generic incomes . In Proceedings of the 2nd ACM Conference on Fairness, Accountability, and Transparency (ACM FAT\u201919) . 180. Moshe Babaioff, Noam Nisan, and Inbal Talgam-Cohen. 2019. Fair allocation through competitive equilibrium from generic incomes. In Proceedings of the 2nd ACM Conference on Fairness, Accountability, and Transparency (ACM FAT\u201919). 180."},{"key":"e_1_2_1_7_1","volume-title":"Fair Representation: Meeting the Ideal of One Man, One Vote","author":"Balinski Michel L.","year":"2001","unstructured":"Michel L. Balinski and H. Peyton Young . 2001 . Fair Representation: Meeting the Ideal of One Man, One Vote . Brookings Institution Press . Michel L. Balinski and H. Peyton Young. 2001. Fair Representation: Meeting the Ideal of One Man, One Vote. Brookings Institution Press."},{"key":"e_1_2_1_8_1","volume-title":"Colloq. Math. 69","author":"Barbanel Julius B.","year":"1995","unstructured":"Julius B. Barbanel . 1995 . Game-theoretic algorithms for fair and strongly fair cake division with entitlements . Colloq. Math. 69 , 1 (1995), 59\u201373. Julius B. Barbanel. 1995. Game-theoretic algorithms for fair and strongly fair cake division with entitlements. Colloq. Math. 69, 1 (1995), 59\u201373."},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 16th Conference on Web and Internet Economics (WINE\u201920)","author":"Barman Siddharth","year":"2020","unstructured":"Siddharth Barman , Umang Bhaskar , and Nisarg Shah . 2020 . Optimal bounds on the price of fairness for indivisible goods . In Proceedings of the 16th Conference on Web and Internet Economics (WINE\u201920) . 356\u2013369. Siddharth Barman, Umang Bhaskar, and Nisarg Shah. 2020. Optimal bounds on the price of fairness for indivisible goods. In Proceedings of the 16th Conference on Web and Internet Economics (WINE\u201920). 356\u2013369."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219166.3219176"},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI\u201921)","author":"Bei Xiaohui","year":"2021","unstructured":"Xiaohui Bei , Ayumi Igarashi , Xinhang Lu , and Warut Suksompong . 2021 . The price of connectivity in fair division . In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI\u201921) . Forthcoming. Xiaohui Bei, Ayumi Igarashi, Xinhang Lu, and Warut Suksompong. 2021. The price of connectivity in fair division. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI\u201921). Forthcoming."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/3367032.3367045"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/3367032.3367047"},{"key":"e_1_2_1_14_1","article-title":"The price of quota-based diversity in assignment problems","volume":"8","author":"Benabbou Nawal","year":"2020","unstructured":"Nawal Benabbou , Mithun Chakraborty , Xuan-Vinh Ho , Jakub Sliwinski , and Yair Zick . 2020 a. The price of quota-based diversity in assignment problems . ACM Trans. Econ. Comput. 8 , 3 (2020), 14:1\u201314:32. Nawal Benabbou, Mithun Chakraborty, Xuan-Vinh Ho, Jakub Sliwinski, and Yair Zick. 2020a. The price of quota-based diversity in assignment problems. ACM Trans. Econ. Comput. 8, 3 (2020), 14:1\u201314:32.","journal-title":"ACM Trans. Econ. Comput."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-57980-7_3"},{"key":"e_1_2_1_16_1","volume-title":"Proceedings of the 10th Innovations in Theoretical Computer Science Conference (ITCS\u201919)","author":"Bil\u00f2 Vittorio","unstructured":"Vittorio Bil\u00f2 , Ioannis Caragiannis , Michele Flammini , Ayumi Igarashi , Gianpiero Monaco , Dominik Peters , Cosimo Vinci , and William S. Zwicker . 2019. Almost envy-free allocations with connected bundles . In Proceedings of the 10th Innovations in Theoretical Computer Science Conference (ITCS\u201919) . 14:1\u201314:21. Vittorio Bil\u00f2, Ioannis Caragiannis, Michele Flammini, Ayumi Igarashi, Gianpiero Monaco, Dominik Peters, Cosimo Vinci, and William S. Zwicker. 2019. Almost envy-free allocations with connected bundles. In Proceedings of the 10th Innovations in Theoretical Computer Science Conference (ITCS\u201919). 14:1\u201314:21."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/3304415.3304430"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/3171642.3171663"},{"key":"e_1_2_1_19_1","volume-title":"Handbook of Computational Social Choice, Felix Brandt, Vincent Conitzer, Ulle Endriss, J\u00e9r\u00f4me Lang, and Ariel D","author":"Bouveret Sylvain","unstructured":"Sylvain Bouveret , Yann Chevaleyre , and Nicolas Maudet . 2016. Fair allocation of indivisible goods . In Handbook of Computational Social Choice, Felix Brandt, Vincent Conitzer, Ulle Endriss, J\u00e9r\u00f4me Lang, and Ariel D . Procaccia (Eds.). Cambridge University Press , Chapter 12, 284\u2013310. Sylvain Bouveret, Yann Chevaleyre, and Nicolas Maudet. 2016. Fair allocation of indivisible goods. In Handbook of Computational Social Choice, Felix Brandt, Vincent Conitzer, Ulle Endriss, J\u00e9r\u00f4me Lang, and Ariel D. Procaccia (Eds.). Cambridge University Press, Chapter 12, 284\u2013310."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10458-015-9287-3"},{"key":"e_1_2_1_21_1","volume-title":"Taylor","author":"Brams Steven J.","year":"1996","unstructured":"Steven J. Brams and Alan D . Taylor . 1996 . Fair Division : From Cake-Cutting to Dispute Resolution. Cambridge University Press . Steven J. Brams and Alan D. Taylor. 1996. Fair Division: From Cake-Cutting to Dispute Resolution. Cambridge University Press."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1086\/664613"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/3355902"},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the 18th ACM Conference on Economics and Computation (EC\u201917)","author":"Conitzer Vincent","year":"2017","unstructured":"Vincent Conitzer , Rupert Freeman , and Nisarg Shah . 2017 . Fair public decision making . In Proceedings of the 18th ACM Conference on Economics and Computation (EC\u201917) . 629\u2013646. Vincent Conitzer, Rupert Freeman, and Nisarg Shah. 2017. Fair public decision making. In Proceedings of the 18th ACM Conference on Economics and Computation (EC\u201917). 629\u2013646."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33011853"},{"key":"e_1_2_1_26_1","article-title":"The complexity of cake cutting with unequal shares","volume":"16","author":"Cseh \u00c1gnes","year":"2020","unstructured":"\u00c1gnes Cseh and Tam\u00e1s Fleiner . 2020 . The complexity of cake cutting with unequal shares . ACM Trans. Algor. 16 , 3 (2020), 29:1\u201329:21. \u00c1gnes Cseh and Tam\u00e1s Fleiner. 2020. The complexity of cake cutting with unequal shares. ACM Trans. Algor. 16, 3 (2020), 29:1\u201329:21.","journal-title":"ACM Trans. Algor."},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI\u201914)","author":"Dickerson John P.","year":"2014","unstructured":"John P. Dickerson , Jonathan Goldman , Jeremy Karp , Ariel D. Procaccia , and Tuomas Sandholm . 2014 . The computational rise and fall of fairness . In Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI\u201914) . 1405\u20131411. John P. Dickerson, Jonathan Goldman, Jeremy Karp, Ariel D. Procaccia, and Tuomas Sandholm. 2014. The computational rise and fall of fairness. In Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI\u201914). 1405\u20131411."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1613\/jair.1.11291"},{"key":"e_1_2_1_29_1","first-page":"45","article-title":"Resource allocation and the public sector","volume":"7","author":"Foley Duncan K.","year":"1967","unstructured":"Duncan K. Foley . 1967 . Resource allocation and the public sector . Yale Econ. Essays 7 , 1 (1967), 45 \u2013 98 . Duncan K. Foley. 1967. Resource allocation and the public sector. Yale Econ. Essays 7, 1 (1967), 45\u201398.","journal-title":"Yale Econ. Essays"},{"key":"e_1_2_1_30_1","article-title":"Which is the fairest (rent division) of them all","volume":"64","author":"Gal Ya\u2019akov","year":"2017","unstructured":"Ya\u2019akov (Kobi) Gal , Moshe Mash , Ariel D. Procaccia , and Yair Zick . 2017 . Which is the fairest (rent division) of them all ? J. ACM 64 , 6 (2017), 39:1\u201339:22. Ya\u2019akov (Kobi) Gal, Moshe Mash, Ariel D. Procaccia, and Yair Zick. 2017. Which is the fairest (rent division) of them all? J. ACM 64, 6 (2017), 39:1\u201339:22.","journal-title":"J. ACM"},{"key":"e_1_2_1_31_1","article-title":"Fair enough: Guaranteeing approximate maximin shares","volume":"64","author":"Kurokawa David","year":"2018","unstructured":"David Kurokawa , Ariel D. Procaccia , and Junxing Wang . 2018 . Fair enough: Guaranteeing approximate maximin shares . J. ACM 64 , 2 (2018), 8:1\u20138:27. David Kurokawa, Ariel D. Procaccia, and Junxing Wang. 2018. Fair enough: Guaranteeing approximate maximin shares. J. ACM 64, 2 (2018), 8:1\u20138:27.","journal-title":"J. ACM"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2020.07.008"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/988772.988792"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33012109"},{"key":"e_1_2_1_35_1","unstructured":"Pasin Manurangsi and Warut Suksompong. 2020. Closing gaps in asymptotic fair division. Retrieved from https:\/\/arXiv:2004.05563.  Pasin Manurangsi and Warut Suksompong. 2020. Closing gaps in asymptotic fair division. Retrieved from https:\/\/arXiv:2004.05563."},{"key":"e_1_2_1_36_1","first-page":"231","article-title":"Approximation algorithms and hardness results for fair division with indivisible goods. In Trends in Computational Social Choice, Ulle Endriss (Ed.). AI Access","volume":"12","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 , Chapter 12 , 231 \u2013 247 . 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, Chapter 12, 231\u2013247.","journal-title":"Chapter"},{"key":"e_1_2_1_37_1","volume-title":"Green","author":"Mas-Colell Andreu","year":"1995","unstructured":"Andreu Mas-Colell , Michael D. Whinston , and Jerry R . Green . 1995 . Microeconomic Theory. Oxford University Press . Andreu Mas-Colell, Michael D. Whinston, and Jerry R. Green. 1995. Microeconomic Theory. Oxford University Press."},{"key":"e_1_2_1_38_1","volume-title":"Fair Division and Collective Welfare","author":"Moulin Herv\u00e9","unstructured":"Herv\u00e9 Moulin . 2003. Fair Division and Collective Welfare . MIT Press . Herv\u00e9 Moulin. 2003. Fair Division and Collective Welfare. MIT Press."},{"key":"e_1_2_1_39_1","first-page":"407","article-title":"Fair division in the Internet age. Annu","volume":"11","author":"Moulin Herv\u00e9","year":"2019","unstructured":"Herv\u00e9 Moulin . 2019 . Fair division in the Internet age. Annu . Rev. Econ. 11 (2019), 407 \u2013 441 . Herv\u00e9 Moulin. 2019. Fair division in the Internet age. Annu. Rev. Econ. 11 (2019), 407\u2013441.","journal-title":"Rev. Econ."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1609\/aaai.v33i01.33012141"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1137\/19M124397X"},{"key":"e_1_2_1_42_1","doi-asserted-by":"crossref","unstructured":"Jack Robertson and William Webb. 1998. Cake-Cutting Algorithms: Be Fair If You Can. Peters\/CRC Press.  Jack Robertson and William Webb. 1998. Cake-Cutting Algorithms: Be Fair If You Can. Peters\/CRC Press.","DOI":"10.1201\/9781439863855"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jmaa.2019.123382"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jmateco.2017.01.007"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.artint.2019.103167"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.2021.1835338"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2019.01.036"},{"key":"e_1_2_1_48_1","volume-title":"Handbook of Computational Social Choice, Felix Brandt, Vincent Conitzer, Ulle Endriss, J\u00e9r\u00f4me Lang, and Ariel D","author":"Thomson William","unstructured":"William Thomson . 2016. Introduction to the theory of fair allocation . In Handbook of Computational Social Choice, Felix Brandt, Vincent Conitzer, Ulle Endriss, J\u00e9r\u00f4me Lang, and Ariel D . Procaccia (Eds.). Cambridge University Press , Chapter 11, 261\u2013283. William Thomson. 2016. Introduction to the theory of fair allocation. In Handbook of Computational Social Choice, Felix Brandt, Vincent Conitzer, Ulle Endriss, J\u00e9r\u00f4me Lang, and Ariel D. Procaccia (Eds.). Cambridge University Press, Chapter 11, 261\u2013283."},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0531(74)90075-1"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-4627-6_17"}],"container-title":["ACM Transactions on Economics and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3457166","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3457166","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:17:19Z","timestamp":1750191439000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3457166"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,8,16]]},"references-count":50,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,9,30]]}},"alternative-id":["10.1145\/3457166"],"URL":"https:\/\/doi.org\/10.1145\/3457166","relation":{},"ISSN":["2167-8375","2167-8383"],"issn-type":[{"value":"2167-8375","type":"print"},{"value":"2167-8383","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,8,16]]},"assertion":[{"value":"2020-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-08-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}