[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.5555/3398761.3398793acmconferencesArticle/Chapter ViewAbstractPublication PagesaamasConference Proceedingsconference-collections
research-article

Weighted Envy-Freeness in Indivisible Item Allocation

Published: 13 May 2020 Publication History

Abstract

In this paper, we introduce and analyze new envy-based fairness concepts for agents with weights that quantify their entitlements in the allocation of indivisible items. We propose two variants of weighted envy-freeness up to one item (WEF1) -- strong (where the envy can be eliminated by removing an item from the envied agent's bundle) and weak (where the envy can be eliminated either by removing an item as in the strong version or by replicating an item from the envied agent's bundle in the envious agent's bundle). We prove that for additive valuations, an allocation that is both Pareto optimal and strongly WEF1 always exists; however, an allocation that maximizes the weighted Nash social welfare may not be strongly WEF1 but always satisfies the weak version of the property. Moreover, we establish that a generalization of the round-robin picking sequence 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 classic adjusted winner algorithm. We also explore the connections of WEF1 with approximations to the weighted versions of two other fairness concepts: proportionality and the maximin share guarantee.

References

[1]
Georgios Amanatidis, Georgios Birmpas, and Evangelos Markakis. 2018. Comparing approximate relaxations of envy-freeness. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI). 42--48.
[2]
Haris Aziz, Hau Chan, and Bo Li. 2019 a. Weighted maxmin fair share allocation of indivisible chores. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI). 46--52.
[3]
Haris Aziz, Hervé Moulin, and Fedor Sandomirskiy. 2019 b. A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation. arXiv preprint arXiv:1909.00740 (2019).
[4]
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*). 180.
[5]
Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish. 2018. Finding fair and efficient allocations. In Proceedings of the 19th ACM Conference on Economics and Computation (EC). 557--574. Extended version available as arXiv:1707.04731.
[6]
Nawal Benabbou, Mithun Chakraborty, Edith Elkind, and Yair Zick. 2019. Fairness towards groups of agents in the allocation of indivisible items. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI). 95--101.
[7]
Nawal Benabbou, Mithun Chakraborty, Vinh Ho Xuan, Jakub Sliwinski, and Yair Zick. 2018. Diversity constraints in public housing allocation. In Proceedings of the 17th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS). 973--981.
[8]
Sylvain Bouveret, Yann Chevaleyre, and Nicolas Maudet. 2016. Fair allocation of indivisible goods. Handbook of Computational Social Choice, Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D. Procaccia (Eds.). Cambridge University Press, Chapter 12, 284--310.
[9]
Steven J. Brams and Alan D. Taylor. 1996. Fair Division: From Cake-Cutting to Dispute Resolution. Cambridge University Press.
[10]
Eric Budish. 2011. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy, Vol. 119, 6 (2011), 1061--1103.
[11]
Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang. 2016. The unreasonable fairness of maximum Nash welfare. In Proceedings of the 17th ACM Conference on Economics and Computation (EC). 305--322.
[12]
Mithun Chakraborty, Ayumi Igarashi, Warut Suksompong, and Yair Zick. 2019. Weighted envy-freeness in indivisible item allocation. arXiv preprint arXiv:1909.10502 (2019).
[13]
Vincent Conitzer, Rupert Freeman, and Nisarg Shah. 2017. Fair public decision making. In Proceedings of the 18th ACM Conference on Economics and Computation (EC). 629--646.
[14]
Vincent Conitzer, Rupert Freeman, Nisarg Shah, and Jennifer Wortman Vaughan. 2019. Group fairness for the allocation of indivisible goods. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI). 1853--1860.
[15]
Ágnes Cseh and Tamás Fleiner. 2018. The complexity of cake cutting with unequal shares. In Proceedings of the 11th International Symposium on Algorithmic Game Theory (SAGT). 19--30.
[16]
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). 1405--1411.
[17]
Alireza Farhadi, Mohammad Ghodsi, MohammadTaghi Hajiaghayi, Sebastien Lahaie, David Pennock, Masoud Seddighin, Saeed Seddighin, and Hadi Yami. 2019. Fair allocation of indivisible goods to asymmetric agents. Journal of Artificial Intelligence Research (JAIR), Vol. 64 (2019), 1--20.
[18]
Duncan K. Foley. 1967. Resource allocation and the public sector. Yale Economics Essays, Vol. 7, 1 (1967), 45--98.
[19]
Richard J. Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi. 2004. On approximately fair allocations of indivisible goods. In Proceedings of the 5th ACM Conference on Electronic Commerce (EC). 125--131.
[20]
Pasin Manurangsi and Warut Suksompong. 2017. Asymptotic existence of fair divisions for groups. Mathematical Social Sciences, Vol. 89 (2017), 100--108.
[21]
Pasin Manurangsi and Warut Suksompong. 2019. When do envy-free allocations exist?. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI). 2109--2116.
[22]
Andreu Mas-Colell, Michael D. Whinston, and Jerry R. Green. 1995. Microeconomic Theory. Oxford University Press.
[23]
Benjamin Plaut and Tim Roughgarden. 2018. Almost envy-freeness with general valuations. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). 2584--2603.
[24]
Jack Robertson and William Webb. 1998. Cake-Cutting Algorithms: Be Fair if You Can. Peters/CRC Press.
[25]
Erel Segal-Halevi. 2019. Cake-cutting with different entitlements: How many cuts are needed? J. Math. Anal. Appl., Vol. 480, 1 (2019), 123382.
[26]
Warut Suksompong. 2018. Approximate maximin shares for groups of agents. Mathematical Social Sciences, Vol. 92 (2018), 40--47.
[27]
Hal R. Varian. 1974. Equity, envy, and efficiency. Journal of Economic Theory, Vol. 9 (1974), 63--91.
[28]
Dao-Zhi Zeng. 2000. Approximate envy-free procedures. Game Practice: Contributions from Applied Game Theory, Fioravante Patrone, Ignacio García-Jurado, and Stef Tijs (Eds.). Springer, Chapter 17, 259--271.

