API Reference

MixedHierarchyGames

A Julia package for solving mixed hierarchy (Stackelberg) trajectory games.

Provides two solvers:

• QPSolver - For quadratic programming problems with linear dynamics
• NonlinearSolver - For general nonlinear problems

Both solvers implement the TrajectoryGamesBase.solve_trajectory_game! interface.

AbstractMixedHierarchyGameSolver

Abstract supertype for all hierarchy game solvers.

Subtypes must implement:

• solve(solver, parameter_values; kwargs...) → JointStrategy
• solve_raw(solver, parameter_values; kwargs...) → NamedTuple

QPSolver

Solver for quadratic programming hierarchy games (linear dynamics, quadratic costs).

Fields

• problem::HierarchyProblem - The problem specification
• solver_type::Symbol - Solver backend (:linear or :path)
• precomputed::QPPrecomputed - Precomputed symbolic components (variables, KKT conditions)

NonlinearSolver

Solver for general nonlinear hierarchy games.

Uses iterative quasi-linear policy approximation with configurable line search.

Fields

• problem::HierarchyProblem - The problem specification
• precomputed::NamedTuple - Precomputed symbolic components from preoptimizenonlinearsolver
• options::NonlinearSolverOptions - Solver options
  • use_sparse can be :auto (sparse for leaders, dense for leaves), :always, or :never

NonlinearSolverOptions

Concrete options struct for NonlinearSolver. Replaces the untyped NamedTuple previously used for solver options.

Fields

• max_iters::Int - Maximum iterations (default: 100)
• tol::Float64 - Convergence tolerance (default: 1e-6)
• verbose::Bool - Print iteration info (default: false)
• linesearch_method::Symbol - Line search method: :armijo, :geometric, or :constant (default: :geometric)
• recompute_policy_in_linesearch::Bool - Recompute K matrices at each line search trial step (default: true)
• use_sparse::Symbol - Strategy for M\N solve: :auto, :always, or :never (default: :auto). Bool values (true/false) are accepted and normalized to :always/:never.
• show_progress::Bool - Display iteration progress (default: false)
• regularization::Float64 - Tikhonov regularization parameter λ (default: 0.0)

HierarchyGame

A trajectory game with hierarchical (Stackelberg) structure.

Fields

• game::TrajectoryGame - The underlying trajectory game
• hierarchy_graph::SimpleDiGraph - DAG representing leader-follower relationships (edge i→j means player i is a leader of player j)

HierarchyProblem

Low-level problem specification for hierarchy games. Stores cost functions, constraints, and symbolic variables. Used by both QPSolver and NonlinearSolver.

Fields

• hierarchy_graph::SimpleDiGraph - DAG of leader-follower relationships
• Js::Dict - Cost functions per player: Js[i](zs...; θ) → scalar
• gs::Vector - Constraint functions per player: gs[i](z) → Vector
• primal_dims::Vector{Int} - Decision variable dimension per player
• θs::Dict - Symbolic parameter variables per player
• state_dim::Int - State dimension per player (for trajectory extraction)
• control_dim::Int - Control dimension per player (for trajectory extraction)

QPPrecomputed

Precomputed components for QPSolver, cached during construction for efficient repeated solves.

Type Parameters

• TV - Type of problem variables (from setupproblemvariables)
• TK - Type of KKT conditions result (from getqpkkt_conditions)
• TP<:AbstractDict - Type of stripped policy constraints (Dict)
• TM - Type of parametric MCP (ParametricMCP)
• TJ - Type of Jacobian buffer (sparse or dense matrix)

Fields

• vars::TV - Problem variables from setupproblemvariables
• kkt_result::TK - KKT conditions from getqpkkt_conditions
• πs_solve::TP - Stripped policy constraints for solving
• parametric_mcp::TM - Cached ParametricMCP for solving
• J_buffer::TJ - Pre-allocated Jacobian buffer for solveqplinear
• F_buffer::Vector{Float64} - Pre-allocated residual buffer for solveqplinear
• z0_buffer::Vector{Float64} - Pre-allocated zero vector for solveqplinear

solve(solver::QPSolver, initial_state; kwargs...)

Solve the QP hierarchy game with given initial state (parameter values).

Uses precomputed symbolic KKT conditions for efficiency.

Arguments

• solver::QPSolver - The QP solver with precomputed components
• initial_state - Per-player parameter values. Accepts:
  • Dict{Int, Vector}: Player index → parameter vector
  • Vector{Vector}: Converted to Dict with 1-based keys

Keyword Arguments

• verbose::Bool=false - Print debug info
• iteration_limit::Int=100000 - Maximum iterations for PATH solver (only used with :path)
• proximal_perturbation::Float64=1e-2 - Proximal perturbation parameter (only used with :path)
• use_basics::Bool=true - Use basic solution from PATH (only used with :path)
• use_start::Bool=true - Use starting point from PATH (only used with :path)

Returns

• JointStrategy containing OpenLoopStrategy for each player

solve(solver::NonlinearSolver, initial_state; kwargs...)

Solve the nonlinear hierarchy game with given initial state (parameter values).

Uses precomputed symbolic components for efficiency.

Arguments

• solver::NonlinearSolver - The nonlinear solver with precomputed components
• initial_state - Per-player parameter values. Accepts:
  • Dict{Int, Vector}: Player index → parameter vector
  • Vector{Vector}: Converted to Dict with 1-based keys

Keyword Arguments

• initial_guess::Union{Nothing, Vector}=nothing - Warm start for the solver
• show_progress::Union{Nothing, Bool}=nothing - Display iteration progress table
• Additional options override solver.options

