Trembling-Hand Perfection in Extensive-Form Games with Commitment

1 Introduction

In interactions, it can make a significant difference if one player can commit to a strategy first. This was originally studied in the context of using pure strategies to commit to quantity [Cournot, 1838] or price [Bertrand, 1883] in deterring market entry [von Stackelberg, 1934]. Further power can be gained by committing to a mixed (i.e., randomized) strategy [Conitzer and Sandholm, 2006; von Stengel and Zamir, 2010]. In a mixed Stackelberg equilibrium (SE), a leader commits to a (potentially mixed) strategy, and a follower then best responds. When multiple follower actions are bestresponses, tie-breaking needs to be considered. Two notable cases are the strong (i.e., optimistic) SE (SSE) and weak (i.e., pessimistic) SE (WSE), in which the follower breaks ties to maximize or minimize, respectively, the leader's utility [Breton et al., 1988]. The SE is now a well-known solution concept in game theory, and has been deployed to practical settings such as airport patrol scheduling, air marshal allocation to flights, and train security [Tambe, 2011; Yin et al., 2012]. Usually, these scenarios are modeled as specialized classes of normal-form games, and an SSE is sought. An SSE and a WSE in 2-player normal-form games can be found in polynomial time [Conitzer and Sandholm, 2006; von Stengel and Zamir, 2010]. This is Poly-APXcomplete in Bayesian games when the number of types is not fixed [De Nittis et al., 2018].

