# multileader_congestion_games_with_an_adversary__7af7182c.pdf Multi-Leader Congestion Games with an Adversary Tobias Harks1, Mona Henle2, Max Klimm3, Jannik Matuschke4, Anja Schedel1 1 University of Augsburg, 86159 Augsburg, Germany 2 University of Applied Sciences Augsburg, 86161 Augsburg, Germany 3 TU Berlin, 10623 Berlin, Germany 4 KU Leuven, 3000 Leuven, Belgium tobias.harks@math.uni-augsburg.de, mona.henle@hs-augsburg.de, klimm@math.tu-berlin.de, jannik.matuschke@kuleuven.be, anja.schedel@math.uni-augsburg.de We study a multi-leader single-follower congestion game where multiple users (leaders) choose one resource out of a set of resources and, after observing the realized loads, an adversary (single-follower) attacks the resources with maximum loads, causing additional costs for the leaders. For the resulting strategic game among the leaders, we show that pure Nash equilibria may fail to exist and therefore, we consider approximate equilibria instead. As our first main result, we show that the existence of a K-approximate equilibrium can always be guaranteed, where K 1.1974 is the unique solution of a cubic polynomial equation. To this end, we give a polynomial time combinatorial algorithm which computes a K-approximate equilibrium. The factor K is tight, meaning that there is an instance that does not admit an α-approximate equilibrium for any α < K. Thus α = K is the smallest possible value of α such that the existence of an α-approximate equilibrium can be guaranteed for any instance of the considered game. Secondly, we focus on approximate equilibria of a given fixed instance. We show how to compute efficiently a best approximate equilibrium, that is, with smallest possible α among all α-approximate equilibria of the given instance. 1 Introduction Hierarchical leader-follower games have received considerable attention in the artificial intelligence community, especially, because several real-world applications related to the protection of vulnerable systems can be modeled within this framework. Applications include the security domain (Kiekintveld et al. 2009; Marchesi, Castiglioni, and Gatti 2019; Sinha et al. 2018; Gan, Elkind, and Wooldridge 2018), where a leader aims at protecting a set of valuable targets and moves first by applying a defender strategy such as controls or fortification of resources. The adversary acts as a follower and, after observing the leader s defensive strategy, chooses a strategy incurring maximum damage. The leader anticipates the followers strategy. Thus, the computation of the defender strategy takes the follower reaction into account. While most works in this literature consider the case of a single leader, the case of multiple leaders playing a simultaneous-move strategic game subject to one or more followers has received much less attention and only very few Copyright 2022, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. 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 operator are the followers; see Leyffer and Munson (2010) and references therein. Also in the security domain related to transport and communication networks, there are usually multiple leaders that compete over the network resources subject to a followers response; see Kulkarni and Shanbhag (2015). 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; see Kulkarni and Shanbhag (2015). In this paper, we consider a class of multi-leader singlefollower games on discrete strategy spaces that are motivated by security applications with congestion effects. Consider a standard singleton congestion game where multiple users (leaders) choose one resource out of a set of resources. After observing the realized loads, an adversary (singlefollower) attacks the resources with maximum loads, causing additional disutilities for the users on the attacked resources. The adversary may be thought of as either being a malicious player attacking the resources in order to maximize the caused damage or as controls by a central authority to counter tax or fare evasion; see Correa et al. (2017) for a related mathematical model of fare evasion without any congestion or load balancing effects. In both applications it is sensible to assume that the adversary has limited resources, modeled by a fixed budget for his interventions that can be distributed freely on the resources, and that he acts rationally, investing the budget only on resources with maximum load. The users anticipate this strategy. From their perspective, every maximum-load resource is equally likely under attack, that is, they assume the budget to be spent evenly among the resources with maximum load (this can be interpreted as a randomized strategy of the adversary choosing the uniform distribution over maximum-load resources). For the users, the additional cost term corresponds to the expected additional damage cost due to an attack. This fundamental model has, to the best of our knowl- The Thirty-Sixth AAAI Conference on Artificial Intelligence (AAAI-22) edge, not been analyzed before and we investigate the existence and computation of (approximate) pure Nash equilibria of this multi-leader single-follower game. 1.1 Our Results and Proof Techniques We first observe that pure Nash equilibria do not always exist in the introduced game, not even for linear congestion costs. This motivates the analysis of approximate pure Nash equilibria, where no unilateral deviation improves the cost of the deviating leader by more than a factor α, for some α 1 (the adversary is still assumed to act optimally.) We analyze existence and efficient computation of approximate equilibria for the introduced game with linear congestion costs. As our first main result, we show that α = K 1.1974 is the smallest possible value of α such that the existence of an α-approximate pure Nash equilibrium can always be guaranteed (K is the unique solution of some cubic polynomial equation). For the proof, we give an efficient algorithm which computes a K-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 α = K, showing existence of K-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 (Milchtaich 1996; Ackermann, R oglin, and V ocking 2009), 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 pure Nash equilibrium for any α < K. This shows that α = K 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 single given instance, better approximate equilibria might exist, that is, there may be α-approximate equilibria with α < K. We show how to compute efficiently, for a given instance, a best approximate equilibrium, that is, an α-approximate equilibrium for the smallest value of α for which such an 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, from which an optimal approximate equilibrium can then be found using a simple linear program. We provide a formal definition of the model in Section 2. In Sections 3 and 4, respectively, we describe the two algorithms and sketch the proofs of the corresponding results. The complete proofs can be found in the full version of this article (Harks et al. 2021). 1.2 Related Work The game that we analyze in this paper constitutes a Stackelberg game with multiple leaders and a single follower. The leaders game is a singleton congestion game and we assume symmetric strategies, meaning that all leaders have the same strategy space. Stackelberg games with an underlying congestion game for (a subset of) the players have received considerable attention in the literature. Castiglioni et al. (2019) and Marchesi, Castiglioni, and Gatti (2019) consider a game with a single leader and multiple followers where all players participate in a congestion game (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 exact 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 (Castiglioni et al. 2019), or the followers can be divided in classes having the same strategies (Marchesi, Castiglioni, and Gatti 2019). There are several works analyzing hierarchical situations with a subsequent nonatomic network routing game, where a set of infinitesimally small players chooses paths in a network, and each player aims to minimize the (loaddependent) length of her chosen path leading to a Wardrop equilibrium (Wardrop 1952). For works analyzing situations where a single leader determines capacities or prices in order to reduce the total congestion (plus investments for the case of capacities) of the Wardrop equilibria in a subsequent network routing game, we refer to Marcotte (1986); Gairing, Harks, and Klimm (2017) for setting capacities, and Beckmann, Mc Guire, and Winsten (1956) and Yang and Huang (2004) for setting prices. Labb e, Marcotte, and Savard (1998) study a model where a single leader sets prices in order to maximize her profit in a subsequent network routing game (but without congestion effects). Correa et al. (2018) and Harks, Schr oder, and Vermeulen (2019) 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 threelevel 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, e.g., analyzed by Johari, Weintraub, and Van Roy (2010), Liu, Chen, and Huang (2011), and Harks and Schedel (2019). Regarding the computation of approximate equilibria in atomic congestion games, we refer to Caragiannis et al. (2011, 2015). Finally, we also mention here congestion games with an adversarial structure such as agent or resource failures, see Bil o, Moscardelli, and Vinci (2018); Meir et al. (2012); Li et al. (2017) or games with malicious players (Babaioff, Kleinberg, and Papadimitriou 2009). load profile deviation (of some player using r to r , notation r r ) resulting cost improvement (5, 0, 0) r1 r2 5ar1 + B = 6 > 2 = ar2 (4, 1, 0) r1 r2 4ar1 + B = 6 > 4 = 2ar2 (3, 2, 0) r1 r3 3ar1 + B = 6 > 5 = ar3 (3, 1, 1) r3 r2 ar3 = 5 > 4 = 2ar2 (2, 2, 1) r2 r1 2ar2 + B/2 = 7 > 6 = 3ar1 + B Table 1: Improving deviations for the candidate profiles for the game in Example 1. 2 The Model For an integer k Z 0, let [k] := {1, . . . , k}. Let N = [n] be a finite set of players (leaders) and R = {r1, . . . , rm} be a finite set of m resources. For each player i, the set of strategies available to player i is Xi = R. We call x = (x1, . . . , xn) with xi Xi for all i N a strategy profile, and X = X1 Xn the strategy space. We use standard game theory notation; for a strategy profile x X, we write x = (xi, x i) meaning that xi is the strategy that player i plays in x and x i is the partial strategy of all players except i. Every strategy profile x = (x1, . . . , xn) X induces a load or congestion on the resources given by ℓr(x) := |{i N | xi = r}|, r R. We are further given linear cost functions arℓr(x), r R with nonnegative coefficients ar 0. In classical congestion games, the private cost of player i under strategy profile x X is defined as πi(x) = axiℓxi(x). Now we model the actions of an adversary (follower) after the leaders have chosen their joint strategy profile x X. Formally, given x X the adversary solves r R ℓr(x)κr s.t.: X r R κr B, κ 0. (LP) The linear program (LP) has the interpretation that the adversary has a budget of B > 0 that can be freely distributed among the resources. For each unit of budget spent on a resource, the adversary receives a utility equal to the number of players on that resource since any interaction with a leader on a resource is equally beneficial for the follower. Thus, the adversary strategically selects those resources that are used by the maximum number of players in order to maximize the caused damage. It is not hard to see that these are precisely the optimal solutions to (LP). While (LP) may have multiple optimal solutions, a reasonable selection among the optimal solutions is the following, where we use the notation M(x) := maxr R{ℓr(x)} together with M 1(x) := arg maxr R{ℓr(x)}: ( B |M 1(x)|, if r M 1(x), 0, else. (1) Clearly, κ r(x) is an optimal solution to (LP) and has the intuitive interpretation that, assuming that every maximumload resource is equally likely to be under attack by the adversary, from the perspective of the players it represents the expected additional resource cost due to an attack. The multi-leader congestion game with an adversary can be defined as the game G = (N, X, B, π) in strategic form, where πi(x) := axiℓxi(x) + κ xi(x). (2) We furthermore define cr(x) := arℓr(x) + κ r(x) (3) for all r R (this is useful in case we do not want to consider a specific player using r). A strategy profile x X is called a pure Nash equilibrium (PNE) of G if for all i N: πi(x) πi(yi, x i) for all yi Xi. Let us give an example of a multi-leader congestion game with an adversary showing that pure Nash equilibria need not exist in general. Example 1. Consider the game with m = 3 resources, n = 5 players, budget B = 6 and resource cost coefficients ar1 = 0, ar2 = 2, and ar3 = 5. We proceed to show that this game has no pure Nash equilibrium. To this end, we show for each strategy profile x that there exists a player who can decrease her cost by a unilateral deviation from x. Since the players are symmetric, it suffices to analyze all load profiles (ℓr1(x), ℓr2(x), ℓr3(x)), that is, all vectors (ℓr1, ℓr2, ℓr3) N3 with ℓr1 +ℓr2 +ℓr3 = n = 5. Since ar1 < ar2 < ar3, the only candidates for a PNE are those strategy profiles x with ℓr1(x) ℓr2(x) ℓr3(x). Thus, 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) and (2, 2, 1). Table 1 provides an improving deviation for each of these candidate profiles, showing that the game has no PNE. This example motivates the analysis of approximate equilibria defined as follows. Definition 2. A strategy profile x X is an α-approximate pure Nash equilibrium (α-PNE) of G for some α 1, if for all i N: πi(x) α πi(yi, x i) for all yi Xi. A unilateral deviation which decreases the cost of the deviating player more than a factor α is called an α-improving deviation, or an α-improving move. For α = 1, we obtain the standard 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 scaleinvariance of the games studied in this article; see the full version of this article for details. Algorithm 1: Computation of an α-approximate PNE. Input: Player set N = [n], resource set R = {r1, . . . , rm}, resource cost coefficients 0 a1 am, and α 1. Output: α-approximate pure Nash equilibrium x. 1 x (0, 0, . . . , 0); 2 for k = 1, 2, . . . , n do 3 k min{i [m] : cri(x k, ri) cr(x k, r) r R}; 5 while Wα(x) := {i N : xi = 0 and cxi(x) > α cr(x i, r) for a resource r R} = do 6 Rα(x) {r R : xi = r for some i Wα(x)}; 7 i max{j [m] : rj Rα(x) and crj(x) cr(x) r Rα(x)}; 8 i some player with xi = ri ; 9 i+ min{j [m] : crj(x i, rj) cr(x i, r) r R}; 3 Computing K-approximate PNE In this section, we analyze approximate PNE of the introduced multi-leader congestion games with an adversary. As Example 1 shows, existence of (exact) PNE can not be guaranteed for these games. We show that α = K 1.1974 is the smallest possible α such that the existence of an α-PNE can be guaranteed for any instance, where is the unique solution of the equation x3 + x2/2 + 1 = 0. To this end, we provide Algorithm 1 which efficiently computes a K-approximate PNE (see Theorem 3). This result is complemented by an instance where no α-approximate PNE with α < K exists (see Theorem 6). As an easy consequence of the proof, we also get that exact PNE are guaranteed to exist if n 4 or m 2 (see Corollary 5). 3.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, etc. Note that this approach has been used before to compute exact PNE, for example for player-specific costs or weighted congestion games on matroids (Milchtaich 1996; Ackermann, R oglin, and V ocking 2009). 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. For the formal description of our algorithm see Algorithm 1. We assume that the resource set R = {r1, . . . , rm} is ordered such that a1 am (where aj := arj). 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 x (R {0})n, where xi = 0 means that player i has not yet been added to the game. Given such a vector x = 0, the cost cxi(x) incurred to player i with xi = 0 is defined as the cost which is experienced by her in the game where only the players j with xj = 0 are present. Now define, for a strategy profile x (R {0})n, the following set of players Wα(x) who are unhappy with their strategy, meaning that they have an α-improving move: Wα(x) := {i N : xi = 0 and cxi(x) > α cr(x i, r) for a resource r R}. In each iteration of the for-loop in line 2 of Algorithm 1, a new player k is added to the game. We place k on a best response (with respect to the strategies of the players {1, . . . , k 1} already added to the game). If there is more than one best response, we choose the one with smallest index, see lines 3 and 4. After having added player k, it may be the case that some players are not happy with their strategy, that is, Wα(x) = , where x denotes the current strategy profile. In the while-loop starting in line 5, we iteratively choose a player who is maximally unhappy , meaning that she experiences maximum cost among all unhappy players, and let her deviate to a best response, until all players in {1, . . . , k} 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, and if there is more than one best response, we choose the one with smallest index (see lines 7, 8 and 9). After this, we return to line 2 where the next player k + 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 α = K. 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 a1 a2 am, ensure that the loads are always decreasing along the resources, that is, ℓr1(x) ℓr2(x) ℓrm(x) always holds during the algorithm. An illustrating example for the application of Algorithm 1 can be found in the full version. 3.2 Termination of Algorithm 1 for α = K In this subsection, we outline the analysis that reveals that Algorithm 1 terminates for α = K, and thus computes a K-approximate PNE. We also show that the running time of Algorithm 1 can be bounded by min{O(n2m), O(nm2)}. The complete analysis can be found in the full version. We need to prove that the while-loop terminates in each iteration k {1, . . . , n} of the for-loop. For k = 1, the while-loop obviously terminates since we only have one player, and she is placed on the best response r1. Therefore, WK(x) = WK(r1, 0, . . . , 0) = and the while-loop terminates without changing anything. For k = 2, the second player is placed on r1 if 2a1 + B a2 + B/2, and is placed on r2 otherwise. It is easy to see that in both cases, both players are happy and the while-loop immediately terminates. For iteration k 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 k 3. Note that since the while-loop terminated in iteration k 1, the players in {1, . . . , k 1} were happy before the next player k was added to the game. That is, with respect to the profile x directly before player k is added, no player i {1, . . . , k 1} has a K-improving deviation, i.e., an alternative resource r with cxi(x) > K cr(x i, r). But it may be the case that some players are unhappy after the addition of player k. Additionally, the deviation of one of these players 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, . . . , k} are happy again. We thus need to keep track of the set of unhappy players during the course of the while-loop. To this end, we derive necessary properties for players who either become unhappy due to the addition of player k, or due to the subsequent deviation of some other player during the while-loop. The derived properties are primarily depend on the loads, e.g., conditions on the load of an unhappy player i s current strategy xi, and on the load of a corresponding K-improving deviation r. Combining these properties with further structural insights, we then proceed by a careful case distinction regarding the sequence of deviating players in iteration k, and show that this sequence terminates in all cases. Let us now briefly sketch the mentioned case distinction. Let x and x denote the profiles directly before and after the new player k is added. If all players are happy with their strategy in x , the statement follows; thus assume that player i changes from x i = xi to r in the while-loop. The conditions on the resource loads mentioned above imply that there are three possible cases regarding the load of player k s current strategy x k. Namely, the load ℓx k(x) of x k (before player k is added) needs to be in {M 2, M 1, M}, where M := M(x) denotes the maximum load with respect to x. We then analyze all three cases. As it turns out, the cases ℓx k(x) = M 2 and ℓx k(x) = M 1 are very simple, whereas ℓx k(x) = M is more complicated and requires further subcases. However, by repeated application of the aforementioned conditions, we can show termination of the while-loop also for this case. At the end of this proof sketch, we want to briefly indicate Figure 1: A cycling sequence of deviations which might occur during the while-loop of Algorithm 1: First, some player moves from r3 to r2, then another player changes her strategy from r1 to r3, and finally, a player using r2 moves to r1. the role of the constant K. To this end, consider Figure 1 which shows a simplified version of a subcase occurring in the proof. In particular, the displayed sequence of deviations might occur during the while-loop of the algorithm, and this implies that the following three inequalities need to hold: a3 > α 2a2 3a1 + B > α a3 2a2 +B/2 > α (3a1 + B) From this, one can derive (1+α2/2 α3)B > (α3 1)3a1, which yields a contradiction for α = K and any a1 0, as the left-hand side is equal to 0, whereas the right-hand side is non-negative. Thus, cycles of this form cannot occur during the algorithm for α = K, independent of the budget and the cost coefficients. Ruling out several other special cases of cyclic behavior, we derive the following theorem. Theorem 3. For α = K, where K = 1/6 (1 + 330) 1.1974 is the unique solution of the equation x3 + x2/2 + 1 = 0, Algorithm 1 computes a K-approximate PNE. The proof of Theorem 3 also yields the following upper bound on the running time of Algorithm 1. Corollary 4. For α = K, the running time of Algorithm 1 can be bounded by min{O(n2m), O(nm2)}. Proof. First note that each iteration of the while-loop can be implemented in O(m) (note that although the cost of deviating to a resource r is in general player-specific, since it depends on the load of the deviating player s current resource, it can in fact only be different for two players if one of these players is using a resource with maximum load, and the other not). Furthermore, in the kth iteration of the forloop, we can bound the number of iterations of the whileloop either by O(m), or alternatively by 2k since one can show that no player moves more than twice. Since there are n iterations of the for-loop, we get min{O(n2), O(nm)} as an upper bound for the total number of iterations, implying the desired bound on the total running time. The proof of Theorem 3 also reveals that n 5 and m 3 need to hold for any instance which has no exact PNE. This follows from the fact that the case displayed in Figure 1 essentially is the only situation where the whileloop might not terminate for α = 1, and this case requires load profile α-improving deviation (of some player using r to r , notation r r ) conditions on α (5, 0, 0) r1 r2 5a1 + B > αa2 α < 1/a2 = 2 K 1/2 2.86 (4, 1, 0) r1 r2 4a1 + B > α2a2 α < 1/(2a2) = 1 K 1/2 1.43 (3, 2, 0) r1 r3 3a1 + B > αa3 α < 1/a3 = K (3, 1, 1) r3 r2 a3 > α2a2 α < 1 K(K 1/2) = K (2, 2, 1) r2 r1 2a2 + B/2 > α(3a1 + B) α < 2a2 + 1/2 = K Table 2: α-improving deviations for the candidate profiles. at least five players and at least three resources. Thus we get the following corollary. Corollary 5. Exact PNE always exist if n 4 or m 2. 3.3 Tightness of α = K In this subsection, we provide an instance where no αapproximate PNE with α < K exists, showing that α = K is the smallest possible value such that the existence of an α-approximate equilibrium can be guaranteed. Theorem 6. There exists an instance with three resources and five players such that there is no α-approximate PNE for any α < K, where K 1.1974 is as specified in (4). Proof. Consider the instance with m = 3 resources, n = 5 players, budget B = 1, and resource cost coefficients a1 := ar1 = 0, a2 := ar2 = K/2 1/4 0.3487, and a3 := ar3 = 1/K 0.8351. We proceed to show that there is no α-approximate PNE for α < K. To this end, note that it suffices to show that there is no α-approximate PNE among the five load profiles (5, 0, 0), (4, 1, 0), (3, 2, 0), (3, 1, 1), (2, 2, 1) (since a1 < a2 < a3; it can be shown that if there exists an αapproximate PNE, there is also one with corresponding load profile among the five listed load profiles). Let α < K. We show that for any of the five load profiles, there exists an α-improving deviation, showing the claim. To this end, consider Table 2, 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 α < K. 4 Computing Optimal Approximate Equilibria In the last section, we showed that α = K is the smallest possible value for α such that the existence of an αapproximate PNE can be guaranteed for any instance of a multi-leader congestion game with an adversary. However, there are clearly instances where α-PNE with α < K 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 R = [m] and a1 am. We can restrict our attention to strategy profiles x with decreasing loads, that is, with ℓ1(x) ℓm(x), since it can be shown that if an α-PNE exists, there also exists one with decreasing loads. Also note that we can assume α [1, K] since we want to find the smallest possible α. Thus, let x be a strategy profile with ℓ1(x) ℓm(x). Note that, clearly, M(x) = max{ℓr(x) : r R} n m holds. Furthermore, if M(x)m = n (which is equivalent to ℓr(x) = M(x) for all r R), x is an α-PNE if and only if am M(x) + B/m α(a1 (M(x) + 1) + B) holds. Thus we can assume in the following that there are resources with load < M(x). We denote by k = k(x) < m the largest resource having maximum load M = M(x). Similarly, k = k (x) denotes the smallest resource with load strictly smaller than M 1, and k = k (x) denotes the smallest resource with load strictly smaller than M 2. In other words, ℓr(x) = M for all r {1, . . . , k}, ℓr(x) = M 1 for all r {k+1, . . . , k 1}, ℓr(x) = M 2 for all r {k , . . . , k 1}, and ℓr(x) M 3 for all r {k , . . . , m}, see Figure 2 for illustration. Note that k = k + 1 or k = k are possible, in which case there are no resources with load M 1 or M 2, respectively. We now define the following values c M = c M(x) and c k, and (5) ak M + B/k α c M. (6) Figure 2: Illustration for the definition of k, k and k . Regarding this, note that there are some cases in which c M or c k, then c