On the computational complexity of coalitional resource games.

*(English)*Zbl 1131.91011Summary: We study Coalitional Resource Games (CRGS), a variation of Qualitative Coalitional Games (QCGS) in which each agent is endowed with a set of resources, and the ability of a coalition to bring about a set of goals depends on whether they are collectively endowed with the necessary resources. We investigate and classify the computational complexity of a number of natural decision problems for CRGS, over and above those previously investigated for QCGS in general. For example, we show that the complexity of determining whether conflict is inevitable between two coalitions with respect to some stated resource bound (i.e., a limit value for every resource) is co-NP-complete. We then investigate the relationship between CRGS and QCGS, and in particular the extent to which it is possible to translate between the two models. We first characterise the complexity of determining equivalence between CRGS and QCGS. We then show that it is always possible to translate any given CRG into a succinct equivalent QCG, and that it is not always possible to translate a QCG into an equivalent CRG; we establish some necessary and some sufficient conditions for a translation from QCGS to CRGS to be possible, and show that even where an equivalent CRG exists, it may have size exponential in the number of goals and agents of its source QCG.

##### MSC:

91A12 | Cooperative games |

68Q25 | Analysis of algorithms and problem complexity |

68T99 | Artificial intelligence |

PDF
BibTeX
XML
Cite

\textit{M. Wooldridge} and \textit{P. E. Dunne}, Artif. Intell. 170, No. 10, 835--871 (2006; Zbl 1131.91011)

Full Text:
DOI

##### References:

[1] | T. Agotnes, W. van der Hoek, M. Wooldridge, Temporal qualitative coalitional games, in: Proceedings of the Fifth International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS-2006), Hakodate, Japan, 2006 · Zbl 1171.03008 |

[2] | Ben-Ari, M., Principles of concurrent and distributed programming, (1990), Prentice Hall Englewood Cliffs, NJ · Zbl 0701.68001 |

[3] | J. Bilbao, J. Fernández, J. López, Complexity in cooperative game theory, Manuscript |

[4] | () |

[5] | Brent, R.; Kuck, D.J.; Maruyama, K., The parallel evaluation of arithmetic expressions without division, IEEE transactions computers, C-22, 532-534, (1973) · Zbl 0252.68028 |

[6] | P. Buzing, A. ter Mors, J. Valk, C. Witteveen, Task coordination for non-cooperative planning agents, in: Proceedings of the Second European Workshop on Multi-Agent Systems (EUMAS-04), Barcelona, Spain, 2004, pp. 87-99 |

[7] | Chakrabarti, A.; de Alfaro, L.; Henzinger, T.A.; Stoelinga, M., Resource interfaces, (), 117-133 |

[8] | V. Conitzer, T. Sandholm, Complexity of determining nonemptiness of the core, in: Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence (IJCAI-03), Acapulco, Mexico, 2003, pp. 613-618 |

[9] | V. Conitzer, T. Sandholm, Computing Shapley values, manipulating value division schemes, and checking core membership in multi-issue domains, in: Proceedings of the Nineteenth National Conference on Artificial Intelligence (AAAI-2004), San Jose, CA, 2004, pp. 219-225 |

[10] | Deng, X.; Papadimitriou, C.H., On the complexity of cooperative solution concepts, Mathematics of operations research, 19, 2, 257-266, (1994) · Zbl 0824.90146 |

[11] | Dunne, P.E., The complexity of Boolean networks, (1988), Academic Press London · Zbl 0672.68012 |

[12] | Dunne, P.E.; Bench-Capon, T.J.M., Complexity in value-based argument systems, (), 360-371 · Zbl 1111.68673 |

[13] | Durfee, E.H., Distributed problem solving and planning, (), 121-164 |

[14] | Foster, I.; Kesselman, C.; Tuecke, S., The anatomy of the grid: enabling scalable virtual organisations, International journal of supercomputer applications, 15, 3, 200-222, (2001) |

[15] | Garey, M.R.; Johnson, D.S., Computers and intractability: A guide to the theory of \scnp-completeness, (1979), W.H. Freeman New York |

[16] | Ghallab, M.; Nau, D.; Traverso, P., Automated planning: theory and practice, (2004), Morgan Kaufmann San Mateo, CA · Zbl 1074.68613 |

[17] | S. Ieong, Y. Shoham, Marginal contribution nets: A compact representation scheme for coalitional games, in: Proceedings of the Sixth ACM Conference on Electronic Commerce (EC’05), Vancouver, Canada, 2005 |

[18] | Johnson, D.S., A catalog of complexity classes, (), 67-161 · Zbl 0900.68246 |

[19] | Karp, R.M.; Ramachandran, V., Parallel algorithms for shared-memory machines, (), 869-942 · Zbl 0900.68267 |

