Fair allocation of indivisible goods and chores | Autonomous Agents and Multi-Agent Systems Skip to main content
Springer Nature Link
Log in

Fair allocation of indivisible goods and chores

  • Published:
Autonomous Agents and Multi-Agent Systems Aims and scope Submit manuscript

Abstract

We consider the problem of fairly dividing a set of indivisible items. Much of the fair division literature assumes that the items are “goods” that yield positive utility for the agents. There is also some work in which the items are “chores” that yield negative utility for the agents. In this paper, we consider a more general scenario in which an agent may have positive or negative utility for each item. This framework captures, e.g., fair task assignment, where agents can experience both positive and negative utility for each task. We demonstrate that whereas some of the positive axiomatic and computational results extend to this more general setting, others do not. We present several new and efficient algorithms for finding fair allocations in this general setting. We also point out several gaps in the literature regarding the existence of allocations that satisfy certain fairness and efficiency properties and examine the complexity of computing such allocations.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2

Similar content being viewed by others

Explore related subjects

Discover the latest articles, news and stories from top researchers in related subjects.

Notes

  1. A moving-knife procedure for computing a proportional allocation for a cake is known as the Dubins-Spanier moving-knife procedure [22].

References

  1. Aleksandrov, M., & Walsh, T. (2020). Two algorithms for additive and fair division of mixed manna. In KI 2020: Advances in artificial intelligence—43rd German conference on AI, Proceedings, Bamberg, Germany, September 21-25, 2020 (pp. 3–17).

  2. Amanatidis, G., Birmpas, G., Christodoulou, G., & Markakis, E. (2017). Truthful allocation mechanisms without payments: characterization and implications on fairness. In Proceedings of the 18th ACM conference on economics and computation (EC).

  3. Amanatidis, G., Markakis, E., Nikzad, A., & Saberi, A. (2017). Approximation algorithms for computing maximin share allocations. ACM Transactions on Algorithms, 13(4), 52:1-52:28.

    Article  MathSciNet  Google Scholar 

  4. Aziz, H. (2016). Computational social choice: Some current and new directions. In Proceedings of the 25th international joint conference on artificial intelligence (IJCAI) (pp. 4054–4057).

  5. Aziz, H., & Rey, S. (2020). Almost group envy-free allocation of indivisible goods and chores. In Proceedings of the 29th international joint conference on artificial intelligence (IJCAI) (pp. 39–45).

  6. Aziz, H., Biro, P., Lang, J., Lesca, J., & Monnot, J. (2016). Optimal reallocation under additive and ordinal preferences. In Proceedings of the 15th international conference on autonomous agents and multiagent systems (AAMAS) (pp. 402–410).

  7. Aziz, H., Rauchecker, G., Schryen, G., & Walsh, T. (2017). Algorithms for max-min share fair allocation of indivisible chores. In Proceedings of the 31st AAAI conference on artificial intelligence (AAAI) (pp. 335–341).

  8. Aziz, H., Caragiannis, I., Igarashi, A., & Walsh, T. (2019). Fair allocation of indivisible goods and chores. In Proceedings of the 28th international joint conference on artificial intelligence (IJCAI) (pp. 53–59).

  9. Aziz, H., Moulin, H., & Sandomirskiy, F. (2020). A polynomial-time algorithm for computing a Pareto optimal and almost proportional allocation. Operations Research Letters, 48(5), 573–578.

    Article  MathSciNet  Google Scholar 

  10. Barman, S., & Krishnamurthy, S. K. (2020). Approximation algorithms for maximin fair division. ACM Transactions on Economics and Computation, 8(1), 5:1-5:28.

    Article  MathSciNet  Google Scholar 

  11. Barman, S., Kumar Krishna Murthy, S., & Vaish, R. (2018). Finding fair and efficient allocations. In Proceedings of the 19th ACM conference on economics and computation (EC) (pp. 557–574).

  12. Bérczi, K., Bérczi-Kovács, E. R., Boros, E., Gedefa, F. T., Kamiyama, N., Kavitha, T., Kobayashi, Y., & Makino, K. (2020). Envy-free relaxations for goods, chores, and mixed items. CoRR arXiv:abs/2006.04428.

  13. Bhaskar, U., Sricharan, A. R., & Vaish, R. (2020). On approximate envy-freeness for indivisible chores and mixed resources. CoRRarXiv:abs/2012.06788.

  14. Bilò, V., Caragiannis, I., Flammini, M., Igarashi, A., Monaco, G., Peters, D., Vinci, C., & Zwicker, W. S. (2019). Almost envy-free allocations with connected bundles. In Proceedings of the 10th innovations in theoretical computer science conference (ITCS) (pp. 14:1–14:21).

  15. Bogomolnaia, A., Moulin, H., Sandomirskyi, F., & Yanovskaya, E. (2017). Competitive division of a mixed manna. Econometrica, 85(6), 1847–1871.

    Article  MathSciNet  Google Scholar 

  16. Bogomolnaia, A., Moulin, H., Sandomirskyi, F., & Yanovskaya, E. (2019). Dividing goods and bads under additive utilities. Social Choice and Welfare, 52, 395–417.

    Article  MathSciNet  Google Scholar 

  17. Bouveret, S., & Lang, J. (2008). Efficiency and envy-freeness in fair division of indivisible goods: Logical representation and complexity. Journal of Artificial Intelligence Research, 32, 525–564.

    Article  MathSciNet  Google Scholar 

  18. Bouveret, S., & Lang, J. (2011). A general elicitation-free protocol for allocating indivisible goods. In Proceedings of the 22nd international joint conference on artificial intelligence (IJCAI) (pp. 73–78). AAAI Press.

  19. Bouveret, S., Chevaleyre, Y., & Maudet, N. (2016). Chapter 12: Fair allocation of indivisible goods. In F. Brandt, V. Conitzer, U. Endriss, J. Lang, & A. D. Procaccia (Eds.), Handbook of computational social choice (pp. 284–310). Cambridge University Press.

    Chapter  Google Scholar 

  20. Bouveret, S., Cechlárová, K., Elkind, E., Igarashi, A., & Peters, D. (2017). Fair division of a graph. In Proceedings of the 26th international joint conference on artificial intelligence (IJCAI) (pp. 135–141).

  21. Brams, S. J., & Fishburn, P. C. (2000). Fair division of indivisible items between two people with identical preferences: Envy-freeness, Pareto-optimality, and equity. Social Choice and Welfare, 17(2), 247–267.

    Article  MathSciNet  Google Scholar 

  22. Brams, S. J., & Taylor, A. D. (1996). Fair division: From cake-cutting to dispute resolution. Cambridge University Press.

    Book  Google Scholar 

  23. Brams, S. J., & Taylor, A. D. (1996). A procedure for divorce settlements. Issue Mediation Quarterly Mediation Quarterly, 13(3), 191–205.

    Google Scholar 

  24. Brams, S. J., & Taylor, A. D. (1996). A procedure for divorce settlements. Mediation Quarterly, 13(3), 191–205.

    Article  Google Scholar 

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

    Article  Google Scholar 

  26. Caragiannis, I., Kaklamanis, C., Kanellopoulos, P., & Kyropoulou, M. (2012). The efficiency of fair division. Theory of Computing Systems, 50(4), 589–610.

    Article  MathSciNet  Google Scholar 

  27. Caragiannis, I., Kurokawa, D., Moulin, H., Procaccia, A. D., Shah, N., & Wang, J. (2016). The unreasonable fairness of maximum Nash welfare. In Proceedings of the 17th ACM conference on economics and computation (EC) (pp. 305–322). ACM Press.

  28. Caragiannis, I., Kurokawa, D., Moulin, H., Procaccia, A. D., Shah, N., & Wang, J. (2019). The unreasonable fairness of maximum Nash welfare. ACM Transactions on Economics and Computation, 7(3), 12:1-12:32.

    Article  MathSciNet  Google Scholar 

  29. Chaudhury, B. R., Garg, J., & Mehlhorn, K. (2020). EFX exists for three agents. In Proceedings of the 21st ACM conference on economics and computation (EC) (pp. 1—19).

  30. Chaudhury, B. R., Garg, J., McGlaughlin, P., & Mehta, R. (2021). Competitive allocation of a mixed manna. In Proceedings of the 32nd annual ACM-SIAM symposium on discrete algorithms (SODA).

  31. Conitzer, V., Freeman, R., & Shah, N. (2017). Fair public decision making. In Proceedings of the 18th ACM conference on economics and computation (EC) (pp. 629–646).

  32. de Keijzer, B., Bouveret, S., Klos, T., & Zhang, Y. (2009). On the complexity of efficiency and envy-freeness in fair division of indivisible goods with additive preferences. In Proceedings of the 1st international conference on algorithmic decision theory (pp. 98–110).

  33. Eisenberg, E., & Gale, D. (1959). Consensus of subjective probabilities: The pari-mutuel method. The Annals of Mathematical Statistics, 30(1), 165–168.

    Article  MathSciNet  Google Scholar 

  34. Foley, D. K. (1967). Resource allocation and the public sector. Yale Economic Essays, 7, 45–98.

    Google Scholar 

  35. Garg, J., & McGlaughlin, P. (2020). Computing competitive equilibria with mixed manna. In Proceedings of the 19th international conference on autonomous agents and multiagent systems (AAMAS) (pp. 420–428).

  36. Ghodsi, M., HajiAghayi, M., Seddighin, M., Seddighin, S., & Yami, H. (2018). Fair allocation of indivisible goods: Improvements and generalizations. In Proceedings of the 19th ACM Conference on Economics and Computation (EC) (pp. 539–556).

  37. Kurokawa, D., Procaccia, A. D., & Wang, J. (2018). Fair enough: Guaranteeing approximate maximin shares. Journal of the ACM, 65(2), 8:1-8:27.

    Article  MathSciNet  Google Scholar 

  38. Lipton, R. J., Markakis, E., Mossel, E., & Saberi, A. (2004). On approximately fair allocations of indivisible goods. In Proceedings of the 5th ACM conference on electronic commerce (EC) (pp. 125–131).

  39. Meunier, F., & Zerbib, S. (2019). Envy-free cake division without assuming the players prefer nonempty pieces. Israel Journal of Mathematics, 234, 907–925.

    Article  MathSciNet  Google Scholar 

  40. Moulin, H. (2019). Fair division in the internet age. Annual Review of Economics, 11, 1–37.

    Article  Google Scholar 

  41. Plaut, B., & Roughgarden, T. (2018). Almost envy-freeness with general valuations. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, 2018 (pp. 2584–2603).

  42. Robertson, J. M., & Webb, W. A. (1998). Cake cutting algorithms: Be fair if you can. A. K. Peters.

    Book  Google Scholar 

  43. Segal-Halevi, E. (2018). 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 (AAMAS) (pp. 1276–1284).

  44. Steinhaus, H. (1949). The problem of fair division. Econometrica, 17, 315–319.

    Article  MathSciNet  Google Scholar 

  45. Stromquist, W. (1980). How to cut a cake fairly. The American Mathematical Monthly, 87(8), 640–644.

    Article  MathSciNet  Google Scholar 

  46. Su, F. E. (1999). Rental harmony: Sperner’s lemma in fair division. The American Mathematical Monthly, 106(10), 930–942.

    Article  MathSciNet  Google Scholar 

  47. Varian, H. R. (1974). Equity, envy, and efficiency. Journal of Economic Theory, 9(1), 63–91.

    Article  MathSciNet  Google Scholar 

  48. Woodall, D. R. (1980). Dividing a cake fairly. Journal of Mathematical Analysis and Applications, 78(1), 233–247.

    Article  MathSciNet  Google Scholar 

Download references

Acknowledgements

We would like to thank Bérczi et al. [12] and Bhaskar et al. [13] for pointing out an error in the IJCAI version [8]. We thank the IJCAI 2019 reviewers and Warut Suksompong for helpful feedback. Ayumi Igarashi is supported by the KAKENHI Grant-in-Aid for JSPS Fellows number 18J00997 and JST, PRESTO number JPMJPR20C1. Toby Walsh is funded by the European Research Council under the Horizon 2020 Programme via AMPLify 670077.

Author information

Authors and Affiliations

  1. UNSW Sydney and Data61 CSIRO, Sydney, Australia

    Haris Aziz & Toby Walsh

  2. Aarhus University, Aarhus, Denmark

    Ioannis Caragiannis

  3. National Institute of Informatics, Chiyoda City, Japan

    Ayumi Igarashi

Authors
  1. Haris Aziz
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Ioannis Caragiannis
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Ayumi Igarashi
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Toby Walsh
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Ayumi Igarashi.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Aziz, H., Caragiannis, I., Igarashi, A. et al. Fair allocation of indivisible goods and chores. Auton Agent Multi-Agent Syst 36, 3 (2022). https://doi.org/10.1007/s10458-021-09532-8

Download citation

  • Accepted:

  • Published:

  • DOI: https://doi.org/10.1007/s10458-021-09532-8

Search

Navigation