Zero-Sum Stochastic Stackelberg Games
Authors: Denizalp Goktas
Sadie Zhao
Amy Greenwald
Venue: NeurIPS 2022 Accept (2022)
Keywords: Stackelberg games
Equilibrium Computation
Market equilibrium

Abstract: Zero-sum stochastic games have found important applications in a variety of fields, from machine learning to economics. Work on this model has primarily focused on the computation of Nash equilibrium due to its effectiveness in solving adversarial board and video games. Unfortunately, a Nash equilibrium is not guaranteed to exist in zero-sum stochastic games when the payoffs at each state are not convex-concave in the players' actions. A Stackelberg equilibrium, however, is guaranteed to exist. Consequently, in this paper, we study zero-sum stochastic Stackelberg games. Going beyond known existence results for (non-stationary) Stackelberg equilibria, we prove the existence of recursive (i.e., Markov perfect) Stackelberg equilibria (recSE) in these games, provide necessary and sufficient conditions for a policy profile to be a recSE, and show that recSE can be computed in (weakly) polynomial time via value iteration. Finally, we show that zero-sum stochastic Stackelberg games can model the problem of pricing and allocating goods across agents and time. More specifically, we propose a zero-sum stochastic Stackelberg game whose recSE correspond to the recursive competitive equilibria of a large class of stochastic Fisher markets. We close with a series of experiments that showcase how our methodology can be used to solve the consumption-savings problem in stochastic Fisher markets.

