"On Representations and the Complexity of Coalitional Games"

Speaker: Michael Wooldridge, Computer Science, University of Liverpool
Date: Wednesday, 6 December
Time: 12noon
Place: Ross 201

Abstract:

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
useful 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
investigate the key issues that arise in this setting; in particular,
the issue of *representing* coalitional games.

We first give an introduction to the types of models used in
cooperative game theory, and 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.)