Tech Reports

ULCS-04-008

Qualitative Coalitional Reasoning with Preferences

Paul E. Dunne and Michael Wooldridge

Abstract

Qualitative coalitional games (QCGs) are a variation of conventional coalitional games in which each coalition may choose to cooperate in a number of different ways, with different choices resulting in potentially different sets of goals being achieved; each agent is associated with a set of goals, the intuition being that an agent is "satisfied" if any of its goals are achieved, but is indifferent between them. In this paper, we extend the framework of QCGs to incorporate preferences that agents have over their goals. In addition to establishing some basic properties of QCGs with Preferences (QCGPs), we investigate and characterise the complexity of six natural decision problems associated with QCGPs. For example, we prove that the problem of establishing Pareto optimality of a goal set with respect to some coalition is co-NP-complete. We end with some brief conclusions and a discussion of related work.

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.