Returns

• JointStrategy containing OpenLoopStrategy for each player

solve_raw(solver::QPSolver, initial_state; kwargs...)

Solve and return raw solution vector (for debugging/analysis).

Arguments

• solver::QPSolver - The QP solver
• initial_state - Per-player parameter values (Dict or Vector of Vectors)

Keyword Arguments

• verbose::Bool=false - Print debug info
• iteration_limit::Int=100000 - Maximum iterations for PATH solver (only used with :path)
• proximal_perturbation::Float64=1e-2 - Proximal perturbation parameter (only used with :path)
• use_basics::Bool=true - Use basic solution from PATH (only used with :path)
• use_start::Bool=true - Use starting point from PATH (only used with :path)

Returns

Named tuple with fields:

• sol::Vector{Float64} - Solution vector (concatenated player decision variables)
• status::Symbol - Solver status (:solved or :failed)
• info - PATH solver info (only for :path backend, nothing for :linear)
• vars - Symbolic variables from precomputation

solve_raw(solver::NonlinearSolver, initial_state; kwargs...)

Solve and return raw solution with convergence info (for debugging/analysis).

Arguments

• solver::NonlinearSolver - The nonlinear solver
• initial_state - Per-player parameter values (Dict or Vector of Vectors)

Keyword Arguments

• initial_guess::Union{Nothing, Vector}=nothing - Warm start for the solver
• max_iters::Int - Maximum iterations (default from solver.options)
• tol::Float64 - Convergence tolerance (default from solver.options)
• verbose::Bool - Print iteration info (default from solver.options)
• linesearch_method::Symbol - Line search method (default from solver.options)
• recompute_policy_in_linesearch::Bool - Recompute K matrices at each line search trial step (default from solver.options)
• show_progress::Bool - Display iteration progress table (default from solver.options)

Returns

Named tuple with fields:

• sol::Vector{Float64} - Solution vector (concatenated player decision variables)
• converged::Bool - Whether solver converged to tolerance
• iterations::Int - Number of iterations taken
• residual::Float64 - Final KKT residual norm
• status::Symbol - Solver status:
  • :solved - Converged successfully
  • :solved_initial_point - Initial guess was already a solution
  • :max_iters_reached - Did not converge within iteration limit
  • :linear_solver_error - Newton step computation failed
  • :line_search_failed - Armijo line search failed to find sufficient decrease
  • :numerical_error - NaN or Inf encountered

solve_with_path(parametric_mcp, θs::Dict, parameter_values::Dict; kwargs...)

Solve KKT system using PATH solver via ParametricMCPs.jl with cached MCP.

Arguments

• parametric_mcp - Precomputed ParametricMCP from QPSolver construction
• θs::Dict - Symbolic parameter variables per player
• parameter_values::Dict - Numerical parameter values per player

Keyword Arguments

• initial_guess::Union{Nothing, Vector}=nothing - Warm start
• verbose::Bool=false - Print solver output
• iteration_limit::Int=100000 - Maximum iterations for PATH solver
• proximal_perturbation::Float64=1e-2 - Proximal perturbation parameter
• use_basics::Bool=true - Use basic solution from PATH
• use_start::Bool=true - Use starting point from PATH

Returns

Tuple of:

• sol::Vector - Solution vector
• status::Symbol - Solver status (:solved, :failed, etc.)
• info - PATH solver info

solve_with_path(πs::Dict, variables::Vector, θs::Dict, parameter_values::Dict; kwargs...)

Solve KKT system using PATH solver via ParametricMCPs.jl (builds MCP internally).

Arguments

• πs::Dict - KKT conditions per player
• variables::Vector - All symbolic variables
• θs::Dict - Symbolic parameter variables per player
• parameter_values::Dict - Numerical parameter values per player

Keyword Arguments

• initial_guess::Union{Nothing, Vector}=nothing - Warm start
• verbose::Bool=false - Print solver output
• iteration_limit::Int=100000 - Maximum iterations for PATH solver
• proximal_perturbation::Float64=1e-2 - Proximal perturbation parameter
• use_basics::Bool=true - Use basic solution from PATH
• use_start::Bool=true - Use starting point from PATH

Returns

Tuple of:

• sol::Vector - Solution vector
• status::Symbol - Solver status (:solved, :failed, etc.)
• info - PATH solver info

solve_qp_linear(parametric_mcp, θs::Dict, parameter_values::Dict; kwargs...)

Solve LQ game KKT system using direct linear solve with cached MCP.

For LQ games with only equality constraints, the KKT system is linear: Jz = -F where J is the Jacobian and F is the KKT residual.

Arguments

• parametric_mcp - Precomputed ParametricMCP from QPSolver construction
• θs::Dict - Symbolic parameter variables per player
• parameter_values::Dict - Numerical parameter values per player

Keyword Arguments

• verbose::Bool=false - Print solver output

Returns

Tuple of:

• sol::Vector - Solution vector
• status::Symbol - Solver status (:solved or :failed)

solve_qp_linear(πs::Dict, variables::Vector, θs::Dict, parameter_values::Dict; kwargs...)

Solve LQ game KKT system using direct linear solve (builds MCP internally).

For LQ games with only equality constraints, the KKT system is linear: Jz = -F where J is the Jacobian and F is the KKT residual.

Arguments

• πs::Dict - KKT conditions per player
• variables::Vector - All symbolic variables
• θs::Dict - Symbolic parameter variables per player
• parameter_values::Dict - Numerical parameter values per player

Keyword Arguments

• verbose::Bool=false - Print solver output

Returns

Tuple of:

• sol::Vector - Solution vector
• status::Symbol - Solver status (:solved or :failed)

qp_game_linsolve(A, b; kwargs...)

Solve linear system Ax = b for QP games.

For LQ games, the KKT system is linear so this directly solves for the solution.

Arguments

• A - System matrix (Jacobian of KKT conditions)
• b - Right-hand side

Returns

• x::Vector - Solution vector

run_nonlinear_solver(
    precomputed::NamedTuple,
    initial_states::Dict,
    hierarchy_graph::SimpleDiGraph;
    initial_guess::Union{Nothing, Vector{Float64}} = nothing,
    max_iters::Int = 100,
    tol::Float64 = 1e-6,
    verbose::Bool = false,
    linesearch_method::Symbol = :geometric,
    recompute_policy_in_linesearch::Bool = true,
    use_sparse::Union{Symbol,Bool} = :auto,
    show_progress::Bool = false,
    to::TimerOutput = TimerOutput()
)

Orchestrates the Newton iteration loop for solving nonlinear hierarchy games.

Each iteration: evaluate the KKT residual, check convergence, compute a Newton step via compute_newton_step, and select a step size via configurable line search. Convergence is checked by check_convergence.

Arguments

• precomputed::NamedTuple - Precomputed symbolic components from preoptimize_nonlinear_solver
• initial_states::Dict - Initial state for each player (keyed by player index)
• hierarchy_graph::SimpleDiGraph - Player hierarchy graph

Keyword Arguments

• initial_guess::Union{Nothing, Vector{Float64}}=nothing - Starting point (zero-initialized if nothing)
• max_iters::Int=100 - Maximum Newton iterations
• tol::Float64=1e-6 - Convergence tolerance on KKT residual norm
• verbose::Bool=false - Print per-iteration convergence info
• linesearch_method::Symbol=:geometric - Line search method (:armijo, :geometric, or :constant)
• recompute_policy_in_linesearch::Bool=true - Recompute K matrices at each line search trial step. Set to false for ~1.6x speedup (reuses K from current Newton iteration).
• use_sparse::Union{Symbol,Bool}=:auto - Strategy for M\N solve (see compute_K_evals)
• show_progress::Bool=false - Display iteration progress table (iter, residual, step size, time)
• regularization::Float64=0.0 - Tikhonov regularization parameter λ for K = (M + λI)\N. Improves stability for near-singular M matrices at the cost of solution bias.
• callback::Union{Nothing, Function}=nothing - Optional callback invoked each iteration with (; iteration, residual, step_size, z_est). Enables iteration history tracking, convergence analysis, and external monitoring. z_est is a copy of the post-update solution vector. Note: residual is the pre-step KKT residual (evaluated before the Newton update), while z_est is the post-step solution. The residual at z_est is not computed until the next iteration's convergence check.
• to::TimerOutput=TimerOutput() - Timer for profiling solver phases

Returns

Named tuple (; sol, converged, iterations, residual, status):

• sol::Vector{Float64} - Solution vector
• converged::Bool - Whether the solver reached the tolerance
• iterations::Int - Number of iterations performed
• residual::Float64 - Final KKT residual norm
• status::Symbol - One of :solved, :solved_initial_point, :max_iters_reached, :linear_solver_error, :line_search_failed, :numerical_error

extract_trajectories(sol::Vector, dims::NamedTuple, T::Int, n_players::Int)

Extract state and control trajectories from flattened solution vector.

Arguments

• sol::Vector - Flattened solution
• dims::NamedTuple - Dimension info per player
• T::Int - Time horizon
• n_players::Int - Number of players

Returns

• xs::Dict{Int, Vector{Vector}} - State trajectories per player
• us::Dict{Int, Vector{Vector}} - Control trajectories per player

solution_to_joint_strategy(xs::Dict, us::Dict, n_players::Int)

Convert trajectory dictionaries to JointStrategy of OpenLoopStrategys.

Arguments

• xs::Dict - State trajectories per player
• us::Dict - Control trajectories per player
• n_players::Int - Number of players

Returns

• JointStrategy over OpenLoopStrategys

split_solution_vector(sol::AbstractVector, block_sizes::Vector{Int})

Split a flat vector into blocks using BlockArrays.

Returns an iterable of blocks where each block is a view into the original vector. Uses PseudoBlockVector for a zero-copy view.

Arguments

• sol - Flat vector to split
• block_sizes - Size of each block

Example

sol = [1.0, 2.0, 3.0, 4.0, 5.0]
player_blocks = split_solution_vector(sol, [2, 3])
# blocks: [[1.0, 2.0], [3.0, 4.0, 5.0]]

check_convergence(residual, tol; verbose=false, iteration=nothing)

Check whether the solver has converged based on the KKT residual norm.

Returns a named tuple (converged, status) where:

• converged::Bool - whether the residual is below tolerance
• status::Symbol - :solved, :not_converged, or :numerical_error

Arguments

• residual::Real - Current KKT residual norm
• tol::Real - Convergence tolerance

Keyword Arguments

• verbose::Bool=false - Print convergence info
• iteration::Union{Nothing,Int}=nothing - Current iteration number (for verbose output)

compute_newton_step(linsolver, jacobian, neg_residual)

Solve the Newton step linear system jacobian * δz = neg_residual.

Uses the provided LinearSolve solver instance for the factorization and solve. Handles singular matrix errors gracefully by returning success=false.

Arguments