The Stackelberg paradigm can also be applied to extensiveform games (EFGs). EFGs can provide a richer description of a strategic situation. They can be used to model sequential multi-step settings, such as patrol scheduling with interaction between patrols and adversaries. Letchford and Conitzer [2010] show that finding an SSE in an EFG is NPhard. Furthermore, because Bayesian games are a special case of EFGs with Nature moves the results of De Nittis et al. [2018] imply Poly-APX hardness for EFGs with Nature moves as well. Worst-case exponential-time algorithms have been developed for computing an SSE [Boˇsansk`y and Cermak, 2015; Kroer and Sandholm, 2015; Cermak et al., 2016]. Kroer et al. [2018] propose robust SEs, where a solution is found against the worst-case follower's utility model.

In this paper we extend the extensive-form Stackelberg paradigm to settings where players might take offequilibrium actions with low-but-non-zero probability (a.k.a. trembles). Trembles are common in other types of games for refining solution concepts to play well even in parts of the game tree that are reached only through one or more mistakes [van Damme, 1991]. Trembles that cause every information set of the game to be reached with positive probability guarantee off-equilibrium-path optimality. In extensive-form games, the two best-known trembling-hand-perfection-based refinements of Nash equilibrium (NE) are the quasi-perfect equilibrium (QPE) [van Damme, 1984], where players play their best response at every information set taking into account only the future trembles of the opponent(s), and the extensive-form perfect equilibrium (EFPE) [Selten, 1975], in which they account for future trembles of themselves also. 1

SEs, including SSEs and WSEs, may be suboptimal in presence of trembles. In particular, an SE may be suboptimal due to a leader's mistake (Fig. 1(a)), a follower's mistake (Fig. 1(b)), or both (Fig. 1(c)). The robust SE of Kroer et al. [2018] does not guard against trembles either. Consider the game in Fig. 1(b): the leader should commit to (a1ℓ , a4ℓ ) in order to get utility 10. However, (a1ℓ , a3ℓ ) also achieves utility 10, but it is a worse strategy when trembles may happen. Adding payoff uncertainty on the (1, 0)-payoff node such that the follower has a utility function where she picks a1f does not solve this problem. The robust solution would pick a2ℓ initially, since the worst-case follower picks a1f . In contrast, our perturbed SEs will uniquely identify (a1ℓ , a4ℓ ) as the solution.

1 A further NE refinement, defined on the normal form and known as the normal-form perfect equilibrium (NFPE), does not guarantee off-equilibrium-path optimality. The same holds for SE: in Fig. 1(c), when uniform trembles are applied over the normal-form actions, an SE requires players to pick a1ℓ , while the only optimal choice is a2ℓ .

Contributions of this paper. We extend the extensiveform Stackelberg paradigm to settings where players might tremble. We show that for every perturbation scheme, the set of limit points of SEs for perturbed games with vanishing perturbations is always a nonempty subset of the SEs of the nonperturbed game. This does not hold when focusing only on SSEs (or WSEs): for a given game, the set of SSEs (or WSEs) in the non-perturbed game may be disjoint from the set of limit points of SSEs (or WSEs) in the perturbed game. We resort to the perturbation schemes used for QPEs and EFPEs to define quasi-perfect SEs (QP-SEs) and extensive-form perfect SEs (EFP-SEs)-and their strong and weak versions-as refinements of SE in which, at every information set, the follower plays a best response and the leader's commitment is optimal. We prove that the sets of SSEs and QP-SSEs may be disjoint and that the same holds for the sets of SSEs and EFP-SSEs and for the sets of WSEs and EFP-WSEs. Furthermore, we show that the problem of deciding the existence of an SE-refined or not-that gives the leader expected value at least ν is NP-hard.

2 Preliminaries

Following the notation in the textbook by Shoham and Leyton-Brown [2008], we define a Stackelberg extensiveform game (SEFG) with imperfect information as a tuple (N,H,Z,A, ρ, χ, uℓ, uf , Iℓ, If), where: N = {ℓ, f} is the set of players (ℓ being the leader and f the follower), H = Hℓ ∪Hf , with Hℓ and Hf being finite sets of leader's and follower's nonterminal decision nodes, respectively, Z is a finite set of terminal nodes, A is a finite set of actions, ρ : H → 2A is the action function that assigns to each nonterminal node a set of available actions, χ : H ×A → H ∪Z is the successor function that defines the node that is reached when an action is performed in a nonterminal node (if possible), uℓ and uf , with uℓ, uf : Z → R, specify the leader's and follower's payoffs, respectively, in each terminal node, and Iℓ and If define a partition of Hℓ and Hf , respectively, into information sets, i.e., groups of nonterminal nodes that are indistinguishable by the player. For every player i ∈ N, information set Ii ∈ Ii, and nonterminal nodes h, h′ ∈ Ii, it must be the case that ρ(h) = ρ(h′ ), otherwise the nodes in Ii would not be indistinguishable for player i. Therefore, we can overload notation and let ρ(Ii) be the set of actions available to player i in all nodes belonging to Ii ∈ Ii. Moreover, we focus on perfectrecall games in which no player forgets what she did or knew in the past, i.e., for every i ∈ N and Ii ∈ Ii, all decision nodes belonging to Ii share the same sequence of player i's moves on their paths from the root.

In an imperfect-information extensive-form game, a player's pure strategy (akin to a contingent plan in AI terminology) specifies an action at each information set in which it is the player's turn to move. A mixed strategy is a probability distribution over a player's pure strategies. In games with perfect recall, we can restrict the attention to behavioral strategies [Kuhn, 1953], which define, for every player i ∈ N and information set Ii ∈ Ii, a probability distribution over the actions ρ(Ii) available at Ii. For every i ∈ N, let βi be a player i's behavioral strategy, where βi : Ii ∈ Ii ↦→ ∆(ρ(Ii)). For simplicity, we use βi(a) to denote the probability that βi assigns to action a ∈ A. In the following, we overload the notation and use ui(βℓ, βf ) to denote player i's expected utility when βℓ and βf are played.

Perfect-recall extensive-form games admit an equivalent representation, the sequence form [Romanovskii, 1962; Koller et al., 1996; von Stengel, 1996]. A sequence for player i ∈ N, defined by a node h ∈ H ∪ Z, is the ordered set of player i's actions on the path from the root to h. Let Qℓ and Qf be the sets of leader's and follower's sequences, respectively. As usual, we assume that each Qi, for i ∈ N, contains a fictitious sequence q∅ that corresponds to the root node. Moreover, given a sequence q ∈ Qi and an action a ∈ A, we denote as qa the extended sequence obtained by appending a to q. With an overloading of notation, uℓ and uf , with uℓ, uf : Qℓ × Qf → R, denote players' utilities in the sequence form, i.e., uℓ(qℓ, qf) and uf(qℓ, qf) are the leader's and the follower's payoff, respectively, in the terminal node reached when playing the actions in qℓ and qf . If qℓ and qf do not identify a terminal node, then uℓ(qℓ, qf) and uf(qℓ, qf) are assumed to be zero. In the sequence form, a strategy, called a realization plan, assigns each sequence with its probability of being played. For i ∈ N, let ri : Qi → R be a player i's realization plan. In order to be well-defined, a realization plan ri must be such that ri(q∅) = 1 and, for every Ii ∈ Ii and sequence q leading to Ii, ri(q) = ∑a∈ρ(Ii) ri(qa). In the following, we denote with L and F the strategy polytopes of all leader's and follower's realization plans, respectively. Overloading the notation, we use ui as if it were defined over L × F instead of Qℓ × Qf , denoting player i's expected utility.

Given a realization plan ri, we can easily recover an equivalent behavioral strategy βi by setting βi(a) = ri(qa) ri(q) , where q is the sequence leading to the information set in which a is played. The equivalence is in terms of probabilities that the two strategies induce on terminal nodes. Similarly, every βi has an equivalent ri.

Stackelberg solution concepts. A Stackelberg equilibrium prescribes the leader to commit to a utility-maximizing strategy, given that the follower best-responds to it. Given any strategy for the leader, rℓ ∈ L, a best response for the follower is any strategy rf ∈ F that maximizes uf(rℓ, rf) = ∑qℓ∈Qℓ,qf∈Qf rℓ(qℓ)rf(qf)uf(qℓ, qf). Let BR(rℓ) = argmaxrf∈F uf(rℓ, rf) be the set of follower's best-responses to rℓ ∈ L. If there are multiple follower best responses to the leader's strategy, in order for the leader to determine an optimal commitment, the leader needs to make an assumption about which one of the follower's best responses the follower will choose. A follower response function specifies how the follower responds to any possible (mixed) strategy of the leader.

Definition 1. A follower response function is a function τ : L → F such that τ(rℓ) ∈ BR(rℓ) for all rℓ ∈ L.

• strong (i.e., optimistic) follower response functions τ st break ties in favor of the leader: uℓ(rℓ, τ st (rℓ)) ≥ uℓ(rℓ, rf ) ∀rf ∈ BR(rℓ), rℓ ∈ L;

Two classes of follower response functions are popular in the literature [von Stengel and Zamir, 2010]:

• weak (i.e., pessimistic) follower response functions τ we break ties to minimize the leader's utility: uℓ(rℓ, τ we (rℓ)) ≤ uℓ(rℓ, rf ) ∀rf ∈ BR(rℓ), rℓ ∈ L.

We formally define the concept of Stackelberg equilibrium.

Definition 2. Given an SEFG and a follower response function τ, a τ-Stackelberg equilibrium (τ-SE), if it exists, is any leader-utility-maximizing strategy profile, that is, any (rℓ, τ(rℓ)) ∈ L × F such that uℓ(r′ℓ , τ(r′ℓ )) ≤ uℓ(rℓ, τ(rℓ)) for all r′ℓ ∈ L.

Definition 3. Given an SEFG, (rℓ, rf ) is a Stackelberg equilibrium (SE) if there exists a follower response function τ such that (rℓ, rf) is a τ-SE.

The following are two well-known examples of SEs.

Definition 4. A strong Stackelberg equilibrium (SSE) is a τ st - SE. 2 A weak Stackelberg equilibrium (WSE) is a τ we -SE.

It is known that an SSE always exists, while a WSE might not exist [von Stengel and Zamir, 2010].

3 Game Perturbation Schemes

As discussed in the introduction, many of the most important Nash equilibrium refinement concepts are based on the idea that the player and/or opponent makes mistakes at every decision point (i.e., information set) with some small, vanishing probability. In this section, we introduce a more general family of such perturbation, of which the typical prior schemes, EFPEs and QPEs, are subfamilies. Then in the following sections we develop theory for the whole family and the subfamilies in the context of Stackelberg extensive-form games. 3

2 Some authors only mean SSE when they talk about Stackelberg equilibrium [Boˇsansk`y et al., 2017].

