Games with recurring certainty
Infinite games where several players seek to coordinate under imperfect information are known to be intractable, unless the information flow is severely restricted. Examples of undecidable cases typically feature a situation where players become uncertain about the current state of the game, and thi...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Open Publishing Association
2014-04-01
|
| Series: | Electronic Proceedings in Theoretical Computer Science |
| Online Access: | http://arxiv.org/pdf/1404.7770v1 |
| _version_ | 1828199005815832576 |
|---|---|
| author | Dietmar Berwanger Anup Basil Mathew |
| author_facet | Dietmar Berwanger Anup Basil Mathew |
| author_sort | Dietmar Berwanger |
| collection | DOAJ |
| description | Infinite games where several players seek to coordinate under imperfect information are known to be intractable, unless the information flow is severely restricted. Examples of undecidable cases typically feature a situation where players become uncertain about the current state of the game, and this uncertainty lasts forever. Here we consider games where the players attain certainty about the current state over and over again along any play. For finite-state games, we note that this kind of recurring certainty implies a stronger condition of periodic certainty, that is, the events of state certainty ultimately occur at uniform, regular intervals. We show that it is decidable whether a given game presents recurring certainty, and that, if so, the problem of synthesising coordination strategies under w-regular winning conditions is solvable. |
| first_indexed | 2024-04-12T10:48:00Z |
| format | Article |
| id | doaj.art-9ef4527a0f9445d985e99031c72538c7 |
| institution | Directory Open Access Journal |
| issn | 2075-2180 |
| language | English |
| last_indexed | 2024-04-12T10:48:00Z |
| publishDate | 2014-04-01 |
| publisher | Open Publishing Association |
| record_format | Article |
| series | Electronic Proceedings in Theoretical Computer Science |
| spelling | doaj.art-9ef4527a0f9445d985e99031c72538c72022-12-22T03:36:20ZengOpen Publishing AssociationElectronic Proceedings in Theoretical Computer Science2075-21802014-04-01146Proc. SR 2014919610.4204/EPTCS.146.12:17Games with recurring certaintyDietmar Berwanger0Anup Basil Mathew1 Laboratoire Specification et Verification CNRS & ENS Cachan, France Institute of Mathematical Sciences Chennai, India Infinite games where several players seek to coordinate under imperfect information are known to be intractable, unless the information flow is severely restricted. Examples of undecidable cases typically feature a situation where players become uncertain about the current state of the game, and this uncertainty lasts forever. Here we consider games where the players attain certainty about the current state over and over again along any play. For finite-state games, we note that this kind of recurring certainty implies a stronger condition of periodic certainty, that is, the events of state certainty ultimately occur at uniform, regular intervals. We show that it is decidable whether a given game presents recurring certainty, and that, if so, the problem of synthesising coordination strategies under w-regular winning conditions is solvable.http://arxiv.org/pdf/1404.7770v1 |
| spellingShingle | Dietmar Berwanger Anup Basil Mathew Games with recurring certainty Electronic Proceedings in Theoretical Computer Science |
| title | Games with recurring certainty |
| title_full | Games with recurring certainty |
| title_fullStr | Games with recurring certainty |
| title_full_unstemmed | Games with recurring certainty |
| title_short | Games with recurring certainty |
| title_sort | games with recurring certainty |
| url | http://arxiv.org/pdf/1404.7770v1 |
| work_keys_str_mv | AT dietmarberwanger gameswithrecurringcertainty AT anupbasilmathew gameswithrecurringcertainty |