Be a Leader or Become a Follower: The Strategy to Commit to with Multiple Leaders

1 Introduction

Over the last years, Stackelberg games are receiving an increasing attention from the algorithmic game theory community, thanks to their many applications in real-world scenarios, such as in security [Tambe, 2011]. In the classical Stackelberg setting [Von Stackelberg, 1934], there is a leader with the ability to play before the other player, who acts as follower by observing the realization of the leader's strategy. In this work, we follow a different approach, where the leader looks for a strategy to commit to [Conitzer and Sandholm, 2006], and the follower observes the leader's mixed strategy, without knowing its actual realization. An interpretation of this setting is provided by Von Stengel and Zamir [2010]: any (underlying) game is extended as a sequential game in which the leader plays first, having a continuum of choices corresponding to mixed-strategy commitments.

The majority of the works in the literature focus on games with a single leader and a single follower [Conitzer and Sandholm, 2006; Von Stengel and Zamir, 2010]. In this setting, the leader seeks for a utility-maximizing mixed strategy to commit to, while the follower plays a best response to the commitment. This model has been largely studied, especially for security applications [Paruchuri et al., 2008; Kiekintveld et al., 2009; An et al., 2011].

∗Equal Contribution

Some works also study games with a single leader and multiple followers. Conitzer and Korzhyk [2011] introduce a model where the leader commits to a correlated strategy and, accordingly, she draws recommendations for the followers, who must obey the incentive constraints of correlated equilibria [Aumann, 1974]. The authors show that, in normal-form games, an optimal correlated strategy to commit to can be computed in polynomial time. Other works study situations where the followers play a Nash equilibrium [Nash, 1951] in the game resulting from the leader's mixed-strategy commitment [Von Stengel and Zamir, 2010; Coniglio et al., 2017; 2018; De Nittis et al., 2018; Marchesi et al., 2018; 2019]. However, these models usually result in intractable computational problems even with a fixed number of followers.

Settings including multiple leaders are widely unexplored in the literature. In spite of this, many real-world applications naturally involve more than one player with competitive advantages, playing the role of leader. Some scenarios are, e.g., network platforms with premium (prioritized) users, markets where a group of firms forms a price-determining dominant cartel, and political elections in which some candidates choose policy positions in advance of challengers.

Restricted to the security context, there are some works addressing games with multiple uncoordinated defenders (leaders) [Smith et al., 2014; Lou and Vorobeychik, 2015; Laszka et al., 2016; Lou et al., 2017; Gan et al., 2018]. However, differently from our work, they all enforce Nash-like constraints on the leaders' strategies. Moreover, their models suffer from two major drawbacks: (i) an exact equilibrium may not exist, and (ii) they strongly rely on problem-specific structures arising in security problems.

The operations research literature provides further works on multi-leader-follower settings, under the name of mathematical programs with equilibrium constraints [Luo et al., 1996]. They assume that both leaders and followers are subject to Nash constraints, with the latter playing in the game resulting from the leaders' strategies [Leyffer and Munson, 2010; Kulkarni and Shanbhag, 2014]. Furthermore, other works from the same field focus on oligopoly models where the leaders select the level of investment to maximize profits [DeMiguel and Xu, 2009]. All these works considerably depart from ours, as they use fundamentally different models and lack thorough game theoretic and computational studies.

Original Contributions

We introduce a new way to apply the Stackelberg paradigm to any finite (underlying) game. Our approach extends the idea of commitment to correlated strategies in settings involving multiple leaders and followers, generalizing the work of Conitzer and Korzhyk [2011]. The crucial component of our framework is that a leader can decide whether to participate in the commitment or to defect from it by becoming a follower. This induces a preliminary agreement stage that takes place before the underlying game is played, where the leaders decide, in turn, whether to opt out from the commitment or not. We model this stage as a sequential game, whose size is factorial in the number of players. Our goal is to identify commitments guaranteeing some desirable properties that we define on the agreement stage. The first one requires that the leaders do not have any incentive to become followers. It comes in two flavors, called stability and perfect stability, which are related to, respectively, Nash and subgame perfect equilibria of the sequential game representing the agreement stage. The second property is also defined in two flavors, namely efficiency and perfect efficiency, both enforcing Pareto optimality with respect to the leaders' utility functions, though at different levels of the agreement stage.