Cited By

View all
  • (2024)Weighted EF1 and PO allocations with few types of agents or choresProceedings of the Thirty-Third International Joint Conference on Artificial Intelligence10.24963/ijcai.2024/310(2799-2806)Online publication date: 3-Aug-2024
  • (2023)For One and All: Individual and Group Fairness in the Allocation of Indivisible GoodsProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems10.5555/3545946.3598969(2466-2468)Online publication date: 30-May-2023
  • (2022)I Will Have Order! Optimizing Orders for Fair Reviewer AssignmentProceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems10.5555/3535850.3536085(1711-1713)Online publication date: 9-May-2022

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
AAMAS '20: Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems
May 2020
2289 pages
ISBN:9781450375184

Sponsors

Publisher

International Foundation for Autonomous Agents and Multiagent Systems

Richland, SC

Publication History

Published: 13 May 2020

Check for updates

Author Tags

  1. envy-freeness
  2. fair division
  3. indivisible items
  4. unequal entitlements

Qualifiers

  • Research-article

Funding Sources

  • European Research Council
  • Singapore Ministry of Education
  • KAKENHI Grant-in-Aid for JSPS Fellows
  • JST ACT-X
  • Singapore NRF Research Fellowship

Conference

AAMAS '19
Sponsor:

Acceptance Rates

Overall Acceptance Rate 1,155 of 5,036 submissions, 23%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)2
  • Downloads (Last 6 weeks)0
Reflects downloads up to 14 Jan 2025

Other Metrics

Citations

Cited By

View all
  • (2024)Weighted EF1 and PO allocations with few types of agents or choresProceedings of the Thirty-Third International Joint Conference on Artificial Intelligence10.24963/ijcai.2024/310(2799-2806)Online publication date: 3-Aug-2024
  • (2023)For One and All: Individual and Group Fairness in the Allocation of Indivisible GoodsProceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems10.5555/3545946.3598969(2466-2468)Online publication date: 30-May-2023
  • (2022)I Will Have Order! Optimizing Orders for Fair Reviewer AssignmentProceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems10.5555/3535850.3536085(1711-1713)Online publication date: 9-May-2022

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media