# multileader_congestion_games_with_an_adversary__e40413f3.pdf

Multi-Leader Congestion Games with an Adversary

TOBIAS HARKS, University of Passau, Germany MONA HENLE , University of Applied Sciences Augsburg, Germany MAX KLIMM, TU Berlin, Germany JANNIK MATUSCHKE, Research Center for Operations Management, KU Leuven, Belgium ANJA SCHEDEL, University of Passau, Germany

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 𝐾 1.1974 is the smallest possible factor such that the existence of a 𝐾-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 𝛼 𝐾for a given instance, in particular finding an exact equilibrium if one exists.

JAIR Associate Editor: Davide Grossi

JAIR Reference Format: Tobias Harks, Mona Henle, Max Klimm, Jannik Matuschke, and Anja Schedel. 2025. Multi-Leader Congestion Games with an Adversary. Journal of Artificial Intelligence Research 83, Article 29 (August 2025), 34 pages. doi: 10.1613/jair.1.15768

1 Introduction

Congestion games serve as a fundamental model for the competition over scarce, congestion-sensitive resources: Users (or players) choose subsets of a common resource set and the cost a user experiences depends on the utilization of the chosen resources. Applications range from network routing, wireless spectrum sharing, cloud computing, scheduling, facility location, and many more. From a theoretical point of view, congestion games are conceptually simple and have appealing properties, for instance, a pure Nash equilibrium is guaranteed to exist by the famous result of Rosenthal [54]. This combination of nice theoretic behaviour and the ability to capture many aspects of practical applications has spurred the interest of the research community and led to many deep and influential results (see, e.g., [56, 16]). In this paper, we study a model where a congestion game is complemented with an adversary subsequently attacking some of the resources after the players of the congestion game have chosen their strategies, causing additional costs for them. Specifically, we assume that the adversary is greedy, wanting to cause as much damage

Corresponding Author.

Authors Contact Information: Tobias Harks, orcid: 0000-0002-7873-3779, tobias.harks@uni-passau.de, University of Passau, Passau, Germany; Mona Henle, orcid: 0009-0000-8006-9216, mona-henle@arcor.de, University of Applied Sciences Augsburg, Augsburg, Germany; Max Klimm, orcid: 0000-0002-9061-2267, klimm@math.tu-berlin.de, TU Berlin, Berlin, Germany; Jannik Matuschke, orcid: 0000-0002-74633279, jannik.matuschke@kuleuven.be, Research Center for Operations Management, KU Leuven, Leuven, Belgium; Anja Schedel, orcid: 0000-0003-1417-651X, anja.schedel@uni-passau.de, University of Passau, Passau, Germany.

This work is licensed under a Creative Commons Attribution International 4.0 License.

2025 Copyright held by the owner/author(s). doi: 10.1613/jair.1.15768

Journal of Artificial Intelligence Research, Vol. 83, Article 29. Publication date: August 2025.

29:2 Harks, Henle, Klimm, Matuschke & Schedel

as possible, and, consequently, only attacks resources having largest load. For classic load balancing congestion games [10] or network congestion games [54], this type of adversary is very natural: Consider the scenario of clients each wanting to run a job on a computer server which can be selected from a set of available servers. In Denial-of-Service (Do S) attacks, it makes sense for the adversary to attack a server with maximum load, because this way, the attack reaches the largest number of clients and, ultimately, causes maximum damage. As another example, consider the scenario that users choose one of several entries in order to enter a sports arena. For this example, a promotional campaign who wants to reach as many people as possible will use an entry point with maximum load causing additional delays to the entry. The model described above constitutes a Stackelberg, or Leader-Follower game a game in which the players are partitioned into leaders, acting first, and followers, choosing their strategy only after the leaders choices become apparent. Such hierarchical relationships appear in many real-world problems, for example, in applications from the security domain [34, 35, 59, 21, 55, 44, 4], pricing or toll setting problems [33, 37, 28, 27], supply chain and marketing management [29], voting scenarios [60], and many others. Due to this broad variety of applications, Stackelberg games have received considerable attention from scientists in artificial intelligence, operations research, theoretical computer science, economics, and other disciplines. While most works in the literature consider the case of a single leader, the case of multiple leaders (that occurs in our model) playing a simultaneous-move strategic game subject to one or more followers has received much less attention and only few results with respect to the existence and computational complexity of equilibria are known. Note that the multi-leader case applies to several scenarios, for example, in the analysis of deregulated electricity markets in which some of the large energy producers are the leaders and the smaller energy producers and independent system operators are the followers; see [39], or in the security context when multiple defenders protect common targets, see [38, 43, 21, 20]. One well-known obstacle in the analysis of multi-leader games even in the realm of continuous formulations with convex action spaces for the leaders and single-valuedness of the followers response is the inherent non-convexity of the best-response correspondence that results in non-existence of pure Nash equilibria [36, 21]. Indeed, it turns out that pure Nash equilibria fail to exist for the class of games studied in this paper, already in very simple settings: Even in symmetric singleton congestion games where each player chooses exactly one of the resources, and linear congestion cost functions, one cannot guarantee existence of pure Nash equilibria among the leaders. (The adversary is assumed to use a fixed budget to attack one of the maximum load resources uniformly at random.) The observed non-existence of pure Nash equilibria motivates two major research questions that we study in this paper for congestion games with an adversary: Firstly, the analysis of conditions leading to the existence (or non-existence) of pure Nash equilibria. Secondly, in the absence of pure Nash equilibria, the study of alternative solution concepts. In this paper, we focus on approximate pure Nash equilibria where no unilateral deviation improves the cost of the deviating leader by more than a certain factor.

1.1 Our Results and Proof Techniques In this paper, we study multi-leader congestion games with an adversary and assume linear congestion cost functions (for a discussion of the limitations of this and other assumptions, see Section 6.2). Regarding the existence of pure Nash equilibria for such multi-leader games, we show that if the linear cost coefficients of all resources are identical and the leaders strategies are given by base sets of player-specific matroids, equilibria are guaranteed to exist. To prove this, we use a special lexicographical ordering on the resource load vectors, and, making use of the basis exchange property, show that a minimum corresponds to a pure Nash equilibrium. On the other hand, we observe that if the resource cost coefficients are non-identical, equilibria do not always exist, not even for symmetric singleton action spaces of the leaders (where each leader is allowed to choose exactly one of the available resources). This motivates the analysis of approximate pure Nash equilibria, where no

Journal of Artificial Intelligence Research, Vol. 83, Article 29. Publication date: August 2025.

Multi-Leader Congestion Games with an Adversary 29:3

unilateral deviation improves the cost of the deviating leader by more than a factor 𝛼, for some 𝛼 1. We analyze existence and efficient computation of approximate equilibria for the case that the underlying congestion game is a symmetric singleton congestion game (and the congestion costs are linear). Note that although the assumption of singleton strategy spaces is certainly restrictive, this class is still rich enough to model many applications [31], among them the described example of clients choosing servers and a subsequent Do S attack, and has attracted a lot of attention in the literature, for example, [19, 7, 12, 13, 11]. Moreover, the analysis of approximate equilibria in our model turns out to be challenging already for singleton strategies. As our main result, we show that 𝛼= 𝐾 1.1974 is the smallest possible value of 𝛼such that the existence of an 𝛼-approximate equilibrium can always be guaranteed, where 𝐾is the unique solution of the equation 𝑥3 + 𝑥2/2 + 1 = 0. For the proof, we give an efficient algorithm computing a 𝐾-approximate equilibrium. The basic approach is to start with an empty game, and add the players one after another, always placing them on a best-response resource. If the addition of a new player makes some of the already added players unhappy , meaning that there is a unilateral deviation decreasing their cost by more than a factor 𝛼, we let the unhappy players deviate one after another until all players are happy again, that is, an 𝛼-approximate pure Nash equilibrium is reached for the subset of players already added. Only then the next player is added. By choosing the possible deviations carefully, we can show that this procedure terminates after a polynomial number of steps for 𝛼= 𝐾, showing existence of 𝐾-approximate pure Nash equilibria and giving an efficient way of computing them. A similar approach has been used before to compute exact pure Nash equilibria for weighted congestion games [1, 47], but we are not aware of any results regarding approximate equilibria applying this technique. We furthermore provide an instance which does not admit an 𝛼-approximate equilibrium for any 𝛼< 𝐾. This shows that 𝛼= 𝐾is tight in the sense that it is the smallest possible value such that the existence of an 𝛼-approximate equilibrium can be guaranteed for all instances of the introduced game. However, for a specific given instance, better approximate equilibria might exist, that is, there may be an 𝛼-approximate equilibrium with 𝛼< 𝐾. We show how to compute efficiently, for a given instance, a best approximate equilibrium, that is, with smallest possible value of 𝛼such that an 𝛼-approximate equilibrium exists. Note that this in particular implies that we can decide efficiently whether a given instance admits an exact pure Nash equilibrium, and in case of existence, we can also compute such an equilibrium. Our algorithm is based on a careful analysis of the structure of optimal approximate equilibria, which allows us to enumerate a polynomially-sized set of possible resource-load configurations.

1.2 Related Work The games analyzed in this paper are an extension of classical congestion games. Different generalizations of congestion games are analyzed in the literature, including games with weighted players, player-specific cost functions [47], local effect games [40], and resource graph games [32, 26]. In resource graph games, as in our model, the cost of each resource depends on the whole vector of resource loads. Harks et al. [26] show that pure Nash equilibria in these games are guaranteed to exist for arbitrary strategy sets if and only if the dependence of the cost of a resource on the loads of other resources is linear and symmetric. In our model this dependence is non-linear, but also the strategy spaces are matroids or singletons and, hence, more restricted. For weighted congestion games, a pure Nash equilibrium may also fail to exist [25], but the existence and computation of approximate equilibria is fairly well understood [9, 8, 14, 22, 23]. The adversary model we consider can be seen as a particular model of a resource failure. Penn et al. [52, 53, 51] consider congestion games where resources fail with a certain probability and derive existence and efficient computation of pure Nash equilibria. In contrast to our work, players are allowed to choose any subset of the resources and the resource failure rate of a resource depends only on its own load. In our adversary model, the additional cost of a resource due to the adversary action depends on the load of all resources. Nickerl and

Journal of Artificial Intelligence Research, Vol. 83, Article 29. Publication date: August 2025.

29:4 Harks, Henle, Klimm, Matuschke & Schedel

Torán [48] consider fixed resource failure probabilities but more general strategy spaces and show existence of pure Nash equilibria as well as hardness of computation. Wang et al. [57] analyze under which conditions the pure Nash equilibria of the original standard congestion game are preserved in a model with fixed resource failure probabilities. Bilò et al. [6] consider a network routing game where one edge is adversarially destroyed for each player. They study the existence and quality of a particular class of mixed strategies in this setting. Congestion games with agent failures are studied in [46]. The authors show that pure Nash equilibria always exist and study the price of anarchy for the case of identical and independent failure probabilities. Li et al. [41] consider resource and agent failures simultaneously for congestion games where the symmetric strategy sets are given by 𝑘-uniform matroids. They show the existence of pure Nash equilibria and analyze the quality for the case of identical players and identical resources. They also study a model with correlated resource failures (but no agent failures) and derive existence and efficient computation of pure Nash equilibria. Babaioff et al. [3] consider a non-atomic congestion game with a malicious player controlling a certain amount of the flow with the incentive to maximize the average delay of the induced network congestion game. Malicious players in atomic congestion games are studied by Gairing [17], who assumes that each player has a fixed probability to be malicious. Congestion games in which the players are partly altruistic are considered, for example, by Hoefer and Skopalik [30]. They show that pure Nash equilibria are guaranteed to exist and can be computed efficiently for matroid congestion games and convex congestion cost functions. They also study the level of altruism that needs to be added in order to achieve certain behaviour, for example, that a social optimum coincides with a pure Nash equilibrium, for singleton congestion games. This is also studied by Apt and Schäfer [2] for linear congestion cost functions. There are several works analyzing hierarchical games where in the lower level non-atomic users settle in a Wardrop equilibrium [58]. Marcotte [45] and Garing et al. [18] study an optimization problem where a single leader invests in network capacities with the goal of minimizing the sum of the total congestion costs and the costs for installing of capacities. Beckmann et al. [5] and Yang and Huang [61] study the problem of a single leader to set road tolls. Correa et al. [15] and Harks et al. [28] consider a game where multiple leaders set prices in order to maximize their own profits achieved in a network routing game. The prices that the leaders are allowed to choose are upper-bounded by price caps (leader-specific or equal for all leaders, respectively), and the two papers consider the three-level problem of a system designer who chooses the cap(s) in order to minimize total congestion. Finally, models where multiple leaders choose prices and capacities to maximize their individual profits in a network routing game are, for example, analyzed by Johari et al. [33], Liu et al. [42], and Harks and Schedel [27]. Castiglioni et al. [12] and Marchesi et al. [44] consider a model in which the players of the congestion game are partitioned into a (single) leader and multiple followers (but the leader s congestion cost functions may be different from the followers ). Depending on the structure of strategy spaces and congestion cost functions, they analyze the computational complexity of computing pure Nash equilibria. In particular, they find that efficient algorithms are only possible for singleton strategy spaces (unless P = NP), and derive such algorithms for singleton strategy spaces where either all followers have the same strategies [12], or the followers can be divided in classes having the same strategies [44].

2 The Model For an integer 𝑘 Z 0, let [𝑘] := {1, . . . ,𝑘}. Let 𝑁= [𝑛] be a finite set of players (leaders) and 𝑅= {𝑟1, . . . ,𝑟𝑚} be a finite set of 𝑚resources. For each player 𝑖 𝑁, the set of strategies available to player 𝑖is a subset 𝑋𝑖 2𝑅. We call 𝑥= (𝑥1, . . . ,𝑥𝑛) with 𝑥𝑖 𝑋𝑖for all 𝑖 𝑁a strategy profile, and 𝑋= 𝑋1 𝑋𝑛the strategy space. We use standard game theory notation; for a strategy profile 𝑥 𝑋, we write 𝑥= (𝑥𝑖,𝑥 𝑖) meaning that 𝑥𝑖is the strategy that player 𝑖plays in 𝑥and 𝑥 𝑖is the partial strategy of all players except 𝑖. Every strategy profile

Journal of Artificial Intelligence Research, Vol. 83, Article 29. Publication date: August 2025.

Multi-Leader Congestion Games with an Adversary 29:5

𝑥= (𝑥1, . . . ,𝑥𝑛) 𝑋induces a load or congestion on the resources given by ℓ𝑟(𝑥) := |{𝑖 𝑁: 𝑟 𝑥𝑖}|,𝑟 𝑅. We assume linear congestion cost functions 𝑎𝑟ℓ𝑟(𝑥),𝑟 𝑅with nonnegative coefficients 𝑎𝑟 0. In classical congestion games, the private cost of player 𝑖under strategy profile 𝑥 𝑋is then defined as Í 𝑟 𝑥𝑖𝑎𝑟ℓ𝑟(𝑥). In the game studied in this paper, the players experience additional costs caused by the adversary that we describe now. The adversary (follower) has a budget of 𝐵> 0 that is used to attack one of the maximum-load resources uniformly at random. Define for a strategy profile 𝑥 𝑋the maximum load as 𝑀(𝑥) := max𝑟 𝑅{ℓ𝑟(𝑥)} and the resources with maximum load as 𝑀 1(𝑥) := arg max𝑟 𝑅{ℓ𝑟(𝑥)}. From the perspective of a player (leader) in the congestion game, the expected additional cost on resource 𝑟 𝑅due the attack of the adversary is