3 Our perturbation family applies to any strategy polytope, not just Stackelberg extensive-form games, and not even just the se-

In the following definition, X is any strategy polytope, where no distinction is made based on to which player the polytope belongs.

Definition 5. An ϵ-perturbation scheme for a strategy polytope X is a function ϵ ↦→ X(ϵ) defined over ϵ ∈ (0, 1] such that

• X(ϵ) ⊆ X(ϵ′ ) for all ϵ ≥ ϵ′ , and

The closure operation cl(·) assumes that a topology is defined for the space containing X. We will always assume that the strategy polytopes X live in a Euclidean space where the usual metric induces open balls Bδ(¯x) = {x : ‖x - ¯x‖ < δ}. The classic EFPE- and QPE-type perturbations (which we define formally in the next section) are two notable subfamilies of ϵ-perturbation schemes.

• cl(⋃ϵ∈(0,1] X(ϵ)) =X.

As a direct consequence of the conditions in Definition 5, every point in X is eventually "reached" by X(ϵ) when ϵ is small enough:

Lemma 1. Given ¯x ∈ X and δ > 0, there exists ˆx ∈ X and ¯ ϵ ∈ (0, 1] such that ˆx ∈ X(ϵ) ∩ Bδ(¯x) for all ϵ ≤ ¯ ϵ.