Zero-Sum Stochastic Stackelberg Games
Denizalp Goktas
Jiayi Zhao
Department of Computer Science Brown University Providence, RI 02906, USA Gemizalp_goktasebronn edu
Department Computer Science
Pomona College Pomona, CA, USA
jzae201 90mymail www.na. edu
Amy Greenwald Brown University Providence, RI 02906, USA amy sey-ggreenwllddbbromm edu
Abstract
Zero-sum stochastic games have found important applications a variety fields, from machine learning to economics. Work this model has primarily focused on the computation of Nash equilibrium due its effectiveness in solving adversarial board and video games. Unfortunately, Nash equilibrium is not guaranteed exist in zero-sum stochastic games when the payoffs at each state are not convex- concave in the players' actions. A Stackelberg equilibrium, however, is guaranteed to exist. Consequently, in this paper, we study zero-sum stochastic Stackelberg games. Going beyond known existence results for (non-stationary) Stackelberg equilibria, we prove the existence of recursive (i.e., Markov perfect) Stackelberg equilibria (reeSE) in these games, provide necessary and sufficient conditions for a policy profile to be recSE, and show that recSE can be computed in (weakly) polynomial time via value iteration. Finally, we show that zero-sum stochastic Stackelberg games can model the problem of pricing and allocating goods across agents and time. More specifically, we propose a zero-sum stochastic Stackelberg game whose recSE correspond to the recursive competitive equilibria of large class of stochastic Fisher markets. We close with series of experiments that showcase how our methodology can be used to solve the consumption-savings problem in stochastic Fisher markets.
Min-max optimization has paved the way for recent progress in a variety of fields, from machine learning economics. These applications require computing solutions constrained min-max optimization problem i.e., min max,ey) (xx y). where the objective function f : x y - TR. continuous, and the constraint sets X 1 and y C R. are nonempty and compact. When f is convex-concave, and the constraint sets X' and y are convex, the seminal minimax theorem [ 2 holds, i.e., min maXyey [xx y) maxyey mines f(, y). and such problems can be interpreted as computing a Nash equilibrium of simultaneous-move min-max (or zero-sum) game between an outer player z and an inner player y with respective payoff functions -f. f and respective action sets X. y. where the solutions (x" y²) E X' ) are best responses to one another.
infinite discrete time horizon N.. The game starts at some initial state ( ~ ()) At each subsequent time-step t N players encounter new state (()) S. After taking their respective actions (xx(") ((() from their respective action spaces (( C R and (()()) C IR" they receive payoff's ((s(() x0()) ( and then either transition new state g(++1) p(- (t)) ((),, (!))) with probability 7, or the game ends with the remaining probability. The goal of the outer (resp. inner) player is to play a sequence
More generally, one consider zero-sum stochastic games, played
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

of actions fx (resp. (t). that maximizes (resp. minimizes) their expected cumulative
discounted payoff (resp. loss) E |Et=o ("r((()) x(9) y( fixing their opponent's 's policy.
(stationary) policy is a mapping from states to actions. When r(s, æ, y) is bounded, continuous, and concave-convex in (a, y). for all 8 E S, we are guaranteed the existence of a stationary policy profile, i.e., a pair of policies Tx -S- - X' Ty S + ) for the outer and inner players, respectively, specifying the actions taken at each state, with unique value such that both players maximize their expected payoffs, as a generalization of the minimax theorem holds B
min Wa C. Ty EyB
B
>'r(s(t)) A (S )TT (S(0))
min I
Σ (r(ss (T(())) T (S(00)) m-0
Ty ey 2a EXS
In other words, under the aforementioned assumptions, we are guaranteed the existence of a recursive Nash equilibrium (sometimes called a Markov perfect Nash equilibrium A a stationary policy profile in which players not only best respond one another, but they do so at every state of the game. Additionally, when the rewards at each state are convex-concave, a recursive Nash equilibrium can be computed in polynomial time by iterative application of the min-max operator ( Zero-sum stochastic games generalize zero-sum games from single state to multiple states, and have found even more applications in a variety of fields
Unfortunately, when the objective function in min-max optimization problem is not convex- concave, a minimax theorem not guaranteed hold, precluding the interpretation of the game as simultancous-move and the guaranteed existence of Nash equilibrium. Nonetheless, the game can still be viewed as a Stackelberg game, in which the outer player moves before the inner one. The canonical solution concept in such games is Stackelberg equilibrium (SE). Moreover, in Stackelberg games, the inner player's 's actions can be constrained by the outer player's choice, without impacting existence (6). The result is min-max Stackelberg game: i.e., min maxye...(a..u (2) I (æ. y) where f, h x x y - IP are continuous, and X, y are non-empty and compact. Even more problems of interest can be captured by this model
One can likewise consider zero-sum stochastic Stackelberg games, which generalize both zero-sum Stackelberg games and zero-sum stochastic games. Similar to zero-sum stochastic games, these games are played over an infinite discrete time horizon N,,, start at some state (()) ~ مr()) and consist of nonempty and compact actions spaces X RR" and y R state-dependent payoff' function r(8, x, y). a transition probability p(s' 8, x., y). and discount rate 7, but are in addition augmented with state-dependent (joint action) constraint function ((s, ær, y). with two players that seek to optimize their cumulative discounted payoffs,, in expectation, while satisfying the constraint g(s, x y) > at each state s S. Applications of this model include autonomous driving (8] [0]. reach-avoid problems in human-robot interaction (9). and robust optimization in stochastic environments and, as we show, economic markets.
While in stochastic games, players announce their policies simultaneously before play commences, in stochastic Stackelberg games, the outer player, announces their (in general, non-stationary) policy: i.e., the action they will take at each time step, first, after which the inner player announces theirs. The canonical solution concept for such games is the Stackelberg equilibrium, which is guaranteed to exist (in non-stationary policies) under mild assumptions TT 6].
The computational complexity of non-stationary cquilibrium policies in stochastic games can be prohibitive, since even representing such policies in an infinite horizon setting is intractable. A natural question to ask then is whether stationary equilibria exist in zero-sum Stackelberg games, i.e. stationary policy profiles at which the outer player maximizes their expected discounted cumulative payoff while the inner player best responds. We call such policies recursive Stackelberg equilibria (recSE) (or Markov perfect Stackelberg equilibria).
In this paper, we define and prove the existence of recSE in zero-sum stochastic Stackelberg games, provide necessary and sufficient conditions for a policy profile to be a recSE, and show that a recSE can be computed in (weakly) polynomial time via value iteration. We further show that zero-sum stochastic Stackelberg games can be used to solve problems of pricing and allocating goods across
"hhalee'ss original results, which concem dete-deppnd payoff functions that bilinear in the outer and inner players' actions, extend directly to payoffs which are convex- concave the players' actions. 'To simplify notation, we drop the dependency of action spaces on states going forward, but our theory applies in this more general setting.

---

agents and time. In particular, we introduce stochastic Fisher markets, a stochastic gemeralization of the Fisher market [[2), and a special case of Friesen's [33] financial market model, which itself is stochastic generalization of the Arrow and Debreu model of a competitive economy (14). We
then prove the existence of recursive competitive equilibrium (recCE) [15] in this model, under the assumption that consumers have continuous and homogeneous utility functions, by characterizing the recCE of any stochastic Fisher market as the recSE of a corresponding zero-sum stochastic Stackelberg game. Finally, we use value iteration to solve various stochastic Fisher markets, highlighting the issues that value iteration can encounter, depending on the smoothness properties of the utilities.
Algorithms for min optimization problems (i.c.. sum games) with inde- pendent strategy sets have been extensively studied [[6 17 18
Related Work
28 38 39 (for summary see, Section G Goktas and Greenwald
19 20
29,
30
31
32
33
34
35
36
37
studied min-max games with dependent strategy sets, proposing polynomial-tiin time nested gradient descent ascent (GDA)
6 and simultaneous GDA algorithms for such problems [40].
The computation of Stackelberg equilibrium in two-player stochastic Stackelberg games has been studied in several interesting settings, in which the leader moves before the follower, but without the leader's s actions impacting the followers' choice sets. Bensoussan, Chen, and Sethi [4]] study continuous- time general-sumy stochastic Stackelberg games with continuous action spaces, and prove existence of solution in this setting. Vorobeychik and Singh [T] consider a general-sun Stackelberg game with finite state-action spaces and an infinite horizon. These authors show that stationary SE policies do not exist in this very general setting. but nonetheless identify a subclass of games, namely team (or potential) Stackelberg games for which stationary Stackelberg equilibrium policies do exist. Vu al. 42 study the empirical convergence of policy gradient methods in the same setting as Vorobeychik and Singh (TT), while Ramponi and Restelli [43] study non-stationary
stochastic
equilibria in this same setting, assuming a finite horizon. Chang, Erera, and White 4 and Sengupta
and Kambhampati [45] consider partially observable version of Vorobeychik and Singh's
model, and provide methods to compute Stackelberg equilibria in their setting.
Some recent research concerns one leader-many followers Stackelberg games. Vasal 46 studies a discrete-ting time, finite horizon one leader-many follower stochastic Stackelberg game with discrete action and state spaces, and provides algorithms to solve such games. DeMiguel and Xu (77 consider a stochastic Stackelberg game-like market model with n leaders and m followers; they prove the existence of a SE in their model, and provide (without theoretical guarantees) algorithms that converge to such an equilibrium in experiments. Dynamic Stackelberg games (48) have been applied to a wide
range of problems, including security (4 [T]. insurance provision [49 50 advertising [1 robust
agent design [2]. allocating goods across time intertemporal pricing [53
The study of algorithms that compute competitive equilibria in Fisher markets was initiated by Devanur al., who provided a polynomial-time method for solving these markets assuming linear utilities. More recently, there have been efforts to study markets in dynamic settings (55] 56 6]. in which the goal is either track the changing equilibrium of a changing market, or minimize some regret-like quantity for the market. The models considered in these earlier works differ from ours as they do not have stochastic structure and do not invoke dynamic solution concept.
1 Preliminaries
Notation We use caligraphic uppercase letters to denote sets (e.g., A)); bold lowercase letters to denote vectors (e.g., P; π); bold uppercase letters to denote matrices and vector-valued random which one should be clear from context; lowercase letters to denote scalar quantities (e.g., 2r, 7); and uppercase letters denote scalar-valued random variables (e.g., X, I)). We denote the ith row vector of a matrix (e.g.. X) by the corresponding bold lowercase letter with subscript i (e.g.. az)). Similarly, we denote the jthh entry of vector (e.g., p or æ:)) by the corresponding Roman lowercase letter with subscript j (e.g., pj or Izz)). We denote functions by a letter: e.g., f if the function is scalar valued, and f the function vector valued. We denote the vector of ones of size n by 1n- We denote the set of integers {l...., n by [n]. the set of natural numbers by N. the set of real numbers by TR. We denote the postive and strictly positive elements of set by a + and ++ subscript respectively, e.g., R4, and R++- We denote the orthogonal projection operator onto a set C by II, i.e., (x) = arg millyec || x - v We denote by A,, (a E RD by A (A), the set of probability measures the set A.
variables (e.g., X, -hhic
E I, = =1}, and
3

---

A stochastic Stackelberg game (S, p1 T.. P.7.) 7) is a two-player game played over an infinite discrete time horizon N4. At each time-step E N,. the players, who we call the outer- (resp. inner-) players, encounter a new state E S, and choose an action to play from their continuous set of actions X' C IR" (resp. } C I.. Play initiates at a start state S drawn from a distribution 20 : S + [o. 1]. At each state & E S the action 2 E X chosen by the outer player determines the set of feasible actions {y y/ g x. y) 2 0} available to the inner player, where g: S x X' x y + R.. After the outer and inner players both make their moves, they receive payoffs T : xXX'x + IR and ry S x X' x - R, respectively, and the game either ends with probability
1 7 where ? E (0, 1) is called the discount factor, or transitions
new state s' E S, according
to transition probability function p: S x S X X x y - [0, 1] s.t. p(s' 8, I. y) E [0, 1] denotes the probability of transitioning to state s' E S from state E S when action profile (x. y) X x y is chosen by the players.
In this paper, we focus on zero-sum stochastic Stackelberg games ( = (S.
r. r.g.P. 7)
in which the outer player's 's loss is the inner player's 's gain, i... Tx = -y. A zero-sum stochastic Stackelherg game reduces to zero-sum (simultaneous-mong
stochastic game 3 in the special case where g(s, a: y) 2 0, for all state-action tuples (s, æ. y) S x X' x y More generally, a policy
profile (Ta: πy) E E y is said to be feasible if g(s, (s), Ty (s)) 2 0, for all states s E S.
To simplify notation, we introduce a function G X x y - RlS)xd xd such that G(T Ty) = (g(s, a (8))) and define feasible policy profiles as those (Tz Tyy) E X x y s.t. G(T Tyy 2 O. From now on, we assume:
Assumption 1.1. 1. For all states s E S, the functions "), X' x V, and payoffs are bounded, i.e., || I Tmax < oc, for some mmax E R+, 2. X. y are
are continuous in (x. y)
non-empty and compact, and for all s E S and x E X' there exists E s.t. v) 2 0
Given zero-sum stochastic Stackelberg game g(0), the state-value function, v : SX S x y + R. and the action-value function, q: : S x X V x X5 x2S - R. respectively, defined as:
v(s; Tw: nty
Ty g(t-1) x (t
7 T' ((1))y(it) (005 =
(I)
(8, α. y Tw: Tw; Rty)
g(t (((-1)) x(1)) rr((S()) | x0)) = ( y x1)
Te
(2)
Again, simplify notation, we write expectations conditional on (() T (S(0) and y( (S(() as ET,.,"y, and denote the state- and action-value functions by (s). and ( x. y), respectively. Additionally, we let V 1- 1 be the space of all state-value functions of the form U : S + [- rtax////) and we let Q [I-max/1-n, rmae/1-1j5xxxx be the space of all action-value functions of the form g S x xxX y + [-rmx//1-y, /max/1-2]. Note that by Assumption I.] the range of the state- and action-value functions [-rmar/1- 1mmx//// The cumulative payoff function of the game 8 x ys + R is the total expected loss (resp. gain) of the outer (resp. inner) player, given by u ( πy) E (e) (s)).
The canonical solution concept for stochastic Stackelberg games is the Stackelberg equilibrium (SE). A feasible policy protile (TT TT)) E XS x yJ is said to be a Stackelberg equilibrium (SE) of a zero-sum stochastic Stackelberg game (()) iff
max Ty SS G 1210
u (TT nyy) S u (T TT))=
S min
max T=EX Ey m,)0
1 (Ta, Tyy
Note the strength of this definition, as it requires the constraints g(s, πæ. F.) > 0 be satisfied at all states s E S, not only states which are reached with strictly positive probability. A SE is
NNte that this condition is weaker than Slater's condition; it simply ensures the feasible action sets are non-empty for the inner player at each state.

---

guaranteed to exist in sur stochastic Stackelberg games, under Assumption I.I as corollary of Goktas and Greenwald's (6) Proposition B.2.; however, this existence result is non-constructive
In this paper, we study a Markov perfect refinement of SE, which we call recursive Stackelberg equilibrium (recSH).
Definition 1.2 (Recursive Stackelberg Equilibrium (recSE)). A policy profile (T Ti) E 8* SD is recursive Stackelberg equilibrium (recSE) for all S, it holds that:
max (E):g(a:m(()))))
M (3 (x), v) 9 (2))) n. (v)) S
min max =ex vE>'g(+...0200
2 v).
Equivalently, a policy profile (T mHy) is rec if (T (s), n each state & E S: i..., ())) = min maXyeV qT T (s. x. y). for all s E S.
is SE with value ( (s)
Mathematical Preliminaries A probability measure @i E (S) convex stochastically dominates (CSD) 92 (SS) if Jss (s)) 2 Js (s))2((s) for all continuous, bounded, and convex functions on S. A transition function p is termed CSD convex in x if, for all X E (0, 1), E ) and any (s', æ²), (st, æ²) E x X, with (s.x) A(s', x²) + (1 -)(stt æT), ), it holds that + (1 - A)p(- 8" xl, y) CSD p(- 8, s. A transition function p is termed x',y) y)
Ap(: | s',
CSD concave in y if, for all À E 10,1) and any (s', y') yd) E SESx x X x V. with (s. y) = X(s', )') + (1 (1- (s ), holds that p(- s, y) CSD Ap(- s,, y') + (1 A)p( 8 x. yt). A mapping L : + B is said to be a contraction mapping (resp. non-expansion) w.r.t. norm |I||| iff for all x, y E A. and for k E [0, 1) (resp. = 1) such that [(xx) - L(y))l S A || - yll. The min-max operator millge maxyEy RX + R w.t.t to sets X, takes as input a function and outputs mingex maxyey f(x. y). The generalized min-max operator
f: x x y + min max yaX (2))))))))))))) 2)20 Xxx' + R w.r.t. to sets X.Y and the function g g:4 X x y - R takes f(x y).
as input a function f X y + IR and outputs min
2 Properties of Recursive Stackelberg equilibrium
In this section, we show that reeSE exists in all zero-sum stochastic Stackelberg games Fl To do so, we first associate an operator C : V - V with any zero-sum stochastic Stackelberg game (()), the fixed points of which satisfy Definition 1.2 and hence correspond to the value function associated with a recSE of gro), We then show that this operator is a contraction mapping, thereby establishing the existence of such fixed point. This result generalizes Shap- ley's theorem on the existence of Markov perfect Nash equilibria in zero-sum stochastic games [3] Define C V + V for any zero-sum stochastic Stackelberg game (()) as the operator (Cv) (8) mingex maxyeY-gla (a,,))))) Eptlep( [r(s, x, y) + (S")) We first show that the fixed points of C' correspond to the recSE of the associated game.
Theorem 2.1. (TT Tiy) is a recSE of (() Tu iff it induces a value function which is fixed point of C: i... (T (T))TT)) is Stackelberg equilbrium iff. for all s E S, (Comims) (s) (s)..
The following technical lemma is crucial to proving that C is a contraction mapping. It tells us that the generalized min-max operator is non-expansive; other words, the generalized min-max operator is I-Lipschitz w.r.t. the sup-norm.
Lemma 2.2. Suppose that f, h X y - RR, x y - IRd are continuous functions, and X, are compact sets. Then mingex maxyc)'g(*.w)2> f y) minnex max) h( y)
< ()) (f y) h(x y)l.
With the above lemma in hand, we can now prove that C' is a contraction mapping.
Theorem 2.3. Consider the operator C associated with stochastic Stackelberg game ((o), Under
Assumption 1.1 C is a contraction mapping w.r.t to the sup norm II-IIac with constant 7,
Wwe note SE should technically be defined in terms non- stationay policies; however, as we will show, stationary policies suffice, since SE exist stationary policies.
5 All omitted results and proof's can be found in the appendix.
5

---

We will show that C' is a contraction mapping, which then by Banach fixed point theorem establish the result. Let v, v' E V be any two state value functions and q. E Q be the respective associated action-value functions. We then have by Lemma 2.2
Proof of Theorem 2.3
||Cu- - Cv' S
max min #ES #EX (a.
max (8, y) min max
q ( x. v)
(3)
= w))
max max #ES (m.j)x xy (q x. y) (s, x; y)
Replacing the definition of the state-action value function in the above, we get that C' is a contraction mapping since y E (0,1): 1):
S max max #ES (x.))EX (am [r(8, 2. y) + yo
[r(8, x. y) + yo (S')
(5)
s'~p(11...1))
S y max max
E
(u(S") - rs())
(6)
#E8 (a.)) xy
(S'mp(- s.2.y)
S y max max #ES xx)
|0(s) - -'s)) = ||u 01
(7)
Given an initial vtate-value function v0()) E V, we define the value iteration process (+++)) Cylt,, for all t E N+ (Algorithm D. One way to interpret e(()) is as the function that returns the value (s) of each state E S in the (-stage zero-sum stochastic Stackelberg game starting at the last stage l and continuing until stage 0, with terminal payoffs given by v(0), The following theorem, which is a consequence of Theorems 2. and 2.3 and the Banach fixed point theorem [57], not only proves the existence of recSE, but further provides us with a means of computing a recSE via value iteration.
Theorem 2.4. Consider zero-sum stochastic Stackelberg game g( Under Assumption 1.1 g())
has unique value function v u. associated with all recSE (TT TTy)) which can be computed by iteratively applying C to any initial state-value function (0)) E V: ie., lime-1oo v(() = u=
Remark 2.5. Unlike Shapley's 's existence theorem for recursive Nash equilibria in zero-sum stochastic
games, Theorem 2.4 does not require the payoff function to be needed are continuity of the payoffs and constraints, and bounded payoffs. This makes the recSE potentially useful solution concept, even for non-comve--non-cooeee stochastic games.
The only conditions
Since recSE is guaranteed exist, and is by definition independent of the initial state dis- tribution, we can infer that the recSE of any zero-sum stochastic Stackelberg game (()) (S,X, X,Y, X,),,()) .r, 9: 7) is independent of the initial state distribution (9) Hence, in the remainder of the paper, we denote zero-sum stochastic Stackelberg games by G = (S, X, r. 9.P..7 7).
V,,,r
Theorem 2.4 tells us that value iteration converges to the value function associated with a recSE. Additionally, under Assumption 1.1 recSE is computable in (weakly) polynomial time
Theorem 2.6 (Convergence of Value Iteration). Suppose value iteration is run on input G. Let (Th ) be recSE of with function u. Under Assumption 1.1 if we initialize ((0) 0. for all 8 E S, then for 2 - log a(1-9y, holds that (k)) 1
=* S.
3 Subdifferential Envelope Theorems and Optimality Conditions for Recursive Stackelberg Equilibrium
In this section, we derive optimality conditions for recursive Stackelberg equilibria. In particular, we provide necessary conditions for a policy profile to be recSE of any zero-sum stochastic Stackelberg game, and show that under additional convexity assumptions, these conditions are also sufficient.
'This convergence is only weakly polynomial time, because the computation of the generalized min max operator applied to an arbitrary continuous function is an NP-hard problem; it is at least as hard as non convex optimization. If, however, we restrict attention to convex-concave stochastic Stackelberg games, then Stackelberg equilibria are computable in polynomial time.

---

The
theorem characterizes the derivative of the optimal value function associated with a recursive optimization problem w.r.t. its parameters, when it is differentiable (58). Our proofs of the necessary and sufficient optimality conditions rely on a novel subdifferential generalization (Theorem C.2 Appendix C of this theorem, which applies even when the optimal value function is not differentiable. A consequence of our subdifferential version of the Benveniste- Scheinkman theorem is that we can easily derive the first-order necessary conditions for a policy profile to be recSE of any zero-sum stochastic Stackelberg game G satisfying Assumption under standard regularity conditions.
Theorem 3.1. Consider a zero-sum stochastic Stackelberg game 9. where X' for E R" (x) < 0, .......,........................ (p(x)))((() S 0} and y = {y E RT r1( 0, -O,...,1(y)) 2 0} are conver. Let fa (y. A) = r(s, x. v) + + -s--p((1e,x.00)) (o(5', x)) ]]] Σx= (s 2. y) where Cv =
Suppose that Assumption [.1 holds, and that 1. for all max {r(s in
E
S.
88 v. y) + BBypp(() Ver(s, x. y), (s. ...., vega(s, x. y), V Vyr(s, (s. x. y). V (9 (ss..,y)........ y)...... Vyga(s. x. y) exist, for all s E S. E N.y E Y,
con-
cave
I
8. 4. pls' 8. y) is continuous and differentiable in (ær, y), and S. Slater's condition holds,
X. Fy E y s.I. 9k (8, x. U) > 0. for all = -I..... d and rz(ū) > for all j j= 1,...,,, and Fx R s.L. (x) < 0 for all k = 1...,,. Then, there exists pt :S R..
Le., Vs E SS
: x X' + +R and v² SSX x X - R4, s.t. a policy profile ( Tÿy) X x y is a recSE of G only if it satisfies the following conditions, for all E S:
V VaLa (T)
T (s)) +
Vale =0
(8)
k=
(yCan)go)(T T (s)) +
v ग. (8) ( 0
(9)
( ((()))((TTT)))) (s)) =
1 (x) < 0
Wk E [p]
(10)
gu(s, (s), 20
Xss (s)))))
(T) =0
Wk [d]
(11)
(T)
=0
(T) 20 0
4k E
(12)
Under the conditions of Theorem if we additionally assume that for all 8 E S and x E X, both r(s, x, y) and 91 (s, x. y)..... gd S, x, y) are concave in y, and p(s' 8, x. y) is continuous, CSD concave in y, and differentiable in (x. y), Equations (59) to (63 become necessary and sufficient optimality conditions. For completeness, the reader can find the necessary and sufficient optimality conditions for convex-concave stochastic Stackelberg games under standard regularity conditions in Theorem (Appendix C. The proof follows exactly as that of Theorem 2.1
4 Recursive Market Equilibrium
We now introduce an application of zero-sum stochastic Stackelberg games, which generalizes a well known market model, the Fisher market (12), to dynamic setting in which buyers not only participate in markets across time, but their wealth persists. A (static) Fisher market consists of n buyers and m divisible goods [12] Each buyer i [n] is endowed with budget by E B, C R_ and utility function RT. X T + R. which is parameterized by a type t, E T that defines preference relation over the consumption space RT Each good is characterized by supply Øj E 2, C R,,
An instance of a Fisher market is then tuple M = (n, m,U, T. b, q), where U = [uI,..., Un } is a set of utility functions, one per buyer, b RR is the vector of buyer budgets, and g E IR the vector of supplies. When clear from context, we simply denote M by (T. b.q).
stochastic Fisher market with savings is a dynamic market in which each state corresponds to static Fisher market: i.c., each state s E S is characterized by a tuple s = (T, b, q). At each state, the market determines the prices p of the goods, while the buyers choose their allocations X = (a.,...., )² e Raxm and potentially set aside some savings 3, E [0, b.] to spend some future state. Once allocations, savings, and prices have been determined, the market terminates with
7

---

probability 1 - 7, or it transitions to new state s' with probability yp(s' 8, B), depending on the buyers' saving decisions We denote a stochastic Fisher market by F(O) = (nz, m, m,U,S, s s()), ,, 7).
Given a stochastic Fisher market with savings FF() a recursive competitive equilibrium (recCE)
[5] is a tuple 13" .p") E 1 x x 14 x R4 RT*s which consists of an allocation, savings, and price system s.t. 1) the buyers and spending constraints, i.., for all buyers i E [n], (x), (,,8;) is an optimal policy that, for all states = (T, b, q) S, solves the consumption-savings problem, defined by the following Bellman equations: for all 8 E S, (s())
expected utility maximizing, constrained by their savings
E us (z,, + ("".b'.'')~p((eeee (00,0,00.....00000000000 [T, b' + Br }
max (0) (E), "..pp (e)+0,5b
where X 3 denote the allocation and saving systems excluding buyer i; and 2) the market clears in each state so that unallocated goods in each state are priced O, i.e., for all j E [m] and Eie(n] [i S qj- By analogy with subgame perfect equilibrium, we can view recCH as a "submarket" perfect equilibrium, as recCE corresponds to competitive equilibrium of the market starting from any state, i.., buyers allocated expected discounted cumulative mulity-maximizine aggregate demand for any good is equal to its aggregate supply at all encountered markets.
E S. (. > = Eigln] (8)(8) qj and (s) 2 0 =
goods starting any state, and the
The following theorem states that any recSE of stochastic Fisher market with savings is in fact a recCE. Since recSE are guaranteed exist, recCE are also guaranteed to exist. As recSE, and hence recCE, are independent of the initial market state, we denote any stochastic Fisher market with savings by F (n, m, S.P.).
Theorem 4.1. stochastic Fisher market with savings F in which U is a set of continuous and homogeneous utility functions and the transition function is continuous in 3, has at least one recCE. Additionally, the recSE that solves the following Bellman equation corresponds to a recCE of F:
v(8) PER (X.8)ER
min
max Xp
Σ JE(m)
9jPg
Σ iE(m]
(b. B₂) log(u, (.)
E [T(TT + B,4'))
(13)
T b' a (')
Remark 4.2. This result cannot be obtained by modifying the Lagrangian formulation, i.e.. the simultaneuus-mov game form, of the Eisenberg-Gar Gale program, because the inner maximization problem is convex-non-concave while recursive Nash equilibria guaranteed to exist in zero-sum stochastic games only under the assumption of convex-concave payoffs (5).
5 Experiments
The zero-sum stochastic Stackelberg game associated with a stochastic Fisher market, can, in theory, be solved via value iteration (Algorithm IT] assuming that one can compute the solution to the min-max optimization in line 4 of Algorithm [ However, the min-max optimization problem which has be solved at each step of value iteration is convex-non-coneane
Specifically, the This
Eie(n] (b. - (&) log(u; (I,, t,) term renders the objective function convex-non-concart means that in general one is not guaranteed compute a globally optimal solution to the min-max max optimization problem in line 4 of Algorithm [ and instead can only converge to local min-max solution with known (first-order) methods, e.g. nested gradient descent ascent [ Unfortunately, if we are not able to compute globally optimal solution to the generalized min-max optimization, our guarantees for the convergence of value iteration do not apply. That said, gradient methods have been observed to escape local solutions many non-convex optimization problems (e.g., see (60) 6T])
leading to investigate how well we can solve the generalized min-max operator in Algorithm using nested gradient descent ascent 6 and in turn how effectively we can implement value iteration (Algorithm in practice.
"In our model, which is consistent with the literature (59) 1. prices do not determine the next state since market prices are set by a "fictional auctioneer," not an actual market participant; 2. allocations do not determine the next state. Only savings, which forward-looking decisions, affect future states budgets, specifically.

---

Algorithm 1 Value Iteration for Stochastic Fisher Market
Initialize (0) arbitrarily, e.g, v1())
2: for k = 1...., To do
3: For all s E S, ((+11 (T.b.q)
4: min
max p20 (X (x.))20:xp+85b
Σ je/m
pps
Σ (6. log(u((x)) + + [o(k) (T), b' B. ie/ni
To do so, we computed the recursive Stackelberg equilibria of three different classes of stochastic Fisher markets with savings Specifically, we created markets with three classes of utility functions, each of which endowed the state-value function with different smoothness properties. Let t; E RT be a vector of parameters, i.e., type, that describes the utility function of buyer i E [m]. We considered the following (standard) utility function classes: 1. linear: u,(,)) = Emmm 4yg
Cobb-Douglas: uy (x;) = [[]E(m] bt and 3. Leontief: u,,x), = minje[m]]
Bay
We ran two different experiments. First, we modeled small stochastic Fisher market with savings without interest rates. In this setting, buyers' budgets, which are initialized the start of the game, persist across states, and are replenished by constant amount with each state transition. Thus, the buyers' budgets from one state to the next are deterministic.
Second, we modeled a larger stochastic Fisher market with savings and probabilistic interest rates. In this model, although buyers' savings persist across states, they are nondeterministic, or decrease based on the random movements of an interest rate with each state transition. More specifically, we chose five different equiprobable interest rates (0.9, 1.0, 1.1, 1.2, and 1.5) to provide buyers with more incentive to save as compared to the model without interest rates.
they increase
Since budgets are part of the state space in stochastic Fisher markets, the state space is continuous; so we attempted to estimate the value function at each iteration of value iteration by running linear regression on a sample of state and associated min-max value pairs, finding fit via linear regression (e.g., (22). To compute the min-max value of each state that we sampled, i.c., the solution to the optimization problem in line 4 of Algorithm [ we used nested gradient descent ascent (6) which runs step of gradient descent on the prices and loop of gradient ascent on allocations and savings repeatedly (Algorithm B) where we computed gradients via nuto-differentiation using JAX (63) which we observed achieved better numerical stability than analytically derived gradients as can often be the case with autodifferentiation (64]
In both experiments, to check whether the optimal value function was found, we measured the exploitability of the market, meaning the distance between the recCE. computed and the actual recCE. To do so, we checked two conditions: I) whether each buyer's 's expected utility was maximized at the computed allocation and savings, at the prices outputted by the algorithm, and 2) whether the market always cleared. In both settings, we extracted the greedy policy from the value function computed by value iteration, and unrolled across time to obtain the greedy actions (X(1), (1)), p()) at each state s(t) We then computed the cumulative utility of these allocation and savings, i.e., for all E [m]. ú, = ET= r'u,(=!")), We compared these values to the expected maximum utility uf, given the prices and the other buyers' allocations computed by our algorithm. We report the normalized distance between these two values, û, and ut, which we call the normalized distance to utility maximization (UM). For example, in the case of two buyers, the normalized distance to UM ((ā),ā)) (.) (m)l Finally, we also measured excess demand, which we took as the distance to [[(s
market clearance (MC), i.e., 1 Σt= E[El1 x
(0112
In the experiment with smaller markets and without interest rates, Figure D depicts the average value of the value function across a sample of states as it varies with time, and Table records the exploitability of the recCE found by nested GDA. For all three class of utility functions, not only do the value functions converge, exploitability is also sufficiently minimized, as all the buyer utilities are maximized and the market always clears.
*Our code can be found here and details of experimental setup can be found in Appendix

---

Average Values acmos Budtguts with Nested CIM
100
Learest
Linear
Douglen
Utility
500
Distance to UM
Distance to MC
Class
100
Linear
0.011
0.010
Leontief
0.056
0.010
200
Cobb-Douglas
0.006
0.010
Table I: Exploitability of recCE found by Nested GDA.
Figure 1: The value function averaged across budgets.
Table 2: Nested GDA in stochastic Fisher markets with savings but without interest rates.
Values Nested GDA
Lnoar Leontet
Dougins
Utility
Distance to UM
Distance to MC
Class
Linear
0.040
0.009
Leontief
0.463
0.009
509
Cobb-Douglas
0.017
0.009
250
Table 3: Exploitability of recCE found by Nested GDA.
20
Figure 2:
The value function averaged across budgets.
Table 4: Nested GDA in stochastic Fisher markets with savings and probabilistic interest rates.
In the experiment with larger markets and probabilistic interest rates (Figure 2 Table 3 in lincar and Cobb-Douglas markets, the value functions converge, and exploitability sufficiently minimized. In Leontief markets, however, although the value function converges and the markets almost clear, the buyers' utilities are not fully maximized, since the cumulative utilities they obtained are less than half of their expected maximum utilities. The difficulty in this case likely arises from the fact that the Leontief utility function is not differentiable, so the problem for Leontief markets neither smooth nor convex-concave, which makes it difficult, if not impossible, for nested GDA find even a stationary point of the objective of the min-max optimization problem line 4 of Algorithm [] since gradient ascent function is not guaranteed to converge stationary point of that function if it is non-come con-convex-nonn -oo-e---oooo-oot------- 65
Conclusion
In this paper, we proved the existence recursive Stackelberg equilibria in zero-sum stochastic Stackelberg games, provided necessary and sufficient conditions for policy profile to be recursive Stackelberg equilibrium, and showed that Stackelberg equilibrium can be computed in (weakly) polynomial time via value iteration. Finally, we showed that recursive Stackelberg equilibria coincide with recursive competitive equilibria in stochastic Fisher markets, and we used value iteration together with nested GDA to solve for them. Future work in this space could try using deep reinforcement learning methods to learn better (i.e.. nonlinear) representations of the value functions. It is also conceivable that deep reinforcement learning would be able learn better policies, thereby resolving the difficulties that our methods face due to non non-smootee non-smoothness and non-concavity have in solving for global solutions of the min-max optimization problem in line 4 of Algorithm
Acknowledgments and Disclosure of Funding
This work was supported by NSF Grant CMM1-1761546.
10

---

References
[1] J v Neumann. "Zur theorie der gosellschaftsspicle" In: Mathematische annalen 100.1 (1928),
pp. 295-320.
[2] Maurice Sion et al. "On general minimax theorems." " In: Pucific Journal of mathematics 8.1
(1958), pp. 171-176.
[3] Lloyd S Shapley. "Stochastic games". : In: Proceedings of the national academy of sciences
39.10 (1953), pp. 1095-1100.
[4] Eric Maskin and Jean Tirole. "Markov perfect equilibrium: Observabble actions", In: Journal of Economic Theory 100.2 (2001), pp. 191-219.
[5] Anna Jaškiewiez and Andrzej S Nowak. "Zero-sum stochastic games". In: Handbook of dynamic game theory (2018), pp. 1-64.
[6] Denizalp Goktas and Amy Greenwald. "Convex-Concave Min-Max Stackelberg Games". In: Advances in Neural Information Processing Systems 34 (2021).
[7] Dimitris Bertsimas, David B Brown, and Constantine Caramanis. "Theory and applications of robust optimization". In: SIAM review 53.3 (2011), pp. 464-501.
[8] Jaime Fisac et "Reach-avoid problems with time-varying dynamics, targets and con- straints". In: Proceedings of the 18th international conference on hybrid systems: computation and control. 2015, pp. 11-20.
[9] Somil Bansal et al. "Hamilton-jacohi reachability: A brief overview and recent advances". In: 2017 IEEE 56th Annual Conference Decision and Control (CDC). IEEE, 2017, pp. 2242- 2253.
[10] Karen Leung et al. "Learning Autonomous Vehicle Safety Concepts from Demonstrations", In: arXiv preprint arXiv:2210.022 (2022).
[11] Yevgeniy Vorobeychik and Satinder Singh. "Computing stackelberg equilibria in discounted stochastic games". In: Proceedings of the AAAI Conference Artificial Intelligence. Vol. 26.
1. 2012, pp. (478-1484)
[12] William C Brainard, Herbert E Scarf, et al. How to compute equilibrium prices in 1891.
Citeseer, 2000.
[13] Peter H. Friesen. "The Arrow-Debreu Model Extended to Financial Markets". In: Econometrica
47.3 (1979), pp. 689-707. ISSN: 00129682, 14680262. URL: http: www jstor org stable/1910415
[14] Kenneth Arrow and Gerard Debreu. "Existence of an equilibrium for a competitive economy".
In: Econometrica: Journal the Econometric Society (1954), pp. 265-290..
[15] R Mehra and EC Prescott. "Recursive Competitive Equilibria and Capital Asset Pricing". In: Essays in Financial Economics (1977).
[16] Paul Tseng. "On linear convergence of iterative methods for the variational inequality problem". In: Journal of Computational and Applied Mathematics 60.1 (1995). Proceedings of the International Meeting Lineat/Nonlinear Iterative Methods and Verification of Solution,
pp. 237-252 ISSN: 0377-0427. DOE: http::::/ddoirrrgr 11111/00777--477774 URI.: https://wwe weciencediree rect. httptt//oo/..eeeeeeeeeee/eee////
[17] Yurii Nesterov and Laura Scrimali. "Solving strongly monotone variational and quasi- variational inequalities". In: Discrete & Continuous Dynamical Systems 31.4 (201 I), pp. 1383
1396.
[18] Gauthier Gidel et al. Variational Inequality Perspective on Generative Adversarial Networks. 2020. arXiv: 1802. 10551 [G]
[19] Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. Convergence Rate O(1kk) for Optimistic Gradient and Extra-gradies Methods in Smooth Conver-Concave Saddle Point Problems. 2020. arviv: 1906. 01115 [math. [C]
[20] Adam Ibrahim et "Lower bounds and conditioning of differentiable games". In: arXiv preprini arXiv: /900: 0900.0730000000 (2019).
[21] Mingyi Hong, Junyu Zhang, Shuzhong Zhang, al. On Lower lteration Complexity Bounds for the Saddle Point Problems. 2020. arXiv: 1912.00 07481 [math.OC]
[22] Tianyi Lin, Chi Jin, and Michael I Jordan. "Near-optimal algorithms for minimax optimization". In: Conference Learning Theory. PMLR. 2020, pp. 2738-2779.

---

[23] Mohammad Alkousa et al. Accelerated methods for composite non-bilinead saddle point problem. 2020. arXiv: 1906. 03620 [math. OC]
[24] Anatoli Juditsky, Arkadi Nemirovski, et al. "First order methods for nonsmooth convex large-
scale optimization, ii: utilizzing problems structure". In: Optimization for Machine Learning 30.9 (2011), pp. 149-183.
[25] Erfan Yazdandoost Hamedani and Necdet Serhat Aybat. "A primal-dual algorithm for general convex-concave saddle point problems". In: arXiv preprint 1803.v8803.01440 (2018). [26] Zhao Renbo. Optimal algorithms for stochastic three-composite convex-concave saddle point problems. 2019. arXiv: 1903. 01 687 [math.OC, OC],
[27] Kiran Koshy Thekumparampil et al. Efficient Algorithms for Smooth Minimax Optimization.
2019. Xiv: 1907 01543 [math.OC]]
[28] Yuyuan Ouyang and Yangyang Xu. Lower complexity bounds of first-order methods for convex-concare bilinear saddle-point problems. 2018. arXiv: 1808. 02901 [aath.OC]
[29] Arkadi Nemirovski. "Prox-method with rate of convergence O (1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems". " In: SIAM Journal on Optimization 15.1 (2004). pp. 229-251.
[30] Yurii Nesterov. "Dual extrapolation and its applications to solving variational inequalities and related problems".. In: Mathematical Programming 109.2 (2007), pp. 319-344.
[31] Paul Tseng. "On accelerated proximal gradient methods for convex-concave optimization". In: submitted to SIAM Journal on Optimization 1 (2008).
[32] Maziar Sanjabi et al. "On the Convergence and Robustness of Training GANs with Regular- ized Optimal Transport". In: Proceedings of the 32nd International Conference on Neural Information Processing Systems. NIPS' 18. Montreal, Canada: Curran Associates Inc., 2018, pp. 7091-7101.
[33] Maher Nouiehed et al. "Solving a class of non-convex min-max games using iterative first order methods". In: arXiv preprint arXiv: / 08297 (2019).
[34] Songtao Lu, Ioannis Tsaknakis, and Mingyi Hong. "Block alternating optimization for non- convex min-max problems: algorithms and applications in signal processing and communi- cations". In: ICASSP 2019-2019 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP). IEEE. 2019, pp. 4754 4758.
[35] Chi Jin, Praneeth Netrapalli, and Michael Jordan. What Local Optimality Nonconvex- Nonconcave Minimax Optimization? 2020. arxiv: 1902. 00618 [Cs.LG]
[36] Dmitrii M Ostrovskii, Andrew Lowy, and Meisam Razaviyayn. "Efficient search of first- order nash equilibria in nonconvex-conest smooth min-max problems". In: arXiv preprint arXiv:2002.0799 (2020).
[37] Tianyi Lin, Chi Jin, and Michael Jordan. "On gradient descent ascent for nonconvex-concave minimax problems". In: International Conference on Machine Learning. PMLR. 2020,
pp. 6083-6093.
[38] Renbo Zhao. A Primal Dual Smoothing Framework for Mux-Structured Nonconver Optimiza- tion. 2020. arXiv: 2003. 04375 [math. [m
[39] Hassan Rafique et al. Non-Convex Min-Max Optimization: Provable Algorithms and Applica- tions in Machine Learning. 2019. arXiv: 1810. 02060 [math.OC]
[40] Denizalp Goktas and Amy Greenwald. Robust No- Ro-Regret Learning in Min-Max Stackelberg Games. 2022.
[41] Alain Bensoussan, Shaokuan Chen, and Suresh P Sethi, "The maximum principle for global solutions of stochastic Stackelberg differential games". In: SIAM Journal on Control and Optimization 53.4 (2015), pp. 1956-1981.
[42] Quoc-Liem Vu et al. "Stackelberg Policy Gradient: Evaluating the Performance of Leaders and Followers". In: ICLR 2022 Workshop on Gamification and Multiagent Solutions. 2022.
[43] Giorgia Ramponi and Marcello Restelli. "Learning Markov Games: can we exploit a general-sum opponent?" In: The 38th Conference on Uncertainly in Artificial Intelligence. 2022.
[44] Yanling Chang, Alan Erera, and Chelsea C White. "A leader partially observed, multiobjective Markov game". In: Annals of Operations Research 235.1 (2015), pp. 108-128.
12

---

[45] Sailik Sengupta and Subbarao Kambhampati. "Multi-agent reinforcement learning in bayesian stackelberg markov games for adaptive moving target defense". In: arXiv preprint arXiv:2007. 10457 (2020).
[46]
Deepanshu Vasal. Stochastic Stackelberg games. 2020. arXiv: 2005. 01997 [math. [C]
[47] Victor DeMiguel and Huifu Xu. "A stochastic multiple-leader Stackelberg model: analysis, computation, and application". In: Operations Research 57.5 (2009), pp. 1220-1235.
[48] Tao Li and Suresh P Sethi. "A review of dynamic Stackelberg game models". In: Discrete & Continuous Dynamical Systems-B B 22.1 (2017), p. 125.
[49] Lv Chen and Yang Shen. "On a new paradigm of optimal reinsurance: a stochastic Stackelberg differential game between an insurer and a reinsurer". In: ASTIN Bulletin: The Journal of the IAA 48.2 (2018), pp. 905-960.
[50] Yu Yuan, Zhibin Liang, and Xia Han. "Robust reinsurance contract with asymmetrie informa- tion in a stochastic Stackelberg differential game". In: Scandinavian Actuarial Journal (2021),
pp. 1-28.
[51] Xiuli He, Ashutosh Prasad, and Suresh P Sethi. "Cooperative advertising and pricing in dynamic stochastic supply chain: Feedback Stackelberg strategies". In: SCCMET008-2000 Portland International Conference on Management of Engineering & Technology. IEEE. 2008,
pp. 1634-1649.
[52] Sean C Rismiller, Jonathan Cagan, and Christopher McComb. "Stochastic stackelberg games for agent-driver driven robust design". In: International Design Engineering Technical Conferences and Computers and Information in Engineering Conference. Vol. 84003. American Society of Mechanical Engineers. 2020, V11ATI
[53] Bernt Oksendal, Leif Sandal, and Jan Uboe, "Stochastic Stackelberg equilibria with applica- tions to time-dependent newsvendor models". In: Journal of Economic Dynamics and Control 37.7 (2013), pp. 1284-1299.
[54] N. R. Devanur et al. "Market equilibrium via a primal-dualtypp algorithm". In: The 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002. Proceedings. 2002.
pp. 389-395. Do1: 16. 101.011011111 1T09/FFCC 2002. 1181963
[55] Yun Kuen Cheung, Martin Hoefer, and Paresh Nakhe. "Tracing Equilibrium in Dynamic Markets via Distributed Adaptation". In: Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems. 2019, pp. 1225-1233.
[56] Yuan Gao, Christian Kroer, and Alex Peysakhovich. "Online Market Equilibrium with Appli- cation to Fair Division". In: Advances in Neural Information Processing Systems 34 (2021).
[57] Stefan Banach. "Sur les opérations dans les ensembles abstraits et leur application aux équa- tions intégrales". In: Fund, math 3.1 (1922), pp. 133-181.
[58] L. M. Benveniste and J. A. Scheinkman. "On the Differentiability of the Value Function in Dynamic Models of Economics" In: Econometrica 47.3 (1979), pp. 727-732. ISSN: 00129682, 14680262. URL: http://://ww...stroorrrrrroee. /ttttoorgg/ttbbl//11eeee
[59] David Romer. Advanced Macroeconomics, 4e. New York: McGraw-Hill, 2012.
[60] Chi Jin et al. "How to escape saddle points efficiently". In: International Conference Muchine Learning. PMLR. 2017, pp. 1724-1732.
[61] Simon S Du et al. "Gradient descent can take exponential time to escape saddle points". In: Advances in neural information processing systems 30 (2017).
[62] Justin Boyan and Andrew Moore. "Generalization in reinforcement learning: Safely approxi- mating the value function"" In: Advances in neural information processing systems 7 (1994).
[63] James Bradbury et al. JAX: composable transformations of Python+NumPyy programs. Ver- sion 0.3. 2018. URL: http: / //gi thub. com/ google/jax
[64] Andreas Griewank, Kshitij Kulshreshtha, and Andrea Walther. "On the Numerical Stability of Algorithmic Differentiaaion" In: Computing 94.2-4 (Mar. 2012), pp. 125-149. ISSN: 0010- 485x. DOI: To. 1007/ 001-006677011--1622
URL: ht // org/ 10. 1007/500607
011-0162-2
[65] Michael I Jordan, Tianyi Lin, and Manolis Zampetakis. "On the Complexity of Deterministic Nonsmooth and Nonconvex Optimization". In: arXiv preprint arXiv:2209. 1233442309.1 (2022).
[66] Richard Bellman. "On the theory of dynamic programming" In: Proceedings of the National Academy of Sciences of the United States of America 38.8 (1952), 716.
13

---

[67] Harley Flanders. "Differentiation Under the Integral Sign". In: The American Mathematical Monthly 80.6 (1973), pp. 615-627. ISSN: 00029890, 19300972. URL: http: jstor
htg/stabble2239115
[68] Alp E. Atakan. "Stochastic Convexity in Dynamic Programming" In: Economic Theory 22.2 (2003), pp. 447-455 ISSN: 09382259, 14320479.
URL: http: //t////wwwwww/ baastorrorgo. htt.o//bl///////e////eee/
25055693
[69]
HW Kuhn and AW Tucker. Proceedings of 2nd berkeley symposium. 1951.
[70] S. N. Afriat. "Theory Maxima and the Method of Lagrange". In: SIAM Journal on Applied
Mathematicc 20.3 (1971), pp. 343-357. ISSN: 00361399, URL: http: www..sttrr......o............... org/ stable/2099955
[71] Paul Milgrom and Ilya Segal. "Envelope theorems for arbitrary choice sets". In: Econometrica 70.2 (2002), pp. 583-601.
[72] Guido Van Rossum and Fred Drake Jr. Python tutorial. Centrum voor Wiskunde en Infor- matica Amsterdam, The Netherlands, 1995.
[73] Charles R. Harris al. "Array programming with NumPy". In: Nature 585 (2020), pp. 357-
362. DO1: 10. 1038/544000 04///415555 586-156662 0000000-2922 2649-2)
[74] Steven Diamond and Stephen Boyd. "CVXPY: A Python-embedded modeling language for convex optimization". In: Journal of Machine Learning Research 17.83 (2016), pp. 1-5.
[75] J. D. Hunter. "Matplotlib: 2D graphics environment". In: Computing Science Engineer-
ing 9.3 (2007), pp. 90-95. DOT: 10. 109/MCSE 2007. 55
14

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] Yes, details are discussed in
conclusion, and experiments sections.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions all theoretical results? [Yes] Assumptions are summarized in Assumption
(b) Did you include complete proofs of all theoretical results? [Yes] Yes, all proofs can be found in the appendix.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or URLY? [Yes] Yes. code repo can be found here: / www.coo///aaa// Sonn/Saiie-Zho. Zero- srttchastic-sttakelllee----mm
(b) Did you specify all the training details (c.g.. data splits, hyperparameters, how they were chosen)? [Yes] Details can be found in section 5 and Appendix E.
(c) Did report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [Yes] For experiments run multiple times, i.c., zero-sum convex constraints, exploitability always reached zero, and there was hence no error to report in all randomly initialized examples.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes]] Details can be found in Appendix E.
4. If you are using existing assets (e.g., code, data, models) or curating/rellusing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] Details can be found in Appendix E.
(b) Did you mention the license of the assets? [Yes] Details be found in Appendix E.
(c) Did you include any assets either in the supplemental material URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'le 're're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "KywiZC_wFkh", "reviewer": "Reviewer_nfFs", "summary": "The authors analyze the zero-sum stochastic Stackelberg game. They proved the existence of an optimal solution in zero-sum games and showed how to compute a recursive Stackelberg equilibrium via value iteration. Then they provide some applications of stochastic Stackelberg games.", "questions": "1. Could Lemma 2.1 be written only from the \"equivalently\" part? The first part seems redundant.\n\n2. It would be useful to add citations on how to solve the min-max constrained problem defined by the contraction operator.\n\n3. How does the proposed method differ from the min-max algorithm from [1]?\n\n4. Remark 2.6 said that the payoff function can also be non-convex-non-concave. How can we solve the optimization problem given by the contraction operator if the payoff function is non-convex-non-concave?\n\n5. How can the algorithm be independent of the initial-state distribution? If we start from a state $s$ which is disconnected from the other states we are achieving a different recSE... or am I missing something (maybe connected to Assumption 1)?\n\n6. I find section 3 quite interesting but not well commented. I suggest explaining better what the implications of the proposed theorem are.\n\n7. Although less interesting, it would be useful to add experiments with finite state-action spaces, where the authors can use the value-iteration method. Is it possible to use [2] as a baseline?\n\n8. Are there other applications of the game considered?\n\n[1] Littman, M. L. (1994). Markov games as a framework for multi-agent reinforcement learning. In Machine learning proceedings 1994 (pp. 157-163). Morgan Kaufmann.\n\n[2] Fiez, T., Chasnov, B., & Ratliff, L. (2020, November). Implicit learning dynamics in stackelberg games: Equilibria characterization, convergence analysis, and empirical study. In International Conference on Machine Learning (pp. 3133-3144). PMLR.", "limitations": "Since there is space the authors could add a section analyzing the limitation and the potential negative societal impact of their work. However, since the work is more theoretical, I don't think it has an immediate negative societal impact.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n1. The paper studies an interesting problem: a leader-follower game where the follower's actions depend on the leader's actions. \n\n2. The authors propose (as far as I know) a novel solution concept recSE and study when this equilibrium exists in stochastic games.\n\n3. The authors propose a value-iteration algorithm to converge to the equilibrium solution.\n\n\nWeaknesses\n1. The related work does not mention the works on Stochastic Stackelberg Games and Leader-follower stochastic Stackelberg games as [1,2,3,4,5]. What is the relation between the considered setting and these other ones? Maybe the name stochastic Stackelberg game is not the most appropriate.\n\n2. Line 129, 140, 264 have formatting problems. $\\alpha$ is an unusual way to bound the rewards I suggest putting 1 or $R_\\max$.\n\n3. I have some questions which I listed below. \n\n[1] Vorobeychik, Y., & Singh, S. (2012). Computing stackelberg equilibria in discounted stochastic games. In Proceedings of the AAAI Conference on Artificial Intelligence (Vol. 26, No. 1, pp. 1478-1484).\n\n[2] Chang, Yanling, Alan L. Erera, and Chelsea C. White. \"A leader–follower partially observed, multiobjective Markov game.\" Annals of Operations Research 235.1 (2015): 103-128.\n\n[3] Sengupta, S., & Kambhampati, S. (2020). Multi-agent reinforcement learning in bayesian stackelberg markov games for adaptive moving target defense. arXiv preprint arXiv:2007.10457.\n\n[4] Ramponi, G., & Restelli, M. (2022, February). Learning in Markov Games: can we exploit a general-sum opponent?. In The 38th Conference on Uncertainty in Artificial Intelligence.\n\n[5] Vu, Q. L., Alumbaugh, Z., Ching, R., Ding, Q., Mahajan, A., Chasnov, B., ... & Ratliff, L. J. (2022, March). Stackelberg Policy Gradient: Evaluating the Performance of Leaders and Followers. In ICLR 2022 Workshop on Gamification and Multiagent Solutions.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "8MEWSlQMFXy", "reviewer": "Reviewer_j5ee", "summary": "This paper studies zero-sum Stackelberg games. First, this paper proves the existence of the recursive Stackelberg equilibrium. Furthermore, the authors provide necessary and sufficient conditions for identifying the Stackelberg equilibrium and show that a recursive Stackelberg equilibrium can be computed in polynomial time via value iteration. Finally, the authors show that the stochastic Fisher market can be modeled by the stochastic Stackelberg games.", "questions": "1. \tIt seems that some results (e.g. value iteration) are straightforward. I hope the authors point out the non-trivial part if I miss something. I also encourage the authors to highlight the technique novelties in the paper.\n2. \tThis paper only considers planning problems where the model is known. Recently, some papers considers learning problems in Stackelberg games [1] [2]. Can these methods (with some modifications) be applied to finding recursive Stackelberg equilibria in online zero-sum Stackelberg games? I hope the authors make some comments on this.\n \n[1] Y. Bai, C. Jin, H. Wang, and C. Xiong. Sample-efficient learning of Stackelberg equilibria in general-sum games. In NeurIPS, 2021.\n \n[2] H. Zhong, Z. Yang, Z. Wang, and M. I. Jordan. Can reinforcement learning find Stackelberg-Nash equilibria in general-sum Markov games with myopic followers? 2021. arXiv:2112.13521.\n \n", "limitations": "Yes", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper studies the zero-sum Stackelberg game and provides a complete set of results for this problem. The authors also show that the zero-sum Stackelberg game can model the Fisher market. This is interesting. But I still have some concerns (see the questions below).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "4b5soW7IV3i", "reviewer": "Reviewer_CYu7", "summary": "The paper introduces a novel variant of the stochastic game model, where the available strategies of one player may be constrained by strategy choice of the other player. The paper establishes the existence of a corresponding solution concept and shows that a variant of value iteration approaches it. The paper shows the relevance of the proposed model by using it to model a realistic variant of Fisher market. Finally, the paper demonstrates that the algorithm converges very close to the solution in some games and a little further in more complex games.", "questions": "What is the intuitive reason why the solution does not depend on the initial distribution?\n", "limitations": "The limitations are discussed and I do not think there is a significant societal impact.", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "I enjoyed reading the paper. The paper is not very well motivated in the introduction, but the separate Section 4 already nicely demonstrates the usefulness of the model. The results in the paper are not very surprising, but still important to establish for a new game model. The content is quite technical, but notation is intuitive and definitions sufficiently thorough to make the paper reasonably easy to follow. \n\nI have only smaller suggestions for improvements:\n\nI understand the motivation by the Stackelberg setting.and I like the name of the model. However, referring to the distinction from the standard model as static vs. dynamic is very confusing for me. Stochastic games are fundamentally dynamic and referring to the games as static/dynamic based on what happens in individual states makes the claims, e.g. in the abstract, sound just wrong.\n\nLines 49-51: It was completely unclear to me how the mentioned games could benefit from being modeled as Stackelberg games.\n\nLine 65-66: The line of 22 references without giving any context is useless and makes it look like an artificial inflation of the number of citations. What is the reader supposed to learn from that? Since this paper is about the Slackelberg setting, these papers do not seem relevant at all.\n\nLines 69-78: Similar as above, I am not sure what is the relation of these papers to the current work. Few lines of explanation would be very appreciated.\n\nLine 243: I guess you mean equations (1)-(5).\n\nI would appreciate a plain text explanation of equation (6) to make it faster to understand.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept