11institutetext: Artificial Intelligence Center, Department of Computer
Science,
Faculty of Electrical Engineering, Czech Technical University in Prague

# Computing Stackelberg Equilibrium with Memory in Sequential Games

Aditya Aradhye Branislav Bošanský Michael Hlaváček Email address:
<EMAIL_ADDRESS>Aditya Aradhye  Corresponding author.
Artificial Intelligence Center, Faculty of Electrical Engineering, Czech
Technical University in Prague, Karlovo nám. 13, 120 00, Prague, Czech
Republic.
E-mail address<EMAIL_ADDRESS>Branislav Bošanský
<EMAIL_ADDRESS>Michael Hlaváček<EMAIL_ADDRESS>
###### Abstract

Stackelberg equilibrium is a solution concept that describes optimal
strategies to commit: Player 1 (_the leader_) first commits to a strategy that
is publicly announced, then Player 2 (_the follower_) plays a best response to
the leader’s commitment. We study the problem of computing Stackelberg
equilibria in sequential games with finite and indefinite horizons, when
players can play history-dependent strategies. Using the alternate formulation
called strategies with memory, we establish that strategy profiles with
polynomial memory size can be described efficiently. We prove that there exist
a polynomial time algorithm which computes the Strong Stackelberg Equilibrium
in sequential games defined on directed acyclic graphs, where the strategies
depend only on the memory states from a set which is linear in the size of the
graph. We extend this result to games on general directed graphs which may
contain cycles. We also analyze the setting for approximate version of Strong
Stackelberg Equilibrium in the games with chance nodes.

JEL Classification: C61; C73; D83

_Keywords:_ Sequential games, Strategies with memory, Commitment, Strong
Stackelberg equilibrium

##  1 Introduction

The Stackelberg competition was introduced by von Stackelberg [29] addressing
an economic problem of duopoly. One player— _the leader_ —chooses a strategy
to execute and publicly announces this strategy. The second player— _the
follower_ —decides its own strategy only after observing the strategy of the
first player. The leader must have commitment power (for instance a firm with
monopoly in an industry) and cannot undo its publicly announced strategy,
while the follower (for instance a new competitor) plays a best response to
the leader’s chosen strategy.

The Stackelberg competition and the solution concept of a _Stackelberg
equilibrium_ have been extensively studied in economics (e.g., [24, 1, 21]),
in computer science (e.g., [30, 8, 19]), and have many important applications.
One of the desired characteristics is that Stackelberg equilibrium
_prescribes_ the leader a strategy to be executed, assuming the follower
reacts to this strategy. This asymmetry arises in many real-world scenarios
where the leader corresponds to a government or a defense agency that need to
publicly issue and execute a policy (or a security protocol) which others can
observe. Indeed, many of the successful applications of Stackelberg
equilibrium strategies can be found in security domain (see [26, 25] for an
overview) or, for example, in wildlife protection [11, 10].

We are interested in the computational questions of Stackelberg equilibrium
and restrict to the two-player setting with one leader and one follower
111This setting has attained the most attention in the real-world
applications. Moreover, computing a Stackelberg equilibrium with $2$ or more
followers requires finding a specific Nash equilibrium in a general-sum game
as a subproblem, which is already a computationally hard task [3].. We focus
on sequential (or dynamic) games that are played over time. In this setting,
the leader commits to a randomized strategy in each possible decision point
that can arise in the game and the follower plays a best response to this
commitment. Only few applied models consider strategic sequential interactions
among the players directly (e.g., in [31]), however, many currently modeled
scenarios are essentially sequential – police forces can commit to a security
protocol describing not only their allocation to targets but also their
strategy in case of an attack (or some other event) and results in a strategic
response. Similarly, sequential models would allow rangers in national parks
react to immediate observations made in the field.

In this paper, we study sequential games in which the state of the game is
perfectly observable by the players. Games with determined finite horizon are
played on a directed acyclic graph (DAG) and games without determined finite
horizon are played on a general directed graph (DG). In such graphs, each node
corresponds to a state of the game. Each node is assigned to a player that
decides which action (an edge) to take and the game transitions to another
state. Terminal states have assigned pair of utility values, one value for
each player. The goal of the leader is to find such a strategy to commit to
that maximizes the expected outcome if the follower plays a best response. Our
solution concept is strong Stackelberg equilibrium (SSE), in which the
follower breaks ties in favour of the leader. The complexity of computing
equilibria in these games have been analyzed for many settings, however, most
of the previous works is aimed at computing strategies which do not depend on
past history (with the exception of works by Gupta et al. [13]) – i.e., the
leader commits to a probability distribution over actions in each node
assigned to her.

The determining result is due to Letchford and Conitzer [19], showing a
polynomial time algorithm to compute SSE in the sequential games with two
players in the following settings: (1) The graphs are trees and players can
play mixed strategies (2) The graphs are DAGs and players are restricted to
play only pure strategies. The main idea in these algorithms is to compute the
sets of the outcomes which the leader can guarantee, and these sets are used
to construct commitment of the leader. They however, also show NP-hardness
result of computing SSE in mixed strategies played on DAGs.

The main driving factor of their hardness result is the following. In the
directed acyclic graphs, there are large number paths arriving at a node. The
leader needs to commit to one of many possible actions at that node,
irrespective of the path which leads to this node. If the number of such nodes
is large (linear in the size of the graph), it might result in finding an
optimal solution among the potentially exponentially many outcomes. This issue
is exploited by [18, 19] to reduce the SAT problem to sequential games on DAGs
with mixed strategies, thus proving the hardness result. Hence, the main issue
here is the inability of the leader to make decisions irrespective of the path
followed to reach a particular node.

###  1.1 Our contributions

We address the natural question that arises from the above discussion. Is it
possible to compute the SSE in polynomial time for games on DAGs where players
are allowed to use mixed strategies which can depend on history? Is there a
way around to efficiently describe history-dependent strategies, since the
possible number of histories is exponential in the size of the graph? In this
paper we positively answer both of these questions.

Since the players are rewarded utility only at the terminal nodes, the actual
path taken to reach that node does not matter for the sake of computing the
utility. However in games on DAGs and DGs, histories can still play an
important role in determining the behaviour of the players, as they can be
used as a virtual randomization device. Using different histories to reach at
the same node controlled by the follower, the leader can enforce certain
behaviour from the follower in best response, and can also use the histories
to punish the follower if the follower does not play accordingly. When players
can use history-dependent mixed strategies, the solution of SSE differs from
their history-independent counterpart. As the strategy space is richer, the
leader is always (at least weakly) better off. Fig.2 shows an example of a
game in which strategy profile with memory gives a strictly better payoff for
the leader when compared to the their history-independent counterpart.

In case of DAGs and DGs, there can be exponentially large number of histories.
In such cases it is impossible to fully describe a general history-dependent
strategy efficiently. However as we show that there are strategy profiles
which can be described efficiently, as they uses only a partial information
from the histories. To capture the idea that the players might not use the
entire history space to make their decisions, we define a different
formulation for history-dependent strategy profiles, called strategy profile
with memory. According this formulation, the strategy profiles are equipped
with a set of public memory states. These memory states store a partial
information about the past history. The players can make decisions depending
only on the current memory state, and not on the entire history. This
formulation however does not restrict the set of history-dependent strategy
profiles. If the set of memory states is equal to the set of all possible
histories, then any arbitrary history-dependent strategy can be described as a
strategy profile with memory, since both players are perfectly informed. On
the other hand, if the set of memory states is small, particularly polynomial
in size, then the strategies can be described efficiently.

The main result of this paper is the existence of polynomial time algorithm to
compute SSE with memory (size of memory set is linear in the size of graph) in
DAGs. Firstly, the algorithm performs a dynamic programming style upward pass
to constructs the commitment sets of the outcomes (probability distribution on
terminal nodes) to which the leader can commit, that is, there is a commitment
strategy for the leader and a corresponding best response from the follower
such that the given outcome is reached. Also importantly, this upward pass
also recursively stores the information which can be used later to compute the
commitment for the leader. Using this information, the algorithm then performs
a downward pass, which constructs a commitment strategy for the leader. They
crucial step in the downward pass is the construction of the memory states.
The memory states act as a recommendation for the follower to preform certain
actions so as to reach the outcome desired for the commitment of the leader.
Whenever the follower takes an action other than the one suggested by the
memory state, the game perpetually goes into ’red flag’ memory state. On
observing the red flag memory state, the leader plays punishing strategy which
commits to the outcome with the lowest possible utility for the follower. This
acts as an incentive for the follower to act according the recommendations
from the memory state.

We extend our result to games on general DGs. Although the dynamic programming
techniques can not be used directly due to the existence of directed cycles,
we are able to modify our algorithm by decomposing the graph into strongly
connected components (SCCs) and applying the dynamic programming on the set of
SCCs. The main driving factor here is that although the nodes may be visited
multiple times in a SSE, which would make the computation difficult, we show
an existence of a SSE in which any node is visited at most twice with positive
probability. This results allows us to use the upward pass twice to construct
the commitment sets accurately, and the downward pass works similarly. When
there are chance nodes, a reduction similar to [19] shows that it is NP-hard
to compute SSE with memory. [4] shows a polynomial time algorithm for the
approximate version of SSE for history-independent strategies on trees. With
the strategies with memory formulation, we extend this result for DAGs.

###  1.2 Related Work

There is a rich body of literature studying the problem of computing
Stackelberg equilibria. Our setting is closely related to the literature
studying the Stackelberg equilibrium in the extensive form games. Letchford et
al.[19] showed the existence of polynomial time algorithm to compute the
Stackelberg equilibrium in the extensive form games in the cases where either
the graph was a tree or the players are restricted to play pure strategies.
They also show the NP hardness result if there exist chance nodes or if the
graph is DAG and strategies are mixed. Bošanský et al. [4] showed that
allowing the leader to commit to correlated strategies can reduce
computational complexity (e.g., computing Stackelberg equilibrium is NP-hard
on games with chance, but polynomial when the leader commits to correlated
strategies). They also show an FPTAS algorithm to compute the Stackelberg
equilibrium in games with chance nodes. Kroer et al. [16, 17], consider the
Stackelberg setting in a limited lookahead variant of extensive form games. In
a related work for dynamic games, Černý et al. [28] proposed compact
representation of strategies in the form of automata playing extensive-form
games. In their work, the authors show that Stackelberg equilibrium can be
computed in polynomial time when the complexity of the strategies is bounded.

The main feature of our setting that separates our paper from the others is
that in our setting, the players can base decision on the past history. To the
best of our knowledge, no previous work analyzed the impact of allowing the
leader to use memory in finite games played on directed graphs. There are some
results for infinite stochastic games by Gupta et al. [13] who considered
Stackelberg equilibria with memory in games on directed graphs. However, their
objective is to optimize discounted sum and they have negative results about
finiteness of the memory needed. Later, these results were extended to mean
payoff games [12].

Our setting also relates to other class of Stackelberg games in a broader
sense. The computational complexity of the problem is known for one-shot games
[8], Bayesian games [8], and some infinite stochastic games [12, 13, 20].
Similarly, many practical algorithms are also known and typically based on
solving multiple linear programs [8], or mixed-integer linear programs for
Bayesian [23] and extensive-form games [5, 27]. The Stackelberg equilibria are
studied extensively in the various models of security games [2, 6, 9, 14, 15,
22] Another variant of the Stackelberg notion is when the leader is allowed to
commit to correlated strategies [7, 20, 32].

The structure of the paper is as follows. In section 2 we introduce the model
and in the section 3, we define the concept of strategy profile with memory.
In sections 4 and 5 we discuss the polynomial time algorithm to compute the
SSE in the games on DAGs and general DGs respectively. In section 6, we
describe discuss the setting on directed acyclic graphs with chance nodes and
in section 7, we have concluding remarks.

