Iterated Boolean games

Julian Gutierrez, Paul Harrenstein, Michael Wooldridge

Research output: Contribution to journalArticleResearchpeer-review

32 Citations (Scopus)

Abstract

Iterated games are well-known in the game theory literature. We study iterated Boolean games. These are games in which players repeatedly choose truth values for Boolean variables they have control over. Our model of iterated Boolean games assumes that players have goals given by formulae of Linear Temporal Logic (LTL), a formalism for expressing properties of state sequences. In order to represent the strategies of players in such games, we use a finite state machine model. After introducing and formally defining iterated Boolean games, we investigate the computational complexity of their associated game-theoretic decision problems, as well as semantic conditions characterising classes of LTL properties that are preserved by equilibrium points (pure-strategy Nash equilibria) whenever they exist.

Original languageEnglish
Pages (from-to)53-79
Number of pages27
JournalInformation and Computation
Volume242
DOIs
Publication statusPublished - Jun 2015
Externally publishedYes

Cite this