We introduce three solution concepts, which we generally call Stackelberg correlated equilibria (SCEs). They differ depending on the properties they call for. Specifically, SCEs, SCEs with perfect agreement (SCE-PAs), and SCE-PAs with perfect efficiency (SCE-PAPEs) require, respectively, stability and efficiency, perfect stability and efficiency, and both perfect stability and perfect efficiency.

First, we investigate the game theoretic properties of our solution concepts. We show that SCEs and SCE-PAs are guaranteed to exist in any game, while SCE-PAPEs may not. Moreover, we compare them with other solution concepts.

Then, we switch the attention to the computational complexity perspective. We show that, provided a suitably defined stability oracle is solvable in polynomial time, an SCE optimizing some linear function of leaders' utilities (such as the leaders' social welfare) can be computed in polynomial time, even in the number of players. The same holds for finding an SCE-PA, while we prove that computing an optimal SCE-PA is an intractable problem. Nevertheless, in the latter case, we provide an (exponential in the game size) upper bound on the necessary number of queries to the oracle.

In conclusion, we study which classes of games admit a polynomial-time stability oracle, focusing on those with polynomial type [Papadimitriou and Roughgarden, 2008]. We show that the problem solved by our oracle is strictly connected with the weighted deviation-adjusted social welfare problem introduced by Jiang and Leyton-Brown [2011]. As a result, we get that our oracle is solvable in polynomial time in all the game classes where the same holds for the problem of finding an optimal correlated equilibrium. 1

1 Full proofs of all the results are in [Castiglioni et al., 2019].

2 Preliminaries

In this section, we introduce some basic concepts about games and their equilibria used in the rest of the paper.

2.1 Finite Games and Their Equilibria

A (finite) game G is a tuple (N, {Sp}p∈N, {up}p∈N), where N = {1, . . . , n} is a finite set of players, Sp is a finite set of player p's strategies or actions, and up : S → R is player p's utility, defined over the set of strategy profiles S =×p∈N Sp. Given s ∈ S, let s-p ∈ S-p =×q∈N\{p} Sq be the partial profile obtained by dropping player p's strategy sp from s, so that s = (sp, s-p). We call X = ∆(S) the set of correlated distributions defined over strategy profiles, i.e., each x ∈ X satisfies ∑s∈S x(s) = 1 and x(s) ≥ 0 for all s ∈ S. Moreover, overloading notation, up(x) = ∑s∈S x(s)up(s) is player p's expected utility in x ∈ X .

A correlated distribution x ∈ X is a correlated equilibrium (CE) [Aumann, 1974] if, for every player p ∈ N and strategies sp ̸= s′p ∈ Sp, the following constraint holds:

We can interpret a CE in terms of a mediator who draws some strategy profile s ∈ S from a publicly known distribution x, and, then, it privately communicates each recommendation sp to player p. The distribution is an equilibrium if no player has an incentive to deviate from the recommendation, as made formal by the incentive constraints of Eq. (1). Moreover, a Nash equilibrium (NE) [Nash, 1951] is a CE x ∈ X that can be written as the product distribution of players' mixed strategies, i.e., x(s) = ∏p∈N xp(sp) for all s ∈ S, where each xp ∈ ∆(Sp) is a probability distribution over strategies Sp denoting a player p's mixed strategy.

In the following, we denote with X CE P ⊆ X the set of correlated distributions that satisfy the incentive constraints of Eq. (1) only for a subset of players P ⊆ N. Clearly, X CE = X CE N is the set of CEs of the game.

