The Complexity of Min-Max Optimization with Product Constraints
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917247976472576 |
|---|---|
| author | Bernasconi, Martino Castiglioni, Matteo |
| author_facet | Bernasconi, Martino Castiglioni, Matteo |
| contents | We study the computational complexity of the problem of computing local min-max equilibria of games with a nonconvex-nonconcave utility function $f$. From the work of Daskalakis, Skoulakis, and Zampetakis [DSZ21], this problem was known to be hard in the restrictive case in which players are required to play strategies that are jointly constrained, leaving open the question of its complexity under more natural constraints. In this paper, we settle the question and show that the problem is PPAD-hard even under product constraints and, in particular, over the hypercube. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_04665 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | The Complexity of Min-Max Optimization with Product Constraints Bernasconi, Martino Castiglioni, Matteo Computational Complexity Computer Science and Game Theory We study the computational complexity of the problem of computing local min-max equilibria of games with a nonconvex-nonconcave utility function $f$. From the work of Daskalakis, Skoulakis, and Zampetakis [DSZ21], this problem was known to be hard in the restrictive case in which players are required to play strategies that are jointly constrained, leaving open the question of its complexity under more natural constraints. In this paper, we settle the question and show that the problem is PPAD-hard even under product constraints and, in particular, over the hypercube. |
| title | The Complexity of Min-Max Optimization with Product Constraints |
| topic | Computational Complexity Computer Science and Game Theory |
| url | https://arxiv.org/abs/2602.04665 |