• linsolver - Initialized LinearSolve solver (mutated in place)
• jacobian - Jacobian matrix (∇F)
• neg_residual - Negative residual vector (-F)

Returns

Named tuple (step, success) where:

• step::Vector - Newton step direction δz (undefined if success=false)
• success::Bool - Whether the linear solve succeeded

perform_linesearch(residual_norm_fn, z_est, δz, current_residual_norm; use_armijo=true)

Perform backtracking line search to select step size for Newton update.

When use_armijo=true, backtracks from α=1.0 by halving until the trial point has a smaller residual norm than the current point, or max iterations are reached. When use_armijo=false, returns α=1.0 (full Newton step).

Arguments

• residual_norm_fn - Function z_trial -> Float64 returning residual norm at trial point
• z_est::Vector - Current iterate
• δz::Vector - Newton step direction
• current_residual_norm::Float64 - Residual norm at current iterate

Keyword Arguments

• use_armijo::Bool=true - Whether to perform backtracking line search
• z_trial_buffer::Union{Nothing,Vector{Float64}}=nothing - Pre-allocated buffer for trial points. When provided, avoids allocating z_est + α*δz each iteration. Must have same length as z_est.

Returns

• α::Float64 - Selected step size

armijo_backtracking(f, x, d, alpha_init; c1=1e-4, rho=0.5, max_iters=20)

Armijo backtracking line search for step size selection.

Uses the merit function ϕ(x) = ||f(x)||² and checks the sufficient decrease condition:

ϕ(x + α*d) ≤ ϕ(x) + c1 * α * ∇ϕ'*d

where for Newton-like methods ∇ϕ'd ≈ -2||f(x)||².

Arguments

• f::Function - Residual function evaluating at a point, returns a vector
• x::Vector - Current point
• d::Vector - Search direction (typically the Newton step)
• alpha_init::Float64 - Initial step size

Keyword Arguments

• c1::Float64=1e-4 - Sufficient decrease parameter (Armijo constant)
• rho::Float64=0.5 - Step size reduction factor per backtracking iteration
• max_iters::Int=20 - Maximum number of backtracking iterations
• x_buffer::Union{Nothing,Vector}=nothing - Pre-allocated buffer for trial points. When provided, avoids allocating x + α*d each iteration. Must have same length as x.

Returns

• α::Float64 - Selected step size, or 0.0 if no sufficient decrease found

geometric_reduction(f, x, d, alpha_init; rho=0.5, max_iters=20)

Geometric step-size reduction line search.

Reduces the step size by a fixed factor rho each iteration until the merit function ϕ(x) = ||f(x)||² strictly decreases:

ϕ(x + α*d) < ϕ(x)

This is a simpler alternative to armijo_backtracking — it requires only strict decrease rather than sufficient decrease, and has no Armijo constant c1.

Arguments

• f::Function - Residual function evaluating at a point, returns a vector
• x::Vector - Current point
• d::Vector - Search direction (typically the Newton step)
• alpha_init::Float64 - Initial step size

Keyword Arguments

• rho::Float64=0.5 - Step size reduction factor per iteration
• max_iters::Int=20 - Maximum number of reduction iterations
• x_buffer::Union{Nothing,Vector}=nothing - Pre-allocated buffer for trial points. When provided, avoids allocating x + α*d each iteration. Must have same length as x.

Returns

• α::Float64 - Selected step size, or 0.0 if no decrease found

constant_step(alpha)

Create a constant step-size line search that always returns alpha.

Returns a closure with the same interface as other line search methods (f, x, d, alpha_init) -> α, but ignores all arguments and returns the fixed step size.

Useful as a baseline or when the appropriate step size is known a priori.

Arguments

• alpha::Float64 - The fixed step size to return

Returns

• A function (f, x, d, alpha_init) -> alpha that always returns the fixed step size

get_qp_kkt_conditions(
    G::SimpleDiGraph,
    Js::Dict,
    zs,
    λs,
    μs::Dict,
    gs,
    ws::Dict,
    ys::Dict,
    ws_z_indices::Dict;
    θ = nothing,
    verbose::Bool = false
)

Construct KKT conditions for all players in reverse topological order.

Handles both leaf and non-leaf players differently:

• Leaf players: Standard KKT (stationarity + constraints)
• Non-leaf players: KKT with policy constraints from followers, stored as BlockVector via mortar to preserve the interleaved block structure

Arguments

• G::SimpleDiGraph - DAG of leader-follower relationships
• Js::Dict{Int, Function} - Cost function for each player: Js[i](zs...; θ) → scalar
• zs - Decision variables per player (Dict or Vector)
• λs - Lagrange multipliers per player (Dict or Vector)
• μs::Dict{Tuple{Int,Int}, Any} - Policy constraint multipliers for (leader, follower) pairs
• gs - Constraint functions per player: gs[i](z) → Vector
• ws::Dict - Remaining variables (for policy constraints)
• ys::Dict - Information variables (leader decisions)
• ws_z_indices::Dict - Index mapping: ws_z_indices[i][j] gives range where zs[j] appears in ws[i]
• θ - Parameter variables (optional)
• verbose::Bool - Print debug info

Returns

Named tuple containing:

• πs::Dict - KKT conditions per player (BlockVector for leaders, Vector for leaves)
• Ms::Dict - M matrices for followers (from Mw + Ny = 0)
• Ns::Dict - N matrices for followers
• Ks::Dict - Policy matrices K = M \ N

strip_policy_constraints(πs::Dict, hierarchy_graph::SimpleDiGraph, zs::Dict, gs)

