Who Plays First? Optimizing the Order of Play in Stackelberg Games with Many Robots
<|reference_start|>Who Plays First? Optimizing the Order of Play in Stackelberg Games with Many Robots: 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.<|reference_end|>
@article{hu2024who,
    title={Who Plays First? Optimizing the Order of Play in Stackelberg Games with
  Many Robots},
    author={Haimin Hu, Gabriele Dragotto, Zixu Zhang, Kaiqu Liang, Bartolomeo
  Stellato, Jaime F. Fisac},
    journal={arXiv preprint arXiv:2402.09246},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.09246},
    primaryClass={cs.RO cs.AI cs.SY eess.SY math.OC}
}