{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T07:44:51Z","timestamp":1740123891741,"version":"3.37.3"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2022,3,23]],"date-time":"2022-03-23T00:00:00Z","timestamp":1647993600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,3,23]],"date-time":"2022-03-23T00:00:00Z","timestamp":1647993600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100000921","name":"European Cooperation in Science and Technology","doi-asserted-by":"publisher","award":["COST Action IC1025"],"award-info":[{"award-number":["COST Action IC1025"]}],"id":[{"id":"10.13039\/501100000921","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002345","name":"Eberhard Karls Universit\u00e4t T\u00fcbingen","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100002345","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Ann Math Artif Intell"],"published-print":{"date-parts":[[2022,4]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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.<\/jats:p>","DOI":"10.1007\/s10472-022-09789-z","type":"journal-article","created":{"date-parts":[[2022,3,23]],"date-time":"2022-03-23T03:38:30Z","timestamp":1648006710000},"page":"339-371","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Minimising inequality in multiagent resource allocation"],"prefix":"10.1007","volume":"90","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-7327-0680","authenticated-orcid":false,"given":"Sebastian","family":"Schneckenburger","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Britta","family":"Dorn","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ulle","family":"Endriss","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,3,23]]},"reference":[{"issue":"6","key":"9789_CR1","doi-asserted-by":"publisher","first-page":"865","DOI":"10.2307\/2094626","volume":"43","author":"PD Allison","year":"1978","unstructured":"Allison, P.D.: Measures of inequality. Am. Sociol. Rev. 43(6), 865\u2013880 (1978)","journal-title":"Am. Sociol. Rev."},{"key":"9789_CR2","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1016\/0022-0531(70)90039-6","volume":"2","author":"AB Atkinson","year":"1970","unstructured":"Atkinson, A.B.: On the measurement of inequality. J. Econ. Theory 2, 244\u2013263 (1970)","journal-title":"J. Econ. Theory"},{"key":"9789_CR3","doi-asserted-by":"crossref","unstructured":"Atkinson, A.B.: Inequality Harvard University Press (2015)","DOI":"10.4159\/9780674287013"},{"issue":"7","key":"9789_CR4","doi-asserted-by":"publisher","first-page":"411","DOI":"10.1080\/00029890.1934.11987615","volume":"41","author":"ET Bell","year":"1934","unstructured":"Bell, E.T.: Exponential numbers. Am. Math. Mon. 41(7), 411\u2013419 (1934)","journal-title":"Am. Math. Mon."},{"issue":"1","key":"9789_CR5","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1287\/opre.1100.0865","volume":"59","author":"D Bertsimas","year":"2011","unstructured":"Bertsimas, D., Farias, V.F., Trichakis, N.: The price of fairness. Oper. Res. 59(1), 17\u201331 (2011)","journal-title":"Oper. Res."},{"key":"9789_CR6","doi-asserted-by":"crossref","unstructured":"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)","DOI":"10.1017\/CBO9781107446984.013"},{"issue":"2","key":"9789_CR7","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1016\/j.artint.2008.10.010","volume":"173","author":"S Bouveret","year":"2009","unstructured":"Bouveret, S., Lema\u00eetre, M.: Computing leximin-optimal solutions in constraint networks. Artif. Intell. 173(2), 343\u2013364 (2009)","journal-title":"Artif. Intell."},{"issue":"4","key":"9789_CR8","doi-asserted-by":"publisher","first-page":"589","DOI":"10.1007\/s00224-011-9359-y","volume":"50","author":"I Caragiannis","year":"2012","unstructured":"Caragiannis, I., Kaklamanis, C., Kanellopoulos, P., Kyropoulou, M.: The efficiency of fair division. Theory Comput. Syst. 50(4), 589\u2013610 (2012)","journal-title":"Theory Comput. Syst."},{"key":"9789_CR9","doi-asserted-by":"crossref","unstructured":"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\u2013322 ACM (2016)","DOI":"10.1145\/2940716.2940726"},{"key":"9789_CR10","unstructured":"Cauchy, A.L.: Cours d\u2019analyse. OEuvres Completes Bd 3 (1821)"},{"key":"9789_CR11","first-page":"3","volume":"30","author":"Y Chevaleyre","year":"2006","unstructured":"Chevaleyre, Y., Dunne, P.E., Endriss, U., Lang, J., Lema\u00eetre, M., Maudet, N., Padget, J., Phelps, S., Rodr\u00edguez-Aguilar, J.A., Sousa, P.: Issues in multiagent resource allocation. Informatica 30, 3\u201331 (2006)","journal-title":"Informatica"},{"key":"9789_CR12","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.artint.2016.09.005","volume":"242","author":"Y Chevaleyre","year":"2017","unstructured":"Chevaleyre, Y., Endriss, U., Maudet, N.: Distributed fair allocation of indivisible goods. Artif. Intell. 242, 1\u201322 (2017)","journal-title":"Artif. Intell."},{"issue":"119","key":"9789_CR13","doi-asserted-by":"publisher","first-page":"348","DOI":"10.2307\/2223525","volume":"30","author":"H Dalton","year":"1920","unstructured":"Dalton, H.: The measurement of the inequality of incomes. Econ. J. 30(119), 348\u2013361 (1920)","journal-title":"Econ. J."},{"issue":"1\u20132","key":"9789_CR14","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/j.artint.2005.01.006","volume":"164","author":"PE Dunne","year":"2005","unstructured":"Dunne, P.E., Wooldridge, M., Laurence, M.: The complexity of contract negotiation. Artif. Intell. 164(1\u20132), 23\u201346 (2005)","journal-title":"Artif. Intell."},{"key":"9789_CR15","unstructured":"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\u2013182 IFAAMAS (2013)"},{"key":"9789_CR16","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1613\/jair.1870","volume":"25","author":"U Endriss","year":"2006","unstructured":"Endriss, U., Maudet, N., Sadri, F., Toni, F.: Negotiating socially optimal allocations of resources. J. Artif. Intell. Res. (JAIR) 25, 315\u2013348 (2006)","journal-title":"J. Artif. Intell. Res. (JAIR)"},{"key":"9789_CR17","doi-asserted-by":"crossref","unstructured":"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\u2013286. IJCAI (2019)","DOI":"10.24963\/ijcai.2019\/40"},{"key":"9789_CR18","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"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)"},{"key":"9789_CR19","unstructured":"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)"},{"key":"9789_CR20","unstructured":"Gini, C.: Variabilit\u00e1 e Mutabilit\u00e1. C. Cuppini, Bologna (1912)"},{"key":"9789_CR21","unstructured":"Gourv\u00e8s, L., Monnot, J., Tlilane, L.: Near fairness in matroids. In: T. Schaub, G. Friedrich, and B. O\u2019Sullivan, editors, Proceedings of the 21st European Conference on Artificial Intelligence (ECAI-2014), vol. 263 of Frontiers in Artificial Intelligence and Applications, pp. 393\u2013398. IOS Press (2014)"},{"issue":"4","key":"9789_CR22","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1109\/4236.780967","volume":"3","author":"MN Huhns","year":"1999","unstructured":"Huhns, M.N., Malhotra, A.K.: Negotiating for goods and services. IEEE Internet Comput. 3(4), 97 (1999)","journal-title":"IEEE Internet Comput."},{"key":"9789_CR23","unstructured":"Knuth, D.E.: The Art of Computer Programming, vol. 1: Fundamental Algorithms, 3rd Edition. Addison-wesley Professional, 3 edition 7 (1997)"},{"issue":"6","key":"9789_CR24","doi-asserted-by":"publisher","first-page":"1041","DOI":"10.2307\/1909676","volume":"39","author":"Y Kondor","year":"1971","unstructured":"Kondor, Y.: An old-new measure of income inequality. Econometrica 39(6), 1041\u201342 (1971)","journal-title":"Econometrica"},{"key":"9789_CR25","unstructured":"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\u2013398 (2010)"},{"key":"9789_CR26","doi-asserted-by":"crossref","unstructured":"Moulin, H.: Axioms of cooperative decision making Cambridge University Press (1988)","DOI":"10.1017\/CCOL0521360552"},{"issue":"2","key":"9789_CR27","doi-asserted-by":"publisher","first-page":"155","DOI":"10.2307\/1907266","volume":"18","author":"JF Nash Jr","year":"1950","unstructured":"Nash Jr, J.F.: The bargaining problem. Econometrica 18(2), 155\u2013162 (1950)","journal-title":"Econometrica"},{"key":"9789_CR28","doi-asserted-by":"crossref","unstructured":"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\u2013131 Springer-Verlag (2010)","DOI":"10.1007\/978-3-642-15117-0_9"},{"issue":"2","key":"9789_CR29","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1016\/S0021-9800(69)80045-1","volume":"7","author":"BC Rennie","year":"1969","unstructured":"Rennie, B.C., Dobson, A.J.: On Stirling numbers of the second kind. J. Comb. Theory 7(2), 116\u2013121 (1969)","journal-title":"J. Comb. Theory"},{"key":"9789_CR30","unstructured":"Rosenschein, J.S., Zlotkin, G.: Rules of encounter: designing conventions for automated negotiation among computers MIT press (1994)"},{"key":"9789_CR31","unstructured":"Sandholm, T.W.: Contract types for satisficing task allocation: I Theoretical results Inproceedings of the 1998 AAAI Spring Symposium on Satisficing Models (1998)"},{"key":"9789_CR32","unstructured":"Sandholm, T.W.: Distributed rational decision making. In: G. Weiss, editor, Multiagent Systems: A Modern Approach to Distributed Artificial Intelligence, pp. 201\u2013258. MIT Press (1999)"},{"key":"9789_CR33","unstructured":"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)"},{"key":"9789_CR34","doi-asserted-by":"crossref","unstructured":"Sen, A.: On economic inequality Oxford University Press (1973)","DOI":"10.1093\/0198281935.001.0001"},{"issue":"1","key":"9789_CR35","doi-asserted-by":"publisher","first-page":"67","DOI":"10.2307\/1911889","volume":"33","author":"H Theil","year":"1965","unstructured":"Theil, H.: The information approach to demand analysis. Econometrica 33(1), 67\u201387 (1965)","journal-title":"Econometrica"},{"key":"9789_CR36","unstructured":"Vazirani, V.V.: Approximation algorithms Springer-Verlag (2001)"}],"container-title":["Annals of Mathematics and Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-022-09789-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10472-022-09789-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10472-022-09789-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,1,29]],"date-time":"2023-01-29T20:23:45Z","timestamp":1675023825000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10472-022-09789-z"}},"subtitle":["Structural analysis of a distributed approach"],"short-title":[],"issued":{"date-parts":[[2022,3,23]]},"references-count":36,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2022,4]]}},"alternative-id":["9789"],"URL":"https:\/\/doi.org\/10.1007\/s10472-022-09789-z","relation":{},"ISSN":["1012-2443","1573-7470"],"issn-type":[{"type":"print","value":"1012-2443"},{"type":"electronic","value":"1573-7470"}],"subject":[],"published":{"date-parts":[[2022,3,23]]},"assertion":[{"value":"16 February 2022","order":1,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"23 March 2022","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}