提出可多项式求解的期望变分不等式，突破传统难题。
Expected Variational Inequalities
- 用期望约束替代原问题，将难解变分不等式转为可高效求解。
- 在一般非单调算子下，首次实现多项式时间求解。
- 适用于博弈、耦合约束、非凹效用等多类场景，通用性强。
变分不等式（VIs）涵盖工程、经济和机器学习等多个领域的基础问题，但其强表达力带来计算上的不可行性。本文引入并分析一种自然松弛——期望变分不等式（EVIs），目标是找到一个满足VI约束期望值的分布。通过借鉴博弈论最新技术，我们证明：与传统VIs不同，即使在一般（非单调）算子下，EVIs也可在多项式时间内求解。EVIs捕捉了核心的关联均衡概念，且适用范围远超博弈场景。该框架还统一并推广了多个现有结果，包括平滑博弈、带耦合约束博弈及非凹效用博弈等情形。
原文摘要 · Abstract (English)
Variational inequalities (VIs) encompass many fundamental problems in diverse areas ranging from engineering to economics and machine learning. However, their considerable expressivity comes at the cost of computational intractability. In this paper, we introduce and analyze a natural relaxation -- which we refer to as expected variational inequalities (EVIs) -- where the goal is to find a distribution that satisfies the VI constraint in expectation. By adapting recent techniques from game theory, we show that, unlike VIs, EVIs can be solved in polynomial time under general (nonmonotone) operators. EVIs capture the seminal notion of correlated equilibria, but enjoy a greater reach beyond games. We also employ our framework to capture and generalize several existing disparate results, including from settings such as smooth games, and games with coupled constraints or nonconcave utilities.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。