Different classes of games are employed depending on how strategies and utilities are represented. The most common representation is the normal form, which encodes each utility function up as an n-dimensional matrix indexed by s ∈ S. Thus, the size of a normal-form game is exponential in the number of players. Many other representations have been introduced in the literature. In Section 7, we are interested in those with polynomial type [Papadimitriou and Roughgarden, 2008], where the number of players and the number of strategies are bounded by polynomials in the size of the game. Many important classes of games admit a polynomial-type representation, such as graphical games [Kearns et al., 2013], polymatrix games [Eaves, 1973], anonymous games [Blonski, 2000], and congestion games [Rosenthal, 1973].

2.2 Stackelberg Games and Equilibria

Any finite game has a Stackelberg counterpart where some of the players are leaders and the others are followers. The former have the ability to commit to a course of play beforehand, while the latter decide how to play after observing the commitment [Von Stengel and Zamir, 2010].

Definition 1. Given a finite game G, a Stackelberg game (SG) is a tuple (G, L, F) where L and F are the sets of leaders and followers, respectively, with N = L ∪ F .

In single-leader single-follower SGs, the follower best responds to the leader's mixed-strategy commitment [Conitzer and Sandholm, 2006; Von Stengel and Zamir, 2010].

Definition 2. Given an SG (G, {1}, {2}), a leader's mixed strategy x1 ∈ ∆(S1) defines a Stackelberg equilibrium (SE) if it maximizes u1 given that, for each x′1 ∈ ∆(S1), the follower plays an x2(x′1 ) ∈ ∆(S2) maximizing u2. 2

The multi-follower case unfolds in different scenarios depending on how the followers are assumed to play. Conitzer and Korzhyk [2011] study what they call optimal correlated strategies to commit to, where the leader commits to a utilitymaximizing correlated distribution satisfying the incentive constraints (Eq. (1)) for the followers only. Formally:

Definition 3. Given an SG (G, {1},N \ {1}), x ∈ X is an optimal correlated strategy to commit to if it maximizes the leader's utility u1(x) over the set X CE N\{1} .

In our work, we pursue the approach of Conitzer and Korzhyk [2011], rather than letting the followers play an NE, as done, e.g., by Von Stengel and Zamir [2010]. Indeed, while the two models provide the same leader's utility in single-follower SGs (corresponding to that in an SE), the latter may be strictly better in SGs with two or more followers (see [Conitzer and Korzhyk, 2011] for an example).

3 Multi-Leader-Follower Stackelberg Games

We address SGs with multiple leaders and followers. The key components of our approach are the following. First, we allow the leaders to decide whether to participate in the commitment or to defect from it by taking on the role of followers. This is modeled by the agreement stage of the SG, whose result is the formation of an agreement involving a subset of the leaders. Second, in the spirit of CEs, we introduce a correlation device that, after the agreement, draws recommendations and privately communicates them to the players. Following Conitzer and Korzhyk [2011], we assume that the leaders involved in the agreement commit to play their recommendations, while the followers obey to the usual incentive constraints of CEs (see Eq. (1)). The correlation device may adopt different distributions depending on the sequence of defections that determined the agreement, and these distributions are publicly known. Our goal is to design the device, so as to achieve some desirable properties of the commitment, which we formally describe in the rest of the section.

Before going into our main definitions, we introduce some useful notation. Given a subset of players P ⊆ N, we denote with ΠP the collection of ordered subsets of P , including the empty set ∅. Given π ∈ ΠP and p ∈ P \ π, we let πp be the ordered set obtained by appending p at the end of π. We use x = [xπ] to denote a vector of correlated distributions xπ ∈ X CE π∪F , one per ordered subset of leaders π ∈ ΠL, while X = ×π∈ΠL X CE π∪F is the set of all such vectors. In words, π ∈ ΠL represents a sequence of leaders' defections in the agreement stage, while x defines the publicly known correlated distributions adopted by the correlation device, with xπ being the one used when the sequence of defections is π.

2 In the literature, different SE concepts are defined depending on how the follower is assumed to break ties. The strong and weak SEs are two notable cases [Breton et al., 1988], where the follower is assumed to break ties in favor and against the leader, respectively.

Definition 4. Given a vector of distributions x = [xπ] ∈ X, an SG (G, L, F) is structured in the following two stages:

• Agreement. It goes on in rounds. In a given round, each leader, in turn, decides between OPT-IN and OPT-OUT. 3 All the decisions are perfectly observable. If a player chooses OPT-OUT, then she leaves the set of leaders becoming a follower, and a new round starts. The stage ends when, during a round, all remaining leaders decide to OPT-IN. The result is the ordered subset π ∈ ΠL of leaders who decided to OPT-OUT. 4 5
• Play. The correlation device draws some s ∈ S according to the publicly known correlated distribution xπ. Then, each player is privately told her recommendation and the underlying game G is played, with the leaders in L \ π sticking to their recommendations.

Remark 1. The agreement stage of an SG can be represented as a sequential (i.e., tree-form) game involving the leaders. In such game, the players play in turn, according to some fixed order, with only two actions available at each decision point: OPT-IN and OPT-OUT. When a player chooses OPTOUT, then she never plays anymore. The game ends after a sequence of OPT-IN actions performed by all leaders who have not selected OPT-OUT yet. Thus, each leaf of the game corresponds to the ordered subset π ∈ ΠL representing the sequence of leaders who performed OPT-OUT on the path to the leaf. Players' payoffs are defined by up(xπ) for p ∈ L. See Figure 1 (Right) for an example of sequential-gamerepresentation of the agreement stage.

Next, we introduce some desirable properties that the distributions of the correlation device should satisfy. In the following definitions, we assume that an SG (G, L, F ) is given.

First, we introduce stability. In words, we require that the leaders in L do not have any incentive to become followers. We introduce two different notions of stability, as follows.

Definition 5. Given x = [xπ] ∈ X, for any π ∈ ΠL, xπ is stable if, for every p ∈ L \ π, up(xπ) ≥ up(xπp). Moreover:

• x is perfectly stable if xπ is stable for every π ∈ ΠL.
• x is stable if x∅ is stable;

We denote with XS ⊆ X and XPS ⊆ X the sets of stable and perfectly stable distributions, respectively.

Remark 2. The rationale behind stability is that of NE. Indeed, x ∈ X is stable if and only if each leader playing OPTIN is an NE of the sequential game representing the agreement stage. Intuitively, this is because, if x ∈ X is stable, each leader must not have any incentive to play OPT-OUT given that the other leaders always play OPT-IN.

3 We assume that the leaders are asked to take a decision according to some ordering, e.g., p ∈ L decides before q ∈ L if p < q.

4 The agreement stage is finite as there are at most |L| rounds and each round involves at most |L| decisions.

5 Our results do not rely on the protocol implemented in the agreement stage. Others could be adopted, with the only requirement that they must record in which order the leaders do OPT-OUT.

Remark 3. The rationale behind perfect stability is that of subgame perfection. Indeed, x ∈ X is perfectly stable if and only if each leader playing OPT-IN is a subgame perfect equilibrium of the agreement stage. The reason is that perfect stability requires that playing OPT-IN is optimal at any decision point of the sequential game.

The second property that we look for is efficiency. We require that the correlated distributions of the correlation device are Pareto optimal with respect to the utility functions of the leaders who decided to OPT-IN. Given X′ ⊆ X, for π ∈ ΠL, we use PL\π(X′ ) to denote the set of Pareto optimal correlated distributions in the set {x′π | x′ = [x′π ] ∈ X′ }, where the objectives are the functions up, for p ∈ L \ π. Formally:

Definition 6. Given x = [xπ] ∈ X′ ⊆ X, for any π ∈ ΠL, xπ is efficient on the set X′ if xπ ∈ PL\π(X′ ). Moreover:

• x is perfectly efficient on X′ if xπ is efficient on X′ for every π ∈ ΠL.
• x is efficient on X′ if x∅ is efficient on X′ ;

We introduce three different solution concepts for our SGs, which we refer to as Stackelberg correlated equilibria (SCEs). They differ on the types of stability and efficiency that they prescribe. Formally:

Definition 7. Given an SG (G, L, F ), x ∈ X is an:

