Abstract

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]φ expresses that coalition C is effective for φ. 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.

Received 2 May 2000.

Author notes

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