The Cut-and-Play Algorithm: Computing Nash Equilibria via Outer Approximations
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2021
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911863630987264 |
|---|---|
| author | Carvalho, Margarida Dragotto, Gabriele Lodi, Andrea Sankaranarayanan, Sriram |
| author_facet | Carvalho, Margarida Dragotto, Gabriele Lodi, Andrea Sankaranarayanan, Sriram |
| contents | We introduce Cut-and-Play, a practically-efficient algorithm for computing Nash equilibria in simultaneous non-cooperative games where players decide via nonconvex and possibly unbounded optimization problems with separable payoff functions. Our algorithm exploits an intrinsic relationship between the equilibria of the original nonconvex game and the ones of a convexified counterpart. In practice, Cut-and-Play formulates a series of convex approximations of the game and iteratively refines them with cutting planes and branching operations. Our algorithm does not require convexity or continuity of the player's optimization problems and can be integrated with existing optimization software. We test Cut-and-Play on two families of challenging nonconvex games involving discrete decisions and bilevel problems, and we empirically demonstrate that it efficiently computes equilibria while outperforming existing game-specific algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2111_05726 |
| institution | arXiv |
| publishDate | 2021 |
| record_format | arxiv |
| spellingShingle | The Cut-and-Play Algorithm: Computing Nash Equilibria via Outer Approximations Carvalho, Margarida Dragotto, Gabriele Lodi, Andrea Sankaranarayanan, Sriram Optimization and Control Computer Science and Game Theory We introduce Cut-and-Play, a practically-efficient algorithm for computing Nash equilibria in simultaneous non-cooperative games where players decide via nonconvex and possibly unbounded optimization problems with separable payoff functions. Our algorithm exploits an intrinsic relationship between the equilibria of the original nonconvex game and the ones of a convexified counterpart. In practice, Cut-and-Play formulates a series of convex approximations of the game and iteratively refines them with cutting planes and branching operations. Our algorithm does not require convexity or continuity of the player's optimization problems and can be integrated with existing optimization software. We test Cut-and-Play on two families of challenging nonconvex games involving discrete decisions and bilevel problems, and we empirically demonstrate that it efficiently computes equilibria while outperforming existing game-specific algorithms. |
| title | The Cut-and-Play Algorithm: Computing Nash Equilibria via Outer Approximations |
| topic | Optimization and Control Computer Science and Game Theory |
| url | https://arxiv.org/abs/2111.05726 |