• SCE if it is efficient on the set XS ;
• SCEwith perfect agreement (SCE-PA) if it is efficient on the set XPS ;
• SCE with perfect agreement and perfect efficiency (SCE-PAPE) if it is perfectly efficient on the set XPS .

We denote with XSCE , XSCE-PA , and XSCE-PAPE the sets of SCEs, SCE-PAs, and SCE-PAPEs, respectively.

Example 1. Consider the SG in Figure 1, where L = {1, 2} and F = ∅. Let x = [xπ] be such that x∅(s1,1, s2,1) = 1, x{2}(s1,5, s2,1) = 1, and xπ(s1,1, s2,2) = 1 for all the other π ∈ ΠL. Clearly, xπ ∈ X CE π for all π ∈ ΠL. Moreover, being x∅ stable and Pareto optimal, x is an SCE. Observe that, if player 2 performs OPT-OUT, x prescribes an irrational behavior to player 1, as u1(x{2}) = 0, while she gets 1 by doing OPT-OUT. Thus, x is not perfectly stable, as playing OPT-IN must be optimal at any decision point of the agreement stage. For instance, x′ = [x′π ] with x′∅(s1,2, s2,1) = 1 and x′π (s1,3, s2,2) = 1 for every other π ∈ ΠL is an SCEPA. However, notice that x′ is not an SCE-PAPE since x′{2} does not maximize player 1's utility. Instead, x′′ = [x′′π ] with x′′∅(s1,4, s2,1) = 1, x′′ {2} (s1,3, s2,1), and x′′π (s1,4, s2,2) = 1 for all the other π ∈ ΠL is an SCE-PAPE.

4 On the Existence of SCEs

We investigate the existence of our solution concepts in general SGs. We show that SCEs and SCE-PAs always exist, while we provide an SG where there is no SCE-PAPE.

The fundamental step for proving our existence results (Theorem 1) is to show that (i) XS and XPS are polytopes, x{2}

1

x{2,1}

Table 1: Three-player normal-form SG with no SCE-PAPE (players 1, 2, and 3 select rows, columns, and matrices, respectively).

and (ii) they are non-empty. The latter point is a direct consequence of the fact that all vectors x = [xπ] ∈ X with xπ = x for some CE x ∈ X CE are perfectly stable.

Theorem 1. Every SG admits an SCE and an SCE-PA.

Proposition 1. There are SGs with no SCE-PAPE.

Proof sketch. Consider the SG in Table 1, where L = {1, 2, 3} and F = ∅. Any x = [xπ] ∈ XSCE-PAPE must be such that, for every xπ with player 3 in π, u3(xπ) = 1 (as player 3 always gets 1 by deviating to s3,3). Given the definition of stability and player 3's incentive constraints, x{1,2} and x{2,1} must always recommend s3,3 to player 3. Moreover, by stability and efficiency, x{1} must always recommend (s1,1, s2,2, s3,2), where player 1 gets a utility of 2. Similarly, x{2} must always recommend (s1,2, s2,2, s3,1) and, thus, player 2 receives a utility of 2. Thus, for stability, x∅ must satisfy u1(x∅), u2(x∅) ≥ 2, which is impossible.

As a result, in the rest of this work we focus on SCEs and SCE-PAs. We remark that the non-existence of SCE-PAPEs implies that, under the requirements of perfect stability and perfect efficiency, there cannot be an agreement involving all the leaders. This does not rule out the possibility that some subsets of leaders can still reach an agreement. However, these cases are much more involved, as the actual group of leaders reaching an agreement inevitably depends on the rules of the protocol implemented in the agreement stage.

5 SCEs and Other Solution Concepts

We show that the optimal correlated strategies to commit to introduced by Conitzer and Korzhyk [2011] are a special case of SCEs. Intuitively, in single-leader SGs, efficiency is equivalent to the maximization of leader's utility, while stability does not enforce additional constraints on the commitment.

Theorem 2. Given an SG (G, {1}, N\{1}), it holds XSCE = XSCE-PA = XSCE-PAPE and, given some x = [xπ] ∈ XSCE , x∅ is an optimal correlated strategy to commit to.

