Document Open Access Logo

On Approximate Envy-Freeness for Indivisible Chores and Mixed Resources

Authors Umang Bhaskar, A. R. Sricharan, Rohit Vaish

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2021.1.pdf
  • Filesize: 0.77 MB
  • 23 pages

Document Identifiers

Author Details

Umang Bhaskar
  • Tata Institute of Fundamental Research, Mumbai, India
A. R. Sricharan
  • Chennai Mathematical Institute, India
Rohit Vaish
  • Tata Institute of Fundamental Research, Mumbai, India

Funding

UB and RV acknowledge support from project no. RTI4001 of the Department of Atomic Energy, Government of India. RV also acknowledges support from the Prof. R Narasimhan postdoctoral award.

Acknowledgements

We thank the anonymous reviewers for helpful comments.

Cite AsGet BibTex

Umang Bhaskar, A. R. Sricharan, and Rohit Vaish. On Approximate Envy-Freeness for Indivisible Chores and Mixed Resources. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 207, pp. 1:1-1:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2021.1

Abstract

We study the fair allocation of undesirable indivisible items, or chores. While the case of desirable indivisible items (or goods) is extensively studied, with many results known for different notions of fairness, less is known about the fair division of chores. We study envy-free allocation of chores and make three contributions. First, we show that determining the existence of an envy-free allocation is NP-complete even in the simple case when agents have binary additive valuations. Second, we provide a polynomial-time algorithm for computing an allocation that satisfies envy-freeness up to one chore (EF1), correcting a claim in the existing literature. A modification of our algorithm can be used to compute an EF1 allocation for doubly monotone instances (where each agent can partition the set of items into objective goods and objective chores). Our third result applies to a mixed resources model consisting of indivisible items and a divisible, undesirable heterogeneous resource (i.e., a bad cake). We show that there always exists an allocation that satisfies envy-freeness for mixed resources (EFM) in this setting, complementing a recent result of Bei et al. [Bei et al., 2021] for indivisible goods and divisible cake.

Subject Classification

ACM Subject Classification
  • Theory of computation → Algorithmic game theory
  • Theory of computation → Exact and approximate computation of equilibria
  • Mathematics of computing → Combinatorial algorithms
