Easy and hard coalition resource game formation problems: a parameterized complexity analysis

ABSTRACT

Coalition formation is a key topic in multi--agent systems (mas). Coalitions enable agents to achieve goals that they may not have been able to achieve independently, and encourages resource sharing among agents with different goals.

A range of previous studies have found that problems in coalitional games tend to be computationally complex. However, such hardness results consider the entire input as one, ignoring any structural information on the instances. In the case of coalition formation problems, this bundles together several distinct elements of the input, e.g. the agent set, the goal set, the resources, etc. In this paper we reexamine the complexity of coalition formation problems in the coalition resources game model, as a function of their distinct input elements, using the theory of parameterized complexity. The analysis shows that not all parts of the input are created equal, and that many instances of the problem are actually tractable. We show that the problems are FPT in the number of goals, implying that if the number of goals is bounded then an efficient algorithm is available. Similarly, the problems are FPT in the combination of the number of agents and resources, again implying that if these parameters are bounded, then an efficient algorithm is available. On the other hand, the problems are para-NP hard in the number of resources, implying that even if we bound the number of resources the problems (probably) remain hard. Additionally, we show that most problems are W[1]-hard in the size of the coalition of interest, indicating that there is (probably) no algorithm polynomial in all but the coalition size. The exact definitions of the parameterized complexity notions FPT, Para-NP and W[1] are provided herein.

REFERENCES

• 1: A. H. Bond and L. Gasser, editors. Readings in Distributed Artificial Intelligence. Morgan Kaufmann Publishers: San Mateo, CA, 1988.
• 2: Vincent Conitzer , Tuomas Sandholm, Complexity of constructing solutions in the core based on synergies among coalitions, Artificial Intelligence, v.170 n.6, p.607-619, May 2006 [doi>10.1016/j.artint.2006.01.005]
• 3: R. Downey. Parameterized complexity for the skeptic. In Proc. 18th IEEE Annual Conference on Computational Complexity, pages 147--169, 2003.
• 4: Rod G. Downey , Michael R. Fellows, Fixed-Parameter Tractability and Completeness I: Basic Results, SIAM Journal on Computing, v.24 n.4, p.873-921, Aug. 1995 [doi>10.1137/S0097539792228228]
• 5: Rod G. Downey , Michael R. Fellows, Fixed-parameter tractability and completeness II: on completeness for W[1], Theoretical Computer Science, v.141 n.1-2, p.109-131, April 17, 1995 [doi>10.1016/0304-3975(94)00097-3]
• 6: R. G. Downey and M. R. Fellows. Parameterized complexity after almost ten years: review and open questions. In Combinatorics, Computation and Logic, DMTCS'99 and CATS'99. Australian Computer Science Communications, Springer-Verlag, Singapore, vol. 21, pages 1--33, 1999.
• 7: J. Flum , M. Grohe, Parameterized Complexity Theory (Texts in Theoretical Computer Science. An EATCS Series), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 8: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 9: Ravi Kalakota , Andrew B. Whinston, Frontiers of electronic commerce, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1996
• 10: Moni Naor, On fairness in the carpool problem, Journal of Algorithms, v.55 n.1, p.93-98, April 2005 [doi>10.1016/j.jalgor.2004.05.001]
• 11: Tuomas W. Sandholm , Victor R. Lesser, Coalitions among computationally bounded agents, Artificial Intelligence, v.94 n.1-2, p.99-137, July 1997 [doi>10.1016/S0004-3702(97)00030-1]
• 12: O. Shehory and S. Kraus. Coalition formation among autonomous agents: Strategies and complexity. In C. Castelfranchi and J.-P. Müller, editors, From Reaction to Cognition --- Fifth European Workshop on Modelling Autonomous Agents in a Multi-Agent World, MAAMAW-93 (LNAI Volume 957), pages 56--72. Springer-Verlag: Berlin, Germany, 1995.
• 13: Onn Shehory , Sarit Kraus, Methods for task allocation via agent coalition formation, Artificial Intelligence, v.101 n.1-2, p.165-200, May 1998 [doi>10.1016/S0004-3702(98)00045-9]
• 14: G. Weiß, editor. Multi-Agent Systems. The MIT Press: Cambridge, MA, 1999.
• 15: Michael Woolridge , Michael J. Wooldridge, Introduction to Multiagent Systems, John Wiley & Sons, Inc., New York, NY, 2001
• 16: Michael Wooldridge , Paul E. Dunne, On the computational complexity of qualitative coalitional games, Artificial Intelligence, v.158 n.1, p.27-73, September 2004 [doi>10.1016/j.artint.2004.04.002]
• 17: Michael Wooldridge , Paul E. Dunne, On the computational complexity of coalitional resource games, Artificial Intelligence, v.170 n.10, p.835-871, July 2006 [doi>10.1016/j.artint.2006.03.003]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

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

General Terms:
Algorithms, Theory

Keywords:
coalition problems, parameterized complexity