Proof sketch. Since the SG has only one leader (player 1), XS = XPS , and, thus, XSCE = XSCE-PA . For the same reasons, XSCE-PA = XSCE-PAPE . Moreover, Pareto optimality is the same as maximizing the leader's utility function u1. Let x = [xπ] ∈ XSCE and assume, by contradiction, that x∅ is not an optimal correlated strategy to commit to. Then, there would be another ˆx ∈ X CE N\{1} such that u1(ˆx) ≥ u1(x∅). However, replacing x∅ with ˆx in x would give us another ˆx ∈ XS , contradicting the efficiency of x.

Given the relation between optimal correlated strategies to commit to and SEs in single-leader single-follower SGs:

Corollary 2.1. Given an SG (G, {1}, {2}), any x = [xπ] ∈ XSCE is such that u1(x∅) is the leader's utility in an SE.

For the relationships of SCEs with other non-Stackelberg solution concepts, see [Castiglioni et al., 2019].

6 Computational Complexity of SCEs

We study the computational complexity of SCEs and SCEPAs in general SGs. We distinguish between the problem of finding an equilibrium and that of computing an optimal equilibrium, i.e., one maximizing a specific given linear function of leaders' utilities, such as the leader's social welfare. We introduce the following formal definitions (problems f-SCEPA and o-SCE-PA(λ) are defined analogously for SCE-PAs).

Definition 8 (f-SCE). Given an SG (G, L, F ), find an SCE. Definition 9 (o-SCE(λ)). Given an SG (G,L, F) and λ = [λp] ∈ [0, 1]|L| , find an SCE x = [xπ] ∈ XSCE maximizing

the objective function fλ = ∑p∈L ∑s∈S λpup(s)x∅(s).

Let us remark that, in general, the size of a vector x ∈ X is factorial in the number of players. Thus, in the following, we assume that there is some compact representation for x. 6

We establish a tight connection between our problems and an auxiliary one, which is a generalization of the problem of finding an optimal CE. In the rest of the section, we assume to have access to an oracle solving this auxiliary problem, which we call stability oracle. In Section 7, we then investigate for which games the oracle can be efficiently implemented.

Definition 10. A stability oracle O(G, c,L, {xp}p∈L′⊆L) is an algorithm that, given a finite game G, a coefficients vector c = [cp] ∈ [-1, 1]n , a set of leaders L ⊆ N, and a collection of correlated distributions xp ∈ X for p ∈ L′ ⊆ L, returns an x ∈ X CE N\L maximizing ∑p∈N ∑s∈S cpup(s)x(s) subject to the stability constraints, i.e., up(x) ≥ up(xp) for all p ∈ L′ . 7

In the following, we are interested in games where the stability oracle runs in polynomial time. Thus, we assume that O always returns a correlated distribution with size polynomial in the size of the game. 8 We also consider the decision form of the stability oracle, which reads as follows:

6 As we see next, for all our positive results we can safely assume that there is a compact representation for x ∈ X (e.g., x only requires a polynomial number of polynomially-sized distributions).

7 Note that, given a finite game G, O(G, c, ∅, ∅) returns an optimal CE x ∈ X CE for the objective function defined by c ∈ [0, 1]n .

8 Indeed, this assumption is not restrictive, as all the games we study in Section 7 admit a poly-time oracle O with this property.

Definition 11. The decision form of a stability oracle O is an algorithm OD (x, L, {xp}p∈L′⊆L) that, given x ∈ X , L ⊆ N, and xp ∈ X for p ∈ L′ ⊆ L, answers YES if x ∈ X CE N\L and x satisfies the stability constraints, and NO otherwise.

In the following, given L ⊆ N and λ = [λp] ∈ [0, 1]|L| , we let cλ = [cλ,p] ∈ [0, 1]n be such that cλ,p = λp if p ∈ L, while cλ,p = 0 if not. Moreover, given p ∈ N, we let cp = [cp,q] ∈ [0, 1]n be such that cp,p = -1 and cp,q = 0 for all q ∈ N \ {p}. Note that cλ is the coefficients vector of the objective fλ, while cp corresponds to minimizing up.

