Víctor Bucarey
email: vbucarey@ulb.ac.be

Eugenio Della Vecchia
email: eugenio@fceia.unr.edu.ar

Alain Jean-Marie
email: alain.jean-marie@inria.fr

Fernando Ordóñez

Stationary Strong Stackelberg Equilibrium in Discounted Stochastic Games

Keywords: Stochastic games, Stackelberg Equilibrium, Optimal control Jeux stochastiques, Équilibre de Stackelberg, Contrôle optimal

In this work we focus on Stackelberg equilibria for discounted stochastic games. We begin by formalizing the concept of Stationary Strong Stackelberg Equlibrium (SSSE) policies for such games. We provide classes of games where the SSSE exists, and we prove via counterexamples that SSSE does not exist in the general case. We define suitable dynamic programming operators whose fixed points are referred to as Fixed Point Equilibrium (FPE). We show that the FPE and SSSE coincide for a class of games with Myopic Follower Strategy. We provide numerical examples that shed light on the relationship between SSSE and FPE and the behavior of Value Iteration, Policy Iteration and Mathematical programming formulations for this problem. Finally, we present a security application to illustrate the solution concepts and the efficiency of the algorithms studied in this report.

Introduction

Stackelberg games model interactions between strategic agents, where one agent, the leader, can enforce a commitment to a strategy and the remaining agents, referred to as followers, take that decision into account when selecting their own strategies. This Stackelberg game interaction can be extended to a multistage setting where leader and followers repeatedly make strategic decisions. Such dynamic Stackelberg models have been considered in applications in economics [START_REF] Bagchi | Some Economic Applications of Dynamic Stackelberg Games[END_REF], marketing and supply chain management [START_REF] Li | A Review of Dynamic Stackelberg Game Models[END_REF], dynamic congestion pricing [START_REF] Wie | Dynamic Stackelberg equilibrium congestion pricing[END_REF], and security [START_REF] Maria | Game-theoretic patrolling with dynamic execution uncertainty and a case study on a real transit system[END_REF]. For example, in a dynamic security application, a defender could decide on a strategy to patrol a number of targets over multiple periods and the attackers would take this defender patrol into consideration when deciding whether to attack and where in each period.

The sequential interaction between leader and follower in Stackelberg games and Stackelberg stochastic games, characterizes its equilibrium solutions with a system of optimality conditions that are in general non-linear and non convex. Previous work has developed specialized methods to find such equilibrium solutions for different problem types. In the specific case of Stackelberg security games, bi-level mathematical optimization formulations have been used to compute the Strong Stackelberg Equilibrium solution [START_REF] Kar | Trends and Applications in Stackelberg Security Games[END_REF] and, in the case of stochastic games, the Strong Stackelberg Equilibrium in stationary strategies (SSSE) [START_REF] Maria | Game-theoretic patrolling with dynamic execution uncertainty and a case study on a real transit system[END_REF]. An alternative method determines the SSSE by solving a non-linear potential game formulation [3]. These solution methods are either tailored for specific problems or only capable of solving small instances. It is therefore important to study alternative solution methods for Stackelberg stochastic games that are general and could solve large instances.

In this paper, we propose to use iterative algorithms, based on the operator formalism, to compute the SSSE solution of stochastic games. Our proposal is to use the well-known algorithms for solving Markov Decision Processes, Value Iteration and Policy Iteration, based on a suitably defined dynamic programming operator. Such algorithms are both conceptually simple and have a small computational burden per iteration. However, their use raises the question of convergence: do they converge, and if so, do they converge to some SSSE? Answering these questions led us to: a) conclude that SSSE do not necessarily exist, something not obvious from the current literature; b) identify classes of games where iterative algorithms converge to an SSSE. We then exploited this property in the analysis of a model of dynamic planning of police patrols on a transportation graph.

In the remainder of this introduction we clarify the problem under consideration, present related literature, describe the contributions of our work and introduce the notation that is used in this paper.

Problem Statement

We present now the notion of Strong Stackelberg Equilibria in Stationary policies (SSSE) for Stochastic Games. Consider a dynamic system evolving in discrete time on a finite set of states, where two players control the evolution. Players have a perfect information on the state of the system. One of them, called Leader or Player A, observes the current state s and commits to a, possibly mixed, strategy f depending solely on the state s. Then the other player, called Follower or Player B, observes the state and strategy of Player A and plays his best response denoted by g. Given the selected strategies there is a one-step reward for each player (r f g A (s) and r f g B (s) for player A and B, respectively) and a random transition probability Q f g (s |s) to another state s . This dynamics is illustrated in the following scheme:

s 0 Player A chooses f 0
Player B observes f 0 and chooses g 0

Q f 0 g 0 (s 1 |s 0 ) r f 0 g 0 A (s 0 ),r f 0 g 0 B (s 0 ) s 1 Player A chooses f 1
Player B observes f 1 and chooses g 1

• • •

Aggregated payoffs for both players are evaluated with the expected total discounted revenue over the infinite horizon, each player having their own discount factor. The aim for the leader is to find a policy that, in each state, maximizes her revenue taking into account that the follower will observe this policy and will respond by optimizing his own payoff. This general "Stackelberg" approach to the solution of the game is complemented with the rule that if the follower is indifferent between strategies, he chooses the one that benefits the leader: this refinement is the strong Stackelberg solution.

Related bibliography

The study of Strong Stackelberg Equilibria (SSE) has received much attention in the recent literature due to its relevance in security applications [START_REF] Kar | Trends and Applications in Stackelberg Security Games[END_REF]. In static games, the need to generalize the standard Stackelberg equilibrium has been pointed out by Leitman [START_REF] Leitman | On generalized Stackelberg strategies[END_REF] who introduced a conservative version of it. This generalization is formalized in Breton et al [2] as a Weak Stackelberg Equilibrium, together with the definition of the optimistic generalization, the Strong Stackelberg Equilibrium. The relationship between SSE and bi-level optimization appears in [2], solution methods for static Stackelberg Games are discussed in [START_REF] Dempe | Foundations of bilevel programming[END_REF].

Stackelberg equilibria in multi-stage and dynamic games have been studied in [START_REF] Simaan | Additional Aspects on the Stackeberg Strategy in Nonzero-Sum Games[END_REF][START_REF] Simaan | On the Stackeberg Strategy in Nonzero-Sum Games[END_REF]. In particular, authors propose in [START_REF] Simaan | Additional Aspects on the Stackeberg Strategy in Nonzero-Sum Games[END_REF] to focus on feedback strategies that can be obtained via dynamic programming. The idea is reused in [2] which introduces Strong Sequential Stackelberg Equilibria, in a setting very similar to ours. The notable difference is that, in the problem they consider, the follower gets to observe the action of the leader, not just its strategy. In their analysis, the formalism of operators linked to dynamic programming, introduced by Denardo [START_REF] Denardo | Contraction Mappings in the Theory Underlying Dynamic Programming[END_REF] and developed in [START_REF] Whitt | Representation and Approximation of Noncooperative Sequential Games[END_REF], is essential. Our analysis uses this formalism as well.

The stochastic game model we study in this paper is also the topic of Vorobeychik and Singh in [START_REF] Vorobeychik | Computing Stackelberg Equilibria in Discounted Stochastic Games[END_REF]. Although they do not provide any formal definition of SSSE, authors show that SSSE always exist in stochastic games for team games where both players have the same rewards by reducing the game to a MDP. They also propose mathematical Inria programming formulations to find the SSSE, extending the analysis for MDPs (see [13, ch. 6.]) and Nash equilibrium in stochastic games [START_REF] Filar | Competitive Markov decision processes[END_REF], for this case. Similar mathematical programming formulations are established in [START_REF] Maria | Game-theoretic patrolling with dynamic execution uncertainty and a case study on a real transit system[END_REF] and [START_REF] Vorobeychik | Computing solutions in infinite-horizon discounted adversarial patrolling games[END_REF] for problems in security applications. However, no prior work has provided a proof of the relationship between the solutions of these mathematical programming formulations and the SSSE of the stochastic game being considered. In this paper we present conditions that guarantee the existence of SSSE for stochastic games in diverse classes of problems, including team games. Furthermore we present numerical examples that suggest that the mathematical programming formulation computes the SSSE solution when it exists.

The complexity of computing a SSE is studied in [START_REF] Letchford | Computing Optimal Strategies to Commit to in Stochastic Games[END_REF]. That work shows, by reduction to 3SAT, that it is NP-hard to determine a SSE for a Stackelberg Stochastic Game with any discount factor β > 0 common for both players. The possibility that a Stackelberg Stochastic Game does not have a SSE is not mentioned.

As mentioned above, security applications are an important motivation for research on dynamic games. An attacker-defender Stackelberg security game is also considered in [3] for a repeated stochastic Markov chain game. This problem is represented as a potential game in terms of a suitable Lyapunov function, which is used to prove convergence results to compute the strong Stackelberg equilibrium [4]. While this method is a general approach for Ergodic Markov chains, the results presented show solutions only for instances with few states. It is interesting to single out the stochastic game model described in [START_REF] Filar | Competitive Markov decision processes[END_REF]Chapter 6.3]. The authors are interested in the average reward and the solution concept used is the Nash Equilibrium, a choice different from ours. However, the model has the feature that only one player, the defender, controls the transitions between states. This feature is one of the properties that guarantees the existence of SSSE, as we will show later.

Contribution

While previous work has formulated Stackelberg equilibrium for stochastic games and considered different solution methods to compute the SSSE, to the best of our knowledge the general question of the existence of SSSE is still largely open, in the sense that, so far: a) no case of non-existence is reported, b) few sufficient conditions for existence have been established. Furthermore, no work to date has advocated the use of the operator method, neither for the mathematical analysis of the problem, nor for its algorithmic solution.

We contribute to the issue in the following ways: First, we give a formal definition of the Strong Stationary Stackelberg Equilibrium (SSSE) in stochastic games (Section 1.4). We develop the operator-based analysis of such games by introducing an operator acting on the space of value functions. The operator introduced is related to the one-step evaluation of each player's payoff. We then define Fixed Point Equilibria (FPE) as the fixed points of this operator. Next, we introduce the class of games with Myopic Follower Strategy (MFS), for which specific operators are relevant. We prove that these operators are contractive. Finally, we introduce the algorithms for computing FPE, for general games and for games with MFS. We prove the convergence of both Value Iteration and Policy Iteration to the FPE of games with MFS. We also recall the Mathematical Programming formulation for SSSE. This is the topic of Section 2.

Next, we focus on the general question of existence of SSSE and FPE, and how they are related. We show that games with MFS and Team Games have both SSSE and FPE and that they coincide. The operator formalism is instrumental in this proof. We also address the classes of Zero-Sum Games and Acyclic Games. This analysis is developed in Section 3.

We then illustrate different situations with specific examples. In a first case, an FPE and an SSSE exist and coincide, although the game does not have MFS (the assumption of our main existence result). In a second case, depending on the parameters: either no SSSE exist, or no FPE exist, or both an SSSE and an FPE exist but they do not coincide. In a third case, an FPE exists but Value Iteration does not necessarily converge to it. These examples are summarized in Section 4 and described in more detail in Appendix C.

Finally, we take advantage of the convergence properties we have shown, to propose a solution methodology in a dynamic security game, representing the problem of security patrols in a network. This is reported in Section 5.

Notation and definitions

We introduce now formally the elements of the model and the notation. A synthesis of this notation is presented in Appendix A.

Let S represent the finite set of states of the game. Let A, B denote the finite set of actions available to players A and B respectively, and we denote by A s ⊂ A and B s ⊂ B the actions available in state s ∈ S. For a given state s ∈ S and actions a ∈ A s and b ∈ B s , Q ab (s |s) represents the transition probabilities of reaching the state s ∈ S. We denote with Q the family of these probability distributions. The reward received by each player in state s when selecting actions a ∈ A s and b ∈ B s is referred to as the one-step reward functions and are given by r A = r ab A (s) and r B = r ab B (s). The constants β A , β B ∈ [0, 1) are discount factors for Player A and B respectively. In our setting time increases discretely and the time horizon is infinite. Therefore we represent a two-person stochastic discrete game G by

G = (S, A, B, Q, r A , r B , β A , β B ) .
Strategies. We denote by P(A s ) and P(B s ) the sets of distribution functions over A s and B s , respectively. The sets of stationary strategies are defined by:

W A = {f : S → P(A)| f (s) ∈ P(A s )} W B = {g : S → P(B)| g(s) ∈ P(B s )} .
For f ∈ W A , f (s) is a probability measure on A s . In order to simplify the notation, we represent with f (s, a) = (f (s))({a}) = f (a|s) the probability that Player A chooses action a when in state s. Likewise, for g ∈ W B , we denote with g(s, b) = g(b|s) the probability that Player B chooses b when in state s. In the case that g ∈ W B is a deterministic policy, Inria we will denote directly with g(s) the element of B s that has probability one. The notation will be clear from context. The set W B is assumed to be equipped with a total order ≺ B , which will be used for determining a unique element in case Player B is indifferent between several policies.

In order to simplify notation, given stationary strategies f and g, we define the reward for player i(= A, B) by:

r f g i (s) = a∈As b∈Bs f (s, a)g(s, b)r ab i (s). (1.1)
Values. Given a pair (f, g) ∈ W A × W B , the evolution of the states is that of a Markov chain on S with transition probabilities

Q f g (s |s) = a∈As b∈Bs f (s, a)g(s, b)Q ab (s |s).
Denote with {S n } n the (random) sequence of states of this Markov chain and E f g s the expectation corresponding to the distribution of this sequence, conditioned on the initial state being S 0 = s. Then the value of this pair of strategies for Player i, from state s, is:

V f g i (s) = E f g s ∞ k=0 β k i r f (S k ),g(S k ) i (S k ) (1.2) = E f g s   ∞ k=0 β k i a∈A b∈B f (S k , a)g(S k , b)r ab i (S k )   .
Reaction sets. We proceed with the definition of the player's reaction sets. These definitions rely heavily on the fact that when the leader selects a stationary strategy, the follower faces a finite-state, finite-action, discounted MDP. It is then well-known that there exists optimal stationary and deterministic policies which maximize simultaneously the follower's values starting from any state. Moreover, the set of optimal policies is the cartesian product of the set of optimal decisions in each state. This fact results from e.g. Corollary 6.2.8, p. 153 in [START_REF] Puterman | Markov decision processes[END_REF]. Accordingly, let: [START_REF] Letchford | Computing Optimal Strategies to Commit to in Stochastic Games[END_REF][START_REF] Vorobeychik | Computing Stackelberg Equilibria in Discounted Stochastic Games[END_REF].

