Multiagent resource allocation in \(k\)-additive domains: preference representation and complexity. (English) Zbl 1170.91418
Summary: 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.
MSC:
| 91B32 | Resource and cost allocation (including fair division, apportionment, etc.) |
| 91B08 | Individual preferences |
| 68M14 | Distributed systems |
Keywords:
resource allocation; negotiation; multiagent systems; preference representation; computational complexityReferences:
| [1] | Arrow, K. J., Sen, A. K., & Suzumura, K. (Eds.) (2002). Handbook of social choice and welfare (Vol. 1), Amsterdam: North-Holland. · Zbl 1307.91009 |
| [2] | 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. · Zbl 0937.68002 |
| [3] | Boros, E., & Hammer, P. L. (2002). Pseudo-boolean optimization. Discrete Applied Mathematics, 123(1–3), 155–225. · Zbl 1076.90032 · doi:10.1016/S0166-218X(01)00341-9 |
| [4] | 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. |
| [5] | 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. · Zbl 1183.68570 |
| [6] | Brams, S. J., & Taylor, A. D. (1996). Fair division: from cake-cutting to dispute resolution. Cambridge: Cambridge University Press. · Zbl 0991.91019 |
| [7] | 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. · Zbl 1170.91418 |
| [8] | 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. |
| [9] | 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. · Zbl 1152.91455 |
| [10] | 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. |
| [11] | 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. |
| [12] | Cramton, P., Shoham, Y., & Steinberg, R. (Eds.) (2006). Combinatorial auctions. Cambridge: MIT Press. · Zbl 1194.91018 |
| [13] | Dunne, P. E., Wooldridge, M., & Laurence, M. (2005). The complexity of contract negotiation. Artificial Intelligence, 164(1–2), 23–46. · Zbl 1132.68539 · doi:10.1016/j.artint.2005.01.006 |
| [14] | 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. |
| [15] | Endriss, U., Maudet, N., Sadri, F., & Toni, F. (2006). Negotiating socially optimal allocations of resources. Journal of Artificial Intelligence Research, 25, 315–348. |
| [16] | 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. · doi:10.3166/tsi.23.1219-1238 |
| [17] | Fishburn, P. C. (1970). Utility theory for decision making. New York: Wiley. · Zbl 0213.46202 |
| [18] | 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. |
| [19] | Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: a guide to the theory of NP-completeness. New York: Freeman. · Zbl 0411.68039 |
| [20] | 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. |
| [21] | Grabisch, M. (1997). k-order additive discrete fuzzy measures and their representation. Fuzzy Sets and Systems, 92, 167–189. · Zbl 0927.28014 · doi:10.1016/S0165-0114(97)00168-1 |
| [22] | Keeney, R. L., & Raiffa, H. (1993). Decisions with multiple objectives: preferences and value trade-offs. Cambridge: Cambridge University Press. · Zbl 0488.90001 |
| [23] | 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. · Zbl 1122.68657 |
| [24] | Moulin, H. (1988). Axioms of cooperative decision making. Cambridge: Cambridge University Press. · Zbl 0699.90001 |
| [25] | Nisan, N. (2000). Bidding and allocation in combinatorial auctions. In Proc. ACM conference on electronic commerce (EC-2000). New York: ACM Press. |
| [26] | Papadimitriou, C. H. (1994). Computational complexity. Reading: Addison-Wesley. · Zbl 0833.68049 |
| [27] | 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. · Zbl 0986.68566 |
| [28] | 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. · Zbl 0121.02406 · doi:10.1007/BF00531932 |
| [29] | Rothkopf, M. H., Pekec, A., & Harstad, R. M. (1998). Computationally manageable combinational auctions. Management Science, 44(8), 1131–1147. · Zbl 0989.90094 · doi:10.1287/mnsc.44.8.1131 |
| [30] | Sandholm, T. W. (1998). Contract types for satisficing task allocation: I. Theoretical results. In Proc. AAAI spring symposium: satisficing models. |
| [31] | Sandholm, T. W. (2002). Algorithm for optimal winner determination in combinatorial auctions. Artificial Intelligence, 135(1–2), 1–54. · Zbl 0984.68039 · doi:10.1016/S0004-3702(01)00159-X |
| [32] | Sandholm, T. W., & Boutilier, C. (2006). Preference elicitation in combinatorial auctions. In P. Cramton et al. (Eds.), Combinatorial auctions. New York: MIT Press. |
| [33] | Wooldridge, M. (2002). An introduction to multiagent systems. New York: Wiley. · Zbl 1079.91500 |
| [34] | 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. · Zbl 1274.91211 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