( 𝐵 |𝑀 1(𝑥) |, if 𝑟 𝑀 1(𝑥),

The multi-leader congestion game with an adversary that we study in this paper can be defined as the game 𝐺= (𝑁, 𝑅,𝑋, 𝜋) in strategic form, where

𝑎𝑟ℓ𝑟(𝑥) + 𝜅 𝑟(𝑥) for all 𝑖 𝑁. (1)

We furthermore define 𝑐𝑟(𝑥) := 𝑎𝑟ℓ𝑟(𝑥) + 𝜅 𝑟(𝑥)

as the cost of resource 𝑟 𝑅under strategy profile 𝑥with the congestion part 𝑎𝑟ℓ𝑟(𝑥), and the adversary part 𝜅 𝑟(𝑥). A strategy profile 𝑥 𝑋is called a pure Nash equilibrium (PNE) of 𝐺if

𝜋𝑖(𝑥) 𝜋𝑖(𝑦𝑖,𝑥 𝑖) for all 𝑖 𝑁and 𝑦𝑖 𝑋𝑖.

As one of our first observations (see the next section), we find that pure Nash equilibria do not always exist for the introduced congestion games with an adversary. This motivates the analysis of approximate equilibria defined as follows.

Definition 1. A strategy profile 𝑥 𝑋is an 𝛼-approximate pure Nash equilibrium (𝛼-PNE) of 𝐺for some 𝛼 1, if 𝜋𝑖(𝑥) 𝛼 𝜋𝑖(𝑦𝑖,𝑥 𝑖) for all 𝑖 𝑁and 𝑦𝑖 𝑋𝑖.

A unilateral deviation which decreases the cost of the deviating player more than a factor of 𝛼is called an 𝛼-improving deviation, or an 𝛼-improving move.

For 𝛼= 1, we obtain the standard (exact) PNE. For general 𝛼 1, the interpretation is that no player can improve her cost by a unilateral deviation gaining more than a factor 𝛼. We remark that, while one can similarly define additively approximate equilibria, no existence guarantees can be given for such equilibria for any additive constant due to the scale-invariance of the games studied in this article (see Section 6.1 for details). Furthermore, despite the fact that the existence of mixed-strategy equilibria is guaranteed, pure strategies are favoured in many cases since mixed strategies do not always have a meaningful interpretation (see, for example, the discussion on mixed strategies in Section 3.2 of [49]).

3 On the Existence of Pure Nash Equilibria In this section, we analyze existence of pure Nash equilibria for the introduced congestion games with an adversary. As the main result, we show that pure Nash equilibria exist if the players strategy spaces consist of (player-specific) base sets of matroids and all resource cost coefficients 𝑎𝑟, 𝑟 𝑅, are identical. However, we also find that if we relax at least one of these two conditions, that is, strategy spaces are not matroids or cost coefficients are different, one cannot guarantee existence of pure Nash equilibria anymore.

Journal of Artificial Intelligence Research, Vol. 83, Article 29. Publication date: August 2025.

29:6 Harks, Henle, Klimm, Matuschke & Schedel

We start with the positive result about matroid congestion games and to this end, we need to introduce some notation. An ordered pair (𝑅, I) with I 2𝑅is a matroid if the following three properties are satisfied:

(i) I; (ii) If 𝑥 𝑦and 𝑦 I, then 𝑥 I; (iii) If 𝑥,𝑦 I and |𝑥| < |𝑦|, then there exists 𝑟 𝑦\ 𝑥such that 𝑥 {𝑟} I.

The sets in I are called independent sets. Specifically, the (inclusion-wise) maximal independent sets are the bases of the matroid M = (𝑅, I). As an easy example, if I consists of the empty set together with all singletons I = {{𝑟},𝑟 𝑅}, then (𝑅, I) is a matroid and the base set is {{𝑟} : 𝑟 𝑅}. For more information on matroids, see for instance the book by Oxley [50]. If in a congestion game, the players strategies are bases of matroids, that is, for each 𝑖 𝑁there exists a matroid M𝑖= (𝑅, I𝑖) such that 𝑋𝑖equals the base set of M𝑖, we call the game a matroid congestion game. In particular, singleton congestion games are matroid congestion games. As the following theorem shows, existence of pure Nash equilibria can be guaranteed in matroid congestion games with an adversary if all cost coefficients are identical:

Theorem 2. Let 𝑋𝑖,𝑖 𝑁correspond to the base sets of player-specific matroids M𝑖= (I𝑖, 𝑅). If 𝑎𝑟= 𝑎𝑟 holds for all 𝑟,𝑟 𝑅, then exact PNE do exist.

Proof. We use the sorted lexicographical order of load vectors to construct a PNE. For two vectors 𝑎,𝑏 R𝑚, denote by 𝑎and 𝑏the sorted vectors obtained by permuting the entries of 𝑎,𝑏in non-increasing order, that is, 𝑎1 𝑎2 𝑎𝑚and similarly for 𝑏. Then, 𝑎is strictly sorted lexicographically smaller than 𝑏, written as 𝑎<𝑙𝑒𝑥𝑏, if there is an index 1 𝑗 𝑚with 𝑎𝑖= 𝑏𝑖for all 1 𝑖< 𝑗and 𝑎𝑗< 𝑏𝑗. The vector 𝑎is sorted lexicographically smaller than 𝑏(written as 𝑎 𝑙𝑒𝑥𝑏), if 𝑎<𝑙𝑒𝑥𝑏or 𝑎= 𝑏. Choose a strategy profile 𝑥whose load vector ℓ(𝑥) is sorted lexicographically minimal, that is, ℓ(𝑥) 𝑙𝑒𝑥ℓ(𝑦) for all 𝑦 𝑋. We argue that 𝑥is a PNE. To see this, consider any alternative strategy 𝑦𝑖 𝑋𝑖of some player 𝑖and let 𝑦:= (𝑦𝑖,𝑥 𝑖). By the basis exchange property (see, e.g., Lemma 1.2.2 in [50]), there is a bijection 𝜎: 𝑦𝑖 𝑥𝑖 with 𝜎(𝑟) = 𝑟for 𝑟 𝑥𝑖 𝑦𝑖and 𝑦𝑟 𝑖:= (𝑥𝑖\ {𝜎(𝑟)}) {𝑟} 𝑋𝑖for all 𝑟 𝑦𝑖. Note that ℓ(𝑥) 𝑙𝑒𝑥ℓ(𝑦𝑟 𝑖,𝑥 𝑖) by lexicographic minimality of 𝑥, which implies

ℓ𝜎(𝑟) (𝑥) ℓ𝑟(𝑦𝑟 𝑖,𝑥 𝑖) = ℓ𝑟(𝑦) (2)

for all 𝑟 𝑦𝑖. Note also that 𝑀(𝑥) 𝑀(𝑦) by lexicographic minimality of 𝑥. We distinguish two cases:

If 𝑀(𝑦) > 𝑀(𝑥), then 𝑀 1(𝑦) 𝑦𝑖because ℓ𝑟(𝑦) ℓ𝑟(𝑥) for all𝑟 𝑅\𝑦𝑖. Hence 𝜋𝑖(𝑦) = 𝐵+Í 𝑟 𝑦𝑖𝑎𝑟ℓ𝑟(𝑦) 𝐵+ Í 𝑟 𝑦𝑖𝑎𝜎(𝑟)ℓ𝜎(𝑟) (𝑥) 𝜋𝑖(𝑥), where we use (2) and the premise that 𝑎𝑟= 𝑎𝑟 for all 𝑟,𝑟 𝑅. If 𝑀(𝑦) = 𝑀(𝑥), then note that 𝑟 𝑀 1(𝑦) 𝑦𝑖for all 𝑟with 𝜎(𝑟) 𝑀 1(𝑥) 𝑥𝑖by (2). Therefore |𝑀 1(𝑦) 𝑦𝑖| |𝑀 1(𝑥) 𝑥𝑖| and 𝑀 1(𝑦) \ 𝑦𝑖 𝑀 1(𝑥) \ 𝑥𝑖, from which we conclude that |𝑀 1(𝑦) 𝑦𝑖|(|𝑀 1(𝑥) 𝑥𝑖| + |𝑀 1(𝑥) \ 𝑥𝑖|) |𝑀 1(𝑥) 𝑥𝑖|(|𝑀 1(𝑦) 𝑦𝑖| + |𝑀 1(𝑦) \ 𝑦𝑖|) and hence Õ

𝑟 𝑦𝑖 𝜅 𝑟(𝑦) = |𝑀 1(𝑦) 𝑦𝑖|

|𝑀 1(𝑦)| 𝐵 |𝑀 1(𝑥) 𝑥𝑖|

|𝑀 1(𝑥)| 𝐵= Õ

𝑟 𝑥𝑖 𝜅 𝑟(𝑥).

Using (2) and the premise that𝑎𝑟= 𝑎𝑟 for all𝑟,𝑟 𝑅, we again obtain 𝜋𝑖(𝑦) = Í 𝑟 𝑦𝑖𝜅 𝑟(𝑦)+Í 𝑟 𝑦𝑖𝑎𝑟ℓ𝑟(𝑦) Í 𝑟 𝑥𝑖𝜅 𝑟(𝑥) + Í 𝑟 𝑦𝑖𝑎𝜎(𝑟)ℓ𝜎(𝑟) (𝑥) = 𝜋𝑖(𝑥).

We conclude that 𝜋𝑖(𝑦) 𝜋𝑖(𝑥) and hence a deviation to 𝑦𝑖does not improve the cost for player 𝑖.

Journal of Artificial Intelligence Research, Vol. 83, Article 29. Publication date: August 2025.

Multi-Leader Congestion Games with an Adversary 29:7

In the remainder of this section, we will present various examples showing that matroid strategy spaces and identical cost coefficients are, in a sense, necessary for guaranteeing existence of pure Nash equilibria. All our examples live in the realm of network congestion games on parallel paths. Formally, in such a game, there is a network consisting of two nodes, a source 𝑠and a sink 𝑡, together with 𝑘 1 edge-disjoint parallel paths 𝑝1, . . . , 𝑝𝑘from 𝑠to 𝑡, where each path 𝑝𝑖consists of 𝑚𝑖 1 edges. If for each player 𝑖 𝑁, the strategy set 𝑋𝑖= {𝑝1, . . . , 𝑝𝑘}, we speak of a network congestion game on parallel paths. In the context of network congestion games, we also use the terms resources and edges interchangeably. The following lemma provides useful sufficient conditions for the non-existence of pure Nash equilibria in (specific) instances with underlying network congestion game on parallel paths.

Lemma 3. Consider a congestion game with an adversary, where the congestion game is a network congestion game on 𝑘 1 parallel paths 𝑝1, . . . , 𝑝𝑘with numbers of edges 1 𝑚1 < < 𝑚𝑘. Assume further that all edge cost coefficients are identical and strictly positive 𝑎1 = = 𝑎𝑚=: 𝑎> 0. Then: If there is no pure Nash equilibrium 𝑥such that the induced path loads ℓ𝑝(𝑥) := |{𝑖 𝑁: 𝑥𝑖= 𝑝}| satisfy ℓ𝑝1(𝑥) ℓ𝑝𝑘(𝑥), then the instance does not have any pure Nash equilibrium.

Proof. Assume, by contradiction, that there is a pure Nash equilibrium 𝑥. By assumption, there exist paths 𝑝𝑎, 𝑝𝑏 with 𝑚𝑎< 𝑚𝑏but ℓ𝑝𝑎(𝑥) < ℓ𝑝𝑏(𝑥). We show that if one player, say player 𝑖, deviates from 𝑝𝑏to 𝑝𝑎, this move improves the cost of player 𝑖, contradicting the fact that 𝑥is an equilibrium. Note first that the congestion part of player 𝑖 s cost clearly decreases: Õ

𝑟 𝑝𝑏 𝑎𝑟ℓ𝑟(𝑥) = Õ

𝑟 𝑝𝑏 𝑎ℓ𝑝𝑏(𝑥) = 𝑚𝑏 𝑎ℓ𝑝𝑏(𝑥) > 𝑚𝑎 𝑎ℓ𝑝𝑏(𝑥) 𝑚𝑎 𝑎(ℓ𝑝𝑎(𝑥) + 1) = Õ

𝑟 𝑝𝑎 𝑎𝑟ℓ𝑟(𝑝𝑎,𝑥 𝑖).

We show in the following that the adversary part does not increase, that is, Í 𝑟 𝑝𝑏𝜅 𝑟(𝑥) Í 𝑟 𝑝𝑎𝜅 𝑟(𝑝𝑎,𝑥 𝑖), completing the proof. Trivially, we have 0 Í 𝑟 𝑝𝑎𝜅 𝑟(𝑝𝑎,𝑥 𝑖) 𝐵. Consequently, the statement holds if Í 𝑟 𝑝𝑏𝜅 𝑟(𝑥) = 𝐵or Í 𝑟 𝑝𝑎𝜅 𝑟(𝑝𝑎,𝑥 𝑖) = 0. Let us thus assume that both equations are not fulfilled, that is, Í 𝑟 𝑝𝑏𝜅 𝑟(𝑥) < 𝐵and Í 𝑟 𝑝𝑎𝜅 𝑟(𝑝𝑎,𝑥 𝑖) > 0. The first inequality implies that there exists a path having maximum load in 𝑥which is different from 𝑝𝑏(and 𝑝𝑎). The second inequality shows that 𝑝𝑎is a maximum load path after one player deviated from 𝑝𝑏to 𝑝𝑎. Taking both inequalities together shows that ℓ𝑝𝑎(𝑥) = ℓ𝑝𝑏(𝑥) 1 = 𝑀(𝑥) 1 is the only possible remaining case, where 𝑀(𝑥) = max{𝑟 𝑅: ℓ𝑟(𝑥)} denotes the maximum load in 𝑥. In this case, we have that Õ

𝑟 𝑝𝑏 𝜅 𝑟(𝑥) = 𝑚𝑏 𝐵 |𝑀 1(𝑥)| > 𝑚𝑎 𝐵 |𝑀 1(𝑥)| 𝑚𝑏+ 𝑚𝑎 = Õ

𝑟 𝑝𝑎 𝜅 𝑟(𝑝𝑎,𝑥 𝑖),

where the inequality uses that |𝑀 1(𝑥)| > 𝑚𝑏> 𝑚𝑎> 0 and |𝑀 1(𝑥)| denotes the number of maximum load resources in 𝑥.

The lemma that we just proved becomes useful in the following example. It demonstrates that if the cost coefficients are identical, but players strategy spaces are not bases of matroids anymore, pure Nash equilibria may fail to exist.

Example 4. Consider the network displayed in Figure 1. We have three parallel paths 𝑝1, 𝑝2, 𝑝3 with𝑚1 = 1,𝑚2 = 4, and 𝑚3 = 9 many edges. All linear edge cost coefficients are equal to 𝑎= 1. Finally, assume that the number of players is 𝑛= 5, where the strategy set of each player 𝑖is 𝑋𝑖= {𝑝1, 𝑝2, 𝑝3}, and the adversary s budget equals 𝐵= 7. We proceed to show that the corresponding multi-leader congestion game with an adversary does not admit a pure Nash equilibrium. To this end, we prove that for each strategy profile, there exists a player who can decrease her experienced cost by a unilateral deviation.

Journal of Artificial Intelligence Research, Vol. 83, Article 29. Publication date: August 2025.

29:8 Harks, Henle, Klimm, Matuschke & Schedel

Fig. 1. Illustration for the given paths 𝑝1 (blue), 𝑝2 (green), 𝑝3 (red) in Example 4. The edges are labeled with their respective linear cost coefficients.

By Lemma 3, it suffices to show that there is no pure Nash equilibrium 𝑥such that the induced path loads satisfy ℓ𝑝1(𝑥) ℓ𝑝2(𝑥) ℓ𝑝3(𝑥). That is, we need to analyze all path load vectors (ℓ𝑝1, ℓ𝑝2, ℓ𝑝3) N3 with ℓ𝑝1 + ℓ𝑝2 + ℓ𝑝3 = 𝑛= 5 and ℓ𝑝1 ℓ𝑝2 ℓ𝑝3. Thus, it suffices to show that there is no PNE with path load vector among (5, 0, 0), (4, 1, 0), (3, 2, 0), (3, 1, 1) and (2, 2, 1). Table 1 provides an improving deviation for each of these candidate path load vectors, showing that the game has no PNE.

Table 1. Improving deviations for the candidate path load vectors for the game in Example 4.

path loads deviation resulting cost improvement (of a player using 𝑝to 𝑝 , notation 𝑝 𝑝 )

(5, 0, 0) 𝑝1 𝑝2 5𝑎+ 𝐵 = 12 > 4 = 4 𝑎 (4, 1, 0) 𝑝1 𝑝2 4𝑎+ 𝐵 = 11 > 8 = 4 2𝑎 (3, 2, 0) 𝑝1 𝑝3 3𝑎+ 𝐵 = 10 > 9 = 9 𝑎 (3, 1, 1) 𝑝3 𝑝2 9𝑎 = 9 > 8 = 4 2𝑎 (2, 2, 1) 𝑝2 𝑝1 4 (2𝑎+ 𝐵/5) = 13, 6 > 10 = 3𝑎+ 𝐵

We would like to remark that in the above example, at least three paths are necessary to allow non-existence of pure Nash equilibria: If there are only two paths available for the players, it is an easy observation that any best response dynamic terminates with a pure Nash equilibrium. Furthermore, the paths cannot all have the same length: If the number of edges is the same for all paths, and all edge cost coefficients are identical, then we can in fact assume w.l.o.g. that all paths consist of a single edge only, and this then constitutes a (symmetric, singleton) matroid congestion game with identical cost coefficients for which we have shown existence of pure Nash equilibria in Theorem 2. In the next example, we present a network congestion game with three parallel paths, each consisting of a single edge only (that is, a symmetric singleton matroid congestion game), but with non-identical cost coefficients. As in the previous example, the corresponding congestion game with an adversary does not admit a pure Nash equilibrium.

Example 5. Consider a network consisting of three parallel edges 𝑟1,𝑟2, and 𝑟3. The edge cost coefficients are given by 𝑎𝑟1 = 0, 𝑎𝑟2 = 2, and 𝑎𝑟3 = 5. For an illustration see Figure 2. Assume we have 𝑛= 5 players with strategy set

Journal of Artificial Intelligence Research, Vol. 83, Article 29. Publication date: August 2025.

Multi-Leader Congestion Games with an Adversary 29:9

𝑋𝑖= {𝑟1,𝑟2,𝑟3} for each player 𝑖, and the adversary s budget is 𝐵= 6. We proceed to show that the corresponding congestion game with an adversary has no pure Nash equilibrium.

Fig. 2. Illustration for the resources 𝑟1 (blue), 𝑟2 (green), 𝑟3 (red) in Example 5. The edges are labeled with their respective linear cost coefficients.

Very similar as in the proof of Lemma 3, one can show that if there does not exist a pure Nash equilibrium 𝑥 such that ℓ𝑟1(𝑥) ℓ𝑟2 (𝑥) ℓ𝑟3 (𝑥), then the game does not admit a pure Nash equilibrium at all. Thus, it suffices to show that there is no PNE with edge load profile (ℓ𝑟1(𝑥), ℓ𝑟2(𝑥), ℓ𝑟3(𝑥)) among (5, 0, 0), (4, 1, 0), (3, 2, 0), (3, 1, 1) and (2, 2, 1). Table 2 provides an improving deviation for each of these candidate load profiles, showing that the game does not admit a PNE.

Table 2. Improving deviations for the candidate profiles for the game in Example 5.

load profile deviation resulting cost improvement (of a player using 𝑟to 𝑟 , notation 𝑟 𝑟 )

(5, 0, 0) 𝑟1 𝑟2 5𝑎𝑟1 + 𝐵 = 6 > 2 = 𝑎𝑟2 (4, 1, 0) 𝑟1 𝑟2 4𝑎𝑟1 + 𝐵 = 6 > 4 = 2𝑎𝑟2 (3, 2, 0) 𝑟1 𝑟3 3𝑎𝑟1 + 𝐵 = 6 > 5 = 𝑎𝑟3 (3, 1, 1) 𝑟3 𝑟2 𝑎𝑟3 = 5 > 4 = 2𝑎𝑟2 (2, 2, 1) 𝑟2 𝑟1 2𝑎𝑟2 + 𝐵/2 = 7 > 6 = 3𝑎𝑟1 + 𝐵

As we have seen in this section, pure Nash equilibria exist if the players action spaces are bases of matroids and the resource cost coefficients are identical. However, if one of these two conditions is not fulfilled, existence cannot be guaranteed anymore. Motivated by this, we study approximate equilibria in the rest of this paper.

4 Computing 𝐾-approximate PNE

Motivated by the fact that PNE do not always exist, even for very simple forms of the underlying congestion game, we study in this section approximate PNE for the case of symmetric singleton congestion games, where each player is allowed to choose exactly one of the available resources. That is, 𝑋𝑖= {{𝑟} : 𝑟 𝑅} for all players 𝑖 𝑁 is assumed throughout this section. We show that 𝛼= 𝐾 1.1974 is the smallest possible 𝛼such that the existence

Journal of Artificial Intelligence Research, Vol. 83, Article 29. Publication date: August 2025.

29:10 Harks, Henle, Klimm, Matuschke & Schedel

of an 𝛼-PNE can be guaranteed for any such instance, where

is the unique solution of the equation 𝑥3 + 𝑥2/2 + 1 = 0. To this end, we provide Algorithm 1 which efficiently computes a 𝐾-approximate PNE (see Theorem 10). This result is complemented by an instance where no 𝛼approximate PNE with 𝛼< 𝐾exists (see Theorem 14). As an easy consequence of the proof of Theorem 10, we also get that exact PNE are guaranteed to exist if 𝑛 4 or 𝑚 2 (see Corollary 12).

4.1 An Algorithm for Computing 𝛼-Approximate Equilibria For computing an 𝛼-approximate PNE, we use the following basic approach. Starting with an empty game, we add the players one after another to the game, where a newly added player is always placed on a best response. If the addition of a new player makes some of the earlier added players unhappy , meaning that they now have an 𝛼-improving move, we let unhappy players deviate one after another to a best response until all players are happy again. Only then we add the next player and proceed as before. Note that this approach has been used before to compute exact PNE, for example for player-specific costs or weighted congestion games on matroids [1, 47]. However, to the best of our knowledge, it has not been utilized in the context of approximate PNE. We believe that this technique will be useful for showing existence and computing approximate equilibria beyond the class of games that we analyze here. We now formally describe our algorithm (see also Algorithm 1). We assume that the resource set 𝑅= {𝑟1, . . . ,𝑟𝑚} is ordered such that 𝑎1 𝑎𝑚(where 𝑎𝑗:= 𝑎𝑟𝑗). Since we need to consider strategy profiles for subsets of the players, let us extend the notion of a strategy profile to the set of vectors 𝑥 (𝑅 {0})𝑛, where 𝑥𝑖= 0 means that player 𝑖has not yet been added to the game. Given such a vector 𝑥 0, the cost 𝑐𝑥𝑖(𝑥) incurred to player 𝑖 with 𝑥𝑖 0 is defined as the cost which is experienced by player 𝑖in the game where only the players 𝑗with 𝑥𝑗 0 are present. Now define, for a strategy profile 𝑥 (𝑅 {0})𝑛, the following set of players 𝑊𝛼(𝑥) who are unhappy with their strategy, meaning that they have an 𝛼-improving move:

𝑊𝛼(𝑥) := {𝑖 𝑁: 𝑥𝑖 0 and 𝑐𝑥𝑖(𝑥) > 𝛼 𝑐𝑟(𝑟,𝑥 𝑖) for a resource 𝑟 𝑅}.

In each iteration of the for-loop in line 2 of Algorithm 1, a new player 𝑘is added to the game. We place 𝑘on a best response (with respect to the strategies of the players {1, . . . ,𝑘 1} already added to the game). If there is more than one best response, we choose the one with smallest index (the first among the best responses if we view the resources ordered from 𝑟1 to 𝑟𝑚), see lines 3 and 4. After having added player 𝑘, it may be the case that some players are not happy with their strategy, that is, 𝑊𝛼(𝑥) , where 𝑥denotes the current strategy profile. In the while-loop starting in line 5, we iteratively choose a player who is maximally unhappy , meaning that this player experiences maximum cost among all unhappy players, and let this player deviate to a best response, until all players in {1, . . . ,𝑘} are happy. If there is more than one resource with maximum cost among the resources used by unhappy players, we choose a player on the maximum cost resource with largest index (the last maximum cost resource w.r.t. the ordering from 𝑟1 to 𝑟𝑚), and if there is more than one best response, we choose the one with smallest index (the first best response), see lines 7, 8, and 9. After this, we return to line 2 where the next player 𝑘+ 1 is added to the game.

It is clear that if Algorithm 1 terminates, the computed strategy profile is an 𝛼-PNE. In the next subsection, we show that Algorithm 1 terminates for 𝛼= 𝐾. Note that the special choices made by the algorithm in case of non-unique best responses or non-unique most expensive resources, together with the fact that resources are ordered such that 𝑎1 𝑎2 𝑎𝑚, ensure that the loads are always decreasing along the resources, that is, ℓ𝑟1 (𝑥) ℓ𝑟2 (𝑥) ℓ𝑟𝑚(𝑥) always holds during the algorithm.

Journal of Artificial Intelligence Research, Vol. 83, Article 29. Publication date: August 2025.

Multi-Leader Congestion Games with an Adversary 29:11

Algorithm 1: Computation of an 𝛼-approximate PNE.

Input: Player set 𝑁= [𝑛], resource set 𝑅= {𝑟1, . . . ,𝑟𝑚}, resource cost coefficients 0 𝑎1 𝑎𝑚, budget 𝐵> 0, and 𝛼 1. Output: 𝛼-approximate pure Nash equilibrium 𝑥.

1 𝑥 (0, 0, . . . , 0);

2 for 𝑘= 1, 2, . . . ,𝑛do

3 𝑡 min{𝑡 [𝑚] : 𝑐𝑟𝑡(𝑟𝑡,𝑥 𝑘) 𝑐𝑟(𝑟,𝑥 𝑘) 𝑟 𝑅};

5 while 𝑊𝛼(𝑥) do

6 𝑅𝛼(𝑥) {𝑟 𝑅: 𝑥𝑖= 𝑟for some 𝑖 𝑊𝛼(𝑥)};

7 𝑡 max{𝑡 [𝑚] : 𝑟𝑡 𝑅𝛼(𝑥) and 𝑐𝑟𝑡(𝑥) 𝑐𝑟(𝑥) 𝑟 𝑅𝛼(𝑥)};

8 𝑖 some player with 𝑥𝑖= 𝑟𝑡 ;

9 𝑡+ min{𝑡 [𝑚] : 𝑐𝑟𝑡(𝑟𝑡,𝑥 𝑖) 𝑐𝑟(𝑟,𝑥 𝑖) 𝑟 𝑅};

We conclude this subsection with an illustrating example for Algorithm 1.

Example 6. Consider the game with 𝑛= 7 players, 𝑚= 5 resources with cost coefficients 𝑎1 = 1, 𝑎2 = 𝑎3 = 4, 𝑎4 = 𝑎5 = 10, and budget 𝐵= 9. Let 𝛼= 𝐾 1.1974 as specified in (3). We now describe the steps performed by Algorithm 1, see also Figure 3. Note that in the first six iterations of the for-loop, the players 1 to 6 are placed on the resources 𝑟1,𝑟2,𝑟3,𝑟1,𝑟4,𝑟5, and no player changes during the while-loops. Only after player 7 is added (to resource 𝑟1; see Figure 3 (a)), the players 5 and 6 become unhappy, because the cost for deviating to 𝑟2 (or 𝑟3) decreased from 12.5 to 8. Since the players 5 and 6 currently experience the same cost, but player 6 s resource has a larger index, player 6 gets to change due to the tie-breaking rule of the algorithm. Both 𝑟2 and 𝑟3 are best responses, where 𝑟2 has a smaller index, thus player 6 changes to 𝑟2; see Figure 3 (b). The deviation of player 6 causes the players on 𝑟1 to be unhappy since they can now improve their cost from 12 to 10 (more than a factor 𝐾) by deviating to 𝑟5. Furthermore, player 5 can improve her cost from 10 to 8 (which is also more than a factor 𝐾) by deviating to 𝑟3. By the tie-breaking rule of the algorithm, a player on 𝑟1 gets to change since 12 > 10. If one of the players on 𝑟1, say player 7, deviates to 𝑟5, the resulting strategy profile (see Figure 3 (c)) is a 𝐾-PNE since no player has a 𝐾-improving deviation anymore. (In fact, the profile is a 12.5/12 1.0417-PNE.) Note that if some player now deviates from 𝑟2 to 𝑟1 (which is a best response move), the resulting profile is not a 𝐾-PNE anymore the situation is essentially as in Figure 3 (a). This shows that, starting from a 𝐾-PNE, a sequence of best responses does not necessarily yield a 𝐾-PNE.

4.2 Termination of Algorithm 1 for 𝛼= 𝐾 In this subsection, we prove that Algorithm 1 terminates for 𝛼= 𝐾, and thus computes a 𝐾-approximate PNE. Furthermore, we show that the running time of Algorithm 1 can be bounded by min{𝑂(𝑛2𝑚),𝑂(𝑛𝑚2)}. We start by stating some observations. While being simple, they turn out to be quite helpful in the subsequent analysis.

Observation 7. During the course of Algorithm 1, the following statements always hold.

(1) It is never beneficial to deviate to a resource where the load is smaller by one than the currently experienced load.

Journal of Artificial Intelligence Research, Vol. 83, Article 29. Publication date: August 2025.

29:12 Harks, Henle, Klimm, Matuschke & Schedel

(a) Situation after player 7 is added. In the whileloop, player 6 wants to deviate to 𝑟2 since 10 > 𝐾 8 9.58.

(b) Situation after player 6 deviated to 𝑟2. Player 7 now wants to deviate to 𝑟5 since 12 > 𝐾 10 11.97.

(c) Situation after player 7 deviated to 𝑟5. The while-loop terminates since no player has a 𝐾-improving deviation anymore.

Fig. 3. Example for Algorithm 1 with 𝑛= 7 players and five resources 𝑟1, . . . ,𝑟5. Player 𝑖 [𝑛] is represented by a square containing number 𝑖.

(2) If there are several resources with the same load, it is cheapest to deviate to the first such one (w.r.t. the ordering of the edges from 𝑟1 to 𝑟𝑚). (3) In the profile resulting from the addition of player 𝑘to the game, any player which experiences the same load as player 𝑘is happy. (4) In the profile resulting from the deviation of some player 𝑖during the while-loop, any player which experiences the same load as player 𝑖is happy.

The statements (1) and (2) are direct consequences of the facts that loads are always decreasing along the resources while 𝑎1 𝑎2 𝑎𝑚. For (3) and (4), note first that if 𝑥is a strategy profile and player 𝑖unilaterally deviates to 𝑟 𝑥𝑖, the deviation cost of player 𝑖to 𝑟(w.r.t. 𝑥) is 𝑐𝑟(𝑟,𝑥 𝑖) = 𝑎𝑟(ℓ𝑟(𝑥) + 1) + 𝜅 𝑟(𝑟,𝑥 𝑖) with

𝜅 𝑟(𝑟,𝑥 𝑖) =

𝐵, if ℓ𝑟(𝑥) = 𝑀, 0, if ℓ𝑟(𝑥) 𝑀 3, 𝐵 𝑝, if ℓ𝑟(𝑥) = 𝑀 1 and ℓ𝑥𝑖(𝑥) = 𝑀,

𝐵 𝑝+1, if ℓ𝑟(𝑥) = 𝑀 1 and ℓ𝑥𝑖(𝑥) 𝑀 1,

0, if ℓ𝑟(𝑥) = 𝑀 2 and 𝑀 1(𝑥) {𝑥𝑖}, 𝐵 𝑞+2, if ℓ𝑟(𝑥) = 𝑀 2 and 𝑀 1(𝑥) = {𝑥𝑖},

where 𝑀:= 𝑀(𝑥) is the maximum load in 𝑥, 𝑝:= |𝑀 1(𝑥)| is the number of maximum load resources, and 𝑞:= |{𝑟 𝑅: ℓ𝑟(𝑥) = 𝑀 1}| is the number of resources with load 𝑀 1. From this we directly observe for two players 𝑖and 𝑗with 𝑥𝑖 𝑥𝑗but ℓ𝑥𝑖(𝑥) = ℓ𝑥𝑗(𝑥), that the deviation costs to 𝑟 {𝑥𝑖,𝑥𝑗} are the same. Now consider the profile 𝑥resulting from the addition of player 𝑘to the game (in Algorithm 1). Obviously, player 𝑘(as well as any player using 𝑥𝑘) is happy and 𝑥𝑘is the last resource with load ℓ𝑥𝑘(𝑥) (w.r.t. the ordering from 𝑟1 to 𝑟𝑚). Consequently, if there is a player 𝑗with 𝑥𝑗 𝑥𝑘but ℓ𝑥𝑗(𝑥) = ℓ𝑥𝑘(𝑥), the cost experienced on 𝑥𝑗is not larger than the cost on 𝑥𝑘.

Journal of Artificial Intelligence Research, Vol. 83, Article 29. Publication date: August 2025.

Multi-Leader Congestion Games with an Adversary 29:13

Thus player 𝑗does not want to deviate to 𝑥𝑘, but also does not want to deviate to 𝑟 𝑥𝑘since player 𝑘does not want to deviate to 𝑟. That is, player 𝑗is also happy. Statement (4) follows by the same argumentation.

We now turn to showing that Algorithm 1 terminates for 𝛼= 𝐾. We need to prove that the while-loop terminates in each iteration 𝑘 {1, . . . ,𝑛} of the for-loop. For 𝑘= 1, we only have one player, and this player is placed on the best response 𝑟1. Therefore, 𝑊𝐾(𝑥) = 𝑊𝐾(𝑟1, 0, . . . , 0) = and the while-loop terminates without changing anything. For 𝑘= 2, the second player is placed on 𝑟1 if 2𝑎1 +𝐵 𝑎2 +𝐵/2, and is placed on 𝑟2 otherwise. It is easy to see that in both cases, both players are happy and the while-loop immediately terminates. But for iteration 𝑘 3, it may be the case that some players change their strategy during the while-loop. We show inductively that the while-loop also terminates in iteration 𝑘 3. Note that since the while-loop terminated in iteration 𝑘 1, the players in {1, . . . ,𝑘 1} were happy before the next player 𝑘was added to the game. That is, with respect to the profile 𝑥directly before player 𝑘is added, no player 𝑖 {1, . . . ,𝑘 1} has a 𝐾-improving deviation, that is, an alternative resource 𝑟with 𝑐𝑥𝑖(𝑥) > 𝐾 𝑐𝑟(𝑟,𝑥 𝑖). But it may be the case that some players are unhappy after the addition of player 𝑘and want to deviate. In the next lemma, we derive necessary properties for this to happen. The derived properties primarily depend on the loads, that is, the load of the resource where the new player 𝑘is placed, as well as the loads of an unhappy player 𝑖 s strategy and of a corresponding 𝐾-improving deviation (that player 𝑖wants to deviate to). For example, the first line in Table 3 means that if player 𝑘is placed on a resource having load 𝑀 2, where 𝑀denotes the maximum load before player 𝑘was added, then player 𝑖 (who becomes unhappy) currently uses the unique maximum load resource and wants to deviate to a resource having load 𝑀 2. Similarly, the second line means that if player 𝑘is placed on a resource having load 𝑀 1, then player 𝑖wants to deviate from a resource having load at most 𝑀 1 to a resource having load 𝑀 1, and so on.

Lemma 8. Let 𝑥and 𝑥 = (𝑥 𝑘,𝑥 𝑘) denote the strategy profiles directly before and after a new player 𝑘is added. Furthermore, let 𝑀:= 𝑀(𝑥) = max{ℓ𝑟(𝑥) : 𝑟 𝑅} denote the maximum load with respect to 𝑥, that is, before player 𝑘is added. Let 𝑖 {1, . . . ,𝑘 1} be a player who becomes unhappy due to the addition of the new player 𝑘, that is, player 𝑖 has a 𝐾-improving deviation 𝑟w.r.t. the profile 𝑥 . Then, regarding the loads of the resources 𝑥 𝑘, 𝑥 𝑖= 𝑥𝑖, and 𝑟, one of the cases shown in Table 3 (each row corresponds to one possible case) needs to hold.

Table 3. Cases for the loads of the resources 𝑥 𝑘,𝑥𝑖, and 𝑟, where 𝑟is a 𝐾-improving deviation for player 𝑖who becomes unhappy due to the addition of a new player 𝑘on 𝑥 𝑘.

ℓ𝑥 𝑘(𝑥) ℓ𝑥𝑖(𝑥 ) = ℓ𝑥𝑖(𝑥) ℓ𝑟(𝑥 ) = ℓ𝑟(𝑥) further conditions

𝑀 2 𝑀 𝑀 2 𝑀 1(𝑥) = {𝑥𝑖} (= 𝑀 1(𝑥 ))

𝑀 1 𝑀 1 𝑀 1

Proof. Let 𝑖 {1, . . . ,𝑘 1} be a player who is unhappy with her strategy 𝑥 𝑖= 𝑥𝑖in 𝑥 , and 𝑟a corresponding 𝐾-improving deviation. Note that the players using 𝑥 𝑘are happy w.r.t. 𝑥 and thus 𝑥𝑖 𝑥 𝑘holds. Since 𝑥 𝑘is the only resource where the load has changed compared to profile 𝑥, this implies ℓ𝑥𝑖(𝑥) = ℓ𝑥𝑖(𝑥 ). From that we

Journal of Artificial Intelligence Research, Vol. 83, Article 29. Publication date: August 2025.

29:14 Harks, Henle, Klimm, Matuschke & Schedel

easily get that 𝑐𝑥𝑖(𝑥 ) 𝑐𝑥𝑖(𝑥), that is, the addition of player 𝑘to the game did not increase the cost experienced by player 𝑖(the congestion part of the cost remains unchanged and the adversary part can only decrease). But since player 𝑖was happy before player 𝑘was added and in particular did not want to deviate to 𝑟then, we thus get that the deviation cost (if player 𝑖deviates to 𝑟) decreased, that is, 𝑐𝑟(𝑟,𝑥 𝑖) < 𝑐𝑟(𝑟,𝑥 𝑖) holds. Clearly, the congestion part of the deviation cost did not decrease, since ℓ𝑟(𝑥 ) ℓ𝑟(𝑥). Therefore, the adversary part of the deviation cost needs to be smaller in 𝑥 than it was in 𝑥, and this is only possible if it was positive in 𝑥. We thus get (compare (4)) that ℓ𝑟(𝑥) 𝑀 2, where ℓ𝑟(𝑥) = 𝑀 2 is only possible if 𝑥𝑖is the only resource with load 𝑀 in 𝑥. Furthermore, the adversary part of the deviation cost w.r.t. 𝑥 needs to be smaller than 𝐵, which implies that 𝑟cannot be a maximum load resource w.r.t. 𝑥 . From that we can easily deduce that 𝑟 𝑥 𝑘: Otherwise, we get by the above that ℓ𝑥 𝑘(𝑥) 𝑀 2, but also ℓ𝑥 𝑘(𝑥) {𝑀 1, 𝑀} (else 𝑥 𝑘would be a maximum load resource w.r.t. 𝑥 ). Thus the only possible case is ℓ𝑥 𝑘(𝑥) = 𝑀 2, where, additionally, 𝑥𝑖is the only resource with load 𝑀in 𝑥. Then, however, the adversary part of the deviation cost to 𝑟= 𝑥 𝑘w.r.t. 𝑥 is 𝐵; contradiction. Therefore we have 𝑟 𝑥 𝑘and, consequently, ℓ𝑟(𝑥) = ℓ𝑟(𝑥 ). We now distinguish between the three possible values for ℓ𝑟(𝑥) {𝑀 2, 𝑀 1, 𝑀} and derive the conditions stated in Table 3. If ℓ𝑟(𝑥) = 𝑀, then 𝑀(𝑥 ) = 𝑀+ 1 and ℓ𝑥 𝑘(𝑥) = 𝑀(since 𝑟cannot be a maximum load resource w.r.t. 𝑥 ). If ℓ𝑟(𝑥) = 𝑀 1, we get that ℓ𝑥𝑖(𝑥) 𝑀 1 since it is never beneficial to deviate to a resource where the load is smaller by one (compare Observation 7). Furthermore, ℓ𝑥 𝑘(𝑥) {𝑀 1, 𝑀} holds, otherwise the adversary part of the deviation cost to 𝑟does not decrease. It remains to analyze the case that ℓ𝑟(𝑥) = 𝑀 2 and 𝑥𝑖is the only resource with load 𝑀in 𝑥. Since 𝑥 𝑘 𝑥𝑖we get that ℓ𝑥 𝑘(𝑥) 𝑀. Furthermore, ℓ𝑥 𝑘(𝑥) 𝑀 2, otherwise the adversary part of the deviation cost to 𝑟does not decrease. Finally, since player 𝑖is unhappy whereas players experiencing the same load as player 𝑘, that is, with load ℓ𝑥 𝑘(𝑥 ), are happy in 𝑥 (see again Observation 7), one gets that 𝑀= ℓ𝑥𝑖(𝑥 ) ℓ𝑥 𝑘(𝑥 ) = ℓ𝑥 𝑘(𝑥) + 1, and, altogether, ℓ𝑥 𝑘(𝑥) = 𝑀 2. Altogether, one of the cases stated in Table 3 needs to hold.

We have now seen that under the conditions stated in Table 3, some players might be unhappy after a new player 𝑘is added to the game, and want to deviate in the while-loop. However, a deviation of one of these players during the while-loop may cause further players to be unhappy. For the termination of the while-loop, we need to show that after finitely many deviations, all players in {1, . . . ,𝑘} are happy again. We thus need to keep track of the set of unhappy players, as well as their corresponding 𝐾-improving deviations, during the course of the while-loop. To this end, we derive in the next lemma necessary properties for a player 𝑗who gets a new 𝐾-improving deviation 𝑟due to a deviation of some other player 𝑖in the while-loop, where new means that 𝑟was not 𝐾-improving for player 𝑗before player 𝑖deviated. Note that for this to happen, either player 𝑗 s own cost needs to increase, or the deviation cost of player 𝑗to 𝑟needs to decrease. In the proof, we analyze both cases, and derive the conditions shown in Table 4.

Lemma 9. Assume that player 𝑖 {1, . . . ,𝑘} deviates in some iteration of the while-loop of Algorithm 1, and denote the strategy profiles before and after this deviation by 𝑥and 𝑥 := (𝑥 𝑖,𝑥 𝑖), respectively. Furthermore, let 𝑀:= 𝑀(𝑥) = max{ℓ𝑟(𝑥) : 𝑟 𝑅} denote the maximum load with respect to 𝑥, that is, before player 𝑖deviated. If player 𝑗 {1, . . . ,𝑘}\{𝑖} gets a new 𝐾-improving deviation 𝑟 𝑥 𝑗= 𝑥𝑗due to player 𝑖 s deviation, then 𝑥𝑗 𝑥 𝑖, and regarding the loads of the resources 𝑥𝑖,𝑥 𝑖,𝑥𝑗, and 𝑟, one of the cases shown in Table 4 (each row corresponds to one possible case) needs to hold.

Proof. Clearly, 𝑥 𝑖 𝑥 𝑗= 𝑥𝑗since player 𝑖is happy in 𝑥 while player 𝑗is not, and 𝑖is the only player who changed strategy. Assume first that 𝑐𝑥𝑗(𝑥) < 𝑐𝑥𝑗(𝑥 ), that is, player 𝑗 s own cost increased due to player 𝑖 s deviation. Since 𝑥𝑗 𝑥 𝑖implies ℓ𝑥𝑗(𝑥) ℓ𝑥𝑗(𝑥 ), the congestion part of player 𝑗 s cost did not increase, thus the adversary part needed to increase. In particular, the adversary part w.r.t. 𝑥 cannot be zero, which implies that 𝑥𝑗

Journal of Artificial Intelligence Research, Vol. 83, Article 29. Publication date: August 2025.

Multi-Leader Congestion Games with an Adversary 29:15

Table 4. Cases for the loads of the resources 𝑥𝑖,𝑥 𝑖,𝑥𝑗, and 𝑟, where 𝑟is a new 𝐾-improving deviation for player 𝑗after player 𝑖 deviated from 𝑥𝑖to 𝑥 𝑖. In the last row, ℓ𝑟(𝑥 ) 𝑀 3 is only possible if 𝑟= 𝑥𝑖.

ℓ𝑥𝑖(𝑥) ℓ𝑥 𝑖(𝑥) ℓ𝑥 𝑗(𝑥 ) = ℓ𝑥𝑗(𝑥 ) ℓ𝑟(𝑥 ) further conditions

𝑀 2 𝑀 𝑀or 𝑀 2 𝑀 1(𝑥) {𝑥𝑖}

𝑀 3 𝑀 1 𝑀 1 or 𝑀 3 𝑀 1(𝑥) = {𝑥𝑖}

𝑀 1 𝑀 1 𝑀 1

𝑀 2 𝑀 2 𝑀 𝑀 2 or 𝑀 1(𝑥) = {𝑥𝑗} 𝑀 3 (𝑟= 𝑥𝑖)

has maximum load in 𝑥 , and the adversary part w.r.t. 𝑥cannot be 𝐵. We distinguish between the different values that the maximum load 𝑀(𝑥 ) can take. Since 𝑀(𝑥 ) = ℓ𝑥𝑗(𝑥 ) ℓ𝑥𝑗(𝑥) 𝑀, we have that 𝑀(𝑥 ) {𝑀 1, 𝑀}. If 𝑀(𝑥 ) = 𝑀 1, then player 𝑖moved from the only resource with load 𝑀to a resource with load at most 𝑀 2. Even more, we can exclude the case that ℓ𝑥 𝑖(𝑥) = 𝑀 2: If player 𝑖moves to a resource with load 𝑀 2, then all players having load 𝑀 1 are happy in 𝑥 (since they have the same load as player 𝑖, see Observation 7), but we know that player 𝑗is unhappy and has load 𝑀(𝑥 ) = 𝑀 1 in 𝑥 ; contradiction.1

Furthermore, 𝑥𝑗 𝑥𝑖and thus ℓ𝑥𝑗(𝑥) = ℓ𝑥𝑗(𝑥 ) = 𝑀 1 since the adversary part of player 𝑗 s cost in 𝑥cannot be 𝐵. Finally, ℓ𝑟(𝑥 ) 𝑀 1 = 𝑀(𝑥 ) and ℓ𝑟(𝑥 ) 𝑀 2 since it is never beneficial to move to a resource where the load is smaller by one and ℓ𝑥𝑗(𝑥 ) = 𝑀 1. Consequently, either ℓ𝑟(𝑥 ) = 𝑀 1 or ℓ𝑟(𝑥 ) 𝑀 3. We have thus derived the conditions stated in the fourth row of Table 4. If 𝑀(𝑥 ) = 𝑀, we get that 𝑀 ℓ𝑥𝑗(𝑥) ℓ𝑥𝑗(𝑥 ) = 𝑀, that is, ℓ𝑥𝑗(𝑥) = ℓ𝑥𝑗(𝑥 ) = 𝑀(and, consequently, 𝑥𝑗 𝑥𝑖). Since the adversary part of player 𝑗 s cost needs to increase, we have that the number of resources with load 𝑀 needs to decrease. But this means that player 𝑖moved from a resource with load 𝑀to a resource with load at most 𝑀 2. In particular, there are at least two resources with load 𝑀in 𝑥(namely 𝑥𝑖and 𝑥𝑗). Noting that ℓ𝑟(𝑥 ) 𝑀(𝑥 ) = 𝑀, and that player 𝑗does not want to deviate to a resource where the load is smaller by one, that is, where the load is 𝑀 1, we obtain the conditions in the third row of Table 4. Now consider the case that player 𝑗 s own cost did not increase due to player 𝑖 s deviation. Then, the deviation cost of player 𝑗to 𝑟is decreased. Consider first the case that 𝑟 𝑥𝑖. In that case ℓ𝑟(𝑥) ℓ𝑟(𝑥 ), and consequently, the congestion part of the deviation cost did not decrease. Therefore, the adversary part is decreased. In particular, the adversary part was positive w.r.t. 𝑥, and it is smaller than 𝐵w.r.t. 𝑥 . This shows that ℓ𝑟(𝑥) 𝑀 2 and ℓ𝑟(𝑥 ) < 𝑀(𝑥 ). We distinguish between the different values for 𝑀(𝑥 ) {𝑀 1, 𝑀, 𝑀+ 1}.

1When we speak of a player having a certain load, we mean that the player s current strategy has that load.

Journal of Artificial Intelligence Research, Vol. 83, Article 29. Publication date: August 2025.

29:16 Harks, Henle, Klimm, Matuschke & Schedel

If 𝑀(𝑥 ) = 𝑀+ 1, we have that ℓ𝑥 𝑖(𝑥) = 𝑀and 𝑀 2 ℓ𝑟(𝑥) ℓ𝑟(𝑥 ) 𝑀. Furthermore, ℓ𝑟(𝑥 ) = 𝑀 2 is only possible if 𝑟 𝑥 𝑖and 𝑥𝑗was the only resource with load 𝑀in 𝑥(otherwise the adversary part of deviating to 𝑟is zero in 𝑥). But this shows 𝑥𝑗= 𝑥 𝑖; contradiction. Thus ℓ𝑟(𝑥 ) {𝑀 1, 𝑀}. We are thus in one of the cases corresponding to rows 1, 2, 5 and 6 of Table 4 (we again use that it is never beneficial to deviate to a resource where the load is smaller by one). If 𝑀(𝑥 ) = 𝑀, we get ℓ𝑥 𝑖(𝑥) 𝑀 1 and 𝑀 2 ℓ𝑟(𝑥) ℓ𝑟(𝑥 ) 𝑀 1. We distinguish between the two different values that ℓ𝑟(𝑥) {𝑀 2, 𝑀 1} can take. If ℓ𝑟(𝑥) = 𝑀 2, then 𝑥𝑗is the only resource with load 𝑀 in 𝑥. Since the maximum load did not decrease, we get from this that 𝑥𝑖 𝑥𝑗and consequently, ℓ𝑥𝑖(𝑥) 𝑀 1 and ℓ𝑥𝑗(𝑥 ) = ℓ𝑥𝑗(𝑥) = 𝑀. Since it is not beneficial to deviate to a resource with load smaller by one, we get ℓ𝑟(𝑥 ) = 𝑀 2. This shows ℓ𝑥 𝑖(𝑥) {𝑀 1, 𝑀 2} (the number of resources with load 𝑀, or the number of resources with load 𝑀 1, needs to be larger than before). However, the case ℓ𝑥 𝑖(𝑥) = 𝑀 1 can be excluded (otherwise, players with load 𝑀in 𝑥 would be happy, but player 𝑗is not happy). Consequently, ℓ𝑥 𝑖(𝑥) = 𝑀 2 and ℓ𝑥𝑖(𝑥) 𝑀 2. We have thus derived a situation which is captured by the last row in Table 4. Now consider the case that ℓ𝑟(𝑥) = 𝑀 1, and, consequently, ℓ𝑟(𝑥 ) = 𝑀 1 while ℓ𝑥𝑗(𝑥 ) 𝑀 1. Recall that ℓ𝑥 𝑖(𝑥) 𝑀 1 and if ℓ𝑥 𝑖(𝑥) = 𝑀 1, we know that ℓ𝑥𝑖(𝑥) 𝑀 1 and we are thus in the case described by the seventh row of Table 4. On the other hand, ℓ𝑥 𝑖(𝑥) 𝑀 2 is not possible: In that case, the number of maximum load resources can only be smaller in 𝑥 than in 𝑥. However this contradicts the fact that the deviation cost of player 𝑗to 𝑟 decreased: We know that ℓ𝑥𝑗(𝑥 ) 𝑀 1. Now if ℓ𝑥𝑗(𝑥) 𝑀 1, the deviation cost to 𝑟can only be larger. Else, we have that ℓ𝑥𝑗(𝑥) = 𝑀thus 𝑥𝑖= 𝑥𝑗. But then, the deviation cost to 𝑟is unchanged. If 𝑀(𝑥 ) = 𝑀 1, player 𝑖moved from the only resource with load 𝑀in 𝑥to a resource with load at most 𝑀 2. Furthermore, 𝑀 2 ℓ𝑟(𝑥) ℓ𝑟(𝑥 ) < 𝑀(𝑥 ) implies ℓ𝑟(𝑥 ) = ℓ𝑟(𝑥) = 𝑀 2. But since the adversary part of the deviation cost to 𝑟w.r.t. 𝑥needs to be positive, this is only possible if 𝑥𝑗is the only resource with load 𝑀in 𝑥, that is, 𝑥𝑗= 𝑥𝑖, and consequently, ℓ𝑥𝑗(𝑥 ) = 𝑀 1. However, it is never beneficial to deviate to a resource with load smaller by one; contradiction. It remains to analyze the case that 𝑟= 𝑥𝑖. In particular, 𝑥𝑖 𝑥𝑗and ℓ𝑥𝑗(𝑥) = ℓ𝑥𝑗(𝑥 ). Since we assumed that player 𝑗 s own cost did not increase, we have 𝑐𝑥𝑗(𝑥) 𝑐𝑥𝑗(𝑥 ). If, additionally, 𝑐𝑥𝑖(𝑥𝑖,𝑥 𝑗) 𝑐𝑥𝑖(𝑥) and 𝑐𝑥 𝑖(𝑥 𝑖,𝑥 𝑖) 𝑐𝑥 𝑖(𝑥 𝑖,𝑥 𝑗) hold, we can derive a contradiction as follows. Using that player 𝑖deviated from 𝑥𝑖to 𝑥 𝑖and player 𝑗wants to deviate from 𝑥𝑗to 𝑥𝑖, we get

𝑐𝑥𝑗(𝑥) 𝑐𝑥𝑗(𝑥 ) > 𝐾𝑐𝑥𝑖(𝑥𝑖,𝑥 𝑗) 𝐾𝑐𝑥𝑖(𝑥)> 𝐾2𝑐𝑥 𝑖(𝑥 𝑖,𝑥 𝑖) > 𝐾𝑐𝑥 𝑖(𝑥 𝑖,𝑥 𝑖) 𝐾𝑐𝑥 𝑖(𝑥 𝑖,𝑥 𝑗).

This means that 𝑥 𝑖is a 𝐾-improving deviation for player 𝑗w.r.t. 𝑥, too, and furthermore, 𝑐𝑥𝑗(𝑥) > 𝑐𝑥𝑖(𝑥). But this contradicts the fact that player 𝑖is an unhappy player with largest cost in 𝑥(by the rules of Algorithm 1). Thus it is not possible that both 𝑐𝑥𝑖(𝑥𝑖,𝑥 𝑗) 𝑐𝑥𝑖(𝑥) and 𝑐𝑥 𝑖(𝑥 𝑖,𝑥 𝑖) 𝑐𝑥 𝑖(𝑥 𝑖,𝑥 𝑗) hold. Consider first the case that 𝑐𝑥𝑖(𝑥𝑖,𝑥 𝑗) < 𝑐𝑥𝑖(𝑥). Clearly, the congestion parts of these two costs are the same since the load on 𝑥𝑖is the same, thus the adversary part of 𝑐𝑥𝑖(𝑥𝑖,𝑥 𝑗) needs to be smaller. This implies that the adversary part of 𝑐𝑥𝑖(𝑥) is positive. In particular, ℓ𝑥𝑖(𝑥) = 𝑀, which implies ℓ𝑥 𝑖(𝑥) 𝑀 1 and ℓ𝑟=𝑥𝑖(𝑥 ) = 𝑀 1. From the last, we also get ℓ𝑥𝑗(𝑥 ) 𝑀 1. Furthermore, since the adversary part of 𝑐𝑥𝑖(𝑥𝑖,𝑥 𝑗) needs to be smaller, either the maximum load in (𝑥𝑖,𝑥 𝑗) is larger than 𝑀(that is, 𝑀+ 1, and ℓ𝑥 𝑖(𝑥) = 𝑀), or the number of resources with load 𝑀increased (but this is only possible if ℓ𝑥 𝑖(𝑥) = 𝑀 1; contradiction). We have thus derived the conditions stated in the second row of Table 4. Now assume that 𝑐𝑥 𝑖(𝑥 𝑖,𝑥 𝑖) < 𝑐𝑥 𝑖(𝑥 𝑖,𝑥 𝑗), that is, the adversary part of the deviation cost to 𝑥 𝑖is smaller for player 𝑖than for player 𝑗. This means ℓ𝑥 𝑖(𝑥) {𝑀 1, 𝑀 2} (compare (4)). If ℓ𝑥 𝑖(𝑥) = 𝑀 1, we get that ℓ𝑥𝑗(𝑥) = 𝑀and ℓ𝑥𝑖(𝑥) 𝑀 1. But then, all players with load 𝑀are happy in 𝑥

(since ℓ𝑥 𝑖(𝑥 ) = 𝑀), contradicting the fact that player 𝑗is unhappy. If ℓ𝑥 𝑖(𝑥) = 𝑀 2, we get that 𝑥𝑗is the only resource with load 𝑀in 𝑥and ℓ𝑥𝑖(𝑥) 𝑀 1. Consequently, ℓ𝑥𝑖(𝑥) 𝑀 2 and ℓ𝑟=𝑥𝑖(𝑥 ) 𝑀 3. We thus have a situation which is captured by the last row of Table 4.

Journal of Artificial Intelligence Research, Vol. 83, Article 29. Publication date: August 2025.

Multi-Leader Congestion Games with an Adversary 29:17

We are now ready to prove the main result of this section.

Theorem 10. For 𝛼= 𝐾, where

is the unique solution of the equation 𝑥3 + 𝑥2/2 + 1 = 0, Algorithm 1 computes a 𝐾-PNE.

Proof. It suffices to show that in iteration 𝑘 3 of the for-loop, the while-loop terminates. Let 𝑥and 𝑥 denote the profiles directly before and after the new player 𝑘is added. If all players are happy with their strategy in 𝑥 , the statement follows; thus assume that at least one player becomes unhappy due to the addition of player 𝑘. Let 𝑀:= 𝑀(𝑥) = max{ℓ𝑟(𝑥) : 𝑟 𝑅} be the maximum load in 𝑥, that is, before player 𝑘is added, and recall that 𝑥 𝑘denotes the resource to which player 𝑘is added. Consequently, ℓ𝑥 𝑘(𝑥) denotes the load of 𝑥 𝑘before player 𝑘 was added. By Lemma 8, we have ℓ𝑥 𝑘(𝑥) {𝑀 2, 𝑀 1, 𝑀}, and we also know the following about unhappy players and their 𝐾-improving deviations: If ℓ𝑥 𝑘(𝑥) = 𝑀 2, unhappy players use the only resource with load 𝑀 and want to move to resources with load 𝑀 2. If ℓ𝑥 𝑘(𝑥) = 𝑀 1, unhappy players want to move to resources with load 𝑀 1 (and currently experience load 𝑀 1 since it is never beneficial to move to a resource with load smaller by one). Finally, if ℓ𝑥 𝑘(𝑥) = 𝑀, unhappy players use resources with load 𝑀and want to deviate to resources with load 𝑀 1 or load 𝑀(if they want to move to load 𝑀 1, their current load is 𝑀 1). We now analyze each of these three cases, and make repeated use of Lemma 9 and Observation 7. Figure 4 illustrates the complete case distinction that we carry out in the proof.

players on 𝑟1 never deviate

player 𝑘deviates from 𝑟1 to 𝑟

ℓ𝑟 (𝑥𝑡+1) = 𝑀 1 𝑟 = 𝑟𝑡

next dev.: 𝑀 1 𝑀 1

next dev.: 𝑟𝑡 𝑟1

next dev.: 𝑟𝑡 𝑟𝑡 1

Fig. 4. Illustration for the case distinction in the proof of Theorem 10.

Case ℓ𝑥 𝑘(𝑥) = 𝑀 2. We know that unhappy players use the only resource with load 𝑀and want to deviate to resources with load 𝑀 2. Assume that one of these players, say player 𝑖, deviates in the while-loop from 𝑥 𝑖= 𝑥𝑖to 𝑟, and denote the profile resulting from player 𝑖 s deviation by 𝑥 := (𝑟,𝑥 𝑖). Figure 5 illustrates the situation. We now show that all players are happy in 𝑥 and thus the while-loop terminates after one iteration.

Journal of Artificial Intelligence Research, Vol. 83, Article 29. Publication date: August 2025.

29:18 Harks, Henle, Klimm, Matuschke & Schedel

Note first that all players having the same load in 𝑥 as player 𝑖, that is, with load 𝑀 1, are happy in 𝑥 (cf. Observation 7). In particular, all players who were unhappy before player 𝑖deviated are now happy, since they used the only resource with load 𝑀and the load on that resource decreased to 𝑀 1. Therefore, if there is an unhappy player 𝑗with 𝐾-improving deviation 𝑟 in 𝑥 , then player 𝑗was happy before player 𝑖deviated and 𝑟 is a new 𝐾-improving deviation for player 𝑗in 𝑥 . However, applying Lemma 9 for the deviation of player 𝑖(thus 𝑥,𝑥 in the statement of the lemma are now 𝑥 ,𝑥 ) shows that there cannot be a new 𝐾-improving deviation: Note that ℓ𝑥 𝑖(𝑥 ) = 𝑀, ℓ𝑥 𝑖(𝑥 ) = 𝑀 2, and resource 𝑥 𝑖is the only resource with load 𝑀in 𝑥 , but this case does not occur in Table 4 and thus there are no new 𝐾-improving deviations. We conclude that all players are happy in 𝑥 and the while-loop terminates after one iteration.

Fig. 5. Situation in Case ℓ𝑥 𝑘(𝑥) = 𝑀 2: Player 𝑘is placed on the first resource with load 𝑀 2, and player 𝑖deviates from the only resource with load 𝑀to resource 𝑟with load 𝑀 2.

Case ℓ𝑥 𝑘(𝑥) = 𝑀 1. We know that unhappy players want to deviate to resources with load 𝑀 1 (and currently experience load 𝑀 1). Assume as above that one of these players, say player 𝑖, deviates in the while-loop from 𝑥 𝑖= 𝑥𝑖to 𝑟, and denote the profile resulting from player 𝑖 s deviation by 𝑥 := (𝑟,𝑥 𝑖). Figure 6 illustrates the situation. If all players are happy in 𝑥 , the while-loop terminates after one iteration, thus we may assume that there is an unhappy player 𝑗with 𝐾-improving deviation 𝑟 . We show that ℓ𝑟 (𝑥 ) = 𝑀 1, that is, player 𝑗 wants to move to a resource with load 𝑀 1 (which implies that the current load of player 𝑗is 𝑀 1 since it is never beneficial to deviate to a resource with load smaller by one). If 𝑟 is a new 𝐾-improving deviation for player 𝑗, we get from Lemma 9 applied for the deviation of player 𝑖 (thus 𝑥,𝑥 ,𝑟in the statement of the lemma are now 𝑥 ,𝑥 ,𝑟 ) that ℓ𝑟 (𝑥 ) = 𝑀 1 (seventh row of Table 4). Now assume that 𝑟 was already 𝐾-improving for player 𝑗before player 𝑖deviated. Consequently, the load on 𝑟 was 𝑀 1 before player 𝑖deviated. It remains to argue that the load on 𝑟 did not change by player 𝑖 s deviation. Clearly, the only resources with different load are 𝑥 𝑖and 𝑥 𝑖= 𝑟. Furthermore, 𝑟 = 𝑥 𝑖is not possible (since player 𝑖was chosen as the deviating player in the while-loop, player 𝑖experiences as least as high cost in 𝑥

than player 𝑗, 𝑐𝑥 𝑖(𝑥 ) 𝑐𝑥 𝑗(𝑥 ), and consequently, 𝑥 𝑖is not 𝐾-improving for player 𝑗in 𝑥 ). Finally, since 𝑟1 (the best option with load 𝑀) is not 𝐾-improving for player 𝑗(that would be a new 𝐾-improving deviation but all those have load 𝑀 1, as we already showed), deviating to any resource with load 𝑀is not 𝐾-improving. Thus 𝑟 = 𝑥 𝑖is also not possible, showing altogether that players who are unhappy in 𝑥 want to change to load 𝑀 1 (and use resources with load 𝑀 1). However this is the same situation as before player 𝑖deviated, thus by repeating the same argumentation we get that all future deviations move to resources with load 𝑀 1. But since each deviation decreases the number of resources with load 𝑀 1 at least by one and there are at most 𝑚 2 resources with load 𝑀 1 in 𝑥 , we conclude that the while-loop terminates after 𝑂(𝑚) iterations.

Journal of Artificial Intelligence Research, Vol. 83, Article 29. Publication date: August 2025.

Multi-Leader Congestion Games with an Adversary 29:19

𝑥 𝑘 𝑟= 𝑥 𝑖 𝑥𝑖= 𝑥 𝑖

Fig. 6. Situation in Case ℓ𝑥 𝑘(𝑥) = 𝑀 1: Player 𝑘is placed on the first resource with load 𝑀 1, and player 𝑖deviates from a resource with load 𝑀 1 to resource 𝑟with load 𝑀 1. (There might be more than one resource with load 𝑀before player 𝑘was added.)

Case ℓ𝑥 𝑘(𝑥) = 𝑀. Note that in this case, the maximum load increased from 𝑀to 𝑀+1, and in particular, 𝑥 𝑘= 𝑟1 is the only resource with load 𝑀+ 1 in 𝑥 . We know that unhappy players use resources with load 𝑀and want to deviate to resources with load 𝑀 1 or load 𝑀(if they want to move to load 𝑀 1, their current load is 𝑀 1). Assume as above that one of these players, say player 𝑖, deviates in the while-loop from 𝑥 𝑖= 𝑥𝑖to 𝑟, and denote the profile resulting from player 𝑖 s deviation by 𝑥 := (𝑟,𝑥 𝑖). We distinguish between the two different values that the load ℓ𝑟(𝑥 ) {𝑀 1, 𝑀} can take (see Figure 7 for illustrations of both cases).

𝑟= 𝑥 𝑖 𝑥𝑖= 𝑥 𝑖

(a) Player 𝑖deviates from a resource with load 𝑀to resource 𝑟with load 𝑀.

𝑟= 𝑥 𝑖 𝑥𝑖= 𝑥 𝑖

(b) Player 𝑖deviates from a resource with load 𝑀 1 to resource 𝑟with load 𝑀 1.

Fig. 7. Situation in Case ℓ𝑥 𝑘(𝑥) = 𝑀: Player 𝑘is placed on 𝑟1.

First consider the case that ℓ𝑟(𝑥 ) = 𝑀(Figure 7 (a)), and assume there is a player 𝑗who is unhappy in 𝑥

with 𝐾-improving deviation 𝑟 . We want to show that ℓ𝑟 (𝑥 ) {𝑀 1, 𝑀}. If 𝑟 is a new 𝐾-improving deviation for player 𝑗, we get by Lemma 9 applied for player 𝑖 s deviation (thus 𝑥,𝑥 , 𝑀,𝑟in the statement of the lemma are now 𝑥 ,𝑥 , 𝑀+ 1,𝑟 ), that ℓ𝑟 (𝑥 ) = 𝑀(see the seventh row in Table 4). Now consider the case that 𝑟 was already 𝐾-improving for player 𝑗in 𝑥 . Then ℓ𝑟 (𝑥 ) {𝑀 1, 𝑀}. If the load on 𝑟 is unchanged, we get the desired property. Clearly, the only resources with changed load are 𝑥 𝑖and 𝑟= 𝑥 𝑖. Moreover, 𝑟 𝑥 𝑖(since

Journal of Artificial Intelligence Research, Vol. 83, Article 29. Publication date: August 2025.

29:20 Harks, Henle, Klimm, Matuschke & Schedel

𝑐𝑥 𝑖(𝑥 ) 𝑐𝑥 𝑗(𝑥 ) and, consequently, 𝑥 𝑖is not 𝐾-improving for player 𝑗in 𝑥 ). Finally, since 𝑟1 (the best option with load 𝑀+ 1) is not 𝐾-improving for player 𝑗(that would be a new 𝐾-improving deviation but all those have load 𝑀, as we already showed), deviating to any resource with load 𝑀+ 1 is not 𝐾-improving. Thus 𝑟 𝑥 𝑖. Altogether, if ℓ𝑟(𝑥 ) = 𝑀, players who are unhappy in 𝑥 use resources with load 𝑀(since all players with the same load as player 𝑖, that is, with load 𝑀+ 1, are happy) and want to deviate to resources with load 𝑀 1 or load 𝑀(if they want to move to load 𝑀 1, their current load is 𝑀 1). For the case that ℓ𝑟(𝑥 ) = 𝑀 1 (see Figure 7 (b)), assume again there is a player 𝑗who is unhappy in 𝑥 with 𝐾-improving deviation 𝑟 . Note that ℓ𝑥 𝑗(𝑥 ) 𝑀since all players with the same load as player 𝑖, that is, with load 𝑀, are happy in 𝑥 . If 𝑟 is a new 𝐾-improving deviation for player 𝑗, we get from Lemma 9 that player 𝑗 uses 𝑟1 and either wants to deviate to a resource with load 𝑀 1, or to 𝑥 𝑖(see the last row in Table 4). If 𝑟 was already 𝐾-improving for player 𝑗in 𝑥 , we know as before that ℓ𝑟 (𝑥 ) {𝑀 1, 𝑀}. Furthermore, the load on 𝑟

cannot be smaller in 𝑥 (since 𝑟 𝑥 𝑖by the same argumentation as above), and it can only be larger if 𝑟 = 𝑥 𝑖, but in that case the load is now 𝑀. Thus we still have ℓ𝑟 (𝑥 ) {𝑀 1, 𝑀}. Therefore, if ℓ𝑟(𝑥 ) = 𝑀 1, players who are unhappy in 𝑥 either use 𝑟1 and want to deviate to a resource with load 𝑀 1 or 𝑥 𝑖, or they use resources with load 𝑀 1 and want to deviate to resources with load 𝑀 1 or 𝑀. Using the above, we can argue that if the players on 𝑟1 never deviate during the while-loop, then the only changes are from resources having load 𝑀to resources with load 𝑀, or from 𝑀 1 to 𝑀 1. But this terminates after 𝑂(𝑚) many deviations (each deviation, except one from load 𝑀 2 to 𝑀 1, strictly decreases the number of resources with load in {𝑀 1, 𝑀}; and there can also be at most 𝑂(𝑚) many deviations from load 𝑀 2 to 𝑀 1). Thus we can now assume that in some iteration of the while-loop, a player deviates from 𝑟1 to a resource 𝑟 . Consider the first such change, that is, all changes before have been from load 𝑀to load 𝑀or from 𝑀 1 to 𝑀 1. More exactly, note that the changes before cannot include a change to load 𝑀, because after such a change, all players having load 𝑀+ 1 are happy and never become unhappy afterwards (see Lemma 9 and note that 𝑟1 is not the only resource with load 𝑀+ 1 anymore). Therefore, all changes before were moves from load 𝑀 1 to 𝑀 1 (and there was at least one such change). Let 𝑖1, . . . ,𝑖𝑡be the corresponding sequence of deviating players, where 𝑖1 = 𝑖is the first, and 𝑖𝑡the last player deviating before player 𝑘deviates (we can assume w.l.o.g. that player 𝑘is the player deviating from 𝑟1 to 𝑟 ). Let 𝑟𝑠and 𝑟𝑠denote player 𝑖𝑠 s resources before and after changing, for 𝑠= 1, . . . ,𝑡, and let 𝑥𝑠+1 be the strategy profile resulting from 𝑖𝑠 s change. Finally, let 𝑥𝑡+2 := (𝑟 ,𝑥𝑡+1 𝑘) be the strategy profile resulting from 𝑥𝑡+1 due to player 𝑘 s deviation from 𝑟1 to 𝑟 . Figure 8 shows an illustration for the situation before player 𝑘deviates.

𝑟1 𝑟2 𝑟𝑡 𝑟𝑡

Fig. 8. Situation before player 𝑘deviates (with 𝑡= 3).

Journal of Artificial Intelligence Research, Vol. 83, Article 29. Publication date: August 2025.

Multi-Leader Congestion Games with an Adversary 29:21

Note that 𝑟1 is the only resource with load 𝑀+ 1 in 𝑥𝑡+1. Furthermore, all players having load 𝑀are happy in 𝑥𝑡+1 (since the last deviation was to load 𝑀 1), thus the only unhappy players in 𝑥𝑡+1 (except from the players using 𝑟1) might want to change from load 𝑀 1 to load 𝑀 1 or to load 𝑀. Now consider the situation after player 𝑘deviated to 𝑟 . Recall that player 𝑘either deviates to a resource with load 𝑀 1, or to 𝑟𝑡(smallest resulting cost among all resources where the players 𝑖1, . . . ,𝑖𝑡deviated from, and smallest index in case of non-uniqueness).

Subcase ℓ𝑟 (𝑥𝑡+1) = 𝑀 1. If player 𝑘deviates to a resource with load 𝑀 1, then all players having load 𝑀are happy in 𝑥𝑡+2. Thus consider a player 𝑗with load 𝑀 1. Comparing the current situation, that is, profile 𝑥𝑡+2, with the situation before player 𝑘was added to the game, that is, profile 𝑥, we observe that player 𝑗 s private cost can only be smaller in 𝑥𝑡+2 than in 𝑥. Furthermore, the deviation cost to a resource 𝑟can only be smaller in 𝑥𝑡+2 than in 𝑥if the load of 𝑟is 𝑀 1, or if 𝑟 {𝑟1,𝑟2, . . . ,𝑟𝑡}. Since player 𝑗was happy in 𝑥, we get that if 𝑟is a 𝐾-improving deviation for player 𝑗in 𝑥𝑡+2, then either the load of 𝑟is 𝑀 1, or 𝑟 {𝑟1,𝑟2, . . . ,𝑟𝑡}. However, the latter case can also be excluded, since player 𝑗did not want to deviate to such a resource before player 𝑘deviated (𝐾-improving deviations had load 𝑀 1 or 𝑀), and player 𝑘 s deviation did neither influence player 𝑗 s private cost, nor the deviation cost to one of these resources. Consequently, unhappy players in 𝑥𝑡+2 have load 𝑀 1 and want to deviate to a resource with load 𝑀 1. Using very similar arguments as before, one observes that in fact all future changes are from load 𝑀 1 to load 𝑀 1, showing that the while-loop terminates after 𝑂(𝑚) iterations.

Subcase 𝑟 = 𝑟𝑡. It remains to analyze the case that player 𝑘deviates from 𝑟1 to 𝑟𝑡(the resource where player 𝑖𝑡 deviated from). Assume player 𝑗is unhappy after that change with 𝐾-improving deviation 𝑟. Clearly, the load of player 𝑗 s resource is 𝑀, and if it is equal to 𝑀, the load of 𝑟is either 𝑀or 𝑀 2. If, on the other hand, player 𝑗uses a resource with load 𝑀 1, then we can show by a very similar argumentation as in the last paragraph that the load of 𝑟is 𝑀 1. Therefore, there are three possible cases regarding the next deviation in the while-loop: Either a player deviates from 𝑟𝑡(the resource where player 𝑖𝑡deviated to, see Figure 8) to 𝑟1, or from 𝑟𝑡to a resource with load 𝑀 2, or from a resource with load 𝑀 1 to load 𝑀 1 (note that 𝑟𝑡has largest cost and largest index, while 𝑟1 has smallest cost and smallest index, among the resources with load 𝑀). In the last case, all players with load 𝑀are happy after the change, and by very similar arguments as before, the only further moves can be from load 𝑀 1 to load 𝑀 1. This terminates after 𝑂(𝑚) iterations. The case that a player moves from 𝑟𝑡to 𝑟1 (see Figure 9 for an illustration) can be excluded since it leads to the following contradiction. Let ℓ𝑟𝑡denote the load of resource 𝑟𝑡directly before player 𝑖𝑡deviated from it. Furthermore note that there are at least two resources with load 𝑀in 𝑥𝑡+2 (𝑟1 and 𝑟1). Then, the following three inequalities hold.

𝑎𝑟𝑡 ℓ𝑟𝑡> 𝐾 𝑎 𝑟𝑡 𝑀 (5)

𝑎1 (𝑀+ 1) + 𝐵> 𝐾 𝑎𝑟𝑡 ℓ𝑟𝑡 (6)

𝑎 𝑟𝑡 𝑀+ 𝐵/2 > 𝐾 (𝑎1 (𝑀+ 1) + 𝐵). (7)

Using that (7) is equivalent to 𝐾𝑎 𝑟𝑡 𝑀> 𝐾2𝑎1 (𝑀+ 1) + (𝐾2 𝐾/2)𝐵and combining this with (5) and (6) yields

𝐾2𝑎1 (𝑀+ 1) + (𝐾2 𝐾/2)𝐵< 𝑎𝑟𝑡 ℓ𝑟𝑡< 𝑎1 (𝑀+1)+𝐵

From this we conclude the contradiction

0 (𝐾3 1)𝑎1 (𝑀+ 1) < ( 𝐾3 + 𝐾2/2 + 1)𝐵= 0,

where we additionally used that 𝐾3 > 1 and 𝐾3 + 𝐾2/2 + 1 = 0 by definition of 𝐾. Therefore, the only remaining case is that a player on 𝑟𝑡changes to a resource 𝑟 with load 𝑀 2. We will first show that 𝑟 = 𝑟𝑡 1 holds. Note that the cost for deviating to 𝑟 is strictly smaller than the cost for deviating to 𝑟1 (otherwise, one would change to 𝑟1). Therefore, 𝑟 needs to have strictly smaller load now than it had in 𝑥

Journal of Artificial Intelligence Research, Vol. 83, Article 29. Publication date: August 2025.

29:22 Harks, Henle, Klimm, Matuschke & Schedel

𝑟1 𝑟2 𝑟𝑡 𝑟𝑡

Fig. 9. Illustration for the case 𝑟𝑡 𝑟1 (with 𝑡= 3).

(before player 𝑘was added to the game, otherwise, player 𝑘would be placed on 𝑟 rather than on 𝑟1). This shows that 𝑟 {𝑟1, . . . ,𝑟𝑡 1} needs to hold, and since deviating to 𝑟𝑡 1 is cheapest and 𝑟𝑡 1 has the smallest index among the cheapest deviations, the assertion follows. Consider the situation after the change from 𝑟𝑡to 𝑟𝑡 1 (of some player 𝑗, see Figure 10 for illustration). We will show that unhappy players have load 𝑀(consequently, they want to deviate to a resource with load 𝑀or load 𝑀 2). Assume, by contradiction, that there is an unhappy player ℎon a resource with load 𝑀 1 (and 𝐾-improving deviation ˆ𝑟). Compare the current situation with the situation before player 𝑘was added to the game. Since the cost of player ℎ s resource can only be smaller and the players on that resource were happy in 𝑥, we get that the deviation cost to ˆ𝑟needs to be strictly smaller than it was before player 𝑘was added to the game. That is, either the load of ˆ𝑟is 𝑀 1, or ˆ𝑟 {𝑟1, . . . ,𝑟𝑡 2}. However, the order in which the players moved during the while-loop shows that it is neither beneficial for player ℎto move to 𝑟𝑡(the best option with load 𝑀 1) nor to 𝑟𝑡 2 (the best option in {𝑟1, . . . ,𝑟𝑡 2}); contradiction. Therefore, we get that unhappy players have load 𝑀(and want to move to a resource with load 𝑀or load 𝑀 2). Consequently, the next move is from 𝑟𝑡 1 to 𝑟1, or from 𝑟𝑡 1 to a resource with load 𝑀 2. The former case leads to a contradiction (note that in this case, (5) (7) hold since 𝑎 𝑟𝑡 𝑎 𝑟𝑡 1). Thus we are in the situation that a player on 𝑟𝑡 1 changes to a resource with load 𝑀 2. As above, we can show that the deviation is to 𝑟𝑡 2, and any player who is unhappy after that move has load 𝑀(and consequently wants to move to load 𝑀or load 𝑀 2). Repeating this argumentation shows that there can be no more than𝑡 3 further deviations (leading to at most 2𝑡= 𝑂(𝑚) many deviations in the while-loop in total).

The proof of Theorem 10 also yields the following upper bound on the running time of Algorithm 1.

Corollary 11. For 𝛼= 𝐾 1.1974, the running time of Algorithm 1 can be bounded by min{𝑂(𝑛2𝑚),𝑂(𝑛𝑚2)}.

Proof. We first argue that each iteration of the while-loop can be implemented in 𝑂(𝑚). Note that the deviation cost 𝑐𝑟(𝑟,𝑥 𝑖) if some player 𝑖deviates to 𝑟(w.r.t. 𝑥) does not only depend on 𝑟, but also on player 𝑖 s strategy 𝑥𝑖 (at least in some cases, cf. Observation 7). However, it can only be different for two players if one of these players is using a resource with maximum load 𝑀:= 𝑀(𝑥), and the other not. For that reason, we define for each resource 𝑟 𝑅the costs 𝑐1 𝑟(𝑥) and 𝑐2 𝑟(𝑥) if a player with load 𝑀and a player with load < 𝑀deviates to it (for example, if ℓ𝑟(𝑥) = 𝑀 1 then 𝑐1 𝑟(𝑥) := 𝑎𝑟(ℓ𝑟(𝑥) + 1) + 𝐵 |𝑀 1(𝑥) | and 𝑐2 𝑟(𝑥) := 𝑎𝑟(ℓ𝑟(𝑥) + 1) + 𝐵 |𝑀 1(𝑥) |+1). With 𝑐1(𝑥) := min𝑟 𝑅𝑐1 𝑟(𝑥) and 𝑐2(𝑥) := min𝑟 𝑅𝑐2 𝑟(𝑥), as well as 𝑟1(𝑥) and 𝑟2(𝑥) being the resources with smallest index in arg min𝑟 𝑅𝑐1 𝑟(𝑥) and arg min𝑟 𝑅𝑐2 𝑟(𝑥), we get that the players on resource 𝑟 𝑅are happy

Journal of Artificial Intelligence Research, Vol. 83, Article 29. Publication date: August 2025.

Multi-Leader Congestion Games with an Adversary 29:23

𝑟1 𝑟2 𝑟𝑡 𝑟𝑡

Fig. 10. Illustration for the case 𝑟𝑡 𝑟𝑡 1 (with 𝑡= 3).

if and only if 𝑐𝑟 (𝑥) 𝛼𝑐1(𝑥) for ℓ𝑟 (𝑥) = 𝑀, and 𝑐𝑟 (𝑥) 𝛼𝑐2(𝑥) for ℓ𝑟 (𝑥) < 𝑀. Furthermore, in case the players on resource 𝑟 are unhappy, 𝑟1(𝑥) (or 𝑟2(𝑥), respectively) is a best response with smallest index for ℓ𝑟 (𝑥) = 𝑀(for ℓ𝑟 (𝑥) < 𝑀). With this, it is easy to see that each iteration of the while-loop can be implemented in 𝑂(𝑚). Furthermore, the proof of Theorem 10 shows that in the 𝑘th iteration of the for-loop, the number of iterations of the while-loop can be bounded by 𝑂(𝑚), or alternatively also by 2𝑘(no player moves more than twice). Since there are 𝑛iterations of the for-loop and Í𝑛 𝑘=1 2𝑘= 𝑂(𝑛2), we get min{𝑂(𝑛2),𝑂(𝑛𝑚)} as an upper bound for the total number of iterations of the while-loop, implying the desired bound on the total running time.

The proof of Theorem 10 also reveals that 𝑛 5 and 𝑚 3 need to hold for any instance which has no exact PNE, or, in other words, the following corollary holds.

Corollary 12. Exact PNE always exist if 𝑛 4 or 𝑚 2.

Proof. Note that the only case where the proof of Theorem 10 fails if we consider 𝛼= 1 instead of 𝛼= 𝐾is the case corresponding to Figure 9. Since 𝑟1, 𝑟𝑡and 𝑟𝑡are three different resources, and with respect to 𝑥 there are at least three players using 𝑟1, at least one player using 𝑟𝑡and at least one player using 𝑟𝑡, the statement follows.

4.3 Tightness of 𝛼= 𝐾

In this subsection, we provide an instance where no 𝛼-approximate PNE with 𝛼< 𝐾exists, showing that 𝛼= 𝐾 is the smallest possible value such that the existence of an 𝛼-approximate equilibrium can be guaranteed. The following lemma tells us that if we want to investigate the existence of an 𝛼-PNE (for some 𝛼 [1, 2]), it suffices to consider profiles with decreasing loads.

Lemma 13. Assume that the resource set 𝑅= {𝑟1, . . . ,𝑟𝑚} is ordered such that 𝑎1 𝑎𝑚. Then: For any 𝛼 [1, 2], if there exists an 𝛼-approximate PNE, then there also exists an 𝛼-approximate PNE 𝑥with decreasing loads, that is, with ℓ1(𝑥) ℓ𝑚(𝑥).

Proof. Consider an 𝛼-approximate PNE 𝑦. If the loads are decreasing we are done, thus assume that there are resources 𝑟,𝑟 𝑅with 𝑎𝑟 𝑎𝑟and ℓ𝑟 (𝑦) < ℓ𝑟(𝑦); see Figure 11(a) for illustration. Consider the profile 𝑥 resulting from 𝑦by switching the players using 𝑟and 𝑟 , thus ℓ𝑟(𝑥) = ℓ𝑟 (𝑦), ℓ𝑟 (𝑥) = ℓ𝑟(𝑦) and ℓ 𝑟(𝑥) = ℓ 𝑟(𝑦) for all 𝑟 𝑅\ {𝑟,𝑟 }; see Figure 11(b). We now show that 𝑥is an 𝛼-approximate PNE, too, which proves the

Journal of Artificial Intelligence Research, Vol. 83, Article 29. Publication date: August 2025.

29:24 Harks, Henle, Klimm, Matuschke & Schedel

lemma. Let 𝑀:= 𝑀(𝑦) = max{ℓ 𝑟(𝑦) : 𝑟 𝑅} denote the maximum load with respect to 𝑦. Note that 𝑀= 𝑀(𝑥) and |𝑀 1(𝑥)| = |𝑀 1(𝑦)|. We now show that all players are happy in 𝑥.

(a) Situation in profile 𝑦.

(b) Situation in profile 𝑥(after switching the players using 𝑟and 𝑟 )

Fig. 11. Illustration for Lemma 13.

First consider a player 𝑗with 𝑥𝑗 {𝑟,𝑟 }. Clearly, the cost experienced by player 𝑗did not change (comparing 𝑦and 𝑥). Also, the deviation cost of player 𝑗to 𝑟 {𝑟,𝑟 } did not change. Furthermore, since the load on 𝑟

increased, the deviation cost to 𝑟 can only be larger than before (that is, w.r.t. 𝑦). Finally, the deviation cost to 𝑟 w.r.t. 𝑥can only be larger than the deviation cost to 𝑟 w.r.t. 𝑦. Using that player 𝑗was happy in 𝑦, we conclude that the same holds in 𝑥. Now assume player 𝑗uses 𝑟 , that is, 𝑥𝑗= 𝑟 and 𝑦𝑗= 𝑟. Since ℓ𝑟 (𝑥) = ℓ𝑟(𝑦), the cost experienced by player 𝑗 can only be smaller in 𝑥(compared to 𝑦). Furthermore, the deviation cost if player 𝑗deviates to a resource 𝑟 𝑟 did not change. Finally, the deviation cost of player 𝑗to 𝑟w.r.t. 𝑥can only be larger than the deviation cost of player 𝑗to 𝑟 w.r.t. 𝑦. Since player 𝑗was happy in 𝑦, we again conclude that player 𝑗is also happy in 𝑥. It remains to consider the players using resource 𝑟. Since the load on 𝑟decreased, the cost experienced on 𝑟 can only be smaller in 𝑥compared to 𝑦. It is furthermore easy to see that the deviation cost if a player deviates from 𝑟to 𝑟 can only be larger in 𝑥than in 𝑦. This shows that players do not want to deviate from 𝑟to 𝑟 (w.r.t. 𝑥). To complete the proof, it remains to show that the same holds for a deviation from 𝑟to 𝑟 𝑟 . If the deviation cost from 𝑟to 𝑟did not change we are done, thus assume it changed. This is only possible in two cases: Either ℓ 𝑟(𝑦) = 𝑀 1 and ℓ𝑟(𝑦) = 𝑀, or ℓ 𝑟(𝑦) = 𝑀 2 and 𝑟was the only maximum load resource in 𝑦. Note that in both cases, ℓ𝑟(𝑥) = ℓ𝑟 (𝑦) 𝑀 1. Consider first the case that ℓ 𝑟(𝑦) = 𝑀 1 and ℓ𝑟(𝑦) = 𝑀and assume, by contradiction, that a deviation from 𝑟 to 𝑟is 𝛼-improving in 𝑥, and thus

𝑎𝑟(𝑀 1) 𝑎𝑟ℓ𝑟(𝑥) = 𝑐𝑟(𝑥) > 𝛼(𝑎 𝑟𝑀+ 𝐵 𝑝+1), (8)

where 𝑝:= |𝑀 1(𝑦)| 1 denotes the number of resources with load 𝑀in 𝑦. On the other hand, using that 𝑦is an 𝛼-PNE, 𝑐𝑟(𝑦) = 𝑎𝑟𝑀+ 𝐵

𝑝 𝛼(𝑎 𝑟𝑀+ 𝐵

Combining inequalities (8) and (9) leads to

𝑝 𝑎 𝑟𝑀< 𝑎𝑟(𝑀 1)

Journal of Artificial Intelligence Research, Vol. 83, Article 29. Publication date: August 2025.

Multi-Leader Congestion Games with an Adversary 29:25

Multiplying with 𝛼 𝑝yields

𝑎𝑟𝑀𝑝+ 𝐵 𝛼𝐵< 𝑎𝑟(𝑀 1)𝑝 𝛼𝐵𝑝

𝑝+1 (1 𝛼+ 𝛼𝑝

𝑝+1)𝐵< 𝑎𝑟𝑝 0.

Since 𝐵> 0 we get 1 𝛼+ 𝛼𝑝

𝑝+1 < 0, or, equivalently, 𝛼> 𝑝+ 1 2. But this contradicts 𝛼 2. To complete the proof, it remains to consider the case that ℓ 𝑟(𝑦) = 𝑀 2 and 𝑟is the only resource with load 𝑀 in 𝑦. As above, we assume by contradiction that

𝑎𝑟(𝑀 1) 𝑎𝑟ℓ𝑟(𝑥) = 𝑐𝑟(𝑥) > 𝛼(𝑎 𝑟(𝑀 1)). (10)

Since 𝑦is an 𝛼-PNE, we have 𝑐𝑟(𝑦) = 𝑎𝑟𝑀+ 𝐵 𝛼(𝑎 𝑟(𝑀 1) + 𝐵 𝑞+2), (11)

where 𝑞 0 denotes the number of resources with load 𝑀 1 in 𝑦. Combining inequalities (10) and (11) yields

𝛼 𝐵 𝑞+2 + 𝑎 𝑟 𝑎 𝑟𝑀< 𝑎𝑟(𝑀 1)

and this implies 𝐵(1 𝛼 𝑞+2) < 𝑎𝑟 0.

But with 𝐵> 0 and 1 𝛼 𝑞+2 0 (note that 𝛼 2), we get a contradiction. We have thus shown that players on 𝑟 do not want to deviate to 𝑟 𝑟 (w.r.t. 𝑥), completing the proof.

Using the above lemma, we can show the following theorem.

Theorem 14. There exists an instance with three resources and five players such that there is no 𝛼-approximate PNE for any 𝛼< 𝐾, where 𝐾 1.1974 is as specified in (3).

Proof. Consider the instance with 𝑚= 3 resources, 𝑛= 5 players, budget 𝐵= 1, and resource cost coefficients

𝑎1 = 0, 𝑎2 = 𝐾/2 1/4 0.3487, and 𝑎3 = 1/𝐾 0.8351.

We proceed to show that there is no 𝛼-approximate PNE for 𝛼< 𝐾. Using 𝑎1 < 𝑎2 < 𝑎3 and Lemma 13, it suffices to show that there is no 𝛼-PNE among the five load profiles (5, 0, 0), (4, 1, 0), (3, 2, 0), (3, 1, 1), (2, 2, 1). Let 𝛼< 𝐾. We show that for any of these load profiles, there exists an 𝛼-improving deviation, showing the claim. To this end, consider Table 5, where we provide a deviation for each candidate profile which is 𝛼-improving if the given conditions on 𝛼are satisfied. It is easy to check that these conditions are indeed fulfilled for 𝛼< 𝐾.

5 Computing Optimal Approximate Equilibria

As in the last section, we again assume throughout this section that the underlying congestion game is a symmetric singleton congestion game, that is, each player chooses exactly one of the available resources. In the last section, we showed that 𝛼= 𝐾is the smallest possible value for 𝛼such that the existence of an 𝛼-approximate PNE can be guaranteed for any such instance of a multi-leader congestion game with an adversary. However, there are clearly instances where 𝛼-PNE with 𝛼< 𝐾exist (in particular, all instances exhibiting an exact PNE). We show in this section how to compute efficiently a best approximate PNE for a given instance, that is, with smallest possible 𝛼such that an 𝛼-PNE exists for this instance. To this end, consider a multi-leader congestion game with an adversary with resource set 𝑅= [𝑚] and 𝑎1 𝑎𝑚.2 We first show that for a given 𝛼 [1, 𝐾], one can decide in polynomial time whether there exists an 𝛼-PNE 𝑥. (Note that we can assume 𝛼 [1, 𝐾] since we want to find the smallest possible 𝛼.) Secondly, we argue that we only need to consider polynomially many values for 𝛼.

2Note that, in this section, we use the simplified notation 𝑅= [𝑚] for the set of resources.

Journal of Artificial Intelligence Research, Vol. 83, Article 29. Publication date: August 2025.

29:26 Harks, Henle, Klimm, Matuschke & Schedel

Table 5. 𝛼-improving deviations for the candidate profiles.

load profile 𝛼-improving deviation conditions on 𝛼 (of a player using 𝑟to 𝑟 , notation 𝑟 𝑟 )

(5, 0, 0) 𝑟1 𝑟2 5𝑎1 + 𝐵> 𝛼𝑎2 𝛼< 1/𝑎2 = 2 𝐾 1/2 2.86

(4, 1, 0) 𝑟1 𝑟2 4𝑎1 + 𝐵> 𝛼2𝑎2 𝛼< 1/(2𝑎2) = 1 𝐾 1/2 1.43

(3, 2, 0) 𝑟1 𝑟3 3𝑎1 + 𝐵> 𝛼𝑎3 𝛼< 1/𝑎3 = 𝐾

(3, 1, 1) 𝑟3 𝑟2 𝑎3 > 𝛼2𝑎2 𝛼< 1 𝐾(𝐾 1/2) = 𝐾

(2, 2, 1) 𝑟2 𝑟1 2𝑎2 + 𝐵/2 > 𝛼(3𝑎1 + 𝐵) 𝛼< 2𝑎2 + 1/2 = 𝐾

Let 𝛼 [1, 𝐾]. We want to investigate the existence of an 𝛼-PNE. Note that by Lemma 13, we can restrict our attention to profiles 𝑥with decreasing loads, that is, with ℓ1(𝑥) ℓ𝑚(𝑥). Together with 𝑎1 𝑎𝑚, this leads to the following three easy observations (compare also Observation 7): Firstly, if several resources have the same load, then all players using these resources are happy if and only if the players on the last such resource are happy.3 Secondly, deviating to the first among several resources having the same load is always cheapest among those resources. Thirdly, it is never beneficial to deviate to a resource where the load is smaller by one than the currently experienced load. Making use of these observations, it is easy to check whether there is an 𝛼-PNE among the profiles with a difference of at most two between the largest and the smallest load: In the following three cases, we first test the profile in which all resources have the same load, that is, the difference between the largest and the smallest load is zero, then all profiles with difference between the largest and the smallest load equal to one, and finally the profiles where the difference is two.

𝑚 N and 𝑎𝑚 𝑛

𝑚+ 1) + 𝐵), any 𝑥with ℓ𝑟(𝑥) = 𝑛

