On the structure of events in Boolean games

Julian Bradfield, Julian Gutierrez, Michael Wooldridge

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

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.
Original languageEnglish
Title of host publicationLOFT 2014
Subtitle of host publicationThe Eleventh Conference on Logic and The Foundations of Game and Decision Theory
EditorsThomas Agotnes, Giacomo Bonanno, Wiebe van der Hoek
Place of PublicationBergen Norway
PublisherSpringer
Number of pages15
Publication statusPublished - 2014
Externally publishedYes
EventThe Eleventh Conference on Logic and The Foundations of Game and Decision Theory 2014 - Bergen, Norway
Duration: 27 Jul 201430 Jul 2014
Conference number: 11th
https://folk.uib.no/nmita/LOFT11/About.html

Conference

ConferenceThe Eleventh Conference on Logic and The Foundations of Game and Decision Theory 2014
Abbreviated titleLOFT 2014
CountryNorway
CityBergen
Period27/07/1430/07/14
Internet address

Cite this