Abstract
We study a framework for multiagent resource allocation where autonomous software agents negotiate over the allocation of bundles of indivisible resources. Connections to well-known combinatorial optimisation problems, including the winner determination problem in combinatorial auctions, shed light on the computational complexity of the framework. We give particular consideration to scenarios where the preferences of agents are modelled in terms of k-additive utility functions, i.e. scenarios where synergies between different resources are restricted to bundles of at most k items.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Arrow, K. J., Sen, A. K., & Suzumura, K. (Eds.) (2002). Handbook of social choice and welfare (Vol. 1), Amsterdam: North-Holland.
Ausiello, G., Crescenzi, P., Gambosi, G., Kann, V., Marchetti-Spaccamela, A., & Protasi, M. (1999). Complexity and approximation: combinatorial optimization problems and their approximability properties. Berlin: Springer.
Boros, E., & Hammer, P. L. (2002). Pseudo-boolean optimization. Discrete Applied Mathematics, 123(1–3), 155–225.
Boutilier, C., Brafman, R. I., Geib, C., & Poole, D. (1997). A constraint-based approach to preference elicitation and decision making. In Proc. AAAI spring symposium on qualitative decision theory.
Bouveret, S., & Lang, J. (2005). Efficiency and envy-freeness in fair division of indivisible goods: logical representation and complexity. In Proc. 19th international joint conference on artificial intelligence (IJCAI-2005). San Mateo: Morgan Kaufmann.
Brams, S. J., & Taylor, A. D. (1996). Fair division: from cake-cutting to dispute resolution. Cambridge: Cambridge University Press.
Chevaleyre, Y., Endriss, U., Estivie, S., & Maudet, N. (2004). Multiagent resource allocation with k-additive utility functions. In Proc. DIMACS-LAMSADE workshop on computer science and decision theory. Annales du LAMSADE 3.
Chevaleyre, Y., Endriss, U., Lang, J., & Maudet, N. (2005). Negotiating over small bundles of resources. In Proc. 4th international joint conference on autonomous agents and multiagent systems (AAMAS-2005). New York: ACM Press.
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. (2006). Issues in multiagent resource allocation. Informatica, 30, 3–31.
Conitzer, V., Sandholm, T. W., & Santi, P. (2005). Combinatorial auctions with k-wise dependent valuations. In Proc. 20th national conference on artificial intelligence (AAAI-05). Menlo Park: AAAI Press.
Coste-Marquis, S., Lang, J., Liberatore, P., & Marquis, P. (2004). Expressive power and succinctness of propositional languages for preference representation. In Proc. of the 9th international conference on principles of knowledge representation and reasoning (KR-2004). Menlo Park: AAAI Press.
Cramton, P., Shoham, Y., & Steinberg, R. (Eds.) (2006). Combinatorial auctions. Cambridge: MIT Press.
Dunne, P. E., Wooldridge, M., & Laurence, M. (2005). The complexity of contract negotiation. Artificial Intelligence, 164(1–2), 23–46.
Endriss, U., & Maudet, N. (2005). On the communication complexity of multilateral trading: extended report. Journal of Autonomous Agents and Multiagent Systems, 11(1), 91–107.
Endriss, U., Maudet, N., Sadri, F., & Toni, F. (2006). Negotiating socially optimal allocations of resources. Journal of Artificial Intelligence Research, 25, 315–348.
Fargier, H., Lang, J., Lemaître, M., & Verfaillie, G. (2004). Partage équitable de ressources communes: (2) Éléments de complexité et d’algorithmique. Technique et Science Informatique, 23(9), 1219–1238.
Fishburn, P. C. (1970). Utility theory for decision making. New York: Wiley.
Fujishima, Y., Leyton-Brown, K., & Shoham, Y. (1999). Taming the computational complexity of combinatorial auctions: optimal and approximate approaches. In Proc. 16th international joint conference on artificial intelligence (IJCAI-1999). San Mateo: Morgan Kaufman.
Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: a guide to the theory of NP-completeness. New York: Freeman.
Gonzales, C., & Perny, P. (2004). GAI networks for utility elicitation. In Proc. of the 9th international conference on principles of knowledge representation and reasoning (KR-2004). Menlo Park: AAAI Press.
Grabisch, M. (1997). k-order additive discrete fuzzy measures and their representation. Fuzzy Sets and Systems, 92, 167–189.
Keeney, R. L., & Raiffa, H. (1993). Decisions with multiple objectives: preferences and value trade-offs. Cambridge: Cambridge University Press.
Lang, J. (2005). Some representation and computational issues in social choice. In Proc. 8th European conference on symbolic and quantitative approaches to reasoning with uncertainty (ECSQARU-2005). Berlin: Springer.
Moulin, H. (1988). Axioms of cooperative decision making. Cambridge: Cambridge University Press.
Nisan, N. (2000). Bidding and allocation in combinatorial auctions. In Proc. ACM conference on electronic commerce (EC-2000). New York: ACM Press.
Papadimitriou, C. H. (1994). Computational complexity. Reading: Addison-Wesley.
Papadimitriou, C. H. (2001). Algorithms, games, and the Internet. In Proc. 33rd annual ACM symposium on theory of computing (STOC-2001). New York: ACM Press.
Rota, G. C. (1964). On the foundations of combinatorial theory I: Theory of Möbius functions. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete, 2(4), 340–368.
Rothkopf, M. H., Pekec̆, A., & Harstad, R. M. (1998). Computationally manageable combinational auctions. Management Science, 44(8), 1131–1147.
Sandholm, T. W. (1998). Contract types for satisficing task allocation: I. Theoretical results. In Proc. AAAI spring symposium: satisficing models.
Sandholm, T. W. (2002). Algorithm for optimal winner determination in combinatorial auctions. Artificial Intelligence, 135(1–2), 1–54.
Sandholm, T. W., & Boutilier, C. (2006). Preference elicitation in combinatorial auctions. In P. Cramton et al. (Eds.), Combinatorial auctions. New York: MIT Press.
Wooldridge, M. (2002). An introduction to multiagent systems. New York: Wiley.
Zinkevich, M. A., Blum, A., & Sandholm, T. W. (2003). On polynomial-time preference elicitation with value queries. In Proc. ACM conference on electronic commerce (EC-2003). New York: ACM Press.
Author information
Authors and Affiliations
Corresponding author
Additional information
A preliminary version of this paper has been presented at the 1st DIMACS-LAMSADE Workshop on Computer Science and Decision Theory (Chevaleyre et al. 2004). We would like to thank the anonymous reviewers for their helpful comments on the manuscript.
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
Chevaleyre, Y., Endriss, U., Estivie, S. et al. Multiagent resource allocation in k-additive domains: preference representation and complexity. Ann Oper Res 163, 49–62 (2008). https://doi.org/10.1007/s10479-008-0335-0
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-008-0335-0