𝑚for all 𝑟 [𝑚] is an 𝛼-PNE. (2) For each 𝑘 {1, . . . ,𝑚 1} with 𝑀:= 𝑛 𝑘+𝑚

𝑚 N and 𝑀 1: If the following conditions are fulfilled, any 𝑥with ℓ𝑟(𝑥) = 𝑀for all 𝑟 𝑘and ℓ𝑟(𝑥) = 𝑀 1 for all 𝑟 {𝑘+ 1, . . . ,𝑚} is an 𝛼-PNE:

𝑎𝑚(𝑀 1) 𝛼 (𝑎1(𝑀+ 1) + 𝐵) if 𝑘< 𝑚 1 : 𝑎𝑚(𝑀 1) 𝛼 (𝑎𝑘+1 𝑀+ 𝐵 𝑘+1)

players with load 𝑀 1 happy

if 𝑘 2 : 𝑎𝑘 𝑀+ 𝐵

𝑘 𝛼 (𝑎1(𝑀+ 1) + 𝐵) players with load 𝑀happy

(3) For each 𝑘 {1, . . . ,𝑚 1} and 𝑘 {𝑘+ 1, . . . ,𝑚} with 𝑀:= 𝑛+2𝑚+1 𝑘 𝑘

𝑚 N and 𝑀 2: If the following conditions are fulfilled, any 𝑥with ℓ𝑟(𝑥) = 𝑀for all 𝑟 𝑘, ℓ𝑟(𝑥) = 𝑀 1 for all 𝑟 {𝑘+ 1, . . . ,𝑘 1} and ℓ𝑟(𝑥) = 𝑀 2 for all 𝑟 {𝑘 , . . . ,𝑚} is an 𝛼-PNE. (Note that 𝑘 = 𝑘+ 1 is possible, which means that there

3Expressions such as first or last are with respect to the ordering 𝑟1,𝑟2, . . . ,𝑟𝑚of the resources.

Journal of Artificial Intelligence Research, Vol. 83, Article 29. Publication date: August 2025.

Multi-Leader Congestion Games with an Adversary 29:27

are no resources having load 𝑀 1.)

