Source-linked AI summary
Open-Loop Stackelberg LQ Difference Games with Coupled-Affine Inequality Constraints: An Exact OCP--LCS/LCQP Reformulation
Shrestha Ghosh, Puduru Viswanadha Reddy
TL;DR
The paper studies finite-horizon linear–quadratic Stackelberg difference games with coupled-affine state-control constraints, where constrained follower responses must be incorporated into the leader’s problem. It develops exact OCP–LCS and LCQP reformulations, with global LCQP minimizers yielding GOLSEs and an affine recovery map producing the follower strategy.
Problem
Coupled state-control constraints make the follower response and leader-feasibility conditions interdependent in constrained open-loop Stackelberg games.
Method
A Riccati-based costate transformation embeds the follower’s KKT conditions into an OCP–LCS, then eliminates dynamic variables to obtain an initial-state-parametrized LCQP.
Results
Global minimizers of the OCP–LCS correspond to GOLSEs, and the LCQP reformulation supports numerical computation of these equilibria.
Takeaways & Limitations
The reformulation provides an exact computational representation of constrained open-loop Stackelberg equilibria, including an explicit affine recovery map for the follower strategy.
Abstract
from arXiv · showhide
In this letter, we study finite-horizon linear-quadratic Stackelberg difference games with coupled-affine state-control inequality constraints. Under the stated assumptions, we show that generalized open-loop Stackelberg equilibria admit an exact reformulation as an optimal control problem subject to a discrete-time linear complementarity system. Eliminating the dynamic variables yields a large-scale linear complementarity quadratic program, together with an explicit recovery map for the follower strategy. This reformulation enables the numerical computation of these equilibria. We illustrate the proposed approach using a constrained network-flow game.
I. INTRODUCTION
The paper addresses finite-horizon open-loop Stackelberg games with coupled state-control constraints, where follower responses and leader feasibility are mutually dependent. It contributes exact OCP–LCS and LCQP reformulations that preserve this sequential coupling.
- Coupled state-control constraints make the follower’s feasible set depend on the leader’s announcement and can affect the leader’s feasibility through the follower’s response.
- Existing approaches restrict the coupling structure, use simultaneous rather than sequential decisions, or study different Stackelberg information structures.
- The paper formulates GOLSEs using a follower-feasible reaction set and a leader-admissible announcement set that incorporates follower-induced constraints.
- A Riccati-based costate transformation converts the follower’s KKT conditions into a coupled discrete-time LCS.
- Eliminating state and costate trajectories produces an initial-state-parametrized LCQP whose global minimizers correspond to GOLSEs in the primal decision variables.
II. PROBLEM FORMULATION
The model is a finite-horizon two-player linear–quadratic difference game in which the leader commits to an open-loop strategy and the follower responds under coupled-affine inequality constraints. Regularity assumptions ensure follower feasibility, compactness, and a well-defined leader problem based on a single-valued response.
- The game has two players, with player 1 as leader and player 2 as follower, choosing actions over discrete decision instants.
- Each player uses an open-loop strategy, and the resulting state trajectory follows discrete-time dynamics subject to state-control inequality constraints.
- Both players minimize stage-additive linear–quadratic cost functionals.
- For a fixed leader announcement, the follower’s feasible strategy set is defined separately, while follower-feasible leader announcements must account for the induced response.
- Assumption 1 requires a nonempty leader strategy set and bounded follower feasible sets; after state elimination, these sets are compact polyhedra.
- The formulation adopts single-valued follower responses because otherwise the leader’s cost depends on a response the leader cannot enforce.
III. GENERALIZED OPEN-LOOP STACKELBERG EQUILIBRIUM
The paper reformulates the generalized open-loop Stackelberg equilibrium as an optimal-control problem constrained by a discrete-time linear complementarity system.
- The GOLSE admits an exact reformulation as an OCP–LCS.
A. Follower’s Problem
The follower’s constrained problem is reduced through KKT conditions and a Riccati-based costate transformation. Under positive-definite stage matrices, the follower strategy is unique, while auxiliary complementarity variables may remain nonunique.
- For a fixed leader announcement, the follower solves a constrained optimal-control problem whose KKT conditions form a coupled discrete-time LCS.
- A Riccati difference equation and positive-definite matrices Γ_k provide the regularity conditions used in the follower reduction.
- The Riccati-based transformation introduces a costate residual ζ_k and converts the follower conditions into the reduced system used for reformulation.
- The follower objective is strictly convex in u2, so the compact feasible problem has a unique minimizer and its affine-constraint KKT conditions are necessary and sufficient.
- The stagewise complementarity problem has a unique multiplier solution when its relevant matrix is positive definite.
- The follower strategy is unique, but distinct admissible pairs of auxiliary variables (ζ,µ) can represent that same strategy.
B. Leader’s problem
The leader’s constrained problem is reformulated by embedding the follower’s KKT conditions into an OCP–LCS, with equivalence between feasible solutions and GOLSEs under the stated assumptions. The reformulation is exact but does not itself ensure existence, and complementarity generally makes the feasible set nonconvex.
- OCP–LCS formulation: The leader’s problem is formulated using an OCP–LCS that embeds the follower’s KKT conditions and induced leader constraints.The follower response is recovered from the transformed state, leader action, costate, and multiplier variables.
- Equivalence: Feasible OCP–LCS points correspond exactly to feasible leader announcements, with matching objective values and recovered follower responses.The equivalence holds in both directions through the follower’s unique response and the recovery construction.
- Equilibrium recovery: Global minimizers of the OCP–LCS yield generalized open-loop Stackelberg equilibria through the recovery map.The solution-set relation is expressed through the image of OCP–LCS minimizers under the recovery map.
- Existence conditions: The exact reformulation does not guarantee existence of a GOLSE or a global OCP–LCS minimizer.Existence additionally requires a nonempty leader-feasible set and attainment of a global minimum.
- Nonconvexity: Complementarity imposes an either-or condition on multipliers and slacks, making the OCP–LCS feasible set generally nonconvex.Each complementarity pair requires either the multiplier or the corresponding slack to be zero, with both nonnegative.
C. LCQP reformulation
Eliminating state and costate trajectories reduces the OCP–LCS to a large-scale LCQP in the leader strategy and complementarity multipliers. The LCQP preserves exact equilibrium recovery while retaining complementarity-induced nonconvexity.
- Variable elimination: State and costate variables are eliminated to obtain an LCQP in the leader strategy and multiplier variables.Forward state and backward costate recursions provide affine expressions parameterized by the initial state.
- Variable elimination: For fixed leader and multiplier variables, the eliminated state and costate trajectories are uniquely determined by the boundary conditions.The state is propagated forward from the initial state, while the costate is propagated backward from its terminal condition.
- Equilibrium recovery: Global minimizers of the LCQP characterize GOLSEs, with the follower strategy recovered from the explicit affine map.The recovery uses the reconstructed state and costate components together with the optimal leader and multiplier variables.
- Exactness: The LCQP and OCP–LCS have corresponding feasible points and identical objective values for each fixed initial state.Substitution of the eliminated trajectories preserves the complementarity and leader constraints as well as the quadratic objective.
- Computational structure: When the quadratic objective is convex, elimination adds no nonconvexity; complementarity remains the only nonconvex component.Finite bounds can replace complementarity with mixed-integer constraints, yielding an exact MIQP solvable by certified global methods.
IV. NUMERICAL ILLUSTRATION
The numerical illustration compares simultaneous GOLNE and leader-first GOLSE play in a constrained two-player, two-relay network-flow game. Leader-first play redistributes scarce battery-limited flow toward the leader, with its advantage disappearing once battery capacity reaches the destination-flow ceiling.
- Network-flow game: The example uses a network with two players, two sources, two relays, and two destinations under shared relay-capacity, battery, and destination constraints.The players minimize discounted-payoff costs while routing flows over a 30-stage horizon.
- Numerical setup: The LCQP is solved globally through a big-M MIQP reformulation in 0.2 s using Gurobi with MIPGap=10^-6.The reported implementation uses M=5000 on an Intel Core i5 computer with 32 GB RAM.
- Baseline equilibria: Under simultaneous GOLNE play, the four path flows coincide at every stage, whereas GOLSE preserves within-player path symmetry but makes allocation across players asymmetric.The baseline comparison is depicted as GOLNE on the left and GOLSE on the right.
- Baseline equilibria: 160 total flow is delivered under both equilibria, while leader-first play yields cost differences of ∆L = 119.91 and ∆F = 291.32.The redistribution changes player allocation without increasing total throughput.
- Resource-scarcity variation: At v = 13, battery capacity reaches the 240-unit destination-flow ceiling, so ∆L = ∆F = 0 and the Stackelberg flow share returns to 0.5.As the common initial relay charge increases, the leader’s excess flow share and both cost differences decrease.
- Resource-scarcity variation: The advantage of announcing first arises only when the common relay-battery resource is scarce, specifically while S(v) < K ∑2.The experiment varies symmetric initial relay charges x1_0 = x2_0 = v for v ∈ {2,...,16}.
V. CONCLUSION
The paper studies finite-horizon linear–quadratic Stackelberg difference games with coupled-affine state-control constraints. It derives an exact OCP–LCS reformulation and an LCQP whose global minimizers yield generalized open-loop Stackelberg equilibria, while identifying feedback information structures as future work.
- The paper studies finite-horizon linear–quadratic Stackelberg difference games with coupled-affine state-control constraints.
- A Riccati-based costate transformation yields an exact OCP–LCS reformulation and a large-scale LCQP parametrized by the initial state.
- Global minimizers of the LCQP yield generalized open-loop Stackelberg equilibria, with the follower strategy recovered through an explicit affine map.
- Extending the results to a feedback information structure is identified as a natural direction for future work.
APPENDIX
The appendix introduces notation for the forward and backward equations and defines block matrices used in the reformulation. These objects organize transition propagation and the coupling terms entering the transformed system.
- The matrices Φk,i describe state-transition products, with Φk,k = In and k ≥ i.
- The appendix defines block-diagonal matrices Ei, Si, Wi, Ui and stacked vectors ri using player-indexed blocks.
- The matrices Ni and Vi combine these block terms with transition and costate-related matrices in the reformulation.