# Who Plays First? Optimizing the Order of Play in Stackelberg Games with Many Robots

arXiv: https://arxiv.org/abs/2402.09246 · HTML: https://mlsanity.com/paper/2402.09246/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 69 references that are in the map.
- First posted on arXiv 14 Feb 2024.

## Builds on (most cited first, 28 of 28)

- [AirSim: High-Fidelity Visual and Physical Simulation for Autonomous Vehicles](https://mlsanity.com/paper/1705.05065/) (2017)
- [Hamilton-Jacobi Reachability: A Brief Overview and Recent Advances](https://mlsanity.com/paper/1709.07523/) (2017)
- [Multi-Agent Pathfinding: Definitions, Variants, and Benchmarks](https://mlsanity.com/paper/1906.08291/) (2019)
- [The Safety Filter: A Unified View of Safety-Critical Control in Autonomous Systems](https://mlsanity.com/paper/2309.05837/) (2023)
- [Hierarchical Game-Theoretic Planning for Autonomous Vehicles](https://mlsanity.com/paper/1810.05766/) (2018)
- [Robust Model Predictive Shielding for Safe Reinforcement Learning with Stochastic Dynamics](https://mlsanity.com/paper/1910.10885/) (2019)
- [Efficient Iterative Linear-Quadratic Approximations for Nonlinear Multi-Player General-Sum Differential Games](https://mlsanity.com/paper/1909.04694/) (2019)
- [On Infusing Reachability-Based Safety Assurance within Planning Frameworks for Human-Robot Vehicle Interactions](https://mlsanity.com/paper/2012.03390/) (2020)
- [Maximum-Entropy Multi-Agent Dynamic Games: Forward and Inverse Solutions](https://mlsanity.com/paper/2110.01027/) (2021)
- [Safety Assurances for Human-Robot Interaction via Confidence-aware Game-theoretic Human Models](https://mlsanity.com/paper/2109.14700/) (2021)
- [Prioritized Planning Algorithms for Trajectory Coordination of Multiple Mobile Robots](https://mlsanity.com/paper/1409.2399/) (2014)
- [FaSTrack: a Modular Framework for Real-Time Motion Planning and Guaranteed Safe Tracking](https://mlsanity.com/paper/2102.07039/) (2021)
- [Active Uncertainty Reduction for Safe and Efficient Interaction Planning: A Shielding-Aware Dual Control Approach](https://mlsanity.com/paper/2302.00171/) (2023)
- [SHARP: Shielding-Aware Robust Planning for Safe and Efficient Human-Robot Interaction](https://mlsanity.com/paper/2110.00843/) (2021)
- [Deception Game: Closing the Safety-Learning Loop in Interactive Robot Autonomy](https://mlsanity.com/paper/2309.01267/) (2023)
- [Dynamic Tube MPC for Nonlinear Systems](https://mlsanity.com/paper/1907.06553/) (2019)
- [Planning, Fast and Slow: A Framework for Adaptive Real-Time Safe Trajectory Planning](https://mlsanity.com/paper/1710.04731/) (2017)
- [The Computation of Approximate Generalized Feedback Nash Equilibria](https://mlsanity.com/paper/2101.02900/) (2021)
- [MPOGames: Efficient Multimodal Partially Observable Dynamic Games](https://mlsanity.com/paper/2210.10814/) (2022)
- [Multi-Step Model Predictive Safety Filters: Reducing Chattering by Increasing the Prediction Horizon](https://mlsanity.com/paper/2309.11453/) (2023)
- [Safe Sequential Path Planning of Multi-Vehicle Systems via Double-Obstacle Hamilton-Jacobi-Isaacs Variational Inequality](https://mlsanity.com/paper/1412.7223/) (2014)
- [Stackelberg Meta-Learning for Strategic Guidance in Multi-Robot Trajectory Planning](https://mlsanity.com/paper/2211.13336/) (2022)
- [The Critical Node Game](https://mlsanity.com/paper/2303.05961/) (2023)
- [When Nash Meets Stackelberg](https://mlsanity.com/paper/1910.06452/) (2019)
- [Leadership Inference for Multi-Agent Interactions](https://mlsanity.com/paper/2310.18171/) (2023)
- [Learning Hyperplanes for Multi-Agent Collision Avoidance in Space](https://mlsanity.com/paper/2311.09439/) (2023)
- [The computation of approximate feedback Stackelberg equilibria in multi-player nonlinear constrained dynamic games](https://mlsanity.com/paper/2401.15745/) (2024)
- [Stackelberg Strategic Guidance for Heterogeneous Robots Collaboration](https://mlsanity.com/paper/2202.01877/) (2022)

## Built on by (most cited first, 1 of 1)

- [TSC: Topology-Conditioned Stackelberg Coordination for Multi-Agent Reinforcement Learning in Interactive Driving](https://mlsanity.com/paper/2602.23896/) (2026)

## Abstract (arXiv)

We consider the multi-agent spatial navigation problem of computing the socially optimal order of play, i.e., the sequence in which the agents commit to their decisions, and its associated equilibrium in an N-player Stackelberg trajectory game. We model this problem as a mixed-integer optimization problem over the space of all possible Stackelberg games associated with the order of play's permutations. To solve the problem, we introduce Branch and Play (B&P), an efficient and exact algorithm that provably converges to a socially optimal order of play and its Stackelberg equilibrium. As a subroutine for B&P, we employ and extend sequential trajectory planning, i.e., a popular multi-agent control approach, to scalably compute valid local Stackelberg equilibria for any given order of play. We demonstrate the practical utility of B&P to coordinate air traffic control, swarm formation, and delivery vehicle fleets. We find that B&P consistently outperforms various baselines, and computes the socially optimal equilibrium.