𝑎𝑚(𝑀 2) 𝛼 (𝑎1(𝑀+ 1) + 𝐵) if 𝑘 > 𝑘+ 1 : 𝑎𝑚(𝑀 2) 𝛼 (𝑎𝑘+1 𝑀+ 𝐵 𝑘+1) if 𝑘 < 𝑚: 𝑎𝑚(𝑀 2) 𝛼 (𝑎𝑘 (𝑀 1))

players with load 𝑀 2 happy

if 𝑘 > 𝑘+ 1 : 𝑎𝑘 1(𝑀 1) 𝛼 (𝑎1(𝑀+ 1) + 𝐵) if 𝑘 > 𝑘+ 2 : 𝑎𝑘 1(𝑀 1) 𝛼 (𝑎𝑘+1 𝑀+ 𝐵 𝑘+1)

players with load 𝑀 1 happy

if 𝑘= 1 : 𝑎𝑘 𝑀+ 𝐵 𝛼 (𝑎𝑘 (𝑀 1) + 𝐵

𝑘 ) if 𝑘 2 : 𝑎𝑘 𝑀+ 𝐵

𝑘 𝛼 (𝑎1(𝑀+ 1) + 𝐵) if 𝑘 2 : 𝑎𝑘 𝑀+ 𝐵