##  2 Sequential games

We consider two-player general sum sequential games, both with finite and
indefinite horizon.

###### Definition 1

A two-player sequential game is a tuple
$\mathcal{G}=(G,v_{0},\rho,\sigma_{c},u)$ where

  * •

$\left\\{1,2\right\\}$ is a set of players, player $1$ is called the leader
and player $2$ is called the follower,

  * •

$G=(V,E)$ is the directed graph on which the game is played, $V$ is the set of
nodes and $E$ is the set of directed edges,

    * –

$N\subseteq V$ denotes the set of non-leaf nodes,

    * –

$L\subseteq V$ denotes the set of leaves,

    * –

$C(v)\subseteq V$ denotes the set of children of node $v$, edges leading to
the children nodes are also termed _actions_ at node $v$,

  * •

$v_{0}\in V$ is the root node, where the game starts,

  * •

$\rho:V\to\\{1,2,c\\}$ is a function which defines which player plays in the
given node $s$, ($\rho(v)=1$ or $\rho(v)=2$), or whether the node is a chance
node ($\rho(v)=c$);

    * –

$V_{i}$ denotes the set of all states in which a player or the chance plays,
$V_{i}=\left\\{v\in V|\rho(v)=i\right\\}$

    * –

An action of the players at any given node corresponds to a child node they
choose to move. Hence the action set at a node $v$ is same as the children set
$C(v)$. $C_{i}=\bigcup_{v\in V_{i}}C(v)$ denotes the set of all actions of
player $i$ or nature,

  * •

$\sigma_{c}:V_{c}\times V\to[0,1]$ are the nature probabilities in chance
nodes, $\sigma_{c}(v,w)$ denotes the probability with which the nature moves
to $w$ starting at $v$. For each $v\in V_{c}$, $\sigma_{c}$ satisfies the
following: $\sum_{w\in C(v)}\sigma_{c}(v,w)=1$

  * •

$u=(u_{1},u_{2})$ where $u_{i}:L\to$ is the utility function of each player
$i$.

Graph structure The graph $G$ determines the horizon of the game. The game
graph is assumed to be a connected graph. If the graph is a tree or a directed
acyclic graph (DAG) then the game has finite horizon and if the graph has
directed cycles then the game has infinite horizon. The graph does not contain
self loops. The _Height_ of the game graph which is a tree or a DAG is the
maximum distance from the root node to a leaf node. We use the term _outcome_
to denote the leaf node reached at the end of the play or a probability
distribution on the set of leaf nodes reached if players mix their actions.

Histories A history $h$ at a node $v$ is a sequence of nodes visited, formally
$h=v_{0},\ldots,v_{k}$ where $v_{0}$ is the root node, $v_{k}=v$ and for
$0\leq j\leq k-1$, $v_{j+1}$ is a child of $v_{j}$. For a given history $h$,
let $v_{h}$ denote the final node in the sequence $h$. For a node $v$, let
$H_{v}$ denote the set of possible histories at $v$ and let $H=\cup_{v\in
S}H_{v}$ be the set of all histories. Let $H_{1}=\cup_{v\in S_{1}}H_{v}$ and
$H_{2}=\cup_{v\in S_{2}}H_{v}$ denote the set of histories for the leader and
the follower respectively. Any history of the form
$v_{0},\ldots,v_{k},\ldots,v_{l}$ is a continuation of of history
$v_{0},\ldots,v_{k}$. A _play_ $\pi$ is a sequence $v_{0},\ldots,v_{k}$ where
$v_{0}$ is the root node and $v_{k}$ is a leaf node, $\Pi$ is the set of all
plays.

Strategies and utilities For $i=1,2$, a history-dependent strategy for player
$i$ is defined as $\sigma_{i}:H_{i}\to\Delta(A)$ where $\sigma_{i}(h)$ denotes
a probability measure over $A$ and $\sigma_{i}(h,a)$ denotes a probability of
an action $a\in A$ at history $h$. Each $\sigma_{i}$ satisfies the equality
$\sum_{a\in A(v_{h})}\sigma_{i}(h,a)=1$. Let $\Sigma_{i}$ denotes the set of
history-dependent strategies of player $i$. A strategy profile
$\sigma=(\sigma_{1},\sigma_{2})$ is a tuple of strategies of the leader and
the follower. Let $u_{i}(\sigma)$ denote the expected utility for player $i$
according to a strategy profile $\sigma$ and $u_{i}(\sigma)(h)$ denote the
expected utility conditional on the history $h$ as been observed. A play or a
history has positive support in a strategy profile, if it is realized with
positive probability.

Strong Stackelberg equilibrium A strategy $\sigma_{2}$ is a best response to a
strategy $\sigma_{1}$ if $u_{2}(\sigma_{1},\sigma_{2})\geq
u_{2}(\sigma_{1},\sigma^{\prime}_{2})$ for all
$\sigma^{\prime}_{2}\in\Sigma_{2}$. Let ${\cal BR}(\sigma_{1})$ be the set of
all best responses to strategy $\sigma_{1}$.

###### Definition 2

A strategy profile $\sigma$ is a Strong Stackelberg equilibrium (SSE) if

$\sigma=\operatorname*{arg\,max}_{\sigma^{\prime}_{1}\in\Sigma_{1},\sigma^{\prime}_{2}\in{\cal
BR}(\sigma^{\prime}_{1})}u_{1}(\sigma^{\prime}_{1},\sigma^{\prime}_{2}).$

An important point to note here is that in a SSE, if the follower has more
than one best response to the leader’s strategy, he chooses a best response
which maximizes the utility for the leader. This implies that, although there
can be multiple SSEs, all of them provide the same utility for the leader.

$v_{0}$$v_{2}$$(0,1)$$(0,2)$$(2,0)$

$u_{2}$$u_{1}$$(2,0)$$(0,2)$$(0,1)$$(1,1)$

Figure 1: An example of an extensive form game. The leader plays in the
circular node $v_{2}$, the follower in the rectangular $v_{0}$. To the right
is the visualisation of possible outcomes in the space of utilities. The red
dashed line represents the maxmin value $\mu_{2}(v_{0})$ of the follower’s
node $v_{0}$.

###### Example 1

To demonstrate SSE in sequential games, consider the game in Fig. 1. In Nash
equilibrium, the leader always plays to $(2,0)$ in $v_{2}$. Knowing this, the
follower plays to $(0,1)$ to get better utility. In SSE, the leader has the
option to commit to playing an even mixture between the leaves $(0,2)$ and
$(2,0)$, offering both players the utility of $1$. Because the follower is
assumed to break ties in the leader’s favor, she plays to $v_{2}$. Hence, the
follower obtains better utility in the SSE.

In our results, we use a visualisation of outcomes of two player games due to
[19]. We can identify a leaf node with utilities $(u_{1},u_{2})$ with a point
in a two dimensional space. A set of all mixtures over two leaf nodes
$z_{1},z_{2}$ with utilities $(u_{1}^{1},u_{2}^{1})$ and
$(u_{1}^{2},u_{2}^{2})$ is then a line segment connecting these two points. To
illustrate this concept, refer to Fig. 1. The leader, who plays second, has
the option of mixing between two leafs with utilities $(2,0)$ and $(0,2)$,
hence the line segment. The vertical line positioned at $u_{2}=1$ represents
the follower’s maxmin value – the minimum utility the follower is willing to
accept when playing Left. ∎

###  2.1 Preliminary results

#### 2.1.1

###### Definition 3

The maxmin value at node $v$ for the follower is the worst-case utility the
follower can guarantee for himself, irrespective of the leader’s strategy.
Formally, maxmin value at node $v$ is
$\mu_{2}(v)=\max_{\sigma_{2}\in\Sigma_{2},h\in
H_{v}}\min_{\sigma_{1}\in\Sigma_{1}}u_{2}(\sigma_{1},\sigma_{2})(h)$. A
punishing strategy is a memoryless strategy of the leader which for each $v\in
V$ guarantees the payoff of at most $\mu_{2}(v)$ for the follower at node $v$.
A punishing strategy $\sigma^{p}_{1}$ satisfies
$u_{2}(\sigma^{p}_{1},\sigma_{2})(h)\leq\mu_{2}(v)$ for each
$\sigma_{2}\in\Sigma_{2}$, $v\in V$ and $h\in H_{v}$ .

The maxmin value of the follower is completely independent of the leader’s
utility. While playing the punishing strategy, the leader acts as an adversary
to the follower, disregarding their own utility. Maxmin value at any node is
does not depend on through which history that node is reached.

###### Lemma 1

For any sequential game on a graph which does not contain directed cycles, the
leader has a punishing strategy.

###### Proof

We prove the Lemma by constructing the punishing strategy for the leader in
the backward fashion. During this backward procedure, we also keep track of
the maxmin value for the follower at each node $v$.

For a leaf node $v$, clearly $\mu_{2}(v)$ is equal to the payoff the follower
obtains at the leaf $v$. Consider a node $v$ which is not a leaf. Assume that
$\mu_{2}(w)$ has been calculated for each child $w$ of $v$. If $v$ is a leader
node, then leader can choose the action which hurts the follower the most,
hence $\mu_{2}(v)=\min_{w\text{ child of }v}\mu_{2}(w)$ and the leader moves
to the node $arg\min_{w\text{ child of }v}\mu_{2}(w)$ with probability 1. If
$v$ is a follower node, then follower can minimize his punishment by moving to
a child with largest maxmin value, hence $\mu_{2}(v)=\max_{w\text{ child of
}v}\mu_{2}(w)$. ∎

###### Lemma 2

For any SSE $(\sigma_{1},\sigma_{2})$, there exists a SSE
$(\sigma_{1},\hat{\sigma_{2}})$ where $\hat{\sigma_{2}}$ is a pure strategy.

###### Proof

We will construct $\hat{\sigma_{2}}$ by modifying $\sigma_{2}$ at each history
where $\sigma_{2}$ randomizes between more than one actions. Consider an
arbitrary such history $h$, assume that at $h$, $\sigma_{2}$ plays actions
$w_{1},\ldots,w_{k}$ with positive probability. First we claim that
$u_{2}(\sigma_{1},\sigma_{2})(hw_{i})=u_{2}(\sigma_{1},\sigma_{2})(hw_{j})$
for each $i,j=1,\ldots,k$. Assume the contrary, that for some $i,j$,
$u_{2}(\sigma_{1},\sigma_{2})(hw_{i})>u_{2}(\sigma_{1},\sigma_{2})(hw_{j})$.
Then follower can obtain a strictly better payoff if he deviates from
$\sigma_{2}$ by transferring all the weight of action $w_{j}$ to action
$w_{i}$. Note that, in the profile $(\sigma_{1},\sigma_{2})$ the follower
plays both $w_{i}$ and $w_{j}$ with positive probability, so the leader can
not distinguish the strategy $\sigma_{2}$ from its deviation just by observing
the history and thus can not punish the deviation. This contradicts that
$\sigma_{2}$ is a best response to $\sigma_{2}$. So, we must have
$u_{2}(\sigma_{1},\sigma_{2})(hw_{i})=u_{2}(\sigma_{1},\sigma_{2})(hw_{j})$
for each $i,j=1,\ldots,k$. Let
$i_{0}=\operatorname*{arg\,max}_{i}\\{u_{1}(\sigma_{1},\sigma_{2})(hw_{i})\\}$
and let $\hat{\sigma_{2}}$ plays $i_{0}$ with probability 1 at $h$. Since
$u_{1}(\sigma_{1},\hat{\sigma_{2}})(h)\geq u_{1}(\sigma_{1},\sigma_{2})(h)$,
$(\sigma_{1},\hat{\sigma_{2}})$ is also a SSE. By performing the modification
of $\sigma_{2}$ at every history, we obtain a pure strategy $\hat{\sigma_{2}}$
such that $(\sigma_{1},\hat{\sigma_{2}})$ is a SSE. ∎

