More Web Proxy on the site http://driver.im/

research-article

Ordinal Maximin Share Approximation for Chores

Authors:

Erel Segal-HaleviAuthors Info & Claims

AAMAS '22: Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems

Pages 597 - 605

Published: 09 May 2022 Publication History

Abstract

We study the problem of fairly allocating a set of m indivisible chores (items with non-positive value) to n agents. We consider the desirable fairness notion of 1-out-of-d maximin share (MMS)---the minimum value that an agent can guarantee by partitioning items into d bundles and receiving the least valued bundle---and focus on ordinal approximation of MMS that aims at finding the largest dłeq n for which 1-out-of-d MMS allocation exists. Our main contribution is a polynomial-time algorithm for 1-out-of-ł 2n/3 MMS allocation, and a proof of existence of 1-out-of-łfloor 3n/4 MMS allocation of chores. Furthermore, we show how to use recently-developed algorithms for bin-packing to approximate the latter bound up to a logarithmic factor in polynomial time.

References

[1]

Elad Aigner-Horev and Erel Segal-Halevi. 2022. Envy-free matchings in bipartite graphs and their applications to fair division. Information Sciences 587 (2022), 164--187.

Digital Library

[2]

Georgios Amanatidis, Evangelos Markakis, Afshin Nikzad, and Amin Saberi. 2017. Approximation algorithms for computing maximin share allocations. ACM Transactions on Algorithms (TALG) 13, 4 (2017), 52.

Digital Library

[3]

Haris Aziz, Ioannis Caragiannis, Ayumi Igarashi, and Toby Walsh. 2019. Fair allocation of combinations of indivisible goods and chores. In Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI). 53--59.

Digital Library

[4]

Haris Aziz, Hau Chan, and Bo Li. 2019. Maxmin share fair allocation of indivisible chores to asymmetric agents. In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems. 1787--1789.

[5]

Haris Aziz, Hau Chan, and Bo Li. 2019. Weighted Maxmin Fair Share Allocation of Indivisible Chores. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19. International Joint Conferences on Artificial Intelligence Organization, 46--52. https://doi.org/10.24963/ijcai.2019/7

[6]

Haris Aziz, Bo Li, and Xiaowei Wu. 2019. Strategyproof and Approximately Maxmin Fair Share Allocation of Chores. In Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI-19. International Joint Conferences on Artificial Intelligence Organization, 60--66. https://doi.org/ 10.24963/ijcai.2019/9

[7]

Haris Aziz, Bo Li, and Xiaowei Wu. 2020. Approximate and Strategyproof Maximin Share Allocation of Chores with Ordinal Preferences. arXiv preprint arXiv:2012.13884 (2020).

[8]

Haris Aziz, Hervé Moulin, and Fedor Sandomirskiy. 2020. A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation. Operations Research Letters 48, 5 (2020), 573--578.

[9]

Haris Aziz, Gerhard Rauchecker, Guido Schryen, and Toby Walsh. 2017. Algorithms for Max-Min Share Fair Allocation of Indivisible Chores. Proceedings of the AAAI Conference on Artificial Intelligence 31, 1 (Feb. 2017). https://ojs.aaai.org/index.php/AAAI/article/view/10582

[10]

Moshe Babaioff, Noam Nisan, and Inbal Talgam-Cohen. 2019. Fair Allocation through Competitive Equilibrium from Generic Incomes. In Proceedings of the Conference on Fairness, Accountability, and Transparency. 180--180.

Digital Library

[11]

Moshe Babaioff, Noam Nisan, and Inbal Talgam-Cohen. 2021. Competitive equilibrium with indivisible goods and generic budgets. Mathematics of Operations Research 46, 1 (2021), 382--403.

Digital Library

[12]

Brenda S Baker. 1985. A new proof for the first-fit decreasing bin-packing algorithm. Journal of Algorithms 6, 1 (1985), 49--70.

[13]

Siddharth Barman and Sanath Kumar Krishna Murthy. 2017. Approximation algorithms for maximin fair division. In Proceedings of the 2017 ACM Conference on Economics and Computation. 647--664.

Digital Library

[14]

Anna Bogomolnaia and Hervé Moulin. 2022. Guarantees in Fair Division: General or monotone preferences. arXiv preprint 1911.10009.

[15]

Anna Bogomolnaia, Hervé Moulin, Fedor Sandomirskiy, and Elena Yanovskaia. 2019. Dividing bads under additive utilities. Social Choice and Welfare 52, 3 (2019), 395--417.

[16]

Sylvain Bouveret and Michel Lemaître. 2016. Characterizing conflicts in fair division of indivisible goods using a scale of criteria. Autonomous Agents and Multi-Agent Systems 30, 2 (01 Mar 2016), 259--290. https://doi.org/10.1007/s10458-015--9287--3

[17]

Steven J Brams and Alan D Taylor. 1996. Fair Division: From cake-cutting to dispute resolution. Cambridge University Press.

[18]

Felix Brandt, Vincent Conitzer, Ulle Endriss, Jérôme Lang, and Ariel D Procaccia. 2016. Handbook of computational social choice. Cambridge University Press.

Digital Library

[19]

Eric Budish. 2011. The combinatorial assignment problem: Approximate competitive equilibrium from equal incomes. Journal of Political Economy 119, 6 (2011), 1061--1103.

[20]

Simon Caney. 2009. Justice and the distribution of greenhouse gas emissions. Journal of global ethics 5, 2 (2009), 125--146.

[21]

Bhaskar Ray Chaudhury, Jugal Garg, Peter McGlaughlin, and Ruta Mehta. 2020. Dividing bads is harder than dividing goods: On the complexity of fair and efficient division of chores. arXiv preprint arXiv:2008.00285 (2020).

[22]

Xingyu Chen and Zijie Liu. 2020. The fairness of leximin in allocation of indivisible chores. arXiv preprint arXiv:2005.04864 (2020).

[23]

Edward G Coffman, Jr, Michael R Garey, and David S Johnson. 1978. An application of bin-packing to multiprocessor scheduling. SIAM J. Comput. 7, 1 (1978), 1--17.

Digital Library

[24]

György Dósa. 2007. The tight bound of first fit decreasing bin-packing algorithm is FFD (I) <= 11/9OPT (I)+ 6/9. In International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies. Springer, 1--11.

[25]

György Dósa, Rongheng Li, Xin Han, and Zsolt Tuza. 2013. Tight absolute bound for First Fit Decreasing bin-packing: FFD (L) <= 11/9 OPT (L)+ 6/9. Theoretical Computer Science 510 (2013), 13--61.

Digital Library

[26]

Edith Elkind, Erel Segal-Halevi, and Warut Suksompong. 2021. Graphical Cake Cutting via Maximin Share. In Proceedings of IJCAI.

[27]

Edith Elkind, Erel Segal-Halevi, and Warut Suksompong. 2021. Mind the Gap: Cake Cutting With Separation. In Proceedings of the AAAI Conference on Artificial Intelligence. 5330--5338.

[28]

Uriel Feige, Ariel Sapir, and Laliv Tauber. 2021. A tight negative example for MMS fair allocations. arXiv preprint arXiv:2104.04977 (2021).

[29]

Rupert Freeman, Sujoy Sikdar, Rohit Vaish, and Lirong Xia. 2020. Equitable Allocations of Indivisible Chores. In Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems. 384--392.

Digital Library

[30]

Jugal Garg, Peter McGlaughlin, and Setareh Taki. 2018. Approximating Maximin Share Allocations. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik.

[31]

Jugal Garg and Setareh Taki. 2020. An improved approximation algorithm for maximin shares. In Proceedings of the 21st ACM Conference on Economics and Computation. 379--380.

Digital Library

[32]

Mohammad Ghodsi, MohammadTaghi HajiAghayi, Masoud Seddighin, Saeed Seddighin, and Hadi Yami. 2018. Fair allocation of indivisible goods: Improvements and generalizations. In Proceedings of the 2018 ACM Conference on Economics and Computation. ACM, 539--556.

Digital Library

[33]

Laurent Gourvès and Jérôme Monnot. 2019. On maximin share allocations in matroids. Theoretical Computer Science 754 (2019), 50--64.

