# Multi-Leader Congestion Games with an Adversary

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 6 of its 32 references that are in the map.
- First posted on arXiv 14 Dec 2021.

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

- [An Existence Result for Hierarchical Stackelberg v/s Stackelberg Games](https://mlsanity.com/paper/1401.0186/) (2013)
- [Complexity and Approximation of the Continuous Network Design Problem](https://mlsanity.com/paper/1307.4258/) (2013)
- [Fare Evasion in Transit Networks](https://mlsanity.com/paper/1405.2826/) (2014)
- [Leadership in Singleton Congestion Games: What is Hard and What is Easy](https://mlsanity.com/paper/1808.10209/) (2018)
- [Toll Caps in Privatized Road Networks](https://mlsanity.com/paper/1802.10514/) (2018)
- [Capacity and Price Competition in Markets with Congestion Effects](https://mlsanity.com/paper/1905.05683/) (2019)

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

- [The Complexity of Optimizing Atomic Congestion](https://mlsanity.com/paper/2312.10219/) (2023)

## Abstract (arXiv)

We study a multi-leader single-follower congestion game where multiple users (leaders) choose one resource out of a set of resources and, after observing the realized loads, an adversary (single-follower) attacks the resources with maximum loads, causing additional costs for the leaders. For the resulting strategic game among the leaders, we show that pure Nash equilibria may fail to exist and therefore, we consider approximate equilibria instead. As our first main result, we show that the existence of a K-approximate equilibrium can always be guaranteed, where K ≈ 1.1974 is the unique solution of a cubic polynomial equation. To this end, we give a polynomial time combinatorial algorithm which computes a K-approximate equilibrium. The factor K is tight, meaning that there is an instance that does not admit an α-approximate equilibrium for any α<K. Thus α=K is the smallest possible value of α such that the existence of an α-approximate equilibrium can be guaranteed for any instance of the considered game. Secondly, we focus on approximate equilibria of a given fixed instance. We show how to compute efficiently a best approximate equilibrium, that is, with smallest possible α among all α-approximate equilibria of the given instance.