How good is a strategy in a game with nature?

Arnaud Carayol; Olivier Serre

doi:10.1109/LICS.2015.62

How good is a strategy in a game with nature?

Arnaud Carayol
, Olivier Serre

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

Abstract

We consider games with two antagonistic players - Éloïse (modelling a program) and Abelard (modelling a byzantine environment) - and a third, unpredictable and uncontrollable player, that we call Nature. Motivated by the fact that the usual probabilistic semantics very quickly leads to undecidability when considering either infinite game graphs or imperfect information, we propose two alternative semantics that leads to decidability where the probabilistic one fails: one based on counting and one based on topology.

Original language	English
Title of host publication	Proceedings - 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2015
Publisher	Institute of Electrical and Electronics Engineers Inc.
Pages	609-620
Number of pages	12
ISBN (Electronic)	9781479988754
DOIs	https://doi.org/10.1109/LICS.2015.62
Publication status	Published - 31 Jul 2015
Externally published	Yes
Event	30th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2015 - Kyoto, Japan Duration: 6 Jul 2015 → 10 Jul 2015

Publication series

Name	Proceedings - Symposium on Logic in Computer Science
Volume	2015-July
ISSN (Print)	1043-6871

Conference

Conference	30th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2015
Country/Territory	Japan
City	Kyoto
Period	6/07/15 → 10/07/15

Keywords

Cardinality constraints
Large sets of branches
Qualitative study of games
Tree automata

Access to Document

10.1109/LICS.2015.62

Cite this

@inproceedings{014f0800b6ab4290ae939475e19c232e,

title = "How good is a strategy in a game with nature?",

abstract = "We consider games with two antagonistic players - {\'E}lo{\"i}se (modelling a program) and Abelard (modelling a byzantine environment) - and a third, unpredictable and uncontrollable player, that we call Nature. Motivated by the fact that the usual probabilistic semantics very quickly leads to undecidability when considering either infinite game graphs or imperfect information, we propose two alternative semantics that leads to decidability where the probabilistic one fails: one based on counting and one based on topology.",

keywords = "Cardinality constraints, Large sets of branches, Qualitative study of games, Tree automata",

author = "Arnaud Carayol and Olivier Serre",

note = "Publisher Copyright: {\textcopyright} 2015 IEEE.; 30th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2015 ; Conference date: 06-07-2015 Through 10-07-2015",

year = "2015",

month = jul,

day = "31",

doi = "10.1109/LICS.2015.62",

language = "English",

series = "Proceedings - Symposium on Logic in Computer Science",

publisher = "Institute of Electrical and Electronics Engineers Inc.",

pages = "609--620",

booktitle = "Proceedings - 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2015",

}

Carayol, A & Serre, O 2015, How good is a strategy in a game with nature? in Proceedings - 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2015., 7174916, Proceedings - Symposium on Logic in Computer Science, vol. 2015-July, Institute of Electrical and Electronics Engineers Inc., pp. 609-620, 30th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2015, Kyoto, Japan, 6/07/15. https://doi.org/10.1109/LICS.2015.62

How good is a strategy in a game with nature? / Carayol, Arnaud; Serre, Olivier.
Proceedings - 2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2015. Institute of Electrical and Electronics Engineers Inc., 2015. p. 609-620 7174916 (Proceedings - Symposium on Logic in Computer Science; Vol. 2015-July).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review