R B (f ) := {g ∈ W B | V f g B (s) ≥ V f h B (s), ∀s ∈ S, h ∈ W B } ∩ s∈S {0, 1} |Bs| (1.3) SR B (f ) := {g ∈ R B (f ) | V f g A (s) ≥ V f h A (s), ∀s ∈ S, h ∈ R B (f )} (1.4) γ B (f ) := max ≺ B SR B (f ) R A (s) := {f ∈ W A | V f γ B (f ) A (s) ≥ V hγ B (h) A (s), ∀h ∈ W A } . (1.5) Given that Player A selects strategy f , R B (f )
Definition 1 (SSSE). A strategy pair (f, g) ∈ W A × W B is a Stationary Strong Stackel- berg Equilibrium if i/ g = γ B (f ); ii/ f ∈ R A (s) for all s ∈ S.
In an SSSE, the strategy f maximizes simultaneously the leader's reward in every state. In contrast with MDP where this is always possible, there is no guarantee that this will happen in a Stackelberg stochastic game. Indeed, in Section 4.3 we provide an example where ∩ s R A (s) is empty, and consequently there is no SSSE.

To the best of our knowledge, the literature does not provide general statements about the existence of an SSSE. We address in Section 3 this issue in special cases.

Operators, Fixed Points and Algorithms

In this section, we develop the formalism of operators, as commonly found in texts on MDPs [START_REF] Puterman | Markov decision processes[END_REF], and also for games in [2,[START_REF] Denardo | Contraction Mappings in the Theory Underlying Dynamic Programming[END_REF][START_REF] Whitt | Representation and Approximation of Noncooperative Sequential Games[END_REF]. We focus on fixed points of these operators, as a means to discuss existence of equilibria, and also as a computational procedure. Accordingly, we study the monotonicity and contractivity of these operators. This allows us to prove the convergence of Value Iteration, Policy Iteration and Mathematical Programming-based algorithms, in certain situations.

Definition of operators

We start with the definition of one-step (or "return function" [START_REF] Denardo | Contraction Mappings in the Theory Underlying Dynamic Programming[END_REF]) operators. The set of value functions, i.e. mappings from S to R, will be denoted with F(S). Given (f, g) ∈ W A × W B we define T f g i : F(S) → F(S), such that

T f g i v (s) = a∈As f (s, a) b∈Bs g(s, b) r ab i (s) + β i z∈S Q ab (z|s)v(z) .
It is important to note that the value (T f g i v)(s) depends only on f (s) and g(s), and not on the rest of the strategies f and g. In the following, with a slight abuse of notation, we will use this quantity for values of f and g specified only at state s.

The set of pairs of value functions is F(S) × F(S). A typical element of it will be denoted as v = (v A , v B ). Using T f g A and T f g B we define the operator T f g on F(S) × F(S) as:

(T f g v) i = T f g i v i Inria for i = A, B.
It will be recalled in Lemma 1 that T f g i is a contraction for i = A, B. It follows that T f g is contractive as well. As a consequence of Banach's theorem, it admits a unique fixed point on the complete space F(S) × F(S) with the supremum norm, that turns out to be V f g = (V f g A , V f g B ), these functions being defined in (1.2).

Extended reaction sets. We now extend the definitions of reaction sets to involve value functions. They correspond to a dynamic game with only one step and a "scrap value" v = (v A , v B ). In contrast to the sets introduced in Section 2.1 for SSSE, the sets we discuss here are relative to local strategies depending on each state, rather than global strategies in W A and W B .

For s ∈ S, f ∈ P(A s ), v ∈ F(S) × F(S), and v B ∈ F(S), let:

R B (s, f, v B ) := {g ∈ B s | (T f g B v B )(s) ≥ (T f h B v B )(s), ∀h ∈ B s } (2.1) SR B (s, f, v) := {g ∈ R B (s, f, v B ) | (T f g A v A )(s) ≥ (T f h A v A )(s), ∀h ∈ R B (s, f, v B )} (2.2) γ B (s, f, v) := max ≺ B SR B (s, f, v) (2.3) R A (s, v) := {f (s) ∈ P(A s ) | (T f γ B (s,f,v) A v A )(s) ≥ (T hγ B (s,h,v) A v A )(s), ∀h ∈ P(A s )} . ( 2.4)
The definition of Player B's response in (2.3) is such that one unique, non-ambiguous policy is defined as a solution. Any f (s) ∈ R A (s, v) is considered as a solution of the problem.

The dynamic programming operator. The one-step Strong Stackelberg problem naturally leads to a mapping in the space of value functions, which is formalized as follows.

Definition 2 (Dynamic programming operator T ). Let T : F(S) × F(S) → F(S) × F(S) be defined as:

(T v) i (s) = T R A (s,v),γ B (s,R A (s,v),v) i v i (s) (2.5) for i = A, B.
Observe that the definition depends on the ordering ≺ B . By changing the ordering, many operators can be defined for the same problem.

Fixed points. We are now in position to define the fixed-point equilibria.

Definition 3 (Fixed Point Equilibrium, FPE). A strategy pair (f, g)

∈ W A × W B is an FPE if the function v * = V f g , the unique fixed point of T f g , is such that T v * = v * . Equivalently, if i/ g(s) = γ B (s, f, v * ) for all s ∈ S; RR n°9271 ii/ f (s) ∈ R A (s, v * ) for all s ∈ S.
One of the purposes of this paper is to propose results concerning FPEs and SSSE: discuss whether they respectively exist, and when they do, whether they coincide or not.

Properties of operators

The following property is well-known (e.g. [START_REF] Puterman | Markov decision processes[END_REF]) for finite-state, finite-action discounted Markov Reward Processes: Lemma 1. For i = A, B, the operator T f g i is linear, monotone, contractive and V f g i defined in (1.2) is its unique fixed point. This fixed point has the expression

V f g i = (I -β i Q f g ) -1 r f g i , ( 2.6)
where r f g i is defined in (1.1), where the probability transition matrix Q f g is defined similarly in Section 1.4, and I is the identity matrix of appropriate dimension.

We now introduce a particular class of games, and the particular properties of operators for these games.

Definition 4 (Myopic Follower Strategy, MFS). A stochastic game G is said to be with Myopic Follower Strategy

if R B (s, f, v B ) = R B (s, f ), for all s ∈ S, f ∈ W A and v B ∈ F(S).
Games with Myopic Follower Strategy are games where the response of the follower is independent of the expected future values: for her, only immediate rewards are relevant. As it is stated in Lemma 5, this setting happens whenever β B = 0 (as it is used in [START_REF] Maria | Game-theoretic patrolling with dynamic execution uncertainty and a case study on a real transit system[END_REF]) or the leader controls the transitions of the games, see for e.g. single-controller games in [START_REF] Filar | Competitive Markov decision processes[END_REF].

When a game is with MFS, the reaction of the follower depends only on the leader's value v A :

∀f ∈ W A , ∀v ∈ F(S) × F(S), ∀s ∈ S, γ B (s, f, v) = γ B (s, f, v A ). (2.7)
Then the following Lemma is relevant.

Lemma 2. Assume (2.7) holds. Then there exists an operator T A from F(S) to F(S) such that for all v ∈ F(S) × F(S),

(T v) A = T A v A . (2.8)
Proof. According to Definition (2.4) and due to (2.7), we have R A (s, v) = R A (s, v A ) for all v ∈ F(S) and s ∈ S. Then, from (2.5),

(T v) A (s) = (T R A (s,v),γ B (s,R A (s,v),v) A v A )(s) = (T R A (s,v A ),γ B (s,R A (s,v A ),v A ) A v A )(s) =: (T A v A )(s) .

Inria

An alternate construction of operator T A is as follows. It is possible to define, for each f ∈ W A , the operator T f A from F(S) to F(S) as:

(T f A v A )(s) = (T f,γ B (s,f,v A ) A v A )(s) .
(2.9)

Another consequence of MFS is this property which follows from the definition of γ B (•) in (2.3) and

SR B (•) in (2.2): (T f A v A )(s) = max g∈R B (s,f ) (T f g A v A )(s) . (2.10)
In this equation, the maximization set on the right-hand side does not depend on v at all. Finally, define the operator T A from F(S) to F(S) as, for all s ∈ S:

(T A v A )(s) = max f ∈W A (T f A v A )(s) . (2.11)
Observe that the maximum is indeed attained, because the right-hand side is a linear combination of the finite set of values f (s, a), a ∈ A s .

We can now state the principal tool of this paper for ascertaining the existence of FPE.

Theorem 1. Let G be a stochastic game with MFS, then it is true that: a) For any stationary strategy f ∈ W A , the operator T Proof. The central argument of the proof is the following fact. Let h 1 and h 2 be two real functions defined on some set B, where they attain their maximum. Then for all b 1 ∈ arg max B {h 1 (b)} and all b 2 ∈ arg max B {h 2 (b)},

h 1 (b 2 ) -h 2 (b 2 ) ≤ max B {h 1 (b)} -max B {h 2 (b)} ≤ h 1 (b 1 ) -h 2 (b 1 ) .
(2.12)

To show a), take v A , u A ∈ F(S), a stationary strategy f ∈ W A , and s ∈ S. Then, using (2.10), (T

f A v A )(s) -(T f A u A )(s) = max b∈R B (s,f ) a∈As f (s, a) r ab A (s) + β A z∈S Q ab (z|s)v A (z) -max b∈R B (s,f ) a∈As f (s, a) r ab A (s) + β A z∈S Q ab (z|s)u A (z) .
(2.13)

RR n°9271

Then from (2.12), there exists b ∈ R B (s, f ) such that:

(T f A v A )(s) -(T f A u A )(s) ≤ a∈As f (s, a) r ab A (s) -r ab A (s) + β A z∈S Q ab (z|s)v A (z) -Q ab (z|s)u A (z) = a∈As f (s, a)β A z∈S Q ab (z|s)(v A (z) -u A (z)) (2.14) ≤ β A ||v A -u A || ∞ .
By reversing the roles of v A and u A , then taking the maximum over s ∈ S we have that:

||T f A v A -T f A u A || ∞ = max s∈S |(T f A v A )(s) -(T f A u A )(s)| ≤ β A ||v A -u A || ∞ , concluding that T f
A is a contracting map of modulus β A . In order to show b), take v A , u A ∈ F(S), a state s ∈ S and f * any optimal policy realizing max f ∈W A (T

f A v A )(s). Then, (T A v A )(s) -(T A u A )(s) = max f ∈P(As) (T f A v A )(s) -max f ∈P(As) (T f A u A )(s) = (T f * A v A )(s) -max f ∈P(As) (T f A u A )(s) ≤ (T f * A v A )(s) -(T f * A u A )(s) ≤ β A ||v A -u A || ∞ .
Then, by reversing the roles of v A , u A and taking the maximum the result follows.

Consider now statement c). If v A ≥ u A , then from (2.13) with (2.12) and (2.14), there exists some b ∈ R B (s, f ) such that:

(T f A v A )(s) -(T f A u A )(s) ≥ a∈As f (s, a)β A z∈S Q ab (z|s)(v A (z) -u A (z)) ≥ 0 .
Then c) also holds. The extension to T A is classical.

Value Iteration Algorithms

Value Iteration generally consists in applying a dynamic programming operator to some initial value function, until a convergence criterion is met. Specifically, given some ε > 0, Value Iteration applies some operator repeatedly until the distance between two functions v n A and v n+1 A is less than ε. In view of the preceding discussion, two variants of the algorithm will be used: one for the general situation (Algorithm 1) and one for the specific situation of MFS, i.e. when (2.7) holds (Algorithm 2). Compute v n as v n (s) := (T v n-1 )(s), ∀s ∈ S with T according to Definition (2.5)

5: until ||v n -v n-1 || ∞ ≤ ε 6: Pick (f * , g * ) such that v n (s) = (T f * g * v n-
n := n + 1 4: Compute v n A as v n A (s) := (T A v n-1 A )(s), ∀s ∈ S with T as in (2.11) 5: until ||v n A -v n-1 A || ∞ ≤ ε 6: Pick f * such that v n A (s) = (T f * A v n-1 A )(s) and g * such that g * (s) = γ B (s, f * , v n-1 A ), for all s ∈ S 7: return Approximate Stationary Strong Stackelberg policies (f * , g * )
There is no guarantee in general that Algorithm 1 will converge, and we present in Section 4.4 an example where it does not. However, thanks to Theorem 2, we can state that Algorithm 2 does converge.

Theorem 2. Let G be a stochastic game with MFS. Then the sequence of value functions v n A in Algorithm 2 converges to v * A , which is the fixed point of T A . Moreover the following bounds hold:

||v * A -v n A || ∞ ≤ 2β n A ||r A || ∞ 1 -β A for any n ∈ N, ||v * A -V f * g * A || ∞ ≤ 2β A ε 1 -β A .
Proof. Let the pair of policies (f * , g * ) be the ones returned by Algorithm 2 and V f * g * A be the fixed point of T f * A . By Theorem 1 b) and Banach's Theorem, we know that T A has a unique fixed point, v * A . Then,

||V f * g * A -v * A || ∞ ≤ ||V f * g * A -v n A || ∞ + ||v n A -v * A || ∞ . (2.15)
In (2.15), the first term on the right-hand side is bounded as follows:

||V f * g * A -v n A || ∞ = ||T f * A V f * g * A -v n A || ∞ ≤ ||T f * A V f * g * A -T A v n A || ∞ + ||T A v n A -v n A || ∞ = ||T f * A V f * g * A -T f * A v n A || ∞ + ||T A v n A -T A v n-1 A || ∞ ≤ β A ||V f * g * A -v n A || ∞ + β A ||v n A -v n-1 A || ∞ ,
where the first equality is by definition, the inequality right after is the triangular inequality. The third line is because of the definition of T

f *
A and the inequality is because T f * A and T A are contracting maps of modulus β A . This last inequality implies that

||V f * g * A -v n A || ∞ ≤ β A 1 -β A ||v n A -v n-1 A || ∞ .
For the second term on the right-hand side of (2.15), we have:

||v n A -v * A || ∞ = lim t→∞ ||v n A -v t A || ∞ ≤ lim t→∞ t-n-1 k=0 ||v n+k A -v n+k+1 A || ∞ ≤ lim t→∞ t-n-1 k=0 β k A ||v n-1 A -v n A || ∞ = β A 1 -β A ||v n-1 A -v n A || ∞ .
Then, we have that the policies returned by the algorithm satisfy:

||V f * g * A -v * A || ∞ ≤ 2 β A 1 -β A ||v n-1 A -v n A || ∞ = 2β A 1 -β A ε .
Furthermore, given that

||v n-1 A -v n A || ∞ ≤ β n-1 A ||v 0 A -v 1 A || ∞ = β n-1 ||v 1 A || ∞ ≤ β n-1 A ||r A || ∞
the result follows.

Policy Iteration

The Policy Iteration (PI) algorithm directly iterates in the policy space. This algorithm starts with an arbitrary policy f and then finds the optimal infinite discounted horizon values, taking into account the optimal response g(f ). These values are then used to compute new policies. These two steps of the algorithm can be defined as the Evaluation Phase and the Improvement Phase.

Inria

As in the previous section, two variants of the algorithm will be used: one for the general situation (Algorithm 3) and one for the specific situation of a MFS, i.e. when (2.7) holds (Algorithm 4).

Algorithm 3 Policy Iteration (PI); general case

