Department of Computer Science
University of Liverpool
3pm Tuesday 9th November 2004
Room 2511, JCMB, King's Buildings
The multi-agent systems field is primarily concerned with systems composed of multiple self-interested autonomous or semi-autonomous computational entities known as agents. Game theory has proved to be a fruitful tool for understanding the property of such systems, and yet standard game theoretic models of cooperative systems are typically not directly applicable to the problem of understanding and reasoning about computational multi-agent systems. In this seminar, we present a type of coalitional game 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 a range natural solution concepts and associated decision problems for QCGs, and investigate 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^p-complete. 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. (This talk will include joint work with Paul E. Dunne.)