Tech Reports

ULCS-04-016

On the Logic of Co-operation and Propositional Control

Wiebe van der Hoek and Michael Wooldridge

Abstract

Cooperation logics have recently begun to attract attention within the multi-agent systems community. Using a cooperation logic, it is possible to represent and reason about the strategic powers of agents and coalitions of agents in game-like multi-agent systems. These powers are generally assumed to be implicitly defined within the structure of the environment, and their origin is rarely discussed. In this paper, we study a cooperation logic in which agents are each assumed to control a set of propositional variables – the powers of agents and coalitions then derive from the allocation of propositions to agents. The basic modal constructs in this Coalition Logic of Propositional Control (CL-PC) allow us to express the fact that a group of agents can cooperate to bring about a certain state of affairs. After motivating and introducing CL-PC, we provide a complete axiom system for the logic, and prove that the model checking and satisfiability problems for CL-PC are both PSPACEcomplete. We then investigate the issue of characterising control in CL-PC with respect to the underlying power structures of the logic, and formally investigate the relationship between CL-PC and Pauly’s Coalition Logic. We conclude by discussing our results and how CL-PC sits in relation to other logics of cooperation.

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.