Anytime-Constrained Equilibria in Polynomial Time
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910858506928128 |
|---|---|
| author | McMahan, Jeremy |
| author_facet | McMahan, Jeremy |
| contents | We extend anytime constraints to the Markov game setting and the corresponding solution concept of an anytime-constrained equilibrium (ACE). Then, we present a comprehensive theory of anytime-constrained equilibria that includes (1) a computational characterization of feasible policies, (2) a fixed-parameter tractable algorithm for computing ACE, and (3) a polynomial-time algorithm for approximately computing ACE. Since computing a feasible policy is NP-hard even for two-player zero-sum games, our approximation guarantees are optimal so long as $P \neq NP$. We also develop the first theory of efficient computation for action-constrained Markov games, which may be of independent interest. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_23637 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Anytime-Constrained Equilibria in Polynomial Time McMahan, Jeremy Machine Learning Artificial Intelligence Data Structures and Algorithms Computer Science and Game Theory We extend anytime constraints to the Markov game setting and the corresponding solution concept of an anytime-constrained equilibrium (ACE). Then, we present a comprehensive theory of anytime-constrained equilibria that includes (1) a computational characterization of feasible policies, (2) a fixed-parameter tractable algorithm for computing ACE, and (3) a polynomial-time algorithm for approximately computing ACE. Since computing a feasible policy is NP-hard even for two-player zero-sum games, our approximation guarantees are optimal so long as $P \neq NP$. We also develop the first theory of efficient computation for action-constrained Markov games, which may be of independent interest. |
| title | Anytime-Constrained Equilibria in Polynomial Time |
| topic | Machine Learning Artificial Intelligence Data Structures and Algorithms Computer Science and Game Theory |
| url | https://arxiv.org/abs/2410.23637 |