Polynomial Expectation Property for Max-Polymatrix Games
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866908621771636736 |
|---|---|
| author | Dai, Howard |
| author_facet | Dai, Howard |
| contents | We address an open problem on the computability of correlated equilibria in a variant of polymatrix where each player's utility is the maximum of their edge payoffs. We demonstrate that this max-variant game has the polynomial expectation property, and the results of Papadimitriou and Roughgarden can thus be applied. We propose ideas for extending these findings to other variants of polymatrix games, as well as briefly address the broader question of necessity for the polynomial expectation property when computing correlated equilibria. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_01343 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Polynomial Expectation Property for Max-Polymatrix Games Dai, Howard Computer Science and Game Theory We address an open problem on the computability of correlated equilibria in a variant of polymatrix where each player's utility is the maximum of their edge payoffs. We demonstrate that this max-variant game has the polynomial expectation property, and the results of Papadimitriou and Roughgarden can thus be applied. We propose ideas for extending these findings to other variants of polymatrix games, as well as briefly address the broader question of necessity for the polynomial expectation property when computing correlated equilibria. |
| title | Polynomial Expectation Property for Max-Polymatrix Games |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2506.01343 |