Breaking Exponential Complexity in Games of Ordered Preference: A Tractable Reformulation
Authors: Dong Ho Lee, Jingqi Li, Lasse Peters, Georgios Bakirtzis, David Fridovich-Keil
Organizations: Aerospace Engineering and Engineering Mechanics, University of Texas at Austin, Austin, TX 78712-1221 USA · Oden Institute for Computational Engineering and Sciences, University of Texas at Austin, Austin, TX 78712-1221 USA · Department of Mechanical Engineering, UC Berkeley, Berkeley, CA 94720-1740 USA · LTCI, Télécom Paris, Institut Polytechnique de Paris, France
Games of ordered preference (GOOPs) model multi-player equilibrium problems in which each player maintains a distinct hierarchy of strictly prioritized objectives. Existing approaches solve GOOPs by deriving and enforcing the necessary optimality conditions that characterize lexicographically constrained Nash equilibria through a single-level reformulation. However, the number of primal and dual variables in the resulting KKT system grows exponentially with the number of preference levels, leading to severe scalability challenges. We derive a compact reformulation of these necessary conditions that preserves the essential primal stationarity structure across hierarchy levels, yielding a "reduced" KKT system whose size grows polynomially with both the number of players and the number of preference levels. The reduced system constitutes a relaxation of the complete KKT system, yet it remains a valid necessary condition for local GOOP equilibria. For GOOPs with quadratic objectives and linear constraints, we prove that the primal solution sets of the reduced and complete KKT systems coincide. More generally, for GOOPs with arbitrary (but smooth) nonlinear objectives and constraints, the reduced KKT conditions recover all local GOOP equilibria but may admit spurious non-equilibrium solutions. We introduce a second-order sufficient condition to certify when a candidate point corresponds to a local GOOP equilibrium. We also develop a primal-dual interior-point method for computing a local GOOP equilibrium with local quadratic convergence. The resulting framework enables scalable and efficient computation of GOOP equilibria beyond the tractable range of existing exponentially complex formulations.
Figures & tables
Figure 1: ( Left ) For quadratic objectives and linear constraints, under the assumptions of Section 3.1 , the reduced and complete KKT systems share the same primal solution set, and every GOOP equilibrium is SOSC-qualified (hence the corresponding sets coincide). ( Right ) For general smooth GOOPs, the reduced KKT primal solution set is a relaxation (superset) of the complete KKT primal solution set, which contains the GOOP equilibria; theorem 11 certifies a subset of such equilibria.
System size
Variable size
Solve time (s) for Quad. GOOP
Solve time (s) for Nonquad. GOOP
Level ( K )
R
C
R
C
R
C
R
C
2
132
168
128
136
0.05±0.06
0.07±0.06
0.08±0.12
0.19±0.21
3
188
368
244
304
0.17±0.16
0.34±0.12
0.53±0.44
1.11±0.35
4
244
800
408
672
0.32±0.32
2.32±2.20
0.54±0.56
5.09±2.82
5
300
1728
620
1472
0.60±0.75
Failed
0.96±0.88
Failed
6
356
3712
880
3200
1.19±0.80
Failed
1.79±3.01
Failed
Table 1: Comparison of reduced and complete KKT systems across preference levels. R denotes the reduced KKT system, and C denotes the complete KKT system.
Figure 2: Convergence of Algorithm 1 for reduced and complete KKT systems under varying ρ . The curve and the shaded area denote the mean and the variance of log10(∥Kρ(y)∥2) , respectively.
Figure 3: Monte Carlo comparison over 100 randomly generated GOOP instances with nonquadratic objectives and nonlinear constraints, showing close agreement between primal solutions zcomplete and zreduced , obtained from the complete and reduced KKT systems, respectively.
Figure 4: Two-player intersection scenario solved using the reduced KKT system. We use the four-preference setup as in [ 19 ] . Player 1 (blue) prioritizes reaching its goal and accelerates beyond the speed limit. Player 2 (red) prioritizes obeying the speed limit and proceeds toward its goal while remaining within the limit. The convergence plot shows local quadratic convergence of the KKT residual to 10−8 . The homotopy parameter ρ is reduced following a geometric schedule {1,2−1,…,2−10} ; the reported results correspond to ρ=2−10 .
There has been significant recent progress in algorithms for approximation of Nash equilibrium in large two-player zero-sum imperfect-information games and exact computation of Nash equilibrium in multiplayer strategic-form games. While counterfactual regret minimization and fictitious play are scalable to large games and have convergence guarantees in two-player zero-sum games, they do not guarantee convergence to Nash equilibrium in multiplayer games. Recently, an approach has been presented for exact computation of Nash equilibrium in multiplayer imperfect-information games that solves a quadratically constrained program based on a nonlinear complementarity problem formulation derived from the sequence-form game representation. This formulation was solved using Gurobi's nonconvex quadratic solver, which employs spatial branch-and-bound to iteratively refine variable bounds by solving convex relaxations of bilinear terms via McCormick envelopes. During presolve, Gurobi introduces auxiliary variables and, in some cases, binary variables, leading to an internal MIQCP reformulation. This approach was demonstrated to outperform prior algorithms from the Gambit software suite and quickly solve three-player Kuhn poker after removal of dominated actions; however, the algorithm was not able to solve the full version of the game within 24 hours. In this paper, we derive finite bounds on slack and multiplier variables in the nonlinear complementarity formulation. These bounds strengthen the convex relaxations used within spatial branch-and-bound and lead to substantial computational improvements. We demonstrate the impact of the proposed bounds on exact Nash equilibrium computation in three-player Kuhn poker.
There has been significant recent progress in algorithms for approximation of Nash equilibrium in large two-player zero-sum imperfect-information games and exact computation of Nash equilibrium in multiplayer strategic-form games. While counterfactual regret minimization and fictitious play are scalable to large games and have convergence guarantees in two-player zero-sum games, they do not guarantee convergence to Nash equilibrium in multiplayer games. We present an approach for exact computation of Nash equilibrium in multiplayer imperfect-information games that solves a quadratically-constrained program based on a nonlinear complementarity problem formulation from the sequence-form game representation. This approach capitalizes on recent advances for solving nonconvex quadratic programs. Our algorithm is able to quickly solve three-player Kuhn poker after removal of dominated actions. Of the available algorithms in the Gambit software suite, only the logit quantal response approach is successfully able to solve the game; however, the approach takes longer than our algorithm and also involves a degree of approximation. Our formulation also leads to a new approach for computing Nash equilibrium in multiplayer strategic-form games which we demonstrate to outperform a previous quadratically-constrained program formulation.
Nash equilibrium serves as a fundamental mathematical tool in economics and game theory. However, it classically assumes knowledge of player utilities, whereas economics generally regards preferences as more fundamental. To leverage equilibrium analysis in strategic scenarios, one must first elicit numerical utilities consistent with player preferences, a delicate and time-consuming process. In this work, we forgo precise utilities and generalize the Nash equilibrium to a setting where we only assume a player is capable of providing an ordinal ranking of their actions within the context of other players' joint actions. The key technical challenge is to rethink the definition of a best-response. While the classical definition identifies actions maximizing expected payoff, we naturally look towards social choice theory for how to aggregate preferences to identify the most preferred actions. We define this generalized notion of a context-ordinal Nash equilibrium, establish its existence under mild conditions on aggregation methods, introduce notions of regularization, approximation, and regret, explore complexity for simple settings, and develop learning rules for computing such equilibria. In doing so, we provide a generalization of Nash equilibrium and demonstrate its direct applicability to elicited preferences in human experiments.
Ian Gemp, Crystal Qian, Marc Lanctot +1
Google DeepMind · New York, NY, USA · New York, NY USA +2