𝑘 𝛼 (𝑎𝑘 (𝑀 1))

players with load 𝑀 happy

Clearly, one can check the above three cases in 𝑂(𝑚2), leading to the following result.

Lemma 15. We can decide in 𝑂(𝑚2) whether there is an 𝛼-PNE among the profiles with a difference of at most two between the largest and the smallest load. In case of existence, we can also compute a corresponding load vector efficiently.

In the following, we analyze the profiles where the difference between the largest and the smallest load is larger than two. For such a profile 𝑥, we introduce the following notation. Let 𝑀:= 𝑀(𝑥) denote the maximum load in 𝑥. Then, 𝑘= 𝑘(𝑥) denotes the largest resource having load 𝑀, 𝑘 = 𝑘 (𝑥) is the smallest resource with load strictly smaller than 𝑀 1, and 𝑘 = 𝑘 (𝑥) denotes the smallest resource with load strictly smaller than 𝑀 2. In other words, ℓ𝑟(𝑥) = 𝑀for all 𝑟 {1, . . . ,𝑘}, ℓ𝑟(𝑥) = 𝑀 1 for all 𝑟 {𝑘+ 1, . . . ,𝑘 1}, ℓ𝑟(𝑥) = 𝑀 2 for all 𝑟 {𝑘 , . . . ,𝑘 1}, and ℓ𝑟(𝑥) 𝑀 3 for all 𝑟 {𝑘 , . . . ,𝑚}, see Figure 12 for illustration. Note that 𝑘 = 𝑘+ 1 or 𝑘 = 𝑘 are possible, in which cases there are no resources with load 𝑀 1 or 𝑀 2, respectively.

