Breaking Exponential Complexity in Games of Ordered Preference: A Tractable Reformulation

Dong Ho Lee; Jingqi Li; Lasse Peters; Georgios Bakirtzis; David Fridovich-Keil

cs.GTMar 27, 2026

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

Abstract

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

Panel of Figure 1 — 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.

Level ( $K$ )	R	C	R	C	R	C	R	C
	System size		Variable size		Solve time (s) for Quad. GOOP		Solve time (s) for Nonquad. GOOP
2	132	168	128	136	$0.05\pm 0.06$	$0.07\pm 0.06$	$0.08\pm 0.12$	$0.19\pm 0.21$
3	188	368	244	304	$0.17\pm 0.16$	$0.34\pm 0.12$	$0.53\pm 0.44$	$1.11\pm 0.35$
4	244	800	408	672	$0.32\pm 0.32$	$2.32\pm 2.20$	$0.54\pm 0.56$	$5.09\pm 2.82$
5	300	1728	620	1472	$0.60\pm 0.75$	Failed	$0.96\pm 0.88$	Failed
6	356	3712	880	3200	$1.19\pm 0.80$	Failed	$1.79\pm 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 $\rho$ . The curve and the shaded area denote the mean and the variance of $\log_{10}(\|\mathcal{K}_{\rho}(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

z_{\mathrm{complete}}

and

z_{\mathrm{reduced}}

, obtained from the complete and reduced KKT systems, respectively.

Panel of Figure 4 — 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 $\rho$ is reduced following a geometric schedule $\{1,2^{-1},\dots,2^{-10}\}$ ; the reported results correspond to $\rho=2^{-10}$ .

Nash Equilibrium Computation

Nash equilibrium computation develops algorithms for finding stable strategies in strategic, stochastic, and imperfect-information games.

See all 69 papers

Variable Bound Tightening for Nash Equilibrium Computation in Multiplayer Imperfect-Information Games
Jun 24, 2026Sam GanzfriedNash Equilibrium Branch and Bound
Ganzfried Research, Cornell University
Quadratic Programming Approach for Nash Equilibrium Computation in Multiplayer Imperfect-Information Games
Sep 30, 2025Sam GanzfriedNash Equilibrium Imperfect-Information Games
Ganzfried Research
Nash without Numbers: A Social Choice Approach to Mixed Equilibria in Context-Ordinal Games
May 8, 2026Ian Gemp, Crystal Qian, Marc Lanctot +1Nash Equilibrium Social Choice Theory
Google DeepMind · New York, NY, USA · New York, NY USA +2

Jun 24, 2026J/K move · Enter open · S save

Variable Bound Tightening for Nash Equilibrium Computation in Multiplayer Imperfect-Information Games

Sam Ganzfried

Ganzfried Research, Cornell University

Nash Equilibrium Branch and Bound Imperfect-Information Games Constrained Optimization Nash Equilibrium Computation

Open paper AskPDF arXiv

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.

Abstract

Nash Equilibrium Computation

Explore similar work

Variable Bound Tightening for Nash Equilibrium Computation in Multiplayer Imperfect-Information Games

Quadratic Programming Approach for Nash Equilibrium Computation in Multiplayer Imperfect-Information Games

Nash without Numbers: A Social Choice Approach to Mixed Equilibria in Context-Ordinal Games