Rational Verification in Iterated Electric Boolean Games

Youssouf Oualhadj
(LACL, U-PEC, Paris, France)
Nicolas Troquard
(LACL, U-PEC, Paris, France)

Electric boolean games are compact representations of games where the players have qualitative objectives described by LTL formulae and have limited resources. We study the complexity of several decision problems related to the analysis of rationality in electric boolean games with LTL objectives. In particular, we report that the problem of deciding whether a profile is a Nash equilibrium in an iterated electric boolean game is no harder than in iterated boolean games without resource bounds. We show that it is a PSPACE-complete problem. As a corollary, we obtain that both rational elimination and rational construction of Nash equilibria by a supervising authority are PSPACE-complete problems.

In Alessio Lomuscio and Moshe Y. Vardi: Proceedings of the 4th International Workshop on Strategic Reasoning (SR 2016), New York City, USA, 10th July 2016, Electronic Proceedings in Theoretical Computer Science 218, pp. 41–51.
Published: 10th July 2016.

ArXived at: https://dx.doi.org/10.4204/EPTCS.218.4 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org