Tech Reports

ULCS-04-007

On the Computational Complexity of Qualitative Coalitional Games

Michael Wooldridge and Paul E. Dunne

Abstract

We study coalitional games in which agents are each assumed to have a goal to be achieved, and where the characteristic property of a coalition is a set of choices, with each choice denoting a set of goals that would be achieved if the choice was made. Such qualitative coalitional games (QCGs) are a natural tool for modelling goal-oriented multiagent systems. After introducing and formally defining QCGs, we systematically formulate fourteen natural decision problems associated with them, and determine the computational complexity of these problems. For example, we formulate a notion of coalitional stability inspired by that of the core from conventional coalitional games, and prove that the problem of showing that the core of a QCG is non-empty is $D_{1}^{p}$-complete. (As an aside, we present what we believe is the first "natural" problem that is proven to be complete for $D_{2}^{p}$.) We conclude by discussing the relationship of our work to other research on coalitional reasoning in multiagent systems, and present some avenues for future research.

For each technical report listed here, copyright and all intellectual property rights remain with the respective authors. Copyright is effective from the year of publication in each case. By downloading a file from this page, you agree to use it only for purposes of research and scholarship. Any other use of this material or storage of it in any medium or its sale or distribution in any form is expressly forbidden without prior written permission from the authors concerned.