  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.
