The Complexity of Min-Max Optimization for Quadratic Polynomials
Establishes fundamental hardness results for min-max optimization problems, impacting the theoretical understanding of computational complexity in game theory and optimization.
The paper proves that computing approximate stationary points of min-max optimization over the hypercube is PPAD-hard for quadratic polynomials, even under strong restrictions, and obtains the first PPAD-hardness results for two-team zero-sum polymatrix games.
We prove that computing approximate stationary points of min-max optimization over the hypercube is PPAD-hard for quadratic polynomials. This holds even when the polynomials are multilinear, each variable appears in at most three monomials, and the approximation factor is inverse polynomial. As a direct consequence, we obtain the first PPAD-hardness results for two-team zero-sum polymatrix games.