The Zero Regrets Algorithm: Optimizing over Pure Nash Equilibria via Integer Programming
提出零遗憾算法，利用整数规划技术计算整数规划博弈中的纳什均衡，能高效求解、枚举和选择均衡，并在多个实际问题中验证了有效性。
Designing efficient algorithms to compute Nash equilibria poses considerable challenges in algorithmic game theory and optimization. In this work, we employ integer programming techniques to compute Nash equilibria in integer programming games, a class of simultaneous and noncooperative games in which each player solves a parameterized integer program. We introduce zero regrets, a general and efficient cutting-plane algorithm to compute, enumerate, and select Nash equilibria. Our framework leverages the concept of equilibrium inequality, an inequality valid for any Nash equilibrium, and the associated equilibrium separation oracle. We evaluate our algorithmic framework on a wide range of practical and methodological problems from the literature, providing a solid benchmark against the existing approaches. History: Accepted by Andrea Lodi, Area Editor for Design & Analysis of Algorithms – Discrete. Supplemental Material: The online supplement is available at https://doi.org/10.1287/ijoc.2022.0282 .