Fig. 12. Illustration for the definition of 𝑘, 𝑘 , and 𝑘 .

We now argue that there exist values 𝑐𝑀= 𝑐𝑀(𝑥) and 𝑐<𝑀= 𝑐<𝑀(𝑥) such that 𝑥is an 𝛼-PNE if and only if

𝑎𝑘 𝑀+ 𝐵/𝑘 𝛼 𝑐𝑀 and (12)

𝑎𝑟 ℓ𝑟(𝑥) 𝛼 𝑐<𝑀for all 𝑟> 𝑘. (13)

Essentially, the values 𝑐𝑀and 𝑐<𝑀describe the cost of a best response for a player using a resource with load 𝑀, and load smaller than 𝑀, respectively. We now explain this in more detail. Consider, for example, a player 𝑖using

Journal of Artificial Intelligence Research, Vol. 83, Article 29. Publication date: August 2025.

29:28 Harks, Henle, Klimm, Matuschke & Schedel

a resource with load < 𝑀. Then, the cost of a best response for player 𝑖is

min{𝜋𝑖(𝑟,𝑥 𝑖) : 𝑟 𝑅,𝑟 𝑥𝑖}

= min{𝑎1 (𝑀+ 1) + 𝐵,𝑎𝑘+1 𝑀+ 𝐵 𝑘+1 if ℓ𝑘+1(𝑥) = 𝑀 1 and 𝑘+ 1 𝑥𝑖,

𝑎𝑟 (ℓ𝑟(𝑥) + 1) 𝑟 𝑅with ℓ𝑟(𝑥) 𝑀 2 and 𝑟 𝑥𝑖}.

