The Complexity of Min-Max Optimization for Quadratic Polynomials
English summary
This paper proves that computing an approximate stationary point of a min-max optimization problem over the hypercube is PPAD-hard when the objective is a quadratic polynomial. The hardness result holds even under strong restrictions: the polynomials are multilinear, each variable appears in at most three monomials, and the desired approximation factor is only inverse polynomial. As a direct corollary, the authors obtain the first PPAD-hardness results for two-team zero-sum polymatrix games. This establishes a fundamental computational barrier for a simple class of min-max problems.
Chinese summary
本文证明了在超立方体上计算二次多项式极小极大优化问题的近似稳定点是PPAD困难的。即使对多项式施加严格限制——要求多项式是多线性的、每个变量至多出现在三个单项式中，且允许的近似因子仅为逆多项式——该困难性仍然成立。作为直接推论，作者首次给出了双团队零和多矩阵博弈的PPAD困难性结果，为这类简单极小极大问题确立了根本的计算障碍。
Key points
Proved PPAD-hardness for finding approximate stationary points of min-max quadratic polynomial optimization over the hypercube.
证明了在超立方体上寻找二次多项式极小极大优化的近似稳定点是PPAD困难的。
Hardness persists even when the polynomials are multilinear, each variable appears in ≤3 monomials, and approximation factor is inverse polynomial.
困难性在多项式为多线性、每个变量至多出现在3个单项式中、且近似因子仅为逆多项式的限制下依然成立。
Obtained the first PPAD-hardness results for two-team zero-sum polymatrix games as a direct consequence.
作为直接推论，首次得到了双团队零和多矩阵博弈的PPAD困难性结果。