Multi-Leader Congestion Games with an Adversary
| Autor: | Tobias Harks, Mona Henle, Max Klimm, Jannik Matuschke, Anja Schedel |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2021 |
| Předmět: |
FOS: Computer and information sciences
TheoryofComputation_MISCELLANEOUS Computer Science::Computer Science and Game Theory Artificial Intelligence (cs.AI) Discrete Mathematics (cs.DM) Computer Science - Computer Science and Game Theory Computer Science - Artificial Intelligence TheoryofComputation_GENERAL General Medicine Computer Science and Game Theory (cs.GT) Computer Science - Discrete Mathematics |
| Popis: | 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 \approx 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 $\alpha$-approximate equilibrium for any $\alpha |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|