###### Lemma 3

Consider an outcome in which payoff vectors
$(x_{1},y_{1}),\ldots,(x_{k},y_{k})$ are realized with probabilities
$p_{1},\ldots,p_{k}$. Then there exists 2 vectors, WLG say
$(x_{1},y_{1}),(x_{2},y_{2})$ and a probability $\hat{p}$, such that the
outcome in which $(x_{1},y_{1})$ is realized with probability $\hat{p}$ and
$(x_{2},y_{2})$ is realized with probability $(p_{1}+\ldots+p_{k})-\hat{p}$ is
weakly preferred by both the players.

###### Proof

Let $p=p_{1}+\ldots+p_{k}$. We view the payoff vectors as points in
2-dimensional plane. The point
$A=p_{1}(x_{1},y_{1})+\ldots+p_{k}(x_{k},y_{k})$ is a convex combination of
the points $p(x_{1},y_{1}),\ldots,p(x_{k},y_{k})$, hence lies in the interior
or on the boundary of their convex hull. So there exists a point $B$ on the
boundary of the convex hull with same payoff for the leader and (possibly
weakly) better payoff for the follower than $A$.

$u_{2}$$u_{1}$$A$$B$

∎

###### Proposition 1

In any SSE with history-dependent strategies, the leader obtains (weakly)
better payoff than any SSE with history-independent strategies.

In Section 3 we show an example of a game in which the leader obtains strictly
better payoff in SSE with history-dependent strategies, than SSE with history-
independent strategies.

##  3 Strategy profiles with Memory

When the graph is not a tree, the number of different histories can be
exponentially large. So the history-dependent strategies can not be described
efficiently. In this section, we define a different formulation for history-
dependant strategies profiles, called _Strategy profiles with Memory_. In this
formulation, the profiles are equipped with a set of memory states which store
partial information about the past histories. Players do not make decisions
according to a complete history, but only according to a memory state. We
assume that the memory is public, that is, both the leader and the follower
observe the same memory.

###### Definition 4

A strategy profile with memory is a tuple $(\sigma,M,\mathcal{M},m_{0})$,
where

  * •

$M$ is a set of memory states

  * •

$\sigma=(\sigma_{1},\sigma_{2})$ are the strategies of players with
$\sigma_{i}:M\times V_{i}\times V\to[0,1]$ where $\sigma_{i}(m,v,w)$ denotes
the probability that player $i$ at node $v\in V_{i}$ moves to a node $w\in
C(v)$. For each $v\in V_{i}$, $\sigma_{i}$ satisfies the following:
$\sum_{w\in C(v)}\sigma_{c}(m,v,w)=1$.

  * •

$\mathcal{M}:M\times V\times V\to M$ is the memory update function, where
$\mathcal{M}(m,v,w)$ is the updated memory state if a player or nature moves
to node $w$ from node $v$ when the current memory state is $m$

  * •

$m_{0}\in M$ is the initial memory state.

If the set of memory states $M$ is equal to the set of all possible histories
$H$, then a general history-dependant strategy profile can be described using
this formulation. However, when the set $M$ is at most polynomial in size, the
strategy profiles can be described efficiently. A strategy profile with
history-independent strategies can be described by choosing $M$ to be a
singleton set.

###  3.1 Memory as a randomization device

In this subsection we discuss the use with memory as a randomization device to
obtain better expected payoff for the leader. We explain this concept using a
simple example which captures the main idea.

$v_{0}$$v_{2}$$(0,5)$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$v_{7}$$(4,0)$$(3,4)$$(2,0)$$(1,6)$$a^{2}_{u}$$a^{2}_{d}$$a^{5}_{u}$$a^{5}_{d}$$a^{5}_{d}$$a^{6}_{u}$$a^{7}_{d}$$a^{7}_{u}$$a^{1}_{r}$$a^{1}_{d}$
Figure 2: An example of a game on a DAG. The leader plays in circular nodes,
the follower plays in square nodes.

###### Example 2

Consider the game described by the graph in Fig.2, where $v_{0}$ is the root
node. The SSE with history-dependant strategies can be described as follows.
The leader wants to make the follower play $a_{r}^{1}$ in $v_{0}$, in order to
avoid obtaining utility $0$. So at node $v_{2}$, the leader must commit to a
randomized strategy in order to offer the follower utility at least $5$. If
the leaf nodes $(3,4)$ and $(1,6)$ both are reached with equal probabilities,
then the follower is guaranteed the expected payoff $5$ and the leader gets
expected payoff $2$. In order to do so, the leader plays the actions
$a_{u}^{2}$ and $a_{d}^{2}$ with equal probabilities at node $v_{2}$ and
conditions his strategy in $v_{6}$ and $v_{7}$ on whether $a^{2}_{u}$ or
$a^{2}_{d}$ was played. If $a^{2}_{u}$ was played, the leader wants to reach
the leaf $(3,4)$, and so hopes that the follower plays $a_{u}^{5}$ at $v_{5}$
and if $a^{2}_{d}$ was played, the leader wants to reach the leaf $(1,6)$, and
so hopes that the follower plays $a_{d}^{5}$ at $v_{5}$. He incentivizes the
follower to play $a_{u}^{5}$ at $v_{5}$ on observing history $a^{2}_{l}$ at
$v_{2}$, by committing $a_{u}^{6}$ at $v_{6}$ and $a_{u}^{7}$ at $v_{7}$, (so
the follower is better off playing $a_{u}^{5}$ at $v_{5}$, as the follower is
punished by with utility 0 if he plays $a^{5}_{r}$). Symmetrically, if
$a^{2}_{r}$ was played, the leader commits to playing to $(1,6)$ in $v_{7}$
and to $(4,0)$ in $v_{6}$.

The memory states for this SSE can be described as follows. The set $M$ has 3
memory states, $M=\left\\{m_{0},m_{l},m_{r}\right\\}$ where $m_{0}$ is initial
memory state.

The above analysis relies on the key fact that both the players can play
depending on the past history. Otherwise for instance, if the leader’s
strategy is history-independent, he would not be able to punish the follower.
And so in the best response, the follower plays $a_{d}^{7}$ irrespective of
history to obtain himself the utility 6 and the leader gets the utility 1.
Hence the leader obtains strictly better payoff in SSE with history-dependent
strategies, than SSE with history-independent strategies.

##  4 Algorithm for Games without Chance Nodes on a DAG

In this section, we consider the games on DAGs without chance nodes. As there
are no directed cycles, the game has finite horizon. The main result is the
construction of a polynomial time algorithm that computes a SSE where the
players use strategy profile with memory. We show that the size of memory set
is linear, thus it can be described very efficiently.

###### Theorem 4.1

In games on DAGs without chance nodes, there exists a SSE with strategy
profile with memory, where the size of memory set is linear in the number of
nodes. There exists a polynomial time algorithm which computes such a SSE.

Our algorithm consists of two parts. In the first part, the algorithm performs
an upward dynamic programming pass, which constructs for each node $v$ the
_commitment set_ , which is the set of all the outcomes to which the leader
can commit. If leader can commit to number of different outcomes, he can also
commit to any convex combination of those outcomes by choosing the appropriate
mixed strategy. Hence the commitment set is convex and infinite. As the
commitment set is infinite, it is impossible store all its points. However,
the convexity allows an efficient representation of $S_{v}$, the algorithm
stores only finitely many points whose convex hull is the commitment set. We
denote this finite set by $S_{v}$. In the upward pass, the algorithm also
constructs a function $S$, which for every node $v$ and outcome $p$ in
$S_{v}$, defines the route with which leader can commit to $p$ starting at
$v$.

In the second part, the algorithm performs a downward pass, which constructs a
commitment strategy $\sigma$ with memory for the leader, the memory update
function $\mathcal{M}$ and the set of memory states $M$. The labels
constructed in the upward pass are used to construct the commitment at each
node.

Algorithm 1 Upward Pass

1:Sort $V$ in reverse topological order

2:for $v$ in $V$ do

3: $S_{v}\leftarrow\\{\\}$

4: if $v$ is leaf node then UpwardLeaf(v)

5: else if $v$ is a leader node then UpwardLeader(v)

6: elseUpwardFollower(v)

7: end if

8:end for

9:

10:1 – Leaf nodes

11:

12:procedure UpwardLeaf($v$)

13: Add $v$ to $S_{v}$

14: $L(v,v)\leftarrow()$

15:end procedure

16:

17:2 – Leader nodes

18:

19:procedure UpwardLeader($v$)

20: for $w$ in $C(v)$ do

21: for $p$ in $S_{w}$ do

22: Add $p$ in $S_{v}$

23: $L(v,p)\leftarrow(1,w,p)$

24: end for

25: end for

26:end procedure

27:

28:3 – Follower nodes

29:

30:procedure UpwardFollower($v$)

31: for $w$ in $C(v)$ do

32: for $p$ in $S_{w}$ do

33: if $u_{2}(p)\geq i(w)$ then

34: Add $p$ to $S_{v}$

35: end if

36: $L(v,p)\leftarrow(1,w,p)$

37: end for

38: for $p_{1}$ and $p_{2}$ in $S_{w}$ do

39: if $\alpha\cdot u_{2}(p_{1})+(1-\alpha)\cdot u_{2}(p_{2})=i(w)$ for
$0<\alpha<1$ then

40: Add $p=\alpha\cdot u_{2}(p_{1})+(1-\alpha)$ to $S_{v}^{w}$

41: $L(v,p)\leftarrow(\alpha,w,p_{1},1-\alpha,w,p_{2})$

42: end if

43: end for

44: Add outcome in $S_{v}^{w}$ with highest utility for leader to $S_{v}$

45: end for

46:end procedure

Upward pass

Each outcome can be stored as a point in two-dimensional space, whose
$x$-coordinate denotes the follower’s expected utility and $y$-coordinate
denotes the leader’s expected utility (see Fig. 1). For each node $v$ and
outcome $p$ in $S_{v}$, algorithm maintains the label $L(v,p)$, which stores
the information about which mixed path from $v$ the leader can guarantee in
order to obtain the outcome $p$. Each label is stored as am ordered tuple.
This label will be used in Part 2 to create a procedure which computes the
commitment strategy for the leader. The label is stored in the form of an
ordered tuple, where an element is added for each action which is suggested
positive probability.

The upward pass starts by fixing a reverse topological order of the nodes, the
commitment sets for each node are constructed in that order. This construction
is easy for leaf nodes, since starting at a leaf node, the leader can commit
to a unique outcome. For non-leaf nodes, they are constructed using the
commitment sets already constructed for their children.

Leaf nodes:

For each leaf node $v\in L$, algorithm assigns $S_{v}=\\{v\\}$. For $v$ in
$S_{v}$, assigns an empty label $L(v,v)=()$.

Leader nodes:

Consider a leader node $v$, a child node $w\in C(v)$ and an outcome $p\in
S_{w}$, so leader can commit to the outcome $p$ starting at $w$. Then leader
can also commit to $p$ from $v$, by simply committing to go to $w$ at $v$.
Hence, for each $p\in S_{w}$, we have $p\in S_{v}$. For each $p\in S_{w}$, the
algorithm assigns $L(v,p)=(1,w,p)$ The label $(1,w,p)$ for committing to
outcome $p$ starting at $v$ can be read as an instruction as follows: First
commit at $v$ to $w$ with probability 1 and then commit to outcome $p$
starting at $w$ using the label $L(w,p)$. Such a label is called a pure label.

