Combinatorics of Correlated Equilibria
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917598370725888 |
|---|---|
| author | Brandenburg, Marie-Charlotte Hollering, Benjamin Portakal, Irem |
| author_facet | Brandenburg, Marie-Charlotte Hollering, Benjamin Portakal, Irem |
| contents | We study the correlated equilibrium polytope $P_G$ of a game $G$ from a combinatorial point of view. We introduce the region of full-dimensionality for this class of polytopes and prove that it is a semialgebraic set for any game. Using a stratification via oriented matroids, we propose a structured method for describing the possible combinatorial types of $P_G$, and show that for $(2 \times n)$-games, the algebraic boundary of the stratification is a union of coordinate hyperplanes and binomial hypersurfaces. Finally, we provide a computational proof that there exists a unique combinatorial type of maximal dimension for generic $(2 \times 3)$-games. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2209_13938 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Combinatorics of Correlated Equilibria Brandenburg, Marie-Charlotte Hollering, Benjamin Portakal, Irem Combinatorics Computer Science and Game Theory Algebraic Geometry 14P10, 52B05, 52B40, 52C40, 91A05, 91A10 We study the correlated equilibrium polytope $P_G$ of a game $G$ from a combinatorial point of view. We introduce the region of full-dimensionality for this class of polytopes and prove that it is a semialgebraic set for any game. Using a stratification via oriented matroids, we propose a structured method for describing the possible combinatorial types of $P_G$, and show that for $(2 \times n)$-games, the algebraic boundary of the stratification is a union of coordinate hyperplanes and binomial hypersurfaces. Finally, we provide a computational proof that there exists a unique combinatorial type of maximal dimension for generic $(2 \times 3)$-games. |
| title | Combinatorics of Correlated Equilibria |
| topic | Combinatorics Computer Science and Game Theory Algebraic Geometry 14P10, 52B05, 52B40, 52C40, 91A05, 91A10 |
| url | https://arxiv.org/abs/2209.13938 |