The Complexity of Pure Strategy Relevant Equilibria in Concurrent Games
Fuente:
arXiv
Guardado en:
| Autor principal: | |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915505441341440 |
|---|---|
| author | Bhaduri, Purandar |
| author_facet | Bhaduri, Purandar |
| contents | We study rational synthesis problems for concurrent games with omega-regular objectives. Our model of rationality considers only pure strategy Nash equilibria that satisfy either a social welfare or Pareto optimality condition with respect to an omega-regular objective for each agent. This extends earlier work on equilibria in concurrent games, without consideration about their quality. Our results show that the existence of Nash equilibria satisfying social welfare conditions can be computed as efficiently as the constrained Nash equilibrium existence problem. On the other hand, the existence of Nash equilibria satisfying the Pareto optimality condition possibly involves a higher upper bound, except in the case of Buchi and Muller games, for which all three problems are in the classes P and PSPACE-complete, respectively. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_07501 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | The Complexity of Pure Strategy Relevant Equilibria in Concurrent Games Bhaduri, Purandar Computer Science and Game Theory Computational Complexity Formal Languages and Automata Theory Logic in Computer Science Multiagent Systems We study rational synthesis problems for concurrent games with omega-regular objectives. Our model of rationality considers only pure strategy Nash equilibria that satisfy either a social welfare or Pareto optimality condition with respect to an omega-regular objective for each agent. This extends earlier work on equilibria in concurrent games, without consideration about their quality. Our results show that the existence of Nash equilibria satisfying social welfare conditions can be computed as efficiently as the constrained Nash equilibrium existence problem. On the other hand, the existence of Nash equilibria satisfying the Pareto optimality condition possibly involves a higher upper bound, except in the case of Buchi and Muller games, for which all three problems are in the classes P and PSPACE-complete, respectively. |
| title | The Complexity of Pure Strategy Relevant Equilibria in Concurrent Games |
| topic | Computer Science and Game Theory Computational Complexity Formal Languages and Automata Theory Logic in Computer Science Multiagent Systems |
| url | https://arxiv.org/abs/2505.07501 |