## 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 generalise the conventional Boolean games framework. 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 variable p

can be taken into account when choosing a value for variable q. We refer to games played with

dependency graphs as partial order Boolean games. In partial order 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. Partial order

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 partial order Boolean games can be represented using a closure operator semantics,

and conclude by considering the relationship of our model to Independence Friendly (IF) logic.

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 generalise the conventional Boolean games framework. 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 variable p

can be taken into account when choosing a value for variable q. We refer to games played with

dependency graphs as partial order Boolean games. In partial order 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. Partial order

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 partial order Boolean games can be represented using a closure operator semantics,

and conclude by considering the relationship of our model to Independence Friendly (IF) logic.

Original language | English |
---|---|

Title of host publication | LOFT 2014 |

Subtitle of host publication | The Eleventh Conference on Logic and The Foundations of Game and Decision Theory |

Editors | Thomas Agotnes, Giacomo Bonanno, Wiebe van der Hoek |

Place of Publication | Bergen Norway |

Publisher | Springer |

Number of pages | 15 |

Publication status | Published - 2014 |

Externally published | Yes |

Event | The Eleventh Conference on Logic and The Foundations of Game and Decision Theory 2014 - Bergen, Norway Duration: 27 Jul 2014 → 30 Jul 2014 Conference number: 11th https://folk.uib.no/nmita/LOFT11/About.html |

### Conference

Conference | The Eleventh Conference on Logic and The Foundations of Game and Decision Theory 2014 |
---|---|

Abbreviated title | LOFT 2014 |

Country | Norway |

City | Bergen |

Period | 27/07/14 → 30/07/14 |

Internet address |