Author name cluster

Mona Henle

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers

1 author row

JAIR Journal 2025 Journal Article

Multi-Leader Congestion Games with an Adversary

Tobias Harks
Mona Henle
Max Klimm
Jannik Matuschke
Anja Schedel

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.

PDF Details DOI

AAAI Conference 2022 Conference Paper

Multi-Leader Congestion Games with an Adversary

Tobias Harks
Mona Henle
Max Klimm
Jannik Matuschke
Anja Schedel

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.

PDF Details