A perturbed Stackelberg game is now simply an SEFG augmented with a perturbation scheme for each player:

Definition 6. A perturbed SEFG is an SEFG, together with two ϵ-perturbation schemes ϵ ↦→ L(ϵ) and ϵ ↦→ F(ϵ) for the leader's and the follower's strategy polytope, respectively.

Given a perturbed SEFG (Γ, ϵ ↦→ L(ϵ), ϵ ↦→ F (ϵ)), we denote by Γ(ϵ) the SEFG obtained from Γ by letting the leader and follower strategy polytopes be L(ϵ) and F(ϵ), respectively.

4 EFP and QP Perturbations

In this section we analyze perturbed SEFGs with EFPEand QPE-type perturbations. They are SEFG ϵ-perturbation schemes with specific structure.

In an EFP-ϵ-perturbation scheme, each player takes into account the possibility that all players, including herself, may make mistakes in the future. Players are constrained to placing at least a minimum probability α on every action at each information set, and those lower bounds α are functions of ϵ that go to zero as ϵ → 0. A formal definition, using sequenceform strategy polytopes, follows.

Definition 7. An EFP-ϵ-perturbation scheme for a sequenceform strategy polytope X is an ϵ-perturbation scheme ϵ ↦→ XEFP (ϵ) where a strategy r belongs to XEFP (ϵ) if

• r(q) ≥ α(q, ϵ)r(q′ ) ∀ q, q′ ∈ Q : q = q′a;
• ∑q∈Q|q=q′ a α(q, ϵ) ≤ 1 ∀ q′ ∈ Q.
• α(q, ϵ) ≥ 0 ∀ q ∈ Q and limϵ→0 α(q, ϵ) = 0 ∀ q ∈ Q;

In a QP-ϵ-perturbation scheme, each player takes into consideration only the possibility of opponent's errors, assuming she will not make mistakes in future. This is modeled by requiring that sequences q be played with probabilities at least ω(q, ϵ), which are polynomials of ϵ whose degrees increase as sequences are extended with additional actions. Formally:

quence form. That said, in this paper, we assume that the game is in sequence form.

Definition 8. A QP-ϵ-perturbation scheme for a sequenceform strategy polytope X is an ϵ-perturbation scheme ϵ ↦→ XQP (ϵ) where a strategy r belongs to XQP (ϵ) if

• r(q) ≥ ω(q, ϵ) ∀ q ∈ Q;
• maxdegω(q′ , ϵ) < mindegω(q, ϵ) ∀q, q′ ∈ Q : q = q′a.
• ω(q, ϵ) ≥ 0 ∀ q ∈ Q and limϵ→0 ω(q, ϵ) = 0 ∀ q ∈ Q;

Now, we introduce new solution concepts defined as limit points of sequences of SSEs and WSEs for perturbed game instances Γ(ϵ) as ϵ → 0, given particular perturbation schemes.

Definition 9. Given a perturbed SEFG (Γ, ϵ ↦→ LEFP (ϵ), ϵ ↦→ F EFP (ϵ)), (rℓ, rf) is an EFP-SSE (resp., EFP-WSE) if it is a limit point of SSEs (resp., WSEs) of Γ(ϵ) as ϵ → 0.

Definition 10. Given a perturbed SEFG (Γ, ϵ ↦→ LQP (ϵ), ϵ ↦→ F QP (ϵ)), (rℓ, rf ) is a QP-SSE (resp., QP-WSE) if it is a limit point of SSEs (resp., WSEs) of Γ(ϵ) as ϵ → 0.

Since SSEs always exist in an SEFG, and since the strategy spaces are compact sets, EFP-SSEs and QP-SSEs always exist. The same is not true for EFP- and QP-WSEs, as a WSE need not exist in an SEFG.

The following observation shows that the sets of EFP- or QP-SSEs can be disjoint from the set of SSEs, thereby showing that the EFP- and QP-SSE solution concepts are not refinements of the SSE solution concept!

Observation 1. There are perturbed SEFGs in which an EFP-SSE is not an SSE, a QP-SSE is not an SSE, and an EFP-WSE is not a WSE.

Proof. Consider the game of Figure 2(a). The SSE prescribes the leader and the follower to play a1ℓ and a1f , respectively. On the other hand, in any perturbed instance the leader has to place positive probability on a2ℓ , and the follower's best response is a2f .