Remove policy constraint rows from KKT conditions, keeping only stationarity + constraints.

Used for solving the reduced KKT system.

Arguments

• πs::Dict - Full KKT conditions per player
• hierarchy_graph::SimpleDiGraph - Hierarchy graph
• zs::Dict - Decision variables per player
• gs - Constraint functions per player

Returns

• πs_stripped::Dict - KKT conditions without policy constraint rows

Notes

The KKT conditions have an interleaved structure for leaders:

[grad_self | grad_f1 | policy_f1 | grad_f2 | policy_f2 | ... | own_constraints]

When πs[ii] is a BlockVector (from get_qp_kkt_conditions), blocks are accessed directly. For plain vectors (from the nonlinear solver), block sizes are computed and split_solution_vector is used. In both cases, policy blocks at indices 3, 5, 7, ... are removed.

setup_approximate_kkt_solver(
    G::SimpleDiGraph,
    Js::Dict,
    zs::Dict,
    λs::Dict,
    μs::Dict,
    gs::Vector,
    ws::Dict,
    ys::Dict,
    θs::Dict,
    all_variables::Vector,
    backend;
    verbose::Bool = false
)

Precompute symbolic KKT conditions and M/N matrix evaluation functions for nonlinear solver.

Unlike QP KKT construction which computes K = M \ N symbolically, this creates compiled functions for evaluating M and N numerically, avoiding expression blowup.

Arguments

• G::SimpleDiGraph - Hierarchy graph
• Js::Dict - Cost functions per player
• zs::Dict - Decision variables per player
• λs::Dict - Lagrange multipliers per player
• μs::Dict - Policy constraint multipliers
• gs::Vector - Constraint functions per player
• ws::Dict - Remaining variables (policy output)
• ys::Dict - Information variables (policy input)
• θs::Dict - Parameter variables per player
• all_variables::Vector - All symbolic variables
• backend - SymbolicTracingUtils backend

Keyword Arguments

• verbose::Bool=false - Print debug info
• cse::Bool=false - Enable Common Subexpression Elimination during symbolic compilation. CSE can dramatically reduce construction time and memory for problems with redundant symbolic structure (e.g., quadratic costs), but may slightly increase per-solve runtime. Recommended only when construction time is a bottleneck and you can tolerate slightly slower solve times. Default: false for maximum runtime performance.

Returns

Tuple of:

• all_augmented_variables::Vector - Variables including K matrix symbols
• setup_info::NamedTuple - Contains:
  • graph - Hierarchy graph
  • πs - KKT conditions per player
  • K_syms - Symbolic K matrices per player
  • M_fns! - Compiled M matrix evaluation functions (in-place, writes into caller-provided buffer)
  • N_fns! - Compiled N matrix evaluation functions (in-place, writes into caller-provided buffer)
  • π_sizes - KKT condition sizes per player

preoptimize_nonlinear_solver(
    hierarchy_graph::SimpleDiGraph,
    Js::Dict,
    gs::Vector,
    primal_dims::Vector{Int},
    θs::Dict;
    state_dim::Int = 2,
    control_dim::Int = 2,
    backend = default_backend(),
    verbose::Bool = false
)

Precompute all symbolic components for nonlinear solver.

This is called once before solving to build all the symbolic expressions and compile them to efficient numerical functions.

Arguments

• hierarchy_graph::SimpleDiGraph - Hierarchy graph
• Js::Dict - Cost functions per player
• gs::Vector - Constraint functions per player
• primal_dims::Vector{Int} - Primal variable dimension per player
• θs::Dict - Parameter variables per player

Keyword Arguments

• state_dim::Int=2 - State dimension (for trajectory extraction)
• control_dim::Int=2 - Control dimension (for trajectory extraction)
• backend - SymbolicTracingUtils backend
• verbose::Bool=false - Print debug info
• cse::Bool=false - Enable Common Subexpression Elimination during symbolic compilation. CSE can dramatically reduce construction time and memory for problems with redundant symbolic structure (e.g., quadratic costs), but may slightly increase per-solve runtime. Recommended only when construction time is a bottleneck and you can tolerate slightly slower solve times. Default: false for maximum runtime performance.

Returns

Named tuple containing:

• problem_vars - Problem variables (zs, λs, μs, ws, ys, all_variables)
• setup_info - Setup info from setupapproximatekkt_solver
• mcp_obj - ParametricMCP object for residual evaluation
• linsolver - LinearSolve problem for iterative solving
• all_variables - All symbolic variables
• all_augmented_variables - Variables including K matrices
• F_sym - Symbolic KKT residual vector
• π_sizes_trimmed - Trimmed KKT sizes per player
• state_dim - State dimension
• control_dim - Control dimension

compute_K_evals(z_current, problem_vars, setup_info; use_sparse=:auto, regularization=0.0, M_buffers, N_buffers, buffers=nothing)

Evaluate K (policy) matrices numerically in reverse topological order.

Uses in-place evaluation with pre-allocated buffers to avoid per-call allocations.

Note: This function is NOT thread-safe. The precomputed Mfns! and Nfns! contain shared result buffers that would cause data races if called concurrently. For multi-threaded use, each thread needs its own solver instance. See Phase 6 for planned thread-safety improvements.

Arguments

• z_current::Vector - Current solution estimate
• problem_vars::NamedTuple - Problem variables (from setupproblemvariables)
• setup_info::NamedTuple - Setup info (from setupapproximatekkt_solver)

Keyword Arguments