[34]

Rebecca Hoberg and Thomas Rothvoss. 2017. A logarithmic additive integrality gap for bin packing. In Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 2616--2625.

[35]

Dorit S Hochbaum and David B Shmoys. 1987. Using dual approximation algorithms for scheduling problems theoretical and practical results. Journal of the ACM (JACM) 34, 1 (1987), 144--162.

Digital Library

[36]

Hadi Hosseini and Andrew Searns. 2021. Guaranteeing Maximin Shares: Some Agents Left Behind. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21, Zhi-Hua Zhou (Ed.). International Joint Conferences on Artificial Intelligence Organization, 238--244. https://doi.org/10.24963/ijcai.2021/34 Main Track.

[37]

Hadi Hosseini, Andrew Searns, and Erel Segal-Halevi. 2021. Ordinal Maximin Share Approximation for Goods. arXiv preprint arXiv:2109.01925 (2021).

[38]

Hadi Hosseini, Andrew Searns, and Erel Segal-Halevi. 2022. Ordinal Maximin Share Approximation for Chores. arXiv:2201.07424 [cs.GT]

[39]

Xin Huang and Pinyan Lu. 2021. An algorithmic framework for approximating maximin share allocation of chores. In Proceedings of the 22nd ACM Conference on Economics and Computation (EC). 630--631.

Digital Library

[40]

David S Johnson. 1973. Near-optimal bin packing algorithms. Ph.D. Dissertation. Massachusetts Institute of Technology.

[41]

Bernhard Korte and Jens Vygen. 2018. Bin-Packing. In Combinatorial Optimization. Springer, 489--507.

[42]

Rucha Kulkarni, Ruta Mehta, and Setareh Taki. 2021. Indivisible Mixed Manna: On the Computability of MMS + PO Allocations. In Proceedings of the 22nd ACM Conference on Economics and Computation. 683--684.

Digital Library

[43]

David Kurokawa, Ariel D Procaccia, and Junxing Wang. 2018. Fair enough: Guaranteeing approximate maximin shares. Journal of the ACM (JACM) 65, 2 (2018), 8.

Digital Library

[44]

Peter McGlaughlin and Jugal Garg. 2020. Improving Nash social welfare approximations. Journal of Artificial Intelligence Research 68 (2020), 225--245.

[45]

Hervé Moulin. 2019. Fair Division in the Internet Age. Annual Review of Economics 11, 1 (2019), 407--441. https://doi.org/10.1146/annurev-economics-080218-025559 arXiv:https://doi.org/10.1146/annurev-economics-080218-025559

[46]

Nhan-Tam Nguyen, Trung Thanh Nguyen, and Jörg Rothe. 2017. Approximate solutions to max-min fair and proportionally fair allocations of indivisible goods. In Proceedings of the 16th Conference on Autonomous Agents and MultiAgent Systems. International Foundation for Autonomous Agents and Multiagent Systems, 262--271.

[47]

Ariel D Procaccia and Junxing Wang. 2014. Fair enough: Guaranteeing approximate maximin shares. In Proceedings of the fifteenth ACM conference on Economics and computation. ACM, 675--692.

Digital Library

[48]

Mathias Risse. 2008. Who Should Shoulder the Burden? Global Climate Change and Common Ownership of the Earth. Technical Report. Harvard University, John F. Kennedy School of Government.

[49]

Andrew Searns and Hadi Hosseini. 2020. Fairness Does Not Imply Satisfaction (Student Abstract). Proceedings of the AAAI Conference on Artificial Intelligence 34, 10 (Apr. 2020), 13911--13912. https://doi.org/10.1609/aaai.v34i10.7228

[50]

Erel Segal-Halevi. 2019. The Maximin Share Dominance Relation. arXiv preprint 1912.08763.

[51]

Erel Segal-Halevi. 2020. Competitive equilibrium for almost all incomes: existence and fairness. Autonomous Agents and Multi-Agent Systems 34, 1 (2020), 1--50.

Digital Library

[52]

Martino Traxler. 2002. Fair chore division for climate change. Social Theory and Practice 28, 1 (2002), 101--134.

