On the Structure of Events in Boolean Games

Abstract
Conventional Boolean games embody two important assumptions: (i) all events in the game occur simultaneously; and (ii) assignments to variables must be made in complete ignorance of the values assigned to other variables. For many settings, these assumptions represent gross simplifications. In this paper, we show how Boolean games can be enriched by dependency graphs, which allow us to overcome these limitations. A dependency graph specifies for every variable in the game what information will be available when a value is assigned to that variable. More precisely, a dependency graph is a directed acyclic graph over the set of game variables, where an edge from p to q means that the value assigned to p can be taken into account when choosing a value for q. We refer to games played with dependency graphs as structured Boolean games. In structured Boolean games, players simultaneously choose strategies that define how values will be assigned to variables; these strategies must take into account information dependencies as specified in the dependency graph. Once chosen, strategies are executed, and generate a run-time sequence of events corresponding to the assignment of values to variables as defined by the strategies. The dependency graph induces a partial order model of concurrency for run-time behaviour: if a variable q depends on p, then at run-time the assignment of a value to p must precede the assignment of a value for q. Structured Boolean games thus distinguish between the event corresponding to the selection of a strategy and the events that arise from executing that strategy (i.e., the assignment of values to variables). They thus more closely resemble the reality of multi-agent systems, in which multiple programs (representing player strategies) are concurrently executed to generate run-time behaviour. After motivating and presenting the game 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 concurrent behaviour of structured Boolean games can be represented using a closure operator semantics, and conclude by considering the relationship of our model to Independence Friendly (IF) logic.