Exponential Lower Bounds on the Double Oracle Algorithm in Zero-Sum 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_ | 1866914791624278016 |
|---|---|
| author | Zhang, Brian Hu Sandholm, Tuomas |
| author_facet | Zhang, Brian Hu Sandholm, Tuomas |
| contents | The double oracle algorithm is a popular method of solving games, because it is able to reduce computing equilibria to computing a series of best responses. However, its theoretical properties are not well understood. In this paper, we provide exponential lower bounds on the performance of the double oracle algorithm in both partially-observable stochastic games (POSGs) and extensive-form games (EFGs). Our results depend on what is assumed about the tiebreaking scheme -- that is, which meta-Nash equilibrium or best response is chosen, in the event that there are multiple to pick from. In particular, for EFGs, our lower bounds require adversarial tiebreaking, whereas for POSGs, our lower bounds apply regardless of how ties are broken. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_06797 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Exponential Lower Bounds on the Double Oracle Algorithm in Zero-Sum Games Zhang, Brian Hu Sandholm, Tuomas Computer Science and Game Theory The double oracle algorithm is a popular method of solving games, because it is able to reduce computing equilibria to computing a series of best responses. However, its theoretical properties are not well understood. In this paper, we provide exponential lower bounds on the performance of the double oracle algorithm in both partially-observable stochastic games (POSGs) and extensive-form games (EFGs). Our results depend on what is assumed about the tiebreaking scheme -- that is, which meta-Nash equilibrium or best response is chosen, in the event that there are multiple to pick from. In particular, for EFGs, our lower bounds require adversarial tiebreaking, whereas for POSGs, our lower bounds apply regardless of how ties are broken. |
| title | Exponential Lower Bounds on the Double Oracle Algorithm in Zero-Sum Games |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2405.06797 |