Oxford Journals
tools journals homepage advanced search contact help
Journal of Logic and Computation: Current Issue
 
home
browse
current
etoc
authors
subinfo
subscribers
samples

OUP > Journals > Computing/Engineer. & Mathematics/Stats. > Journal of Logic and Computation

Journal of Logic and Computation

Volume 12, Issue 1, February 2002: pp. 149-166

A Modal Logic for Coalitional Power in Games

Marc Pauly1

1Center for Mathematics and Computer Science (CWI), P.O. Box 94079, 1090 GB Amsterdam, The Netherlands. E-mail: pauly@cwi.nl

We present a modal logic for reasoning about what groups of agents can bring about by collective action. Given a set of states, we introduce game frames which associate with every state a strategic game among the agents. Game frames are essentially extensive games of perfect information with simultaneous actions, where every action profile is associated with a new state, the outcome of the game. A coalition of players is effective for a set of states X in a game if the coalition can guarantee the outcome of the game to lie in X. We propose a modal logic (Coalition Logic) to formalize reasoning about effectivity in game frames, where [C][phgr] expresses that coalition C is effective for [phgr]. An axiomatization is presented and completeness proved. Coalition Logic provides a unifying game-theoretic view of modal logic: Since nondeterministic processes and extensive games without parallel moves emerge as particular instances of game frames, normal and non-normal modal logics correspond to 1- and 2-player versions of Coalition Logic. The satisfiability problem for Coalition Logic is shown to be PSPACE-complete.

Keywords: Modal logic; game theory; multiagent systems

Table of Contents   Full-Text PDF (222 KB)

Oxford University Press
Published by Oxford University Press
Copyright ©Oxford University Press 2003
Print ISSN: 0955-792X  Online ISSN: 1465-363X.
Oxford University Press Privacy Policy and Legal Statement