Multi-Leader Congestion Games with an Adversary

Abstract

We study a multi-leader single-follower congestion game where multiple users choose subsets out of a given set of resources and an adversary attacks the resources with maximum loads, causing additional costs for the users. We first show that the resulting strategic game among the leaders admits a pure Nash equilibrium if the users’ strategy-spaces are given by matroids and the resource costs are linear and identical. However, equilibria may fail to exist already when strategy spaces are not matroids or the linear cost coefficients are not identical. We therefore consider approximate equilibria for the case that each user chooses one resource and the resource costs are linear but non-identical. Our main result establishes that K ≈ 1.1974 is the smallest possible factor such that the existence of a K-approximate equilibrium is guaranteed for all instances of the game. We also provide a polynomial time algorithm for computing an α-approximate equilibrium with the smallest possible factor α ≤ K for a given instance, in particular finding an exact equilibrium if one exists.