💻 computer science

Efficiently Solving Mixed-Hierarchy Games with Quasi-Policy Approximations

This paper introduces a quasi-policy approximation and an inexact Newton method to efficiently solve N-robot forest-structured mixed-hierarchy games, overcoming the intractability of high-order derivatives in standard KKT conditions while achieving local exponential convergence and real-time performance in both simulation and hardware experiments.

Original authors: Hamzah Khan, Dong Ho Lee, Jingqi Li, Tianyu Qiu, Christian Ellis, Jesse Milzman, Wesley Suttle, David Fridovich-Keil

Published 2026-05-18

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Hamzah Khan, Dong Ho Lee, Jingqi Li, Tianyu Qiu, Christian Ellis, Jesse Milzman, Wesley Suttle, David Fridovich-Keil

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a busy highway where several cars need to merge into a single lane. Some cars are in a convoy, moving together, while others are trying to slip in between them. In the real world, these cars don't just drive randomly; they make decisions based on what they think the other cars will do.

This paper introduces a new way for robots (or self-driving cars) to figure out the perfect plan for these complex situations. Here is the breakdown using simple analogies:

The Problem: A Messy Mix of Bosses and Peers

Usually, game theory (the math of strategy) handles two types of relationships:

The "Boss" (Stackelberg): One robot is the leader, and the others are followers. The leader moves first, and the followers react. Think of a general giving orders to soldiers.
The "Peers" (Nash): Everyone moves at the same time, trying to guess what the others will do. Think of a group of friends deciding where to eat dinner; no one is in charge, they just negotiate.

The Challenge: Real life is messy. Sometimes you have a mix. In the paper's example, Car 1 is the "Boss" of Car 2, but Car 2 and Car 3 are "Peers" negotiating at the same time. Existing math tools were too slow or rigid to handle this specific "mixed" structure, especially when the cars have complex physics (like not being able to turn instantly) and non-linear goals (like avoiding a crash without just minimizing distance).

The Solution: The "Quasi-Policy" Shortcut

To solve this, the authors had to deal with a mathematical nightmare. To find the perfect plan, the math usually requires calculating how a robot's plan changes if another robot's plan changes, which changes another robot's plan, and so on. It's like trying to calculate the ripple effect of a stone thrown in a pond, but the ripples keep bouncing off other stones and changing shape. The math gets so complicated (involving "high-order derivatives") that computers can't solve it in real-time.

The Trick: The authors invented a "Quasi-Policy Approximation."

The Analogy: Imagine you are the leader of a team. To plan your move, you usually need to know exactly how your teammates will react to your reaction to their reaction to your reaction. That's impossible to calculate perfectly.
The Fix: The authors say, "Let's assume your teammates' reactions are simple and linear for a split second." They ignore the super-complex, deep-layer ripples and only look at the immediate, first-level reaction.
The Result: This "quasi-policy" is a smart shortcut. It simplifies the math just enough that a computer can solve it instantly, while still being accurate enough to get the right answer.

The Engine: The "Inexact Newton" Method

Once they simplified the math using the shortcut, they needed a way to actually solve the equations. They used a method called an "Inexact Newton Method."

The Analogy: Imagine you are trying to find the bottom of a valley in the fog. A perfect method would require you to map every single inch of the valley before moving. The "Inexact" method is like taking a confident step downhill based on the slope you can see right now. If you aren't quite at the bottom, you take another step.
Why it works: The paper proves that even though they are taking "approximate" steps (because of their shortcut), they will zoom toward the perfect solution very quickly (exponentially fast) once they get close.

The Proof: Real Robots and Simulations

The team didn't just write theory; they built a software library (written in a language called Julia) and tested it:

Hardware Test: They put three real robots on the floor. One was a "guard," one was a "pursuer," and one was a "target." The guard had to lead the target while the pursuer tried to catch it. The robots calculated their moves in real-time (taking about 13 milliseconds per calculation) and successfully navigated the game without crashing.
Simulation Test: They simulated a convoy of cars merging. They tested different "hierarchy" rules (who is the boss, who is a peer).
- Result: When the hierarchy changed, the cars' behavior changed logically. If Car 1 was the boss, it sped up to stay ahead. If they were peers, Car 1 slowed down to let the other car merge. The system handled these complex, non-linear rules smoothly.

Summary

The paper presents a new "rulebook" for robots to play games where some are bosses and some are peers. By using a clever mathematical shortcut (ignoring overly complex future ripples) and a fast-solving engine, they allow robots to make split-second, safe, and strategic decisions in complex, mixed-structure environments. They proved this works on both real robots and computer simulations.

Technical Summary: Efficiently Solving Mixed-Hierarchy Games with Quasi-Policy Approximations

Problem Statement

Multi-robot coordination often involves complex information structures where decision-making is neither purely simultaneous (Nash) nor purely sequential (Stackelberg), but a mixture of both. Existing game-theoretic solvers struggle to handle these mixed-hierarchy games, particularly when they involve:

Nonlinear constraints (e.g., arising from nonlinear motion dynamics).
Nonquadratic objectives (encoding complex tasks beyond simple quadratic costs).
Forest-structured information patterns, where robots form leader-follower chains (trees) that interact via Nash equilibria across different branches.

A primary theoretical and computational barrier is that deriving the first-order optimality conditions (Karush–Kuhn–Tucker or KKT conditions) for such games requires computing increasingly high-order derivatives of followers' best-response policies as the hierarchy depth increases. This renders direct solution methods intractable for deep hierarchies or complex dynamics.

Methodology

The authors propose a framework to solve $N$ -robot forest-structured mixed-hierarchy games by approximating the optimality conditions to avoid high-order derivative computations.

1. Problem Formulation

The game is modeled as a directed acyclic graph $G$ where nodes represent robots and edges represent leader-follower relationships. The authors assume $G$ is a forest (a union of disconnected trees), ensuring each robot has at most one direct leader.

Strategies: Each robot $i$ minimizes an objective $J_i(z)$ subject to equality constraints $g_i(z_i)=0$ (e.g., dynamics).
Equilibrium Definition: A mixed-hierarchy equilibrium requires each robot to satisfy:
- Stackelberg conditions: Optimizing its strategy and its subtree's strategies given the leaders' strategies.
- Nash conditions: Optimizing its strategy given the strategies of robots in other branches (Nash relatives) that it cannot influence.

2. Quasi-Policy Approximation

To circumvent the intractability of high-order derivatives in the exact KKT conditions, the authors introduce a quasi-policy approximation:

Mechanism: When deriving the KKT conditions for a leader, the method embeds the followers' best-response policies. However, instead of computing the full recursive dependence of these policies on the leader's strategy (which generates higher-order derivatives), the method ignores higher-order derivatives of the followers' policies.
Effect: This reduces the recursive complexity, allowing the KKT system to be constructed using only first-order policy gradients. This extends recent work on feedback Nash and Stackelberg games to the mixed-hierarchy setting.

3. Inexact Newton Solver

The authors develop an inexact Newton method to solve the resulting approximate KKT system:

Algorithm: The solver iterates in reverse topological order to construct the approximate KKT conditions for each robot. It then solves a linear system using an approximate Jacobian (where high-order terms are zeroed out) to determine a search direction.
Convergence: The paper provides a theoretical proof of local exponential convergence for games with nonquadratic objectives and nonlinear constraints, provided the higher-order policy sensitivities are small relative to first-order gradients (a condition often met in control problems with strong regularization).

Key Contributions

Principled Approximation: A novel method for constructing approximate optimality conditions for nonlinear, equality-constrained mixed-hierarchy games by embedding followers' best responses as locally first-order policy approximations (quasi-policies).
Scalable Algorithm: An efficient, flexible solver for arbitrary forest-structured mixed-hierarchy games with nonlinear costs and constraints. The authors prove and empirically demonstrate local exponential convergence.
Open-Source Implementation: The release of MixedHierarchyGames.jl, a highly optimized Julia library. The library supports complex scenarios, including hardware experiments and simulations with hundreds of variables.

Experimental Results

The approach was evaluated in both hardware and simulation:

Hardware (Target Guarding): A three-robot experiment involving a pursuer, a guard, and a target. The guard leads the target, while both have a Nash relationship with the pursuer. The solver ran in real-time (mean 13.6 ms per call) on a standard CPU, successfully coordinating the robots in a receding-horizon fashion to achieve the target-guarding objective.
Simulation (Convoy Merging): A four-vehicle merging scenario was tested under four different hierarchy structures: pure Nash, two mixed hierarchies, and a pure Stackelberg chain.
- The solver demonstrated that changing the hierarchy structure leads to distinct, interpretable behaviors (e.g., a leader vehicle accelerating to maintain position vs. yielding).
- All resulting equilibria ensured safe interactions.
- Empirical results confirmed the monotone decay of the merit function and local exponential convergence near the equilibrium, validating Theorem 1.

Significance and Claims

The paper claims to bridge a critical gap in multi-robot planning by enabling the efficient solution of mixed-hierarchy games with nonlinear dynamics and nonquadratic objectives, which were previously limited to linear/quadratic settings or simple structures.

Real-Time Feasibility: The quasi-policy approximation successfully removes the computational bottleneck of high-order derivatives, enabling real-time convergence for complex information structures.
Generalizability: The framework unifies Nash and Stackelberg games as special cases and handles arbitrary forest topologies.
Practical Impact: The method is demonstrated to be viable for real-world deployment, as evidenced by the hardware experiment where robots successfully executed plans generated by the solver in a dynamic environment.

The authors conclude that while the forest structure assumption (Assumption 2) currently limits the scope to single-leader trees, the proposed quasi-policy approach provides a robust foundation for solving complex, asymmetric information games in robotics. Future work aims to relax this assumption to allow multi-leader structures and incorporate inequality constraints.