Iterated Boolean games

Julian Gutierrez; Paul Harrenstein; Michael Wooldridge

doi:10.1016/j.ic.2015.03.011

Iterated Boolean games

Julian Gutierrez, Paul Harrenstein, Michael Wooldridge

Research output: Contribution to journal › Article › Research › peer-review

55 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 language	English
Pages (from-to)	53-79
Number of pages	27
Journal	Information and Computation
Volume	242
DOIs	https://doi.org/10.1016/j.ic.2015.03.011
Publication status	Published - Jun 2015
Externally published	Yes

Access to Document

10.1016/j.ic.2015.03.011

301275390-oaFinal published version, 671 KB

Cite this

@article{1041c67d0bd54def8023d5fedb02356d,

title = "Iterated Boolean games",

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.",

author = "Julian Gutierrez and Paul Harrenstein and Michael Wooldridge",

year = "2015",

month = jun,

doi = "10.1016/j.ic.2015.03.011",

language = "English",

volume = "242",

pages = "53--79",

journal = "Information and Computation",

issn = "0890-5401",

publisher = "Elsevier",

}

TY - JOUR

T1 - Iterated Boolean games

AU - Gutierrez, Julian

AU - Harrenstein, Paul

AU - Wooldridge, Michael

PY - 2015/6

Y1 - 2015/6

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84930380839&partnerID=8YFLogxK

U2 - 10.1016/j.ic.2015.03.011

DO - 10.1016/j.ic.2015.03.011

M3 - Article

AN - SCOPUS:84930380839

SN - 0890-5401

VL - 242

SP - 53

EP - 79

JO - Information and Computation

JF - Information and Computation

ER -

Iterated Boolean games

Abstract

Access to Document

Other files and links

Research output

Iterated Boolean games

Cite this