Consider the game of Figure 2(b). The follower plays a1f a3f , while in any perturbed instance resulting from an EFPϵ-perturbation scheme, the follower has to put positive probability on a4f and her best response at the root becomes a2f .

We leave as an open problem the determination of whether a QP-WSE is also a WSE (assuming it exists) or not.

5 Stackelberg Trembling-Hand Refinements

As we showed in the previous section, SSEs and WSEs are not refinable by trembling. In this section we remedy this problem by showing that the universal set of all Stackelberg equilibria is natural for trembling-hand perfection: it does not suffer from the problem above. In other words, the set of SEs is closed under trembling-hand refinement. Formally, we prove that any limit point of SEs for the perturbed game Γ(ϵ) as ϵ → 0 is an SE of the original, unperturbed SEFG Γ.

Theorem 1. Let {ϵi} → 0 and let {(rℓi, rf i )} be a sequence of SEs for the perturbed game instances {Γ(ϵi)}. Then:

• all limit points of {(rℓi, rf i )} are SEs.
• {(rℓi, rf i )} has at least one limit point, and

We now present three lemmas, and at the end of this section we present the proof of the theorem using these lemmas.

One can think of SEs as "minimally-rational" for the leader: any strategy for the leader is acceptable as long as there is no other strategy for the leader that is better no matter how the follower breaks ties. We now formalize this by giving the following alternative characterization of SEs.

Lemma 2. A strategy profile (rℓ, rf) is an SE if and only if rf ∈ BR(rℓ) and for all r′ℓ ∈ L there exists r′f (r′ℓ ) ∈ BR(r′ℓ ) such that uℓ(r′ℓ , r′f (r′ℓ )) ≤ uℓ(rℓ, rf ).

Proof. (⇐) Construct the follower response function τ defined as τ(rℓ) = rf and τ(r′ℓ ) = r′f (r′ℓ ). Then, for all r′ℓ ∈ L,

uℓ(rℓ, rf ).

uℓ(r′ℓ , τ(r′ℓ )) ≤ uℓ(rℓ, τ(rℓ)), and thus (rℓ, rf ) is a τ-SE. (⇒) Assume that (rℓ, rf) is a τ-SE. Then rf = τ(rℓ) ∈ BR(rℓ). Furthermore, by definition of τ-SE, for all r′ℓ ∈ L, r′f = τ(r′ℓ ) is such that uℓ(r′ℓ , r′f ) ≤ uℓ(rℓ, τ(rℓ)) =

Lemma 3. Let {ϵi} → 0 and let {(rℓi, rf i )} be a sequence of strategy profiles for the SEFG instances {Γ(ϵi)}. Then {(rℓi, rf i )} has at least one limit point.

Proof. The conclusion follows directly from the BolzanoWeierstrass theorem since L(ϵ) × F(ϵ) ⊆ L × F for all ϵ ∈ (0, 1] and L×F is a compact set.

Lemma 4. Let {ϵi} → 0 and let {(rℓi, rf i )} be a sequence of strategy profiles for the SEFG instances {Γ(ϵi)} where rf i is a best-response to rℓi. Then any limit point (¯ rℓ, ¯ rf) of {(rℓi, rf i )} is such that ¯ rf is a best-response to ¯ rℓ.

Proof. Existence of at least one limit point for {(rℓi, rf i )} is guaranteed by Lemma 3. Without loss of generality, assume that (rℓi, rf i ) → (¯ rℓ, ¯ rf) ∈ L × F. Suppose, for contradiction, that ¯ rf is not a best response to ¯ rℓ which means that there exists ˆ rf ∈ F such that uf(¯ rℓ, ˆ rf) > uf (¯ rℓ, ¯ rf). By continuity of uf , there exists δ > 0 such that uf(r> ℓ , r> f ) > uf(r< ℓ , r< f ) for all (r> ℓ , r> f ) ∈ Bδ(¯ rℓ) × Bδ(ˆ rf) and (r< ℓ , r< f ) ∈ Bδ(¯ rℓ) × Bδ(¯ rf). From Lemma 1 we know that there exist ¯ ϵ ∈ (0, 1] and ˜ rf such that ˜ rf ∈ F (ϵ) ∩ Bδ(ˆ rf) for all ϵ ≤ ¯ ϵ. Considering the three converging sequences ϵi → 0, rℓi → ¯ rℓ and rf i → ¯ rf , we know that there exists an index j ∈ N such that ϵj ≤ ¯ ϵ, rℓj ∈ Bδ(¯ rℓ), and rf j ∈ Bδ(¯ rf). Furthermore, from ϵj ≤ ¯ ϵ we deduce that (rℓj, ˜ rf ) ∈ L(ϵj) × F(¯ ϵ) ⊆ L(ϵj) × F(ϵj). Thus (rℓj , ˜ rf) is a valid strategy profile for Γ(ϵj). Yet, (rℓj, ˜ rf ) ∈ Bδ(¯ rℓ) × Bδ(ˆ rf ) and (rℓj , rf j ) ∈ Bδ(¯ rℓ) × Bδ(¯ rf), implying uf (rℓj , ˜ rf ) > uf (rℓj , rf j ) and contradicting the fact that rf j is a best response to rℓj.

