Tractable negotiation in tree-structured domains

ABSTRACT

Multiagent resource allocation is a timely and exciting area of research at the interface of Computer Science and Economics. One of the main challenges in this area is the high complexity of negotiation. In particular, the complexity of the task of identifying rational deals, i.e. deals that are beneficial for all participants, often hinders the successful transfer of theoretical results to practical applications. To address this issue, we propose several protocols designed to tame the complexity of negotiation by exploiting structural properties of the utility functions used by agents to model their preferences over alternative bundles of resources. In particular, we consider domains where utility functions are k-additive (that is, synergies between different resources are restricted to bundles of at most k items) and tree-structured in the sense that the bundles for which there are synergies do not overlap. We show how protocols exploiting these properties can allow for drastically simplified negotiation processes.

REFERENCES

• 1: K. J. Arrow, A. K. Sen, and K. Suzumura, editors. Handbook of Social Choice and Welfare. North-Holland, 2002.
• 2: Urszula Chajewska , Daphne Koller, Utilities as Random Variables: Density Estimation and Structure Discovery, Proceedings of the 16th Conference on Uncertainty in Artificial Intelligence, p.63-71, June 30-July 03, 2000
• 3: Y. Chevaleyre, U. Endriss, S. Estivie, and N. Maudet. Multiagent resource allocation with k-additive utility functions. In Proc. DIMACS-LAMSADE Workshop on Computer Science and Decision Theory, 2004.
• 4: Yann Chevaleyre , Ulle Endriss , Jérôme Lang , Nicolas Maudet, Negotiating over small bundles of resources, Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, July 25-29, 2005, The Netherlands [doi>10.1145/1082473.1082518]
• 5: V. Conitzer, T. W. Sandholm, and P. Santi. Combinatorial auctions with k-wise dependent valuations. In Proc. AAAI-2005. AAAI Press, 2005.
• 6: Peter Cramton , Yoav Shoham , Richard Steinberg, Combinatorial Auctions, The MIT Press, 2006
• 7: Paul E. Dunne , Michael Wooldridge , Michael Laurence, The complexity of contract negotiation, Artificial Intelligence, v.164 n.1-2, p.23-46, May 2005 [doi>10.1016/j.artint.2005.01.006]
• 8: Ulle Endriss , Nicolas Maudet, On the Communication Complexity of Multilateral Trading: Extended Report, Autonomous Agents and Multi-Agent Systems, v.11 n.1, p.91-107, July 2005 [doi>10.1007/s10458-005-1080-2]
• 9: U. Endriss, N. Maudet, F. Sadri, and F. Toni. Negotiating socially optimal allocations of resources. Journal of Artificial Intelligence Research, 2006. To appear.
• 10: Boi Faltings , Makoto Yokoo, Introduction: special issue on distributed constraint satisfaction, Artificial Intelligence, v.161 n.1-2, p.1-5, January 2005 [doi>10.1016/j.artint.2004.10.001]
• 11: Michel Grabisch, k-order additive discrete fuzzy measures and their representation, Fuzzy Sets and Systems, v.92 n.2, p.167-189, Dec. 1, 1997 [doi>10.1016/S0165-0114(97)00168-1]
• 12: P. J. 't Hoen and J. A. La Poutré. A decommitment strategy in a competitive multi-agent transportation setting. In AMEC V. Springer-Verlag, 2004.
• 13: M. Lemaître, G. Verfaillie, F. Jouhaud, J.-M. Lachiver, and N. Bataille. Selecting and scheduling observations of agile satellites. Aerospace Sciences and Technology, 6:367--381, 2002.
• 14: N. Nisan. Bidding languages for combinatorial auctions. In P. Cramton et al., editors, Combinatorial Auctions. MIT Press, 2006.
• 15: Valentin Robu , D. J. A. Somefun , J. A. La Poutré, Modeling complex multi-issue negotiations using utility graphs, Proceedings of the fourth international joint conference on Autonomous agents and multiagent systems, July 25-29, 2005, The Netherlands [doi>10.1145/1082473.1082516]
• 16: J. S. Rosenschein and G. Zlotkin. Rules of Encounter. MIT Press, 1994.
• 17: Michael H. Rothkopf , Aleksandar Pekec , Ronald M. Harstad, Computationally Manageable Combinational Auctions, Management Science, v.44 n.8, p.1131-1147, August 1998 [doi>10.1287/mnsc.44.8.1131]
• 18: T. W. Sandholm. Contract types for satisficing task allocation: I Theoretical results. In Proc. AAAI Spring Symposium: Satisficing Models, 1998.
• 19: Peter R. Wurman , William E. Walsh , Michael P. Wellman, Flexible double auctions for electionic commerce: theory and implementation, Decision Support Systems, v.24 n.1, p.17-27, Nov. 1998 [doi>10.1016/S0167-9236(98)00060-8]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
        I.2.11 Distributed Artificial Intelligence
            Subjects: Multiagent systems

Additional Classification:
  J. Computer Applications
  J.4 SOCIAL AND BEHAVIORAL SCIENCES

General Terms:
Economics, Theory

Keywords:
multiagent resource allocation, negotiation