Leader can also commit by playing a mixed action at $v$. By Lemma 3 for
purpose of computing a SSE, it is sufficient to only consider the outcomes
obtained by mixing over at most two children. Consider children
$w_{1},w_{2}\in C(v)$ and outcomes $p_{1}\in S_{w_{1}}$, $p_{2}\in S_{w_{2}}$.
Then leader by committing to $w_{1}$ and $w_{2}$ with appropriate
probabilities can also commit to any outcome which is convex combination of
$p_{1}$ and $p_{2}$. However since $p_{1},p_{2}$ are already in $S_{v}$, and
the algorithm stores only the extreme points of the convex set $S_{v}$, the
algorithm does not store the convex combinations of $p_{1}$ and $p_{2}$.
Hence, $S_{v}=\Big{(}\cup_{w\text{ child of }v}S_{w}\Big{)}$.

Follower nodes: The case with follower nodes is bit more complicated for the
following reason. Consider a follower node $v$, a child node $w\in C(v)$ and
an outcome $p\in S_{w}$, so leader can commit to the outcome $p$ starting at
$w$. Then it is not necessarily true that leader can also commit to $p$ from
$v$. In fact, the leader can commit to $p$ from $v$, if and only if the
follower has an incentive to go to $w$ from $v$. To prevent the follower from
going to node $w^{\prime}$ instead of $w$, the leader can commit at
$w^{\prime}$ to the outcome in $S_{w^{\prime}}$ which gives the follower least
utility. If $u_{2}(p)\geq\min_{p^{\prime}\in S_{w^{\prime}}}u_{2}(p^{\prime})$
then the follower obtains higher expected utility by going to $w$ at which the
leader commits to $p$, than going to $w^{\prime}$ at which the leader commits
to $\operatorname*{arg\,min}_{p^{\prime}\in S_{w^{\prime}}}u_{2}(p^{\prime})$.
So the follower has no incentive to prefer $w^{\prime}$ over $w$. Denote the
quantity $i(w)=\max_{w^{\prime}\neq w}\min_{p^{\prime}\in
S_{w^{\prime}}}u_{2}(p^{\prime})$ where $w^{\prime}\in C(v)$. Hence the
algorithm adds $p$ in $S_{v}$ if $u_{2}(p)\geq i(w)$. The label $L(v,p)$ is
defined as $L(v,p)=(1,w,p)$.

Now consider two arbitrary outcomes $p_{1},p_{2}$ in $S_{w}$ such that
$u_{2}(p_{1})\geq i(w)$ and $u_{2}(p_{2})<i(w)$. Then there exists an
$\alpha\in(0,1]$ such that $p=\alpha p_{1}+(1-\alpha)p_{2}$ and
$u_{2}(p)=i(w)$. In this case, the leader is not able to commit to $p_{2}$,
but he is able to commit to $p$ by first committing to $w$ and then at $w$,
committing to outcome $p_{1}$ with probability $\alpha$ and to outcome $p_{2}$
with probability $1-\alpha$. Let $S_{v}^{w}$ a set of such outcomes $p$. Note
that for any $p,p^{\prime}\in S_{v}^{w}$, $u_{2}(p)=u_{2}(p^{\prime})$. The
algorithm adds for each $w\in C(v)$, one outcome in $S_{v}^{w}$ (provided
$S_{v}^{w}$ is not empty) which has the maximum utility for the leader (in
case of multiple outcomes with same utility for the leader, one outcome is
arbitrarily chosen).

If $p\in S_{v}^{w}$ is added to $S_{v}$, the label $L(v,p)$ is defined as
$L(v,p)=(\alpha,w,p_{1},1-\alpha,w,p_{2})$. The label
$(\alpha,w,p_{1},1-\alpha,w,p_{2})$ for committing to the outcome $p$ starting
at $v$ can be read as an instruction as follows: With probability $\alpha$
commit at $v$ to $w$ and then commit to outcome $p_{1}$ starting at $w$ using
the label $L(w,p_{1})$ and with probability $1-\alpha$ commit at $v$ to $w$
and then commit to outcome $p_{2}$ starting at $w$ using the label
$L(w,p_{2})$. Such a label is called a mixed label.

Solution:

After constructing the commitment sets for all the nodes, the algorithm
computes the outcome in $S_{v_{0}}$ with maximum $y$-coordinate (recall that
$v_{0}$ is the initial node). This is the outcome the leader can commit
starting from $s_{0}$ which gives him the maximum expected utility. Formally,
$p^{*}=\operatorname*{arg\,max}_{p\in S_{v_{0}}}u_{1}(p)$. ∎

Downward pass

During the downward pass, the algorithm constructs the commitment strategy
$\sigma$ of the leader, the set of memory states $M$ and the memory update
function $\mathcal{M}$. The procedure $\textsc{Strategy}(v,p,m)$ at a node $v$
with a target outcome $p$ and current memory state $m$ performs the following
3 steps,

  1. 1.

Memory update: After a player moves to a node $w$ from $v$ on observing the
memory $m$, this step updates the memory state to a new state denoted by
$\mathcal{M}(m,v,w)$.

  2. 2.

Commitment of the leader: If $v$ is a leader node, this step construct a
(possibly) mixed actions at $v$ for committing to the target outcome $p$. If
$v$ is a follower node, then this step is skipped.

  3. 3.

Next target outcome: After moving to a node $w$ from $v$, this step chooses
the target outcome to commit from $w$.

The algorithm starts by performing the $\textsc{Strategy}(v_{0},p^{*},m_{0})$
where $m_{0}$ is an initial memory state denoting the empty memory. After
finishing the 3 steps of $\textsc{Strategy}(v,p,m)$ for some a given $v,p,m$,
the algorithm continues by performing
$\textsc{Strategy}(w,p^{\prime},\mathcal{M}(m,v,w))$ for each $w\in C(v)$
obtained in the Step 2 and the corresponding next target outcome $p^{\prime}$
obtained in the Step 3. The downward pass is finished when a leaf node is
reached. We now describe in detail these 3 steps for specific $v,p,m$.

Algorithm 2 Downward Pass

1:$v\leftarrow v_{0}$ $\triangleright$ $v_{0}$ is the root node

2:$p\leftarrow p^{*}$ $\triangleright$ $p^{*}$ is outcome in $S_{v_{0}}$ with
highest utility for leader

3:Construct $G_{v_{0},p^{*}}$ $\triangleright$ $G_{v_{0},p^{*}}$ is mixed path
graph constructed using $L(v_{0},p^{*})$

4:$m\leftarrow m_{0}$ $\triangleright$ $m_{0}$ is initial memory constructed
using $G_{v_{0},p^{*}}$, details are in the proof

5:Strategy($v_{0},p^{*},m_{0}$)

6:

7:1 – Procedure Strategy

8:

9:procedure Strategy($v,p,m$)

10: while $v$ is not leaf node do

11: $v^{\prime},p,^{\prime},m^{\prime}\leftarrow\textsc{NewTarget($v,p,m$)}$

12: Strategy($v^{\prime},p^{\prime},m^{\prime}$)

13: end while

14:end procedure

15:

16:2 – Memory update function

17:

18:procedure MemoryUpdate($v,p,m$)

19: if $m=R$ then return $R$

20: end if

21: if $v$ is leader node then

22: if Leader constructs randomization device then

23: return $m^{\prime}$ $\triangleright$ The details of randomization device
and $m^{\prime}$ are in the proof

24: elsereturn $m$

25: end if

26: else

27: if $(v,w)$ is in $m$ and follower does not play to $w$ then return $R$

28: elsereturn $m$

29: end if

30: end if

31:end procedure

32:

33:3 – Commitment strategy for the leader

34:

35:procedure Commitment($v,p,m$)

36: if $v$ is follower node then return

37: end if

38: if $m=R$ then

39: Commit to a punishing strategy

40: return $(v^{\prime},p^{\prime})$ $\triangleright$ $v^{\prime},p^{\prime}$
are the node and outcome suggested by the punishing strategy

41: else

42: if L(v,p) = (1,w,p) then

43: Commit to $w$ Return $(w,p)$

44: end if

45: end if

46:end procedure

47:

48:4 – New target node and outcome

49:

50:procedure NewTarget($v,p,m$)

51: if $v$ is leader node then

52: $(w,p)\leftarrow\textsc{Commitment($v,p,m$)}$

53: return $(w,p,\textsc{MemoryUpdate($v,p,m$)})$

54: else

55: if MemoryUpdate($v,p,m$) = R then

56: return $(v,^{\prime}p^{\prime},R)$ $\triangleright$
$v^{\prime},p^{\prime}$ are the node and outcome suggested by the punishing
strategy

57: else if $L(v,p)=(1,w,p)$ then

58: return $(w,p,m)$

59: else if $L(v,p)=(\alpha,w,p_{1},1-\alpha,w,p_{2})$ then

60: return $(w,p_{1},m)$ with probability $\alpha$ and return $(w,p_{2},m)$
with probability $1-\alpha$

61: end if

62: end if

63:end procedure

Memory update:

We shall first define some terminology that we need to construct the memory
update function. Set of memory states $M$ is initialized to an empty set. Each
time the procedure $strategy$ is performed, if a new memory state is created,
it is added to $M$. Each memory state within the set $M$ is again stored as a
set. Every memory state contains encoded information of two types: (1) Move
suggestion (m): This type of memory recommends the follower to take a specific
action. For instance, if $(v,w)$ is an element of a memory state $m$, then
follower at node $v$ is recommended to move to node $w$ on observing memory
$m$. (2) Red flag (R): This memory informs the leader if the follower has not
obeyed the recommendation in the past. There is a unique memory state of this
kind. The leader is recommended to use a punishing strategy on observing the
memory $R$.

A mixed path $G_{v,p}$ corresponding to a node $v$ and an outcome $p$ is a
graph which imitates the recommendations of the label $L(v,p)$. $G_{v,p}$ can
be constructed using $L(v,p)$ as follows. $G_{v,p}$ is initialized as an empty
graph with same set of nodes as the original graph. The operation
$addedge(w,p^{\prime})$ adds an edge from $w$ to $w^{\prime}$ where
$L(w,p^{\prime})=(1,w^{\prime},p^{\prime})$ or
$L(w,p^{\prime})=(\alpha,w^{\prime},p_{1},1-\alpha,w^{\prime},p_{2})$. Edges
are sequentially added in $G_{v,p}$ starting by performing $addedge(v,p)$. For
any $w,p^{\prime}$ if $addedge(w,p^{\prime})$ is performed, then if
$L(w,p^{\prime})=(1,w^{\prime},p^{\prime})$ then $addedge(w,p^{\prime})$ is
also performed, and if
$L(w,p^{\prime})=(\alpha,w^{\prime},p_{1},1-\alpha,w^{\prime},p_{2})$ then
$addedge(w^{\prime},p_{1})$ and $addedge(w^{\prime},p_{2})$ are also
performed. Edge duplication is not allowed.

A node $w$ is _visited_ in the mixed path $G_{v,p}$ if there is edge in
$G_{v,p}$ incoming to $w$. Let $successors(v,p)$ be the set of all nodes that
are visited in $G_{v,p}$. We say that a label $L(w,p^{\prime})$ is contained
in label $L(v,p)$ if the mixed path $G_{w,p^{\prime}}$ is a subgraph of
$G_{v,p}$. $G_{v,p}$ _converges_ (or _diverges_) at node $w$ if $w$ has more
than 2 incoming (or outgoing) edges in $G_{v,p}$. Two mixed paths $G_{v,p}$
and $G_{v^{\prime},p^{\prime}}$ _converge_ (or _diverge_) at node $w$ if $w$
has at least one incoming (or outgoing) edge in both the $G_{v,p}$ and
$G_{v^{\prime},p^{\prime}}$. The memory state at the root node denoted by
$m_{0}$ is constructed using the mixed path $G_{v_{0},p^{*}}$. $m_{0}$ is
initialized as an empty set. For every follower node $v$ at which
$G_{v_{0},p^{*}}$ does not diverge, add $(v,w)$ to $m_{0}$ where $(v,w)$ is
the unique edge outgoing from $v$ in $G_{v_{0},p^{*}}$. The memory state
$m_{0}$ is added to $M$.

