Paper deep dive
Breaking Exponential Complexity in Games of Ordered Preference: A Tractable Reformulation
Dong Ho Lee, Jingqi Li, Lasse Peters, Georgios Bakirtzis, David Fridovich-Keil
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 97%
Last extracted: 3/31/2026, 1:28:18 AM
Summary
The paper introduces a 'reduced' KKT system for Games of Ordered Preference (GOOPs) to address the exponential complexity of existing formulations. By preserving the primal stationarity structure across hierarchy levels, the reduced system scales polynomially with the number of players and preference levels. The authors prove that for quadratic GOOPs with linear constraints, the reduced and complete KKT systems are equivalent, and they provide a second-order sufficient condition for general nonlinear GOOPs to certify local equilibria.
Entities (4)
Relation Signals (2)
Reduced KKT system → isrelaxationof → Complete KKT system
confidence 100% · The reduced system constitutes a relaxation of the complete KKT system, yet it remains a valid necessary condition for local GOOP equilibria.
Reduced KKT system → reducescomplexityof → Games of Ordered Preference
confidence 95% · The resulting framework enables scalable and efficient computation of GOOP equilibria beyond the tractable range of existing exponentially complex formulations.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2603.26950v1
- Canonical: https://arxiv.org/abs/2603.26950v1
Trouble viewing inline? Open PDF directly →
Full Text
75,753 characters extracted from source content.
Expand or collapse full text
BREAKING EXPONENTIAL COMPLEXITY IN GAMES OF ORDERED PREFERENCE: A TRACTABLE REFORMULATION ∗ DONG HO LEE † , JINGQI LI ‡ , LASSE PETERS § , GEORGIOS BAKIRTZIS ¶ ,AND 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 lexico- graphically 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 re- laxation 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. Key words.Lexicographic preferences, hierarchical games, mathematical programming MSC codes.49K99, 91A65, 90C99 1. Introduction.Making decisions under strictly ordered, potentially conflict- ing, 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. Lexico- graphic optimization [16, 2, 4] provides a natural framework for such problems by im- posing a strict priority ordering among multiple objectives for a single decision-maker. In contrast, classical multi-objective optimization [15, 13, 9, 24] studies competing ob- jectives for a single decision-maker through Pareto-optimality [25, 17] and methods such as weighted sums [12, 13],ε-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, namelygames ∗ This is a preprint manuscript. 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 chairArchitecture des Syst`emes Complexesthrough the following partners: Dassault Aviation, Naval Group, Dassault Syst`emes, KNDS France, Agence de l’Innovation de D ́efense, and Institut Polytechnique de Paris. † Aerospace Engineering and Engineering Mechanics, University of Texas at Austin, Austin, TX 78712-1221 USA (leedh0124@utexas.edu, dfk@utexas.edu. ‡ Oden Institute for Computational Engineering and Sciences, University of Texas at Austin, Austin, TX 78712-1221 USA (jingqi.li@austin.utexas.edu. § Department of Mechanical Engineering, UC Berkeley, Berkeley, CA 94720-1740 USA (lasse.peters@mailbox.org). ¶ LTCI, T ́el ́ecom Paris, Institut Polytechnique de Paris, France (bakirtzis@telecom-paris.fr). 1 This manuscript is for review purposes only. arXiv:2603.26950v1 [cs.GT] 27 Mar 2026 2D. LEE, J. LI, L. PETERS, G. BAKIRTZIS, AND D. FRIDOVICH-KEIL of ordered preference(GOOPs) [19, 6], in which each player solves a lexicographically constrained, coupled optimization problem. GOOPs inherit aspects of noncoopera- tive 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 so- lutions 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 opti- mization [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 con- straints (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 exponen- tially 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 refor- mulation is not intrinsic to the equilibrium conditions, but rather a consequence of recursively flattening the problem hierarchy. We derive areducedKKT system that preserves the nested primal stationarity structure while avoiding redundant dual vari- able 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 ob- jectives and constraints, we show that the reduced KKT system may potentially ad- mit 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 involvingNplayers. Let [N] :=1,2,...,N. For a playeri∈ [N], we denote their decision variables as a real-valued vectorz i ∈R n i . We define the collection of all players’ variables asz : =z 1 ,...,z N , and the collection of all players’ variables except those of playeriasz ¬i : =z j j̸=i . When convenient, we identifyzandz ¬i as vectors, i.e.,z= [(z 1 ) ⊤ ,...,(z N ) ⊤ ] ⊤ ∈R n , wheren : = P N i=1 n i , andz ¬i = [(z j ) ⊤ ] ⊤ j̸=i ∈R n−n i . Each player has a hierarchy of strictly prioritized objectives, which we refer to aspreferences. We denote the number of preference levels for playeriasK i ∈N. Unless stated otherwise, players may have different numbers of preference levels, i.e.,K i ̸=K j fori̸=j. We denote the primal variable of playeriat preference levelkasz i k ∈R n i . Playeri’s decision variable is common to all preference This manuscript is for review purposes only. BREAKING EXPONENTIAL COMPLEXITY IN GOOP3 levels; throughout, we may suppress the level index for the top level (k= 1) and definez i : =z i 1 to denote playeri’s top-level decision variable. Each preference level kis associated with a real-valued objective functionJ i k (z i k ,z ¬i ),wherez ¬i denotes the collection of the other players’ top-level variables. Using arg min to denote the argument oflocalminimizers, we state playeri’s problem in the GOOP framework: min z i 1 J i 1 (z i 1 ,z ¬i )(2.1a) s.t. z i 1 ∈arg min z i 2 J i 2 (z i 2 ,z ¬i )(2.1b) . . . s.t. z i K i −1 ∈arg min z i K i J i K i (z i K i ,z ¬i )(2.1c) s.t. z i K i ∈Z i K i (z ¬i ).(2.1d) The innermost feasible set (at levelK i ) is given by Z i K i (z ¬i ) : = z i h i (z i ,z ¬i ) =0, g i (z i ,z ¬i )≥0 ,(2.2) where0denotes a vector (or matrix) of all zeros of appropriate dimension,h i (z i ,z ¬i )∈ R m i E andg i (z i ,z ¬i )∈R m i I are equality and inequality constraints, respectively. In this paper, we consider the following assumption: Assumption2.1. For each playeri∈[N] and each levelk∈[K i ], we assume the objective functionJ i k (z i ,z ¬i ) is sufficiently differentiable with respect toz i , but not necessarily convex inz i . The innermost feasible setZ i K i (z ¬i ) is compact, and an MPCC-tailored constraint qualification, such as MPCC-linear independence con- straint qualification (LICQ) [30], holds. Under the above assumption, we formally define thelocal generalized Nash equi- libriumfor GOOPs. This definition extends the local generalized Nash equilibrium concept in [10, 28] to the lexicographic setting. Definition2.2 (Local Generalized Nash Equilibrium for GOOPs).A vector z ∗ is a local generalized Nash equilibrium for GOOP (2.1), if for each playeri, the strategyz i∗ is feasible for playeri’s nested problem and there exists anε >0such that (2.3)J i 1 (z i∗ ,z ¬i∗ )≤J i 1 (z i ,z ¬i∗ ),∀z i ∈Z i 1 (z ¬i∗ )s.t.∥z i −z i∗ ∥ 2 ≤ε,∀i∈[N], whereZ i 1 (z ¬i∗ )denotes the top-level feasible set that encodes the lexicographic prefer- ences of playeri. Equivalently, no player can unilaterally locally deviate fromz i∗ and achieve a better top-level objective givenz ¬i∗ while remaining consistent with their hierarchy of preferences. In the rest of this work, we refer to a local generalized Nash equilibrium of a GOOP simply as a local GOOP equilibrium. In the next subsection, building on [19], we review the complete KKT conditions for a local GOOP equilibrium and show that its size grows exponentially with hierarchy depth. This exponential complexity motivates the construction of the reduced KKT system, presented in Section 3, whose size grows polynomially in the number of players and preference levels. 2.2. Complete Necessary Conditions for GOOP Equilibria.The refor- mulation in [19] replaces each lower-level problem in (2.1) with itscompleteKKT This manuscript is for review purposes only. 4D. LEE, J. LI, L. PETERS, G. BAKIRTZIS, AND D. FRIDOVICH-KEIL optimality conditions; we refer to this reformulation as the complete KKT system. Construction proceeds by backward induction for each player, starting from the in- nermost level (highest priority) and recursively deriving the KKT systems for outer levels. For clarity, we denote quantities of the complete KKT system with an overbar to distinguish them from terms in the reduced KKT system introduced in Section 3. Innermost levelk=K i for playeri.Consider the bottom-level problem in (2.1c) and (2.1d). Let ̄ λ i K i and ̄γ i K i represent the dual variables for the equality and inequality constraints, respectively. To simplify the notation for playeri’s Lagrangian, we collect the dual variables ̄ λ i K i and ̄γ i K i as ̄η i K i , i.e., ̄η i K i : = [( ̄ λ i K i ) ⊤ ,( ̄γ i K i ) ⊤ ] ⊤ ∈R m i E +m i I .(2.4) The bottom-level Lagrangian is defined in terms of the primal variables ̄z i , the dual variables ̄η i K i , and the other players’ primal variables ̄z ¬i : ̄ L i K i ̄z i , ̄z ¬i , ̄η i K i =J i K i ̄z i , ̄z ¬i − ̄ λ i⊤ K i h i ̄z i , ̄z ¬i − ̄γ i⊤ K i g i ̄z i , ̄z ¬i .(2.5) Let⊙denote the elementwise product. The bottom-level KKT system is given by: ̄ F i K i ̄z i , ̄z ¬i , ̄η i K i = ∇ ̄z i ̄ L i K i ̄z i , ̄z ¬i , ̄η i K i h i ( ̄z i , ̄z ¬i ) g i ( ̄z i , ̄z ¬i )⊙ ̄γ i K i =0,(2.6) ̄ G i K i ̄z i , ̄z ¬i , ̄γ i K i = g i ( ̄z i , ̄z ¬i ) ̄γ i K i ≥0.(2.7) Upper levelk≤K i −1.At levelk=K i −1, the subproblem inherits the equality constraints (2.6) and inequality constraints (2.7) from the lower levelK i . Under this reformulation, dual variables ̄η i K i introduced at levelK i reappear in the level-(K i −1) problem as additionalprimalvariables; we refer to these asinduced primals. Conse- quently, the Lagrangian stationarity conditions are imposed not only with respect to the original primal variables ̄z i , but also with respect to the induced primals ̄η i K i . This procedure is then applied recursively at each upper level. In what follows, we formalize this construction of the complete KKT system for any levelk. We first introduce shorthand notation for level-indexed variables used in the com- plete KKT system. At each levelk, the complete KKT system introduces dual vari- ables comprising: (i) ̄ ψ i k , the multipliers associated with lower-level Lagrangian sta- tionarity; (i) ̄ φ i k , the multipliers associated with complementarity constraints; (i) ̄ λ i k , the multipliers for innermost-level equality constraintsh i ; and (iv) ̄γ i k , the multipliers for innermost-level inequality constraintsg i and lower-level dual feasibility conditions. We collect these dual variables into ̄η i k : = [( ̄ ψ i k ) ⊤ ,( ̄ φ i k ) ⊤ ,( ̄ λ i k ) ⊤ ,( ̄γ i k ) ⊤ ] ⊤ , and define ̄η i k:K i : = [( ̄η i k ) ⊤ ,...,( ̄η i K i ) ⊤ ] ⊤ and similarly, ̄γ i k:K i : = [( ̄γ i k ) ⊤ ,...,( ̄γ i K i ) ⊤ ] ⊤ . At levelk, ̄η i k+1:K i functions as induced primal variables. The Lagrangian function at levelkis given as ̄ L i k ( ̄z i , ̄z ¬i , ̄η i k:K i ) =J i k ( ̄z i , ̄z ¬i )− ̄ λ i⊤ k h i ( ̄z i , ̄z ¬i )− ̄γ i⊤ k,1 g i ( ̄z i , ̄z ¬i )(2.8) − ̄ ψ i⊤ k ∇ ̄z i ̄ L i k+1 ∇ ̄η i k+2:K i ̄ L i k+1 . . . ∇ ̄z i ̄ L i K i − ̄ φ i⊤ k g i ( ̄z i , ̄z ¬i )⊙ ̄γ i k+1,1 ̄γ i k+2:K i ⊙ ̄γ i k+1,2 . . . g i ( ̄z i , ̄z ¬i )⊙ ̄γ i K i − ̄γ i⊤ k,· ̄γ i k+1 . . . ̄γ i K i . This manuscript is for review purposes only. BREAKING EXPONENTIAL COMPLEXITY IN GOOP5 Using (2.8), the complete KKT system at levelkis ̄ F i k ̄z i , ̄z ¬i , ̄η i k:K i = ∇ ̄z i ̄ L i k ̄z i , ̄z ¬i , ̄η i k:K i ∇ ̄η i k+1:K i ̄ L i k ̄z i , ̄z ¬i , ̄η i k:K i ̄ G i k+1 ( ̄z i , ̄z ¬i , ̄γ i k+1:K i )⊙ ̄γ i k ̄ F i k+1 ̄z i , ̄z ¬i , ̄η i k+1:K i =0,(2.9) ̄ G i k ̄z i , ̄z ¬i , ̄γ i k:K i = " g i ( ̄z i , ̄z ¬i ) ̄γ i k:K i # ≥0.(2.10) Observe that at any levelk≤K i −1, the subproblem inherits all equality (2.9) and inequality (2.10) constraints from the lower levelk+ 1. By this nesting property, the complete KKT system for playeriis achieved at the top level, ( ̄ F i 1 , ̄ G i 1 ), which we denote by ( ̄ F i , ̄ G i ) for convenience. Aggregating ( ̄ F i , ̄ G i ) over players yields the complete KKT system ( ̄ F, ̄ G), which provides necessary conditions for a local GOOP equilibrium under Assumption 2.1. We present the complete KKT system next. Theorem2.3 (Complete necessary conditions, cf. [19]).Suppose that ̄z i∗ is a local solution to playeri’s GOOP problem (2.1) under Assumption2.1. Then, for each levelk∈[K i ], there exist (i) induced primal variables from lower levels ̄η i k+1:K i , and (i) dual variables ̄η i k such that the conditions in(2.9)and(2.10)are satisfied at ̄z i∗ , ̄z ¬i∗ , ̄η i k:K i . We now show that the number of variables and conditions in the complete KKT system scales exponentially in the number of preference levels. Proposition2.4 (Exponential growth of the complete KKT system).Consider playeri’s GOOP problem in (2.1). The complete KKT system( ̄ F i , ̄ G i )has N ̄z i , ̄η i = 2 K i −1 (n i +m i E +K i m i I )variables, N ̄ F i = 2 K i −1 (n i +m i E +K i m i I )equations in ̄ F i (·),and N ̄ G i = 2 K i m i I inequalities in ̄ G i (·). Thus, the number of variables and conditions in the complete KKT system grows exponentially with the number of preference levels. Proof.The proof can be found in the Appendix. The preceding result shows that the complete KKT system ( ̄ F, ̄ G) grows linearly in the number of players but exponentially in the number of preference levels in each player’s hierarchy depth. Section 3 derives a reduced KKT system whose size grows polynomially inboththe number of playersandthe number of preference levels. 3. A Reduced Set of Necessary Conditions for GOOP Equilibria.We derive a new formulation of the KKT system for the GOOP problem (2.1), which avoids the exponential scaling in Theorem 2.3. Unless otherwise noted, we adopt the notation of Subsection 2.2, omitting overbars to denote quantities for the reduced KKT system. We construct the reduced KKT system recursively from the innermost level. Innermost levelk=K i for playeri.For the bottom-level (2.1c) and (2.1d), we define the dual variablesη i K i : = [(λ i K i ) ⊤ ,(γ i K i ) ⊤ ] ⊤ ∈R m i E +m i I .The corresponding This manuscript is for review purposes only. 6D. LEE, J. LI, L. PETERS, G. BAKIRTZIS, AND D. FRIDOVICH-KEIL LagrangianL i K i and KKT system (F i K i ,G i K i ) are L i K i z i ,z ¬i ,η i K i =J i K i z i ,z ¬i −λ i⊤ K i h i z i ,z ¬i −γ i⊤ K i g i z i ,z ¬i ,(3.1) π i K i z i ,z ¬i ,η i K i =∇ z i L i K i z i ,z ¬i ,η i K i ,(3.2) F i K i z i ,z ¬i ,η i K i = ∇ z i L i K i z i ,z ¬i ,η i K i h i (z i ,z ¬i ) g i (z i ,z ¬i )⊙γ i K i =0,(3.3) G i K i z i ,z ¬i ,γ i K i = " g i (z i ,z ¬i ) γ i K i # ≥0.(3.4) At the innermost level, the reduced KKT system (3.3) and (3.4) coincides with the complete KKT system (2.6) and (2.7). Upper levelk≤K i −1.Let the functionπ i k+1 (z i ,z ¬i ,η i k+1:K i ) collect the sta- tionarity conditions of levelsk+ 1,...,K i . We associate the dual variableψ i k with the functionπ i k+1 and the dual variableφ i k only with the complementarity constraints involving the innermost inequality constraintg i . Unlike the complete KKT system, we impose stationarity of the Lagrangian function only with respect to the primal variablez i . Defining the dual variablesη i k : = [(ψ i k ) ⊤ ,(φ i k ) ⊤ ,(λ i k ) ⊤ ,(γ i k ) ⊤ ] ⊤ , we write the corresponding LagrangianL i k and KKT system (F i k ,G i k ) as L i k z i ,z ¬i ,η i k:K i =J i k z i ,z ¬i −λ i⊤ k h i z i ,z ¬i −γ i⊤ k g i z i ,z ¬i (3.5) −ψ i⊤ k π i k+1 z i ,z ¬i ,η i k+1:K i − K i −k X ℓ=1 φ i⊤ k,ℓ g i z i ,z ¬i ⊙γ i K i −ℓ+1 , π i k z i ,z ¬i ,η i k:K i = " ∇ z i L i k z i ,z ¬i ,η i k:K i π i k+1 z i ,z ¬i ,η i k+1:K i # ,(3.6) F i k z i ,z ¬i ,η i k:K i = ∇ z i L i k (z i ,z ¬i ,η i k:K i ) g i z i ,z ¬i ⊙γ i k F i k+1 z i ,z ¬i ,η i k+1:K i , =0,(3.7) G i k z i ,z ¬i ,γ i k:K i = " g i z i ,z ¬i γ i k:K i # ≥0.(3.8) After reordering, the reduced KKT system for playeri(F i ,G i ) can be written as F i z i ,z ¬i ,η i 1:K i = ∇ z i L i 1 (z i ,z ¬i ,η i 1:K i ) . . . ∇ z i L i K i (z i ,z ¬i ,η i K i ) h i (z i ,z ¬i ) g i (z i ,z ¬i )⊙γ i 1 . . . g i (z i ,z ¬i )⊙γ i K i =0,(3.9) G i z i ,z ¬i ,γ i 1:K i = g i (z i ,z ¬i ) γ i 1:K i ≥0.(3.10) This manuscript is for review purposes only. BREAKING EXPONENTIAL COMPLEXITY IN GOOP7 Aggregating (F i ,G i ) over players yields the reduced KKT system (F,G). We characterize the relationship between the solution sets of the complete KKT system ( ̄ F, ̄ G) and reduced KKT system (F,G) in the following result. Theorem3.1 (Reduced KKT system is a relaxation of the complete KKT sys- tem).Suppose Assumption2.1holds. Let( ̄z ∗ , ̄η 1∗ 1:K 1 ,..., ̄η N∗ 1:K N )be a solution to the complete KKT system( ̄ F, ̄ G)in(2.9)and(2.10). Then there exists reduced-system dual variables η i∗ 1:K i N i=1 such that( ̄z ∗ ,η 1∗ 1:K 1 ,...,η N∗ 1:K N )satisfies the reduced KKT system(F,G)in(3.7)and(3.8). Consequently, every primal solution ̄z ∗ of the com- plete KKT system is a solution of the reduced KKT system and the reduced system is a relaxed set of necessary conditions that must hold at any local GOOP equilibrium. Proof.The proof can be found in the Appendix. In Proposition 3.2, we prove that the number of variables and conditions in the reduced KKT system (F,G) scales polynomially with the number of levels, in contrast to the exponential scaling of the complete KKT system. Proposition3.2 (Polynomial growth of reduced KKT system).Consider player i’s GOOP problem in (2.1). The corresponding reduced KKT system(F i ,G i )has N z i ,η i = 1 + K i (K i −1) 2 n i +K i m i E + K i (K i + 1) 2 m i I variables, N F i =K i n i +m i E +K i m i I equations inF i (·),and N G i = (K i + 1)m i I inequalities inG i (·). Thus, the number of variables grows quadratically, and the number of equations and inequalities grows linearly with the number of preference levels for the reduced system. Proof.The proof can be found in the Appendix. The reduction in complexity naturally raises the question of whether the reduced KKT system preserves the set of primal solutions. Theorem 3.1 establishes one direc- tion: every primal solution of the complete KKT system satisfies the reduced KKT system via reconstruction of reduced-system dual variables. We now study the con- verse, namely whether a reduced-system solution can be lifted to a complete-system solution. We prove this converse for quadratic GOOPs. For general GOOPs with non- quadratic objectives and nonlinear constraints, establishing the same equivalence is substantially more challenging, because newly arising higher-order terms break the term-by-term correspondence between the two systems. 3.1. Equivalence Between Complete and Reduced KKT Systems in Quadratic GOOPs.We now establish primal solution equivalence between the complete and reduced KKT systems for quadratic GOOPs. We first treat the equality- constrained case and then extend the result to the inequality-constrained case. 3.1.1. Equality-Constrained Quadratic GOOPs.At any levelk, assume that each playeri’s objective is given by: (3.11)J i k (z) : = 1 2 z ⊤ Q i k z+q i⊤ k z, wherez : = [(z i ) ⊤ ,(z ¬i ) ⊤ ] ⊤ ∈R n ,Q i k ∈R n×n , andq i k ∈R n . We partition the matrix Q i k and vectorq i k into blocksQ i,j,k k ∈R n j ×n k andq i,j k ∈R n j for alli,j,k∈[N]: This manuscript is for review purposes only. 8D. LEE, J. LI, L. PETERS, G. BAKIRTZIS, AND D. FRIDOVICH-KEIL (3.12)Q i k : = Q i,1,1 k ·Q i,1,N k . . . . . . . . . Q i,N,1 k ·Q i,N,N k , q i k : = q i,1 k . . . q i,N k . We impose the following regularity assumption: (3.13)Q i,j,j k ⪰0,∀i,j∈[N], and define the following matrices, which combine components in (3.12): (3.14) Q k := Q 1,1,1 k Q 1,1,2 k ·Q 1,1,N k Q 2,2,1 k Q 2,2,2 k ·Q 2,2,N k . . . . . . . . . . . . Q N,N,1 k Q N,N,2 k ·Q N,N,N k , ˆ Q k : = Q 1,1,1 k . . . Q N,N,N k ,q k : = q 1 k . . . q N k . The matrixQ k consists ofi th -block rows ofQ i k . By (3.13), the block-diagonal matrix ˆ Q k is positive semidefinite, and, thus, playeri’s objective is partially convex inz i , i.e., ∇ 2 z i J i k is a positive semidefinite matrix for each playeri∈[N] at each levelk∈[K]. The linear equality constraints imposed on each playeritake the form of: (3.15)H i z=h i , H i : = H i 1 ·H i N , for matrixH i ∈R m i E ×n , vectorh i ∈R m i E , and submatricesH i j ∈R m i E ×n j . Define (3.16)H : = H 1 1 ·H 1 N . . . . . . . . . H N 1 ·H N N , ˆ H : = H 1 1 . . . H N N , h : = h 1 . . . h N . The matrixHis the block-row concatenation ofH i N i=1 , and the matrix ˆ His a block-diagonal matrix that retains only the diagonal blocksH i i fromH. Assumption3.3 (Full row rank of ˆ H). We assume that the block-diagonal matrix ˆ Hhas full row rank. Equivalently, each diagonal blockH i i has full row rank. Different numbers of preference levels.Players need not share a common number of preference levels. For analytical convenience, we regard each player as having levels k∈ 1,...,KwhereK : = maxK i :i∈[N].If playerihas no levelk(i.e., K i < k≤K), we set the player’s objective toQ i k =0, q i k =0, which retains the regularity assumption (3.13) and positive semidefiniteness of ˆ Q k . Using the objective and constraint terms defined above, we develop the recursive structure of the complete and reduced KKT systems. The key idea in the recursion is that, at each levelk, the complete KKT system matrix ̄ M k (resp., the reduced KKT system matrixM k ) isnested: it contains, as a principal block, the level-(k+ 1) KKT system matrix ̄ M k+1 (resp.,M k+1 ). This enforces the inter-level optimality chain where the upper-level’s decision space is constrained by lower-level optimality. Furthermore, we will repeatedly use the following matrix for the recursive structure: (3.17) ̄ R k : = ˆ Q k 0 00 ̄ R k+1 ̄ R k+1 0 ,∀k∈[K−1], ̄ R K : = ˆ Q K ˆ H ⊤ ˆ H0 . This manuscript is for review purposes only. BREAKING EXPONENTIAL COMPLEXITY IN GOOP9 By construction, ̄ R k is symmetric for allk. To align dimensions between the complete and reduced systems, we use the matrix (3.18)R k+1 : = ̄ R k+1,[1:n,:] 0 , which takes the firstnrows of the matrix ̄ R k+1 and appends zeros below (see (3.20)). Thesenrows correspond to the stationarity condition with respect to the primal variablezin (3.7). Moreover, we augment playerwise lower-level dual variables (e.g., ̄ λ K = [( ̄ λ 1 K ) ⊤ ,...,( ̄ λ N K ) ⊤ ] ⊤ ) and use the notation ̄η K:k+1 = [( ̄η K ) ⊤ ,...,( ̄η k+1 ) ⊤ ] ⊤ . We present the resulting complete and reduced KKT systems next. Recursive structure of the complete KKT system.The conditions (2.9) for a quadratic GOOP at any levelkadmit the following linear representation: (3.19) Q k 0 00 ̄ R k+1 ̄ M k+1 0 |z ̄ M k ̄z ̄η K:k+1 ̄η k |z ̄v k = q k 0 q k+1 |z ̄p k ,∀k∈[K−1]. Recursive structure of the reduced KKT system.The conditions (3.7) for a quadratic GOOP at any levelkcan be expressed as: (3.20) Q k 0 00 R k+1 M k+1 0 |z M k z η K:k+1 η k |z v k = q k 0 q k+1 |z p k ,∀k∈[K−1]. For the base levelk=K, the complete and reduced KKT systems coincide: (3.21) Q K ˆ H ⊤ H0 |z M K = ̄ M K z λ K | z v K = ̄v K = q K h | z p K = ̄p K . For anyk∈[K], the top-left blocks of ̄ M k in (3.19) andM k in (3.20) contain the same Q k term on the leading diagonal; thus, the two matrices share the firstncolumns. Furthermore, because the right-hand-side vector is identical,p k = ̄p k , it follows that ̄ M k ̄v k =M k v k . This fact is the basis for the next result, where we establish equivalence of the primal solution sets via a column-space relationship between ̄ M k andM k . Theorem3.4 (Primal solution equivalence in quadratic GOOPs).Consider a GOOP problem (2.1) with partially convex quadratic objectives (3.11) and linear equal- ity constraints (3.15) under Assumption3.3. Then the following hold: (a)Col R k ⊆Col ̄ R k ,∀k∈[K]. (b) Denote the firstncolumns shared by both matrices ̄ M k andM k asC k , and consider the partition: ̄ M k = C k | ̄ M c k andM k = C k |M c k . Then we have Col M c k ⊆Col ̄ M c k ,∀k∈[K−1]. (c) The primal solution sets of the complete KKT system (3.19) and reduced KKT system (3.20) coincide for allk∈[K]. Proof.The proof can be found in the Appendix. Theorem 3.4 formalizes the structural relationships that ensure coincidence of the primal solution sets (even though the corresponding dual variables may differ). This manuscript is for review purposes only. 10D. LEE, J. LI, L. PETERS, G. BAKIRTZIS, AND D. FRIDOVICH-KEIL 3.1.2. Inequality-Constrained Quadratic GOOP.We now extend the pre- ceding result in Subsection 3.1.1 to quadratic GOOPs with linear inequality con- straints. Consider a GOOP problem (2.1) with quadratic objectives (3.11) and linear equality constraints (3.15). Assume that each playerialso has inequality constraints: (3.22)G i z≥g i , G i : = G i 1 ·G i N , for matrixG i ∈R m i I ×n , vectorg i ∈R m i I and submatricesG i j ∈R m j I ×n j . Define the active set at a solutionz ∗ as (3.23)A i (z ∗ ) : =j|(G i z ∗ −g i ) j = 0. Let matrixG i A i be the submatrix ofG i with rows indexed byA i (z ∗ ), and likewise index the entries of the vectorg i corresponding to active inequality constraints asg i A i . Define the vector ̃ h i : = [h i ;g i A i ]. We present the primal solution equivalence result for the inequality-constrained case in Theorem 3.5. Theorem3.5 (Primal solution equivalence in inequality-constrained quadratic GOOPs).Consider a GOOP problem (2.1) with partially convex quadratic objectives (3.11), linear equality constraints (3.15), and inequality constraints (3.22) for each player. Assume that at every solutionz ∗ , the following hold for playeri: 1. Strict complementarity.At the innermost levelK i , every active inequality constraint has a positive multiplier, i.e.,(G i z ∗ −g i ) j = 0andγ i∗ K i ,j >0,∀j∈A i (z ∗ ). 2. Regularity.The matrix (3.24) ̃ H : = H 1 1 G 1 1,A 1 . . . H N N G N N,A N has full row rank. Equivalently, each diagonal block H i i G i i,A i has full row rank. Then, the set of primal solutions of the reduced KKT system(F,G)coincides with that of the complete KKT system( ̄ F, ̄ G). Proof.The proof can be found in the Appendix. The strict complementarity assumption in Theorem 3.5 provides the nondegen- eracy needed at the innermost level to reconstruct the relevant reduced-system dual variables and initiate the recursive argument via Theorem 3.4 across higher levels. Remark3.6. The assumption of strict complementarity at the innermost level guarantees the local reduction to an equality-constrained subproblem. Characterizing primal equivalence under weaker conditions (even in quadratic GOOPs) remains a challenge as the active set may no longer be uniquely identified by the strictly positive multipliers in these degenerate cases. 3.2. From Quadratic GOOPs to Nonquadratic GOOPs.The preceding analysis in Subsections 3.1.1 and 3.1.2 raises the question of whether the reduced and complete KKT systems continue to share the same primal solution set for general smooth GOOPs with nonquadratic objectives and nonlinear constraints. Empirically, we observe such primal equivalence in Section 6, but a general proof is nontrivial. This manuscript is for review purposes only. BREAKING EXPONENTIAL COMPLEXITY IN GOOP11 The difficulty is structural: when players’ objectives are nonquadratic, higher- order derivatives of inner-level objectives introduce additional terms that destroy the block-wise correspondence between the two KKT systems. Consequently, lower-level dual variables—which generally take different values in the complete and reduced systems—generatedifferent coefficientsin the upper-level nonlinear stationarity con- ditions. This misalignment makes it challenging to reconstruct dual variables for the complete KKT system from a reduced KKT-system primal solution. The coefficient mismatchfirstappears at levelk=K i −2 when playeriis subject only to linear equality constraints (3.15). The multipliers for the complete system are ̄η i K i −2 : = [( ̄ ψ i K i −2 ) ⊤ ,( ̄ λ i K i −2 ) ⊤ ] ⊤ . The complete-system Lagrangian stationarity is ∇ ̄z i ̄ L i K i −2 ( ̄z, ̄η i K i −1:K i , ̄η i K i −2 ) =∇ ̄z i J i K i −2 ( ̄z)− ∇ 2 ̄z i ̄ L i K i −1 ( ̄z, ̄η i K i −1:K i ) ⊤ ̄ ψ i K i −2,1 − ∇ 2 ̄z i ̄ L i K i ( ̄z, ̄η i K i ) ⊤ ̄ ψ i K i −2,2 −H i⊤ i ̄ λ i K i −2 .(3.25) The stationarity equation for the reduced system is obtained analogously. Next, ex- pand the Hessian of the lower level (K i −1) Lagrangian appearing in (3.25): (3.26)∇ 2 ̄z i ̄ L i K i −1 ( ̄z, ̄η i K i −1:K i ) =∇ 2 ̄z i J i K i −1 ( ̄z)− ∇ 3 ̄z i J i K i ( ̄z) ⊤ ̄ ψ i K i −1 . The final term in (3.26) arises from the third derivative of the innermost objective and is weighted by the lower-level dual variable ̄ ψ i K i −1 . Notice that ̄ ψ i K i −1 need not coincide with its reduced KKT system counterpartψ i K i −1 . As a result, the misaligned dual variables generate different coefficients in the upper-level stationarity condition (3.25), i.e.,∇ 2 ̄z i ̄ L i K i −1 ( ̄z, ̄η i K i −1:K i )̸=∇ 2 z i L i K i −1 (z,η i K i −1:K i ). In this way, the com- plete and reduced systems progressively accumulate mismatched coefficients in their stationarity conditions. The proof of Theorem 3.4 relied upon consistent coefficients to align the dual variables between the two KKT systems. Consequently, establishing primal solution equivalence in this more general regime requires a different mechanism to align—or otherwise relate—the relevant dual variables across the two systems. Even in the absence of a primal-equivalence guarantee in general settings, we can still certify the local optimality of candidate solutions for general GOOPs. Accord- ingly, we shift our focus to establishing second-order sufficient conditions (SOSC) that characterize when a candidate solution corresponds to a local equilibrium. 4. Second-order Sufficient Conditions.In this section, we describe sufficient conditions for local optimality in a general GOOP problem. As illustrated in Figure 1, a solution to the reduced KKT system may bespurious: it satisfies the reduced system, yet may fail to satisfy the complete KKT system and therefore cannot correspond to a GOOP equilibrium. We present Theorem 4.1, which provides a set of conditions that each subproblem (for every player and level) must satisfy in order for a candidate solution to the reduced KKT system to be a true local GOOP equilibrium. We proceed along the lines established by [11], in the context of identifying weak local minimizers. Using the reduced KKT system (3.7) and (3.8), we define the lin- earized feasible cone and the critical cone of thek th -level subproblem. First, we define playeri’sk th -level active set at (z ∗ ,η i∗ k+1:K i ) (4.1)A i k (z ∗ ,η i∗ k+1:K i ) : =j:G i k,j (z ∗ ,η i∗ k+1:K i ) = 0, whereG i k refers to playeri’s reduced KKT system (inequalities) in (3.8). The set of This manuscript is for review purposes only. 12D. LEE, J. LI, L. PETERS, G. BAKIRTZIS, AND D. FRIDOVICH-KEIL Reduced KKT primal solutions (= Complete KKT primal solutions) GOOP equilibria (= SOSC-qualified) GOOPs with partially convex quadratic objectives and linear constraints Reduced KKT primal solutions Complete KKT primal solutions GOOP equilibria SOSC-qualified GOOP equilibria GOOPs with general objectives and nonlinear constraints Fig. 1: (Left) For quadratic objectives and linear constraints, under the assumptions of Subsection 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 4.1 certifies a subset of such equilibria. linearized feasible directions is (4.2)L F z ∗ ,η i∗ k+1:K i = d ∇ (z i ,η i k+1:K i ) F i k z ∗ ,η i∗ k+1:K i ⊤ d=0, ∇ (z i ,η i k+1:K i ) G i k,j z ∗ ,η i∗ k+1:K i ⊤ d≥0,∀j∈A i k . The critical cone is then (4.3) C k z ∗ ,η i∗ k+1:K i = n d∈L F ∇ (z i ,η i k+1:K i ) G i k,j z ∗ ,η i∗ k+1:K i ⊤ d=0,∀j∈A i+ k o , whereA i+ k : =j∈A i k (z ∗ ,η i∗ k+1:K i ) :γ i∗ k,j >0, and the feasible neighborhood set is (4.4) P k (ε,δ) := p ∥p−d∥≤εfor some critical directiond∈C k (z ∗ ,η i∗ k+1:K i ), (z i∗ ,η i∗ k+1:K i ) + ̃ δpsatisfies (3.7) and (3.8) for some ̃ δsuch that 0< ̃ δ < δ,and∥p∥= 1. . We now present a second-order sufficient condition for thek th -level subproblem of playeriusing the reduced KKT system. Theorem4.1 (Second-order sufficient condition for local GOOP equilibrium). Let(z i∗ ,z ¬i∗ ,η i∗ 1:K i )be a solution to the reduced KKT system in(3.7)and(3.8)under Assumption2.1. Suppose that, for each levelk∈[K i −1], thek th -level Lagrangian functionL i k is stationary with respect toη i k+1:K i , i.e.,∇ η i k+1:K i L i k (z i∗ ,z ¬i∗ ,η i∗ k+1:K i ) = 0. Suppose that there existsε ′ >0,δ ′ >0such that for everyp∈P k (ε ′ ,δ ′ ), we have (4.5)p ⊤ ∇ 2 z i ,η i k+1:K i L i k (z i∗ ,η i∗ k+1:K i ) +α ̃ δp,η i∗ k p≥0 for allα∈(0,1). Then,z i∗ is a weak (possibly non-isolated) local minimizer for player i’sk th -level subproblem. Furthermore, if (4.5) holds at every levelk∈[K i −1]for every playeri∈[N], then the solution of the reduced KKT system z ∗ ,η 1∗ 1:K 1 ,...,η N∗ 1:K N is a weak local solution of the GOOP problem and satisfies Definition2.2. This manuscript is for review purposes only. BREAKING EXPONENTIAL COMPLEXITY IN GOOP13 Proof.By [11, Theorem 2.1], condition (4.5) implies that (z i∗ ,η i∗ k+1:K i ) is a weak local minimizer of playeri’sk th -level subproblem. Applying this argument recursively fork=K i −1,...,1 shows that playeri’s candidate solution is weakly locally mini- mizing at every level of its hierarchy. Repeating this argument for all playersi∈[N] yields that z ∗ ,η 1∗ 1:K 1 ,...,η N∗ 1:K N is a weak local solution of the GOOP problem. Remark4.2 (Implications of a strict local minimizer). If the inequality in (4.5) holds strictly at levelk, the candidate point corresponds to astrictlocal minimizer at that level. Thus, in a neighborhood of the candidate point, the feasible set for the upper levelsk−1,...,1 collapses to the unique solution of the lower level. As a result, the verification of sufficient conditions at these upper levels becomes unnecessary. Remark4.3 (Limitations of Theorem 4.1). Per Remark 4.2, the second-order con- dition established in Theorem 4.1 checks whether a candidate solution is a weak local minimizer at each level for each player. Unfortunately, the condition is not easily checked, in general. This is true even in the case of single-level optimization as dis- cussed in [11]. Establishing easily verified conditions for this case is an important direction for future work. In the next section, we develop a primal-dual interior-point method and analyze its convergence properties. This common solver framework enables a controlled compari- son in Section 6, where we quantify the computational benefits of solving the reduced system relative to the complete formulation. 5. Primal-Dual Interior Point Method for Reduced KKT System and Convergence Analysis.In this section, we present a numerical approach for solving the reduced KKT conditions. We base our approach on the primal-dual interior point (PDIP) method [26], which we view as a homotopy method [21]. To this end, we (i) introduce nonnegative slack variabless i k K i ,N k=1,i=1 , which transform the inequality constraints into equality constraints for all playersi∈[N] and levelsk∈[K i ], and (i) introduce a scalar homotopy parameterρ >0 to perturb the complementarity slackness condition for each playeriat each levelk: (5.1)g i (z i ,z ¬i )−s i k =0, s i k ⊙γ i k =ρ1, s i k ≥0, γ i k ≥0, where1denotes a vector of all ones. Playeri’s perturbed reduced KKT system is K i ρ z i ,z ¬i ,η i 1:K i ,s i 1:K i = ∇ z i L i 1 (z i ,z ¬i ,η i 1:K i ) . . . ∇ z i L i K i (z i ,z ¬i ,η i K i ) h i (z i ,z ¬i ) g i (z i ,z ¬i )−s i 1 . . . g i (z i ,z ¬i )−s i K i s i 1:K i ⊙γ i 1:K i −ρ1 =0.(5.2) Aggregating (5.2) over all players and definingη : = [(η 1 1:K 1 ) ⊤ ,...,(η N 1:K N ) ⊤ ] ⊤ , s : = [(s 1 1:K 1 ) ⊤ ,...,(s N 1:K N ) ⊤ ] ⊤ , andy : = [z ⊤ ,η ⊤ ,s ⊤ ] ⊤ , we obtain theρ-perturbed reduced KKT system:K ρ (y) = h K i ρ z i ,z ¬i ,η i 1:K 1 ,s i 1:K 1 i N i=1 =0.We present our method in Algorithm 5.1. The algorithm gradually decreases homotopy parameterρ This manuscript is for review purposes only. 14D. LEE, J. LI, L. PETERS, G. BAKIRTZIS, AND D. FRIDOVICH-KEIL Algorithm 5.1Primal-Dual Interior Point Method for the Reduced KKT System Require:Initial homotopy parameterρ, toleranceε, maximum outer iterationsℓ max , line search parameterβ∈(0,1), contraction rateσ∈(0,1), initial solutiony (0) ρ := [z (0) ρ ,η (0) ρ ,s (0) ρ ] withs (0) ρ >0andγ (0) ρ >0. 1:forℓ= 0,1,2,...,ℓ max −1do 2:while∥K ρ (y (ℓ) ρ )∥ 2 > εdo 3:Compute the Newton update direction ∆y ρ =−(∇K ρ (y (ℓ) ρ )) + K ρ (y (ℓ) ρ ) 4:Initialize step sizeα←1 5:while∥K ρ (y (ℓ) ρ +α∆y ρ )∥ 2 >∥K ρ (y (ℓ) ρ )∥ 2 or ˆy : =y (ℓ) ρ +α∆y ρ has a nonpos- itive element in its subvector [ˆs ρ ,ˆγ ρ ]do 6:α←β·α 7:end while 8:Ifα < ε,then declare “line-search failure” and break. 9:y (ℓ) ρ ←y (ℓ) ρ +α∆y ρ . 10:end while 11:y (ℓ+1) ρ ←y (ℓ) ρ andρ←σ·ρ 12:end for 13:returny (ℓ) ρ to zero. For eachρ, at iterationℓ, we computey (ℓ) ρ that drives the homotopy residual to zero, i.e.,∥K ρ (y (ℓ) ρ )∥ 2 →0. Since∇K ρ (y (ℓ) ρ ) is not a square matrix in general, we compute the Newton update direction ∆y ρ using the pseudoinverse (∇K ρ (y (ℓ) ρ )) + , (5.3)∆y ρ := (∇K ρ (y (ℓ) ρ )) + (−K ρ (y (ℓ) ρ )). We then choose a step sizeα (ℓ) ∈(0,1] via backtracking line search and update (5.4)y (ℓ+1) ρ =y (ℓ) ρ +α (ℓ) ∆y ρ . During line search, we ensure that the slack variabless (ℓ) ρ and dual variablesγ (ℓ) ρ remain nonnegative after the update. Using the KKT residual∥K ρ (y (ℓ) ρ )∥ 2 as the merit function, we repeat this procedure until convergence, after whichρis reduced and the process continues. Next, we characterize regularity conditions under which our method is provably convergent in Theorem 5.1. Theorem5.1 (Local quadratic convergence).Lety (0) ρ be an initial point with γ (0) ρ ⊙s (0) ρ ≥ε1, for someε∈(0,ρ). DefineS y ρ :=y ρ :∥K ρ (y ρ )∥ 2 ≤∥K ρ (y (0) ρ )∥ 2 ,γ ρ ⊙ s ρ ≥ε1andL:=∥K ρ (y ρ (0) )∥ 2 . Suppose thatK ρ (y ρ )is in the column space of ∇K ρ (y ρ )for ally ρ ∈S y ρ and that there exists an optimal solutiony ∗ ρ ∈S y ρ such that K ρ (y ∗ ρ ) = 0. Furthermore, suppose that there exist constantsC,D >0such that the pseudoinverse of∇K ρ (y ρ )is upper bounded byD,∥ ∇K ρ (y ρ ) + ∥ 2 ≤D,∀y ρ ∈ S y ρ , and the Jacobian∇K ρ (y ρ )isC-Lipschitz continuous: (5.5)∥∇K ρ (y ρ )−∇K ρ ( ̃y ρ )∥ 2 ≤C∥y ρ − ̃y ρ ∥ 2 ,∀y ρ , ̃y ρ ∈S y ρ . Defineˆα:= min 1, 1 CD 2 L , ρ−ε D 2 L 2 , and∆y ρ =−(∇K ρ (y ρ )) + K ρ (y ρ ). Then, for all y ρ ∈S y ρ , there exists a stepsizeα∈(0,1]such thaty ρ +α∆y ρ ∈S y ρ and (5.6)∥K ρ (y ρ +α∆y ρ )∥ 2 ≤ 1− ˆα 2 ∥K ρ (y ρ )∥ 2 . This manuscript is for review purposes only. BREAKING EXPONENTIAL COMPLEXITY IN GOOP15 Moreover, when∥K ρ (y ρ )∥ 2 ≤min 2 CD 2 , √ ρ−ε D , we havey ρ +∆y ρ ∈S y ρ and quadratic convergence holds: (5.7) D 2 C 2 ∥K ρ (y ρ + ∆y ρ )∥ 2 ≤ D 2 C 2 ∥K ρ (y ρ )∥ 2 2 . Proof.The proof is provided in the Appendix. Given a fixedρ >0,K ρ andK 0 differ only in the complementarity conditions, and consequently the proximity betweeny ∗ ρ andy ∗ 0 is directly controlled byρ. We characterize the solution error between the converged solutiony ∗ ρ and a ground truth solutiony ∗ 0 to the reduced KKT system in the following result. Theorem5.2 (Central path).Lety ∗ 0 satisfyK 0 (y ∗ 0 ) = 0under Assumption 2.1, with∥∇K 0 (y) + ∥ 2 ≤D 0 <∞and∇K 0 (y)having constant row rank in a neighborhood ofy ∗ 0 . LetN c = P N i=1 m i I be the total number of complementarity pairs. Then, the solutiony ∗ ρ toK ρ (y ∗ ρ ) = 0satisfies (5.8)∥y ∗ ρ −y ∗ 0 ∥ 2 ≤D 0 p N c ρ. Proof.The proof is provided in the Appendix. Specifically, Theorem 5.2 shows that∥y ∗ ρ −y ∗ 0 ∥ 2 =O(ρ), meaning that the error between the converged PDIP iterate and the solution of the reduced KKT system at ρ= 0 decomposes into two independent contributions: (5.9)∥y (ℓ) ρ −y ∗ 0 ∥ 2 ≤∥y (ℓ) ρ −y ∗ ρ ∥ 2 +D 0 p N c ρ where the first term is the algorithmic error, controlled by the PDIP convergence toleranceεand decreasing quadratically by Theorem 5.1, and the second term is the perturbation error, arising from theρ-relaxation of the complementarity condition s⊙γ=ρ1and decreasing linearly withρ. Therefore, driving bothεandρto zero is sufficient to recover a ground truth solution to the reduced KKT conditions. 6. Numerical Study.In this section, we report a numerical study 1 to quantify the advantages of the reduced KKT system formulation compared with the complete formulation. 6.1. Complexity Study.We compare reduced and complete KKT systems on quadratic and nonquadratic GOOPs withN= 4 players. Each playerihasn i = 10 primal variables,m i E = 3 linear equality constraints, andm I = 2 linear inequality constraints. We vary the number of preference levelsK∈2,...,6and, for eachK, generate 100 random instances with initial values (for primal variables) perturbed as N(0,1) around a feasible primal solutionz (0) ρ . In the quadratic setting, eachQ i k in (3.11) is sampled as rank-2 positive semidefinite from Gaussian matrices, andq i k is chosen from the column space ofQ i k to ensure boundedness; constraints satisfy (3.24). To generate nonquadratic problem instances, we replace the outermost objective with (1 ⊤ z) 4 . We adapt Algorithm 5.1 to the complete KKT system by approximating complementarity as in (5.1), and run it on both the reduced and complete formulations using a geometric scheduleρ∈1,10 −1 ,...,10 −10 . Table 1 reports: (i) total wall-clock solve time of Algorithm 5.1 summed over all values ofρper instance, reported as mean±standard deviation over 100 ran- dom instances after trimming the top and bottom 2.5% of runtimes; (i) the number 1 Code is available at https://github.com/CLeARoboticsLab/Reduced-GOOP. This manuscript is for review purposes only. 16D. LEE, J. LI, L. PETERS, G. BAKIRTZIS, AND D. FRIDOVICH-KEIL 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. System size Variable size Solve time (s) for Quad. GOOP Solve time (s) for Nonquad. GOOP Level (K)RCRCRCRC 2132 168 128 136 0.05±0.06 0.07±0.06 0.08±0.12 0.19±0.21 3188 368 244 304 0.17±0.16 0.34±0.12 0.53±0.44 1.11±0.35 4244 800 408 672 0.32±0.32 2.32±2.20 0.54±0.56 5.09±2.82 5300 1728 620 1472 0.60±0.75Failed0.96±0.88Failed 6356 3712 880 3200 1.19±0.80Failed1.79±3.01Failed Fig. 2: Convergence of Algorithm 5.1 for reduced and complete KKT systems un- der varyingρ. The curve and the shaded area denote the mean and the variance of log 10 (∥K ρ (y)∥ 2 ), respectively. of variables in each KKT system,N z i ,η i (reduced) andN ̄z i , ̄η i (complete); and (i) the number of equality and inequality constraints appearing in each KKT system, (F i ,G i ) (reduced) and ( ̄ F i , ̄ G i ) (complete). The complete system exhibits exponen- tial growth in system size with respect toK, reflected by the rapid increase in the number of variables and constraints. This exponential growth translates directly into greater computational burden: across all tested preference levels, the complete formu- lation requires substantially longer solve times, and the performance gap widens asK increases. The same qualitative behavior is observed in both the quadratic and non- quadratic settings. We do not report nonquadratic GOOP results for the complete KKT system formulation when considering larger preference hierarchies (K >4), since the symbolic compilation became intractable due to the large size of complete KKT systems. 6.2. Convergence Study.We empirically demonstrate linear and local qua- dratic convergence of Algorithm 5.1 on two problem classes. Class (i):N= 3 play- ers withn i = 10 variables andK= 4 levels, using rank-2 quadratic objectives J i k (z) =z ⊤ Q i k z+q i⊤ k zand linear constraints whose normals lie in the column space ofQ i k . Class (i):N= 2 players withn i = 4 variables andK= 3 levels, with a top-levelL 2 objectiveJ i 1 (z) =∥z∥ 2 2 ensuring a unique equilibrium, inner objectives This manuscript is for review purposes only. BREAKING EXPONENTIAL COMPLEXITY IN GOOP17 Fig. 3: Monte Carlo comparison over 100 randomly generated GOOP instances with nonquadratic objectives and nonlinear con- straints, showing close agreement between primal solutionsz complete andz reduced , ob- tained from the complete and reduced KKT systems, respectively. Player 1 Player 2 Start 1 Start 2 Goal 1 Goal 2 (a) Computed trajectories time step [s] 0510 h or i zo n ta l sp e e d [m / s ] 0 2 4 time step [s] 0510 ver t i c a l sp e e d [m / s ] 0 2 4 Player 1 Player 2 Speed Limit [1.5 m/s] (b) Velocity profile Newton iteration 0102030405060 l o g(|| 퓚 휌 ( ℓ ) || ∞ ) −6 −3 0 (c) Convergence plot Fig. 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 schedule1,2 −1 ,...,2 −10 ; the reported results correspond toρ= 2 −10 . J i k (z) =e v ⊤ i,k z +e −v ⊤ i,k z for random unit vectorsv i,k (obtained by normalizing Gaussian samples), and nonlinear coupling constraints. In both settings, the convergence curves in Figure 2, showing the mean and variance of log 10 (∥K ρ (y)∥ 2 ) over 10 runs with ini- tializations perturbed asN(0,0.5) around a feasible solutionz 0 , empirically support Theorem 5.1. Figure 3 further presents a Monte Carlo study over 100 instances of class (i), indicating that the reduced KKT system recovers the same primal solution as the complete system, although theoretical guarantees remain challenging due to the complexity of the nonlinear KKT solution space. 6.3. Application to a practical scenario.Finally, Figure 4 demonstrates the applicability of the reduced GOOP formulation and Algorithm 5.1 on a practical multi-vehicle intersection planning problem, originally formulated in [19], illustrating the potential of games of ordered preference in practical settings. 7. Conclusion.In this paper, we studied games of ordered preference and in- troduced a compact reduced KKT system that avoids the exponential complexity of standard single-level reformulations while preserving the essential primal stationarity structure across preference levels. For quadratic GOOPs with linear constraints, we established primal solution equivalence between the reduced and complete KKT sys- tems. For general smooth nonlinear GOOPs, we showed that the reduced system is This manuscript is for review purposes only. 18D. LEE, J. LI, L. PETERS, G. BAKIRTZIS, AND D. FRIDOVICH-KEIL a relaxation of the complete system and supplemented this result with second-order sufficient conditions for local optimality. We developed a primal-dual interior-point method and proved its local quadratic convergence. Numerical study shows that the reduced KKT system formulation yields faster solve times than the complete KKT formulation, with benefits that grow in the number of preference levels. Future work will address primal solution equivalence beyond the quadratic setting, and broaden the framework to richer classes of hierarchical games and multi-agent decision problems. Appendix A. Supplementary results. Proof of Proposition2.4.For playeriat levelk, we define ̄ d i k : = dim( ̄η i k ), ̄p i k : = dim( ̄η i k+1:K i ), ̄v i k : = dim( ̄z i , ̄η i k:K i ), ̄ f i k : = dim( ̄ F i k ), ̄g i k : = dim( ̄ G i k ), respectively denot- ing the numbers of dual variables, induced primals, total variables, equations, and inequality constraints. For the innermost level, ̄ d i K i =m i E +m i I , ̄p i K i = 0, ̄v i K i = n i +m i E +m i I , ̄ f i K i =n i +m i E +m i I , and ̄g i K i = 2m i I . At anyk∈[K i −1], ̄ d i k = ̄ f i k+1 + ̄g i k+1 , ̄p i k = P K i j=k+1 ̄ d i j , ̄v i k =n i + ̄p i k + ̄ d i k , ̄ f i k =n i + ̄p i k + ̄ d i k , and ̄g i k = 2 K i −k+1 m i I . Observe that ̄ d i k = ̄ f i k −n i − ̄p i k and ̄p i k−1 = ̄ d i k + ̄p i k implies ̄p i k−1 = ̄ f i k −n i . Substituting this into ̄ f i k−1 =n i + ̄p i k−1 + ̄ f i k + ̄g i k yields ̄ f i k = 2 ̄ f i k + ̄g i k . Then, applying the previous identity repeatedly and substituting ̄ f i K i and ̄g i k+j , ̄ f i k = 2 ̄ f i k+1 + ̄g i k+1 = 2 2 ̄ f i k+2 + ̄g i k+2 + ̄g i k+1 =·= 2 K i −k ̄ f i K i + K i −k X j=1 2 j−1 ̄g i k+j = 2 K i −k n i +m i E + (K i −k+ 1)m i I . Proof of Theorem3.1.We show that, for each playeri, every solution of the com- plete KKT system induces a solution of the reduced KKT system at the same primal point. The argument proceeds by backward induction on the preference level. Fix a playeri, and let ( ̄z i , ̄η i 1:K i ) satisfy the complete KKT system. Throughout the proof, we identify the primal variables in the two systems by settingz i : = ̄z i .We then construct reduced-system dual variablesη i 1:K i from the complete-system dual variables ̄η i 1:K i so that the reduced KKT conditions hold at the same primal point. Base casek=K i −1.Consider the complete KKT system at levelK i −1. Let ̄γ i K i −1,1 be the dual variable for the inequality constraintg i ( ̄z i , ̄z ¬i )≥0and ̄γ i K i −1,2 the dual variable for ̄γ i K i ≥0constraint. Relative to the complete system ̄ F i K i −1 , the reduced systemF i K i −1 omits (i)∇ ̄η i K i ̄ L i K i from the stationarity constraints and (i) the complementarity conditions ̄γ i K i ⊙ ̄γ i K i −1,2 .Accordingly, we set the reduced multipliers asψ i K i −1 = ̄ ψ i K i −1 , φ i K i −1 = ̄ φ i K i −1 , λ i K i −1 = ̄ λ i K i −1 , γ i K i −1 = ̄γ i K i −1,1 ,and discard the remaining dual variable ̄γ i K i −1,2 (associated with the omitted complementarity conditions). Next, we obtain the Lagrangian of the reduced KKT system at level K i −1 from the complete-system Lagrangian: ̄ L i K i −1 ( ̄z, ̄η i K i −1:K i ) =J i K i −1 ( ̄z)− ̄ λ i⊤ K i −1 h i ( ̄z)− ̄γ i⊤ K i −1,1 g i ( ̄z)(A.1) − ̄ ψ i⊤ K i −1 ∇ ̄z i ̄ L i K i − ̄ φ i⊤ K i −1 g i ( ̄z)⊙ ̄γ i K i − ̄γ i⊤ K i −1,2 ̄γ i K i =L i K i −1 ( ̄z,η i K i −1:K i ). Hence the reduced systemF i K i −1 is satisfied by the complete-system solution. Like- wise, the reduced inequality systemG i K i −1 is obtained from ̄ G i K i −1 by removing the nonnegativity conditions associated with the discarded multipliers, i.e, ̄γ i K i −1,2 ≥0. This manuscript is for review purposes only. BREAKING EXPONENTIAL COMPLEXITY IN GOOP19 Inductive step.Letk∈2,...,K i −1, and suppose that reduced-system dual variables have already been constructed at levelsk,...,K i so that the reduced KKT conditions hold on those levels. We now construct the reduced dual variables at level k−1. Consider the complete KKT system at levelk−1. Let ̄γ i k−1,1 be the dual variable for the inequality constraintg i ( ̄z i , ̄z ¬i )≥0and ̄γ i k−1,2 the dual variable for ̄γ i k:K i ≥0 constraint. In passing from the complete system ̄ F i k−1 to the reduced systemF i k−1 , we omit: (i) the stationarity conditions with respect to lower-level dual variables, ∇ ̄η i k:K i ̄ L i k−1 , (i) the complementarity conditions involving lower-level inequality mul- tipliers, ̄γ i k:K i ⊙ ̄γ i k−1,2 . Next, we set the reduced dual variables at levelk−1 by retaining only a subset of components of ̄η i k−1 : (i) the components ofψ i k−1 are taken from ̄ ψ i k−1 for the terms associated with∇ z i ̄ L i k:K i ,(i) the components ofφ i k−1 are taken from ̄ φ i k−1 for the terms associated withg i (z i ,z ¬i )⊙ ̄γ i k,1 ,...,g i (z i ,z ¬i )⊙ ̄γ i K i and (i) the current-level feasibility multipliers are preserved:λ i k−1 = ̄ λ i k−1 , γ i k−1 = ̄γ i k−1,1 . The remaining complete-system dual variables at levelk−1, including ̄γ i k−1,2 , are discarded. We illustrate this construction below: ̄ L i k−1 ( ̄z i , ̄z ¬i , ̄η i k−1:K i ) =J i k−1 ( ̄z i , ̄z ¬i )− ̄ λ i⊤ k−1 h i ( ̄z i , ̄z ¬i )− ̄γ i⊤ k−1,1 g i ( ̄z i , ̄z ¬i )(A.2) − ̄ ψ i⊤ k−1 ∇ ̄z i ̄ L i k ∇ ̄η i k+1:K i ̄ L i k ∇ ̄z i ̄ L i k+1 ∇ ̄η i k+2:K i ̄ L i k+1 . . . ∇ ̄z i ̄ L i K i − ̄ φ i⊤ k−1 g i ( ̄z i , ̄z ¬i )⊙ ̄γ i k,1 ̄γ i k+1:K i ⊙ ̄γ i k,2 g i ( ̄z i , ̄z ¬i )⊙ ̄γ i k+1,1 ( ( ( ( ( ( ( ( ̄γ i k+2:K i ⊙ ̄γ i k+1,2 . . . g i ( ̄z i , ̄z ¬i )⊙ ̄γ i K i − ̄γ i⊤ k−1,2 ̄γ i k . . . ̄γ i K i =L i k−1 (z i ,z ¬i ,η i k−1:K i ). With this contruction, the reduced systemF i k−1 is satisfied by the complete-system solution ( ̄z, ̄η i k:K i ). The reduced systemG i k−1 retains only the nonnegativity conditions of ̄γ i k−1,1 and inherits the conditions ̄γ i k,1 ≥0,..., ̄γ i K i ,1 ≥0from levelk, which hold by the induction hypothesis. HenceG i k−1 is also satisfied. Since the construction is valid for every playeri∈[N], we conclude that every solution of the complete KKT system induces a solution of the reduced KKT system at the same primal solution. Proof of Proposition3.2.Fix a playeri∈[N]. The total number of variables in the reduced KKT system (F i ,G i ) consists of (i) primal variablesz i and (i) dual variablesη i 1:K i . For anyk≤K i , the dimension of the dual vectorη i k is (K i −k)n i + (K i −k+ 1)m i I +m i E . The sum of all variables’ dimensions is then N z i ,η i =n i + K i X k=1 (K i −k)n i + (K i −k+ 1)m i I +m i E (A.3) = 1 + K i (K i −1) 2 n i +K i m i E + K i (K i + 1) 2 m i I . Proof of Theorem3.4.The proof has three parts: (a) we establish the column- space inclusion relation between the reduced and complete linear systems, (b) we propagate this relation across levels using the recursive block structure of the two KKT matrices, and (c) we use the resulting column-space inclusions to show that the primal solution sets of the two systems coincide. This manuscript is for review purposes only. 20D. LEE, J. LI, L. PETERS, G. BAKIRTZIS, AND D. FRIDOVICH-KEIL (a) We first prove the equivalent statements: Col(R k )⊆Col( ̄ R k )⇐⇒ N( ̄ R ⊤ k )⊆ N(R ⊤ k ).Lety= [u ⊤ ,v ⊤ ,w ⊤ ,z ⊤ ] ⊤ ∈N( ̄ R ⊤ k ) whereu∈R n . Then, ̄ R ⊤ k y= ˆ Q k 0 00 00 00 ̄ R k+1 ̄ R k+1 u v w x = ˆ Q k u 0 + ̄ R k+1 w x ̄ R k+1 u v = 0 0 0 0 .(A.4) Premultiplying the first block row in (A.4) by [u ⊤ ,v ⊤ ] and using the symmetry of ̄ R k+1 : u ⊤ ˆ Q k u+ u v ⊤ ̄ R k+1 w x =u ⊤ ˆ Q k u+ ̄ R k+1 u v ⊤ w x =u ⊤ ˆ Q k u=0.(A.5) Since ˆ Q k is positive semi-definite, it follows that ˆ Q k u=0. Now, consider R ⊤ k y= ˆ Q k ̄ R ⊤ k+1,[:,1:n] 000 |z ̄ R ⊤ k,[:,1:n] u v w z = ˆ Q k u ̄ R ⊤ k+1,[:,1:n] u = 0 0 , where the second row follows from ̄ R k+1 u v =0in (A.4) and the symmetry of ̄ R k+1 . Hence,y∈N(R ⊤ k ), which impliesN( ̄ R ⊤ k )⊆N(R ⊤ k ). (b) We prove this result by induction onk. Base casek=K−1.We partition the matrixM K−1 as follows. M K−1 = Q K−1 0 ˆ Q K ˆ H ⊤ 0000 Q K ˆ H ⊤ 00 H000 |z C K−1 |z M c K−1 ⇒M c K−1 = 0 0 ˆ H ⊤ 00 000 R K .(A.6) Similarly, we partition the matrix ̄ M K−1 as ̄ M K−1 = Q K−1 0 ˆ Q K ˆ H ⊤ 00 ˆ H0 Q K ˆ H ⊤ 00 H000 |z C K−1 |z ̄ M c K−1 ⇒ ̄ M c K−1 = 0 0 ˆ H ⊤ 00 000 ̄ R K .(A.7) By (a), Col R K ⊆Col ̄ R K . This implies that Col M c K−1 ⊆Col ̄ M c K−1 . Induction step.Assume Col M c k ⊆Col ̄ M c k for anyk∈[K−1]. Consider the levelk−1. Partitioning the matricesM k−1 and ̄ M k−1 are: M c k−1 = 0R k M c k 0 , ̄ M c k−1 = 0 ̄ R k ̄ M c k 0 .(A.8) Define the subspaces:A= Col 0 M c k , ̄ A= Col 0 ̄ M c k , B= Col R k 0 ,and ̄ B= Col ̄ R k 0 .By the induction hypothesis, Col M c k ⊆Col ̄ M c k ⇒A⊆ ̄ A. This manuscript is for review purposes only. BREAKING EXPONENTIAL COMPLEXITY IN GOOP21 By (a),B⊆ ̄ B. SinceAandBare orthogonal subspaces that span Col M c k−1 and, similarly, ̄ Aand ̄ Bare orthogonal subspaces that span Col ̄ M c k−1 , we conclude Col M c k−1 ⊆Col ̄ M c k−1 . (c) We now use the results from parts (a) and (b) to show primal solution equiv- alence. Write ̄v k = ̄z ̄η k:K andv k = z η k:K and define theprimalsolution sets ̄ X( ̄p k ) = n ̄z ∃ ̄η k : ̄ M k ̄v k = ̄p k o ,X( ̄p k ) = n z ∃η k :M k v k = ̄p k o .(A.9) (i)X( ̄p k )⊆ ̄ X( ̄p k ).Partition the matrices ̄ M k ,M k and letz∈X( ̄p k ) so that M k z η k = c k |M c k z η k =c k z+M c k η k .(A.10) Set ̄z=z. Choose a vector ̄η k such thatM c k η k = ̄ M c k ̄η k , which exists by (b). Then, ̄ M k ̄z ̄η k = c k | ̄ M c k ̄z ̄η k =c k ̄z |z c k z + ̄ M c k ̄η k |z M c k η k .(A.11) This implies thatz∈ ̄ X( ̄p k ) and thusX( ̄p k )⊆ ̄ X( ̄p k ). (i) ̄ X( ̄p k )⊆X( ̄p k ).We proceed via induction onk. Base casek=K−1.Let ̄z∈ ̄ X( ̄p K−1 ). Recalling the right-hand-side vector ̄p K−1 in (3.19), we write ̄ M K−1 ̄v K−1 = Q K−1 0 ˆ Q K ˆ H ⊤ 00 ˆ H0 Q K ˆ H ⊤ 00 H000 ̄z ̄ λ K ̄ ψ K−1 ̄ λ K−1 = −q K−1 0 −q K b = ̄p K−1 .(A.12) Setv K−1 = ̄v K−1 (soz= ̄z). Then, M K−1 ̄v K−1 = Q K−1 0 ˆ Q K ˆ H ⊤ 0000 Q K ˆ H ⊤ 00 H000 ̄z ̄ λ K ̄ ψ K−1 ̄ λ K−1 = −q K−1 0 −q K b = ̄p K−1 (A.13) so ̄z∈X( ̄p K−1 ). Induction step.Assume the following holds fork∈[K−1] ̄ M k ̄v k = ̄p k ⇒M k ̄v k = ̄p k .(A.14) From (3.19), the firstnrows are Q k−1 ̄z+ ̄ R k,[1:n,:] ̄η k−1 =q k−1 .(A.15) Setv k−1 = ̄v k−1 (soz= ̄z) Now considerM k−1 ̄v k−1 . From (3.20) using (3.18) and (A.15), (A.16) Q k−1 0 00 R k M k 0 |z M k−1 ̄z ̄η K:k ̄η k−1 |z ̄v k−1 = q k−1 0 q k |z ̄p k−1 , This manuscript is for review purposes only. 22D. LEE, J. LI, L. PETERS, G. BAKIRTZIS, AND D. FRIDOVICH-KEIL where the last row follows from the induction hypothesis andv k = [z ⊤ ,(η K:k ) ⊤ ] ⊤ . Thus, ̄z∈X( ̄p k ). Combining (i) and (i) gives ̄ X( ̄p k ) =X( ̄p k ) for allk∈[K−1]. Proof of Theorem3.5.The proof proceeds in three steps. We first fix the active inequality constraints at the candidate primal solutionz ∗ and show that, atz ∗ , the cor- responding inequality-constrained problem can be reduced to an equality-constrained problem on the active set. We then apply the equality-constrained primal equivalence result from Theorem 3.4. Finally, we reconstruct complete-system inequality multi- pliers from the equality-constrained multipliers using strict complementarity. Step 1.Local active-set reduction. Fix a candidate local solutionz ∗ . Because the active set is fixed atz ∗ , the solution set of the inequality-constrained problem (2.1) for playeriis identical to the solution set of the equality-constrained problem obtained by replacingG i z≥g i withG i A i z=g i A i and discarding the constraints that are inactive (slack) at the optimum. LetP I denote inequality-constrained optimization problem (2.1) andP E denote the corresponding equality-constrained problem. Step 2.The equality-constrained problemP E shares the same primal solution set as its reduced KKT system. This follows directly from Theorem 3.4 applied toP E , given that ̃ Hsatisfies the required full row rank assumption. Step 3.The reduced KKT system for the equality-constrained problem (E) and the reduced KKT system for the inequality-constrained problem (I) share the same set of primal solutions. Consider the stationarity conditions for levelkfor both systems. Reduced KKT System forE:Letμ E : = (z E ,λ E ,ψ E ). Fori∈[N] andk∈[K i ]: (A.17) N X j=1 Q i,i,j k z j,E − K i −k X ℓ=1 h Q i,i,i K i −ℓ+1 ψ i,E k,ℓ i −H i⊤ i λ i,E k,1 −G i⊤ i,A i λ i,E k,2 =−q i k , subject toH i z E =h i andG i A i z E =g i A i . Reduced KKT System forI:Letμ I : = (z I ,λ I ,ψ I ,φ I ,γ I ). Fori∈[N] and k∈[K i ]: N X j=1 Q i,i,j k z j,I − K i −k X ℓ=1 h Q i,i,i K i −ℓ+1 ψ i,I k,ℓ +G i⊤ i,A i φ i,I k,ℓ ⊙γ i,I K i −ℓ+1 i (A.18) −H i⊤ i λ i,I k −G i⊤ i,A i γ i,I k =−q i k , subject toH i z I =h i ,G i A i z I ≥g i A i ,γ i,I 1:K i ≥0, and complementarity conditions. 3.1Ifμ I satisfies (I), then there existsμ E satisfying (E) such thatz E =z I . Assumeμ I : = (z I ,λ I ,ψ I ,φ I ,γ I ) satisfies (I). Define (E) variables fori∈[N]:z i,E : = z i,I , λ i,E k,1 : =λ i,I k , ψ i,E : =ψ i,I , λ i,E k,2 : =γ i,I k + P K i −k ℓ=1 φ i,I k,ℓ ⊙γ i,I K i −ℓ+1 .Substituting these definitions into (A.18) yields stationarity in (A.17). Next, verify feasibility. We haveH i z I =h i .By the construction of the active setA i , any solution to (I) must satisfyG i A i z I =g i A i . Thusz E satisfies the equality constraints of (E). 3.2Ifμ E satisfies (E), then there existsμ I satisfying (I) such thatz I =z E . Assumeμ E : = (z E ,ψ E ,λ E ) satisfies (E). We construct a solution for (I) by induction on the level indexk, proceeding backwards fromK i to 1. First, set shared variables fori∈[N]:z i,I : =z i,E , λ i,I k : =λ i,E k,1 , ψ i,I : =ψ i,E .SinceH i z E =h i andG i A i z E =g i A i , z I satisfies primal feasibility with respect to the innermost constraints. 3.2.1Base Case(k=K i ). Fix a playeri. Defineγ i,I K i =λ i,E K i , whereλ i,E K i denotes the multipliers associated with the equality constraints obtained from the This manuscript is for review purposes only. BREAKING EXPONENTIAL COMPLEXITY IN GOOP23 active inequalities at levelK i . By strict complementarity at the candidate solution, these multipliers are strictly positive. Henceγ i,I K i >0. 3.2.2Induction StepAssume that, for all levelsm i > k, we have determined γ i,I m i ≥0andφ i,I m i ,· . We now determineγ i,I k ≥0andφ i,I k,· for (A.18). From (A.18) and (A.17), matching the terms requiresλ i,E k,2 =γ i,I k + P K i −k ℓ=1 φ i,I k,ℓ ⊙γ i,I K i −ℓ+1 .To satisfy this, it suffices to choose one lower-level term and set the remainingφ i,I k,ℓ equal to zero. We use the term corresponding toℓ= 1, which involvesγ i,I K i , already known to be strictly positive from the base case. Setφ i,I k,ℓ =0for allℓ >1. Then, we have λ i,E k,2 =γ i,I k +φ i,I k,1 ⊙γ i,I K i .For each componentr∈1,...,m i I : •If (λ i,E k,2 ) r ≥0: Set (γ i,I k ) r : = (λ i,E k,2 ) r and (φ i,I k,1 ) r : = 0. •If (λ i,E k,2 ) r <0: Set (γ i,I k ) r : = 0. We must solve (λ i,E k,2 ) r = (φ i,I k,1 ) r ·(γ i,I K i ) r . Since (γ i,I K i ) r >0 (from Base Case 3.2.1), we can uniquely define: (φ i,I k,1 ) r : = (λ i,E k,2 ) r (γ i,I K i ) r . This construction ensuresγ i,I k ≥0, satisfying nonnegativity. The complementarity condition (G i A i z i,E −g A i )⊙γ i,I k =0holds naturally, because primal feasibility gives G i A i z i,E =g A i . Repeat steps 3.2.1 and 3.2.2 for all playersi∈[N]. Thus, we obtainμ I satisfying (I) such thatz I =z E . Combining Steps 1, 2, and 3 proves the theorem. Proof of Theorem 5.1.Lety ρ ∈ S y ρ . We begin the proof by characterizing how the pseudoinverse (∇K ρ (y ρ )) + affects the Newton update. SinceK ρ (y ρ ) is in the column space of∇K ρ (y ρ ) for ally ρ ∈S y ρ , the variable ∆y ρ = (∇K ρ (y ρ )) + (−K ρ (y ρ )) satisfies the equation∇K ρ (y ρ )∆y ρ =−K ρ (y ρ ), where the complementarity rows of this equation give for eachi th element of the vectors ofs ρ ,γ ρ ,∆s ρ ,∆γ ρ : (A.19)s ρ,i ∆γ ρ,i +γ ρ,i ∆s ρ,i =ρ−γ ρ,i s ρ,i . We then proceed to prove the linear convergence property in (5.6). It suffices to show the existence of a stepsizeα∈(0,1] satisfying (5.6) by showing that ˆαis a stepsize rendering∥K ρ (y ρ + ˆα∆y ρ )∥ 2 ≤(1− ˆα 2 )∥K ρ (y ρ )∥ 2 . Following the fundamental theorem of calculus again, we have, for all stepsizeα∈(0,1], (A.20) ∥K ρ (y ρ +α∆y ρ )∥ 2 = K ρ (y ρ ) + Z 1 0 ∇K ρ (y ρ +τα∆y ρ )α∆y ρ dτ 2 ≤∥K ρ (y ρ ) +α∇K ρ (y ρ )∆y ρ ∥ 2 + Z 1 0 (∇K ρ (y ρ +τα∆y ρ )−∇K ρ (y ρ ))α∆y ρ dτ 2 ≤∥K ρ (y ρ )−αK ρ (y ρ )∥ 2 +∥α∆y ρ ∥ 2 · Z 1 0 C∥ατ∆y ρ ∥ 2 dτ ≤(1−α)∥K ρ (y ρ )∥ 2 + 1 2 α 2 CD 2 ∥K ρ (y ρ )∥ 2 2 . Lety ρ ∈S y ρ . Since ˆα≤ 1 CD 2 L and∥K ρ (y ρ )∥ 2 ≤L, we have CˆαD 2 2 ∥K ρ (y ρ )∥ 2 ≤ 1 2 , and (A.21) ∥K ρ (y ρ + ˆα∆y ρ )∥ 2 ≤(1−ˆα)∥K ρ (y ρ )∥ 2 + 1 2 ˆα∥K ρ (y ρ )∥ 2 ≤ 1− 1 2 ˆα ∥K ρ (y ρ )∥ 2 ≤L. which establishes (5.6). To complete the proof ofy ρ + ˆα∆y ρ ∈ S y ρ , we need to show (s ρ + ˆα∆s ρ )⊙(γ ρ + ˆα∆γ ρ )≥ε1. For everyi th element of the vectorss ρ ,γ ρ ,∆s ρ ,∆γ ρ , using the complementarity rows in (A.19) and substituting the Newton’s update, (A.22)(γ ρ,i + ˆα∆γ ρ,i )(s ρ,i + ˆα∆s ρ,i ) = (1−ˆα)γ ρ,i s ρ,i + ˆαρ+ ˆα 2 ∆γ ρ,i ∆s ρ,i . This manuscript is for review purposes only. 24D. LEE, J. LI, L. PETERS, G. BAKIRTZIS, AND D. FRIDOVICH-KEIL From ∆y ρ =−(∇K ρ (y ρ )) + K ρ (y ρ ), we have∥∆y ρ ∥ 2 ≤D∥K ρ (y ρ )∥ 2 ≤DL, and ∥∆γ ρ,i ∆s ρ,i ∥ 2 ≤∥∆y ρ ∥ 2 2 ≤D 2 L 2 . Sinceγ ρ,i s ρ,i ≥εand ˆα≤ ρ−ε D 2 L 2 , we have (A.23)(γ ρ,i + ˆα∆γ ρ,i )(s ρ,i + ˆα∆s ρ,i )≥ε+ ˆα (ρ−ε)−ˆαD 2 L 2 ≥ε which completes the proof ofy ρ + ˆα∆y ρ ∈S y ρ . In what follows, we show the quadratic convergence of our PDIP method when ∥K ρ (y ρ )∥ 2 ≤min 2 CD 2 , √ ρ−ε D . From (A.20), we have (A.24)K ρ (y ρ + ∆y ρ )≤ 1 2 CD 2 ∥K ρ (y ρ )∥ 2 2 ≤ 1 2 CD 2 2 CD 2 ∥K ρ (y ρ )∥ 2 =∥K ρ (y ρ )∥ 2 ≤L. Moreover, since∥∆s ρ,i ∆γ ρ,i ∥ 2 ≤D 2 ∥K ρ (y ρ )∥ 2 2 , we have (A.25)(γ ρ,i + ∆γ ρ,i )(s ρ,i + ∆s ρ,i )≥ε+ (ρ−ε)−D 2 ∥K ρ (y ρ )∥ 2 2 ≥ε and thereforey ρ + ∆y ρ ∈S y ρ . Observing CD 2 2 ∥K ρ (y ρ + ∆y ρ )∥ 2 ≤ CD 2 2 ∥K ρ (y ρ )∥ 2 2 ≤1, we have∥K ρ (y ρ + ∆y ρ )∥ 2 ≤min 2 CD 2 , √ ρ−ε D . By induction, this condition holds at all iterates. Proof of Theorem 5.2.Let1 ρ be defined as a binary vector, where we have ones for the entries corresponding to the complementarity slackness condition. SinceK ρ (y ρ ) =K 0 (y ρ )−ρ·1 ρ , evaluating aty ∗ ρ , we haveK 0 (y ∗ ρ ) =ρ1 ρ . By the fundamental theorem of calculus, we have (A.26)K 0 (y ∗ ρ )−K 0 (y ∗ 0 ) = Z 1 0 ∇ y K 0 (y ∗ 0 +t(y ∗ ρ −y ∗ 0 ))dt | z ̄ J ·(y ∗ ρ −y ∗ 0 ). Since∇ y K 0 has constant row rank in a neighborhood ofy ∗ 0 , forρsufficiently small y ∗ ρ lies in this neighborhood and the right hand side of (A.26) has the same constant row rank, with∥ ̄ J + ∥ 2 ≤D 0 by continuity of the pseudoinverse under constant rank. Multiplying both sides of (A.26) by ̄ J + , we have (A.27) ∥y ∗ ρ −y ∗ 0 ∥ 2 ≤∥ ̄ J + ∥ 2 ∥ρ1 ρ ∥ 2 ≤D 0 p N c ρ REFERENCES [1]T. Bas ̧ar and G. J. Olsder,Dynamic noncooperative game theory, SIAM, 1998. [2]E. O. Camargo, J. E. Candelo-Becerra, and A. S. Mercado,Lexicographic multi-objective optimisation of hybrid power generation systems for communities in non-interconnected zones, International Journal of Energy Economics and Policy, 9 (2019), p. 205. [3]A. Charnes, W. W. Cooper, and R. O. Ferguson,Optimal estimation of executive compen- sation by linear programming, Management science, 1 (1955), p. 138–151. [4]M. Cococcioni, M. Pappalardo, and Y. D. Sergeyev,Lexicographic multi-objective linear programming using grossone methodology: Theory and algorithm, Applied Mathematics and Computation, 318 (2018), p. 298–311. [5]B. Colson, P. Marcotte, and G. Savard,An overview of bilevel optimization, Annals of operations research, 153 (2007), p. 235–256. [6]P. de las Heras Molins, E. Roy-Almonacid, D. H. Lee, L. Peters, D. Fridovich-Keil, and G. Bakirtzis,Approximate solutions to games of ordered preference, in 2025 IEEE 28th International Conference on Intelligent Transportation Systems (ITSC), 2025. [7]G. Debreu,A social equilibrium existence theorem, Proceedings of the national academy of sciences, 38 (1952), p. 886–893. This manuscript is for review purposes only. BREAKING EXPONENTIAL COMPLEXITY IN GOOP25 [8]B. Di and A. Lamperski,Newton’s method, bellman recursion and differential dynamic pro- gramming for unconstrained nonlinear dynamic games, Dynamic Games and Applications, 12 (2022), p. 394–442. [9]M. Ehrgott,Multicriteria optimization, Springer, 2005. [10]F. Facchinei and J.-S. Pang,Finite-dimensional variational inequalities and complementarity problems, Springer, 2003. [11]A. V. Fiacco,Second order sufficient conditions for weak and strict constrained minima, SIAM Journal on Applied Mathematics, 16 (1968), p. 105–108. [12]P. C. Fishburn,Additive utilities with incomplete product sets: Application to priorities and assignments, Operations research, 15 (1967), p. 537–542. [13]N. Gunantara,A review of multi-objective optimization: Methods and its applications, Cogent Engineering, 5 (2018), p. 1502242. [14]Y. Haimes,On a bicriterion formulation of the problems of integrated system identification and system optimization, IEEE transactions on systems, man, and cybernetics, (1971), p. 296–297. [15]C.-L. Hwang and A. S. M. Masud,Multiple objective decision making—methods and appli- cations: a state-of-the-art survey, Springer Science & Business Media, 2012. [16]H. Isermann,Linear lexicographic optimization, Operations-Research-Spektrum, 4 (1982), p. 223–228. [17]D. F. Jones and H. O. Florentino,Multi-objective optimization: methods and applications, in The Palgrave handbook of operations research, Springer, 2022, p. 181–207. [18]F. Laine, D. Fridovich-Keil, C.-Y. Chiu, and C. Tomlin,The computation of approximate generalized feedback nash equilibria, SIAM Journal on Optimization, 33 (2023), p. 294– 318. [19]D. H. Lee, L. Peters, and D. Fridovich-Keil,You can’t always get what you want: Games of ordered preference, IEEE Robotics and Automation Letters, 10 (2025), p. 7182–7189. [20]J. Li, S. Sojoudi, C. J. Tomlin, and D. Fridovich-Keil,The computation of approximate feedback stackelberg equilibria in multiplayer nonlinear constrained dynamic games, SIAM Journal on Optimization, 34 (2024), p. 3723–3749. [21]S. Liao,On the homotopy analysis method for nonlinear problems, Applied mathematics and computation, 147 (2004), p. 499–513. [22]J. Lu, J. Han, Y. Hu, and G. Zhang,Multilevel decision-making: A survey, Information Sciences, 346 (2016), p. 463–487. [23]Z.-Q. Luo, J.-S. Pang, and D. Ralph,Mathematical programs with equilibrium constraints, Cambridge University Press, 1996. [24]K. Miettinen,Nonlinear multiobjective optimization, vol. 12, Springer Science & Business Media, 1999. [25]P. Ngatchou, A. Zarei, and A. El-Sharkawi,Pareto multi objective optimization, in Pro- ceedings of the 13th international conference on, intelligent systems application to power systems, IEEE, 2005, p. 84–91. [26]J. Nocedal and S. J. Wright,Numerical optimization, Springer, 2006. [27]J. Outrata, M. Kocvara, and J. Zowe,Nonsmooth approach to optimization problems with equilibrium constraints: theory, applications and numerical results, vol. 28, Springer Science & Business Media, 2013. [28]F. Palafox, J. Milzman, D. H. Lee, R. Park, and D. Fridovich-Keil,Smooth information gathering in two-player noncooperative games, arXiv preprint arXiv:2404.00733, (2024). [29]R. Sato, M. Tanaka, and A. Takeda,A gradient method for multilevel optimization, Ad- vances in Neural Information Processing Systems, 34 (2021), p. 7522–7533. [30]H. Scheel and S. Scholtes,Mathematical programs with complementarity constraints: Sta- tionarity, optimality, and sensitivity, Mathematics of Operations Research, 25 (2000), p. 1–22. [31]A. Shafiei, V. Kungurtsev, and J. Marecek,Trilevel and multilevel optimization using monotone operator theory, Mathematical Methods of Operations Research, 99 (2024), p. 77–114. [32]D. Yue and F. You,Stackelberg-game-based modeling and optimization for supply chain design and operations: A mixed integer bilevel programming framework, Computers and Chemical Engineering, 102 (2017), p. 81–95. Sustainability and Energy Systems. [33]A. Zanardi, E. Mion, M. Bruschetta, S. Bolognani, A. Censi, and E. Frazzoli,Urban driving games with lexicographic preferences and socially efficient nash equilibria, IEEE Robotics and Automation Letters, 6 (2021), p. 4978–4985. This manuscript is for review purposes only.