[53]

Miroslaw Truszczynski and Zbigniew Lonc. 2020. Maximin Share Allocations on Cycles. Journal of Artificial Intelligence Research 69 (2020), 613--655.

[54]

Gerhard J Woeginger. 1997. A polynomial-time approximation scheme for maximizing the minimum machine completion time. Operations Research Letters 20, 4 (1997), 149--154.

Digital Library

Cited By

Hosseini HLarson K(2024)Algorithmic fairness in distribution of resources and tasksProceedings of the Thirty-Third International Joint Conference on Artificial Intelligence10.24963/ijcai.2024/979(8541-8546)Online publication date: 3-Aug-2024
https://dl.acm.org/doi/10.24963/ijcai.2024/979
Manurangsi PSuksompong WLarson K(2024)Ordinal maximin guarantees for group fair divisionProceedings of the Thirty-Third International Joint Conference on Artificial Intelligence10.24963/ijcai.2024/324(2922-2930)Online publication date: 3-Aug-2024
https://dl.acm.org/doi/10.24963/ijcai.2024/324
Hosseini HMammadov AWąs TElkind E(2023)Fairly allocating goods and (terrible) choresProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/305(2738-2746)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/305

Index Terms

Ordinal Maximin Share Approximation for Chores
1. Applied computing
  1. Law, social and behavioral sciences
    1. Economics
2. Computing methodologies
  1. Artificial intelligence
    1. Distributed artificial intelligence
      1. Multi-agent systems

Recommendations

Approximation Algorithms for Maximin Fair Division
Special Issue on EC'17

We consider the problem of allocating indivisible goods fairly among n agents who have additive and submodular valuations for the goods. Our fairness guarantees are in terms of the maximin share, which is defined to be the maximum value that an agent ...
An Algorithmic Framework for Approximating Maximin Share Allocation of Chores
EC '21: Proceedings of the 22nd ACM Conference on Economics and Computation

We consider the problem of fairly dividing m indivisible chores among n agents. The fairness measure we consider here is the maximin share. The previous best known result is that there always exists a 4/3-approximation maximin share allocation[3]. With ...
Approximation Algorithms for Computing Maximin Share Allocations

We study the problem of computing maximin share allocations, a recently introduced fairness notion. Given a set of n agents and a set of goods, the maximin share of an agent is the best she can guarantee to herself, if she is allowed to partition the ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

AAMAS '22: Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems

May 2022

1990 pages

ISBN:9781450392136

General Chairs:
Catherine Pelachaud
CNRS-ISIR, Sorbonne University, France
,
Matthew E. Taylor
University of Alberta, Canada
,
Program Chairs:
Piotr Faliszewski
AGH University of Science and Technology, Poland
,
Viviana Mascardi
University of Genova, Italy

Sponsors

SIGAI: ACM Special Interest Group on Artificial Intelligence

Publisher

International Foundation for Autonomous Agents and Multiagent Systems

Richland, SC

Publication History

Published: 09 May 2022

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

National Science Foundation USA

Conference

AAMAS ' 22

Sponsor:

SIGAI

AAMAS ' 22: International Conference on Autonomous Agents and Multi-Agent Systems

May 9 - 13, 2022

Virtual Event, New Zealand

Acceptance Rates

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
31
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Hosseini HLarson K(2024)Algorithmic fairness in distribution of resources and tasksProceedings of the Thirty-Third International Joint Conference on Artificial Intelligence10.24963/ijcai.2024/979(8541-8546)Online publication date: 3-Aug-2024
https://dl.acm.org/doi/10.24963/ijcai.2024/979
Manurangsi PSuksompong WLarson K(2024)Ordinal maximin guarantees for group fair divisionProceedings of the Thirty-Third International Joint Conference on Artificial Intelligence10.24963/ijcai.2024/324(2922-2930)Online publication date: 3-Aug-2024
https://dl.acm.org/doi/10.24963/ijcai.2024/324
Hosseini HMammadov AWąs TElkind E(2023)Fairly allocating goods and (terrible) choresProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/305(2738-2746)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/305

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Table of Conten