Pessimistic Leader-Follower Equilibria with Multiple Followers

1 Introduction

In recent years, Leader-Follower (or Stackelberg) Games (LFG) and their corresponding Equilibria (LFE) have attracted a growing interest in Artificial Intelligence. Considering, for simplicity, the two-player case, LFGs describe situations where one player (leader) commits to a strategy and the other player (follower) first observes the leader's commitment and, then, decides how to play. This is the case of, e.g., security games, where a defender (leader) is tasked to allocate scarce resources to protect valuable targets from an attacker (follower). See [Paruchuri et al., 2008; Kiekintveld et al., 2009; An et al., 2011] for real-world applications of such games. Outside the security domain, applications can be found in, e.g., interdiction games [Caprara et al., 2016; Matuschke et al., 2017], toll-setting problems [Labb´e and Violin, 2016], and network routing [Amaldi et al., 2013].

While the majority of the game theoretical investigations on computing LFE have focused on the single-follower case, in this work we address the multi-follower scenario. When facing a multi-follower LFG, two aspects need to be considered: what game the followers play and, in it, how ties among multiple equilibria are broken. As to the type of game, the followers may play, e.g., hierarchically one at

Nicola Gatti and Alberto Marchesi

Politecnico di Milano Piazza Leonardo da Vinci, 32 Milano, Italy

{nicola.gatti, alberto.marchesi}@polimi.it

a time [Conitzer and Sandholm, 2006], simultaneously in a correlated manner [Conitzer and Korzhyk, 2011], or simultaneously and noncooperatively [Basilico et al., 2016; 2017]. As to breaking ties, two cases are possible: the optimistic one, where an equilibrium maximizing the leader's utility is chosen, and the pessimistic case, where the followers select an equilibrium which minimizes the leader's utility. While, in the optimistic case, a LFE always exists, in the pessimistic setting it may not exist, since the leader's utility function may admit a supremum but not a maximum [von Stengel and Zamir, 2010].

We focus on multi-follower LFGs in normal-form where the followers play simultaneously and noncooperatively, reaching a Nash equilibrium. We refer to the corresponding equilibrium as Leader-Follower Nash Equilibrium (LFNE).

Related Work. In single-follower games (n = 2 players), the follower's best-response to the leader's commitment is always (disregarding degenerate cases) a pure strategy. In the optimistic case, a LFE is found in polynomial time by solving a Linear Programming (LP) problem for each action of the follower [Conitzer and Sandholm, 2006]. Although the pessimistic case is more involved, it can still be solved with similar techniques [von Stengel and Zamir, 2010].

In the multi-follower case (n ≥ 3), see [Basilico et al., 2016; 2017], the problem is NP-hard and inapproximable, in poly-time, to within any polynomial factor unless P = NP. While the optimistic version can be solved to global optimality with global optimization techniques up to a finite precision [Basilico et al., 2016; 2017], no exact algorithms are known for the pessimistic case, though some heuristic algorithms are proposed in [Basilico et al., 2017]. When the followers are restricted to pure strategies though, the optimistic problem is in P, as discussed in the next section.

Original Contributions. We address the pessimistic multifollower case, with followers playing pure strategies. This is the case of many applications such as potential games [Monderer and Shapley, 1996], congestion games [Rosenthal, 1973], and toll-setting problems [Labb´e and Violin, 2016].

Differently from the optimistic/pessimistic case with a single follower and the optimistic case with many followers, which are all in P, we show that computing a LFNE in the pessimistic case (P-LFNE) with at least two followers playing pure strategies is NP-hard. This problem is crucial, as the difference in leader's utility between an optimistic LFE

and a pessimistic one can be arbitrarily large, as we show in Section 2. We then propose an exact exponential-time algorithm (a multi-lex-MILP) for computing a P-LFNE and, then, extend it to a branch-and-bound algorithm.

The status, in terms of complexity and known algorithms, of the problem of computing a LFNE, updated with the original results provided in this paper (reported in bold), is:

2 ProblemDefinition

Let N = {1, . . . , n} be the set of players and, for each p ∈ N, let Ap be the corresponding set of actions, with mp = |Ap|. For each player p ∈ N, let xp ∈ [0, 1]mp , with ∑a∈Ap xap = 1, be her strategy vector (or strategy, for short), where each component xap represents the probability that action a ∈ Ap is played. For each p ∈ N, let also ∆p = {xp ∈ [0, 1]mp : ∑a∈Ap xap = 1} be the set of her strategies, called strategy space. A strategy is called pure when only one action is played with positive probability, and mixed otherwise. We denote the collection of strategies of the different players, or strategy profile, by x = (x1, . . . , xn). When all strategies are pure, we denote the collection of actions played by the players, or action profile, by a = (a1, . . . , an).

Consider a normal-form game [Shoham and LeytonBrown, 2008] where Up ∈ Qm1×...×mn represents, for each player p ∈ N, her (multidimensional) utility (or payoff) matrix. Each of its components U a1,...,an p corresponds to the utility obtained by player p when all the players play actions a1, . . . , an. For a strategy profile x, the expected utility of player p ∈ N is the nth-degree polynomial ∑a1∈A1 . . . ∑an∈An U a1,...,an p xa1 1 . . . xan n .

An action profile a = (a1, . . . , an) is called a pure Nash Equilibrium (NE) if U a1,...,an p ≥ U a′1 ,...,a′n p for each player p ∈ N and action profile a′ such that, for all q ∈ N \ {p}, a′q = aq and, possibly, a′p ̸= ap. This implies that, for each p ∈ N, if the players in N \ {p} play as the equilibrium prescribes, player p cannot improve her utility by deviating from the equilibrium and playing some other action a′p ̸= ap. More generally, a mixed NE is a strategy profile x = (x1, . . . , xn) such that no player p ∈ N can improve her utility playing a strategy x′p ̸= xp, assuming the others play as the equilibrium prescribes. Observe that, in a normal-form game, a mixed NE always exists [Nash, 1951], while a pure NE may not.s

In this paper, we are concerned with the computation of an equilibrium in a normal-form game where the followers, after observing the leader's commitment to a mixed strategy, play a pure NE in the resulting game, so as to minimize the leader's utility. We refer to it as Pessimistic Leader-Follower Nash Equilibrium (P-LFNE). For the sake of presentation, we consider the case of two followers (thus, with n = 3), where the nth player (player 3) takes on the role of leader. We also assume, w.l.o.g., m1 = m2 = m3 = m. Our results can be easily generalized to the case of any n > 3.

Computing a P-LFNE amounts to solving the following bilevel problem:

For any x3 ∈ ∆3 determined in the first level, the second level calls for a pair of followers' actions (i∗ , j ∗ ) forming a pure NE in the followers' game induced by x3 which minimizes the leader's utility. Notice that, by definition, (i∗ , j ∗ ) is a NE for the given x3 if and only if i∗ maximizes the utility of follower 1 when assuming that follower 2 would play j ∗ , and j ∗ maximizes the utility of follower 2 when assuming that follower 1 would play i∗ .

In the following, we write the above problem as supx3∈∆3 f(x3), where f is the leader's utility in the pessimistic case. At any x3 where the followers' game does not admit a pure NE we define f(x3) = -∞. Even if supx3∈∆3 f(x3) < ∞ due to the boundedness of f, f may not admit a maximum and, thus, the game may not admit a P-LFNE [von Stengel and Zamir, 2010].

The optimistic version of the problem (i.e., the O-LFNE finding problem), obtained by changing the second level objective from min to max, can be solved in polynomial time. This is because the formulation in [Basilico et al., 2016] becomes an LP when the followers' pure strategies are given, and the set of pure strategies of a normal-form game can be enumerated in polynomial time. Note that a P-LFNE cannot be obtained by just perturbing the leader's strategy in an OLFNE, as shown in Figure 1.

3 Computational Complexity

In this section, we show that computing a P-LFNE is NPhard. In decision form, the problem reads:

Definition 1 (P-LFNE-d). Given a normal-form game with n ≥ 3 players and a finite number K, is there a P-LFNE where the leader achieves a utility ≥ K?