• use_sparse::Union{Symbol,Bool}=:auto - Strategy for M\N solve:
  • :auto - Use sparse for non-leaf players (leaders with followers have larger M), dense for leaf players (small M, no sparse overhead)
  • :always - Always use sparse LU factorization
  • :never - Always use dense solve
  • true/false - Backward-compatible aliases for :always/:never
• regularization::Float64=0.0 - Tikhonov regularization parameter λ. When > 0, solves K = (M + λI) \ N instead of K = M \ N. Improves numerical stability for near-singular M at the cost of a small bias.
• M_buffers::Dict{Int,Matrix{Float64}}=Dict() - Pre-allocated M matrix buffers. When empty, buffers are lazily allocated on first access per player. Pass pre-allocated buffers from run_nonlinear_solver to avoid re-allocation across iterations.
• N_buffers::Dict{Int,Matrix{Float64}}=Dict() - Pre-allocated N matrix buffers (same semantics as M_buffers).
• buffers::Union{Nothing, NamedTuple}=nothing - Pre-allocated buffers to reuse across calls, reducing Dict and vector allocation overhead. When provided, must contain fields: M_evals, N_evals, K_evals, follower_cache, buffer_cache, and all_K_vec. When nothing, fresh containers are allocated each call.

Returns

Tuple of:

• all_K_vec::Vector - Concatenated K matrix values for all players
• info::NamedTuple - Contains Mevals, Nevals, K_evals, status
  • status is :ok or :singular_matrix

setup_problem_variables(
    graph::SimpleDiGraph,
    primal_dims::Vector{Int},
    gs::Vector;
    backend=default_backend()
)

Construct all symbolic variables needed for the KKT system.

Arguments

• graph::SimpleDiGraph - DAG of leader-follower relationships
• primal_dims::Vector{Int} - Decision variable dimension for each player
• gs::Vector - Constraint functions for each player (gs[i](z) returns constraints)
• backend - SymbolicTracingUtils backend (default: SymbolicsBackend)

Returns

Named tuple containing:

• zs::Dict - Decision variables per player
• λs::Dict - Lagrange multipliers for constraints per player
• μs::Dict - Policy constraint multipliers (leader, follower) pairs
• ys::Dict - Information vectors (leader decisions visible to each player)
• ws::Dict - Remaining variables for policy constraints
• ws_z_indices::Dict - Index mapping: ws_z_indices[i][j] gives range where zs[j] appears in ws[i]
• all_variables::Vector - Flattened vector of all variables

setup_problem_parameter_variables(num_params_per_player::Vector{Int}; backend=default_backend())

Create symbolic parameter variables (θ) for each player's initial state.

Arguments

• num_params_per_player::Vector{Int} - Number of parameters for each player
• backend - SymbolicTracingUtils backend (default: SymbolicsBackend)

Returns

• θs::Dict{Int, Vector} - Dictionary mapping player index to their parameter variables

make_symbolic_vector(name::Symbol, player::Int, dim::Int; backend=default_backend())

Create a vector of dim symbolic variables for a player.

Valid names: (:z, :λ, :θ, :u, :x, :M, :N, :K)

make_symbolic_vector(name::Symbol, leader::Int, follower::Int, dim::Int; backend=default_backend())

Create a vector of dim symbolic variables for a leader-follower pair.

Valid names: (:μ,)

make_symbolic_matrix(name::Symbol, player::Int, rows::Int, cols::Int; backend=default_backend())

Create a rows × cols matrix of symbolic variables for a player.

Valid names: (:z, :λ, :θ, :u, :x, :M, :N, :K)

make_symbol(name::Symbol, player::Int)

Create a symbol for a player variable. Valid names: (:z, :λ, :θ, :u, :x, :M, :N, :K)

Returns Symbol("name^player"), e.g., Symbol("z^1").

make_symbol(name::Symbol, leader::Int, follower::Int)

Create a symbol for a leader-follower pair variable. Valid names: (:μ,)

Returns Symbol("name^(leader-follower)"), e.g., Symbol("μ^(1-2)").

Return a fresh SymbolicsBackend instance for symbolic tracing.

is_root(G::SimpleDiGraph, node::Int)

Check if node has no incoming edges (i.e., is a root/top-level leader).

is_leaf(G::SimpleDiGraph, node::Int)

Check if node has no outgoing edges (i.e., is a leaf/pure follower).

has_leader(G::SimpleDiGraph, node::Int)

Check if node has any incoming edges (i.e., has a leader).

get_roots(G::SimpleDiGraph)

Return all root nodes (nodes with no incoming edges).

get_all_leaders(G::SimpleDiGraph, node::Int)

Return all ancestors of node up to root (all direct and indirect leaders).

get_all_followers(G::SimpleDiGraph, node::Int)

Return all descendants of node (entire subtree of followers).

evaluate_kkt_residuals(
    πs::Dict,
    all_variables::Vector,
    sol::Vector,
    θs::Dict,
    parameter_values::Dict;
    tol::Float64 = 1e-6,
    verbose::Bool = false,
    should_enforce::Bool = false
)

Evaluate symbolic KKT conditions at the numerical solution.

Substitutes numerical values and computes residual norms to verify solution validity.

Arguments

• πs::Dict{Int, Any} - Symbolic KKT conditions per player
• all_variables::Vector - All symbolic decision variables
• sol::Vector - Numerical solution vector
• θs::Dict{Int, Any} - Symbolic parameter variables per player
• parameter_values::Dict{Int, Vector} - Numerical values for parameters

Keyword Arguments

• tol::Float64=1e-6 - Tolerance for checking satisfaction
• verbose::Bool=false - Print residual details
• should_enforce::Bool=false - Assert if conditions not satisfied

