Multi-Leader Congestion Games with an Adversary


  • Tobias Harks Augsburg University
  • Mona Henle University of Applied Sciences
  • Max Klimm Technische Universität Berlin
  • Jannik Matuschke KU Leuven
  • Anja Schedel Augsburg University



Game Theory And Economic Paradigms (GTEP)


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 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 (approximately equal to 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 A-approximate equilibrium for any A < K. Thus A = K is the smallest possible value of A such that the existence of an A-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 A among all A-approximate equilibria of the given instance.




How to Cite

Harks, T., Henle, M., Klimm, M., Matuschke, J., & Schedel, A. (2022). Multi-Leader Congestion Games with an Adversary. Proceedings of the AAAI Conference on Artificial Intelligence, 36(5), 5068-5075.



AAAI Technical Track on Game Theory and Economic Paradigms