Firstly $\mathcal{M}(R,v,w)=R$ for any node $v$ and $w\in C(v)$, that is, if
the follower does not obey the recommendations at some node, this Red flag
memory does not change till the end. Consider a follower node $v$. When the
memory $m$ contains an element $(v,w)$ for some $w\in C(v)$, if follower moves
$w$, then $\mathcal{M}(m,v,w^{\prime})=m$ and if follower moves to
$w^{\prime}\in C(v)$ other than $w$, then $\mathcal{M}(m,v,w^{\prime})=R$.
When $m$ does not contain an element $(v,w)$ for any $w\in C(v)$, then
$\mathcal{M}(m,v,w)=m$ for any $w\in C(v)$.

Construction of memory update function for the leader nodes is bit more
complicated, as it depends on the mixed labels of past follower nodes.
Consider a leader node $v$, then $\mathcal{M}(m,v,w)$ returns a new memory
state only in the following scenario. Let there be a follower node
$v^{\prime}$ visited in $G_{v_{0},p^{*}}$ with mixed label
$L(v^{\prime},p)=(\alpha,w^{\prime},p_{1},1-\alpha,w^{\prime},p_{2})$ such
that as the mixed paths $G_{w,p_{1}}$ and $G_{w,p_{2}}$ traverse down the
graph, diverge for the first time at the leader node $v$, say to $w_{1}$ and
$w_{2}$ respectively where $w_{1},w_{2}\in C(v)$. If there is a follower node
$w^{\prime}$ in $successors(w_{1},p_{1})\cap successors(w_{2},p_{2})$ and the
mixed paths $G_{w,p_{1}}$ and $G_{w,p_{2}}$ diverge again at $w^{\prime}$, say
$G_{w,p_{1}}$ goes to $w^{\prime}_{1}$ and $G_{w,p_{2}}$ goes to
$w^{\prime}_{2}$ (where $w^{\prime}_{1},w^{\prime}_{2}\in C(w^{\prime})$),
then algorithm creates two new memory states $m_{w_{1}}$ and $m_{w_{2}}$.
Initialize $m_{w_{1}}=m_{w_{2}}=m$. For every such $w^{\prime}$ satisfying the
above, add $(w^{\prime},w^{\prime}_{1})$ to $m_{w_{1}}$ and
$(w^{\prime},w^{\prime}_{2})$ to $m_{w_{2}}$. Finally
$\mathcal{M}(m,v,w_{1})=m_{w_{1}}$ and $\mathcal{M}(m,v,w_{2})=m_{w_{2}}$,
$m_{w_{1}}$ and $m_{w_{2}}$ are added to $M$. For every other $w"\in C(v)$
other than $w_{1},w_{2}$, $\mathcal{M}(m,v,w")=m$ If either of the above
conditions are not met, then $\mathcal{M}(m,v,w")=m$ for each $w"\in C(v)$.

Commitment of the leader: If the memory $m_{v}=R$ at any leader node $v$, then
the algorithm commits to a punishing strategy for the leader at node $v$ for
the reminder of the game. If $m_{v}\neq R$, then the commitment depends on the
label $L(v,p)$. If $L(v,p)=(1,w,p)$ for some $w\in C(v)$, then the leader
should simply commit to $w$ with probability 1.

Note that the label $L(v,p)$ for any leader node $v$ and for any outcome $p$
is always a pure label, so the leader is committed to play pure action
conditional on the fact that the label $L(v,p)$ is reached. However when the
labels $L(v,p)=(1,w,p)$ are $L(v,p^{\prime})=(1,w^{\prime},p^{\prime})$ are
both reached reached with positive probabilities $\alpha$ and $1-\alpha$
respectively for $w^{\prime}$ different from $w$, then the leader should be
committed to a $w$ with probability $\alpha$ and to $w^{\prime}$ with
probability $1-\alpha$.

Next target outcome: Consider a node $v$ with target outcome $p$ and memory
$m_{v}$. If $L(v,p)=(1,w,p)$, then in the next step
$\textsc{Strategy}(w,p,\mathcal{M}(m,v,w))$ is performed. If
$L(v,p)=(\alpha,w,p_{1},1-\alpha,w,p_{2})$, then
$\textsc{Strategy}(v,p_{1},m_{v})$ and $\textsc{Strategy}(v,p_{2},m_{v})$ are
performed, with probabilities $\alpha$ and $1-\alpha$ respectively. ∎

Runtime Analysis

We start by bounding the size of $S_{v}$ for each $v$. Each outcome in $S_{v}$
is either picked up from $S_{w}$ for some $w\in C(v)$, or it is newly created
while constructing $S_{v}$. The new outcomes are created in two ways. Firstly
an outcome can be generated directly a leaf node, number of such outcomes is
bounded by the number of leaves, that is $|L|$. Secondly an outcome can be
created by a mixture of two outcomes in $S_{w}$ for some $w\in C(v)$. Since at
most one such outcome can be created for any $w\in C(v)$, the number of
outcomes of second type can be bounded by $|C(v)|$. So for any node $v$,
$|S_{v}|$ is bounded by $|V|+|L|$ or simply by $2|V|$.

During the upward pass, to construct $S_{v}$ for node the algorithm needs to
deal each pair of outcomes in $S_{w}$ for each $w\in S_{v}$. Thus for each
pair of $v$ and $w\in C(v)$ we need to compute the value $i(w)$ (which takes
$O(|C(v)||V|)$ operations) and for each pair of outcomes we need to decide
whether a new outcome should be created (which takes $O(|S_{w}|^{2})$
operations). Hence for each pair of $v,w$, we need $O(|V|^{2})$ operations. So
the upward pass needs $O(|V|^{4})$ operations. Choosing the outcome optimal
for the leader takes $|S_{v_{0}}|=O(|V|)$ operations.

During the downward pass, for any $v$ and $p$, mixed path $G_{v,p}$ can be
constructed in $O(|V|^{2})$ operations, since each node and edge in the graph
is traversed at most once. Construction of $m_{0}$ requires $O(|V|^{2})$
operations. While performing the procedure $\textsc{Strategy}(v,p,m)$ if the
$v$ is a follower node, then $\textsc{MemoryUpdate}(v,p,m)$ is performs $O(1)$
operations. When $v$ is a leader node, whether a randomization device should
be created can be checked in $O(|V|^{3})$ operations. Since at most constant
number of memory states are created corresponding to each node, the size of
set of memory states is $O(|V|)$. Commitment at each leader node takes $O(1)$
operations and next target node and outcome can also be determined in $O(1)$
operations. Since Strategy is performed at most $O(|V|)$ times, the downward
pass takes $O(|V|^{5})$ operations.

###### Example 3

$v_{0}$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$v_{7}$$(3,4)\hskip
5.69054pt\bf{l_{1}}$$(4,0)\hskip 5.69054pt\bf{l_{2}}$$(2,0)\hskip
5.69054pt\bf{l_{3}}$$(1,6)\hskip 5.69054pt\bf{l_{4}}$$(0,5)\hskip
5.69054pt\bf{l_{5}}$$a^{2}_{u}$$a^{2}_{d}$$a^{5}_{u}$$a^{5}_{d}$$a^{5}_{d}$$a^{6}_{u}$$a^{7}_{d}$$a^{7}_{u}$$a^{1}_{r}$$a^{1}_{d}$
Figure 3: An example of a game on a DAG. The leader plays in circular nodes,
the follower plays in square nodes.

We will revisit the example from Section 3 to demonstrate how our algorithm
works. In the upward pass, the algorithm computes the sets $S_{v}$ for each
node $v$ in a bottom up manner. The algorithm starts with leaf nodes:
$S_{l_{i}}=\\{l_{i}\\}$ and $L(l_{i},l_{i})=()$ for $i=1,2,3,4,5$. At the
leader node $v_{6}$, leader can commit to both $l_{1}$ and $l_{2}$, so
$S_{v_{6}}=\\{l_{1},l_{2}\\}$ and $L(v_{6},l_{1})=(1,l_{1},l_{1})$ and
$L(v_{6},l_{2})=(1,l_{2},l_{2})$. Similarly, $S_{v_{7}}=\\{l_{3},l_{4}\\}$. At
the follower node $v_{5}$, the algorithm checks all the outcomes in
$S_{v_{6}}$ and $S_{v_{7}}$. Firstly to check whether $l_{1}$ should be added
to $S_{v_{5}}$, the algorithm computes the quantities $u_{2}(l_{1})=4$ and
$i(v_{6})=\max_{w^{\prime}\in C(v_{5}),w^{\prime}\neq
v_{6}}\min_{p^{\prime}\in S_{w^{\prime}}}u_{2}(p^{\prime})=u_{2}(l_{3})=0$.
Since $u_{2}(l_{1})\geq i(v_{6})$, $l_{1}$ is added to $S_{v_{5}}$. As
$u_{2}(l_{2})=0\geq i(v_{6})$, $l_{2}$ is also added to $S_{v_{5}}$. With
similar reasoning, $l_{3}$ and $l_{4}$ are also added to $S_{v_{5}}$. Hence
$S_{v_{5}}=\\{l_{1},l_{2},l_{3},l_{4}\\}$. Labels at $v_{5}$ are defined as
$L(v_{5},l_{1})=(1,v_{6},l_{1})$, $L(v_{5},l_{2})=(1,v_{6},l_{2})$,
$L(v_{5},l_{3})=(1,v_{7},l_{3})$ and $L(v_{5},l_{4})=(1,v_{7},l_{4})$.
Continuing upwards, the sets
$S_{v_{3}}=S_{v_{4}}=S_{v_{2}}=\\{l_{1},l_{2},l_{3},l_{4}\\}$ are constructed.

Now consider the follower node $v_{0}$, which is also a root node. Since the
follower can go to leaf node $v_{5}$ and obtain utility 5, we have
$i(v_{2})=5$. Since $u_{2}(l_{1}),u_{2}(l_{2}),u_{2}(l_{3})<i(v_{2})$, the
outcomes $l_{1},l_{2},l_{3}$ are not added to $S_{v_{0}}$, and since
$u_{2}(l_{4})\geq i(v_{2})$, $l_{4}$ is added to $S_{v_{0}}$. Also $l_{5}$ is
added to $S_{v_{0}}$ since $5=u_{2}(l_{1})\geq i(l_{5})=u_{2}(l_{2})=0$.
Finally, all the pairs of leaves are considered to check if any mixed outcome
should be added to $S_{v_{0}}$. It can be seen that since
$u_{2}(\frac{1}{2}(l_{1})+\frac{1}{2}(l_{4}))=5=i(v_{2})$, outcome
$\frac{1}{2}(l_{1})+\frac{1}{2}(l_{4})$ is added to $S_{v_{0}}$. Similarly,
the outcomes $\frac{1}{6}(l_{2})+\frac{5}{6}(l_{4})$ and
$\frac{1}{6}(l_{3})+\frac{5}{6}(l_{4})$ are added to $S_{v_{0}}$. Hence,
$S_{v_{0}}=\\{l_{4},l_{5},\frac{1}{2}(l_{1})+\frac{1}{2}(l_{4}),\frac{1}{6}(l_{2})+\frac{5}{6}(l_{4}),\frac{1}{6}(l_{3})+\frac{5}{6}(l_{4})\\}$.
Finally the outcome $p^{*}=\frac{1}{2}(l_{1})+\frac{1}{2}(l_{4})$ is chosen
since the leader obtains largest expected utility for this outcome among all
the outcomes in the convex hull of $S_{v_{0}}$. Since $p^{*}$ is newly created
by mixing two different outcomes, the label would be a mixed label and defined
as $L(v_{0},p^{*})=(\frac{1}{2},v_{2},l_{1},\frac{1}{2},v_{2},l_{4})$. Labels
for the other outcomes are defined similarly. This completes the upward pass.

The downward pass begins with the construction of the mixed path
$G_{v_{0},p^{*}}$ where $p^{*}=\frac{1}{2}(l_{1})+\frac{1}{2}(l_{4})$. Using
the labels defined in the upward pass, the edges $(v_{0},v_{2})$,
$(v_{2},v_{3})$, $(v_{2},v_{4})$, $(v_{3},v_{5})$, $(v_{4},v_{5})$,
$(v_{5},v_{6})$, $(v_{5},v_{7})$, $(v_{6},l_{1})$, $(v_{6},l_{2})$,
$(v_{6},l_{3})$, $(v_{6},l_{4})$ are added. Initial memory
$m_{0}=\\{(v_{0},v_{2}),(v3,v_{5}),(v_{4},v_{5})\\}$ is also constructed,
since there is a unique outgoing edge in $G_{v_{0},p^{*}}$ from the follower
nodes $v_{0},v_{3}$ and $v_{4}$.

Procedure Strategy($v_{0},p^{*},m_{0}$) is performed. As $(v_{0},v_{2})\in
m_{0}$, if follower moves to $l_{5}$, memory is updated to $R$. If follower
moves to $v_{2}$, then memory is not changed and since
$L(v_{0},p^{*})=(\frac{1}{2},v_{2},l_{1},\frac{1}{2},v_{2},l_{4})$, procedures
Strategy($v_{2},l_{1},m_{0}$) and Strategy($v_{2},l_{4},m_{0}$) are performed
with probability $\frac{1}{2}$ each. While performing
Strategy($v_{2},l_{1},m_{0}$), since $L(v_{2},l_{1})=(1,v_{3},l_{1})$, leader
commits to $v_{3}$ with probability 1 and a new memory state $m_{3}$ is
created and defined as $m_{3}=m_{0}\cup\\{v_{5},v_{6}\\}$. This acts as a
suggestion to follower to move to $v_{6}$ after node $v_{5}$. Whereas after
performing Strategy($v_{2},l_{4},m_{0}$), since
$L(v_{2},l_{1})=(1,v_{4},l_{4})$, leader commits to $v_{4}$ with probability 1
and a new memory state $m_{4}$ is created and defined as
$m_{4}=m_{0}\cup\\{v_{5},v_{7}\\}$. The node $v_{5}$ is reached in two ways,
with probability $\frac{1}{2}$ via $v_{3}$ and has memory state $m_{3}$ and
with probability $\frac{1}{2}$ via $v_{4}$ and has memory state $m_{4}$. On
observing $m_{3}$ if follower moves to $v_{7}$, memory state is changed to $R$
since $(v_{5},v_{6})\in m_{3}$. In this case the leader plays a punishing
strategy, that is moves to $l_{3}$ so that the follower gets 0. On observing
$m_{3}$ if follower moves to $v_{6}$, memory state is not changed and
Strategy($v_{6},l_{1},m_{3}$) is performed. Similarly on observing memory
$m_{4}$ if follower moves to $v_{6}$. leader plays punishing strategy and if
follower moves to $m_{7}$, Strategy($v_{7},l_{4},m_{4}$) is performed.

##  5 Algorithm for Games Without Chance Nodes on Directed Graphs

In this section, we consider the games on DGs without chance nodes. When there
are directed cycles, the game has infinite horizon. The players still receive
utility only after a leaf node is reached. Due to the existence of directed
cycles, players can move indefinitely without ever reaching a leaf node. Since
we assume that infinite play gives zero payoff to both the players, it might
be beneficial for players to move along a cycle indefinitely, if the terminal
payoffs are negative.

$v_{0}$$v_{2}$$v_{3}$$v_{4}$$(1,-2)$$(-2,1)$ Figure 4: Here in the unique SSE
game is played indefinitely and both players receive zero.

###### Example 4

The Fig. 4 shows an example of a game containing directed cycle where some of
the entries in terminal payoff are negative. In this game, there is a unique
SSE in which the players move indefinitely in the cycle with nodes
$v_{2},v_{3}$ and $v_{4}$ and none of the leaf is ever reached. $\diamond$

To avoid scenarios like in Example 4, we assume in the rest of the sections
that all the terminal payoffs for both the players are non-negative.

$v_{0}$$v_{2}$$v_{3}$$(0,5)$$v_{4}$$v_{5}$$v_{6}$$(4,0)$$(3,4)$$(2,0)$$(1,6)$$a^{5}_{l}$$a^{5}_{r}$
Figure 5: An example of a game on a DG. In SSE, the nodes $v_{2}$ and $v_{3}$
are visited twice.

###### Example 5

Fig. 5 describes an example of a game which is small variant of the one
described by Fig.2. In this game any optimal commitment strategy of the leader
ensures that the states $v_{2}$ and $v_{3}$ are visited more than once with
positive probability. Like in Fig.2, the leader can obtain the payoff 2 if
after state $v_{4}$, the states $v_{5}$ and $v_{6}$ are reached with equal
probabilities. This can be achieved by creating a randomization device. For
instance suppose, on the first visit at $v_{3}$ the leader goes to $v_{4}$ and
$v_{2}$ with equal probabilities, and on second visit at $v_{3}$, the leader
goes to $v_{4}$ with probability 1. Now, the leader can commit at nodes
$v_{5}$ and $v_{6}$ so as to ‘recommend’ the follower that at node $v_{4}$ he
must go to $v_{5}$ if in his observed history $v_{3}$ was visited only once
and to $v_{6}$ if in his observed history $v_{3}$ was visited twice. Since the
leader also observes the same history, he can punish the follower by going to
$(4,0)$ after $v_{6}$ and going to $(2,0)$ after $v_{7}$ if the follower does
not follow the recommendation, thus giving the follower a strict incentive to
follow the leader’s recommendation. $\diamond$

$v_{0}$$(0,5.5)$$v_{2}$$v_{3}$$v_{4}$$v_{5}$$v_{6}$$v_{7}$$(4,0)$$(3,4)$$(2,0)$$(1,6)$$v_{8}$$v_{9}$$v_{10}$$(3,1)$$(2,5)$$(1,1)$$(0,7)$
Figure 6: Another example of a game on a DG. In SSE, the nodes $v_{2}$,
$v_{3}$ and $v_{4}$ are visited twice.

###### Example 6

The Fig. 6 shows an example similar to the Example 5. In any SSE in which the
outcomes (3,4), (1,6), (2,5), (0,7) are achieved with equal probabilities,
hence the expected payoff vector is (1.5,5.5). We can describe the strategy of
the leader in one such SSE as follows. On the first visit at $v_{3}$, the
leader plays $v_{5}$ with probability $\frac{1}{4}$ and $v_{4}$ with
probability $\frac{3}{4}$. On the first visit at $v_{4}$, he plays $v_{8}$
with probability $\frac{1}{3}$ and $v_{4}$ with probability $\frac{2}{3}$. On
the second visit at $v_{3}$, the leader plays $v_{5}$ with probability
$\frac{1}{2}$ and $v_{4}$ with probability $\frac{1}{2}$. On the first visit
at $v_{4}$, he plays $v_{8}$ with probability 1. At $v_{5}$, the follower is
incentivized to play $v_{6}$ if in the history visited $v_{3}$ only once, and
to play $v_{7}$ if in the history visited $v_{3}$ twice. Similarly at $v_{8}$,
the follower is incentivized to play $v_{9}$ if in the history visited $v_{4}$
only once, and to play $v_{10}$ if in the history visited $v_{4}$ twice. This
incentivization is achieved by using punishing strategies. $\diamond$

When the graph has with directed cycles, there are two main issues which make
the computation of a SSE more difficult compared to the case with DAGs.
Firstly, due to the existence of directed cycles there does not exist a
reverse topological order of the nodes, and so, straightforward dynamic
programming techniques do not work. Secondly, as discussed in examples 5 and
6, there are games in which in any SSE, one or more nodes are visited more
than once with positive probability. The outcomes to which leader can commit
starting at a node by visiting certain nodes more than once, might not be
included in the commitment set of that node which is obtained by a single
iteration of the upward pass identical to that of Section 4. So unlike in the
case of of DAGs, a single iteration of an upward pass may not sufficient to
accurately construct the commitment sets.

The first issue can be solved relatively easily by decomposing the graph into
strongly connected components (SCCs) and dealing with the SCCs as a whole by
fixing a reverse topological order on SCCs. In order to circumvent the second
issue, we show (Proposition 2) that there exists a SSE in which each node is
visited at most 2 times. So, we can modify the algorithm from section 4 such
that upward pass is performed twice followed by the exact same downward pass.
This allows us to use Theorem 4.1 and Proposition 2 to construct a polynomial
time algorithm that computes a SSE where the players use strategy profile with
memory.

The main intuition for Proposition 2 is as follows. Since the players do not
receive any payoff before a leaf is reached, their final payoff only depends
on the terminal node, and not on the exact path taken. However by following
certain paths with positive probability, the leader the leader can incentivize
the actions of the follower so that the desired leaf nodes are reached with
positive probability. On certain paths, a node may need to be visited more
than once, so that two different possible histories at that node. Leader can
use this fact to create a randomization device. On the other hand, visiting a
node more than two times does not help the leader any way to obtain better
outcomes.

###### Proposition 2

In any game on DG without chance nodes, there exists a SSE in which each node
is visited at most two times, in any path with positive probability.

###### Proof

We first partition the graph $G$ into strongly connected components (SCC).
Note that, every leaf node in $G$ forms their own singleton SCC. We construct
a directed graph $G_{SCC}$ as follows. For each SCC $C$ in $G$, there is a
corresponding vertex $C$ in $G_{SCC}$. $C^{\prime}$ is a child of $C$ (and $C$
is a parent of $C^{\prime}$) in $G_{SCC}$ if there exists an edge in $G$ from
a vertex in $C$ to a vertex in $C^{\prime}$ (we do not allow self loops and
multiple edges in $G_{SCC}$). $C^{\prime}$ is a successor of $C$ in $G_{SCC}$
if there exists a sequence $C=C_{1},\ldots,C_{k}=C^{\prime}$ such that
$C_{i+1}$ is a child of $C_{i}$ for $i=1,\ldots,k-1$ in . By construction,
$G_{SCC}$ is a DAG. Fix a reverse topological order on SCCs.

Let $(\sigma_{1},\sigma_{2})$ be a SSE and we assume that $\sigma_{2}$ is a
pure strategy (this assumptions is without loss of generality due to Lemma 2).
We will modify $\sigma_{1}$ to construct a new strategy $\hat{\sigma_{1}}$
such that $(\hat{\sigma_{1}},\sigma_{2})$ is also a SSE and each node is
visited at most twice. We initialize $\hat{\sigma_{1}}(h)=\sigma_{1}(h)$ for
each $h\in H$, in each step we will modify $\hat{\sigma_{1}}$ at a single SCC,
according the reverse topological order.

Every time we modify $\hat{\sigma_{1}}$ at a SCC, we show that $\sigma_{2}$ is
still the best response to the modified $\hat{\sigma_{1}}$, and hence modified
$(\hat{\sigma_{1}},\sigma_{2})$ continues to be a SSE.

Now we will explain how to modify $\hat{\sigma_{1}}$ at a fixed SCC $C$. To
avoid confusion, we use notations $\sigma^{\prime}_{1}$ and
$\sigma^{\prime\prime}_{1}$ respectively, to denote the strategy
$\hat{\sigma_{1}}$ just before its modification in $C$ and just after its
modification in $C$.

Note that once a play exits from a SCC $C$, it can never enter $C$ again. Let
$H_{C}$ denote the set of histories which enter $C$ for the first time, in
other words, the set of histories of the form $v_{0},\ldots,v_{k}$ such that
$v_{k}$ is in $C$ and $v_{i}$ for $i<k$ is not in $C$. For $h\in H_{C}$, let
$\Pi^{h}$ denote the set of plays which are continuations of $h$. Let
$H_{C}^{h}$ denote the set of histories which are continuations of $h$ and end
at a vertex in $C$, in other words, the set of continuations of $h$ of the
form $v_{0},\ldots,v_{k}$ such that $v_{k}$ is in $C$. Similarly let
$E_{C}^{h}$ denote the set of histories, which are continuations of $h$ and
exit $C$ for the first time, in other words, the set of continuations of $h$
of the form $v_{0},\ldots,v_{k}$ such that $v_{k-1}$ is in $C$ and $v_{k}$ is
not in $C$.

Fix a history $h\in H_{C}$ and let $v_{h}\in C$ be the final node of $h$. We
now will define the behaviour of $\sigma^{\prime\prime}_{1}$ at every history
in $H_{C}^{h}$, so that in any play in $\Pi^{h}$ with positive support in
$(\sigma^{\prime\prime}_{1},\sigma_{2})$, each node in $C$ is visited at most
twice. If every $h^{\prime}\in H_{C}^{h}$ with positive support in
$(\sigma^{\prime}_{1},\sigma_{2})$ visits each node in $C$ at most twice, then
we let $\sigma^{\prime\prime}_{1}(h^{\prime})=\sigma^{\prime}_{1}(h^{\prime})$
for each $h^{\prime}\in H_{C}^{h}$. Now assume that there is a history in
$H_{C}^{h}$ with positive support in $(\sigma^{\prime}_{1},\sigma_{2})$ which
visits some node in $C$ more than twice.

We will now provide some intuition behind the construction of
$(\sigma^{\prime\prime}_{1},\sigma_{2})$. We will construct
$(\sigma^{\prime\prime}_{1},\sigma_{2})$ in a way that each play in $\Pi^{h}$
exits $C$ via at most two histories. This implies that the leader randomizes
in at most one node in $C$ (note that $\sigma_{2}$ is a pure strategy). So, if
there is a path $\pi\in\Pi^{h}$ such that a node $v$ in $C$ is visited at
least 3 times, no randomization takes place between two consecutive visits of
$v$. So, we can modify $\sigma^{\prime\prime}_{1}$ so that this part is short
circuited to ensure that $v$ is visited at most twice. We formalize the
construction as follows.

Each play in $\Pi^{h}$ is a continuation of exactly one history in
$E_{C}^{h}$. We will now show that it is possible to construct
$\sigma^{\prime\prime}_{1}$ in a way that there are at most two histories in
$E_{C}^{h}$, such that any play in $\Pi^{h}$ with positive support in the
$(\sigma^{\prime\prime}_{1},\sigma_{2})$, is continuation of one of them. Let
$h_{1},\ldots,h_{k}$ be the histories in $E_{C}^{h}$ with positive support in
the $(\sigma^{\prime}_{1},\sigma_{2})$, assume that $h_{i}$ is realized with
probability $p_{i}(>0)$. Note that $p_{1}+\ldots+p_{k}=p$. Due to Lemma 3,
there exist two histories $h_{1}$ and $h_{2}$, and probability $\hat{p}$ such
that

$\hat{p}\cdot u(\sigma^{\prime}_{1},\sigma_{2})(h_{1})+(p-\hat{p})\cdot
u(\sigma^{\prime}_{1},\sigma_{2})(h_{2})\geq p_{1}\cdot
u(\sigma^{\prime}_{1},\sigma_{2})(h_{1})+\ldots+p_{k}\cdot
u(\sigma^{\prime}_{1},\sigma_{2})(h_{k})$ (1)

As the histories $h_{1}$ and $h_{2}$ are realized with positive probabilities
in SSE $(\sigma^{\prime}_{1},\sigma_{2})$, due to equation 1 the leader can
commit to strategy (which will be $\sigma^{\prime\prime}_{1}$) which achieves
the histories $h_{1}$ and $h_{2}$ with probabilities $\hat{p}$ and $p-\hat{p}$
respectively. Since $\sigma^{\prime}_{1}$ and $\sigma^{\prime\prime}_{1}$ are
identical at all histories in $E_{C}^{h}$, we have
$u(\sigma^{\prime\prime}_{1},\sigma_{2})(h_{1})=u(\sigma^{\prime}_{1},\sigma_{2})(h_{1})$
and
$u(\sigma^{\prime\prime}_{1},\sigma_{2})(h_{2})=u(\sigma^{\prime}_{1},\sigma_{2})(h_{2})$.
Hence, $\sigma_{2}$ is best response to $\sigma_{2}$. Since
$(\sigma^{\prime\prime}_{1},\sigma_{2})$ exits $C$ via at most two histories.
∎

###### Theorem 5.1

For sequential games on DGs without chance nodes,there exists a polynomial
time algorithm which computes such a SSE with strategy profile with memory.

##  6 Algorithm for Games with Chance Nodes on DAGs

In this section, we consider the sequential games which contain chance nodes.
We restrict the game graphs to DAGs. In presence of chance nodes, [19] show
that it is NP-Hard to compute SSE even when the graph is a tree. They show
this by reducing an arbitrary instance of KNAPSACK problem to an sequential
game (on trees with chance nodes). Since the reduction restricted to the games
on trees, the same reduction works to show the NP-Hardness to compute SSE with
memory on games on trees or DAGS.

###### Proposition 3

In sequential games with chance nodes, it is NP hard to compute a SSE with
memory.

With no hope of finding polynomial time algorithm to find an exact SSE, we
focus our attention to compute an approximation version of SSE, which gives
the leader a payoff arbitrarily close to his SSE payoff. To simplify the
arguments we transform the graph from a DAG to a binary DAG (the out degree of
each node is at most 2). This transformation is without loss of generality,
since the strategic structure of the game remains same. The transformation is
done by sequentially adding auxiliary nodes for each node which has more than
2 children. These auxiliary nodes ensure that the out degree of each node is
at most 2, while maintaining the same strategic structure of the game. An
example of a transformation step in which auxiliary nodes are added when a
leader node has 4 children is illustrated in Fig. 7. For a node with $k$
children, we require at most $k-1$ auxiliary nodes. Hence, the new graph has
$O(n^{2})$ auxiliary nodes, and the height of the new graph is at most
$\log(n)$ more than the original graph.

$v$$w_{1}$$w_{2}$$w_{3}$$w_{4}$$v$$a_{1}$$a_{2}$$w_{1}$$w_{2}$$w_{3}$$w_{4}$
Figure 7: A general DAG can be replaced by a new binary DAG obtained by adding
auxiliary nodes, which corresponds to the same game.

At each node $v$, algorithm constructs the value $A_{v}[k]$ for each
$k\in\\{U_{1},U_{1}+\delta,\ldots,U_{2}\\}$ which represents the maximum
utility that the follower can obtain starting at $v$, conditional on the fact
that the leader can commit to a strategy which with a best response from the
follower gives the leader utility at least $k$ starting at $v$.

Leaf node: If $v$ is a leaf where leader obtains utility $u_{l}$ and follower
obtains utility $u_{f}$, then

$A_{v}[k]=\begin{cases}u_{f},&\text{if }k\leq u_{l},\\\ -\infty,&\text{if
}k>u_{l}\end{cases}$ (2)

Chance node: If a chance node $v$ has only one child $w$, then
$A_{v}[k]=A_{w}[k]$ for each $k$. Now assume that $v$ has two children $L$ and
$R$. If the chance node plays $L$ with probability $p$ and $R$ with
probability $1-p$, the payoff $k$ can be guaranteed for the leader by
achieving payoff $i$ at the subgame rooted at $L$ and payoff $j$ at subgame
rooted at $R$, such that the inequality $pi+(1-p)j\geq k$ is satisfied. Hence,
the maximum utility for the follower with guarantee that the leader gets at
least $k$ can be calculated as the following maximization problem.

$A_{v}[k]=\max_{i,j}\left\\{pA_{L}[i]+(1-p)A_{R}[j]\hskip 5.69054pt|\hskip
5.69054ptpi+(1-p)j\geq k\right\\}.$ (3)

Follower node: If a follower node $v$ has only one child $w$, then
$A_{v}[k]=A_{w}[k]$ for each $k$. Now assume that $v$ has two children $L$ and
$R$. At node $v$ if the follower goes to $L$, then $A_{L}[k]$ is the maximum
utility the follower can obtain if the leader gets at least $k$. If
$A_{L}[k]<\mu_{2}(R)$, then the leader can not guarantee guarantee himself
payoff of at least $k$ while follower plays $L$, since the follower guarantees
strictly higher payoff of at least $\mu_{2}(R)$ by playing to $R$. Similarly,
if $A_{R}[k]<\mu_{2}(L)$, then the leader can not guarantee guarantee himself
payoff of at least $k$ while follower plays $R$, since the follower guarantees
strictly higher payoff of at least $\mu_{2}(L)$ by playing to $L$. We consider
4 cases.

(a) If $A_{L}[k]<\mu_{2}(R)$ and If $A_{R}[k]<\mu_{2}(L)$, then it is
impossible for the leader to guarantee utility $k$, so $A_{v}[k]=-\infty$.

(b) If $A_{L}[k]\geq\mu_{2}(R)$ and If $A_{R}[k]<\mu_{2}(L)$, then the leader
can not incentivize the follower to play $R$ while guaranteeing utility $k$
for himself. However, he can play the strategy corresponding to $A_{L}[k]$ at
$L$ and punishing strategy at $R$, which incentivizes the follower to play $R$
and guarantees utility of at least $k$ for the leader. Hence,
$A_{v}[k]=A_{L}[k]$.

(c) If $A_{L}[k]<\mu_{2}(R)$ and If $A_{R}[k]\geq\mu_{2}(L)$, then with the
similar reasoning, $A_{v}[k]=A_{R}[k]$.

(d) If $A_{L}[k]\geq\mu_{2}(R)$ and If $A_{R}[k]\geq\mu_{2}(L)$, the leader
can incentivize the follower to play either $L$ or $R$. So,
$A_{v}[k]=\max\\{A_{L}[k],A_{R}[k]\\}$

In the case (d) if leader had access to a randomization device, it would be
possible for the leader to incentivize the follower to play a mixed action at
the node $v$, which may be further beneficial for the leader. Instead in our
setting, follower can use the memory states to imitate the mixed actions. For
a given pair of leader and follower nodes, we define a procedure $achievable$
to check if this is possible.

Procedure $\bm{achievable}$

For a leader node $v$, follower node $w$ where $v$ is an ancestor of $w$ and
real number $U$, we define a procedure $achievable(v,w,U)$ which determines if
there exists a leader’s strategy in which he randomizes at $v$, and a best
response of the follower such that $w$ is reached with positive probability,
conditional on the guarantee that the follower obtains the payoff of $U$ after
reaching $w$. This procedure first creates a new game $\mathcal{G}_{a}$ as
follows. The graph $G_{a}$ is constructed from the original graph $G$ by
deleting all the nodes which are not ancestors of $w$ and adding one leaf node
for each of the remaining follower nodes. An edge is added from each of the
follower node to the corresponding leaf node. The payoff for the follower at
the leaf node corresponding to a follower node $v$ is $\max_{\text{child
}v^{\prime}\text{ of }v\text{ not in }G_{a}}\mu_{2}(v^{\prime})$ and the
payoff for the leader at that leaf node is 0.

Now we perform an upward pass to compute for each node $x$ in $G_{a}$, the
utility $\hat{u}_{2}(x)$ the follower can guarantee. To begin, we have
$\hat{u}_{2}(w)=U$ and for leaf node $l$ with follower’s utility $u$, let
$\hat{u}_{2}(l)=u$. For a leader node $x$, let
$\hat{u}_{2}(x)=\min\\{\hat{u}_{2}(L),\hat{u}_{2}(R)|L,R\text{ children of
}x\\}$. For a follower node $x$, let
$\hat{u}_{2}(x)=\max\\{\hat{u}_{2}(L),\hat{u}_{2}(R)|L,R\text{ children of
}x\\}$. For a chance node $x$ which plays $L$ with probability $p$ and $R$
with probability $1-p$, $\hat{u}_{2}(x)=p\hat{u}_{2}(L)+(1-p)\hat{u}_{2}(R)$.

Finally, we conclude that there exists such strategy for the leader, if $v$
and both of his children $L,R$ are in $G_{a}$ such that
$\hat{u}_{2}(v)=\hat{u}_{2}(L)=\hat{u}_{2}(R)=U$.

Leader node: If a leader node $v$ has only one child $w$, then
$A_{v}[k]=A_{w}[k]$ for each $k$. Now assume that $v$ has two children $L$ and
$R$. Leader can commit to payoff of $k$ in following two ways.

(i) The leader plays $L$ with probability $p$ and $R$ with probability $1-p$,
the payoff of $k$ can be guaranteed by achieving payoff $i$ at the subgame
rooted at $L$ and payoff $j$ at subgame rooted at $R$, while satisfying the
inequality $pi+(1-p)j\geq k$. Hence, the maximum utility for the follower in
such a case, denoted by $X_{v}[k]$, can be calculated as the following
maximization problem.

$X_{v}[k]=\max_{i,j,p}\>\left\\{pA_{L}[i]+(1-p)A_{R}[j]\hskip 5.69054pt|\hskip
5.69054ptpi+(1-p)j\geq k\right\\}.$ (4)

(ii) Continuing the discussion of case (d) in the follower node, if leader had
access to a randomization device, it would be possible to incentivize the
follower to play a mixed action at the node $v$, which may be further
beneficial for the leader. Instead, leader can use memory for a randomization
devise as follows.

This can be done at a leader’s node which is an ancestor to such a follower
node in a following way.

For each of the follower node $w$ such that $v$ is ancestor of $w$, perform
the procedure $achievable(v,w,X_{v}[k])$. For every such $w$ (with children
$L_{w}$ and $R_{w}$) for which the procedure is successful, define

$Y_{w}[k]=\max_{i,j,p}\>\left\\{pA_{L_{w}}[i]+(1-p)A_{R_{w}}[j]\hskip
5.69054pt|\hskip 5.69054ptpi+(1-p)j\geq k\right\\}.$ (5)

So, $Y_{w}[k]$ is a payoff that follower can get conditional on the leader
gets at least $k$, when the follower chooses $L$ with probability $p$ and $R$
with probability $1-p$. The leader can incentivize the follower by choosing
$L$ and $R$ himself at node $v$ with the same probabilities, as a suggestion
that the follower should play $L$ at $w$ if he observes leader playing $L$ at
$v$ and play $R$ otherwise. If the follower does not comply, the leader
commits to playing the punishing at subsequent nodes.
$Y_{v}[k]=\max_{w}\>\\{X_{w}[k]\hskip 5.69054pt|\hskip
5.69054ptachievable(v,w,X_{v}[k])\text{ is successful}\\}$. Finally,
$A_{v}[k]=\max\\{X_{v}[k],Y_{v}[k]\\}$. ∎

##  7 Concluding remarks

We study the two player, non-zero sum, perfect information sequential games on
directed acyclic graphs and directed graphs. The players can play history-
dependent, mixed behavioral strategies. We define an alternate formulation
called strategy profiles with memory for the history-dependent strategy
profiles in which players can base their decisions only on the memory states.
Using this formulation, we establish that strategies with memory can be
described efficiently if the memory size is polynomial.

While it was shown that it is NP-Hard to compute the SSE for games on DAGs
where the strategies are history-independent, we construct a polynomial time
algorithm to compute the SSE for games on DAGs without chance nodes with
strategy profiles with memory. Since the memory size of this strategy profile
is linear in the number of nodes, it can be described very efficiently. We
modify our algorithm to work in games on general directed graphs without
chance nodes, by proving an existence of SSE which visits each node at most
twice. We also discuss the approximate version of SSE with memory for games on
DAGs with chance nodes.

We see many interesting extensions of our model and open question to be
addressed in future work. Our algorithm and the construction of memory states
can be used in various applied models in security games. One future extension
would be to consider the games in which the leader and the follower play
simultaneous moves in the dynamic games.

## Acknowledgements

This research was supported by the Czech Science Foundation (no. 19-24384Y)
and by the Combat Capabilities Development Command Army Research Laboratory
and was accomplished under Cooperative Agreement Number W911NF-13-2-0045 (ARL
Cyber Security CRA). The views and conclusions contained in this document are
those of the authors and should not be interpreted as representing the
official policies, either expressed or implied, of the Combat Capabilities
Development Command Army Research Laboratory or the U.S. Government. The U.S.
Government is authorized to reproduce and distribute reprints for Government
purposes not withstanding any copyright notation here on.

## References

  * [1] Amir, R., Grilo, I.: Stackelberg versus Cournot Equilibrium. Games and Economic Behavior 26(1), 1–21 (1999)
  * [2] Basilico, N., Gatti, N., Amigoni, F.: Leader-follower strategies for robotic patrolling in environments with arbitrary topologies. In: Proceedings of the 8th International Conference on Autonomous Agents and Multiagent Systems. pp. 57–64 (2009), http://portal.acm.org/citation.cfm?id=1558020
  * [3] Basilico, N., Coniglio, S., Gatti, N.: Methods for finding leader-follower equilibria with multiple followers. In: Proceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems. pp. 1363–1364. International Foundation for Autonomous Agents and Multiagent Systems (2016)
  * [4] Bošanský, B., Brânzei, S., Hansen, K.A., Lund, T.B., Miltersen, P.B.: Computation of stackelberg equilibria of finite sequential games. ACM Transactions on Economics and Computation (TEAC) 5(4), 23 (2017)
  * [5] Bošanský, B., Čermák, J.: Sequence-Form Algorithm for Computing Stackelberg Equilibria in Extensive-Form Games. In: Proceedings of AAAI Conference on Artificial Intelligence. pp. 805–811 (2015)
  * [6] Clempner, J.B., Poznyak, A.S.: Stackelberg security games: Computing the shortest-path equilibrium. Expert Systems with Applications 42(8), 3967–3979 (2015)
  * [7] Conitzer, V., Korzhyk, D.: Commitment to Correlated Strategies. In: Proceedings of AAAI Conference on Artificial Intelligence. pp. 632–637 (2011)
  * [8] Conitzer, V., Sandholm, T.: Computing the optimal strategy to commit to. In: Proceedings of the 7th ACM conference on Electronic commerce. pp. 82–90. ACM (2006)
  * [9] Durkota, K., Lisỳ, V., Bošanskỳ, B., Kiekintveld, C., Pěchouček, M.: Hardening networks against strategic attackers using attack graph games. Computers & Security 87, 101578 (2019)
  * [10] Fang, F., Nguyen, T.H., Pickles, R., Lam, W.Y., Clements, G.R., An, B., Singh, A., Schwedock, B.C., Tambe, M., Lemieux, A.: Paws-a deployed game-theoretic application to combat poaching. AI Magazine 38(1), 23–36 (2017)
  * [11] Fang, F., Nguyen, T.H., Pickles, R., Lam, W.Y., Clements, G.R., An, B., Singh, A., Tambe, M., Lemieux, A., et al.: Deploying paws: Field optimization of the protection assistant for wildlife security. (2016)
  * [12] Gupta, A.: Equilibria in Finite Games. Ph.D. thesis, University of Liverpool (2015)
  * [13] Gupta, A., Schewe, S., Wojtczak, D.: Making the best of limited memory in multi-player discounted sum games. In: Proceedings 6th International Symposium on Games, Automata, Logics and Formal Verification. pp. 16–30 (2015)
  * [14] Klaška, D., Kučera, A., Lamser, T., Řehák, V.: Automatic synthesis of efficient regular strategies in adversarial patrolling games. In: Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems. pp. 659–666. AAMAS ’18, International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC (2018), http://dl.acm.org/citation.cfm?id=3237383.3237481
  * [15] Korzhyk, D., Conitzer, V., Parr, R.: Complexity of computing optimal stackelberg strategies in security resource allocation games. In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 24 (2010)
  * [16] Kroer, C., Farina, G., Sandholm, T.: Robust stackelberg equilibria in extensive-form games and extension to limited lookahead. In: Proceedings of the AAAI Conference on Artificial Intelligence. vol. 32 (2018)
  * [17] Kroer, C., Sandholm, T.: Limited lookahead in imperfect-information games. Artificial Intelligence 283, 103218 (2020)
  * [18] Letchford, J.: Computational aspects of stackelberg games. Ph.D. thesis, Duke University (2013)
  * [19] Letchford, J., Conitzer, V.: Computing optimal strategies to commit to in extensive-form games. In: Proceedings of the 11th ACM conference on Electronic commerce. pp. 83–92. ACM (2010)
  * [20] Letchford, J., MacDermed, L., Conitzer, V., Parr, R., Isbell, C.L.: Computing optimal strategies to commit to in stochastic games. In: AAAI (2012)
  * [21] Matsumura, T.: Stackelberg Mixed Duopoly with a Foreign Competitor. Bulletin of Economic Research 55, 275–287 (2003)
  * [22] Nguyen, T.H., Yadav, A., Bosansky, B., Liang, Y.: Tackling sequential attacks in security games. In: International Conference on Decision and Game Theory for Security. pp. 331–351. Springer (2019)
  * [23] Paruchuri, P., Pearce, J.P., Marecki, J., Tambe, M., Ordonez, F., Kraus, S.: Playing games for security: an efficient exact algorithm for solving Bayesian Stackelberg games. In: Proceedings of International Conference on Agents and Multiagent Systems (AAMAS). pp. 895–902 (2008)
  * [24] Sherali, H.D.: A multiple leader stackelberg model and analysis. Operations Research 32(2), 390–404 (1984)
  * [25] Sinha, A., Fang, F., An, B., Kiekintveld, C., Tambe, M.: Stackelberg security games: Looking beyond a decade of success. In: IJCAI. pp. 5494–5501 (2018)
  * [26] Tambe, M.: Security and Game Theory: Algorithms, Deployed Systems, Lessons Learned. Cambridge University Press (2011)
  * [27] Čermák, J., Bošanský, B., Durkota, K., Lisý, V., Kiekintveld, C.: Using Correlated Strategies for Computing Stackelberg Equilibria in Extensive-Form Games. In: Proceedings of AAAI Conference on Artificial Intelligence. pp. 439–445 (2016)
  * [28] Černý, J., Bosanský, B., An, B.: Finite state machines play extensive-form games. In: Proceedings of the 21st ACM Conference on Economics and Computation. p. 509–533. EC ’20, Association for Computing Machinery, New York, NY, USA (2020), https://doi.org/10.1145/3391403.3399517
  * [29] Von Stackelberg, H.: Marktform und gleichgewicht. J. springer (1934)
  * [30] Von Stengel, B., Zamir, S.: Leadership with commitment to mixed strategies. Tech. rep., Technical Report LSE-CDAM-2004-01, CDAM Research Report (2004)
  * [31] Xu, H., Dughmi, S., Tambe, M., Noronha, V.L.: Mitigating the curse of correlation in security games by entropy maximization. In: Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems. pp. 2127–2129. International Foundation for Autonomous Agents and Multiagent Systems (2018)
  * [32] Xu, H., Rabinovich, Z., Dughmi, S., Tambe, M.: Exploring Information Asymmetry in Two-Stage Security Games. In: Proceedings of AAAI Conference on Artificial Intelligence. pp. 1057–1063 (2015)