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

Keeping the Harmony Between Neighbors: Local Fairness in Graph Fair Division

Published: 06 May 2024 Publication History

Abstract

We study the problem of allocating indivisible resources under the connectivity constraints of a graph G. This model, initially introduced by Bouveret et al. (published in IJCAI, 2017), effectively encompasses a diverse array of scenarios characterized by spatial or temporal limitations, including the division of land plots and the allocation of time plots. In this paper, we introduce a novel fairness concept that integrates local comparisons within the social network formed by a connected allocation of the item graph. Our particular focus is to achieve pairwise-maximin fair share (PMMS) among the "neighbors" within this network. For any underlying graph structure, we show that a connected allocation that maximizes Nash welfare guarantees a (1/2)-PMMS fairness. Moreover, for two agents, we establish that a (3/4)-PMMS allocation can be efficiently computed. Additionally, we demonstrate that for three agents and the items aligned on a path, a PMMS allocation is always attainable and can be computed in polynomial time. Lastly, when agents have identical additive utilities, we present a pseudo-polynomial-time algorithm for a (3/4)-PMMS allocation, irrespective of the underlying graph G. Furthermore, we provide a polynomial-time algorithm for obtaining a PMMS allocation when G is a tree.

References

[1]
Rediet Abebe, Jon Kleinberg, and David C. Parkes. 2017. Fair Division via Social Comparison. In Proceedings of the 16th International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS). 281--289.
[2]
Georgios Amanatidis, Haris Aziz, Georgios Birmpas, Aris Filos-Ratsikas, Bo Li, Hervé Moulin, Alexandros A. Voudouris, and Xiaowei Wu. 2022. Fair Division of Indivisible Goods: Recent Progress and Open Questions. arxiv: 2208.08782 [cs.GT]
[3]
Georgios Amanatidis, Georgios Birmpas, and Vangelis Markakis. 2018. Comparing Approximate Relaxations of Envy-Freeness. In Proceedings of the 27th International Joint Conference on Artificial Intelligence (IJCAI). 42--48.
[4]
Georgios Amanatidis, Evangelos Markakis, and Apostolos Ntokos. 2020. Multiple birds with one stone: Beating 1/2 for EFX and GMMS via envy cycle elimination. Theoretical Computer Science, Vol. 841 (2020), 94--109.
[5]
Xiaohui Bei, Ayumi Igarashi, Xinhang Lu, and Warut Suksompong. 2022. The Price of Connectivity in Fair Division. SIAM journal on Discrete Mathematics, Vol. 36, 2 (2022), 1156--1186.
[6]
Xiaohui Bei, Youming Qiao, and Shengyu Zhang. 2017. Networked Fairness in Cake Cutting. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI). 3632--3638.
[7]
Aurélie Beynier, Yann Chevaleyre, Laurent Gourvès, Julien Lesca, Nicolas Maudet, and Anaëlle Wilczynski. 2019. Local envy-freeness in house allocation problems. Autonomous Agents and Multi-Agent Systems, Vol. 33 (2019), 591--627.
[8]
Vittorio Bilò, Ioannis Caragiannis, Michele Flammini, Ayumi Igarashi, Gianpiero Monaco, Dominik Peters, Cosimo Vinci, and William S. Zwicker. 2022. Almost Envy-Free Allocations with Connected Bundles. Games and Economic Behavior, Vol. 131 (2022), 197--221.
[9]
John Adrian Bondy and U. S. R. Murty. 2008. Graph Theory 1st ed.). Springer.
[10]
Sylvain Bouveret, Katarína Cechlárová, Edith Elkind, Ayumi Igarashi, and Dominik Peters. 2017. Fair Division of a Graph. In Proceedings of the 26th International Joint Conference on Artificial Intelligence (IJCAI). 135--141.
[11]
Steven J. Brams and Peter C. Fishburn. 2000. Fair Division of Indivisible Items Between Two People with Identical Preferences: Envy-Freeness, Pareto-Optimality, and Equity. Social Choice and Welfare, Vol. 17, 2 (2000), 247--267.
[12]
Steven J. Brams, Marc Kilgour, and Christian Klamler. 2014. Two-Person Fair Division of Indivisible Items: An Efficient, Envy-Free Algorithm. Notices of the AMS, Vol. 61, 2 (2014), 130--141.
[13]
Robert Bredereck, Andrzej Kaczmarczyk, and Rolf Niedermeier. 2022. Envy-free allocations respecting social networks. Artificial Intelligence, Vol. 305 (2022), 103664.
[14]
Eric Budish. 2011. The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes. Journal of Political Economy, Vol. 119, 6 (2011), 1061--1103.
[15]
Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D. Procaccia, Nisarg Shah, and Junxing Wang. 2019. The Unreasonable Fairness of Maximum Nash Welfare. ACM Transactions on Economics and Computation, Vol. 7, 3 (2019), 12:1--12:32.
[16]
Uriel Feige, Ariel Sapir, and Laliv Tauber. 2022. A Tight Negative Example for MMS Fair Allocations. In Web and Internet Economics (Lecture Notes in Computer Science ), Michal Feldman, Hu Fu, and Inbal Talgam-Cohen (Eds.). Springer International Publishing, Cham, 355--372. https://doi.org/10.1007/978-3-030-94676-0_20
[17]
Leon Festinger. 1954. A theory of social comparison processes. Human Relations, Vol. 7 (1954), 117--140.
[18]
Michael R. Garey and David S. Johnson. 1979. Computers and Intractability; A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., USA.
[19]
Gianluigi Greco and Francesco Scarcello. 2020. The Complexity of Computing Maximin Share Allocations on Graphs. In Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI). 2006--2013.
[20]
Hadi Hosseini, Justin Payan, Rik Sengupta, Rohit Vaish, and Vignesh Viswanathan. 2023. Graphical House Allocation. In Proceedings of the 22nd International Conference on Autonomous Agents and Multi-Agent Systems (AAMAS). 161--169.
[21]
Ayumi Igarashi. 2023. How to cut a discrete cake fairly. In Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI).
[22]
Ayumi Igarashi and Dominik Peters. 2019. Pareto-Optimal Allocation of Indivisible Goods with Connectivity Constraints. In Proceedings of the 33rd AAAI Conference on Artificial Intelligence (AAAI), Vol. 33. 2045--2052.
[23]
D. Marc Kilgour and Rudolf Vetschera. 2018. Two-Player Fair Division of Indivisible Items: Comparison of Algorithms. European Journal of Operational Research, Vol. 271, 2 (2018), 620--631.
[24]
David Kurokawa. 2017. Fair division in game theoretic settings. Ph.D. Dissertation. Carnegie Mellon University.
[25]
David Kurokawa, Ariel D. Procaccia, and Junxing Wang. 2018. Fair enough: Guaranteeing approximate maximin shares. J. ACM, Vol. 64, 2 (2018), 8:1--8:27.
[26]
Abraham Lempel, Shimon Even, and Israel Cederbaum. 1967. An algorithm for planarity testing of graphs. Theory of Graphs: International Symposium (1967), 215--232.
[27]
Zbigniew Lonc. 2023. Approximating Fair Division on D-Claw-Free Graphs. In Proceedings of the Thirty-Second International Joint Conference on Artificial Intelligence. International Joint Conferences on Artificial Intelligence Organization, Macau, SAR China, 2826--2834. https://doi.org/10.24963/ijcai.2023/315
[28]
Hervé Moulin. 2003. Fair Division and Collective Welfare. MIT Press.
[29]
Yehoshua Perl and Stephen R. Schach. 1981. Max-Min Tree Partitioning. J. ACM, Vol. 28, 1 (Jan. 1981), 5--15. https://doi.org/10.1145/322234.322236
[30]
Benjamin Plaut and Tim Roughgarden. 2020. Almost Envy-Freeness with General Valuations. SIAM Journal on Discrete Mathematics, Vol. 34, 2 (Jan. 2020), 1039--1068.
[31]
Leonard I. Schieman, Scott Pearlin. 2006. Neighborhood Disadvantage, Social Comparisons, and the Subjective Assessment of Ambient Problems Among Older Adults. Social Psychology Quarterly, Vol. 69, 3 (2006), 253--269.
[32]
Jerry Suls and Ladd Wheeler (Eds.). 2000. Handbook of Social Comparison: Theory and Research. Springer New York, NY.
[33]
Miroslaw Truszczynski and Zbigniew Lonc. 2020. Maximin Share Allocations on Cycles. Journal of Artificial Intelligence Research, Vol. 69 (Oct. 2020), 613--655.

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
AAMAS '24: Proceedings of the 23rd International Conference on Autonomous Agents and Multiagent Systems
May 2024
2898 pages
ISBN:9798400704864

Sponsors

Publisher

International Foundation for Autonomous Agents and Multiagent Systems

Richland, SC

Publication History

Published: 06 May 2024

Check for updates

Author Tags

  1. fair division
  2. graph
  3. pairwise-maximin fair share

Qualifiers

  • Research-article

Conference

AAMAS '24
Sponsor:

Acceptance Rates

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

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • 0
    Total Citations
  • 21
    Total Downloads
  • Downloads (Last 12 months)21
  • Downloads (Last 6 weeks)0
Reflects downloads up to 19 Dec 2024

Other Metrics

Citations

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