We show the hardness of the P-LFNE searching problem by a polynomial-time reduction of IND-SET, one of Karp's original 21 NP-complete problems [Karp, 1972], to P-LFNEd. In decision form, IND-SET reads:

Definition 2 (IND-SET). Given an undirected graph G = (V,E) and a finite J with J ≤ |V |, does G contain an independent set (a subset of vertices V ′ ⊆ V : ∀u, v ∈ V ′ , {u, v} /∈ E) of size ≥ J?

Before presenting our reduction, we introduce the following class of normal-form games:

Definition 3. Given two reals b and c, with 1 > c > b > 0, and an integer m ≥ 1, let Γcb (m) be a class of normal-form games with three players (n = 3), the first two having m+ 1 actions each, with action sets A1 = A2 = A = {1, ..., m, f}, and the third one having m actions, with action set A3 = A \ {f}. For every third player's action k ∈ A \ {f}, the other players play a game where:

• the payoffs on the main diagonal (where both players play the same action) satisfy U kkk 1 =U kkk 2 =1,U ffk 1 = c, U f f k 2 =b and, ∀i ∈ A \ {k, f}, U iik 1 =U iik 2 =0;
• ∀i, j ∈ A \ {f} with i ̸= j, U ijk 1 =U ijk 2 = b;
• ∀j ∈ A \ {f}, U fjk 1 =c and U fjk 2 =0;
• ∀i ∈ A \ {f}, U ifk 1 =1 and U ifk 2 =0.

No restrictions are imposed on the third player's payoffs.

These games are of interest for the following reason:

Proposition 1. In a Γcb (m) game with c ≤ 1m , for all S ⊆ {(i, i) : i ∈ A \ {f}} with S ̸= ∅ there is a leader's strategy x3 ∈ ∆3 such that the outcomes (i, i) ∈ S are the only pure NE in the resulting followers' game.

Proof. First, observe that the followers' payoffs not on the main diagonal do not depend on the leader's strategy x3. Thus, outcomes (i, j), for any i, j ∈ A \ {f} with i ̸= j, cannot be NE, as the first follower would deviate by playing action f, obtaining a utility c > b. Analogously, outcomes (f, j), with j ∈ A \ {f}, cannot be NE because the second follower would deviate by playing f (since b > 0). The same holds for outcomes (i, f) with i ∈ A \ {f}, since the second follower would be better off playing another action (as b > 0). The last outcome on the diagonal, (f, f), cannot be a NE either, as the first follower would deviate from it (as she would get c in it, while she can obtain 1 > c).

As a result, the only outcomes which can be pure NE are those in {(i, i) : i ∈ A \ {f}}. Clearly, when the leader plays a pure strategy k, the unique pure NE in the followers' game is (k, k) as, due to providing the followers with their maximum payoff, they would not deviate from it. Outcomes (i, i) with i ∈ A \ {f, k} are not NE as, with them, the first follower would get 0 < c. In general, if the leader plays an arbitrary mixed strategy x3 ∈ ∆3, the resulting followers' game is such that the payoffs in (k, k), with k ∈ A \ {f}, are (xk3 , xk3 ). Noticing that (k, k) is an equilibrium if and only if xk3 ≥ c (as, otherwise, the first follower would deviate by playing action f), we conclude that the set of pure NE in the followers' game is S = {(k, k) : xk3 ≥ c}.

In order to guarantee that for every possible S ⊆ {(i, i) : i ∈ A \ {f}} s.t. S ̸= ∅ there is a leader's strategy such that S contains all the pure NE, we must allow the diagonal outcomes to be all (simultaneously) equilibria by properly choosing the value of c. This is done by imposing that, when the leader plays x3 = ( 1m , 1m , ..., 1m ), all outcomes in {(i, i) : i ∈ A \ {f}} are NE, which is obtained by selecting c ≤ 1m .

Notice that, in a Γcb (m) game, the followers' game always admits a pure NE for any leader's commitment x3. See Figure 2 for an example.

Theorem 1. P-LFNE-d is strongly NP-complete even for n = 3.

