Partial-Order Boolean Games: Informational Independence in a Logic-Based Model of Strategic Interaction

Abstract
As they are conventionally formulated, Boolean games are games of simultaneous moves: players make their choices in ignorance of the choices being made by other players. For many settings, this is clearly unrealistic. In this paper, we show how Boolean games can be enriched by dependency graphs which explicitly represent the dependencies between choices in a game. These dependency graphs play two roles. First, they allow us to specify precisely what a player knows about other (previous) choices when that player makes a choice. Second, they capture a richer and more plausible model of concurrency than the simultaneous-action model implicit in conventional Boolean games. Dependency graphs define a partial temporal ordering of choices in a game, and so we refer to Boolean games with dependency graphs as partial-order Boolean games. After motivating and presenting the partial-order Boolean games model, we explore its properties. We show that while some problems associated with our new games have the same complexity as in conventional Boolean games, for others the complexity blows up dramatically. We also show that the concurrency in partial-order Boolean games can be modelled using a closure-operator semantics, and conclude by considering the relationship of our model to Independence-Friendly (IF) logic.