arXiv:2606.17000cs.CCcs.GT2026-06被引 2
证明了二次多项式极小极大优化难解，连零和博弈也难算。
The Complexity of Min-Max Optimization for Quadratic Polynomials
- 用复杂性理论证明极小极大点难求
- 即使变量少、近似精度不高也难解
- 适合研究博弈与优化复杂性的学者
我们证明，对超立方体上的二次多项式进行极小极大优化，计算近似驻点是PPAD难问题。这一结论在多项式为双线性、每个变量最多出现在三个单项式中、且近似因子为多项式倒数时依然成立。作为直接推论，我们首次得到了双人零和多矩阵博弈的PPAD难解性结果。
原文摘要 · Abstract (English)
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.
极小极大优化复杂性理论博弈论
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。