Proof. Mapping. Given an instance of IND-SET, i.e., an undirected graph G = (V,E) and a positive integer J, we construct Γ(G), a special instance of P-LFNE-d of class Γcb (m), as follows. Assuming an arbitrary labeling of the vertices {v1, v2, ..., vm}, let Γ(G) be an instance of Γcb (m) with c < 1 (m+1)2 < 1m and 0 < b < c < 1, where each action i ∈ A \ {f} is associated with vertex vi. In compliance with Definition 3, in which no constraints are specified for the leader's payoffs, we define:

• for any pair of vertices vi, vj ∈ V , U iij 3 = U jji 3 = - 1c -1 if {vi, vj} ∈ E, and U iij 3 = U jji 3 = 1 otherwise;
• ∀k ∈ A \ {f}, U kkk 3 = 0 and U ffk 3 = 0;
• ∀i ̸= j ∈ A and k ∈ A \ {f}, U ijk 3 = U jik 3 = 0.

Finally, let K = J-1 J . Clearly, this transformation can be performed in time polynomial in the number of vertices m.

If. We show that, if the graph G contains an independent set of size ≥ J, then Γ(G) has a P-LFNE with leader's utility ≥ K. Let V ∗ be an independent set with |V ∗ | = J. Consider the case in which outcomes (i, i), with vi ∈ V ∗ , are the only pure NE in the followers' game, and suppose the leader plays x3 with xk3 = 1 |V ∗ | if vk ∈ V ∗ and xk3 = 0 otherwise. Since U iik 3 = 1 for all k ∈ A \ {f, i}, the leader's utility at any equilibrium (i, i) is:

Only if. We show that, if Γ(G) has a P-LFNE with leader's utility ≥ K, then G has an independent set of size ≥ J. Due to Proposition 1, at any P-LFNE the leader plays a strategy ¯x3 inducing a set of pure NE in the followers' game S∗ = {(k, k) : ¯xk3 ≥ c}. We now show that, in a P-LFNE, the leader never plays two actions i, j ∈ A\{f} with probability

≥ c if {vi, vj} ∈ E. By contradiction, suppose the leader's equilibrium strategy ¯x3 is such that ¯xi3 , ¯xj3 ≥ c. The leader's utility when the followers play the equilibrium (i, i) (the same holds for (j, j)) is:

In the right-hand side, the first term is < 1 (as the leader's payoffs are ≤ 1 and ∑k∈A\{f,i,j} ¯xk3 = 1 - ¯xi3 - ¯xj3 < 1, since ¯xi3 , ¯xj3 ≥ c). The second term is ≤ c(- 1c -1) = -1-c (as ¯xj3 ≥ c), which is < -1. It follows that, since (i, i) (or, equivalently, (j, j)) always provides the leader with a < 0 utility, she would never play ¯x3 in an equilibrium. This is because, by playing a pure strategy, she would obtain a utility of at least zero (as, when she plays a pure strategy, the followers' game admits a unique pure NE giving her a zero payoff). As a result, for any action k such that ¯xk3 ≥ c, we have U kkk 3 = 0, and U iik 3 = 1 for every i such that ¯xi3 ≥ c (since vi and vk are not connected by an edge).

Assume the leader either plays an action with probability ≥ c or she does not play it at all. If this is the case, then the leader's utility at an equilibrium (k, k) ∈ S∗ is 1- ¯xk3 . Since, due to the pessimistic assumption, the leader maximizes her utility in the worst NE, her best choice is to select an ¯x3 such that all NE yield the same utility, that is: ¯xi3 = ¯xj3 for every i, j such that (i, i), (j, j) ∈ S∗ . This results in the leader playing all actions k such that (k, k) ∈ S∗ with the same probability ¯xk3 = 1 |S∗ | , obtaining a utility of |S∗ |-1 |S∗ | = K. Therefore, the vertices {vk : (k, k) ∈ S∗ } must form an independent set of G, whose size is |S∗ | = J.

