On the Equivalence of Zero-Sum Games and Conic Programs
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2023
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915932419391488 |
|---|---|
| author | Dimou, Nikos |
| author_facet | Dimou, Nikos |
| contents | We prove the almost equivalence of the minimax theorem and the strong duality theorem for a large class of games and conic programs. The previous fundamental results on the equivalence of linear programming and two-player zero-sum games with simplex-strategy sets are extended to Banach spaces, and a comprehensive framework unifying two-player zero-sum games and conic linear programs is established. Specifically, we show that for every zero-sum game with a bilinear payoff function and strategy sets that represent bases of convex cones, the minimax equality holds and its game value and Nash equilibria can be found by solving a primal-dual pair of conic programs. Conversely, the minimax theorem for the same class of games "almost always" implies strong duality of conic linear programming. In fact, we give a game-dependent characterization of strict feasibility, and show that minimax is equivalent to a generalized version of Ville's theorem of the alternative. Several well-established game classes are embedded in the introduced model, including (i) semi-infinite, (ii) semidefinite, (iii) quantum, (iv) time-dependent, and (v) polynomial games, as well as (vi) the mixed extension of any continuous game with compact strategy sets. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2302_03066 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On the Equivalence of Zero-Sum Games and Conic Programs Dimou, Nikos Optimization and Control Computer Science and Game Theory 90C45, 90C46, 91A05, 46N10 We prove the almost equivalence of the minimax theorem and the strong duality theorem for a large class of games and conic programs. The previous fundamental results on the equivalence of linear programming and two-player zero-sum games with simplex-strategy sets are extended to Banach spaces, and a comprehensive framework unifying two-player zero-sum games and conic linear programs is established. Specifically, we show that for every zero-sum game with a bilinear payoff function and strategy sets that represent bases of convex cones, the minimax equality holds and its game value and Nash equilibria can be found by solving a primal-dual pair of conic programs. Conversely, the minimax theorem for the same class of games "almost always" implies strong duality of conic linear programming. In fact, we give a game-dependent characterization of strict feasibility, and show that minimax is equivalent to a generalized version of Ville's theorem of the alternative. Several well-established game classes are embedded in the introduced model, including (i) semi-infinite, (ii) semidefinite, (iii) quantum, (iv) time-dependent, and (v) polynomial games, as well as (vi) the mixed extension of any continuous game with compact strategy sets. |
| title | On the Equivalence of Zero-Sum Games and Conic Programs |
| topic | Optimization and Control Computer Science and Game Theory 90C45, 90C46, 91A05, 46N10 |
| url | https://arxiv.org/abs/2302.03066 |