Using this, it is easy to see that 𝑎𝑥𝑖ℓ𝑥𝑖(𝑥) 𝛼 min{𝜋𝑖(𝑟,𝑥 𝑖) : 𝑟 𝑅,𝑟 𝑥𝑖} if and only if

𝑎𝑥𝑖ℓ𝑥𝑖(𝑥) 𝛼 min{𝑎1 (𝑀+ 1) + 𝐵,𝑎𝑘+1 𝑀+ 𝐵 𝑘+1 if ℓ𝑘+1(𝑥) = 𝑀 1,

𝑎𝑟 (ℓ𝑟(𝑥) + 1) 𝑟 𝑅with ℓ𝑟(𝑥) 𝑀 2}

= 𝛼 min{𝑎1 (𝑀+ 1) + 𝐵,𝑎𝑘+1 𝑀+ 𝐵 𝑘+1 if 𝑘 𝑘+ 2,

𝑎𝑘 (𝑀 1) if 𝑘 < 𝑘 ,𝑎𝑟 (ℓ𝑟(𝑥) + 1) 𝑟 𝑘 }

By very similar argumentation, one can derive that

( min{𝑎𝑘 (𝑀 1) + 𝐵/𝑘 if 𝑘 < 𝑘 ,𝑎𝑟 (ℓ𝑟(𝑥) + 1) 𝑟 𝑘 }, if 𝑘= 1, min{𝑎1 (𝑀+ 1) + 𝐵,𝑎𝑘 (𝑀 1) if 𝑘 < 𝑘 ,𝑎𝑟 (ℓ𝑟(𝑥) + 1) 𝑟 𝑘 }, if 𝑘 2.

Using the introduced notation, we now describe how to check the existence of an 𝛼-PNE among all profiles with a difference larger than two between the largest and the smallest load. We start with Lemma 16 below, which follows from two main insights (see the proof for all details): First of all, for given values of 𝑀,𝑘,𝑘 and 𝑘 , there are only polynomially many possible values for 𝑐𝑀and 𝑐<𝑀. Secondly, if we (only) know the values 𝑀,𝑘,𝑘

and 𝑘 as well as 𝑐𝑀and 𝑐<𝑀of some 𝛼-PNE 𝑥, we can reconstruct in polynomial time the corresponding load vector ℓ(𝑥). To this end, note that the minimum properties of 𝑐𝑀and 𝑐<𝑀, as well as the Nash condition (13), yield upper and lower bounds for the loads ℓ𝑟(𝑥) of all resources 𝑟 𝑘 (for 𝑟< 𝑘 , the load ℓ𝑟(𝑥) is uniquely determined by the definitions of 𝑀,𝑘,𝑘 and 𝑘 ).

Lemma 16. Given 𝑀 {max{3, 𝑛

𝑚 }, . . . ,𝑛}, 𝑘 {1, . . . ,𝑚 1}, 𝑘 {𝑘+ 1, . . . ,𝑚} and 𝑘 {𝑘 , . . . ,𝑚}, we can decide efficiently if there exists an 𝛼-approximate PNE 𝑥such that 𝑀(𝑥) = 𝑀, 𝑘(𝑥) = 𝑘, 𝑘 (𝑥) = 𝑘 and 𝑘 (𝑥) = 𝑘 . In case of existence, we can also compute a corresponding load vector efficiently.

Proof. Assume for the moment that there exists an 𝛼-PNE 𝑥with 𝑀(𝑥) = 𝑀, 𝑘(𝑥) = 𝑘, 𝑘 (𝑥) = 𝑘 , and 𝑘 (𝑥) = 𝑘 . Recall that

𝑐<𝑀(𝑥) := min{𝑎1(𝑀+ 1) + 𝐵,𝑎𝑘+1𝑀+ 𝐵 𝑘+1 if 𝑘 𝑘+ 2,𝑎𝑘 (𝑀 1) if 𝑘 < 𝑘 ,

𝑎𝑟(ℓ𝑟(𝑥) + 1) 𝑟 𝑘 }

( min{𝑎𝑘 (𝑀 1) + 𝐵/𝑘 if 𝑘 < 𝑘 ,𝑎𝑟(ℓ𝑟(𝑥) + 1) 𝑟 𝑘 }, if 𝑘= 1, min{𝑎1(𝑀+ 1) + 𝐵,𝑎𝑘 (𝑀 1) if 𝑘 < 𝑘 ,𝑎𝑟(ℓ𝑟(𝑥) + 1) 𝑟 𝑘 }, if 𝑘 2.

Since we know the values 𝑀,𝑘,𝑘 ,𝑘 , and for 𝑟 𝑘 the load ℓ𝑟(𝑥) attains values in {0, 1, . . . , 𝑀 3}, there are at most 3 + (𝑚 𝑘 + 1) (𝑀 2) = 𝑂(𝑚𝑛) many possible values that 𝑐<𝑀(𝑥) can attain, and at most 2+ (𝑚 𝑘 +1) (𝑀 2) = 𝑂(𝑚𝑛) many possible values that 𝑐𝑀(𝑥) can attain. Thus we can identify polynomially large candidate sets 𝐶𝑀and 𝐶<𝑀which definitely contain 𝑐𝑀(𝑥) and 𝑐<𝑀(𝑥), respectively (for instance, for 𝑘= 1 and 𝑘 < 𝑘 we define

𝐶𝑀:= {𝑎𝑘 (𝑀 1) + 𝐵/𝑘 ,𝑎𝑟(ℓ+ 1) 𝑟 𝑘 and 0 ℓ 𝑀 3},

Journal of Artificial Intelligence Research, Vol. 83, Article 29. Publication date: August 2025.

Multi-Leader Congestion Games with an Adversary 29:29

and in the same manner for the other cases and for 𝐶<𝑀). We further reduce these candidate sets by deleting all values 𝑐𝑀 𝐶𝑀, 𝑐<𝑀 𝐶<𝑀not satisfying one or more of the following inequalities, where the first inequalities come from the Nash conditions (players using resources with load 𝑀, 𝑀 1 or 𝑀 2 do not want to deviate), and the remaining inequalities are due to the minimum properties of 𝑐𝑀(𝑥) and 𝑐<𝑀(𝑥), respectively:

1. : 𝑎𝑘 𝑀+ 𝐵

if 𝑘 𝑘+ 2: 𝑎𝑘 1 (𝑀 1) 𝛼 𝑐<𝑀;

if 𝑘 < 𝑘 : 𝑎𝑘 1 (𝑀 2) 𝛼 𝑐<𝑀;

2. : if 𝑘 2: 𝑎1 (𝑀+ 1) + 𝐵 𝑐𝑀;

if 𝑘= 1 and 𝑘 < 𝑘 : 𝑎𝑘 (𝑀 1) + 𝐵

if 𝑘 2 and 𝑘 < 𝑘 : 𝑎𝑘 (𝑀 1) 𝑐𝑀;

3. : 𝑎1 (𝑀+ 1) + 𝐵 𝑐<𝑀;

if 𝑘 𝑘+ 2: 𝑎𝑘+1 𝑀+ 𝐵 𝑘+1 𝑐<𝑀;

if 𝑘 < 𝑘 : 𝑎𝑘 (𝑀 1) 𝑐<𝑀.

Note that for all 𝑟 𝑘 we have by the Nash conditions that

𝑎𝑟ℓ𝑟(𝑥) 𝛼 𝑐<𝑀(𝑥) ℓ𝑟(𝑥) j 𝛼 𝑐<𝑀(𝑥)

Furthermore, ℓ𝑟(𝑥) 𝑀 3 (by definition, 𝑟= 𝑘 is the smallest resource with load strictly smaller than 𝑀 2). On the other hand, we also get a lower bound on ℓ𝑟(𝑥) by using the minimum properties of 𝑐𝑀(𝑥) and 𝑐<𝑀(𝑥), since 𝑎𝑟(ℓ𝑟(𝑥) + 1) 𝑐𝑀(𝑥) ℓ𝑟(𝑥) l 𝑐𝑀(𝑥)

and 𝑎𝑟(ℓ𝑟(𝑥) + 1) 𝑐<𝑀(𝑥) ℓ𝑟(𝑥) l 𝑐<𝑀(𝑥)

Altogether, these observations lead to Algorithm 2, which is clearly a polynomial algorithm (its running time can be bounded by 𝑂(𝑚3𝑛2) since we have at most 𝑂(𝑚2𝑛2) iterations of the loop in line 10 and one of these iterations takes 𝑂(𝑚)). For correctness, assume that it terminates in line 26 with a load vector ℓand pair ( 𝑐𝑀, 𝑐<𝑀). We need to show that there exists an 𝛼-PNE 𝑥with ℓ(𝑥) = ℓ, 𝑀(𝑥) = 𝑀, 𝑘(𝑥) = 𝑘, 𝑘 (𝑥) = 𝑘 , and 𝑘 (𝑥) = 𝑘 . Clearly, ℓ𝑟 0 for all 𝑟 𝑅and Í 𝑟 𝑅ℓ𝑟= 𝑛. Thus there exists a strategy profile 𝑥with load vector ℓ(𝑥) = ℓ, which directly implies 𝑀(𝑥) = 𝑀, 𝑘(𝑥) = 𝑘, 𝑘 (𝑥) = 𝑘 and 𝑘 (𝑥) = 𝑘 . It remains to show that 𝑥is in fact an 𝛼-PNE. We obtain that 𝑎𝑘 𝑀+ 𝐵/𝑘 𝛼 𝑐𝑀and 𝑎𝑟ℓ𝑟(𝑥) 𝛼 𝑐<𝑀for all 𝑟> 𝑘hold (by computation of the candidate sets 𝐶𝑀, 𝐶<𝑀, and upper bounds 𝑏 𝑟). Furthermore, 𝑐𝑀 𝑐𝑀(𝑥) and 𝑐<𝑀 𝑐<𝑀(𝑥) (by computation of the candidate sets 𝐶𝑀, 𝐶<𝑀, and lower bounds 𝑏𝑟). Altogether, this shows that 𝑥is an 𝛼-PNE, and that the algorithm is correct (clearly, if it terminates in a line different from line 26, there cannot be an 𝛼-PNE with the desired properties).

Since there are only polynomially many possible values that 𝑀,𝑘,𝑘 , and 𝑘 can attain, Lemma 16 leads to an efficient procedure for testing existence of an 𝛼-PNE among the profiles with a difference larger than two between largest and smallest load. Using this, we can now show the main result of this section.

4Note here that we can assume w.l.o.g. that 𝑎𝑟> 0 for all 𝑟 𝑘 , otherwise there is no 𝛼-PNE corresponding to 𝑀,𝑘,𝑘 ,𝑘 since players on 𝑟1 would always want to deviate to 𝑟. 5Note that 𝑐<𝑀(𝑥) 𝑐𝑀(𝑥) and thus the lower bound on ℓ𝑟(𝑥) achieved from 𝑐𝑀(𝑥) is stronger.

Journal of Artificial Intelligence Research, Vol. 83, Article 29. Publication date: August 2025.

29:30 Harks, Henle, Klimm, Matuschke & Schedel

Algorithm 2: Subroutine needed to compute best-possible 𝛼.

Input: 𝛼 [1, 𝐾] and 𝑀,𝑘,𝑘 ,𝑘 as specified in Lemma 16. Output: Load vector ℓ= ℓ(𝑥) corresponding to an 𝛼-PNE 𝑥with 𝑀(𝑥) = 𝑀, 𝑘(𝑥) = 𝑘, 𝑘 (𝑥) = 𝑘 and 𝑘 (𝑥) = 𝑘 , if such an 𝑥exists.

1 if 𝑎𝑘 = 0 then

2 Terminate the algorithm; // No 𝛼-PNE 𝑥corresponding to 𝑀,𝑘,𝑘 ,𝑘 .

3 ℓ𝑟 𝑀 𝑟 {1, . . . ,𝑘};

4 ℓ𝑟 𝑀 1 𝑟 {𝑘+ 1, . . . ,𝑘 1};

5 ℓ𝑟 𝑀 2 𝑟 {𝑘 , . . . ,𝑘 1};

6 𝑛 𝑛 𝑘𝑀 (𝑘 𝑘 1)(𝑀 1) (𝑘 𝑘 )(𝑀 2); // remaining players

7 if 𝑛 < 0 then

8 Terminate the algorithm; // No 𝛼-PNE 𝑥corresponding to 𝑀,𝑘,𝑘 ,𝑘 .

9 Compute candidate sets 𝐶𝑀, 𝐶<𝑀for 𝑐𝑀, 𝑐<𝑀as described in the proof of Lemma 16;

10 forall ( 𝑐𝑀, 𝑐<𝑀) 𝐶𝑀 𝐶<𝑀with 𝑐𝑀 𝑐<𝑀do

11 for 𝑟= 𝑘 , . . . ,𝑚do

12 𝑏𝑟 max{0, 𝑐𝑀

𝑎𝑟 1}; // lower bound on ℓ𝑟

13 𝑏 𝑟 min{𝑀 3, 𝛼 𝑐<𝑀

𝑎𝑟 }; // upper bound on ℓ𝑟

14 if 𝑏𝑟> 𝑏 𝑟then

15 Go to Line 10 and continue with the next pair ( 𝑐𝑀, 𝑐<𝑀), or terminate the algorithm if current pair was the last;

16 // current pair not correct

17 if 𝑛 [Í 𝑟 𝑘 𝑏𝑟, Í 𝑟 𝑘 𝑏 𝑟] then

18 Go to Line 10 and continue with the next pair ( 𝑐𝑀, 𝑐<𝑀), or terminate the algorithm if current pair was the last;

19 // current pair not correct

20 ℓ𝑟 𝑏𝑟 𝑟 {𝑘 , . . . ,𝑚};

21 𝑛 𝑛 Í 𝑟 𝑘 𝑏𝑟;

22 while 𝑛 > 0 do

23 for 𝑟= 𝑘 , . . . ,𝑚do

24 ℓ𝑟 min{𝑏 𝑟,𝑏𝑟+ 𝑛 };

25 𝑛 𝑛 (ℓ𝑟 𝑏𝑟);

26 Terminate the algorithm;

Theorem 17. For a given instance, we can efficiently compute the smallest possible 𝛼such that an 𝛼-approximate PNE exists, as well as a corresponding load vector.

Proof. First note that if 𝑥is an 𝛼-PNE corresponding to the best possible 𝛼, there need to be resources 𝑟,𝑟 𝑅 (as well as a player 𝑖with 𝑥𝑖= 𝑟) such that 𝑎𝑟ℓ𝑟(𝑥) + 𝜅 𝑟(𝑥) = 𝛼 (𝑎𝑟 ℓ𝑟 (𝑟 ,𝑥 𝑖) + 𝜅 𝑟 (𝑟 ,𝑥 𝑖)) (otherwise 𝛼would not be the smallest possible approximation factor), or, equivalently,

𝛼= 𝑎𝑟ℓ𝑟(𝑥) + 𝜅 𝑟(𝑥) 𝑎𝑟 ℓ𝑟 (𝑟 ,𝑥 𝑖) + 𝜅 𝑟 (𝑟 ,𝑥 𝑖) .

Journal of Artificial Intelligence Research, Vol. 83, Article 29. Publication date: August 2025.

Multi-Leader Congestion Games with an Adversary 29:31

Since there are only 𝑂(𝑛𝑚2) many possible values for 𝑎𝑟ℓ𝑟(𝑥) + 𝜅 𝑟(𝑥), as well as for 𝑎𝑟 ℓ𝑟 (𝑟 ,𝑥 𝑖) + 𝜅 𝑟 (𝑟 ,𝑥 𝑖), there are only 𝑂(𝑛2𝑚4) many possible values for 𝛼. Since for a fixed 𝛼we can decide existence (and compute a load vector) of an 𝛼-PNE efficiently (by Lemmas 15 and 16), the theorem follows.

6 Further Remarks and Conclusion Before we conclude our paper, we briefly discuss a variation of the setting discussed in the preceding sections, namely additive (rather than multiplicative) approximate PNE.

6.1 Additively Approximate PNE

In addition to multiplicatively approximate equilibria, as studied in this paper, it is also possible to define additively approximate equilibria. An 𝜀-additive approximate PNE is a strategy profile 𝑥 𝑋such that

𝜋𝑖(𝑥) 𝜋𝑖(𝑦𝑖,𝑥 𝑖) + 𝜀for all 𝑦𝑖 𝑋𝑖and all 𝑖 𝑁.

Contrasting the case of 𝐾-multiplicative approximate PNE, however, the existence of 𝜀-additive approximate PNE for the class of games studied in Sections 4 and 5 of this paper cannot be guaranteed for any constant 𝜀> 0. To see this, note that the considered multi-leader congestion games with an adversary are invariant under scaling in the sense that multiplying all cost coefficients 𝑎𝑟and the adversary s budget 𝐵with the same factor 𝜆> 0 results in a game in which each player s private cost for any given strategy profile is scaled by the same factor 𝜆. As a result, given any constant 𝜀> 0, any instance of the game that does not have an exact PNE (such as, e.g., the one described in Example 5) can be scaled in such a way that it does not allow for an 𝜀-additive approximate PNE. We remark that, while the existence of approximate PNE with a small additive constant cannot be guaranteed, the approach in Section 5 can easily be adjusted to compute 𝜀-additive approximate PNE with the smallest possible 𝜀for a given instance.

6.2 Conclusion

We introduced a multi-leader single-follower Stackelberg game in which the leaders play a congestion game and subsequently an adversary attacks the resources with maximum loads, causing additional costs for the leaders. We first showed that pure Nash equilibria always exist if the leaders strategies are given by bases of matroids and the (linear) congestion cost functions are identical. However, if one of these two conditions is violated, PNE do not exist in general. Motivated by this, we studied approximate equilibria for the case of symmetric singleton congestion games and resource-specific linear congestion cost functions. Our main result shows that a 𝐾-approximate PNE always exists, where 𝐾 1.1974 is the unique solution of a cubic polynomial equation. To this end, we presented an efficient algorithm which computes a 𝐾-approximate PNE. Furthermore, we showed that the factor 𝐾is tight by providing an instance where no 𝛼-approximate PNE with 𝛼< 𝐾exists. However, for a specific instance there might be a better 𝛼-approximate PNE, that is, with 𝛼< 𝐾. We presented an efficient procedure that computes a best approximate PNE of a given instance. Our work suggests several interesting directions for further research regarding multi-leader congestion games with an adversary. For example, one could analyze whether the results from Section 4 continue to hold if one allows for more general strategy spaces in the leaders congestion game, for example, bases of matroids (and resource-specific congestion cost functions). Another interesting generalization is to consider different cost functions. Regarding this, note that our results from Section 4 (and similarly in Section 5) crucially rely on the existence of an ordering of the resources such that the loads are always nonincreasing during the course of Algorithm 1. For affine congestion cost functions 𝑎𝑟ℓ𝑟(𝑥) + 𝑏𝑟, with different 𝑏𝑟 0, or for resource-specific

Journal of Artificial Intelligence Research, Vol. 83, Article 29. Publication date: August 2025.

29:32 Harks, Henle, Klimm, Matuschke & Schedel

attacker costs, there is in general no such ordering, thus it is not clear how to apply our technique. However if the mentioned ordering exists, which is for example the case if the congestion cost functions are monomials 𝑎𝑟(ℓ𝑟(𝑥))𝑑for some 𝑑> 1 (the ordering then is such that the 𝑎𝑟s are nondecreasing), we believe that our algorithm (and its analysis) can be used, and it would be very interesting to analyze which approximation factor can be guaranteed in such a setting. It would furthermore be interesting to analyze the quality of approximate PNE. For example, one could measure the social cost of a strategy profile by the total cost of all players, and then compare a (best or worse) approximate PNE to a social optimum.

Acknowledgments

We thank the anonymous referees and the associate editor for their careful reading and helpful comments. This work was supported by Deutsche Forschungsgemeinschaft (DFG German Research Foundation) under grants HA 8041/4-1, MA 8439/1-1, and under Germany s Excellence Strategy The Berlin Mathematics Research Center MATH+ (EXC-2046/1, project ID: 390685689). An extended abstract of an earlier version of this article appeared in the Proceedings of the 36th AAAI Conference on Artificial Intelligence [24].

[1] H. Ackermann, H. Röglin, and B. Vöcking. 2009. Pure Nash equilibria in player-specific and weighted congestion games. Theoret. Comput. Sci., 410, 17, 1552 1563. [2] K. R. Apt and G. Schäfer. 2014. Selfishness level of strategic games. J. Artificial Intelligence Res., 49, 207 240. [3] M. Babaioff, R. Kleinberg, and C. H. Papadimitriou. 2009. Congestion games with malicious players. Games Econ. Behav., 67, 1, 22 35. [4] R. Bai, H. Lin, X. Yang, X. Wu, M. Li, and W. Jia. 2023. Stackelberg security games with contagious attacks on a network: reallocation to the rescue. J. Artificial Intelligence Res., 77, 487 515. [5] M. Beckmann, C. B. Mc Guire, and C. Winsten. 1956. Studies in the Economics of Transportation. Yale University Press, New Haven, CT, USA. [6] V. Bilò, L. Moscardelli, and C. Vinci. 2023. Uniform mixed equilibria in network congestion games with link failures. Math. Oper. Res., 49, 1, 509 535. [7] V. Bilò and C. Vinci. 2017. On the impact of singleton strategies in congestion games. In Proc. 25th Annual European Sympos. on Algorithms (ESA), 17:1 17:14. doi: 10.4230/LIPICS.ESA.2017.17. [8] I. Caragiannis, A. Fanelli, N. Gravin, and A. Skopalik. 2015. Approximate pure Nash equilibria in weighted congestion games: existence, efficient computation, and structure. ACM Trans. Economics and Comput., 3, 1, 2:1 2:32. [9] I. Caragiannis, A. Fanelli, N. Gravin, and A. Skopalik. 2011. Efficient computation of approximate pure Nash equilibria in congestion games. In Proc. 52st Annual IEEE Sympos. Foundations Comput. Sci. (FOCS), 532 541. [10] I. Caragiannis, M. Flammini, C. Kaklamanis, P. Kanellopoulos, and L. Moscardelli. 2011. Tight bounds for selfish and greedy load balancing. Algorithmica, 61, 3, 606 637. doi: 10.1007/S00453-010-9427-8. [11] B. Caskurlu, Ö. Ekici, and F. E. Kizilkaya. 2021. On singleton congestion games with resilience against collusion. In Computing and Combinatorics. C.-Y. Chen, W.-K. Hon, L.-J. Hung, and C.-W. Lee, (Eds.) Springer International Publishing, Cham, 37 48. isbn: 978-3-030-89543-3. [12] M. Castiglioni, A. Marchesi, N. Gatti, and S. Coniglio. 2019. Leadership in singleton congestion games: what is hard and what is easy. Artif. Intell., 277, 103177. [13] X. Chen, X. Hu, C. Wang, and X. Wu. 2020. The efficiency of Nash equilibria in the load balancing game with a randomizing scheduler. Theoret. Comput. Sci., 838, 180 194. doi: https://doi.org/10.1016/j.tcs.2020.07.024. [14] G. Christodoulou, M. Gairing, Y. Giannakopoulos, D. Poças, and C. Waldmann. 2023. Existence and complexity of approximate equilibria in weighted congestion games. Math. Oper. Res., 48, 1, 583 602. doi: 10.1287/MOOR.2022.1272. [15] J. R. Correa, C. Guzmán, T. Lianeas, E. Nikolova, and M. Schröder. 2022. Network pricing: how to induce optimal flows under strategic link operators. Oper. Res., 70, 1, 472 489. [16] C. Zaroliagis, G. Pantziou, and S. Kontogiannis, (Eds.) 2015. A selective tour through congestion games. Algorithms, Probability, Networks, and Games: Scientific Papers and Essays Dedicated to Paul G. Spirakis on the Occasion of His 60th Birthday. Springer International Publishing, 223 241. isbn: 978-3-319-24024-4. doi: 10.1007/978-3-319-24024-4_14. [17] M. Gairing. 2009. Malicious bayesian congestion games. In Approximation and Online Algorithms. E. Bampis and M. Skutella, (Eds.) Springer Berlin Heidelberg, 119 132.

Journal of Artificial Intelligence Research, Vol. 83, Article 29. Publication date: August 2025.

Multi-Leader Congestion Games with an Adversary 29:33

[18] M. Gairing, T. Harks, and M. Klimm. 2017. Complexity and approximation of the continuous network design problem. SIAM J. Optim., 27, 3, 1554 1582. [19] M. Gairing and F. Schoppmann. 2007. Total latency in singleton congestion games. In Proc. 3rd Internat. Workshop on Internet and Network Econom. (WINE), 381 387. doi: 10.1007/978-3-540-77105-0\_42. [20] J. Gan, E. Elkind, S. Kraus, and M. Wooldridge. 2022. Defense coordination in security games: equilibrium analysis and mechanism design. Artificial Intelligence, 313, 103791. doi: https://doi.org/10.1016/j.artint.2022.103791. [21] J. Gan, E. Elkind, and M. J. Wooldridge. 2018. Stackelberg security games with multiple uncoordinated defenders. In Proc. 17th Internat. Conf. Autonomous Agents and Multiagent Systems (AAMAS), 703 711. [22] Y. Giannakopoulos and D. Pocas. 2023. A unifying approximate potential for weighted congestion games. Theory Comput. Syst., 67, 4, 855 876. doi: 10.1007/S00224-023-10133-Z. [23] C. Hansknecht, M. Klimm, and A. Skopalik. 2014. Approximate pure Nash equilibria in weighted congestion games. In Proc. 17th. Internat. Workshop Approximation Algorithms Combinatorial Optimization Problems (APPROX), 242 257. doi: 10.4230/LIPICS.APPROXRANDOM.2014.242. [24] T. Harks, M. Henle, M. Klimm, J. Matuschke, and A. Schedel. 2022. Multi-leader congestion games with an adversary. In Proc. 36th Conf. Artif. Intell. (AAAI). Vol. 36 (5), 5068 5075. [25] T. Harks and M. Klimm. 2012. On the existence of pure Nash equilibria in weighted congestion games. Math. Oper. Res., 37, 3, 419 436. [26] T. Harks, M. Klimm, and J. Matuschke. 2022. Pure Nash equilibria in resource graph games. J. Artificial Intelligence Res., 72, 185 213. [27] T. Harks and A. Schedel. 2021. Stackelberg pricing games with congestion effects. Math. Program., 203, 763 799. [28] T. Harks, M. Schröder, and D. Vermeulen. 2019. Toll caps in privatized road networks. Eur. J. Oper. Res., 276, 3, 947 956. [29] X. He, A. Prasad, S. Sethi, and G. Gutierrez. 2007. A survey of Stackelberg differential game models in supply and marketing channels. J. Syst. Sci. Syst. Eng., 16, 385 413. [30] M. Hoefer and A. Skopalik. 2013. Altruism in atomic congestion games. ACM Trans. Econ. Comput., 1, 4, 1 21. doi: 10.1145/2542174.25 42177. [31] S. Ieong, R. Mc Grew, E. Nudelman, Y. Shoham, and Q. Sun. 2005. Fast and compact: a simple class of congestion games. In Proc. 20th Natl. Conf. Artificial Intelligence and the 17th Innovative Appl. Artificial Intelligence Conf. 489 494. [32] A. X. Jiang, H. Chan, and K. Leyton-Brown. 2017. Resource graph games: A compact representation for games with structured strategy spaces. In Proc. 31st Conf. Artif. Intell. (AAAI), 572 578. [33] R. Johari, G. Y. Weintraub, and B. Van Roy. 2010. Investment and market structure in industries with congestion. Oper. Res., 58, 5, 1303 1317. [34] C. Kiekintveld, M. Jain, J. Tsai, J. Pita, F. Ordóñez, and M. Tambe. 2009. Computing optimal randomized resource allocations for massive security games. In Proc. 8th Internat. Conf. Autonomous Agents and Multiagent Systems (AAMAS), 689 696. [35] D. Korzhyk, Z. Yin, C. Kiekintveld, V. Conitzer, and M. Tambe. 2011. Stackelberg vs. Nash in security games: an extended investigation of interchangeability, equivalence, and uniqueness. J. Artificial Intelligence Res., 41, 297 327. [36] A. A. Kulkarni and U. V. Shanbhag. 2015. An existence result for hierarchical Stackelberg v/s Stackelberg games. IEEE Trans. Autom. Control., 60, 12, 3379 3384. [37] M. Labbé and A. Violin. 2016. Bilevel programming and price setting problems. Ann. Oper. Res., 240, 1, 141 169. [38] A. Laszka, J. Lou, and Y. Vorobeychik. 2016. Multi-defender strategic filtering against spear-phishing attacks. In Proc. 30th Conf. Artif. Intell. (AAAI), 537 543. [39] S. Leyffer and T. Munson. 2010. Solving multi-leader-common-follower games. Optim. Methods Softw., 25, 4, 601 623. [40] K. Leyton-Brown and M. Tennenholtz. 2003. Local-effect games. In Proc. 18th Internat. Joint Conf. Artif. Intell. (IJCAI), 772 780. [41] Y. Li, Y. Jia, H. Tan, R. Wang, Z. Han, and F. C. M. Lau. 2017. Congestion game with agent and resource failures. IEEE J. Sel. Areas Commun., 35, 3, 764 778. [42] T.-L. Liu, J. Chen, and H.-J. Huang. 2011. Existence and efficiency of oligopoly equilibrium under toll and capacity competition. Transp. Res. E: Logist. Transp. Rev., 47, 6, 908 919. [43] J. Lou, A. M. Smith, and Y. Vorobeychik. 2017. Multidefender security games. IEEE Intell. Syst., 32, 1, 50 60. [44] A. Marchesi, M. Castiglioni, and N. Gatti. 2019. Leadership in congestion games: multiple user classes and non-singleton actions. In Proc. 28th Internat. Joint Conf. Artif. Intell. (IJCAI), 485 491. [45] P. Marcotte. 1986. Network design problem with congestion effects: a case of bilevel programming. Math. Program., Ser. A, 34, 142 162. [46] R. Meir, M. Tennenholtz, Y. Bachrach, and P. B. Key. 2012. Congestion games with agent failures. In Proc. 26th Conf. Artif. Intell. (AAAI), 1401 1407. [47] I. Milchtaich. 1996. Congestion games with player-specific payoff functions. Games Econom. Behav., 13, 1, 111 124. [48] J. Nickerl and J. Torán. 2023. Pure Nash equilibria in a generalization of congestion games allowing resource failures. Theoret. Comput. Sci., 963, 113933. doi: https://doi.org/10.1016/j.tcs.2023.113933. [49] M. J. Osborne and A. Rubinstein. 1994. A Course in Game Theory. MIT Press. [50] J. Oxley. 2011. Matroid Theory. Oxford University Press.

Journal of Artificial Intelligence Research, Vol. 83, Article 29. Publication date: August 2025.

29:34 Harks, Henle, Klimm, Matuschke & Schedel

[51] M. Penn, M. Polukarov, and M. Tennenholtz. 2011. Congestion games with failures. Discrete Appl. Math., 159, 15, 1508 1525. doi: https://doi.org/10.1016/j.dam.2011.01.019. [52] M. Penn, M. Polukarov, and M. Tennenholtz. 2009. Congestion games with load-dependent failures: identical resources. Games Econom. Behav., 67, 1, 156 173. doi: https://doi.org/10.1016/j.geb.2009.03.004. [53] M. Penn, M. Polukarov, and M. Tennenholtz. 2009. Taxed congestion games with failures. Ann. Math. Artif. Intell., 56, 133 151. doi: https://doi.org/10.1007/s10472-009-9164-3. [54] R. W. Rosenthal. 1973. A class of games possessing pure-strategy Nash equilibria. Internat. J. Game Theory, 2, 1, 65 67. [55] A. Sinha, F. Fang, B. An, C. Kiekintveld, and M. Tambe. 2018. Stackelberg security games: looking beyond a decade of success. In Proc. 27th Internat. Joint Conf. Artif. Intell. (IJCAI), 5494 5501. [56] B. Vöcking. 2006. Congestion games: optimization in competition. In Algorithms and Complexity in Durham 2006 - Proceedings of the Second ACi D Workshop, 9 20. [57] J. Wang, K. Jiang, and Y. Wu. 2022. On congestion games with player-specific costs and resource failures. Automatica, 142, 110367. doi: https://doi.org/10.1016/j.automatica.2022.110367. [58] J. G. Wardrop. 1952. Some theoretical aspects of road traffic research. Proc. Inst. Civil Engineers, 1, Part II, 325 378. [59] A. Wilczynski, A. Jakobik, and J. Kolodziej. 2016. Stackelberg security games: models, applications and computational aspects. Journal of Telecommunications and Information Technology, 3, 70 79. [60] L. Xia and V. Conitzer. 2010. Stackelberg voting games: computational aspects and paradoxes. In Proc. 24th Conf. Artif. Intell. (AAAI), 921 926. [61] H. Yang and H.-J. Huang. 2004. The multi-class, multi-criteria traffic network equilibrium and systems optimum problem. Transportation Res., 38, B, 1 15.

Received 18 July 2024; accepted 1 July 2025

Journal of Artificial Intelligence Research, Vol. 83, Article 29. Publication date: August 2025.