Leadership in Congestion Games: Multiple User Classes and Non-Singleton Actions

1 Introduction

In the last years, Stackelberg games and their corresponding Stackelberg equilibria (SEs) received a lot of attention in the artificial intelligence literature, thanks to their successful applications in real-world settings, e.g., in security domains [Tambe, 2011]. In a Stackelberg game, there is a special player, called leader, who has the ability to commit to a (potentially mixed) strategy beforehand, while the other players, who act as followers, decide how to play after observing the commitment [Von Stengel and Zamir, 2010]. As most of the works in the literature, see, e.g., [Conitzer and Sandholm, 2006; Paruchuri et al., 2008; Conitzer and Korzhyk, 2011], we focus on optimistic SEs (OSEs), which assume that the followers break ties in favor of the leader, maximizing her utility. Few works also analyze pessimistic SEs, where the followers break ties so as to minimize the leader's utility. However, the pessimistic assumption usually results in computational problems that are much harder than their optimistic counterparts, as showed, e.g., by Basilico et al. [2017] and Coniglio et al. [2017; 2018].

∗Equal Contribution

It is well-known that, while finding an OSE in two-player normal-form games is easy [Conitzer and Sandholm, 2006], the problem becomes much harder in games with multiple followers playing a Nash equilibrium (NE). For instance, Basilico et al. [2016; 2019] show that computing an OSE is NP-hard and not in Poly-APX unless P = NP in normal-form games with only two followers, and De Nittis et al. [2018] show the same result for polymatrix games with an arbitrary number of followers. Moreover, finding an OSE is NP-hard also in normal-form games with multiple followers playing sequentially [Conitzer and Sandholm, 2006], while the problem becomes easy if they play simultaneously in a correlated manner [Conitzer and Korzhyk, 2011].

Recently, Marchesi et al. [2018] and Castiglioni et al. [2018] studied the problem of computing OSEs in congestion games (CGs). In a CG, the players' actions are subsets of a given set of shared resources, and each resource has a cost that depends on the number of players using it (a.k.a. congestion). Most of the computational studies on CGs, see, e.g., [Fabrikant et al., 2004; Ieong et al., 2005; Ackermann et al., 2008], focus on finding pure-strategy NEs. Instead, Marchesi et al. [2018] and Castiglioni et al. [2018] apply the Stackelberg paradigm to CGs, assuming that the followers play a pure-strategy NE after observing the leader's mixed-strategy commitment. These works focus on singleton CGs, where actions are made of only one resource. Specifically, Marchesi et al. [2018] show that an OSE can be found in polynomial time when costs are monotonic in the congestion and players are symmetric (i.e., they share the same set of actions), even when the number of followers is non-fixed. Castiglioni et al. [2018] show that the same holds even with non-monotonic costs if we restrict the leader to pure strategies. These results provide some examples of multi-follower Stackelberg games where finding an equilibrium is computationally tractable. On the other hand, Castiglioni et al. [2018] also show that, if either the costs are non-monotonic or players are not symmetric, then the problem becomes NP-hard and not in Poly-APX, unless P = NP.

Identifying new classes of multi-follower Stackelberg games where SEs can be computed in time polynomial in the number of players is crucial for real-world problems, enabling the adoption of SEs in massive applications, such as, e.g., resource-sharing systems with premium (prioritized) users, cybersecuirty with multiple treats, and influence maximization in social networks. Despite this, a complete characterization of hard and easy game instances is still lacking.

Original Contributions

In this paper, we extend the state of the art on the computational problem of finding OSEs in CGs, identifying new cases in which it is solvable in polynomial time and others where it is not. First, we show that having actions made of only one resource is necessary to have efficient (polynomial-time) algorithms. Indeed, we prove that finding an OSE is NP-hard and not in Poly-APX unless P = NP, even if players' actions contain only two resources, costs are monotonic, and players are symmetric. Then, we introduce and study singleton CGs in which the players are partitioned into classes, with followers of the same class sharing the same set of actions. These are a generalization of singleton CGs with symmetric players, capturing the common case in which users can be split into (usually few) different classes, such as, e.g., users with different priorities. For these games, we provide a dynamic programming algorithm that computes an OSE in polynomial time, when the number of classes is fixed and the leader is restricted to play pure strategies. On the other hand, we prove that, if the leader is allowed to play mixed strategies, then the problem becomes NP-hard even with only four classes and monotonic costs. Finally, for both settings, we design mixed-integer linear programming (MILP) formulations for computing OSEs, and we experimentally evaluate them on a testbed containing both randomly generated game instances and worst-case instances based on our hardness reductions. 1

2 RelatedWorks

In this work, we apply the Stackelberg paradigm to CGs following the approach of Von Stengel and Zamir [2010] and Conitzer and Sandholm [2006], i.e., we treat the leader as a special player who seeks for an optimal (in terms of her utility) strategy to commit to. In the literature, there are a number of works that apply the Stackelberg paradigm to CGs following different approaches. Even if these works address settings that are are substantially different from ours, it is worth discussing how their results relate to our work.

There are some works, such as, e.g., [Roughgarden, 2004; Swamy, 2007; Sharma and Williamson, 2009; Fotakis, 2010], which study CGs where the leader is an authority whose objective is to minimize the inefficacy (in terms of followers' social welfare) of the NE reached by the followers (i.e., minimize the price of anarchy). This setting is fundamentally different form ours, as we assume that the leader looks for a strategy to commit to that minimizes her own cost, while she is not concerned with the maximization of followers' social welfare. Let us remark that our approach leads to what is usually called OSE, while the Stackelberg strategies analyzed in these works are not OSEs according to the classical definitions [Conitzer and Sandholm, 2006; Von Stengel and Zamir, 2010].

1 The proofs of all the results are in [Marchesi et al., 2019].

Moreover, there are other works, such as, e.g., [Leme et al., 2012; De Jong and Uetz, 2014; Correa et al., 2015], which apply the Stackelberg paradigm to CGs following yet another approach. They assume that the players play sequentially in a predefined order, reaching a subgame perfect equilibrium (SPE) in the extensive-form extension of the original CG where each player plays after observing the actions performed by the preceding players. This is different from our setting in two fundamental ways: (i) we assume that the followers play simultaneously, rather than sequentially; and (ii) these works study the inefficiency (in terms of followers' social welfare) of SPEs, rather than the computational problem of finding an optimal leader's strategy. Furthermore, we remark that an OSE is an SPE of a particular extensiveform extension of the original CG, known as mixed extension [Von Stengel and Zamir, 2010]. In this extended game, the leader first commits to a mixed strategy (having a continuum of actions), and, then, the followers observe it and play simultaneously, reaching an NE. This is different from the extensive-form extension studied in the work by Leme et al. [2012] and its follow-ups, where only pure-strategy commitments are possible and the followers play sequentially.

3 Preliminaries

We study Stackelberg congestion games (SCGs) with one leader and multiple followers playing an NE in the CG resulting from the leader's commitment. An SCG is a tuple (N, R, A, cℓ, cf ), defined as follows. N = F ∪ {ℓ} is a finite set of players, the leader ℓ and the followers p ∈ F. R is a finite set of resources. A = {Ap}p∈N, where Ap ⊆ 2R is the set of player p's actions, with each action ap ∈ Ap being a non-empty subset of resources, i.e, ap ⊆ R. Finally, cℓ = {ci,ℓ}i∈R and cf = {ci,f}i∈R are, respectively, the leader's and followers' cost functions, with ci,ℓ, ci,f : N → Q being the costs of resource i as a function of its congestion. As usual, we assume ci,ℓ(0) = ci,f (0) = 0 for every i ∈ R. Moreover, we let n := |N| and r := |R| be the number of players and resources, respectively.

Let σp ∈ ∆p be a player p's strategy, which is a probability distribution over actions Ap, with σp(ap) denoting the probability of playing action ap ∈ Ap. A strategy σp ∈ ∆p is pure when it prescribes to play a single action ap ∈ Ap with probability σp(ap) = 1; otherwise, σp is mixed. With an abuse of notation, given σp ∈ ∆p, let σp(i) := ∑ap∋i σp(ap) be the probability of selecting resource i ∈ R when σp is played. We denote with σ = (σℓ, a) a strategy profile, i.e., a tuple of players' strategies, in which the leader plays a (potentially) mixed strategy σℓ ∈ ∆ℓ and the followers play pure strategies that determine a followers' action profile a = (ap)p∈F , which belongs to the set AF =×p∈F Ap.

Given a followers' action profile a ∈ AF , we let ν a i :=

|{p ∈ F | i ∈ ap}| be the number of followers selecting resource i ∈ R in a. For ease of presentation, we define the followers' configuration induced by a as the vector ν a ∈ Nr whose i-th component is ν a i . Furthermore, for σℓ ∈ ∆ℓ, cσℓ i,f : N → Q encodes the followers' expected cost of resource i ∈ R given σℓ, as a function of the number x of followers selecting i, i.e., cσℓ i,f (x) = σℓ(i)ci,f (x+1)+(1-σℓ(i))ci,f (x). Intuitively, the followers who select resource i experience a congestion incremented by one whenever the leader chooses i, which happens with probability σℓ(i). When player p ∈ N plays an action ap ∈ Ap, she pays the sum of the costs of resources i ∈ ap. Thus, given a strategy profile σ = (σℓ, a), cσp := ∑i∈ap cσℓ i,f (ν a i ) is the cost of follower p ∈ F in σ, and cσℓ := ∑aℓ∈Aℓ σℓ(aℓ) ∑i∈aℓ ci,ℓ(ν a i +1) is the leader's one. In an SCG, after observing a leader's strategy σℓ ∈ ∆ℓ, the followers play a new CG with resource costs cσℓ i,f , for i ∈ R. Specifically, we assume that the followers play an NE in pure strategies [Nash, 1951]. Formally, given σ = (σℓ, a), a is a (pure-strategy) NE for σℓ if, for every p ∈ F and a′p ∈ Ap, cσp ≤ cσ′ p , where σ′ = (σℓ, a′ ) and a′ ∈ AF is obtained from a by replacing ap with a′p . In words, in an NE, there is no follower who has an incentive to unilaterally deviate from ap by playing another action a′p . Given σℓ ∈ ∆ℓ, we let Eσℓ be the set of NEs in the followers' game for σℓ. 2

Different subclasses of SCGs can be defined by making additional assumptions on their elements. For instance, one possibility is to require that players' cost functions be (weakly) monotonic in the resource congestion, i.e., for every resource i ∈ R, it must be the case that ci,ℓ(x) ≤ ci,ℓ(x + 1) and ci,f (x) ≤ ci,f (x + 1) for all x ∈ N.

Another possibility is to restrict the structure of the players' action sets Ap. Along this direction, we address Stackelberg singleton congestion games (SSCGs), which are SCGs with players' actions required to be singletons, i.e., |ap| = 1 for every p ∈ N and ap ∈ Ap. Thus, when studying such games, we identify actions with resources, assuming Ap ⊆ R for all p ∈ N. We also use σℓ ∈ ∆ℓ as if it were directly defined over resources in Aℓ, with σℓ(i) being the probability of playing resource i ∈ Aℓ. Moreover, given σ = (σℓ, a), we have cσp = cσℓ ap,f (ν a ap ) and cσℓ = ∑i∈Aℓ σℓ(i)ci,ℓ(ν a i +1).

Finally, we can consider different kinds of players' structures. Here, we focus on two notable cases. In the first one, all players share the same set of actions, i.e., Ap = A ⊆ 2R for all p ∈ N. We refer to these games as symmetric. Instead, in the second case, there exists a finite set T = {1, . . . , T} of followers' classes, with followers of the same class sharing the same set of actions. We say that these games are T -class. Specifically, in a T -class SCG, we can partition the followers into T disjoint sets, i.e., F = ⋃t∈T Ft, so that, for each t ∈ T , Ap = At ⊆ 2R for all p ∈ Ft. We also let |Ft| = nt be the number of followers of class t ∈ T . When studying these games, given a followers' action profile a ∈ AF , we let ν a t,i := |{p ∈ Ft | i ∈ ap}| be the number of followers of class t ∈ T selecting resource i ∈ R in a. Moreover, we define the followers' configuration of class t induced by a as the vector ν a t ∈ Nr whose i-th component is ν a t,i . 3

2 Let us remark that we can safely restrict the attention to purestrategy NEs, as one is guaranteed to exist in every CG [Rosenthal, 1973]. Moreover, it is natural to assume that the followers will end up playing pure-strategy NEs, since they are reachable by best-response dynamics [Monderer and Shapley, 1996], where players continuously change their actions, one at a time, playing a best response to the current players' configuration.

Observe that T -class SSCGs can be fully analyzed using followers' configurations, rather than action profiles. This is because only the number of followers of each class selecting each resource is significant, and, thus, a followers' action profile a ∈ AF can be equivalently represented with the followers' configurations {ν a t }t∈T . Thus, we can directly use the vector νt ∈ Nr with ∑i∈R νt,i = nt to denote a followers' configuration of class t ∈ T . Moreover, given {νt}t∈T , we let ν ∈ Nr be such that νi := ∑t∈T νt,i for i ∈ R. Notice that, given a strategy profile σ = (σℓ, {νt}t∈T ), {νt}t∈T is an NE for σℓ if, for every class t ∈ T , and resources i ∈ At : νt,i > 0 and j ∈ At, it holds cσℓ i,f (νi) ≤ cσℓ j,f (νj +1).

In conclusion, in an SCG, an OSE prescribes the leader an optimal strategy to commit to, assuming that the followers play a pure-strategy NE minimizing her cost in the CG resulting from the commitment. Formally, σ = (σℓ, a) is an OSE if it solves the problem: minσ′ℓ∈∆ℓ mina′∈Eσ′ℓ cσ′=(σ′ℓ ,a′ ) ℓ .

4 Complexity Results on SCG

First, we study the problem of computing an OSE in SCGs, and we prove it is intractable even when the game is symmetric, cost functions are monotonic, and players' actions are made of only two resources. Thus, non-singleton actions make the problem considerably harder than in the singleton case, which admits a polynomial-time algorithm in symmetric games with monotonic costs [Marchesi et al., 2018].

In particular, we show that the problem is NP-hard and not in Poly-APX unless P = NP, i.e., the leader's cost in an OSE cannot be efficiently approximated up to any polynomial factor in the size of the input. Our results are based on a reduction from 3SAT, a well-know NP-complete problem. Intuitively, given ϵ > 0, we map any 3SAT instance to an SCG that admits an OSE σ with cσℓ = ϵ if and only if 3SAT is satisfiable, otherwise cσℓ = 1.

Theorem 1. Computing an OSE in symmetric SCGs is NPhard, even when cost functions are monotonic and players' actions have cardinality at most two.

By letting ϵ = 1 2I , where I is the game size, the reduction used for Theorem 1 also shows the following:

Theorem 2. The problem of computing an OSE in symmetric SCGs is not in Poly-APX unless P = NP, even when costs are monotonic and players' actions have cardinality two.

In conclusion, we provide some side results that deepen our analysis on how non-singleton actions impact on the complexity of finding an OSE in SCGs. The following theorem shows that our intractability results hold even in SCGs where only the followers have non-singleton actions.

3 Let us remark that symmetric SCGs are a special case of T - class SCGs with only one class, i.e., T = {1}, and leader's action set equal to the followers', i.e., Aℓ = A1.

Theorem 3. The problem of computing an OSE in SCGs is NP-hard and not in Poly-APX unless P = NP, even when leader's actions are singletons, costs are monotonic, and followers are symmetric with actions of cardinality at most two.

Since the OSEs of the games used in our reduction prescribe the leader to play a pure strategy, we have that:

Observation 1. The results in Theorems 1, 2, and 3 hold even if we restrict the leader to play pure strategies.

Finally, let us consider the case in which only the leader has non-singleton actions. We have the following observation.

Observation 2. In SCGs with symmetric followers having singleton actions, an OSE can be found in polynomial time if we restrict the leader to play pure strategies. 4

A polynomial-time algorithm enumerates the leader's pure strategies, and, for each of them, it computes an NE minimizing the leader's cost in the resulting followers' symmetric singleton CG, which can be done in polynomial time using dynamic programming, as shown by Ieong et al. [2005].

5 Complexity Results on T -class SSCG

We switch the attention to SSCGs, i.e., games where players' actions are singletons. In particular, we focus on T -class SSCGs, a generalization of symmetric SSCGs. As shown by Castiglioni et al. [2018], finding an OSE in symmetric SSCGs with non-monotonic costs is NP-hard, while the problem becomes easy if: (a) we assume that the leader can only play pure strategies [Castiglioni et al., 2018], or (b) we force players' costs be monotonic [Marchesi et al., 2018].

Here, first we show that, under condition (a), computing an OSE is easy also in T -class SSCGs with a fixed number of classes. Next, we prove that, if condition (a) does not hold, then the problem is NP-hard in T -class SSCGs even if we enforce (b) and there are only four followers' classes.

Let us start providing a polynomial-time algorithm for computing OSEs in T -class SSCGs with a fixed number of classes and the leader restricted to pure strategies. Our algorithm iterates over leader's pure strategies, i.e., resources i ∈ Aℓ, and, for each of them, it finds an NE minimizing the leader's cost in the followers' game for σℓ ∈ ∆ℓ : σℓ(i) = 1. Such NE is computed with an extension of the dynamic programming algorithm proposed by Ieong et al. [2005] for finding an optimal NE in symmetric singleton CGs without leadership. We extend the algorithm to T -class singleton CGs without leadership, which are defined as their Stackelberg counterpart, except for the fact that there is no leader and all players experience the same resource costs c = {ci}i∈R, with ci : N→Q defined as usual.

We define O(h, B1, . . . , BT ,M1, . . . ,MT , V1, . . . , VT ) as the cost of an optimal (according to some optimality criterion) NE for a T -class singleton CG restricted to i resources {1, 2, . . . , i} ⊆ R and Bt players for each class t ∈ T , where Mt is the largest cost experienced by a player of class t and Vt is the smallest cost a player of class t would get by switching to another resource. When the optimality criterion is the minimization of the sum of players' costs, we have:

4 We leave as an open problem the study of the computational complexity when the leader is allowed to play mixed strategies.

Lemma 4. O(i, B1, . . . , BT ,M1, . . . ,MT , V1, . . . , VT ) satisfies the following recursive equation:

Remark 1. Lemma 4 holds also for other optimality criteria, e.g., the minimization of the cost of a given resource.

Thus, we can conclude the following:

Theorem 5. In T -class singleton CGs without leadership, an optimal (given an optimality criterion) NE can be found in O(n6T r4T+1 ). In T -class SSCGs, an OSE can be found in O(n6T r4T+2 ) if we restrict the leader to play pure strategies.

Corollary 5.1. In T -class SSCGs with a fixed number of classes, an OSE can be found in polynomial time if we restrict the leader to play pure strategies.

Now, we prove the hardness result, using a reduction from K-PARTITION, an NP-compete variant of PARTITION with an additional size constraint [Castiglioni et al., 2018].

Theorem 6. Computing an OSE in T -class SSCGs is NPhard, even when cost functions are monotonic and |T | = 4.

6 Mathematical Programming Formulations

In this section, we provide two MILP formulations for finding OSEs in SCGs. The first one is specifically tailored to T -class SSCGs, while the second one works for general SCGs.

Let us start with T -class SSCGs. For ease of presentation, let V (i) := {1, . . . , vmax i } be the set of possible congestion levels induced by the followers on resource i ∈ R, with vmax i := ∑t∈T :i∈At nt. Moreover, let V (t) := {1, . . . , nt} for t ∈ T . For every class t ∈ T , resource i ∈ At, and value v ∈ V (t), let us introduce the binary variable qtiv, which is equal to 1 if and only if v followers of class t select resource i. Furthermore, for every i ∈ R and v ∈ V (i), let the binary variable yiv be equal to 1 if and only if v followers select resource i. These variables represent followers' configurations. Specifically, for t ∈ T , νt ∈ Nr is such that νt,i = ∑v∈V (t) v qtiv for all i ∈ R, while ν ∈ Nr is such that νi = ∑v∈V (i) v yiv for all i ∈ R. For every i ∈ R, let αi ∈ [0, 1] be equal to σℓ(i), and, for v ∈ V (i), let the auxiliary variable ziv be equal to the bilinear term yivαi. Finally, let M > max{ci,f (v) | i ∈ R, v ∈ {1, . . . , vmax i +2}}.

The complete MILP formulation reads as follows:

Function (2a) is the leader's expected cost. Constraints (2b) ensure that at most one variable qtiv be equal to 1 for each class t ∈ T and resource i ∈ At, and, thus, the number of followers of class t on each resource is uniquely determined (note that ∑v∈V (t) qtiv = 0 if no follower of class t selects resource i). Constraints (2c) ensure that at most one variable yiv be equal to 1 for each resource i ∈ R, which guarantees that the congestion level of each resource is uniquely determined. Constraints (2d) guarantee that the followers' configuration be well-defined, i.e., for all t ∈ T , exactly nt followers of class t are present. Constrains (2e) ensure that the congestion level on resource i ∈ R be equal to the sum of the congestion levels induced by all classes. Constraints (2f) force the followers' configurations defined by the qtiv variables be an NE for the leader's strategy identified by the αi variables. This follows from the fact that, being ziv = yivαi and zjv = yjvαj, the right-hand side is the cost incurred by the followers of class t ∈ T selecting resource i ∈ At, while the left-hand side is the cost they would incur after deviating to j ̸= i ∈ At. Note that, for each t ∈ T , the constrains are active only if there is at least one follower of class t selecting i. Finally, Constraints (2g)- (2j) are McCormick envelope constraints [McCormick, 1976] which guarantee ziv = yivαi when yiv ∈ {0, 1}.

Next, we extend Formulation (2) to deal with general SCGs. Letting vmax i := |{p ∈ F | ∃ap ∈ Ap : i ∈ ap}| be the maximum number of followers who can select resource i ∈ R, we define V (i) := {1, . . . , vmax i }. For every follower p ∈ F and action ap ∈ Ap, we introduce the binary variable xpap , which is equal to 1 if and only p plays ap. Moreover, for every aℓ ∈ Aℓ, let αaℓ ∈ [0, 1] be equal to σℓ(aℓ). All the variables already defined in Formulation (2) are used here with the same meaning. Finally, let M > ∑i∈R max{ci,f (v) | i ∈ R, v ∈ {1, . . . , vmax i +2}}.

The complete MILP formulation reads as follows:

Function (3a), Constraints (3c), and Constraints (3e)-(3k) have the same meaning as their counterparts in Formulation (2). Note that, in this case, ziv = yiv ∑aℓ∈Aℓ:i∈aℓ αaℓ , where the summation represents the probability σℓ(i) and σℓ is identified by the αaℓ variables. Constraints (3b) ensure that each follower selects exactly one action. Constraints (3d) guarantee that the followers' configuration represented by the variables yiv be well-defined. Note that, Constraints (3e) are enforced for each follower p ∈ F here, and they are active only for the action ap ∈ Ap that she plays. Constraints (3e) do not account for the costs of resources i ∈ ap ∪ a′p , since they do not change when deviating from ap to a′p .

7 Experimental Results

There is no standard testbed for our games and there is no evidence that some structured games are more representative than others. Thus, we test the MILP formulations proposed in Section 6 on randomly generated games, which represent instances of average-case complexity, and games based on the reductions provided in the proofs of Theorems 1 and 6, which, instead, represent worst-case complexity instances.

All the experiments are run on a UNIX machine with a total of 32 cores working at 2.3 GHz, equipped with 128 GB of RAM. Each instance is solved on a single core within a time limit of 3600 seconds. We use GUROBI 7.0 (with Python interface) as MILP solver.

Random Game Instances

For T -class SSCGs, we generate random game instances with r ∈ {10, 20, 30, 40, 50, 60, 70, 80, 90, 100} resources and T ∈ {1, 2, 3, 4} classes, with nt ∈ {0.2 r, 0.5 r, r} followers per class t ∈ T and |At| = 0.5 r actions per class t ∈ T . Cost functions are randomly generated by sampling uniformly from {1, . . . , nrT}. For general SCGs, we generate instances with r ∈ {5, 10, 15, 20, 25} resources and n ∈ {r, 2 r, 3 r} followers, with |ap| ∈ {1, 2, 3, 4, 5} resources per action ap ∈ Ap and |Ap| = 0.5 r actions per player p ∈ N. Cost functions are randomly generated by sampling uniformly from {1, . . . , nr}. We build a testbed with 20 game instances per combination of the parameters.

Figure 1(a) displays the average computing times for Formulation (2) with 0.5 r followers per class. The formulation scales quite well in practice. Symmetric games (T = 1) are quickly solved up to r = 100. Moreover, we are able to solve within the time limit games with up to four classes, 40 resources, and 160 players (40 players per class). Let us notice that the dynamic programming algorithm presented in Theorem 5 can be employed in this setting to find an OSE, if we restrict the leader to play pure strategies. However, preliminary experiments show that its scalability is extremely limited with respect to that of our formulation, as it finds a solution within the time limit only for games with less than 10 resources, while our formulation scales on much bigger games and it also works for mixed-strategy commitments.

Figure 1(c) shows the average computing times for Formulation (3) with 2 r followers. We can conclude that, as expected, game instances with non-singleton actions are much harder to solve than singleton games. Here, the largest game instances we can solve within the time limit feature actions of cardinality two, 15 resources, and 30 players. 5

Worst-Case Instances

We test Formulation (3) on instances built according to the reduction in Theorem 1. Specifically, we generate these games from random 3SAT instances with |U| ∈ {4, 5, 6, 7, 8, 9} variables and |C| = k|U| clauses, where k ≈ 4.26 is the phase transition parameter determining generally hard-tosolve 3SAT instances [Cheeseman et al., 1991]. We test 10 random instances for each number of variables. Furthermore, we experiment Formulation (2) on instances based on the reduction in Theorem 6. We generate these games from random K-PARTITION instances with |S| ∈ {20, 40, . . . , 160} integers, si ∈ [2, 100] for all si ∈ S, and K = |S| 2 . We test 10 random instances for each value of |S|.

5 Additional experimental results are in [Marchesi et al., 2019].

Figures 1(b) and 1(d) show the computing times for T - class SSCGs and SCGs, respectively. Surprisingly, the results we obtain are comparable to those for random games, empirically showing that, for the games we study, random instances are not easier to solve than structured ones, as instead it is the case, e.g., in normal-form games [Sandholm et al., 2005].

8 Discussion and FutureWorks

This paper studies the problem of computing Stackelberg equilibria in multi-follower Stackelberg games with a massive number of players, focusing on congestion games. Our results shed light on the boundary between hard and easy game instances, significantly advancing the state of the art.

Our analysis about games with non-singleton actions shows that, in oder to compute an equilibrium in time polynomial in the number of players, singleton actions are necessary (Theorems 1 and 2). This answers a question left open by Castiglioni et al. [2018]. Surprisingly, our negative result holds even in games where each action is made of at most two resources. Future works could address non-singleton games with players' actions enjoying specific structures, as it is the case, e.g., in games played on graphs [Werneck et al., 2000].

Our findings about congestion games with multiple classes of players substantially improve known results on symmetric (i.e., single-class) games. Our dynamic programming algorithm can compute optimal leader's pure-strategy commitments in time polynomial in the number of players, even when costs are arbitrary functions and the players are split into a (fixed) number of different classes (Theorem 5).

Future extensions of this work may investigate how adopting a different solution concept for the followers' game, such as, e.g., the correlated equilibrium [Aumann, 1974], affects the computation of equilibria. This has been recently studied for polynomial-type games [Castiglioni et al., 2019].

Acknowledgments

This work has been partially supported by the Italian MIUR PRIN 2017 Project ALGADIMAR "Algorithms, Games, and Digital Market".