Returns

• π_eval::Vector{Float64} - Evaluated residual vector

verify_kkt_solution(solver, sol::Vector, θs::Dict, parameter_values::Dict; kwargs...)

Verify that a solution satisfies the KKT conditions. The solver must have precomputed.setup_info.πs and related fields (NonlinearSolver).

This is a convenience wrapper that extracts the necessary data from the solver and calls evaluate_kkt_residuals.

Note: For NonlinearSolver, this function evaluates the KKT conditions with the actual K (policy derivative) values computed at the solution. The residuals should be small for a properly converged solution.

Arguments

• solver - The solver used to find the solution (NonlinearSolver)
• sol::Vector - The solution vector (from result.sol)
• θs::Dict - Symbolic parameter variables per player
• parameter_values::Dict - Numerical values for parameters

Keyword Arguments

• tol::Float64=1e-6 - Tolerance for checking satisfaction
• verbose::Bool=false - Print residual details
• should_enforce::Bool=false - Assert if conditions not satisfied

Returns

• π_eval::Vector{Float64} - Evaluated residual vector

Example

result = solve_raw(solver, parameter_values)
residuals = verify_kkt_solution(solver, result.sol, θs, parameter_values; verbose=true)

enable_timing!()

Enable timing instrumentation for all @timeit_debug calls.

disable_timing!()

Disable timing instrumentation for all @timeit_debug calls (default). When disabled, @timeit_debug has near-zero overhead (one atomic boolean check).

is_timing_enabled() -> Bool

Check whether timing instrumentation is currently enabled.

with_timing(f)

Execute f() with timing enabled, restoring the previous state afterward.

Example

using TimerOutputs  # Required: MixedHierarchyGames does not re-export TimerOutput
to = TimerOutput()
with_timing() do
    solve(solver, parameter_values; to)
end
show(to)

@timeit_debug timer_output "label" expr

Conditionally timed block. When TIMING_ENABLED[] is true, records timing via TimerOutputs.jl's begin_timed_section!/end_timed_section! API with proper exception handling. When false, executes expr directly with near-zero overhead.

Returns the value of expr in both modes.

Examples

to = TimerOutput()
enable_timing!()
result = @timeit_debug to "my section" begin
    expensive_computation()  # timed
end
disable_timing!()
result = @timeit_debug to "my section" begin
    expensive_computation()  # NOT timed — near-zero overhead
end

TIMING_ENABLED

Global flag controlling whether @timeit_debug records timing data. When false (default), @timeit_debug executes the body with near-zero overhead (one atomic boolean check + try/finally frame). When true, @timeit_debug delegates to TimerOutputs.jl for full instrumentation.

Toggle with enable_timing! and disable_timing!.

_build_augmented_z_est(ii, z_est, K_evals, graph, follower_cache, buffer_cache)

Build augmented z vector for player ii including follower K evaluations.

Arguments

• ii::Int - Player index
• z_est::Vector - Current z estimate
• K_evals::Vector - Numerical K matrices per player (indexed by player ID)
• graph::SimpleDiGraph - Hierarchy graph
• follower_cache::Vector - Cache for follower lists (indexed by player ID)
• buffer_cache::Vector - Cache for augmented buffers (indexed by player ID)

Returns

• augmented_z::Vector - z_est augmented with follower K values

_build_extractor(indices::UnitRange{Int}, total_len::Int)

Build a sparse extraction matrix for policy constraints.

Used to extract the follower's decision variables (zs[j]) from the full policy response (Ks[j] * ys[j]). The indices come from wszindices, which explicitly tracks where each player's variables appear in the ws vector.

Example

If ws[j] = [zs[j], zs[other], λs[j], ...] and zs[j] has dimension 3, then:

• indices = 1:3 (from wszindices[j][j])
• extractor * (Ks[j] * ys[j]) gives the zs[j] portion of the policy response

Returns a sparse matrix E such that E * v extracts v[indices].

_build_parametric_mcp(πs::Dict, variables::Vector, θs::Dict)

Build a ParametricMCP from KKT conditions during QPSolver construction.

The MCP is cached in precomputed to avoid rebuilding it on each solve() call. This provides significant performance benefits for repeated solves with different parameter values (e.g., different initial states).

Note: We use ParametricMCPs primarily for its compiled f! and jacobian_z! functions. The bounds infrastructure (-∞ to ∞) is unused since we only support equality constraints. See task MixedHierarchyGames.jl-s6u for potential future optimization.

_construct_augmented_variables(ii, all_variables, K_syms, G)

Build augmented variable list for player ii including follower K matrices.

For computing M and N that depend on follower policies, we need to include symbolic K matrices in the variable list.

Arguments

• ii::Int - Player index
• all_variables::Vector - Base symbolic variables
• K_syms::Dict - Symbolic K matrices per player
• G::SimpleDiGraph - Hierarchy graph

Returns

• augmented::Vector - Variables including follower K matrix entries

_extract_joint_strategy(sol, primal_dims, state_dim, control_dim)

Extract per-player trajectories from solution vector and build JointStrategy. Shared helper used by both QPSolver and NonlinearSolver.

The solution vector may contain dual variables (λ, μ) after the primal variables. Only the first sum(primal_dims) elements are used.

_merge_options(base::NonlinearSolverOptions; kwargs...) -> NonlinearSolverOptions

Merge keyword overrides into a base NonlinearSolverOptions. nothing values are treated as "no override" and the base option is kept.

This deduplicates the something() override pattern in solve() and solve_raw().