Proof of Theorem 1. The first bullet is by Lemma 3. We now prove the second one. Let BRΓ(rℓ) and BRΓ(ϵi)(rℓ) be the sets of follower's best-responses to rℓ in Γ and Γ(ϵi), respectively. Without loss of generality, assume that {rℓi, rf i } → (¯ rℓ, ¯ rf) ∈ L× F. By Lemma 4, ¯ rf is a best response to ¯ rℓ. Therefore, by Lemma 2, we only need to prove that ∀r′ℓ there exists r′f ∈ BRΓ(r′ℓ ) with uℓ(r′ℓ , r′f ) ≤ uℓ(¯ rℓ, ¯ rf ).

Suppose for contradiction that there exists r′ℓ such that uℓ(r′ℓ , r′f ) > uℓ(¯ rℓ, ¯ rf) for all r′f ∈ BRΓ(r′ℓ ). Let gi be the family of functions with the property that, for all i, gi(rℓ) is equal to one of the rf ∈ BRΓ(ϵi)(rℓ) such that uℓ(rℓ, rf) ≤ uℓ(rℓi, rf i ); existence is guaranteed by Lemma 2 and the fact that (rℓi, rf i ) is an SE by hypothesis. Construct any sequence {(r′ℓi , r′f i )} → (r′ℓ , ˆ r′f ) such that (r′ℓi , r′f i ) are valid profiles for Γ(ϵi) with r′f i = gi(r′ℓi ). From Lemma 4 we know that ˆ r′f ∈ BRΓ(r′ℓ ). However, uℓ(r′ℓi , r′f i ) ≤ uℓ(rℓi, rf i ), and by continuity we have uℓ(r′ℓ , ˆ r′f ) ≤ uℓ(¯ rℓ, ¯ rf). But then ˆ r′f ∈ BRΓ(r′ℓ ) while having value no larger than uℓ(¯ rℓ, ¯ rf ), contradicting our assumption.

Remark. Because SSEs and WSEs are SEs, we have from Theorem 1 that the limit of perturbed SSEs (and perturbed WSEs when they exist) is guaranteed to be an SE. This means that, even though the limits are not SSEs or WSEs in general, they preserve minimal rationality of the commitment-as per Lemma 2.

6 Computational Complexity

In this section we study the computational complexity of deciding the existence of an SE (refined or not) that gives the leader expected value at least ν. This problem (in the unrefined case) is known to be polynomial in constant-sum settings, where all SEs give the same expected utility to the leader, equal to the value of the game. We show that this problem is NP-hard in general-sum settings, using a reduction from 3SAT. In particular, given a 3SAT formula, we construct a polynomially-large SEFG instance such that:

• If the 3SAT formula is satisfiable, all SEs of the SEFG give an expected utility of 1 to the leader.
• If the 3SAT formula is not satisfiable, all SEs of the SEFG give an expected utility strictly less than 1 to the leader. 4

Since the 3SAT decision problem is NP-hard [Garey and Johnson, 1979], this implies the following theorems.

Theorem 2. Deciding the existence of an SE (refined or not) that gives the leader expected value at least ν in an SEFG is NP-hard.

Theorem 3. Given a follower response function τ, deciding the existence of a τ-SE (refined or not) that gives the leader expected value at least ν in an SEFG is NP-hard.

4 Our reduction is based on the construction of Letchford and Conitzer [2010]. However, their construction only proves the NPhardness for the special case of SSEs, since, whenever the 3SAT formula is satisfiable, there are SEs of the SEFG that provide the leader with an expected utility strictly less than 1. We suitably modify players' payoffs so that the result holds for all SEs.

6.1 SEFG Instance Construction

Definition 11. We are given a 3SAT formula (C, V ), where C is a set of 3-literal clauses defined over a set V of variables, with |V | = n. We let the variable corresponding to literal lk be denoted by v(lk). We construct a perfect-recall SEFG Γ(C, V ) as follows:

• All nodes h1,x ℓ belong to I ∈ Iℓ. The available actions at the information set are ρ(I) = {avℓ : v ∈ V }.
• The root is h0f ∈ Hf such that ρ(h0f ) = {atf } ∪ {avf : v ∈ V } ∪ {aφf : φ ∈ C}, χ(h0f , axf ) = h1,x ℓ ∈ Hℓ.
• For all h1,v ℓ and awℓ (v,w ∈ V ), we let χ(h1,v ℓ , awℓ ) = zvw ∈ Z. Furthermore, uℓ(zvw) = 0, and uf(zvw) = ( n+2 (n+1)2 + 1) - 1{v = w}.
• For all h1,φ ℓ and avℓ (φ ∈ C, v ∈ V ), uℓ(zφv) = 0, uf (zφv) = 0, χ(h2,φv ℓ , av,x ℓ ) = zφvx ∈ Z, χ(h1,φ ℓ , avℓ ) = {h2,φv ℓ ∈ Iv if v is in φ zφv ∈ Z otherwise,
• For all avℓ (v ∈ V ), χ(h1,t ℓ , avℓ ) = h2,v f ∈ Hf , ρ(h2,v f ) = {av,T f , av,F f }, χ(h2,v f , av,x f ) = h3,vx ℓ ∈ Iv ∈ Iℓ, ρ(Iv) = {av,T ℓ , av,F ℓ }, χ(h3,vx ℓ , av,y ℓ ) = zvxy ∈ Z, uℓ(zvxy) = uf (zvxy) = 1{x = y}.

and uℓ(zφvx) = 0, uf (zφvT) = n+1 3 (resp., uf(zφvF) = n+1 3 ) if v appears negated (resp., not negated) in φ, uf (zφvx) = 0 otherwise.

Figure 3 shows an example of a game Γ(C, V ). Intuitively, the leader looks for a strategy such that the follower's bestresponse is to play action atf , thus achieving an expected utility of 1. The leader's strategy at information sets Iv (v ∈ V ) defines a truth assignment to the variables such that, whenever a clause φ ∈ C is not satisfied, then the follower bestresponds playing action aφf . Thus, the leader's goal is to find a strategy that defines a truth assignment satisfying all clauses. First we show that when the 3SAT formula is satisfiable there exists a leader's strategy that guarantees a payoff of 1.

Lemma 5. If (C, V ) is satisfiable, then there exists a leader's strategy βℓ such that for all follower's best-responses βf ∈ BR(βℓ) it holds uℓ(βℓ, βf ) = 1.

Proof. Let T be a truth assignment satisfying all clauses. Take βℓ such that βℓ(avℓ ) = 1n ∀ v ∈ V and βℓ(av,T ℓ ) = 1 if T (v) = T, while βℓ(av,F ℓ ) = 1 whenever T(v) = F. Clearly, at each node h2,v f , the unique follower's best-response is to play the action corresponding to that played by the leader in Iv. As a result, the follower gets a utility of 1 by playing atf at the root, i.e, uf(βℓ, atf ) = 1. Now, let us prove that playing action atf at the root is the unique follower's best-response to βℓ. Let us consider actions avf , for all v ∈ V , we have:

Thus, playing avf is not a best-response, for all v ∈ V . Now, we analyze actions aφf , for all φ ∈ C. Since T satisfies all clauses, each clause φ ∈ C has a literal lk that is true under T and, thus, βℓ(av(lk),T ℓ ) = 1 if lk requires the corresponding variable to be true, or βℓ(av(lk),F ℓ ) = 1 if it requires false. Assume, without loss of generality, that lk requires the variable to be true for all lk ∈ φ. By playing aφf , the follower gets utility uf(βℓ, aφf ) = βℓ(av(l1) ℓ )βℓ(av(l1),F ℓ ) n+1 3 + βℓ(av(l2) ℓ )βℓ(av(l2),F ℓ ) n+1 3 + βℓ(av(l3) ℓ )βℓ(av(l3),F ℓ ) n+1 3 . Three cases are possible.

1. There exists unique lk ∈ φ such that βℓ(av(lk),T ℓ ) = 1, for instance literal l1. Thus, since βℓ(av(l2),F ℓ ), βℓ(av(l3),F ℓ ) ≤ 1, it holds uf(βℓ, aφf ) ≤ n+1 3 (βℓ(av(l2) ℓ ) + βℓ(av(l3) ℓ )). Also, βℓ(avℓ ) = 1n ∀v ∈ V implies uf(βℓ, aφf ) < n+1 3 (1- 1n (n-2)) = 2 3 n+1 n < 1, for n sufficiently large (n > 2).
2. Exactly two literals lk in φ are such that βℓ(av(lk),T ℓ ) = 1. With a similar reasoning, we conclude that uf (βℓ, aφf ) < n+1 3 (1 - 1n (n - 1)) < 1, for every n.
3. βℓ(av(lk),T ℓ ) = 1 for all literals lk ∈ φ, and uf(βℓ, aφf ) < 1. Therefore, it must be uf(βℓ, aφf ) < 1 and aφf is not a follower's best-response to βℓ.

In conclusion, the unique follower's best-response is to play atf at node h0f , and uℓ(βℓ, atf ) = 1.

Given that 1 is the maximum leader's payoff in Γ(C, V ), we can conclude the following:

Corollary 1. If (C, V ) is satisfiable, then all SEs of Γ(C, V ) give the leader an expected utility of 1.

We now show that a utility of 1 for the leader implies the existence of a truth assignment satisfying the 3SAT formula.

Lemma 6. If there exists a leader's strategy βℓ and a follower's best-response βf ∈ BR(βℓ) such that uℓ(βℓ, βf) = 1, then (C, V ) is satisfiable.

Proof. Since uℓ(βℓ, βf) = 1, it must be the case that in βf the follower plays atf at the root node h0f , or else the leader would not get a utility of 1. Moreover, the leader's strategy βℓ must be such that either βℓ(av,T ℓ ) = 1 or βℓ(av,F ℓ ) = 1, for every v ∈ V , and, at each node h2,v f , the follower must play the action corresponding to that played by the leader in Iv. Because atf is a best response, it must be that uf (βℓ, avf ) ≤ 1 for every v ∈ V , otherwise atf would not be a follower best response. From uf (βℓ, avf ) ≤ 1, it follows that uf (βℓ, avf ) = n+2 (n+1)2 + 1 - βℓ(avℓ ) ≤ 1, so that βℓ(avℓ ) ≥ n+2 (n+1)2 > 1 n+1 for every n. For every φ ∈ C we have uf(βℓ, aφf ) ≤ 1, otherwise playing atf is not a best response for the follower. As a consequence, for every φ ∈ C, there must exist at least one literal lk ∈ φ such that βℓ(av(lk),T ℓ ) = 1 if lk requires true, or βℓ(av(lk),F ℓ ) = 1 if lk requires false. By contradiction, suppose such a literal lk does not exist, and assume, without loss of generality, that lk requires true for all lk ∈ φ. Thus, uf(βℓ, aφf ) = βℓ(av(l1) ℓ )βℓ(av(l1),F ℓ ) n+1 3 + βℓ(av(l2) ℓ )βℓ(av(l2),F ℓ ) n+1 3 + βℓ(av(l3) ℓ )βℓ(av(l3),F ℓ ) n+1 3 = n+1 3 (βℓ(av(l1) ℓ ) + βℓ(av(l2) ℓ ) + βℓ(av(l3) ℓ )) > 1, as βℓ(avℓ ) > 1 n+1 for all v ∈ V . This contradicts the fact that uf (βℓ, aφf ) ≤ 1. It follows that φ must be satisfied. Since φ was arbitrary, this shows that all clauses are satisfied. In conclusion, a variable assignment T such that T (v) = T if βℓ(av,T ℓ ) = 1, while T (v) = F whenever βℓ(av,F ℓ ) = 1, satisfies all clauses.

It directly follows from Lemma 6 that:

Corollary 2. If (C, V ) is not satisfiable, then all SEs of Γ(C, V ) give an expected utility smaller than 1 to the leader.

7 Conclusions

We initiated the study of equilibrium refinement based on trembling-hand perfection in Stackelberg extensive-form games, that is, games where one player commits to a strategy first. To our knowledge, this is the first solution concept that guarantees off-equilibrium-path optimality in extensiveform Stackelberg games. We studied the equilibrium space of all Stackelberg equilibria (containing both strong and weak Stackelberg equilibria), and showed that it is complete with respect to the limit points induced by perturbation schemes. We showed that this is not the case for strong and weak Stackelberg equilibria. Finally, we showed that deciding the existence of any Stackelberg equilibrium-refined or not-giving the leader expected value of at least ν is NP-hard.

Acknowledgements

This material is based on work supported by the National Science Foundation under grants IIS-1718457, IIS-1617590, and CCF-1733556, and the ARO under award W911NF-17- 10082. Christian Kroer is also sponsored by a Facebook Fellowship.