Most General Winning Secure Equilibria Synthesis in Graph Games
Fuente:
arXiv
Guardado en:
| Autores principales: | , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866910304184565760 |
|---|---|
| author | Nayak, Satya Prakash Schmuck, Anne-Kathrin |
| author_facet | Nayak, Satya Prakash Schmuck, Anne-Kathrin |
| contents | This paper considers the problem of co-synthesis in $k$-player games over a finite graph where each player has an individual $ω$-regular specification $ϕ_i$. In this context, a secure equilibrium (SE) is a Nash equilibrium w.r.t. the lexicographically ordered objectives of each player to first satisfy their own specification, and second, to falsify other players' specifications. A winning secure equilibrium (WSE) is an SE strategy profile $(π_i)_{i\in[1;k]}$ that ensures the specification $ϕ:=\bigwedge_{i\in[1;k]}ϕ_i$ if no player deviates from their strategy $π_i$. Distributed implementations generated from a WSE make components act rationally by ensuring that a deviation from the WSE strategy profile is immediately punished by a retaliating strategy that makes the involved players lose.
In this paper, we move from deviation punishment in WSE-based implementations to a distributed, assume-guarantee based realization of WSE. This shift is obtained by generalizing WSE from strategy profiles to specification profiles $(φ_i)_{i\in[1;k]}$ with $\bigwedge_{i\in[1;k]}φ_i = ϕ$, which we call most general winning secure equilibria (GWSE). Such GWSE have the property that each player can individually pick a strategy $π_i$ winning for $φ_i$ (against all other players) and all resulting strategy profiles $(π_i)_{i\in[1;k]}$ are guaranteed to be a WSE. The obtained flexibility in players' strategy choices can be utilized for robustness and adaptability of local implementations.
Concretely, our contribution is three-fold: (1) we formalize GWSE for $k$-player games over finite graphs, where each player has an $ω$-regular specification $ϕ_i$; (2) we devise an iterative semi-algorithm for GWSE synthesis in such games, and (3) obtain an exponential-time algorithm for GWSE synthesis with parity specifications $ϕ_i$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_09957 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Most General Winning Secure Equilibria Synthesis in Graph Games Nayak, Satya Prakash Schmuck, Anne-Kathrin Computer Science and Game Theory This paper considers the problem of co-synthesis in $k$-player games over a finite graph where each player has an individual $ω$-regular specification $ϕ_i$. In this context, a secure equilibrium (SE) is a Nash equilibrium w.r.t. the lexicographically ordered objectives of each player to first satisfy their own specification, and second, to falsify other players' specifications. A winning secure equilibrium (WSE) is an SE strategy profile $(π_i)_{i\in[1;k]}$ that ensures the specification $ϕ:=\bigwedge_{i\in[1;k]}ϕ_i$ if no player deviates from their strategy $π_i$. Distributed implementations generated from a WSE make components act rationally by ensuring that a deviation from the WSE strategy profile is immediately punished by a retaliating strategy that makes the involved players lose. In this paper, we move from deviation punishment in WSE-based implementations to a distributed, assume-guarantee based realization of WSE. This shift is obtained by generalizing WSE from strategy profiles to specification profiles $(φ_i)_{i\in[1;k]}$ with $\bigwedge_{i\in[1;k]}φ_i = ϕ$, which we call most general winning secure equilibria (GWSE). Such GWSE have the property that each player can individually pick a strategy $π_i$ winning for $φ_i$ (against all other players) and all resulting strategy profiles $(π_i)_{i\in[1;k]}$ are guaranteed to be a WSE. The obtained flexibility in players' strategy choices can be utilized for robustness and adaptability of local implementations. Concretely, our contribution is three-fold: (1) we formalize GWSE for $k$-player games over finite graphs, where each player has an $ω$-regular specification $ϕ_i$; (2) we devise an iterative semi-algorithm for GWSE synthesis in such games, and (3) obtain an exponential-time algorithm for GWSE synthesis with parity specifications $ϕ_i$. |
| title | Most General Winning Secure Equilibria Synthesis in Graph Games |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2401.09957 |