We now show that the previous assumption always holds, i.e., that in a P-LFNE the leader is not better off playing any action with probability less than c. Indeed, this may not happen in presence of isolated vertices. Assume that vi is isolated and that the leader plays actions A \ {i, f} with probability c- = c - ϵ, for some ϵ > 0, and action i with probability 1 - c-(m- 1). Since the latter is greater than c by definition, the unique NE for the followers is (i, i), providing the leader with a utility of c-(m-1), which approaches m-1 m for c- → 1m . In general, let us denote by ℓ the number of isolated vertices in G, and assume that the other m- ℓ ≥ 2 vertices form a complete graph. This represents the worst case possible as, for it, the leader cannot get a utility larger than ℓ ℓ+1 without playing some actions with probability smaller than c, but, at the same time, she could get more by uniformly playing the ℓ actions associated with the isolated vertices, each with probability α = 1-(m-ℓ)cℓ , while playing with probability c- the other m - ℓ actions. If this is the case, the leader's utility is:

Thus, we require (ℓ-1)+(m-ℓ)cℓ < ℓ ℓ+1 for every ℓ ∈ {1, ...,m- 2}, which implies that c must satisfy: (ℓ+1)(ℓ-1)+(ℓ+1)(m-ℓ)c < ℓ2 ↔ c < 1 (ℓ + 1)(m - ℓ) , in which we upper bounded c- by c. Clearly, c satisfies the condition whenever it is less than the minimum value taken by 1 (ℓ+1)(m-ℓ) for all ℓ. The first order derivative of the bound is (ℓ+1)-(m-ℓ) (ℓ+1)2 (m-ℓ)2 , which vanishes at ℓ = m-1 2 . Given that, according to our definition, c < 1 (m+1)2 < 4 (m+1)2 , we obtain that the leader either plays an action with probability at least c or she never plays such action. The reduction is complete.

NP membership. Since we can verify in polynomial time whether a triple (i, j, x3) is a P-LFNE, we deduce that P-LFNE-d is strongly NP-complete due to IND-SET being strongly NP-complete.

4 Enumerative Algorithm

We propose an exact exponential-time algorithm for the computation of supx3∈∆3 f(x3). If there is no x3 ∈ ∆3 where f(x3) achieves value supx3∈∆3 f(x3) (as f(x3) does not admit a maximum), our algorithm also returns a strategy ˆx3 providing the leader with a utility equal to an α-approximation (in additive sense) of supx3∈∆3 f(x3), for any α > 0.

In the remainder of the paper, we denote the closure of a set X ⊆ ∆3 relative to aff(∆3) by X, its boundary relative to aff(∆3) by ∂X, and its complement relative to ∆3 by Xc . 1

The key ingredient of our algorithm is what we call outcome configurations. We say that, for a given x3 ∈ ∆3, a pair (S+, S-) with S+ ⊆ A1 × A2 and S- = A1 × A2 \ S+ is an outcome configuration if, in the followers' game induced by x3, all pairs of actions (i, j) ∈ S+ constitute a NE and all pairs (i, j) ∈ S- do not.

For any (i, j) ∈ A1 × A2, we introduce X(i, j) as the polytope of all x3 ∈ ∆3 for which (i, j) is a NE, so defined:

For all (i, j) ∈ A1 × A2, we also introduce the set Xc (i, j) of all x3 ∈ ∆3 for which (i, j) is not a NE. Let D1(i, j, i′ ) := ⎧⎨⎩x3 ∈ ∆3 : ∑ k∈A3 U ijk 1 xk3 < ∑ k∈A3 U i′ jk 1 xk3 ⎫⎬⎭ and

correspond to the values of x3 for which player 1 (resp., 2) would deviate from (i, j) by playing action i′ (resp., j ′ ). Xc (i, j) is thus the set:

Notice that ∂Xc (i, j) ⊆ ∂∆3, as any other accumulation point of Xc (i, j) satisfies one of the inequalities in D1(i, j, i′ ) or D2(i, j, j ′ ) as an equation and, thus, it is not in Xc (i, j).

Let now X(S+) := ∩(i,j)∈S+X(i, j) (a closed polytope) and X(S-) := ∩(i,j)∈S-Xc (i, j) (the union of nor open not closed polytopes). As for Xc (i, j), X(S-) satisfies ∂X(S-) ⊆ ∂∆3. Its closure X(S-) is obtained by turning the < constraints into ≤ in the definition of D1(i, j, i′ ) and D2(i, j, j ′ ). Finally, let us define P := {(S+, S-) : S+ ∈ 2A1×A2 , S- = 2A1×A2 \ S+}.

