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

Dong Ho Lee, Jingqi Li, Lasse Peters, Georgios Bakirtzis, David Fridovich-Keil · 2026

Read Breaking Exponential Complexity in Games of Ordered Preference: A Tractable Reformulation by Dong Ho Lee, Jingqi Li, Lasse Peters, Georgios Bakirtzis, David Fridovich-Keil (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-26950.txt.

Introduction

Lee and co-authors make games of ordered preference far cheaper to solve. In these games, each player ranks several objectives in a strict priority order. The standard equilibrium conditions form a KKT system that grows exponentially with preference levels. The authors derive a reduced system that keeps the key stationarity structure. Its size grows only polynomially in players and levels. For quadratic games with linear constraints, the reduced and full systems share the same solutions. A second-order test certifies equilibria in the general smooth case.

Catalog record

CREATORDong Ho Lee, Jingqi Li, Lasse Peters, Georgios Bakirtzis, David Fridovich-Keil
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE89286
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.26950

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Breaking Exponential Complexity in Games of Ordered Preference: A Tractable Reformulation Thanks: This is a preprint manuscript. Dong Ho Lee, Jingqi Li, Lasse Peters, Georgios Bakirtzis, David Fridovich-Keil 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 Karush-Kuhn-Tucker (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. keywords Lexicographic preferences, hierarchical games, mathematical programming Funding. D.H. Lee, J. Li, and D. Fridovich-Keil are partially supported by the Army Research Laboratory under Cooperative Agreements W911NF-23-2-0011 and W911NF-25-2-0021, and by the National Science Foundation under Grants 2211548 and 2336840. G. Bakirtzis is partially supported by the academic and research chair Architecture des Systèmes Complexes through the following partners: Dassault Aviation, Naval Group, Dassault Systèmes, KNDS France, Agence de l’Innovation de Défense, and Institut Polytechnique de Paris. † † runningheads: Breaking Exponential Complexity in GOOP / D. Lee, J. Li, L. Peters, G. Bakirtzis, and D. Fridovich-Keil MSC 49K99, 91A65, 90C99 1 Introduction Making decisions under strictly ordered, potentially conflicting, objectives is a central problem in optimization. In many applications—ranging from autonomous driving [ 33 ] and power systems [ 2 ] to supply chains [ 32 ] —higher-priority objectives must be satisfied before lower-priority ones are considered. Lexicographic optimization [ 16 , 2 , 4 ] provides a natural framework for such problems by imposing a strict priority ordering among multiple objectives for a single decision-maker. In contrast, classical multi-objective optimization [ 15 , 13 , 9 , 24 ] studies competing objectives for a single decision-maker through Pareto-optimality [ 25 , 17 ] and methods such as weighted sums [ 12 , 13 ] , \epsilon -constraint formulations [ 14 ] , and goal programming [ 3 , 17 ] . In these approaches, improving one objective may degrade another, and no intrinsic priority structure is imposed. We consider the multi-agent extension of the lexicographic setting, namely games of ordered preference (GOOPs) [ 19 , 6 ] , in which each player solves a lexicographically constrained, coupled optimization problem. GOOPs inherit aspects of noncooperative game theory [ 1 , 10 , 7 ] , but differ fundamentally from standard generalized Nash games [ 8 , 18 , 20 ] : each player faces a hierarchy of ordered objectives rather than a single objective. This hierarchical structure makes the computation of equilibrium solutions substantially more challenging, since a GOOP equilibrium must encode both coupling across players and lexicographic optimality within each player’s problem. A natural route for modeling and solving GOOPs is through multilevel optimization [ 5 , 22 , 29 , 31 ] , where lower-level (high-priority) optimality conditions define upper-level (low-priority) feasibility. The existing solution strategy [ 19 ] adopts this perspective and recursively replaces lower-level problems with their KKT conditions, thereby obtaining a single-level mathematical program with complementarity constraints (MPCC) [ 30 , 23 , 27 ] . However, the MPCC reformulation introduces lower-level dual variables that become primal variables at the upper levels. The expanding set of primal variables causes the number of variables and conditions to grow exponentially with the number of preference levels, and severely limits scalability. By contrast, lexicographic optimization enforces higher-priority optimality by treating objectives sequentially and constraining each subproblem so as not to degrade higher-priority, objective values. However, the principle in lexicographic optimization does not extend readily to noncooperative equilibrium settings, where each player’s feasible set and objectives depend on the decisions of the others. In this paper, we show that the exponential growth of the existing GOOP reformulation is not intrinsic to the equilibrium conditions, but rather a consequence of recursively flattening the problem hierarchy. We derive a reduced KKT system that preserves the nested primal stationarity structure while avoiding redundant dual variable propagation. The proposed system grows polynomially in the number of players and preference levels. Our contributions are threefold. We first show that the reduced system is a relaxation of the complete KKT system. Second, for quadratic GOOPs with linear constraints, we prove primal solution equivalence between the reduced and complete KKT systems. For GOOPs with arbitrary (but smooth) nonlinear objectives and constraints, we show that the reduced KKT system may potentially admit additional solutions. Accordingly, we establish a second-order sufficient condition that certifies local GOOP equilibria. Finally, we develop a primal-dual interior-point method for the reduced KKT system and prove its local quadratic convergence. 2 Games of Ordered Preference In this section, we formalize games of ordered preference (GOOPs) , define the local generalized Nash solution concept, and derive corresponding first-order necessary conditions. 2.1 Local Generalized Nash Equilibrium for GOOP We consider a non-cooperative GOOP involving N players. Let [N]:=\{1,2,...,N\} . For a player i\in[N] , we denote their decision variables as a real-valued vector z^{i}\in\mathbb{R}^{n^{i}} . We define the collection of all players’ variables as z\coloneqq\{z^{1},\dots,z^{N}\} , and the collection of all players’ variables except those of player i as z^{\neg i}\coloneqq\{z^{j}\}_{j\neq i} . When convenient, we identify z and z^{\neg i} as vectors, i.e., z=[(z^{1})^{\top},\dots,(z^{N})^{\top}]^{\top}\in\mathbb{R}^{n} , where n\coloneqq\sum_{i=1}^{N}n^{i} , and z^{\neg i}=[(z^{j})^{\top}]^{\top}_{j\neq i}\in\mathbb{R}^{n-n^{i}} . Each player has a hierarchy of strictly prioritized objectives, which we refer to as preferences . We denote the number of preference levels for player i as K^{i}\in\mathbb{N} . Unless stated otherwise, players may have different numbers of preference levels, i.e., K^{i}\neq K^{j} for i\neq j . We denote the primal variable of player i at preference level k as z_{k}^{i}\in\mathbb{R}^{n^{i}} . Player i ’s decision variable is common to all preference levels; throughout, we may suppress the level index for the top level ( k=1 ) and define z^{i}\coloneqq z_{1}^{i} to denote player i ’s top-level decision variable. Each preference level k is associated with a real-valued objective function J^{i}_{k}(z_{k}^{i},z^{\neg i}), where z^{\neg i} denotes the collection of the other players’ top-level variables. Using \arg\min to denote the argument of local minimizers, we state player i ’s problem in the GOOP framework: \displaystyle\quad\min_{z^{i}_{1}}\quad \displaystyle J^{i}_{1}(z^{i}_{1},z^{\neg i}) (1a) \displaystyle\mathrm{s.t.}~\quad \displaystyle z^{i}_{1}\in\mathop{\rm arg\,min}_{z^{i}_{2}}\>J^{i}_{2}(z^{i}_{2},z^{\neg i}) (1b)

Read the complete text