Synthesising Full-Information Protocols
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2023
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866909104296951808 |
|---|---|
| author | Berwanger, Dietmar Doyen, Laurent Soullard, Thomas |
| author_facet | Berwanger, Dietmar Doyen, Laurent Soullard, Thomas |
| contents | We lay out a model of games with imperfect information that features explicit communication actions, by which the entire observation history of a player is revealed to another player. Such full-information protocols are common in asynchronous distributed systems; here, we consider a synchronous setting with a single active player who may communicate with multiple passive observers in an indeterminate environment. We present a procedure for solving the basic strategy-synthesis problem under regular winning conditions.
We present our solution in an abstract framework of games with imperfect information and we split the proof in two conceptual parts: (i) a generic reduction schema from imperfect-information to perfect-information games, and (ii) a specific construction for full-information protocols that satisfies the requirement of the reduction schema.
Furthermore we show that the number of passive observers induces a strict hierarchy, both in terms of expressiveness and complexity: with n observers, a full-information protocol can express indistinguishability relations (defining imperfect information for the player in the protocol) that are not expressible with n-1 observers, and the strategy-synthesis problem is (n+1)-EXPTIME-complete. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2307_01063 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Synthesising Full-Information Protocols Berwanger, Dietmar Doyen, Laurent Soullard, Thomas Logic in Computer Science We lay out a model of games with imperfect information that features explicit communication actions, by which the entire observation history of a player is revealed to another player. Such full-information protocols are common in asynchronous distributed systems; here, we consider a synchronous setting with a single active player who may communicate with multiple passive observers in an indeterminate environment. We present a procedure for solving the basic strategy-synthesis problem under regular winning conditions. We present our solution in an abstract framework of games with imperfect information and we split the proof in two conceptual parts: (i) a generic reduction schema from imperfect-information to perfect-information games, and (ii) a specific construction for full-information protocols that satisfies the requirement of the reduction schema. Furthermore we show that the number of passive observers induces a strict hierarchy, both in terms of expressiveness and complexity: with n observers, a full-information protocol can express indistinguishability relations (defining imperfect information for the player in the protocol) that are not expressible with n-1 observers, and the strategy-synthesis problem is (n+1)-EXPTIME-complete. |
| title | Synthesising Full-Information Protocols |
| topic | Logic in Computer Science |
| url | https://arxiv.org/abs/2307.01063 |