_run_qp_solver(
    hierarchy_graph::SimpleDiGraph,
    Js::Dict,
    gs::Vector,
    primal_dims::Vector{Int},
    θs::Dict,
    parameter_values::Dict;
    solver::Symbol = :linear,
    verbose::Bool = false
)

Internal QP solver that orchestrates KKT construction and solving.

Note: This is an internal function. Users should prefer QPSolver + solve() for better performance (the MCP is cached in QPSolver.precomputed.parametric_mcp). This function rebuilds the MCP on every call, which is inefficient for repeated solves.

Arguments

• hierarchy_graph::SimpleDiGraph - Hierarchy graph
• Js::Dict - Cost functions per player: Js[i](zs...; θ) → scalar
• gs::Vector - Constraint functions per player: gs[i](z) → Vector
• primal_dims::Vector{Int} - Primal variable dimension per player
• θs::Dict - Symbolic parameter variables per player
• parameter_values::Dict - Numerical parameter values per player

Keyword Arguments

• solver::Symbol=:linear - Solver to use: :linear (direct) or :path (MCP)
• verbose::Bool=false - Print debug info

Returns

Named tuple containing:

• sol::Vector - Solution vector
• status - Solver status
• info - Additional solver info
• vars - Problem variables (zs, λs, μs, etc.)

_solve_K!(M, N, player_idx; use_sparse=false, regularization=0.0)

Solve K = M \ N with protection against singular or ill-conditioned M matrices.

When use_sparse=true, converts M to sparse format before solving, which can be beneficial for large M matrices (>100 rows) with structural sparsity from the KKT system.

When regularization > 0, applies Tikhonov regularization: K = (M + λI) \ N, which improves numerical stability for near-singular M at the cost of a small bias in the solution. Regularization is applied in-place on M's diagonal and restored via try-finally to avoid allocating M + λI. The roundtrip M[i,i] + λ - λ may differ from the original by up to machine epsilon (~2.2e-16).

Returns a NaN-filled matrix (same size as expected K) if M is singular or severely ill-conditioned, with a warning.

_to_parameter_dict(initial_state)

Convert initial state to Dict{Int, Vector} parameter format.

Accepted formats:

• Dict{Int, Vector}: Returned as-is (no copy)
• AbstractVector of AbstractVectors: Converted to Dict with 1-based integer keys

Throws ArgumentError for unrecognized types.

_validate_constraint_functions(gs::Vector, zs::Dict)

Validate that constraint functions have correct signatures, return Vectors, and only depend on the player's own decision variables (decoupled constraints).

Called during problem setup to catch errors early with clear messages.

Arguments

• gs::Vector - Constraint functions per player: gs[i](z) → Vector
• zs::Dict - Decision variables per player (used to test function signatures)

Throws

• ArgumentError if gs[i] has wrong signature, doesn't return AbstractVector, or contains variables from other players (coupled constraint)

_validate_parameter_values(parameter_values::Dict, θs::Dict)

Validate parameter_values against expected θs structure. Throws ArgumentError on mismatch.

_validate_solver_inputs(hierarchy_graph, Js, gs, primal_dims, θs)

Validate inputs for solver constructors. Throws ArgumentError on invalid input. Used by both QPSolver and NonlinearSolver.

_verify_linear_system(mcp, n::Int, θs::Dict)

Verify that the KKT system is affine (constant Jacobian) as required for QP/LQ games.

QPSolver assumes the KKT system F(z) = 0 is affine in z, i.e., F(z) = Jz + b where J is constant. This allows direct linear solve: z = -J⁻¹b. If the system is nonlinear, the linear solve will produce incorrect results.

This check evaluates the Jacobian at two random points during construction. If they differ, a warning is issued. The check runs once at construction time, not at solve time.

flatten_trajectory(xs::Vector{Vector{T}}, us::Vector{Vector{T}}) where T

Flatten state and control trajectories into a single vector.

ordered_player_indices(d::Dict)

Return the keys of d as a sorted vector, providing a canonical player ordering.

This is a convenience wrapper around sort(collect(keys(d))) used throughout the codebase to iterate over player-indexed dictionaries in a deterministic order.

vcat_ordered!(buf, d::Dict, order)

Concatenate d[k] for each k in order into pre-allocated buffer buf using copyto!. This avoids the intermediate allocations of reduce(vcat, ...).

Returns buf.

TrajectoryGamesBase.solve_trajectory_game!(
    solver::NonlinearSolver,
    game::HierarchyGame,
    initial_state;
    kwargs...
)

Solve a nonlinear hierarchy game.

Arguments

• solver::NonlinearSolver - The nonlinear solver instance
• game::HierarchyGame - The hierarchy game to solve
• initial_state - Initial state per player (Dict{Int, Vector} or Vector of Vectors)

Keyword Arguments

• initial_guess::Union{Nothing, Vector}=nothing - Warm start
• verbose::Bool=false - Print iteration info

Returns

• JointStrategy over OpenLoopStrategys for each player

TrajectoryGamesBase.solve_trajectory_game!(
    solver::QPSolver,
    game::HierarchyGame,
    initial_state;
    kwargs...
)

Solve a QP (linear-quadratic) hierarchy game.

Arguments

• solver::QPSolver - The QP solver instance
• game::HierarchyGame - The hierarchy game to solve
• initial_state - Initial state per player (Dict{Int, Vector} or Vector of Vectors)

Keyword Arguments

• verbose::Bool=false - Print debug info

Returns

• JointStrategy containing OpenLoopStrategy for each player