1 Here, aff(∆3) denotes the affine hull of ∆3, which is, in our case, the hyperplane in Rm containing ∆3.

Theorem 2. Let ψ(x3; S+) := min(i,j)∈S+ ∑k∈A3 U ijk x3. The following holds:

Proof. Let ∆′3 := {x3 ∈ ∆3 : there exists a pure NE in the followers' game induced by x3}. Clearly, since f(x3) > -∞ only on this set, supx3∈∆3 f(x3) = supx3∈∆′3 f(x3). Thus, we can focus w.l.o.g. on ∆′3 .

The sets X(S+) ∩ X(S-) ̸= ∅, obtained for all (S+, S-) ∈ P, form a partition of ∆′3 . Since, at any x3 ∈ X(S+) ∩X(S-), the only pure NE induced by x3 in the followers' game are those in S+, we have f(x3) = ψ(x3; S+). Since supx3∈∆′3 f(x3) is the largest value attained by the supremum of f(x3) over all sets forming any partition of ∆′3 , we deduce:

Note that, since X(S+) ∩X(S-) is, in general, not a closed set, ψ(x3; S+) admits a supremum over it but not necessarily a maximum. Since ψ(x3; S+) is continuous (it is the point-wise minimum of finitely many continuous functions), its supremum over X(S+)∩X(S-) equals its maximum over the closure X(S+) ∩ X(S-) of X(S+)∩X(S-). The claim follows since X(S+) ∩ X(S-) = X(S+) ∩ X(S-).

Corollary 1. If, according to the formula in Theorem 2, the value of supx3∈∆3 f(x3) is attained at some (S+, S-) ∈ P for which there exists an x∗3 ∈ X(S+) ∩ X(S-) such that ψ(x∗3 ; S+) = maxx3∈X(S+)∩X(S-) ψ(x3; S+), then supx3∈∆3 f(x3) = maxx3∈∆3 f(x3) = f(x∗3 ).

Proof. Since x∗3 ∈ X(S+) ∩ X(S-), the only pure NE in the followers' game induced by x∗3 are those in S+. Hence, f(x∗3 ) = ψ(x∗3 ; S+) and the result follows.

Theorem 3. There is a finite exponential-time algorithm which computes supx3∈∆3 f(x3) and, whenever supx3∈∆3 f(x3) = maxx3∈∆3 f(x3), also returns a strategy x∗3 with f(x∗3 ) = maxx3∈∆3 f(x3).

Proof. The algorithm relies on the expression given in Theorem 2. All pairs (S+, S-) ∈ P can be constructed by enumeration in time exponential in m. Given ϵ ≥ 0, let:

Since, for ϵ = 0, X(S-; 0) = X(S-), checking whether X(S+)∩X(S-) ̸= ∅ is equivalent to verifying whether there exists some ϵ > 0 such that X(S+) ∩ X(S-; ϵ) ̸= ∅. This can be done by solving:

The condition X(S+) ∩X(S-) ̸= ∅ is verified if and only if the problem admits a solution (ϵ, x3) with ϵ > 0. The problem is a Mixed-Integer Linear Program (MILP). To see this, it suffices to express each Xc (i, j; ϵ) as the set of x3 ∈ ∆3 such that there are binary variables ziji′ ∈ {0, 1}, for i′ ∈ A1\{i}, and zijj ′ ∈ {0, 1}, for j ′ ∈ A2\{j}, satisfying:

1 xk3 +Miji′ (1 - ziji′ ) ∀i′ ∈ A1 \ {i}

with M iji′ := maxk∈A3 {U ijk 1 - U i′ jk 1 } and M ijj ′ := maxk∈A3 {U ijk 2 - U ij ′ k 2 }. X(S-; ϵ) is the intersection of such sets, for all (i, j) ∈ S-.

Finally, observe that maxx3∈X(S+)∩X(S-) ψ(x3; S+) is equal to the value that ψ(x3; S+) achieves at an optimal solution of a lexicographical maximization problem where, among all solutions which maximize ψ(x3; S+), one with the largest ϵ is sought. It reads:

Due to the original problem being a restriction of the lex one obtained for ϵ = 0, we deduce that optimal solutions to the latter are also optimal for the former. Therefore, maxx3∈X(S+)∩X(S-) ψ(x3; S+) can be computed in, at most, exponential time by solving the following lex-MILP:

Assume that supx3∈∆3 f(x3) is attained at some (S+, S-) and let (x∗3 , ϵ∗ ) be the optimal solution of the corresponding lex-MILP. Clearly, ϵ∗ > 0 if and only if x∗3 satisfies the assumptions of Corollary 1. Therefore, f(x∗3 ) = maxx3∈∆3 f(x3).

4.2 Finding an α-Approximate Strategy

Assume that, for the strategy x∗3 where s := supx3∈∆3 f(x3) is attained, f(x∗3 ) < s and, thus, the problem does not admit a maximum. Given any α > 0, we look for a strategy ˆx3 such that s - f(ˆx3) ≤ α, i.e., for an α-approximate strategy ˆx3. Its existence is guaranteed by the following lemma:

Lemma 1. Let X ⊆ Rn , for some n ∈ N, Y ⊆ R, f : X → Y , and s := supx∈X f(x). Assume s < ∞. For any α > 0, there exists x ∈ X : s - f(x) ≤ α.

Proof. By contradiction, assume there is some α > 0 such that, for every x ∈ X, s - f(x) > α. Then, for all x ∈ X, f (x) < s - α, implying supx∈X f (x) ≤ s - α < s.

Theorem 4. Assume that f(x3) does not admit a maximum. Then, for any α > 0, there is an algorithm which computes an α-approximate strategy ˆx3 in, at most, exponential time.

Proof. According to Equation 2, assume supx3∈∆3 f(x3) is achieved at some (S+, S-) and x∗3 , with ψ(x∗3 , S+) = maxx3∈X(S+)∩X(S-) ψ(x3; S+). We deduce x∗3 ∈ X(S-) \ X(S-) as, otherwise, f would achieve a maximum at x∗3 , in contrast with the assumption in the statement of the theorem.

Aiming at an α-approximate strategy ˆx3, we can, w.l.o.g., look for a point ˆx3 ∈ X(S+)∩X(S-) where f(ˆx3) ≥ s-α, whose existence is guaranteed by Lemma 1. To find it, it suffices to solve the following MILP:

Notice that the problem achieves a solution with ϵ > 0 such that there exists x3 ∈ X(S+) ∩X(S-), whose existence is guaranteed by the fact that the formula in Theorem 2 only considers pairs (S+, S-) ∈ P : X(S+) ∩ X(S-) ̸= ∅.

5 Branch-and-Bound Algorithm

As it is clear, the computation of supx3∈∆3 f(x3) as in Theorem 3 is impractical, as it requires the explicit enumeration of all the outcome configurations of a game, many of which, most likely, yield empty regions X(S+) ∩ X(S-). A more efficient algorithm, albeit still exponential, can be obtained by means of a branch-and-bound technique.

Redefine S- as S- ⊆ (A1 × A2) \ S+. In such case, we call the corresponding pair (S+, S-) a relaxed outcome configuration. Starting from some pair of followers' actions (i, j) ∈ A1 × A2, the algorithm, through a sequence of branching operations, constructs and explores two search trees whose nodes correspond to relaxed outcome configurations. One tree, which considers the case where (i, j) is a NE, has the pair ({(i, j)}, ∅) as root, while the other, which considers the case where (i, j) is not a NE, has root (∅, {(i, j)}).

Notice that, when S- ⊂ (A1 × A2) \ S+, solving maxx3∈X(S+)∩X(S-) ψ(x3; S+) might not give a strategy x3 such that, if the leader plays it, the only pure NE in the followers' game are those in S+, even if x3 ∈ X(S+) ∩ X(S-). This is because, due to S+ ∪ S- ⊂ A1 × A2, there might be another NE (i′ , j ′ ) ∈ A1 × A2 \ (S+ ∪ S-) providing the leader with a strictly smaller utility than all the pairs in S+. Since, if that is the case, the followers would play (i′ , j ′ ) for that x3, ψ(x3; S+) is not a valid candidate for being supx3∈∆3 f(x3).

In order to detect whether one such (i′ , j ′ ) exists, it suffices to carry out a feasibility check for x3 by looking for, in the followers' game, a pure NE different from those in S- which minimizes the leader's utility. This can be done by inspection in O(m2 ). If the feasibility check returns some (i′ , j ′ ) /∈ S+, the tree is expanded by performing a branching operation. Two nodes are introduced: a left node (S+ L , SL ), where S+ L = S+ ∪ {(i′ , j ′ )} and SL = S- (accounting for the case where (i′ , j ′ ) is a NE), and a right node (S+ R , SR ), where S+ R = S+ and SR = S- ∪ {(i′ , j ′ )} (accounting for the case where

(i′ , j ′ ) is not a NE). Instead, if (i′ , j ′ ) ∈ S+, then ψ(x3; S+) represents a valid candidate solution, and, thus, (S+, S-) is a leaf node. Observe that the feasibility check can safely ignore all (i, j) ∈ S- since, whenever (i, j) is a NE for x3, due to how the tree is built, there is another node where (i, j) ∈ S+ (which accounts for the case where (i, j) is a NE).

Due to S- ⊆ (A1 × A2) \ S+, solving maxx3∈X(S+)∩X(S-) ψ(x3; S+) for some (S+, S-) gives an upper bound on the leader's utility under the condition that all the pairs in S+ constitute a NE and those in S- do not. Thus, the values obtained by solving maxx3∈X(S+)∩X(S-) ψ(x3; S+) can be used as bounds. However, since maxx3∈X(S+)∩X(S-) ψ(x3; S+) is not well-defined for nodes where S+ = ∅, for such nodes we solve, instead, the optimistic problem (see Section 2) with additional MILP constraints (see Section 4) which impose that all the pairs in S- are not NE.

Finally, suppose that supx3∈∆3 f(x3) is attained at (S+, S-), and let (x∗3 , ϵ∗ ) be the optimal solution of the associated lex-MILP problem. If ϵ∗ > 0, then f(x∗3 ) = maxx3∈∆3 f(x3) due to Corollary 1. Otherwise, the problem admits a supremum but not a maximum. In this case, we look for an α-approximate strategy ˆx3 using the algorithm of Theorem 4. However, since (S+, S-) is a relaxed outcome configuration here, there might be a pair (i′ , j ′ ) ∈ A1 × A2 \ (S+ ∪ S-) which is a NE for ˆx3 providing the leader with a utility strictly smaller than ψ(ˆx3; S+). In order to establish whether such (i′ , j ′ ) exists, we perform a feasibility check for ˆx3. If we obtain (i′ , j ′ ) /∈ S+, we perform a branching operation (adding (i′ , j ′ ) either to S+ or S-), and repeat the procedure of Theorem 4 on each of the resulting relaxed outcome configurations, iterating until we find an αapproximate strategy for which the feasibility check returns (i′ , j ′ ) ∈ S+. Observe that, due to the correctness of the algorithm for the computation of the supremum, at x∗3 there cannot be a NE (i′ , j ′ ) worse than those in S+. Therefore, there must be a strategy which is a convex combination of x∗3 and ˆx3 where either (i′ , j ′ ) is not a NE or it yields a leader's utility not worse than that obtained with the NE in S+. Thus, the algorithm is guaranteed to converge.

Preliminary results (omitted for reasons of space) on threeplayer GAMUT instances [Nudelman et al., 2004] show that, with our branch-and-bound algorithm, we can solve games with up to 30 actions within 1000 seconds.

6 Conclusions

In this paper, we have shown that the problem of computing a pessimistic leader-follower equilibrium with multiple followers playing pure strategies simultaneously and noncooperatively is NP-hard even when the number of followers is two. Moreover, we have described an exact exponentialtime algorithm for finding an equilibrium strategy (or, if it does not exist, an α-approximate one), which we have then enhanced with a branch-and-bound scheme. Future developments include applications to structured games (e.g., congestion games) and the generalization to the mixed case-even though we conjecture that this problem is much harder, probably Σp2 -complete, given its bilevel structure.