[20] | Ketchpel, S., Coalition formation among autonomous agents, (), 73-88 |

[21] | Khrapchenko, V.M., Asymptotic estimation of addition time of a parallel adder, Problemy kibernet., Systems theory res., 19, 105-122, (1970), in Russian. Translation: |

[22] | Klusch, M.; Gerber, A., Dynamic coalition formation among rational agents, IEEE intelligent systems, 17, 3, 42-47, (2002) |

[23] | Kraus, S., Strategic negotiation in multiagent environments, (2001), MIT Press Cambridge, MA · Zbl 1062.68099 |

[24] | Krishna, V., Auction theory, (2002), Academic Press London |

[25] | Modi, P.J.; Shen, W.-M.; Tambe, M.; Yokoo, M., Adopt: asynchronous distributed constraint optimization with quality guarantees, Artificial intelligence, 161, 149-180, (2005) · Zbl 1132.68706 |

[26] | Y. Moses, M. Tennenholtz, Multi-entity models, in: K. Furukawa, D. Michie, S. Muggleton (Eds.), Machine Intelligence 14, Tokyo, Japan, 1995, pp. 65-90 |

[27] | Osborne, M.J.; Rubinstein, A., A course in game theory, (1994), MIT Press Cambridge, MA · Zbl 1194.91003 |

[28] | Papadimitriou, C.H., Computational complexity, (1994), Addison-Wesley Reading, MA · Zbl 0557.68033 |

[29] | Papadimitriou, C.H.; Steiglitz, K., Combinatorial optimization, (1982), Prentice Hall International Hemel Hempstead · Zbl 0503.90060 |

[30] | M. Pauly, Logic for social software, PhD thesis, University of Amsterdam, 2001. ILLC Dissertation Series 2001-10 |

[31] | V.R. Pratt, The effect of basis on the size of Boolean expressions, in: Proceedings of the Sixteenth Symposium on Foundations of Computer Science (FOCS), 1975, pp. 119-121 · Zbl 0469.94017 |

[32] | Riordan, J.; Shannon, C.E., The number of two-terminal series-parallel networks, J. math. phys., 21, 83-93, (1942) |

[33] | Sandholm, T., Distributed rational decision making, (), 201-258 |

[34] | Sandholm, T.; Larson, K.; Andersson, M.; Shehory, O.; Tohmé, F., Coalition structure generation with worst case guarantees, Artificial intelligence, 111, 1-2, 209-238, (1999) · Zbl 0997.91004 |

[35] | T.W. Sandholm, V.R. Lesser, Coalition formation among bounded rational agents, in: Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence (IJCAI-95), Montréal, Québec, Canada, August 1995, pp. 662-671 |

[36] | Sandholm, T.W.; Lesser, V.R., Coalitions among computationally bounded agents, Artificial intelligence, 94, 1-2, 99-138, (1997) · Zbl 0904.68167 |

[37] | Shehory, O.; Kraus, S., Coalition formation among autonomous agents: strategies and complexity, (), 56-72 |

[38] | O. Shehory, S. Kraus, Task allocation via coalition formation among autonomous agents, in: Proceedings of the Fourteenth International Joint Conference on Artificial Intelligence (IJCAI-95), Montréal, Québec, Canada, August 1995, pp. 655-661 |

[39] | Shehory, O.; Kraus, S., Methods for task allocation via agent coalition formation, Artificial intelligence, 101, 1-2, 165-200, (1998) · Zbl 0908.68032 |

[40] | Shehory, O.; Kraus, S., Feasible formation of stable coalitions among autonomous agents in non-super-additive environments, Computational intelligence, 15, 33, 218-251, (1999) |

[41] | M. Tennenholtz, Y. Moses, On cooperation in a multi-entity model: Preliminary report, in: Proceedings of the Eleventh International Joint Conference on Artificial Intelligence (IJCAI-89), Detroit, MI, 1989, pp. 918-923 · Zbl 0713.68080 |

[42] | Valiant, L.G., Short monotone formulae for the majority function, Journal of algorithms, 5, 363-366, (1984) · Zbl 0554.94017 |

[43] | von Martial, F., Coordinating plans of autonomous agents, Lecture notes in artificial intelligence, vol. 610, (1992), Springer-Verlag Berlin |

[44] | () |

[45] | Wellman, M.P., A market-oriented programming environment and its applications to multicommodity flow problems, Journal of AI research, 1, 1-23, (1993) · Zbl 0900.90089 |

[46] | Wooldridge, M., An introduction to multiagent systems, (2002), John Wiley & Sons New York |

[47] | Wooldridge, M.; Dunne, P.E., On the computational complexity of qualitative coalitional games, Artificial intelligence, 158, 1, 27-73, (2004) · Zbl 1085.68070 |

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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.