1: Require ε > 0 2: Initialize with n = 0 3: Choose an arbitrary pair of strategies (f

0 , g 0 ) ∈ W A × W B with g 0 (s) = γ B (s, f 0 , 0) for all s ∈ S 4: Compute u 0 = (u 0 A , u 0 B ) fixed point of T f 0 g 0 5: repeat 6: n := n + 1 7: Improvement Phase: Find a pair of strategies (f n , g n ) such that T fngn u n-1 = T u n-1 with g n (s) = γ B (s, f n , u n-1 ) for all s ∈ S 8: Evaluation Phase: Find u n = (u n A , u n B ), fixed point of the operator T fngn 9: until ||u n -u n-1 || ∞ ≤ ε 10: f * := f n ; g * (s) := γ B (s, f n , u n ) for all s ∈ S 11: return Approximate Stationary Strong Stackelberg policies (f * , g * ) Algorithm 4 Policy Iteration (PI); simplified case 1: Require ε > 0 2: Initialize with n = 0 3: Choose an arbitrary pair of strategies (f 0 , g 0 ) ∈ W A × W B with g 0 (s) = γ B (s, f 0 , 0) for all s ∈ S 4: Compute u 0 A fixed point of T f 0 A 5: repeat 6: n := n + 1 7: Improvement Phase: Find a distribution f n such that T fn A u n-1 A = T A u n-1 A 8:
Evaluation Phase: Find u n A fixed point of the operator

T fn A 9: until ||u n A -u n-1 A || ∞ ≤ ε 10: f * := f n ; g * (s) := γ B (s, f n , u n A ) for all s ∈ S 11: return Approximate Stationary Strong Stackelberg policies (f * , g * )
The Evaluation Phase in Algorithm 3 (respectively Algorithm 4) requires to solve two (resp. one) linear systems of size |S| × |S|. On the other hand, the Improvement Phase can be implemented by solving a static Strong Stackelberg equilibrium for each state s ∈ S. Now we prove that Algorithm 4 converges to the SSSE. In other words, the PI algorithm converges to the SSSE for stochastic games with MFS.

Lemma 3. If a function v

A ∈ F(S) satisfies v A ≤ T f A v A , for some f ∈ P(A) then v A ≤ v f A , where v f A is the unique fixed point of T f A in F(S).
The same holds for T A .

RR n°9271

Proof. By hypothesis we have that

v A ≤ T f A v A ,
that implies by Theorem 1 c),

T f A v A ≤ (T f A ) 2 v A ,
and then

v A ≤ (T f A ) 2 v A .
In the same way, for each n we have

v A ≤ (T f A ) n v A ,
and by Theorem 1 a), when n → ∞,

(T f A ) n v A -→ v f A .
The result follows for T f A . The proof for T A is similar.

Theorem 3. Suppose that Condition (2.7) holds. The sequence of functions u n A in Algorithm 3 verifies u n A ↑ v * A . Further, if for any n ∈ N, u n A = u n+1 A , then it is true that u n A = v * A .
Proof. For each s ∈ S, we have that

u 0 A (s) = T f 0 A (u 0 A )(s) ≤ T A (u 0 A )(s) = T f 1 A (u 0 A )(s) .
Then the value function u 0 A satisfies

u 0 A ≤ T f 1 A u 0 A ,
and by Lemma 3

u 0 A ≤ v f 1 A = u 1 A . Iterating over n, we have that u n A ≤ T A (u n A ) ≤ u n+1 A . (2.16)
Now the sequence {u n A } n∈N being non-decreasing and bounded by ||r

A || ∞ /(1 -β A ), there exists a value function u A such that for any s ∈ S u A (s) = lim n→∞ u n A (s) . Taking n → ∞ in (2.16), u A ≤ T A (u A ) ≤ u A and therefore u A = T A (u A ),

and by uniqueness of the fixed point

u A = v * A ,
Inria and we have the first claim of the theorem:

u n A ↑ v * A .
Also, if it is verified for some n that u n A = u n+1 A , then, using (2.16),

u n+1 A = u n A ≤ T A u n A ≤ u n+1 A , which implies u n A = T A u n A = v * A ,
where the second equality is again given by the uniqueness of the fixed point. The second claim follows.

The results exposed in this section strongly rely on the fact that γ B (s, f, v) is independent on v B . In Section 3 we show that MFS is a sufficient condition for the existence of an FPE but all the results here may fail in the general case.

Mathematical Programming Formulations

In this section we develop the discussion of Mathematical Programming (MP) formulations, as the one proposed in [START_REF] Vorobeychik | Computing Stackelberg Equilibria in Discounted Stochastic Games[END_REF]. To start the discussion we notice that for each f ∈ W A the follower solves an MDP with transition and rewards given by the expectation induced by f . Then, as argued in Section 1.4, there exists (at least) one optimal policy in the set of deterministic stationary policies. This policy g can be retrieved by finding deterministic policies that induce a fixed point of the operator

T f γ(s,f,v) B
. This condition is modeled as the following set of non-linear constraints:

0 ≤ v B (s) -(T f g B v B )(s) ≤ M B (1 -g sb ) s ∈ S, b ∈ B s (2.17) b∈Bs g sb = 1 s ∈ S (2.18)
g sb ∈ {0, 1} s ∈ S, b ∈ B s . (2.19)
The variable of the program g sb is meant to represent the probability g(s, b).

For each f ∈ W A , the deterministic best response set of the follower is determined by constraints (2.17)- (2.19). In (2.17) the constant M B is chosen so that when g sb = 0, the upper bound is not constraining.

Since ||v B || ∞ ≤ ||r B || ∞ /(1 -β B ), the value M B = 2||r B || ∞ /(1 -β B )
is adequate. Now the leader's problem can be reduced to determine which f maximizes in each state its total expected reward. Vorobeychik and Singh in [START_REF] Vorobeychik | Computing Stackelberg Equilibria in Discounted Stochastic Games[END_REF] propose the following formulation:

(MP) max s∈S α s v A (s) (2.
a∈As f sa = 1 s ∈ S v A (s) -(T f g A v A )(s) ≤ M A (1 -g sb ) s ∈ S, b ∈ B s (2.21) f sa ≥ 0, ∀s ∈ S, a ∈ A s .
where α ∈ R |S| + is a non-negative vector of coefficients. Problem (MP) above is a nonlinear optimization problem with integer variables. Such problems are challenging to solve in general. In particular, constraints (2.17) and (2.21) are non-convex quadratic constraints that involve integer variables.

This optimization problem is built based on an analogy to MDPs. In particular, it uses the reduction to a single objective using a vector of weights in (2.20). For MDPs, this choice is arbitrary. As it turns out in the experiments presented in Section 4, the result of (MP) sometimes depends on the vector α s , and sometimes it is not an SSSE. We observe that when such anomalies occur, the operator T A is not monotone. On the other hand, in cases where T A is known to be monotone, no such problems seem to occur. We therefore conjecture that for the correctness of (MP), it is necessary to have monotonicity of the operator.

Existence Results for SSSE and FPE.

In this section we present existence results for Stationary Strong Stackelberg Equilibria and Fixed-Points Equilibria of the dynamic programming operator. The general idea underlying these results is that, under certain assumptions, it can be proved that some operator, typically T or T A defined in Section 2, is contractive. Using Banach's theorem, it then has a fixed point with which the solution is constructed. Then, still under some assumptions, this FPE solution is shown to be an SSSE.

Single-state results

In the case where there is only one state, the game is equivalent to a static game, so that SSE and SSSE coincide. Indeed, if S = {s 0 }, it is clear that

V f g i (s 0 ) = r f g i (s 0 ) 1 -β i . ( 3.1)
for all (f, g) ∈ W A × W B , so that optimization of V f g i and of r f g i are equivalent. The existence of an SSSE for single-state games is well accepted in the literature with however no clear reference. In this section, we state and prove this result and connect it to the FPE.

We start with a general and useful result that applies to any game.

Lemma 4.

Let G be a stochastic game. For all s ∈ S, the set R A (s) is nonempty.

Proof. We use the scheme of proof of Proposition 3.1 in [START_REF] Simaan | On the Stackeberg Strategy in Nonzero-Sum Games[END_REF]. Fix a state s ∈ S.

Define D = {(f, g) ∈ W A × W B |g ∈ R B (f )}. The value functions V f g i can be expressed as V f g i = (I -β i Q f g ) -1 r f g i .
Due to the finiteness of S, this is a rational function of f and g. It does not have singularities inside W A × W B and is therefore continuous. In particular, the mappings (f, g) → V f g i (s) are continuous. Since W A and W B are compact, Inria the maximum theorem applies: the maximum of this function over D exists. Therefore the set R A (s) is nonempty.

Theorem 4. If the game G has only one state, then it has an SSSE which is also an FPE.

Proof. Let S have a single state: S = {s 0 }. The existence of SSSE is a particular case of Lemma 4. The existence of an FPE follows from the observation that the game is MFS: Theorem 1 applies to it. Being a contraction, the operator T A has a unique fixed point from which an FPE is constructed. There remains to show that this FPE coincides with the SSSE.

To that end, we first show that R B (f ) = R B (s 0 , f ) for all f ∈ W A (since the game is with MFS, this latter set does not depend on

v B ∈ F(S)). If g ∈ R B (s 0 , f ), then for all h ∈ W B , V f g B (s 0 ) = r f g B (s 0 ) 1 -β B ≥ r f h B (s 0 ) 1 -β B = V f h B (s 0 ) which means that g ∈ R B (f ). By the same token, if g ∈ R B (f ) then g ∈ R B (s 0 , f ).
So both reaction sets coincide. Since V f g A and r f g A are also proportional, breaking ties in favor of the leader is the same problem for SSSE and FPE: the sets SR B (f ) and SR B (s 0 , f, v B ) also coincide, and

γ B (f ) = γ B (s 0 , f, v) for all f ∈ W A and v ∈ F(S). It follows from (1.5) and (2.4) that R A (s 0 ) = R A (s 0 , v) for all v,
which means that SSSE and FPE coincide.

An alternative algorithmic proof of the existence of the SSSE in Theorem 4 is provided in Appendix B. This is based in the Multiple LPs algorithm which also give as a polynomial algorithm to solve an SSSE in the static case.

Myopic Follower Strategies

Theorem 5 (FPE for MFS). If the game G is with MFS then it admits an FPE.

Proof. According to Theorem 1 b), the operator T

A is contractive. It therefore admits a fixed point v * A . Let f * ∈ W A be defined by, for each s ∈ S, f * (s) = R A (s, v * A ). Let g * ∈ W B be defined for each s ∈ S, by g * (s) = γ B (s, f * , v * A ) = γ B (s, f * , v * ). We show that (f * , g * ) is an FPE.
To avoid confusion in the notation, denote with U = V f * g * , the unique fixed point of T f * g * . We first check that v * A = U A . We have successively: for every s ∈ S,

v * A (s) = (T A v * A )(s) = (T R A (s,v * A ),γ B (s,R A (s,v A ),v * A ) A v * A )(s) = (T f * (s)g * (s) A v * A )(s) .

The first line is the definition of v *

A as a fixed point. The second one is the definition of operator T A in (2.8) and that of T in (2.5), combined with the MFS property, see the proof of Lemma 2. The third one is by definition of f * and g * . This last line is equivalent to saying that v * A is the fixed-point of operator

T f * g * A , hence v * A = U A . As a consequence, (T U ) A = U A .
There remains to be seen that (T U ) B = U B . We have:

(T U ) B = T f * g * B U B = U B since by definition of U , U B is the fixed point of T f * g * . This completes the proof.
In the following Lemma 5, we show that there are actually two main classes games which have MFS. We introduce now these classes of games with one important subclass.

Myopic follower:

We define a game as a myopic follower game if β B = 0. Note that in this case the follower at any step of the game does not take into account the future rewards, but only the instantaneous rewards.

In this case, the one-step operator of the follower is:

(T f g B v B )(s) = r f g B (s) (see (1.1)) and it clearly does not depend on v B . Therefore, the reaction set R B (s, f, v B ) defined in (1.3) does not depend either on v B : R B (s, f, v B ) = R B (s, f ).
It follows that the follower's best response has the form (2.7).

Leader-Controller Discounted Games:

This case is a particular case of the Singlecontroller discounted game described in Filar and Vrieze [START_REF] Filar | Competitive Markov decision processes[END_REF], where the controller is the leader. In other words, the transition law has the form Q ab (z|s) = Q a (z|s).

In that case, the one-step operator of the follower is:

(T f g B v B )(s) = a∈As f (s, a) b∈Bs g(s, b) r ab B (s) + β B z∈S Q a (z|s)v B (z) = r f g B (s) + β B a∈As f (s, a) z∈S Q a (z|s)v B (z) .
Then, for g, h ∈ W B , we have:

(T f g B v B )(s) -(T f h B v B )(s) = r f g B (s) -r f h B (s) and the difference does not depend on v B . The reaction set R B (s, f, v B ) is defined as those g such that: ∀h ∈ B s , (T f g B v B )(s) -(T f h B v B )(s) ≥ 0.
It is therefore independent from v B for any s ∈ S, and as before, (2.7) holds.

Multi-stage games: in such games, the state evolves sequentially and deterministically through s 1 , s 2 , . . . , s K and stops. This can be seen a particular case of Leader-Controlled Discounted Game, where the evolution is actually not controlled at all. An additional terminal state with trivial reward functions may be needed to model the end of a game with finitely many stages.

The reduction of MFS to these classes is the topic of the following lemma.

Lemma 5. Let G be a game with MFS. Then one the following statements is true:

i/ β B = 0; Inria ii/ Q ab (z|s) = Q a (z|s) for all s, z ∈ S and all a ∈ A s , b ∈ B s .
Proof. We prove by contradiction the following statement:

∀s ∈ S, ∀a ∈ A s , ∀b ∈ B s , ∀z ∈ S, β B (Q ab (z|s) -Q ab (z|s)) = 0 , (3.2)
which itself is equivalent to the statement of the lemma.

For each a ∈ A s and s ∈ S, consider the policy where the leader plays the pure strategy a, denoted by

δ a . Take b * ∈ R B (s, δ a , v B ) for a given v B (note that R B (s, f, v B ) = ∅).
Then it is true that for all b ∈ B s :

r ab * B (s) -r ab B (s) + z∈S β B Q ab * (z|s) -Q ab (z|s) v B (z) ≥ 0.
Suppose by contradiction that (3.2) does not hold. Then there exists s, a, b and b such that

ξ = β B (Q ab * (z * |s) -Q ab (z * |s)) = 0 for some z * .
Then by taking v B (z * ) with the opposite sign of ξ big enough, and v B (z) = 0, for z = z * , the inequality will turn negative. That would mean that b * does not belong to R B (s, f, v B ) with v B and then the game is not MFS. This is a contradiction, so such elements s, a, b, b , z do not exist, and (3.2) holds.

We now state the principal results of this section: the MFS property implies the existence of both FPE and SSSE, and their coincidence. Theorem 6. Let G be a stochastic game with MFS. Then G has an SSSE, which corresponds to its FPE.

Proof. Let (f * , g * ) be the FPE of game G, and V * = V f * g * . We know that the FPE exists by Theorem 5. From the proof of this result, we know that

V * A = T A V * A = T f * A V * A . We first prove that R B (f * ) = s∈S R B (s, f * ).
According to Lemma 5, since the game has MFS, then either β B = 0, or the game is Leader-Controlled Discounted. In both cases, the value of Player B has the form (see (2.6)):

V f g B = (I -β B Q f ) -1 r f g B ,
where Q f is the leader-controlled transition matrix, relevant only in case β B = 0. We note that, given that the matrix (I -

β i Q f ) -1 is positive, r f g B ≥ r f h B , implies V f g B ≥ V f h B . Additionally, if for some s, g, h, r f g B (s) > r f h B (s), then V f g B (s) > V f h B (s). Let f be an arbitrary element of W A . On the one hand, s R B (s, f ) ⊂ R B (f ). To see this, pick g ∈ s R B (s, f ). Then for all h ∈ W B , r f g B ≥ r f h B and therefore V f g B ≥ V f h B : this means g ∈ R B (f ). The set R B (f ) is therefore nonempty. On the other hand, R B (f ) ⊂ s R B (s, f ). To see this, pick g ∈ R B (f ) (the set is not empty). If it is not in s R B (s, f ), then there is some s and some b ∈ R B (s, f ) such that r f b B (s) > r f g B (s). Then the policy h ∈ W B which coincides with g except at state s where h(s) = b, is such that V f h B (s) > V f g B (s), a contradiction. Therefore, s R B (s, f ) = R B (f ), for all f ∈ W A .
At this point, we have shown that Player B reacts the same way to Player A's strategy f , in the SSSE problem or in the FPE problem with any scrap value function v. Nevertheless, we cannot conclude that the strong reaction is the same, since that of the FPE problem does depend on the scrap value v.

However, we know that Player B's tie-breaking problem in (1.4) is a Markov Decision Problem. This means that the value of Player A after Player B's strong reaction, say V f A , is given by a Bellman equation, namely:

V f A (s) = max g∈R B (f ) {r f g A (s) + β A (Q f g V f A )(s)} = max b∈R B (s,f ) {r f b A (s) + β A (Q f b V f A )(s)} (3.3)
for all s ∈ S. Here, we have used the fact that R B (f ) is a cartesian product, and that MDPs can be solved state by state. We recognize in the right-hand side of (3.3) the operator T f A defined in (2.10). In other words,

V f A is the fixed point of T f A . Let then define U A ∈ F(S) as: U A (s) = max f ∈W A V f A (s) = V fs A (s) .
Here, f s ∈ W A realizes the maximum for state s. By construction, U A (s) ≥ V f A (s) for any particular f ∈ W A . We proceed to prove that U A = V * A . First, consider the action of T A on U A : for s ∈ S,

(T A U A )(s) = max f ∈W A (T f A U A )(s) ≥ (T fs A U A )(s) ≥ (T fs A V fs A )(s) = V fs A (s) = U A (s) .
The first equality is the definition of T A . The first inequality is clear. The second one results from the monotonicity of operator T f A . The second equality is because V fs is the fixed point of T fs A . Then according to Lemma 3,

T A U A ≥ U A implies U A ≤ V * A since V * A is the fixed point of T A . Now, since V * A = V f * A , the fixed point of operator T f * A , then for all s ∈ S, U A (s) = max f V f A (s) ≥ V f * A (s) = V * A (s). In other words, U A ≥ V * A . We conclude that indeed U A = V * A . As a consequence, we have shown that f * ∈ ∩ s∈S R A (s), that is, (f * , g * ) is an SSSE.

Zero-Sum Games

In zero-sum games, β A = β B and r B = -r A .

Theorem 7.

If the game G is a Zero-Sum Game, then it admits an FPE.

The existence of an FPE follows from the contractivity of the operator associated, in a similar way as in [START_REF] Denardo | Contraction Mappings in the Theory Underlying Dynamic Programming[END_REF]Section 8] for Nash Equilibria in Stochastic Games. We include here an argument in the line of the proof of Theorem 1.

Inria Proof. Consider a function v in the set W = {v ∈ F(S) × F(S)|v B = -v A }. Since v B can be substituted with -v A , it turns out that SR B (s, f, v) = R B (s, f, v B ) = R B (s, f, -v A )
and γ B (s, f, v) can be made dependent only on v A ; in other words, it satisfies (2.7). It is then possible to define the operator T f A as in (2.9). This operator maps W to W. On the other hand, (T

f A v A )(s) = (T f,γ(s,f,v A ) A v A )(s) = (T f,g A v A )(s) for all g ∈ R B (s, f, v A ). But for every f, g, T f g A v A = -T f g B v B .
And by definition (2.1), for all

g ∈ R B (s, f, v A ), h ∈ W B , (T f g B v B )(s) ≥ (T f h B v B )(s), which is equivalent to (T f g A v A )(s) ≤ (T f h A v A )(s). In other words, R B (s, f, v A ) = arg min g∈W B (T f g A v A )(s) so that (T f A v A )(s) = min g∈W B (T f g A v A )(s) .
As it was the case in (2.10), the minimization set in the right-hand side does not depend on v A . The proof of Theorem 1 then applies mutatis mutandis, to conclude that operator T A is contractive on W. It then admits a fixed point v * A in that set. Then the argument in the proof of Theorem 5 applies, and the FPE of the game is constructed from this fixed point.

Team Games

A result of [START_REF] Vorobeychik | Computing Stackelberg Equilibria in Discounted Stochastic Games[END_REF] (Proposition 1) is that Team Games have an SSSE. Team Games (also known as Identical-Goal Games in [START_REF] Simaan | On the Stackeberg Strategy in Nonzero-Sum Games[END_REF]) are such that both players seek to maximize the same metric. This is a property of reward functions only. We slightly generalize the definition of these games and state a similar result for FPE.

Definition 5 (Team Game). The game is a Team Game if β A = β B and there exists real constants µ and ν > 0 such that: r ab B (s) = µ + νr ab A (s).

Theorem 8.

If the game G is a Team Game, then it admits an FPE.

Proof. We adapt the proof of Theorem 7. Consider a function v in the set andγ B (s, f, v) can be made dependent only on v A ; in other words, it satisfies (2.7). It is then possible to define the operator T f A as in (2.9), mapping F(S) to F(S). On the other hand, (T

W = {v ∈ F(S) × F(S)|v B = µ 1-β + νv A }. Since v B can be expressed as a function of v A , then SR B (s, f, v)
f A v A )(s) = (T f,γ(s,f,v A ) A v A )(s) = (T f,g A v A )(s) for all g ∈ R B (s, f, v A ). A straightforward calculation concludes that for every f, g, T f g B v B = µ 1-β + νT f g A v A .
The operator T f g then maps W to W and so does T

∈ R B (s, f, v A ), h ∈ W B , (T f g B v B )(s) ≥ (T f h B v B )(s), which is equivalent to (T f g A v A )(s) ≥ (T f h A v A )(s) since ν > 0. In other words, R B (s, f, v A ) = arg max g∈W B (T f g A v A )(s) so that (T f A v A )(s) = max g∈W B (T f g A v A )(s) .
As it was the case in (2.10), the maximization set in the right-hand side does not depend on v A . The proof concludes as in the proof of Theorem 7.

Acyclic Games

Acyclic games are such that state-to-state transitions do not lead back to a visited state, except for absorbing states. Acyclicity is a property of transition operators only.

We say that state s is reachable from state s if there exist k ∈ N, a sequence of states s = s 0 , s 1 , . . . , s k = s and actions a 0 , . . . ,

a k-1 , b 0 , . . . , b k-1 with Q a 0 b 0 (s 1 |s 0 ) × Q a 1 b 1 (s 2 |s 1 ) × . . . × Q a k-1 b k-1 (s k |s k-1 ) > 0.
Definition 6 (Acyclic Games). The game is an Acyclic Game if the state space S admits the partition S = S ⊥ ∪ S 1 , with:

• for all s ∈ S ⊥ , a ∈ A s , b ∈ B s , Q ab (s|s) = 1;
• for every pair (s, s ) ∈ S 1 × S 1 , if s is reachable from s, then s is not reachable from s .

The following theorem is based on Theorem 4 and generalizes it for the FPE part.

Theorem 9. If the stochastic game G is an Acyclic Game, then it admits an FPE.

Proof. The proof will proceed by successive reductions to static (or single-state) games. The game being acyclic, it is possible to perform a topological sort of the state space.

There exists a partition S = ∪ K k=0 S k with S 0 = S ⊥ and for every s ∈ S k , k > 0, if s is reachable from s then s ∈ S k with k < k. In a first step, we construct a candidate strategy (f * , g * ). Then we prove that this strategy solves the FPE problem.

For each s 0 ∈ S 0 = S ⊥ , consider G 0 , the single-state game with S = {s 0 } and same strategies, rewards and discount factors. Theorem 4 applies to this game. It states that an FPE exists, resulting in a pair of strategies (f * s 0 , g * s 0 ) ∈ P(A s 0 ) × P(B s 0 ) and a value V * (s 0 ).

We now construct the strategies (f * s k , g * s k ) for s k ∈ S k with a recurrence on k. Assume this has been done up to k -1. Pick s k ∈ S k . Because the game is acyclic, we have, for any (f, g)

∈ W A × W B , V f g i (s k ) = r f g i (s k ) + β i k-1 =0 s ∈S Q f g (s |s)V * i (s ) . ( 3

Inria

We now prove that this strategy is an FPE. We prove this with a recurrence. More precisely, we prove that for all k, property P k holds, which says that for and all s k ∈ S k :

g * (s k ) = γ B (s k , f * , V * ) f * (s k ) = R A (s k , V * )
where

V * i = V f * g * i
is the unique fixed point of operator T f * g * i for i = A, B. With Definition 3, the result will follow.

When s 0 ∈ S 0 , the local reaction set LR B (s 0 , f, V * ) does not depend on V * and {g * s 0 } ∈ LR B (s 0 , f * , V * ), as in the proof of Theorem 4. In particular, it follows that g * (s 0 ) = γ B (s 0 , f * , V * ) and f * = R A (s 0 , V * ). So P 0 holds.

Assume now that property P holds for all < k. Let s k ∈ S k . Then

(T f * g B V * B )(s k ) = r f * g i (s k ) + β i k-1 =0 s ∈S Q f * g (s |s)V * B (s ),
to be compared with (3.4). Then since (f * s k , g * s k ) solves (locally) the SSE for the subgame defined by (3.4), then g *

s k = γ B (s k , f * , V * ) and f * s k ∈ R A (s k , V *
) by construction. So property P k holds. By recurrence, P K holds and (f * , g * ) is an FPE.

In contrast with Theorem 4, the existence of SSSE is not guaranteed for acyclic games. In Section 4.3 we study a game without an SSSE. This game is not acyclic, but it is possible to "approximate" it with an acyclic game which will have the same qualitative properties. On the other hand, if the transitions of a game are deterministic, in other words if the game is a multi-stage game, then it is MFS and it does have an SSSE according to Theorem 6.

Numerical Examples.

In this section, we present examples illustrating different situations that can occur by comparing the solutions returned by the different algorithms presented in Section 2.

In the example of Section 4.2, VI converges to some FPE. Also we show that the FPE is an SSSE and the solution returned by (MP). The model involved does not satisfy the sufficient conditions for existence and convergence identified in Sections 2.3 and 3. In Section 4.3, we describe an example where, depending on the discount factors β A , β B : either an SSSE exists and does not coincide with the FPE, or an SSSE does not exist, or an FPE does not exist. Finally, in Section 4.4, we describe an example where an FPE is shown to exist, but VI does not necessarily converge to it.

Experimental setup

The numerical experiments involving Value Iteration and Policy Iteration were performed using Python 3.6, on a machine running under MacOS, a processor of 2,6 GHz Intel Core i5, and memory of 8 GB 1600 MHz DDR3. Operator T is implemented with Cplex 12.8.

To solve the linear systems involved in T f g we use the Python library Numpy. In order to solve (MP) we use the KNITRO 12.0 solver combined with AMPL.

The data of the experiments is presented tables with the convention of the following figure. It shows the relevant parameters when the system is in state s, Player A performs action a and Player B performs action b:

b a (Q ab (s 1 |s), Q ab (s 2 |s)) (r ab A (s), r ab B (s))

Example 1: FPE and SSSE coincide and VI converges

State s2

Table 1: Transition matrix and payoffs for each player.

This example does not satisfy any of the sufficient conditions listed in Sections 2 and 3. However, both Value Iteration and Policy Iteration converge to the FPE, and furthermore the FPE, the SSSE and the optimal solution returned by (MP) coincide. The application of Value Iteration, starting with the null function, results in the evolution displayed in Figure 1. Given that Value Iteration converges, an FPE exists. The policies and values are given in Table 2. Detailed algebraic manipulations of the value functions given the data in this example allows us to show that the SSSE satisfies the values in Table 2. Then, we show that this solution is a fixed point for operator T . These details are provided in Appendix C.1.

Example 2: FPE and SSSE are different

In this section we will study the stochastic game given by the data in Table 3. This game has two states and two actions per state. Figure 2 shows a diagram of the possible transition between states. State s 1 is absorbing for any combination of actions.

b1 b2 a1 (1, 0) (-1, -2) (1, 0) (-2, 1) a2 (1, 0) (0, 0) (1, 0) (2, 0) State s1 b1 b2 a1 (1, 0) (-1, -2) (1, 0) (-2, -2) a2 (0, 1) (0, 1) (1, 0) (1, 1)

State s2

Table 3: Transition matrix and payoffs for each player in Example 2 for both equilibrium concepts, FPE and SSSE, changes. For β A < 1 5 the existence of an FPE is guaranteed, but no SSSE exist. This comes from the fact that for these values of

s 2 s 1 (a 2 , b 1 ) = (a 2 , b 1 )
β A , R A (s 1 ) = {a 1 } × {(f 2 , 1 -f 2 ) : f 2 ∈ [0, 1]} and R A (s 2 ) = {a 2 } × {a 2 }. Clearly, R A (s 1 ) ∩ R A (s 2 ) = ∅
and therefore there is no SSSE. When the game starts in the absorbing state s 1 , the optimal policy for the leader is to play and announce the (static) SSE in s 1 and an arbitrary strategy in s 2 . When the game starts in s 2 , the leader has the incentive to announce a sub-optimal strategy in s 1 in order to remain in state s 2 and increase his expected reward. This could be done only for low values of β A .

In the interval β A ∈ [ 1 5 , 1 3 ], both SSSE and FPE exists, but the strategies and values are different. On the other hand, whenever β A > 1 3 , there is no FPE. This information is summarized in Table 4. The details of this analysis are provided in Appendix C.2. We explain in particular, in Section C.2.3.2.1, the complex dynamics of the operator when β A > 1 3 . The dynamics of Value Iteration is numerically illustrated in Figure 3. In the top two graphs, β A > 1/3 and the iterations for state s 2 exhibit a cycle of order 3. In the bottom two graphs, β A < 1/3 and Value Iteration converges for both states to the FPE identified in Table 4. 5 summarizes the results obtained. In this experiment whenever the SSSE exists (β A ∈ { 1 4 , 1 2 }), (MP) computes it correctly and Policy Iteration converges to the FPE. When no SSSE exists (β A ∈ {0, 1 8 }), (MP) returns a value that is influenced by the vector of weights α s . In these cases Policy iteration converges to an FPE that is different from the solution found by (MP).

SSSE FPE

β A v A (s 1 ) v A (s 2 ) v B (s 1 ) v B (s 2 ) v A (s 1 ) v A (s 2 ) v B (s 1 ) v B (s 2 ) [0, 1 5 ) No No No No 2 1-β A 0 0 1 1-β B [ 1 5 , 1 3 ] 2 1-β A 2β A 1-β A 0 0 2 1-β A 0 0 1 1-β B ( 1 3 , 1) 2 1-β A 2β A 1-β A 0 0 No No No No

Example 3: FPE exists but VI does not converge to it

We now develop an example where an FPE does exist, but Value Iteration does not necessarily converge to it. The data of this example is listed in Table 6.

Consider

β A = β B = 1 2 .
We claim that the pair of strategies (f * , g * ) and value functions (v * A , v * B ) in Table 7 constitute both an SSSE and an FPE. We provide in Appendix C.3 justifications for this claim. (MP) (PI)

β A α s 1 = 100 α s 2 = 1 α s 1 = 1 α s 2 = 100 α s 1 = 1 α s 2 = 1 s 1 s 2 0 v A 2 ∼ 0 -2 1 2 ∼ 0 2 0 v B ∼ 0 ∼ 0 2 2 ∼ 0 ∼ 0 0 2 f (0,1) ( 1 3 , 2 3 ) (1,0) (0,1) (0,1) ( 1 3 , 2 3
) (0,1) (0,1) g (0,1) (0,1) (0,1) (0,1) (0,1) (0,1) (0,1) (1,0)

∼ 0 ∼ 0 2 2 ∼ 0 ∼ 0 0 2 f (0,1) ( 1 3 , 2 3 ) (1,0) (0,1) (0,1) ( 1 3 , 2 3
) (0,1) (0,1) g (0,1) (0,1) (0,1) (0,1) (0,1) (0,1) (0,1) (1,0)

1 4 v A 8/3 2/3 8/3 2/3 8/3 2/3 8/3 0 v B ∼ 0 ∼ 0 ∼ 0 ∼ 0 ∼ 0 ∼ 0 0 2 f (0,1) ( 1 3 , 2 3 ) (0,1) ( 1 3 , 2 3 ) (0,1) ( 1 3 , 2 3
) (0,1) (0, 1) g (0,1) (0,1) (0,1) (0,1) (0,1) (0,1) (0,1) (1,0) (1, 0) (0, 1)

1 2 v A 4 2 4 2 4 2 - - v B ∼ 0 ∼ 0 ∼ 0 ∼ 0 ∼ 0 ∼ 0 - - f (0,1) ( 1 3 , 2 3 ) (0,1) ( 1 3 , 2 3 ) (0,1) ( 1 3 , 2 3 ) - - g (0,1) (0,1) (0,1) (0,1) (0,1) (0,1) - - Table 5:
a2 (1, 0) (0, 1) (0, 1) (1, -1)

State s2

Table 6: Transition matrix and payoffs for each player in Example 3

s 1 s 2 Play of A (1, 0) (5 - √ 19,-4 + √ 19) Play of B b 2 b 2 v A 1 5 (-3 + √ 19) 1 5 (-6 + 2 √ 19) v B 1 5 (16 -2 √ 19) 1 5 (22 -4 √ 19)
Table 7: Values and Policies forming an SSSE and FPE.

Inria

When applying Value Iteration with the null function as a starting point, we get however the evolution in Figure 4. Values obtained with Policy Iteration have a similar behavior. Finally, (MP) returns as the optimal solution the SSSE (and FPE). In this section we present an example of a stochastic game that models the interaction between a security patrol and an attacker. In this game a defender has to patrol (or "cover") a set of locations and an attacker wants to perform an attack in one of these locations, both maximizing their expected rewards. The state of the game, known to both players, is defined by the locations of the defender and attacker and whether an attack occurred or not. Given this information, the leader decides on a patrolling strategy (a location to patrol) which is also known to the attacker when deciding two things: where to move and if he performs an attack or not. Once the attack is performed the game ends in one of two terminal states. This game model situations where the defender has the information where the possible attacker it is located, but they cannot perform any action if an attack is not performed. In real situations, it can be the case of demonstrations or high-risk football matches.

The rewards mainly depend on the place where the attack is performed and whether the location is being covered or not. The effectiveness of the player's movements is influenced by random factors: when they decide to move to some location this move may fail due to external factors, in which case they remain in their current location.

Game description

We introduce now the elements of the model and the notation. A synthesis of this notation is presented in Appendix A. Formally, we consider a set of locations to patrol/targets L = { 1 , 2 , ..., n }. There are some connections allowed between locations represented by edges (denoted by E), so the board of the game is actually a graph (L, E). Player A is the defender, Player B is the attacker. The state space is S = L × L × {0, 1} ∪ {⊥ 0 , ⊥ 1 }. A ,( B ,α)) ∈ S represents the defender's location ( A ∈ L) and the attacker's location ( B ∈ L). The binary parameter α takes the value 1 if the attacker is committing an attack or 0 if he is not, thereby being unnoticed in that period. There are also two special fictitious states ⊥ 0 , ⊥ 1 representing the state of the game once the attack was performed. ⊥ 1 represents the case where the attack is successful and ⊥ 0 when the attacker is caught. These two are absorbing states in our game.

A typical state s = (

The action space A s ⊂ L for the leader represents all the possible location that he can achieve from its current position (given by the state s). For the follower, B s ⊂ L × {0, 1} represents all the possible locations that the attacker can achieve in the state s with and the decision whether to attack or stay unnoticed. We use the notation ∈ L to represent the action of "move to " and α ∈ {0, 1} to represent the action of "attacking" or "stay unnoticed" respectively. In states s ∈ {⊥ 0 , ⊥ 1 }, actions are irrelevant: we can pick A s = L and B s = L × {0, 1} for such states by convention.

The probability of transitions between states is constructed using the function q i ( | ) which denotes the probability that player i ∈ {A, B} reaches location from having decided to move to . We assume that these probabilities are independent between players. In particular, if there is no failure in Player i's movements, then q i ( | ) = 1 if = , and 0 otherwise. The transition probabilities Q ab (z|s) are then defined from these quantities by expressions (5.1)-( 5.3) as follows:

Q ab (z| ⊥ i ) = 1 z =⊥ i , i ∈ {0, 1}, (a, b) ∈ A ⊥ i × B ⊥ i 0 otherwise. (5.1) Q A ,( B ,α) ( A , ( B , α)| A , ( B , 0))) = q A A ( A | A ) q B B ( B | B ) α ∈ {0, 1}, A ∈ A A , ( B , α) ∈ B B , (5.2) Q A ,( B ,α) (z| A , ( B , 1))) =      1 z =⊥ 0 and A = B 1
z =⊥ 1 and A = B 0 otherwise.

(5.3)

Rewards result from the interaction, or lack thereof, between the defender and the attacker. Following the notation used in security games, we denote U u A ( ) < 0 and U c A ( ) > 0 the penalty and the benefit for the defender if an attack is performed in , which depends only if the target is uncovered (superscript u) or covered (superscript c). Similarly, we define U u B ( ) > 0 and U c B ( ) < 0 the reward (and penalty respectively) of the attacker if the location attacked is uncovered or not. Instant rewards r A and r B are defined as the expected values of the rewards R i = R ab i (z|s), i ∈ {A, B}, of the dynamics between players, which depends on the current state of the system s, the actions (a, b) performed by the players and the future state of the system z. This technique is fairly standard, as it is shown in [START_REF] Puterman | Markov decision processes[END_REF]Ch. 2,pp.20]. The expressions for R ab i (z|s), i = A, B are Inria listed in (5.4), in which s is any state and z = ( A , ( B , α)).

R ab A (z|s) R ab B (z|s) U u A ( B ) U u B ( B ) A = B and α = 1 U c A ( B ) U c B ( B ) A = B and α = 1 P A ( A ) P B ( B ) α = 0 P A (⊥ 0 ) P B (⊥ 0 ) z =⊥ 0 P A (⊥ 1 ) P B (⊥ 1 ) z =⊥ 1 (5.4)
The first two lines represent the payoffs when the attack is performed, z = ( A , ( B , 1)). In the third line, P B ( B ) < 0 represents the opportunity cost and risk for the attacker of being in location B and not perform an attack. In the two last lines P A and P B represents the residual value of being in an absorbing state. We assume P A (⊥ 0 ) > 0 and P A (⊥ 1 ) < 0 and the opposite for the attacker. From the definition of R A and R B we obtain instants rewards r A and r B as follows:

r ab i (s) = z∈S Q ab (z|s)R ab i (z|s) i ∈ {A, B}.
The dynamics of the game is summarized as follow: First, at the start of any epoch, the system is in a state formed by the location the both players and the behaviour of the attacker. Then, the defender knowing the state of the game chooses a strategy f (probably mixed) over the locations reachable from his current location. The attacker observes the strategy and chooses where to move and whether to attack or not. We denote this action as g. Note, that if the attacker decide to attack, the success or failure of his strategy will be revealed in the next state. The system evolves to the following state influenced by f , g, and Q. Both players receive their payoffs.

Computational study

Here we evaluate the solution algorithms presented in terms of solution time and quality of the solution obtained. We begin by describing the instances of the graph surveillance problem constructed for this computational study. We compare the solution times of Value Iteration and Policy Iteration on every instance considered. Solving the (MP) formulation was not a competitive solution approach for these problems. Even for the smallest instance considered, solving the (MP) formulation using a state-of-the-art non-linear optimization package did not return a solution after more than 5 hours of computational time, which far exceeds the solution times observed for Value Iteration and Policy Iteration over all instances. We therefore do not present computational results of solving the (MP) formulation. The experimental setup used is the one described in Section 4. To evaluate the quality of the FPE solutions obtained by these algorithms we compare them to heuristic policies, both in the myopic and non-myopic follower case.

We generate instances of different structure and size by considering different graphs to patrol on: paths, cycles, T-shaped graphs and complete graphs. We limit the size of A s and B s by limiting the distance that each player can travel from one time step to the next. To do so, we introduce the parameter k as the maximum geodesic distance that each player can travel through one time step.

Functions q A ( | ) are a function of the nodes that are in the shortest path between and . We denote this set of nodes as SP ( , ) = { , i 2 , . . . , i k-1 , }. Probabilities q A are defined as follows: if |SP ( , )| = 1 and SP ( ,

) = { }, then q A ( | ) = 1, if |SP ( , )| ≥ 2 then q A ( | ) =        1 - = |SP ( , )| -1 ∈ SP ( , )\{ } 0 otherwise.
(5.5)

In our experiments we set the probability of failing to = 0.25. We assume q B ( | ) = 1 = are deterministic: the attacker always succeeds with its intended move. The payoff functions are defined in Table 8. The values of each parameter depend on the degree of the node, representing the fact that nodes with greater degree are more important in order to keep the connectivity of the graph.

Parameter Value Parameter Value U u A ( ) -10deg( ) U c A ( ) 10deg( ) U u B ( ) 2 deg( ) U c B ( ) -2 deg( ) P A ( A ) 0 P B ( B ) -deg( B ) P A (⊥ 0 ) 1 P A (⊥ 1 ) -1 P B (⊥ 0 ) -1 P B (⊥ 1 ) 1
Table 8: Payoff functions description

We test our models in instances with n ∈ {5, 10}, β B = {0, 0.9} and k ∈ {2, 3} for each type of graph. We show how the instances increase with n and k in Table 9, which gives the size of the state set and the average size of the sets of actions for every instance considered. The stopping criterion is set to ε = 10 -3 for both Value Iteration and Policy Iteration.

The experimental setup is the one described in Section 4.1. Figure 5 shows the solution times in a performance profile in logarithmic scale comparing Value Iteration and Policy Iteration over all the instances considered. Policy iteration has faster solution times over the instances tested. We present the solution time results separated for each instance type in Figure 6. The results show that graph structure does not influence significantly the solution times of Value Iteration and Policy Iteration.

We now aim to evaluate the quality of the Stackelberg equilibrium solution for this discounted game. However, since we do not have a method to compute the SSSE in general, we use the FPE that can be computed using Value Iteration as a proxy. Accordingly, we compute the values of equilibrium v * = (v * A , v * B ), with the respective equilibrium policies f * and g * using the Value Iteration algorithm.

We compare the FPE solution to static policies obtained by ignoring the dynamic nature of the game. We refer to these heuristic policies as Myopic policies. the Myopic policy, for each state we compute the Strong Stackelberg policies, f M , g M of the static game, that is with β A = β B = 0. Finally, we evaluate this policy in the dynamic setting: we obtain the value

V f M g M = v M = (v M A , v M B ) as the fixed point of operator T f M g M (see (2.6)) with real values of β A and β B .
Finally, in order to compare the policies obtained for both methods we compare the average value for applying each policy, denoted respectively as v *

A , v * B , vM A and vM B , where v = |S| -1 s∈S v(s). Table 10 shows the comparison of the values for the different types of graph structures mentioned before, and with the parameters n = 10, k = 2, β A = 0.9 and β B = 0. Recall that in this case, Value Iteration converges to an FPE (and SSSE) because the game is MFS. For the complete graph, the myopic strategy generates in average the same reward as the equilibrium strategy. In the other cases, the SSSE strategy outperforms the myopic-heuristic policy. We repeat the same evaluation, but now with β B = 0.9. Note that in this case there are no guarantees that Value Iteration will converge, or that the FPE policy is an SSSE. Value Iteration found an FPE (i.e. converged) in all the instances. Table 11 Note that in relative terms, both the FPE policy and the Myopic policy return a lower average value for Player A. This can be attributed to the follower's change of behavior. More significantly, the FPE solution found obtains lower values for the leader than the Myopic strategy, significantly smaller except for the Complete graph, which is smaller but comparable. In this case, with β B = 0.9, the game does not satisfy MFS and the FPE solution obtained by the Value Iteration may not correspond to the SSSE, which may lead to inefficient solutions.

Conclusions and Further Work

In this paper, we have demonstrated the relevance of the concept of Strong Stationary Stackelberg Equilibria, SSSE, and the related operator-based algorithms, for the computation of policies in the context of two-player discounted stochastic games.

For this, we first defined a suitable operator acting on the set of value functions for both players. We introduced the concept of Fixed-Point Equilibrium, FPE, as the fixed points of this operator. We then investigated the relationship between SSSE and FPE. We show that neither need to exist in general, and that when they do, they do not necessarily coincide. We also show that the solution based on Mathematical Programming suggested in the literature, does not necessarily compute a correct answer. We have nevertheless identified several classes of games where SSSE and FPE do exist and do coincide. Among these is the class of games with Myopic Follower Strategies, MFS, which include games with myopic followers and games with leader controlled transitions.

We consider an application in a security domain, in which a moving defender protects locations on a graph that can be attacked by a moving attacker. We give a formulation of this problem as a Stackelberg equilibrium in a discounted stochastic game. The Value Iteration and Policy Iterations algorithms are able to compute efficiently the FPE for the instances considered of this security application. The instances considered were too difficult to solve if using the Mathematical Programming formulation of the problem. In the case of myopic follower, in which the FPE corresponds to the SSSE, we observe that the solution obtained is efficient and outperforms heuristic policies. However, in examples without MFS, we see that the FPE solution computed is worse than heuristic policies. Future research will aim at identifying more general sufficient conditions for the two concepts, SSSE and FPE, to coincide. The problem of finding general methodologies to detect the existence of SSSE is still open. It is also important to determine algorithms to find the equilibrium in games which possess SSSEs but do not satisfy the MFS condition. Finally, It will also be interesting to determine whether the use of Value Iteration or Policy iteration, when they do not converge, can nevertheless produce nonstationary strategies with a good performance.

A Notation Summary

We list in the following tables the principal notation used in the paper. Table 12 groups the notation related to the general model. Table 13 Policies for the Leader (Player A) and the Follower (Player B) respectively.

V f g i (s)
Expected discounted sum of all rewards for Player i, when policies f and g is applied and the starting state is s.

RB, SRB

Set of optimal responses (and strong respectively) for the Follower. γB Best response which is performed for the Follower.

RA(s)

Best strategies for the Leader starting in state s. vi

Value function for Player i.

F(S)

Set of value functions S → R. T f g i One-step operator for any fixed pair of policies f and g. T Dynamic programming operator. γ B Best response of the Follower when it does not depend on vB. T f A , T One-step operator and Dynamic programming operator when T does not depend on vB.

Mi

Upper bound in value functions for Player i.

Table 12: Table of general notation

Application: Surveillance in a graph L, E Set of locations and connections between locations.

⊥0, ⊥1

Absorbing states of the game. α Binary decision of attack or not.

U u i ( ), U c i ( )
Reward or penalty for player i when an attack is performed in location and it is being protected (c) or unprotected (u).

Pi

Rewards and costs for player i when an attack is not performed. We provide an algorithmic proof for the existence of SSSE in Theorem 4. This proof is also useful because it allows to compute a SSE in the static case, which is an important step in Algorithms 1, 2 and 4.

q i ( | )

Lemma 6.

If the game G is static (i.e. has only one state), then it has a SSSE.

Proof. Proof. Since the state space has only one state, we omit the reference to states in the notation. For each action b ∈ B, define the following problem LP(b):

LP(b) max a∈A r ab A f (a) (B.1) s.t. a∈A r ab B f (a) ≥ a∈A r ab B f (a) ∀b ∈ B (B.2) a∈A f (a) = 1 (B.3) f (a) ≥ 0 ∀a ∈ A. (B.4)
Consider Algorithm 5. Each of these LPs is bounded. Therefore, they are either unfeasible or they have a finite optimal solution. Furthermore, at least one of them is feasible. In that case, the optimal value represents the maximum value achieved by incentivising to the follower to play b. By picking the maximum of these values, the optimal f of that LP with the action b is an SSE for the game. Retrieve f (b) and v * (b), respectively the leader's optimal policy given that the follower plays b, and its value

Algorithm 5 Multiple LPs Algorithm

V f,b1b2 B (s 1 ) = 20 180 f 1 f 2 -235 f 1 + 144 f 2 -55 -9 f 1 -36 f 2 + 67 V f,b1b2 B (s 2 ) = 20 180 f 1 f 2 -207 f 1 + 176 f 2 -83 -9 f 1 -36 f 2 + 67 V f,b2b1 B (s 1 ) = 20 225 f 1 f 2 -245 f 1 + 18 f 2 + 26 -36 f 1 -9 f 2 -13 V f,b2b1 B (s 2 ) = 20 225 f 1 f 2 -225 f 1 + 48 f 2 -2 -36 f 1 -9 f 2 -13 V f,b2b2 B (s 1 ) = 20 27 f 1 f 2 + 5 f 1 + 18 f 2 -20 9 f 1 -9 f 2 + 10 V f,b2b2 B (s 2 ) = 20 27 f 1 f 2 + 26 f 2 -23 9 f 1 -9 f 2 + 10 .

C.1.2.2 Analysis of values.

The objective is to compute, for every state, the best strategy f ∈ W A for Player A: the set R A (s). A SSSE will exist if and only if the intersection of these sets is nonempty.

C.1.2.2.1 Optimization for Player B.

First of all, we identify the sets R B (f ), that is, the solutions to Player B's MDP problem. This is done by calculating the "zones" where some policy g = (b i , b j ) ∈ W B is optimal, formally defined as

Z ij = {f ∈ W A , (b i , b j ) ∈ R B (f )}.
We successively compute the differences

V f,b 1 b 1 B (s) -V f,b 1 b 2 B (s), V f,b 1 b 2 B (s) -V f,b 2 b 2 B
(s), etc. and we identify four critical lines separating the four zones Z ij i, j = 1, 2, as represented in Figure 7.

C.1.2.2.2 Optimization for Player A.

According to the preferences of Player B, we have identified in the previous section a covering of W A in four sets Z ij , on which we proceed to find Player A's maximum (this is a covering and not a partition, since the sets Z ij are not disjoint).

The plot of the functions f → V f,γ B (f ) A (s) when f ∈ W A , are displayed in Figure 8. We deduce from this that the global maximum of both V 1 as a rational function of it. Finally, there exists a SSSE, given by the elements in Table 2. 2, we can check whether this strategy satisfies the conditions for FPE. Replacing v B (s 1 ) and v B (s 2 ) by the numerical values of Table 2, we obtain the functions (up to rounding of floating-point values):

g B (s 1 , f, b 1 ) = -14.25f + 3.13 g B (s 1 , f, b 2 ) = 11.01f -5.62 g B (s 2 , f, b 1 ) = -15.25f + 9.13 g B (s 2 , f, b 2 ) = 17.01f -11.62.
Likewise for Player A, with the scrap value function v A (s 1 ) = 26.841, v A (s 2 ) = 28.437 (see again Table 2), the gains are given by:

g A (s 1 , f, b 1 ) = 17.64f + 17.23 g A (s 1 , f, b 2 ) = -9.56f + 30.15 g A (s 2 , f, b 1 ) = 9.64f + 22.23 g A (s 2 , f, b 2 ) = -1.56f + 26.15.
Finally, the decision problem of Player A is represented in Figure 9: for each state s, we plot the function g A (s, f ):

f → g A (s, f, b 1 ) 1 {g B (s,f,b 1 )≥g B (s,f,b 2 )} + g A (s, f, b 2 ) 1 {g B (s,f,b 1 )<g B (s,f,b 2 )} .
It is checked that the maximum is attained at the values of f that are given in Table 2. This means that the SSSE is a FPE.

C.2 Analysis of Example 2

In this section, we provide details on the analysis of Example 2 introduced in Section 4.3. We compute the Stationary Strong Stackelberg Equilibria (SSSE) and discuss their existence. We compute the one-step operator and discuss its fixed points (FPE).

C.2.1 Data

The data is presented in Table 15 (also Table 3).

b1 b2 a1

(1, 0) (-1, -2)

(1, 0) (-2, 1) a2 (1, 0) (0, 0) (1, 0) (2, 0) State s1 b1 b2 a1 (1, 0) (-1, -2) (1, 0) (-2, -2) a2 (0, 1) (0, 1) (1, 0) (1, 1)

State s2

Table 15: Transition matrix and payoffs for each player in Example 2

Observe that state s 1 is absorbing whatever the players play, and state s 2 is followed by state s 1 , unless players play the combination (a 2 , b 1 ). This is represented in Figure 2. Also, in state s 2 , Player B's actions are indifferent to her.

C.2.2 Computation of the SSSE

C.2.2.1 Values of stationary strategies.

Given a stationary strategy (f, g), let us compute the value V f g i of this strategy for each player i =A,B. The notation is f i = f (s i , a 1 ) and g i = g(s i , b 1 ). We have:

v A (s 1 ) = f 1 g 1 [-1 + β A v A (s 1 )] + f 1 (1 -g 1 )[-2 + β A v A (s 1 )] + (1 -f 1 )g 1 [0 + β A v A (s 1 )] + (1 -f 1 )(1 -g 1 )[2 + β A v A (s 1 )] Inria B's strategies maximizing v B (s 1 ), is of the form R B (f, s 1 ) = R 1 × {b 1 , b 2 }, where R 1 = arg max{v B (s 1 ), g ∈ {b 1 , b 2 }}.
Clearly with (C.2), Player B prefers b 2 (g 1 = 0) when f 1 = 0. When f 1 = 0, she is indifferent between b 1 and b 2 . In other words: if

f 1 = 0, then R 1 = {b 1 , b 2 }; if f 1 = 0, then R 1 = {b 2 }.
C.2.2.2.2 Player B's response for state s 2 . We look now at the maximum of V f g B (s 2 ) with respect to (g 1 , g 2 ), the values of (f 1 , f 2 ) being fixed. Preliminary. First we replace in (C.4) the term v B (s 1 ) by its value from (C.2):

v B (s 2 ) = 1 1 -(1 -f 2 )g 2 β B 1 -3f 2 + (1 -(1 -f 2 )g 2 )β B f 1 (1 -3g 1 ) 1 -β B = 1 -f 1 -3f 2 + 3f 1 g 1 1 -(1 -f 2 )g 2 β B + f 1 1 -3g 1 1 -β B . (C.5)
We deduce:

∂ ∂g 1 v B (s 2 ) = - 3β B f 1 (1 -(1 -f 2 )g 2 ) (1 -β B )(1 (1 -f 2 )g 2 β B )
.

As a function of (g 1 , g 2 ), v B (s 2 ) is strictly decreasing with respect to g 1 , when β B = 0, f 1 = 0 and 1 -(1 -f 2 )g 2 = 0. Its maximum is then attained at g 1 = 0 for all values of g 2 . It is independent on g 1 in the other cases. We will analyze successively the cases f 1 = 0, and f 1 > 0.

We first assume β B = 0. The case β B = 0 will be handled separately. The case f 1 = 0. Letting f 1 = 0 in the value of Player B, we arrive at:

v B (s 2 ) = 1 -3f 2 1 -(1 -f 2 )g 2 β B ,
which is independent of g 1 as determined above. Since β B > 0, as a function of g 2 , this is strictly increasing if 1 -3f 2 > 0 and f 2 = 1, strictly decreasing if 1 -3f 2 < 0 and f 2 = 1, and constant if 1 -3f 2 = 0 or f 2 = 1. The optimal choice of g 2 is respectively

v B (s 2 ) = 1 -f 1 -3f 2 1 -(1 -f 2 )g 2 β B + f 1 1 -β B .
The derivative of this function of g 2 is:

∂ ∂g 2 v B (s 2 ) = (1 -f 1 -3f 2 )β B (1 -f 2 ) (1 -(1 -f 2 )g 2 β B ) 2 (C.6) Inria 0 Z 11 ∩ Z 21 ∩ Z 22 1 1 1/3 Z 22 Z 21 Z 12 ∩ Z 22 Z 11 ∩ Z 21 0 1 1 1/3 Z 22 Z 21 Z 12 ∩ Z 22 Z 11 ∩ Z 21 Z 11 ∩ Z 12 ∩ Z 21 ∩ Z 22 Z 11 ∩ Z 12 ∩ Z 21 ∩ Z 22 Z 21 ∩ Z 22 Z 21 ∩ Z 22 f 2 f 2 f 1 f 1
v B (s 2 ) = 1 -f 1 + 3f 1 g 1 1 -β B g 2 + f 1 1 -3g 1 1 -β B = 1 1 -β B - β B 1 -β B (1 -g 2 )(3f 1 g 1 -f 1 + 1) 1 -β B g 2 .
It is seen that the second term in the right-hand side is always positive, and is zero when either g 2 = 1, or f 1 = 1 and g 1 = 0. The maximum possible for Player B's value is therefore v B (s 2 ) = 1/(1 -β B ), and it is attained when either g 2 = 1 (independently of f 1 and g 1 : in that case, the point is in Z 11 ∩ Z 21 ), or when f 1 = 1 and g 1 = 0 (independently of g 2 : in that case, the point is in Z 22 as well).

C.2.2.2.3 Optimization for Player A. Preliminary. The best response of Player

B is obtained as R B (s 1 , f ) ∩ R B (s 2 , f ) where these sets have been computed in Section C.2.2.2.2. When f 1 > 0, R B (s 1 , f ) = {b 2 } × {b 1 , b 2 } so that the constraint imposed on R B (s 2 , f ) is that g 1 = b 2 . When f 1 = 0, no constraint is imposed. The set R B (f ) is then as depicted in Figure 10 (right). The difference with R B (f, s 2 ) is that the line {(f 1 , 0), 0 < f 1 ≤ 1} does not belong to Z 11 .
The value v A (s 1 ) is given in (C.1). When we replace the term v A (s 1 ) by this value in (C.3), we get:

v A (s 2 ) = 1 1 -(1 -f 2 )g 2 β A 2f 2 g 2 -3f 2 -g 2 + 1 + (1 -(1 -f 2 )g 2 ) β A 1 -β A (3f 1 g 1 + 2 -4f 1 -2g 1 ) . (C.7)
State s 1 . Similarly as for Player B's optimization, Player A's problem does not depend on f 2 and reduces to the best choice of f 1 . Assume first that f 1 > 0. The set SR B (f ) is not known yet, but whatever it is, Player B plays b 2 (g 1 = 0). Player A's value is then (2 -4f 1 )/(1 -β A ) which would be maximized with f 1 = 0 (but the value is outside the case studied).

If f 1 = 0, Player A, has gain, from (C.1): (2 -2g 1 )/(1 -β A ). In that case also, B will play g 1 = 0.

So Player A gets to choose f 1 knowing that g 1 = 0 in (C.1). The optimum is reached at f 1 = 0. The best for Player A is when she plays a 2 and B reacts with b 2 . In other terms: R A (s 1 ) = {a 2 } × P(A s 2 ). The values are then:

v * A (s 1 ) = 2 1 -β A v * B (s 1 ) = 0. (C.8)
State s 2 . According to the preferences of Player B, we have identified the covering of W A by zones Z ij , i, j = 1, 2, on which we proceed to find Player A's maximum. See again Figure 10 for a visualization. Let

m ij = max{v A (s 2 )|(f 1 , f 2 ) ∈ Z ij }. Zone Z 11 : Z 11 is the segment {(0, f 2 ), f 2 ∈ [0, 1/3]}. 1 Since g 1 = g 2 = 1, we have from (C.7): v A (s 2 ) = - f 2 (1 -β A (1 -f 1 )) 1 -(1 -f 2 )β A 1 1 -β A .
All the factors being positive, it is seen that v A (s 2 ) ≤ 0. If f 2 = 0, v A (s 2 ) = 0 and the maximum is realized. As soon as f 2 > 0, v A (s 2 ) < 0. In conclusion, m 11 = 0, a value realized at point (0, 0).

Zone Z 12 : Z 12 is the segment {(0, f 2 ), f 2 ∈ [1/3, 1]}. Player A's value is: v A (s 2 ) = 1 -3f 2 .
Its maximum is therefore attained at f 2 = 1/3, where m 12 = 0.

Zone Z 21 : Z 21 is the region {(f 1 , f 2 ) ∈ W A |0 ≤ f 2 ≤ (1 -f 1 )/3} ∪ {(f 1 , 1)|0 ≤ f 1 ≤ 1}.
Player A's value writes as:

v A (s 2 ) = f 2 1 -(1 -f 2 )β A β A (3 -4f 1 ) -1 1 -β A .
If f 2 = 0, this is constant equal to 0. If f 2 > 0, this is decreasing with respect to f 1 (strictly if β A > 0 ) and therefore maximal at f 1 = 0. The value obtained reduces to

f 2 1 -β A (1 -f 2 ) 3β A -1 1 -β A 1
As observed in Section C.2.2.2.3, for f = (f1, 0), f1 > 0, strategy (b1, b1) belongs to RB(s2, f ) but not to RB(f ).

Inria

and its behavior as a function of f 2 depends on the sign of 3β A -1. If β A ≤ 1/3, the maximum is at f 2 = 0 with value 0. If β A > 1/3, the maximum is at f 2 = 1. We have the following table for locating the maximum m 21 :

case m 21 location 0 ≤ β A < 1/3 0 f 1 ∈ [0, 1], f 2 = 0 β A = 1/3 0 f 1 = 0, f 2 ∈ [0, 1/3] β A > 1/3 3β A -1 1 -β A f 1 = 0, f 2 = 1 Zone Z 22 : Z 22 is the region {(f 1 , f 2 ) ∈ W A |(1 -f 1 )/3 ≤ f 2 ≤ 1}. Player A's value is: v A (s 2 ) = 1 -3f 2 + 2β A (1 -2f 1 ) 1 -β A .
It is therefore maximized when f 2 is as small as possible, which occurs when

f 1 = 1 -3f 2 for all values of f 1 . When f 1 = 1 -3f 2 , the value of Player A is given by: 3f 2 5β A -1 1 -β A + 1 -3β A 1 -β A = f 1 1 -5β A 1 -β A + 2β A 1 -β A .
The location of m 22 depends on the sign of 5β A -1. Enumerating the cases, we have the following table:

case m 22 location 0 ≤ β A < 1/5 1 -3β A 1 -β A f 1 = 1, f 2 = 0 β A = 1/5 1 2 f 1 = 1 -3f 2 , f 2 ∈ [0, 1/3] β A > 1/5 2β A 1 -β A f 1 = 0, f 2 = 1/3
The case β B = 0. If β B = 0, Player B's value in state s 2 is 1 -3f 2 and does not depend on g 1 nor on g 2 . In other terms, Z 11 = Z 12 = Z 21 = Z 22 = W A . Player A's maximization problem is not constrained, and consists in choosing all four variables f 1 , f 2 , g 1 , g 2 in (C.7). As in the general analysis, we have a dichotomy: either

β A (1 -(1 -f 2 )g 2 ) = 0, either it is not 0.
In the first case, the maximization does not involve f 1 or g 1 . Two possibilities:

• either β A = 0: Player A's value is: v A (s 2 ) = 2f 2 g 2 -3f 2 -g 2 + 1 which is maximized at f 2 = g 2 = 0
. The gain of Player A is then 1.

• or f 2 = 0 and g 2 = 1: in that situation, Player A's value is always 0.

In the second case, one starts with maximizing with respect to (f 1 , g 1 ), which yields f 1 = g 1 = 0 because it is the same as playing the static game in s 1 . Then the analysis proceeds to show that f 2 = g 2 = 0 realizes the maximum.

The conclusion is that in all cases of β A , the optimal strategy of Player A is to play f 1 = f 2 = 0 (play a 2 in both states). Player B will react with g 2 = 0 and g 1 = 0 (unless β A = 0, in which case the value of g 1 is irrelevant for Player A). The values obtained are:

v * A (s 2 ) = 1 + β A 1 -β A v * B (s 2 ) = 1. (C.
R A (s 1 ) s 1 s 2 R A (s 2 ) s 1 s 2 Play of A a 2 P(A s 2 ) Play of A a 1 a 2 Play of B b 2 {b 1 , b 2 } Play of B b 2 b 2 v A (s 1 ) 2 1 -β A v A (s 2 ) 1 -3β A 1 -β A v B (s 1 ) 0 v B (s 2 ) 1 1 -β B
The intersection R A (s 1 ) ∩ R A (s 2 ) is empty: there exist no SSSE.

β A = 1/5 and β B > 0: The set R A (s 1 ) is as above. The set R A (s 2 ) is described in the following table:

R A (s 2 ) s 1 s 2 Play of A (1 -3φ, 3φ) (φ, 1 -φ) Play of B b 2 {b 1 , b 2 } v A (s 2 ) 1/2 v B (s 2 ) 1 -3φ 1 -β B
where φ ∈ [0, 1/3]. When φ = 1/3, the corresponding element of R A (s 2 ) is equal to an element of R A (s 1 ). There is therefore an intersection, which is a SSSE, namely:

f 1 = 0, f 2 = 1/3.
β A > 1/5 and β B > 0: The set R A (s 1 ) is still as above and the set R A (s 2 ) is the element described in the following table:

Inria R A (s 2 ) s 1 s 2 Play of A a 2 (1/3, 2/3) Play of B b 2 b 2 v A (s 2 ) 2β A 1 -β A v B (s 2 ) 0
This set is included in R A (s 1 ). There exists then a unique SSSE equal to this element.

β B = 0: The set R A (s 1 ) is still as above and the set R A (s 2 ) is the element described in the following table:

R A (s 2 ) s 1 s 2 Play of A a 2 a 2 Play of B b 2 b 2 v A (s 2 ) 1 + β A 1 -β A v B (s 2 ) 1
This set is included in R A (s 1 ). There exists then a unique SSSE equal to this element.

C.2.2.4 Concluding comments on SSSE. The non-existence of SSSE for β

A < 1 5
and β B > 0 comes from the fact that R A (s 1 ) ∩ R A (s 2 ) = ∅ in this case. The leader plays different strategies if she starts in state s 1 than if she starts in s 2 . We explain briefly the case for β A = 0. Note that if the game starts in s 1 , then the optimal policy for the leader, will be the same than in the static case, that is a game with only state s 1 . The set of best strategies for the leader is to play f 1 = 0 (play a 2 ) in state s 1 and any arbitrary f 2 ∈ [0, 1]. The follower reacts with b 2 in state s 1 and an arbitrary response in s 2 . In this case, the value functions are v A (s 1 ) = 2 and v B (s 1 ) = 0.

If the game starts in s 2 , the value of Player A is, as we have already seen: From (C.2) and (C.4), and assuming f 2 = 0, Player B's value is: Iterations of T starting in zone Z 21 will follow a sequence of points in the direction of P 21 and eventually enter Z 11 , then follow the cycle as above.

v A (s 2 ) = 2f 2 g 2 -3f 2 -g 2 + 1. It is maximized when f 2 = g 2 = 0, that is, when (a 2 , b 2 ) is played. If Player A performs a 2 ,
v B (s 2 ) = 1 -f 1 + 3f 1 g 1 1 -g 2 β B + f 1 1 -3g 1 1 -β B
Depending on the choice of φ, the mapping from the frontier Z 11 -Z 21 may lead to either Z 11 or Z 22 . It then follows the patterns described.

In all cases, there is a limit cycle. The length of this cycle can range from 3 to ∞ depending on the proximity of β A to 1/3.

C.2.3.2.2 Case β

A ≤ 1/3. In this situation, the fixed-point P 21 of operator T 21 is located in zone Z 21 : it is a FPE. The iterations of T starting in Z 21 will converge to it.

Iterations of T starting in Z 22 will be mapped first to P 22 , then converge to P 21 . Likewise, iterations starting in Z 11 will be mapped first to P 11 in Z 22 , then converge to P 21 . Iterations starting on the frontier Z 11 -Z 21 either converge directly, or make one step in Z 22 .

C.2.3.3

The operator when β B = 0. In the special case β B = 0, the expression for operator T f g B becomes, from e.g. (C.11):

(T f g v) B (s 2 ) = 1 -3f 2 .
Since Player B is indifferent, Player A gets to optimize her own reward, namely,

(T f g v) A (s 2 ) = 2f 2 g 2 -3f 2 -g 2 + 1 + (1 -f 2 )g 2 β A w + (1 -(1 -f 2 )g 2 ) 2β A 1 -β A
with respect to f 2 and g 2 . This optimization concludes that f 2 = 0 is always better. Finally, the expression for the operator is:

(T v) A (s 2 ) = max β A w, 1 + β A 1 -β A RR n°9271 (T v) B (s 2 ) = 1 .
This operator is contractive and has the function in (C.9) as fixed point.

C.2.4 One-step Value Iteration from the SSSE

In this section, we compute the action of VI on the SSSE computed in Section C.2.2.3, that is:

v * A (s 1 ) = 2 1 -β A v * A (s 2 ) = 2β A 1 -β A v * B (s 1 ) = v * B (s 2 ) = 0. (C.14)
The purpose of this is to check again that the SSSE is not an FPE, but also to open the door to an investigation of nonstationary strategies in the context of Dynamic Stackelberg games.

Using the operator defined in Section C.2.3.1, we find that z = 0. We must compare w = (2β A )/(1 -β A ) to L = (1 + β A )/β A /(1 -β A ) and find that w ≤ L. Therefore the FPE lies in the zone Z 22 and it is mapped to P 22 by T . The value obtained is then:

(T v * ) A (s 2 ) = 1 + β A 1 -β A (T v * ) B (s 2 ) = 1,
a function we have identified as the SSSE when β B = 0, see (C.9). Interpretation. Independently of β A , the value of both players is improved by applying the operator once, starting from the SSSE. It means that the policy in which Player A announces she: 1) plays once a 2 ; 2) plays the SSSE afterwards, gives a better reward to both players. This nonstationary policy actually menaces to play the SSSE, since at the first step players will play (a 2 , b 2 ) and send the game to state s 1 . The mixed strategy (1/3, 2/3) of the SSSE will never be played.

C.3 Analysis of Example 3

We provide here the technical justifications for the claims of Section 4.4 on Example 3.

C.3.1 Data

The data of this example is presented in Table 16 (see also Table 6): (C. [START_REF] Vorobeychik | Computing Stackelberg Equilibria in Discounted Stochastic Games[END_REF] In order to support this claim, we need to construct the reaction functions γ B (f * ) (for the SSSE) and γ B (s, f * , v * ) (for the FPE). As a common preliminary step, we first list the one-step rewards corresponding to a general strategy f ∈ W A and any possible action g ∈ B s , for all states s. The notation is f 1 = f (s 1 , a 2 ) and f 2 = f (s 2 , a 1 ).

h A (s 1 , f, b 1 , v A ) = 2f 1 -1 + β A [f 1 v A (s 1 ) + (1 -f 1 )v A (s 2 )] h A (s 1 , f, b 2 , v A ) = f 1 -1 + β A v A (s 2 ) h A (s 2 , f, b 1 , v A ) = -f 2 + β A [f 2 v A (s 2 ) + (1 -f 2 )v A (s 1 )] h A (s 2 , f, b 2 , v A ) = 1 -f 2 + β A [f 2 v A (s 1 ) + (1 -f 2 )v A (s 2 )] h B (s 1 , f, b 1 , v B ) = 1 -2f 1 + β B [f 1 v B (s 1 ) + (1 -f 1 )v B (s 2 )] h B (s 1 , f, b 2 , v B ) = -1 + 2f 1 + β B v B (s 2 ) h B (s 2 , f, b 1 , v B ) = 1 -f 2 + β B [f 2 v B (s 2 ) + (1 -f 2 )v B (s 1 )] h B (s 2 , f, b 2 , v B ) = 2f 2 -1 + β B [f 2 v B (s 1 ) + (1 -f 2 )v B (s 2 )].

C.3.2 Computation of the SSSE

Given a strategy f ∈ W A , we know from MDP theory that the best response of Player B is found among the four pure strategies of W B × W B . The value of each of these strategies for both players is obtained by solving the four equations of the list above, where the combination of s i and b j is the one sought, and where h i (s, f, b, v i ) is replaced with v i (s i ).

When setting β B = 1/2, the four values of V f g B (s 2 ) turn out to be:

V f,b 1 b 1 B (s 2 ) = 6(1 -f 2 )(1 -f 1 ) 3 -f 1 -f 2 V f,b 1 b 2 B (s 2 ) = 2(4f 1 f 2 -f 1 -5f 2 + 2) f 1 -f 2 -2 V f,b 2 b 1 B (s 2 ) = 2(1 -f 2 )(2f 1 + 1) 3 -f 2 V f,b 2 b 2 B (s 2 ) = 2(2f 1 f 2 + 3f 2 -2) f 2 + 2 .
The comparison of these four values determines four zones delimited by lines as in Figure 12. When evaluating Player A's value on each of these zones, including the boundaries, it is found that A's optimum lies at the point specified in (C. ). In addition, it is checked that for these values of f (s, a 1 ),

h A (s 1 , f, b 1 , v * A ) > h(s 1 , f, b 2 , v * A ) h A (s 2 , f, b 1 , v * A ) < h(s 2 , f, b 2 , v * A )
so that the "strong" response of Player B is:

γ B (s 1 , f, v) = b 1 if f 1 ≤ f * 1 b 2 if f 1 > f * 1 γ B (s 2 , f, v) = b 1 if f 2 < f * 2 b 2 if f 2 ≥ f * 2 .
In particular, this confirms that γ B (s, f * , v) = {b 2 } for s = s 1 , s 2 . Then, the functions g A (s, f ) := h A (s, f, γ(s, f, v), v * A ) for both states s are represented in Figure 14. It is concluded that

R A (s 1 , v) = {(f * 1 , 1 -f * 1 ), (1, 0)} R A (s 2 , v) = {(f * 2 , 1 -f * 2 )}.
So indeed, the policy f * of (C.15) is such that f * (s) ∈ R A (s, v) for all s.

There remains to check that the values v * A and v * B provided are indeed the values of the policy (f * , g * ). Indeed: We have therefore proved that v * = V f * g * , g * (s) = γ(s, f * , v * ) and f * ∈ R A (s, v * ) for all s. The solution proposed in then a FPE.

h A (s 1 , f * , b 2 , v * A ) = β A v * A (s 2 ) = -3 + √ 19 5 = v * A (

fA

  : F(S) → F(S), defined in (2.9) is a contraction on (F(S), || • || ∞ ) of modulus β A . b) The operator T A defined in (2.11) is a contraction on (F(S), || • || ∞ ), of modulus β A . c) For any stationary strategy f ∈ W A , operator T f A is monotone. Operator T A is monotone as well.

Inria Algorithm 1 1 :

 11 Value function iteration for infinite horizon; general case Require: ε > 0 Initialize with n = 0, v 0 A (s) = v 0 B (s) = 0 for every s ∈ S

fA.

  And by definition (2.1), for all g

Figure 1 :

 1 Figure 1: Value Iteration applied to Example 1

Figure 2 :

 2 Figure 2: Transition structure of Example 2

Inria

Figure 3 :

 3 Figure 3: Value Iteration applied to Example 2: state s 1 (left) and s 2 (right)

  Results for (MP) and (PI) with different values of α and β A with β B = 0

Figure 4 :

 4 Figure 4: Value Iteration applied to Example 3: state s 1 (left) and s 2 (right)

Figure 5 :

 5 Figure 5: Solution time performance profile.

Figure 6 :

 6 Figure 6: Solution time performance profile for each instance type.

1 :

 1 Initialize with n = 0, v 0 A (s) = 0 for every s ∈ S 2: for b ∈ B do

8 :

 8 Set the policy g * , in which the follower plays b * = arg max v * (b) 9: return SSE (f * (b * ), g * ) for the static game Given that Algorithm 5 solves |B| LPs with |A| variables and |B| constraints, it finds a SSSE in polynomial time.

Figure 7 :

 7 Figure 7: Zones Z ij for the SSSE and their boundaries in Example 1

1 B 2 B 1 B

 121 f,γ B (f ) A (s 1 ) and V f,γ B (f ) A (s 2 ) isInria located at the point where all four zones meet. The zone that realizes the maximum is Z 21 . The coordinates of this point are obtained e.g. by solving for (f1 , f 2 ) in the equations V f,b 1 b (s 1 ) = V f,b 1 b (s 1 ) = V f,b 2 b(s 1 ). The solution provides the value of f * 2 as the root of polynomial p(f 2 ) = 3465 f 3 2 -22604 f 2 2 + 26345 f 2 -8516 that belongs to [0, 1], and f *

Figure 8 :

 8 Figure 8: Value V f,γ B (f ) A (s) in Example 1, for s = s 1 (left) and s = s 2 (right)

17

 17

Figure 9 :

 9 Figure 9: Value g A (s, f ) in Example 1, for s = s 1 (left) and s = s 2 (right)

Figure 10 :

 10 Figure 10: Zones of W A for the response sets of Player B, R B (f, s 2 ) (left) and R B (f ) (right); red lines are points that belong to several zones

Figure 11 :

 11 Figure 11: Zones of the mapping T : left, with β A > 1/3; right, with β A < 1/3

Table 16 : 3 Inria

 163 Transition matrix and payoffs for each player in ExampleWe claim that the following pair of strategies (f * , g * ) and value functions (v * A , v * B ) constitute both a SSSE and a FPE:f * (s 1 , a 1 ) = 1 f * (s 2 , a 1 )

  15). This point lies at the boundary of B's best responses g = (b 2 , b 1 ) and (b 2 , b 2 ) (line L6), where f 1 = 1. Player B breaks the tie in favor of Player A by playing b 2 .

Figure 12 :C. 3 . 3

 1233 Figure 12: Best response zones for Example 3

Figure 13 :Figure 14 :

 1314 Figure 13: Player B's responses as a function of f 1 = f (s, a 1 ) in Example 3; state s 1 (left) and state s 2 (right)

  represents the set of deterministic bestresponse strategies of Player B. As argued above, this set is nonempty. The set SR B (f ) is that of strong best-responses, which break ties in favor of Player A. It is possible to break ties simultaneously in all states s, because optimal policies of the MDP form a cartesian product. We denote by γ B (f ) the deterministic policy that is the actual best response of Player B to Player A's f . Finally, R With these notations, we can now define Strong Stackelberg Equilibria of the dynamic game, called here Stationary SSE, as the SSE for the static game where players use stationary strategies in W A × W B . It corresponds to the definitions in

A (s) is the set of Player A's best strategies when starting from state s.

Equilibria.

  1 )(s) for all s ∈ S 7: return Approximate Stationary Strong Stackelberg policies (f * , g * )

	Algorithm 2 Value function iteration for infinite horizon; simplified case
	Require: ε > 0
	1: Initialize with n = 0, v 0 A (s) = 0 for every s ∈ S
	2: repeat
	3:

  .4) Consider the static game (i.e. one-state game with null discount factors) with S = {s k } and rewards defined with this formula. Again, Theorem 4 applies to this game: an FPE exist, resulting in a pair of strategies (f * s k , g * s k ) ∈ P(A s k ) × P(B s k ). When k = K, we have defined this way a strategy (f *

s , g * s ) for each s ∈ S.

Table 2 :

 2 Policies and values of the SSSE in Example 1

			applied to Example 1
		s 1	s 2
	Play of A (0.3467, 0.6533) (0.6434, 0.3566)
	Play of B	b 1	b 2
	v A	26.841	28.437
	v B	-1.807	-0.679

Table 4 :

 4 Existence of FPE and SSSE for different values of β A and β

B > 0. Even when both exist they may not coincide.

Policy iteration and (MP).

Finally, we test the Mathematical Programming (MP) formulation and Policy Iteration (PI) algorithm, for the different values of the parameter α in (MP) and for values of β A in {0,

1

8 , 1 4 , 1 2 }. Table

Table 9 :

 9 To determine Size of the instances (number of states and average number of actions for Player A and B) when changing the graph structure, number of nodes n and displacement limit k

	Inria

Table 10 :

 10 Evaluation of the solution concept with β B = 0.

	type	v * A	vM A	v * B	vM B
	Cycle	9.957	8.376	1.485	2.079
	Path	9.070	6.686	1.109	1.703
	T	10.623 8.129	0.703	2.218
	Complete 89.595 89.595 129774.653 129774.653

shows

  Inriathe average values obtained applying the policies provided by the FPE and the myopic heuristic.

	type	v * A	vM A	v * B	vM B
	Cycle	-17.667 6.767	6.261	2.171
	Path	-14.102 4.938	6.617	1.506
	T	-12.955 6.143	6.739	2.249
	Complete	89.595 89.604 129773.771 129773.762

Table 11 :

 11 Evaluation of the solution concept with β B = 0.9.

  is relative to the application of Section 5. Immediate reward for Player i when actions a and b are performed in state s.Q ab (z|s) Probability of reaching state z from state s when actions a and b are performed.

	Stochastic Games
	G	Stochastic game.
	S	Set of states.
	As, Bs	Set of actions for the Leader and the Follower respectively available in state s.
	r ab i (s)
	βi	Discount factor for Player i.
	Wi	Set of feedback policies for Player i.
	f, g

Table 13 :

 13 Table of notation for the surveillance application

B Algorithmic Proof for the Static Case.

  1 (B plays b 1 ), 0 (B plays b 2 ) and indifferent. In other words:if f 2 < 1/3, the strategy (f 1 , f 2 ) belongs to Z 11 ∩ Z 21 , if 1 > f 2 > 1/3, it belongs to Z 12 ∩ Z 22 , and if f 2 = 1/3 or f 2 = 1, if belongs to Z 11 ∩ Z 21 ∩ Z 12 ∩ Z 22. Player B's value is the same whatever she plays in these last cases. The case f 1 > 0 and f 2 > 0. When f 2 > 0, 1 -(1 -f 2 )g 2 = 0. As we concluded in the preliminaries, g 1 = 0 in this case (Player B plays b 2 in state s 1 ). Points (f 1 , f 2 ) with f 2 > 0 belong to either Z 21 or Z 22 , or both. Setting g 1 = 0 in (C.5), we have:

  Player B is indifferent with immediate rewards (she gains 1 whatever she plays) and she has to arbitrate between staying forever in state s 2 , and receive an additional β B /(1 -β B ) by playing b 1 , or jumping to state s 1 and gain β B v B (s 1 ) by playing b 2 . Player A prefers this second situation because of the immediate reward, not because of future gains. Her interest is therefore to use the tie-breaking rule of Player B to induce her to play b 2 and not b 1 in state s 2 .

RR n°9271

Inria

Publisher Inria Domaine de Voluceau -Rocquencourt BP 105 -78153 Le Chesnay Cedex inria.fr ISSN 0249-6399

Acknowledgments.

Victor Bucarey has been partially supported by the Fonds de la Recherche Scientifique -FNRS under Grant(s) no PDR T0098.18.

C Analysis of the examples

In this section, we provide details and justifications for the examples reported in Section 4. In doing so, we introduce some elements useful in the analysis of the operators involved in Value Iteration algorithms.

C.1 Analysis of Example 1

In this section, we provide details on the analysis of Example 1 introduced in Section 4.2. We compute the Stationary Strong Stackelberg Equilibria (SSSE) and demonstrate their existence. We compute the one-step operator and show it has also a fixed point (FPE) which coincides with this SSSE.

C.1.1 Data

The data of this example is given in Table 14 (also Table 1). We will also specifically consider

(1, 0) (6, -4)

State s2

) and g i = g(s i , b 1 ). We have first, observing that transition probabilities do not depend on the state,

Also,

.

From these elements, one derives the values for Player B in each state, when she plays the four possible strategies: with V f,xy B (s) the value at state s when x is played in state s 1 and y played in state s 2 :

C.2.2.2 Analysis of values.

The objective is to compute, for every state, the best strategy f ∈ W A for Player A: the set R A (s). A SSSE will exist if and only if the intersection of these sets is nonempty. We start with the absorbing state s 1 and proceed with s 2 .

In addition to the existing notation, introduce:

for the set of Player B's best reactions to some fixed strategy f ∈ W A , when in state s. The computation will have the following steps. First, we compute the sets R B (s, f ), s ∈ {s 1 , s 2 } for individual states. We deduce R B (f ) by intersecting them. Next, we look for Player A's optimum: the maximum of V f g A (s) where g is Player B's (global) response to strategy f . For state s 1 , which is absorbing, this turns out to be straightforward. For state s 2 , we focus the analysis on the sets

is, the subsets of W A where playing (b i , b j ) is optimal for Player B in state s 2 . We first identify these sets. In a second step, the maximum of Player A's gain is computed on each Z ij . Finally, the maximum of these maxima is identified.

Observe that the sets Z ij are not disjoint in general: when they intersect, Player B is indifferent between at least two (pure) strategies. She will then select a strategy that maximizes Player A's gain: the set SR B (f ). However, the analysis does not need to identify precisely this best reaction of Player B.

C.2.2.2.1 Player B's response for state s 1 .

We first look at the maximum of V f g B (s 1 ) = v B (s 1 ) with respect to (g 1 , g 2 ). Because state s 1 is absorbing, the expression of v i (s 1 ), i = A,B, depends only on f 1 and g

.

As it turns out, 3f 1 g 1 -f 1 + 1 ≥ 0 and it can be = 0 only when f 1 = 1 and g 1 = 0. If Player A plays any f 1 = 0, the only way Player B can maximize her value is to play g 2 = 1 which is contrary to Player A's preference. On the other hand, if Player A plays f 1 = 1, Player B has can choose either g 1 = 0, or g 2 = 1 (or both). This tie is broken in favor of A, whose value is, when

Therefore B picks g 2 = 0 (g 1 being indifferent), thereby fulfilling Player A's objective. Playing f 1 = 1 (action a 2 ) in state s 1 is however not optimal for Player A since action a 2 strictly dominates it. This explains the lack of SSSE. This argument does not work when β B = 0. In that case, Player B is indifferent and spontaneously breaks the tie in favor of Player A by playing b 2 in state s 2 , Observe here in passing that the "myopic" case does not always bring a simplification to the problem. Despite the fact that the myopic follower condition guarantees the existence of FPE and SSSE, the myopic leader condition does not guarantee the existence of SSSE.

C.2.3 The one-step Value Iteration operator

C.2.3.1 Computation of the operator.

We compute here the operator T , which maps pairs of value functions to pairs of value functions. We restrict our attention to those pairs where the value at state s 1 is the fixed-point obtained in (C.8). There are therefore two remaining variables: v A (s 2 ) and v B (s 2 ). In order to clarify formulas a bit, we use the symbols w := v A (s 2 ) and z := v B (s 2 ). The images (T v) A (s 2 ) and (T v) B (s 2 ) will be denoted with w and z respectively.

By using the values in (C.8), we arrive at a single-state game parametrized by the values of w and z:

C.2.3.1.1 Operators T f g i

First of all, we write down the expressions for (T f g i v)(s 2 ), i = 1, 2 for arbitrary strategies f ∈ W A , g ∈ W B . Those are deduced from the computation in Section C.2.2.1, by adapting the right-hand side of equations, and using values in (C.8). Then,

From (C.11) we see that Player B's optimal reaction to a given f 2 depends on the sign of z, unless f 2 = 1 or β B = 0. We assume β B > 0 in the remainder of this section. The case β B = 0 will be studied in Section C.2.3.3.

If

C.2.3.1.3 Optimization of Player A.

Player A's reward when Player B plays b 1 (g 2 = 1) is:

This is the situation when z > 0. The maximum of this expression with respect to f 2 depends on the location of w with respect to (3β

This is the situation when z < 0. The maximum of this expression with respect to f 2 is when f 2 = 0. When z = 0, these two values must be compared. Which one is the largest depends on the location of w with respect to (1

After optimization with respect to f 2 , we have the following cases:

Case z < 0: here, Player B always plays b 2 and A plays a 2 . We have the fixed mapping:

Case z > 0: here, Player B always plays b 1 .

Case w < (3β

The mapping is also fixed:

The mapping is linear:

Case w = (3β A -1)/β A /(1 -β A ): A plays anything she wants. Let φ be this strategy, the mapping is:

Case z = 0: Player B is indifferent with her own reward. The tie is broken in favor of Player A.

). The mapping is to P 22 .

). The mapping is T 21 (w, z).

In a more compact form, the sub-operator for this game in state s 2 is as follows:

In summary, the plane (w, z) is partitioned in three zones, as illustrated in Figure 11. The three zones are represented: Z 11 in green: points of this zone map to P 11 ; Z 22 in blue: points of this zone map to P 22 ; Z 21 in yellow: points of this zone are mapped by operator T 21 . This mapping T 21 admits as fixed point:

In all cases, P 22 is in the zone Z 21 and point P 11 is in the zone Z 22 . Other notable points are: Point C, the triple point and Point L = ((1 + β A )/β A /(1β A ), 0) which delimits the two cases when z = 0: the horizontal segment (-∞, L] belongs to zone Z 22 and the segment (L, ∞) belongs to zone Z 21 .

Point S is the candidate SSSE with coordinates (2β A /(1 -β A ), 0). Points C and S are always located to the left of Point L, which means that they both belong to Z 22 .

The solid red line, that is, the half-line {w = (3β A -1)/β A /(1 -β A ); z > 0}, is the frontier between Z 21 and Z 22 . It has a special status: by picking any number φ in (C.12), an infinite number of mappings T φ,0 can be chosen. Its image is represented as the dashed red line.

C.2.3.2 Dynamics of the operator.

Two main situations occur: either β A > 1/3, either β A ≤ 1/3. Those are represented in Figure 11, on the left and the right, respectively.

C.2.3.2.1 Case β

A > 1/3. In this situation, the fixed-point of operator T 21 is located in zone Z 11 . The iterations of T starting in Z 22 (with z < 0 or in the segment (-∞, L])) will be mapped first to P 22 , then to T 21 P 22 , then T 2 21 P 22 etc. Eventually, the sequence T k 21 P 22 will enter zone Z 11 . Then the value will be mapped to P 11 and repeat the cycle. This is in particular the case of the SSSE which belongs to Z 22 , see Section C.2.4.

Iterations of T starting in zone Z 11 will map to P 11 and continue as above.

Inria