6.1 Computing SCEs

We show that, in games admitting a polynomial-time stability oracle, an optimal SCE can be computed in polynomial time. Intuitively, o-SCE(λ) is solved by x = [xπ] computed as: x{p} = O(G, cp,L \ {p},∅) for p ∈ L, x∅ = O(G, cλ,L, {x{p}}p∈L), and xπ = O(G, cλ,∅,∅) for every other ordered subset π ∈ ΠL. Formally:

Theorem 3. Given an SG (G,L, F) and λ ∈ [0, 1]|L| , oSCE(λ) can be solved with |L| + 2 queries to an oracle O.

Corollary 3.1. Given an SG (G, L, F), if there is a poly-time oracle O, then o-SCE(λ) can be solved in polynomial time.

6.2 Computing SCE-PAs

First, we provide a positive result: one can find an SCE-PA with polynomially many invocations to a stability oracle. It is sufficient to compute x = [xπ] where x{p} = O(G, cp, ∅, ∅) for p ∈ L and x∅ = O(G, cλ, L, {x{p}}p∈L). Thus:

Theorem 4. Given an SG (G,L, F), f-SCE-PA can be solved with |L| + 1 queries to an oracle O.

Corollary 4.1. Given an SG (G, L, F), if there is a poly-time oracle O, then f-SCE-PA can be solved in polynomial time.

Now, we switch to the problem of computing an optimal SCE-PA, showing that it cannot be solved efficiently, even with access to a polynomial-time stability oracle. Specifically, we prove a stronger negative result: even the easier problem of verifying the perfect stability of a given x ∈ X is computationally intractable. Our statement is based on a reduction from the coNP-complete problem of deciding whether a given formula in disjunctive normal form (DNF) is a tautology or not [Arora and Barak, 2009].

Theorem 5. Given an SG (G,L, F) and x ∈ X, verifying whether x ∈ or ̸∈ XPS is not in P unless NP = coNP, even with access to a polynomial-time decision-form oracle OD .

Proof sketch. Given a formula Φ in DNF, we construct an SG (G, L, F) involving a leader pv for each variable v ∈ V and a single follower pf . Each pv has two actions, sT and sF, which define the truth value of v. As a result, any s ∈ S corresponds to a truth assignment τ s defined by leaders' strategies. The follower has a strategy sv for each variable v ∈ V . Table 2 reports the leaders' utilities (the follower always gets 0). We build x = [xπ] ∈ X with x∅(s) = 1 for some s ∈ S such that spv = sT for all v ∈ V . Furthermore, for every v ∈ V and π ∈ ΠL\{pv}, we let xπpv (s) = 1 for s ∈ S with sp = sF for all p ∈ πpv, sp = sT for all p ∈ L \ πpv, and spf = sv.

If. Suppose Φ is a tautology. For every π ∈ ΠL, xπ recommends all the leaders in π to play sF. Note that, for every v ∈ V and π ∈ ΠL\{pv}, upv (xπ) = #F(τ s ) = |π|, while, if pv decides to OPT-OUT, she is recommended to play sF (one more variable is set to false) and, being spf = sv, she gets the same utility. As a result, all distributions xπ are stable.

that Φ(τ s ) = F. If spv = sT for every v ∈ V , then x∅ is not stable as the leaders would OPT-OUT (getting at least 0 > -1). Otherwise, there exists s′ ∈ S such that Φ(τ s′ ) = T and xπ(s′ ) = 1, xπpv (s) = 1 for some v ∈ V , π ∈ ΠL\{pv}. Then, upv (xπ) = #F(τ s′ ) = |π| and upv (xπpv ) = |V | > |π|. Thus, xπ is not stable, as leader pv would OPT-OUT.

Only if. Suppose Φ is not a tautology. Let s ∈ S be such

As a byproduct of Theorem 3 we have that, when looking for optimal SCEs, one can restrict the attention to those x ∈ X admitting a representation whose size is polynomial in the size of the game. For Theorem 4, the same holds when searching for an SCE-PA. However, Theorem 5 implies that optimal SCE-PAs require an exponential number of different distributions. Moreover, even when x ∈ X can be easily represented in a compact form (as in the proof of Theorem 5), we cannot check in polynomial time whether x ∈ XPS or not.