Keywords
  • Fair Division
  • Indivisible Chores
  • Approximate Envy-Freeness

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Martin Aleksandrov. Almost Envy Freeness and Welfare Efficiency in Fair Division with Goods or Bads. arXiv preprint arXiv:1808.00422, 2018. Google Scholar
  2. Martin Aleksandrov. Jealousy-Freeness and Other Common Properties in Fair Division of Mixed Manna. arXiv preprint arXiv:2004.11469, 2020. Google Scholar
  3. Ahmet Alkan, Gabrielle Demange, and David Gale. Fair Allocation of Indivisible Goods and Criteria of Justice. Econometrica: Journal of the Econometric Society, pages 1023-1039, 1991. Google Scholar
  4. Noga Alon. Splitting Necklaces. Advances in Mathematics, 63(3):247-253, 1987. Google Scholar
  5. Georgios Amanatidis, Evangelos Markakis, and Apostolos Ntokos. Multiple Birds with One Stone: Beating 1/2 for EFX and GMMS via Envy Cycle Elimination. Theoretical Computer Science, 841:94-109, 2020. Google Scholar
  6. Enriqueta Aragones. A Derivation of the Money Rawlsian Solution. Social Choice and Welfare, 12(3):267-276, 1995. Google Scholar
  7. Sergey Avvakumov and Roman Karasev. Envy-Free Division Using Mapping Degree. arXiv preprint arXiv:1907.11183, 2019. Google Scholar
  8. Sergey Avvakumov and Roman Karasev. Equipartition of a Segment. arXiv preprint arXiv:2009.09862, 2020. Google Scholar
  9. Haris Aziz. Achieving Envy-freeness and Equitability with Monetary Transfers. In Proceedings of the 35th AAAI Conference on Artificial Intelligence, pages 5102-5109, 2021. Google Scholar
  10. Haris Aziz, Ioannis Caragiannis, Ayumi Igarashi, and Toby Walsh. Fair Allocation of Combinations of Indivisible Goods and Chores. arXiv preprint arXiv:1807.10684 (version v3), 2018. Google Scholar
  11. Haris Aziz, Ioannis Caragiannis, Ayumi Igarashi, and Toby Walsh. Fair Allocation of Indivisible Goods and Chores. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pages 53-59, 2019. Google Scholar
  12. Haris Aziz, Hau Chan, and Bo Li. Weighted Maxmin Fair Share Allocation of Indivisible Chores. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pages 46-52, 2019. Google Scholar
  13. Haris Aziz, Serge Gaspers, Simon Mackenzie, and Toby Walsh. Fair Assignment of Indivisible Objects under Ordinal Preferences. Artificial Intelligence, 227:71-92, 2015. Google Scholar
  14. Haris Aziz, Bo Li, and Xiaowei Wu. Strategyproof and Approximately Maxmin Fair Share Allocation of Chores. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pages 60-66, 2019. Google Scholar
  15. Haris Aziz and Simon Mackenzie. A Discrete and Bounded Envy-Free Cake Cutting Protocol for Any Number of Agents. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science, pages 416-427, 2016. Google Scholar
  16. Haris Aziz, Hervé Moulin, and Fedor Sandomirskiy. A Polynomial-Time Algorithm for Computing a Pareto Optimal and Almost Proportional Allocation. Operations Research Letters, 48(5):573-578, 2020. Google Scholar
  17. Haris Aziz, Gerhard Rauchecker, Guido Schryen, and Toby Walsh. Algorithms for Max-Min Share Fair Allocation of Indivisible Chores. In Proceedings of the 31st AAAI Conference on Artificial Intelligence, pages 335-341, 2017. Google Scholar
  18. Haris Aziz and Chun Ye. Cake Cutting Algorithms for Piecewise Constant and Piecewise Uniform Valuations. In Proceedings of the 10th International Conference on Web and Internet Economics, pages 1-14, 2014. Google Scholar
  19. Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish. Finding Fair and Efficient Allocations. In Proceedings of the 19th ACM Conference on Economics and Computation, pages 557-574, 2018. Google Scholar
  20. Siddharth Barman, Sanath Kumar Krishnamurthy, and Rohit Vaish. Greedy Algorithms for Maximizing Nash Social Welfare. In Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems, pages 7-13, 2018. Google Scholar
  21. Siddharth Barman and Nidhi Rathi. Fair Cake Division Under Monotone Likelihood Ratios. In Proceedings of the 21st ACM Conference on Economics and Computation, pages 401-437, 2020. Google Scholar
  22. Xiaohui Bei, Zihao Li, Jinyan Liu, Shengxin Liu, and Xinhang Lu. Fair Division of Mixed Divisible and Indivisible Goods. Artificial Intelligence, 293:103436, 2021. Google Scholar
  23. Xiaohui Bei, Shengxin Liu, Xinhang Lu, and Hongao Wang. Maximin Fairness with Mixed Divisible and Indivisible Goods. Autonomous Agents and Multi-Agent Systems, 35(2):1-21, 2021. Google Scholar
  24. Nawal Benabbou, Mithun Chakraborty, Xuan-Vinh Ho, Jakub Sliwinski, and Yair Zick. The Price of Quota-based Diversity in Assignment Problems. ACM Transactions on Economics and Computation, 8(3):1-32, 2020. Google Scholar
  25. Nawal Benabbou, Mithun Chakraborty, Ayumi Igarashi, and Yair Zick. Finding Fair and Efficient Allocations When Valuations Don't Add Up. In Proceedings of the 13th International Symposium on Algorithmic Game Theory, pages 32-46, 2020. Google Scholar
  26. Kristóf Bérczi, Erika R Bérczi-Kovács, Endre Boros, Fekadu Tolessa Gedefa, Naoyuki Kamiyama, Telikepalli Kavitha, Yusuke Kobayashi, and Kazuhisa Makino. Envy-Free Relaxations for Goods, Chores, and Mixed Items. arXiv preprint arXiv:2006.04428, 2020. Google Scholar
  27. Umang Bhaskar, AR Sricharan, and Rohit Vaish. On Approximate Envy-Freeness for Indivisible Chores and Mixed Resources. arXiv preprint arXiv:2012.06788, 2021. Google Scholar
  28. Steven J Brams and Alan D Taylor. Fair Division: From Cake-Cutting to Dispute Resolution. Cambridge University Press, 1996. Google Scholar
  29. Simina Brânzei and Fedor Sandomirskiy. Algorithms for Competitive Division of Chores. arXiv preprint arXiv:1907.01766, 2019. Google Scholar
  30. Johannes Brustle, Jack Dippel, Vishnu V Narayan, Mashbat Suzuki, and Adrian Vetta. One Dollar Each Eliminates Envy. In Proceedings of the 21st ACM Conference on Economics and Computation, pages 23-39, 2020. Google Scholar
  31. Eric Budish. The Combinatorial Assignment Problem: Approximate Competitive Equilibrium from Equal Incomes. Journal of Political Economy, 119(6):1061-1103, 2011. Google Scholar
  32. Eric Budish, Gérard P Cachon, Judd B Kessler, and Abraham Othman. Course Match: A Large-Scale Implementation of Approximate Competitive Equilibrium from Equal Incomes for Combinatorial Allocation. Operations Research, 65(2):314-336, 2017. Google Scholar
  33. Ioannis Caragiannis and Stavros Ioannidis. Computing Envy-Freeable Allocations with Limited Subsidies. arXiv preprint arXiv:2002.02789, 2020. Google Scholar
  34. Ioannis Caragiannis, David Kurokawa, Hervé Moulin, Ariel D Procaccia, Nisarg Shah, and Junxing Wang. The Unreasonable Fairness of Maximum Nash Welfare. ACM Transactions on Economics and Computation, 7(3):12, 2019. Google Scholar
  35. Bhaskar Ray Chaudhury, Jugal Garg, and Ruta Mehta. Fair and Efficient Allocations under Subadditive Valuations. In The 35th AAAI Conference on Artificial Intelligence, pages 5269-5276, 2021. Google Scholar
  36. Xingyu Chen and Zijie Liu. The Fairness of Leximin in Allocation of Indivisible Chores. arXiv preprint arXiv:2005.04864, 2020. Google Scholar
  37. Yuga J Cohler, John K Lai, David C Parkes, and Ariel D Procaccia. Optimal Envy-Free Cake Cutting. In Proceedings of the 25th AAAI Conference on Artificial Intelligence, pages 626-631, 2011. Google Scholar
  38. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Third Edition. The MIT Press, 3rd edition, 2009. Google Scholar
  39. Sina Dehghani, Alireza Farhadi, MohammadTaghi HajiAghayi, and Hadi Yami. Envy-Free Chore Division For an Arbitrary Number of Agents. In Proceedings of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2564-2583. SIAM, 2018. Google Scholar
  40. Duncan Foley. Resource Allocation and the Public Sector. Yale Economic Essays, pages 45-98, 1967. Google Scholar
  41. Rupert Freeman, Nisarg Shah, and Rohit Vaish. Best of Both Worlds: Ex-Ante and Ex-Post Fairness in Resource Allocation. In Proceedings of the 21st ACM Conference on Economics and Computation, pages 21-22, 2020. Google Scholar
  42. Rupert Freeman, Sujoy Sikdar, Rohit Vaish, and Lirong Xia. Equitable Allocations of Indivisible Goods. In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pages 280-286, 2019. Google Scholar
  43. Rupert Freeman, Sujoy Sikdar, Rohit Vaish, and Lirong Xia. Equitable Allocations of Indivisible Chores. In Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems, pages 384-392, 2020. Google Scholar
  44. Martin Gardner. aha! Insight. W. H. Freeman and Company, 1978. Google Scholar
  45. Jonathan Goldman and Ariel D Procaccia. Spliddit: Unleashing Fair Division Algorithms. ACM SIGecom Exchanges, 13(2):41-46, 2015. Google Scholar
  46. Claus-Jochen Haake, Matthias G Raith, and Francis Edward Su. Bidding for Envy-Freeness: A Procedural Approach to N-Player Fair-Division Problems. Social Choice and Welfare, 19(4):723-749, 2002. Google Scholar
  47. Daniel Halpern and Nisarg Shah. Fair Division with Subsidy. In Proceedings of the 12th International Symposium on Algorithmic Game Theory, pages 374-389, 2019. Google Scholar
  48. Hadi Hosseini, Sujoy Sikdar, Rohit Vaish, Hejun Wang, and Lirong Xia. Fair division through information withholding. Proceedings of the AAAI Conference on Artificial Intelligence, 34(02):2014-2021, April 2020. URL: https://doi.org/10.1609/aaai.v34i02.5573.
  49. Xin Huang and Pinyan Lu. An Algorithmic Framework for Approximating Maximin Share Allocation of Chores. In The 22nd ACM Conference on Economics and Computation (forthcoming), 2021. Google Scholar
  50. Flip Klijn. An Algorithm for Envy-Free Allocations in an Economy with Indivisible Objects and Money. Social Choice and Welfare, 17(2):201-215, 2000. Google Scholar
  51. Rucha Kulkarni, Ruta Mehta, and Setareh Taki. Approximating Maximin Shares with Mixed Manna. In The 22nd ACM Conference on Economics and Computation (forthcoming), 2021. Google Scholar
  52. David Kurokawa, John K Lai, and Ariel D Procaccia. How to Cut a Cake Before the Party Ends. In Proceedings of the 27th AAAI Conference on Artificial Intelligence, pages 555-561, 2013. Google Scholar
  53. Richard J Lipton, Evangelos Markakis, Elchanan Mossel, and Amin Saberi. On Approximately Fair Allocations of Indivisible Goods. In Proceedings of the 5th ACM Conference on Electronic Commerce, pages 125-131, 2004. Google Scholar
  54. Eric S Maskin. On the Fair Allocation of Indivisible Goods. In Arrow and the Foundations of the Theory of Economic Policy, pages 341-349. Palgrave Macmillan UK, 1987. Google Scholar
  55. Marc Meertens, Jos Potters, and Hans Reijnierse. Envy-Free and Pareto Efficient Allocations in Economies with Indivisible Goods and Money. Mathematical Social Sciences, 44(3):223-233, 2002. Google Scholar
  56. Frédéric Meunier and Shira Zerbib. Envy-Free Cake Division Without Assuming the Players Prefer Nonempty Pieces. Israel Journal of Mathematics, 234(2):907-925, 2019. Google Scholar
  57. Abraham Othman, Tuomas Sandholm, and Eric Budish. Finding Approximate Competitive Equilibria: Efficient and Fair Course Allocation. In Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems, pages 873-880, 2010. Google Scholar
  58. Parag A Pathak, Tayfun Sönmez, M Utku Ünver, and M Bumin Yenmez. Fair Allocation of Vaccines, Ventilators and Antiviral Treatments: Leaving No Ethical Value Behind in Health Care Rationing. arXiv preprint arXiv:2008.00374, 2020. Google Scholar
  59. Elisha Peterson and Francis Edward Su. N-Person Envy-Free Chore Division. arXiv preprint arXiv:0909.0303, 2009. Google Scholar
  60. Ariel D Procaccia. Cake Cutting Algorithms. In Handbook of Computational Social Choice, Chapter 13. Citeseer, 2015. Google Scholar
  61. Jack Robertson and William Webb. Cake-Cutting Algorithms: Be Fair If You Can. CRC Press, 1998. Google Scholar
  62. Erel Segal-Halevi. Fairly Dividing a Cake after Some Parts were Burnt in the Oven. In Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems, pages 1276-1284, 2018. Google Scholar
  63. Erel Segal-Halevi. Competitive Equilibrium for Almost All Incomes: Existence and Fairness. Autonomous Agents and Multi-Agent Systems, 34(1):1-50, 2020. Google Scholar
  64. Lloyd Shapley and Herbert Scarf. On Cores and Indivisibility. Journal of Mathematical Economics, 1(1):23-37, 1974. Google Scholar
  65. Walter Stromquist. How to Cut a Cake Fairly. The American Mathematical Monthly, 87(8):640-644, 1980. Google Scholar
  66. Francis Edward Su. Rental Harmony: Sperner’s Lemma in Fair Division. The American Mathematical Monthly, 106(10):930-942, 1999. Google Scholar
  67. Martino Traxler. Fair Chore Division for Climate Change. Social Theory and Practice, 28(1):101-134, 2002. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact