Abstract
We analyse the problem of finding an allocation of resources in a multiagent system that is as fair as possible in terms of minimising inequality between the utility levels enjoyed by the individual agents. We use the well-known Atkinson index to measure inequality and we focus on the distributed approach to multiagent resource allocation, where new allocations emerge as the result of a sequence of local deals between groups of agents who agree on an exchange of some of the items in their possession. Our results show that it is possible to design systems that provide theoretical guarantees for optimal outcomes that minimise inequality, but also that there are significant computational hurdles to be overcome in the worst case. In particular, finding an optimal allocation is computationally intractable and under the distributed approach a large number of structurally complex deals, possibly involving many agents and items, may be required before convergence to a socially optimal allocation. This remains true even in severely restricted resource allocation scenarios where all agents have the same utility function. From a methodological point of view, while much work in multiagent resource allocation relies on combinatorial arguments, here we instead use insights from basic calculus.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Allison, P.D.: Measures of inequality. Am. Sociol. Rev. 43(6), 865–880 (1978)
Atkinson, A.B.: On the measurement of inequality. J. Econ. Theory 2, 244–263 (1970)
Atkinson, A.B.: Inequality Harvard University Press (2015)
Bell, E.T.: Exponential numbers. Am. Math. Mon. 41(7), 411–419 (1934)
Bertsimas, D., Farias, V.F., Trichakis, N.: The price of fairness. Oper. Res. 59(1), 17–31 (2011)
Bouveret, S., Chevaleyre, Y., Maudet, N.: Fair allocation of indivisible goods. In: F. Brandt, V. Conitzer, U. Endriss, J. Lang, and A. D. Procaccia, editors, Handbook of Computational Social Choice, chapter 12. Cambridge University Press (2016)
Bouveret, S., Lemaître, M.: Computing leximin-optimal solutions in constraint networks. Artif. Intell. 173(2), 343–364 (2009)
Caragiannis, I., Kaklamanis, C., Kanellopoulos, P., Kyropoulou, M.: The efficiency of fair division. Theory Comput. Syst. 50(4), 589–610 (2012)
Caragiannis, I., Kurokawa, D., Moulin, H., Procaccia, A.D., Shah, N., Wang, J.: The unreasonable fairness of maximum Nash welfare. In: Proceedings of the 17th ACM Conference on Economics and Computation (EC-2016), pp. 305–322 ACM (2016)
Cauchy, A.L.: Cours d’analyse. OEuvres Completes Bd 3 (1821)
Chevaleyre, Y., Dunne, P.E., Endriss, U., Lang, J., Lemaître, M., Maudet, N., Padget, J., Phelps, S., Rodríguez-Aguilar, J.A., Sousa, P.: Issues in multiagent resource allocation. Informatica 30, 3–31 (2006)
Chevaleyre, Y., Endriss, U., Maudet, N.: Distributed fair allocation of indivisible goods. Artif. Intell. 242, 1–22 (2017)
Dalton, H.: The measurement of the inequality of incomes. Econ. J. 30(119), 348–361 (1920)
Dunne, P.E., Wooldridge, M., Laurence, M.: The complexity of contract negotiation. Artif. Intell. 164(1–2), 23–46 (2005)
Endriss, U.: Reduction of economic inequality in combinatorial domains. In: Proceedings of the 12th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-2013), pp. 175–182 IFAAMAS (2013)
Endriss, U., Maudet, N., Sadri, F., Toni, F.: Negotiating socially optimal allocations of resources. J. Artif. Intell. Res. (JAIR) 25, 315–348 (2006)
Freeman, R., Sikdar, S., Vaish, R., Xia, L.: Equitable allocations of indivisible goods. In: S. Kraus, editor Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI-2019), pp. 280–286. IJCAI (2019)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, New York (1979)
Gemici, K., Koutsoupias, E., Monnot, B., Papadimitriou, C.H., Piliouras, G.: Wealth inequality and the price of anarchy. In: Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science (STACS-2019) (2019)
Gini, C.: Variabilitá e Mutabilitá. C. Cuppini, Bologna (1912)
Gourvès, L., Monnot, J., Tlilane, L.: Near fairness in matroids. In: T. Schaub, G. Friedrich, and B. O’Sullivan, editors, Proceedings of the 21st European Conference on Artificial Intelligence (ECAI-2014), vol. 263 of Frontiers in Artificial Intelligence and Applications, pp. 393–398. IOS Press (2014)
Huhns, M.N., Malhotra, A.K.: Negotiating for goods and services. IEEE Internet Comput. 3(4), 97 (1999)
Knuth, D.E.: The Art of Computer Programming, vol. 1: Fundamental Algorithms, 3rd Edition. Addison-wesley Professional, 3 edition 7 (1997)
Kondor, Y.: An old-new measure of income inequality. Econometrica 39(6), 1041–42 (1971)
Lesca, J., Perny, P.: LP Solvable models for multiagent fair allocation problems. In: Proceedings of the 19th European Conference on Artificial Intelligence (ECAI-2010), pp 393–398 (2010)
Moulin, H.: Axioms of cooperative decision making Cambridge University Press (1988)
Nash Jr, J.F.: The bargaining problem. Econometrica 18(2), 155–162 (1950)
Ramezani, S., Endriss, U.: Nash social welfare in multiagent resource allocation InAgent-Mediated Electronic commerce: Designing Trading Strategies and Mechanisms for Electronic Markets, vol 59 of Lecture Notes in Business Information Processing, pp. 117–131 Springer-Verlag (2010)
Rennie, B.C., Dobson, A.J.: On Stirling numbers of the second kind. J. Comb. Theory 7(2), 116–121 (1969)
Rosenschein, J.S., Zlotkin, G.: Rules of encounter: designing conventions for automated negotiation among computers MIT press (1994)
Sandholm, T.W.: Contract types for satisficing task allocation: I Theoretical results Inproceedings of the 1998 AAAI Spring Symposium on Satisficing Models (1998)
Sandholm, T.W.: Distributed rational decision making. In: G. Weiss, editor, Multiagent Systems: A Modern Approach to Distributed Artificial Intelligence, pp. 201–258. MIT Press (1999)
Schneckenburger, S., Dorn, B., Endriss, U.: The Atkinson inequality index in multiagent resource allocation. In: Proceedings of the 16th International Conference on Autonomous Agents and Multiagent Systems (AAMAS-2017) IFAAMAS (2017)
Sen, A.: On economic inequality Oxford University Press (1973)
Theil, H.: The information approach to demand analysis. Econometrica 33(1), 67–87 (1965)
Vazirani, V.V.: Approximation algorithms Springer-Verlag (2001)
Acknowledgements
We thank our anonymous reviewers for their careful reading of the manuscript and their valuable feedback. This work was partly supported by COST Action IC1205 on Computational Social Choice.
Funding
Open Access funding enabled and organized by Projekt DEAL. This work was partly supported by COST Action IC1205 on Computational Social Choice.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher’s note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Financial/Non-financial interests
The authors have no competing interests to declare that are relevant to the content of this article.
An early version of this paper appears in the proceedings of the 16th International Conference on Autonomous Agents and Multiagent Systems [33].
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
About this article
Cite this article
Schneckenburger, S., Dorn, B. & Endriss, U. Minimising inequality in multiagent resource allocation. Ann Math Artif Intell 90, 339–371 (2022). https://doi.org/10.1007/s10472-022-09789-z
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10472-022-09789-z