This poses a new intriguing question: can we restrict the attention to x ∈ X whose size is less than factorial in the number of players? We show that the answer is positive. It is sufficient to consider x ∈ X whose size is exponential in the number of players, as only the unordered set of defecting leaders and the last of them who decided to OPT-OUT matter.

Theorem 6. Given an SG (G,L, F) and x = [xπ] ∈ XPS , there is an x′ = [x′π ] ∈ XPS s.t. x′∅ = x∅ and x′πp = x′π′ p for every p ∈ L and π, π′ ∈ ΠL\{p} defining the same set.

Theorem 6 allows us to reduce the number of queries to a stability oracle that are necessary to find an optimal SCE-PA.

Theorem 7. Given an SG (G,L, F) and λ ∈ [0, 1]|L| , oSCE-PA(λ) can be solved with |L|2|L|-1 + 1 queries to O.

Finally, we can provide an example showing that Theorem 7 is tight, which leads to the following proposition.

Proposition 2. Solving o-SCE-PA(λ) requires to take into account the last player who performed OPT-OUT, while focusing only on the set of defecting leaders is not sufficient.

9 We remark that, for normal-form games, a polynomial-time stability oracle O can be implemented by using a variation of the LP for finding optimal CEs [Shoham and Leyton-Brown, 2008].

7 Stability Oracle for Compact Games

We study which classes of games admit a polynomial-time stability oracle O, focusing on those with polynomial type. 9 We only provide our main final result; a detailed description of all the ancillary results is in [Castiglioni et al., 2019].

Inspired by the classical approaches for finding CEs in games with polynomial type [Papadimitriou and Roughgarden, 2008; Jiang and Leyton-Brown, 2011; 2015], we solve O(G, c,L, {xp}p∈L′⊆L) in polynomial time using the ellipsoid method. This requires that a suitably defined separation problem (Sep(z, t)) can be computed in polynomial time. Our main result is that Sep(z, t) can be reduced to the weighted deviation-adjusted social welfare problem (w-DaSW(y, v, t)) introduced by Jiang and LeytonBrown [2011] for finding an optimal (according to some linear function of players' utilities) CE. This establishes a strict connection between the problem solved by our stability oracle and that of computing optimal CEs. As a consequence, given the results of Jiang and Leyton-Brown [2011], O can be computed in polynomial time for all the compact games where finding an optimal CE is computationally tractable. Thus:

Theorem 8. The following games admit a polynomial-time stability oracle O: anonymous games, symmetric games, and bounded-treewidth graphical and polymatrix games.

Finally, our results also imply that the polynomial-time stability oracle O always outputs a polynomially-sized distribution (see [Castiglioni et al., 2019, Corollary 11.1]).

8 Discussion

This paper introduces a new way to apply the Stackelberg paradigm to any (underlying) finite game. Differently from previous works, our approach deals with scenarios involving multiple leaders by introducing a preliminary agreement stage in which each leader can decide whether to be a leader or become a follower. We introduce and study three natural solution concepts that differ depending on the properties that they require on the agreement stage (others, e.g., requiring stability and perfect efficiency, will be explored in future).

Our equilibria generalize the optimal correlated strategies to commit to introduced by Conitzer and Korzhyk [2011] for single-leader multi-follower Stackelberg games. At the same time, they also provide a significant advancement over the multi-leader solution concepts introduced in the security context (see, e.g., [Gan et al., 2018]). First, correlated-strategy commitments are more natural than leaders' strategies satisfying some Nash-like constraints. Second, our equilibria are funded on strong game-theoretic groundings, as they are guaranteed to exist independently of the game structure. Last but not least our solutions apply to general games.

Finally, our computational findings exploit a general framework relying on a game-independent stability oracle. Thus, our positive results can be extended to other game classes by simply designing polynomial-time oracles.

Acknowledgments

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