tcb@breakable

# Efficient Stackelberg Strategies for Finitely Repeated Games

Eshwar Ram Arunachaleswaran  University of Pennsylvania  Natalie Collina
University of Pennsylvania  Michael Kearns  University of Pennsylvania

(July 2022)

###### Abstract

We study the problem of efficiently computing optimal strategies in asymmetric
leader-follower games repeated a finite number of times, which presents a
different set of technical challenges than the infinite-horizon setting. More
precisely, we give efficient algorithms for finding approximate Stackelberg
equilibria in finite-horizon repeated two-player games, along with rates of
convergence depending on the horizon $T$. We give two algorithms, one
computing strategies with an optimal $\frac{1}{T}$ rate at the expense of an
exponential dependence on the number of actions, and another (randomized)
approach computing strategies with no dependence on the number of actions but
a worse dependence on $T$ of $\frac{1}{T^{0.25}}$. Both algorithms build upon
a linear program to produce simple automata leader strategies and induce
corresponding automata best-responses for the follower. We complement these
results by showing that approximating the Stackelberg value in three-player
finite-horizon repeated games is a computationally hard problem via a
reduction from the balanced vertex cover problem.

##  1 Introduction

The central solution concept in games is the Nash Equilibria, where each agent
is playing optimally against the mixed strategy of the other agents. Nash
equilibria are known to always exist in finite games [28], and the problem of
computing them has been widely studied, with efficient algorithms developed
for many special classes (See [27]), and hardness results for general two
player games (See [11], [15], [29]).

There are many natural variants of this problem. A solution concept of
particular interest is the Stackelberg Equilibrium [17], in which one of the
players, called the leader, is allowed to commit to a strategy first, and
communicates this strategy to the other players. This problem was first
studied through a computational lens by Conitzer and Sandholm [14], who showed
efficient algorithms in the case of two players, and hardness results for
three player games, and has since been the subject of many other works,
including for settings such as security games (See [1]).

In another parallel line of work, repeated games have been studied as a
natural generalization of the single-shot, simultaneous game — agents
repeatedly play the same game over multiple rounds, where the outcome in each
round depends only upon the actions played in that round. However, a critical
point of interest about these games is that the actions employed in each round
may depend arbitrarily upon the history of play and the internal state of each
player. In the most well-studied version of the repeated game problem, the
game is played repeatedly over an infinite time horizon, with each player
seeking to maximize their average payoff in the limit.

It is well-known that several phenomena arise in infinite-horizon repeated
games that are not present in the single-shot setting. First, new equilibrium
strategies can arise, such as cooperation in Prisoners Dilemma, a development
that is generally viewed positively. Second, too many new equilibria may
arise, as witnessed by the Folk Theorem, thus diluting the prescriptive power
of equilibria. Third, while efficiently computing equilibria in single-shot
games for even two players is a notorious open problem for which there is some
evidence of intractability ([29], [11], [15]), there is an efficient algorithm
for computing Nash equilibria of two-player infinitely repeated games.

This last result was shown constructively in the work of Littman and Stone
[25], who gave an efficient algorithm for computing finite automata
equilibrium strategies achieving any given feasible payoff profile. In more
recent work of Zhou and Tang [34], an analogous result was given for infinite
repeated Stackleberg games, again providing an efficient algorithm for
computing finite automata strategies (and a generalization to automata with
infinite states) for both the leader and follower.

These prior works, as well as much of the literature on repeated games, seem
inherently limited to the infinite-horizon setting. Reasoning about finite-
horizon games introduces many complexities not present in the infinite-horizon
case. In infinite-horizon games, any finite prefix of play can be ignored, and
players can have threats of unbounded length. We lose this power in finite-
horizon games, and furthermore must concern ourselves with delicate order of
play and “final-round” complexities. Despite the fundamentally different
reasoning which must occur in the finite-horizon setting, we are able to show
efficient algorithms for computing simple and approximately optimal
Stackelberg strategies for any $T$, which are also approximately as good as
any Stackelberg strategy in the infinite-horizon game.

In the context of Nash equilibria, infinite-horizon games introduce numerous
Nash equilibria which are fundamentally different from the equilibria in their
finite-horizon counterparts [7]. The most famous example of this phenomenon is
repeated Prisoner’s Dilemma, where backwards induction shows that the only
finite-horizon Nash equilibrium is mutual defection at every round. By
contrast, in the infinite-horizon Prisoner’s Dilemma, there exist Nash
equilibria where the players cooperate to achieve socially optimal payoffs.

However, this is _not_ the case for Stackelberg equilibria; as we will see in
this paper, finite-horizon repeated games give rise to Stackelberg equilibria
which are comparable in power and complexity to their infinite-horizon
counterparts. The nature and computation of Stackelberg equilibrium strategies
in repeated games with finite horizon $T$ has previously been poorly
understood. The best known results in fact appear in a related, but different
line of work, which is the study of extensive-form games. The results of
Letchford and Conitzer [22] and Bosansky et al. [3] give algorithms to compute
Stackelberg Equilibria in general extensive-form games in time polynomial and
linear respectively in the size of the game tree. Since finite-horizon
repeated games are a special case of extensive-form games, these results also
imply algorithms to find the Stackelberg Equilibria of finite-horizon games.
However, the running time guarantees are no better than exponential in $T$,
since finite-horizon games cannot be succinctly represented as extensive form
games. To the best of our knowledge, no prior work has explicitly focused upon
Stackelberg equilibria in finite-horizon games and their algorithmic
properties.

In this paper, we consider algorithms for repeated Stackleberg games with
finite horizon. Like previous papers on repeated games, the players in our
game are allowed to employ a broad class of algorithms (essentially any finite
time algorithm) to decide their strategies in each round based upon this
history of play and their internal state. This allows for a large space of
commitment schemes; for example, the leader can employ “threats” such as the
grim-trigger strategy in the repeated Prisoner’s Dilemma.

Our main results are:

  * •

We give two efficient algorithms that find additively approximate Stackelberg
Strategies for the leader that trade off different approximation factors.
First, we show a $\left(\frac{2^{\text{poly}(n)}}{T}\right)$\- additive
approximate Stackelberg strategy where $n$ is the number of actions, which is
asympotically tight in $T$. This is constructed using an algorithm that runs
in polynomial time in the game size and $\log T$. We also present an approach
using randomized sampling which gives a $O(\frac{1}{T^{0.25}})$-additive
approximation that runs in time polynomial in the game size and $T$ 111The
approximation factors also depend upon the maximum number of bits needed to
represent a single payoff.. This second approach provides a slightly weaker
approximation factor in $T$ in exchange for entirely avoiding dependence on
$n$. Both constructions use simple automata (including states that play
distributions over actions) for the leader and also for a corresponding
follower best-response. We leave it as an open question whether there is an
algorithm combining the best of both rates.

  * •

Building upon a reduction of Conitzer and Sandholm [14] that showed that
finding the Stackleberg value of a three player game is NP-hard, we show that
even approximating the Stackelberg value of a three player repeated game is
NP-hard (Theorem 3), ruling out any extension of our results for two player
repeated games. We also use the same reduction to observe that approximating
the Stackelberg value of three-player infinitely repeated games is NP-hard.
These results can be found in Section 5.

We also show a sequence of auxiliary results, that we discuss briefly here to
help the reader to navigate through the paper.

  * •

We show that finding a follower’s best-response even to a poly-time leader
strategy is in general a computationally hard problem (Lemma 9). However, our
approximate Stackelberg leader algorithm (Theorem 2) has an efficiently
computable best-response (Lemma 11). We discuss these results in Appendix B.

  * •

We show that the optimal Stackelberg leader strategy may be different from
simply playing the single-shot game’s Stackelberg strategy in each round of
play, through the example of the well known Prisoner’s Dilemma (Section 3.1).

  * •

No-Regret algorithms are widely studied in the context of repeated games, due
to their strong performance and strategic properties (See [9], [16]). A
natural question is whether no-regret algorithms are in fact optimal leader
algorithms in the Stackelberg setting. We show that, somewhat unsurprisingly,
arbitrary no-regret algorithms are in fact Stacklberg leader algorithms in two
player zero-sum games (Lemma 15). In contrast, we show via a counterexample
that these properties do not hold when the zero-sum condition is removed,
necessitating the broadening of the search to a more general class of
algorithms. These results are in Appendix F.

###  1.1 Our Techniques

In proving our main result (Theorem 2) about efficiently computing a near
optimal Stackelberg leader algorithm, we use a sequence of ideas. Our main
workhorse is a linear program (similar in spirit to that of [34]) that is used
to upper bound the average (per round) payoff that the leader can guarantee
themselves against a rational follower. This linear program additionally gives
us an “ideal” empirical distribution over the action pairs that the transcript
of play must follow to achieve the aforementioned value. We then convert this
ideal empirical distribution into a concrete transcript of play for both the
leader and follower. Akin to Littman and Stone [25] and Zuo and Tang [34], we
use the notion of “threats” to stabilize such a transcript so as to force the
follower to play along with it.

However, in a departure from these works, our construction carefully
choreographs the order of action pairs in this transcript to ensure that the
follower’s best response is to follow the prescribed transcript. One might ask
why we explicitly prescribe these ordered pairs, instead of allowing the
leader to draw pairs from the LP distribution i.i.d. each round. The problem
is that even if the leader commits to drawing from this distribution and
playing their side of the strategy, they have no way to signal to the follower
what they should play at any given round before play occurs. Our approach, in
spirit, involves the leader pre-committing to these signals at the start of
the game. However, this means that the follower can see the payoffs of the
specific move pairs they will be asked to play each round (as opposed to an
expected payoff over an i.i.d. draw), which necessitates the ordering of pairs
by increasing follower payoff. The transcript we construct forces through the
worst action pairs for the follower first, and adds “treats” at the end to
ensure that the follower is incentivized to follow the prescription at each
round of the game. The approximation to the upper bound comes from “fitting” a
probability distribution to a finite number of rounds $T$, and improves as $T$
grows larger. While the average values of the leader and follower in the
transcript will approximate their value in the LP distribution for large $T$,
the ordering means that the actual transcript will not look like a typical
sequence of i.i.d. draws from the distribution.

While the above approach gives us a rate of convergence to optimality that
depends, possibly exponentially badly, on the number of actions for each
player in the game, we show in Section 4.3 how to eliminate the dependence
upon the number of actions. The main idea involved is a randomized sampling
scheme that allows us to simplify the ideal empirical distribution found by
the linear program. This process can also be viewed as randomized rounding of
the linear program’s solution to a more succinctly representable solution.
This rounding also introduces randomization in the leader’s algorithm, and
converts the absolute guarantee of near-optimality into a high probability
guarantee.

In Theorem 3, where we show the hardness of approximation of computing the
Stackelberg value of repeated three player games, we demonstrate a gap-
producing reduction from the balanced vertex cover problem. This reduction
builds upon [14], which showed that finding the Stackelberg value of three-
player games is NP-hard also via reduction from balanced vertex cover. Their
hard instance does not directly extend to repeated games because of the
richness of new strategies available to the leader(s) in the repeated setting.
Most of the work in our reduction goes into proving a stronger result about
the single-shot case, which we do in Lemma 7. We can then lift this stronger
result to the game with $T$ repeated rounds and prove hardness of
approximation in Theorem 3. We also observe that the same lemma can be used to
show that finding the approximate Stackelberg value of three-player infinitely
repeated games is NP-hard.

##  2 Related Work

The notion of Stackelberg Equilibria (SE) was first introduced by von
Stackelberg in [17], who observed the advantage of strategic commitment in
Cournot’s duopoly model. Some followup work in the next decades did focus on
applying the concept to repeated games, but these works focused on proving
necessary and sufficient conditions for SE existence in various settings,
rather than on constructive algorithms. [31] explores SE in repeated games
where the payoff matrix is either static or dynamic. They consider games where
players have have an infinite number of moves (a setting where even Nash
Equilibria may not exist) and derive conditions for SE existence. [2] consider
_sequential_ Stackelberg games, repeated games where the state of the game
matrix is affected by the moves that the players play each round. This setting
is distinct from our own in that the leader makes a commitment each round
instead of committing to an algorithm at the start of the game.

In [14], Conitzer and Sandholm gave a polynomial algorithm for computing exact
Stackelberg mixed strategies in single-shot, two-player games, bringing new
algorithmic interest to the study of computing SE. Their method involves
solving $n$ linear programs, with the $i$th program representing the best
payoff that the leader can get given that they are incentivizing the follower
to play pure strategy $i$. Picking the highest payoffs over all of these LPs
gives the leader their Stackelberg strategy for a single-shot game. They go on
to prove that computing an exact Stackelberg strategy in a three-player game
is NP-hard, via a reduction from Vertex Cover. A closely related work is [33],
which proves various properties about single-shot SE games with convex
strategy sets. These works led to further research considering the complexity
of computing SE in various settings. The most closely related followup work,
which we will describe below, involves NP-hard results for stochastic and
extensive-form games, which are superclasses of finite-horizon repeated games,
and a poly-time algorithm for _infinite_ -horizon repeated games.

In [12], Conitzer and Korzhyk observe that instead of solving a linear program
for each of the $k$ pure strategies to find the SE, it is possible to instead
solve a single linear program over the $k^{2}$ move pairs. This approach gives
equivalent solutions for the two-player setting, but, when armed with a
correlating device, allows them to compute optimal _correlated_ strategies to
commit to in three-player games. The problem of optimizing over distributions
of move pairs is technically similar to our own LP, though the two LPs have
different constraints as they have differing goals. Conitzer and Korzhyk’s
linear program is used to find an optimal correlated equilibria to commit to,
which could involve randomness from both parties, while our LP has the goal of
finding a hypothetical ideal distribution over move pairs that can be stably
enforced by a particular kind of threat in a repeated two player game with a
leader.

Commitment and correlation are further explored in [24], which gives some
hardness results for computing SE in two-player infinite-horizon stochastic
games. They prove NP-hardness for exact Stackelberg in the case where the
leader is allowed to commit to a mixed strategy at each stage. Any finite-
horizon repeated game can be represented as an infinite-horizon stochastic
game by having $T$ states which always transition in line and a $(T+1)$-th
state with a self-loop which has payoff $0$ for both players. However,
infinite-horizon stochastic games are a strictly richer class of games, and
therefore this hardness result does not imply any complexity results for our
case. [24] then show a poly-time algorithm to find an approximate Stackelberg
for the case where the leader is allowed to send signals to the follower
throughout the game, which allows them to commit to a correlated equilibria.
In our setting, this would be equivalent to allowing the leader, at round $t$,
to send not only their move but also information about the realized randomness
of a future move. Our leader algorithms cannot send any information other than
the moves at each round, and therefore this poly-time approximation does not
imply any complexity result for our setting.

Another line of work adjacent to finite-horizon repeated games is that of
finding SE in extensive-form games (EFGs). EFGs can be represented as trees,
with paths down the tree representing move sequences and leaves representing
outcomes. Here, a Stackelberg strategy is usually presented as a mapping from
each node in the game tree to a mixed strategy. [22] show that computing SE
for EFGs with stochastic transitions is NP-hard in the size of the game tree.
There exist exact([32]) and approximate ([21], [13]) algorithms for computing
SE for various special cases of the EFG setting, all of which require time
linear or polynomial in the size of the game tree. Most relevantly to our
work, [22] find an algorithm to compute Stackelberg strategies for the special
case of complete-information, two-player determinstic EFGs that is polynomial
in the size of the game tree. [3] improve this to an algorithm which is linear
in the game tree size. Finite-horizon repeated games can themselves be seen as
a special case of complete-information, deterministic EFGs, and these
techniques can therefore be used in our setting. However, the size of a game
tree in a repeated game is exponential in $T$ — note that on each of the $T$
rounds, there are $n^{2}$ different possible outcomes. Therefore, the pre-
existing algorithms for EFGs imply only an exponential-time algorithm for
repeated games. Our work goes beyond this to find an approximation algorithm
for repeated games which is polynomial in $T$ and in the size of the single-
shot game, and thus sublinear in the size of the corresponding game tree.

There is also work which reasons directly about the repeated-game setting, but
considers only the substantially distinct case of infinite-horizon repeated
games. Zuo and Tang give a poly-time algorithm for computing SE in the space
of machine strategies, which are automata that may have infinite states [34],
and generalize their results to probability distributions over subclasses of
these machine strategies. Similar to our work, [34] solve an LP which
optimizes the leader’s payoff when constrained to offer the follower better
than their safety value (called a security level in their paper). However,
their proof heavily relies upon the infinite nature of the game. They present
a Folk Theorem for infinite-horizon repeated games using machine strategies
and use this to construct optimal commitments in the form of state machines.
These state machines may have an infinite number of states, and therefore they
do not explicitly represent them but rather show the existence of a Turing
Machine which can do so. They also show additional results that examine how
limiting the memory level of the leader and follower’s machine strategies can
affect game outcomes. Their work can be seen as a Stackelberg analogue of
Littman and Stone’s paper, [25]. Both works examine infinite-horizon repeated
games, and both utilize constructive versions of Folk Theorems in order to
construct strategies (in the space of algorithms) that are in (the respective
type of) equilibrium.

Work in finding equilibria in infinite-horizon repeated games cannot be
directly applied to finite-horizon repeated games, as the algorithms for these
two settings are structurally incomparable. While algorithms for infinite-
horizon games have no sense of game length or game ending, algorithms for
finite-horizon games can be constructed with the game length in mind. An
algorithm for a finite-horizon repeated game can therefore behave differently,
for example, in the final move of a game, or operate entirely differently
depending on the initial game length.

From a hardness perspective, Conitzer and Sandholm [14] showed that finding
the Stackelberg value of a three player game is NP-hard. Conitzer and
Letchford [22] showed that finding the Stackelberg value of a three player
extensive-form game is NP-Hard. We extend the former and generalize the latter
result by proving hardness of approximation for finite-horizon repeated three-
player games. Borgs et al. [5] showed that no efficient algorithms exist for
finding Nash Equilibrium in three player infinite-horizon repeated games
unless PPAD is in $P$ when players use algorithms that depend only upon the
history of play (and not upon internal state). Halpern et. al. [18] later
showed that this hardness result can be surmounted if the players are allowed
to use (probabilistic polynomial time) algorithms that depend both upon the
history of play as well as internal state (by demonstrating an efficient
algorithm that finds a $\varepsilon$-approximate equilibrium). Their model is
an infinite-round analogue of our model (and that of [22] for EFGs), which
also allows the player’s algorithms to generate actions using randomness,
history of play and internal state.

Another line of work has investigated _learning_ to play a Stackelberg
strategy in a static repeated game [4], [26], [23]. In this setting, the
Stackelberg leader has limited information about the follower’s payoffs, and
must declare strategies round-by-round in order to learn their preferences.
The opponent is assumed to be responding myopically each round, and therefore
the goal of the leader is to learn and begin to play their single-round
Stackelberg strategy. By contrast, we assume that the follower knows the time
horizon and aims to maximize their payoff in expectation over the entire time
horizon, which, as we will show, allows the leader to do much better than
their single-round Stackelberg strategy in many cases.

In the context of playing repeated games using algorithms, we also mention no-
regret algorithms, which were developed for decision making in online
environments with experts (See [10]). Multiple papers (See [16], [8]) observed
that these algorithms can be used by self interested agents to play repeated
games due to the guarantees associated with them. In particular, in two player
zero-sum games, the transcript of play converges to a Nash Equilibrium if all
players use a no-regret algorithm, and to coarse correlated equilibria in
general games. For special classes of games, such as atomic routing games/
congestion games ([6], [20]) these are particularly compelling algorithms to
use, since they guarantee convergence to Nash Equilibria and stability.
However, as we show in Appendix F, no-regret algorithms are not in general
good algorithms for a leader to commit to in the Stackelberg setting.

We summarize the main results in the field of finding equilibria in single-
shot games, finite-horizon repeated games, and infinite-horizon repeated games
in Table 1. Our new contributions are bolded and in blue.

Table 1: Summary of known results

|  Single-shot |  Finite Horizon |  Infinite Horizon
---|---|---|---
2-player NE |  Hardness of $o(1)$ -approximation [29] 1 |  Hardness of $o\left(\frac{1}{T}\right)$\- approximation2 |  Poly-time algorithm for exact solution [25]
3-player NE |  Hardness of $o(1)$-approximation [29] |  Hardness of $o\left(\frac{1}{T}\right)$\- approximation2 |  Hardness of exact solution [5], hardness of $\frac{1}{\textit{poly}(n)}$-approximation with no internal states [5], poly-time $\frac{1}{\textit{poly}(n)}$-approximation with internal states [18]
2-player SE |  Poly-time algorithm for exact solution [14] |  Poly-time $\min\left(\left(\frac{2^{\text{poly}(n)}}{T}\right),\frac{1}{T^{0.25}}\right)$ -approximation algorithm (Thm 2) |  Poly-time algorithm for exact solution [34]
3-player SE |  Hardness of $o(1)$\- approximation [14]3 |  Hardness of $\left(\frac{1}{T^{\frac{1}{c}}}\right)$-approximation (Thm 3) |  Hardness of $\left(\frac{1}{\textit{poly}(n)}\right)$-approximation (Observation 2) 4

  * 1

An earlier version of the paper used incorrect asymptotic notation while
describing the hardness results.

  * 2

These results come from the fact that, in finite-horizon repeated games, any
pair of NE strategies must involve always playing a single-shot NE on the
final round. The single-shot hardness result can therefore be used to implies
that getting a $\Omega(\frac{1}{T})$ approximation over $T$ rounds is PPAD-
hard.

  * 3

While their paper does not explicitly claim such a result in a lemma, their
proof for hardness of finding an exact SE is in fact a hardness result for
finding any approximate SE.

  * 4

We do not provide a complete proof of this result, as the model we developed
for this paper only makes sense for the finite-horizon case, but we provide a
proof sketch and intuition.

##  3 Notation and Preliminaries

######  Definition 1 (Bimatrix Games).

A bimatrix game $G$ is defined by two $n\times n$ matrices $M_{1}$ and $M_{2}$
that respectively denote the payoffs for Player $1$ and Player $2$ for each
combination of actions chosen by the two players. We assume, without loss of
generality, that both players have the same number of actions, and that their
respective action sets are both indexed by the set $\\{1,2,\cdots n\\}$
denoted as $[n]$. If Player $1$ plays action $i$ and Player $2$ plays action
$j$, then they get payoffs $M_{1}(i,j)$ and $M_{2}(i,j)$. In the asymmetric
Stackelberg setting, Player $1$, or the row player, is assumed to go first and
is referred to as the leader while Player $2$, or the column player, is called
the follower. The strategies for Players $1$ and $2$ are points $x,y$ in
$\Delta^{n}:=\\{x\in\mathbb{R}^{n}_{+}:\sum_{i}x_{i}=1\\}$ denoting the
weights they place on the actions in their respective action sets. A pure
strategy $i\in[n]$ is represented by the standard basis vector $e_{i}$. The
expected payoff of Player $1$ (respectively $2$) is $x^{\intercal}M_{1}y$
(respectively $x^{\intercal}M_{2}y$). We assume that each entry in the payoff
matrix is in $[-1,1]$ and is additionally an integer multiple of
$\frac{1}{A}$, where $A$ is a sufficiently large integer. $A$ can be seen as a
measure of the granularity of the payoff values and will become relevant when
defining our approximation guarantees.

######  Definition 2 (Nash Equilibria in Single-Shot Games).

A pair of strategies $x,y\in\Delta^{n}$ form a Nash Equilibrium for the game
$G$ if there is no incentive for either player to deviate unilaterally, i.e.
for all pure strategies $e_{i}$ ($e_{j}$) of Player $1$ (2), we have
$x^{\intercal}M_{1}y\geq e_{i}^{\intercal}M_{1}y$ ( $x^{\intercal}M_{2}y\geq
x^{\intercal}M_{2}e_{j}$).

######  Definition 3 (Stackelberg Equilibria in Single-Shot Games).

A strategy $x\in\Delta^{n}$ is said to be a Stackelberg strategy for the
leader if it maximizes $x^{\intercal}M_{1}y$ where $y\in\Delta^{n}$ is a best
response for the follower to $x$. Note that it suffices for the follower to
play a pure strategy $e_{j}$ as a best response. The induced play $(x,y)$ is
called the Stackelberg Equilibria (SE) of the game. For the purposes of this
paper, we assume that the follower selects a best possible best response for
the leader if there are multiple best response strategies, a common assumption
in Stackelberg literature. SE with this sort of tiebreaking assumption are
known as _Strong Stackelberg equilibria_ , but for simplicity we will simply
refer to _SE_ throughout this paper.

######  Definition 4 (Repeated Bimatrix Game).

A repeated bimatrix game is defined by a bimatrix game $G$ and a time horizon
$T$, both of which are known to all players. Players will play the game $G$
for exactly $T$ rounds, and their payoffs will be the sum of their payoffs
over all rounds. The payoff matrix will remain static throughout all rounds.
However, players may play different mixed strategies on different rounds and
dynamically update their strategies based upon previous rounds of play. We
refer to the pairs of actions
$(i_{1},j_{2});(i_{2},j_{2}),\cdots(i_{T},j_{T})$ played in the $T$ rounds as
the transcript of the game and use $\mathcal{T}$ to represent this transcript.
The values of interest to us are the expected average per-round payoffs of the
two players where the expectation is over the random bits used by the players.
If $T=\infty$, then we call this an _infinite-horizon_ game. For much of this
paper, we will consider finite $T$, in which case we call this a _finite-
horizon_ game.

It is obvious that players in a finite-horizon repeated game have a much
richer action space than in a single-shot game, since their actions can depend
upon the outcomes of the previous rounds, and even upon their internal states
(possibly influenced by the random coins flipped in previous rounds).
Therefore, we need to formalize exactly what this action spaces consists of –
in our paper, the players are assumed to delegate their play to algorithms,
possibly randomized, that make their choices for them. We offer a general
definition below.

######  Definition 5 (Game Playing Algorithm).

A Game Playing Algorithm or GPA for a finite-horizon repeated game ($G$, $T$)
is defined as a list of $T$ finite-time deterministic algorithms, one for each
round of play, and a collection of unrealized random coins. The $t$-th
deterministic algorithm $f_{t}$ takes as input the actions played by all the
players in the first $t-1$ rounds, as well as the results of all coin flips
the GPA’s player may possibly need throughout all the rounds of play 222The
fact that the algorithms of different rounds share randomness allows
correlations in the probabilistic decisions made across rounds. Implicitly, it
computes a distribution in $\Delta^{n}$ over the $n$ actions to be played in
the $t$-th round, and then uses the randomness to select and play a particular
action.

We say that a Game Playing Algorithm is deterministic if it does not use any
random coins. It is worth noting that each deterministic GPA can be rewritten
as/ shown to be equivalent to a look-up table , implying that operationally,
the set of deterministic GPAs is finite. We will repeatedly use the set of
look-up tables as a canonical representation of deterministic GPAs.

To give further intuition for the richness of GPAs, consider some arbitrary
game where the leader player has two moves, $i_{1}$ and $i_{2}$, and the
follower player has two moves, $j_{1}$ and $j_{2}$. We provide some mechanics
that GPAs support, along with (informal) descriptions of example leader GPAs
exhibiting these mechanics:

  * •

History-dependency: play $i_{1}$ as long as the follower plays $j_{1}$; if the
follower ever plays $j_{2}$, play $i_{2}$ for all remaining rounds.

  * •

Time-dependency: play $i_{2}$ on the final round, and $i_{1}$ on all other
rounds.

  * •

Randomness: flip a new coin each round; play $i_{1}$ if heads, and $i_{2}$ if
tails.

  * •

_Correlated_ randomness: flip a coin at the start of the game. If heads, in
all $T$ rounds of the game, flip a new coin, and play $i_{1}$ if heads and
$i_{2}$ if tails. Otherwise, in all $T$ rounds of the game, play $i_{1}$.

######  Observation 1.

The set of GPAs can equivalently be seen to be probability distributions over
deterministic look-up tables. However, we keep this definition, since it
offers a framework for succinct representations for these algorithms (for
example - no-regret algorithms).

We are almost ready to define a notion of SE for repeated bimatrix games.
However, it is not a priori obvious that there exists a well defined best-
response Game Playing Algorithm for the follower given a fixed GPA for the
leader. We show that a best-response GPA is in fact well defined, and that, in
fact, it can be found among the set of deterministic (though potentially
adaptive) GPAs. This result is analogous to the result in single-shot games
that there always exists a best response pure strategy, and in fact uses this
connection to work backward from the last round of play. Another way of seeing
this result is to observe that finite-horizon repeated games can be rewritten
as a large normal form game, implying the result. The proof can be found in
Appendix A.1.

######  Lemma 1.

For any leader GPA by Player 1, there exists a best response Game Playing
Algorithm by Player 2 within the set of deterministic lookup table GPAs, which
is a finite set. Therefore, a best response is well-defined in the GPA space.

It is even less apparent that an optimal leader algorithm to commit to is well
defined – we provide a constructive proof of existence.

######  Theorem 1.

There exists an optimal GPA $\mathcal{P}$ for the leader such that no other
GPA, when paired up with its corresponding follower best response, gives the
leader a better payoff than $\mathcal{P}$ does against the corresponding
follower best response.

The key idea behind this proof is to observe that finite-horizon repeated
games can be rewritten as normal form games, albeit at the cost of an
exponential blow-up in the number of actions. This is not a new idea; [22]
makes the same observation in the context of Extensive-form games, which
generalize finite-horizon repeated games. For sake of completeness, we sketch
out the proof of this result in Appendix A.2.

We are finally ready to introduce the central solution concept of our paper.

######  Definition 6 (Approximate Stackelberg GPA).

For some $c>0$, we say that a leader GPA $\mathcal{P}$ obtaining a payoff of
$p$ against a best-responding follower is a $c$-approximate Stackelberg GPA
for the finite-horizon repeated game $G,T$ if no other leader GPA can
guarantee a payoff greater than $p+c$ against a best-responding follower. Note
that the approximation definition only allows slack in the leader’s payoff–we
still require that the follower is _exactly_ best-responding.

The precise computational question that we answer affirmatively in this paper
is thus as follows: given a two player game $G$ (parameterized by the number
of actions $n$ and the granularity $A$), and a time horizon $T$, does there
exist an efficient algorithm to find an approximate Stackelberg GPA for the
leader?

###  3.1 Separation of Repeated Game Stackelberg From Single-Round Stackelberg

Even in a single-shot game, the Stackelberg leader can often expect value
higher than than of their best Nash equilibrium. As being a leader in a
single-shot game is so powerful, a natural question to ask is if repeated
rounds can really strengthen the leader’s hand. In particular, one might
observe that simply committing to play the single-shot Stackelberg strategy in
each round will guarantee the leader the Stackelberg value of the single-shot
game on average. We address this question by showing an example where a leader
in a finite-horizon repeated game can do strictly better on average than
getting their single-shot Stackelberg value each round. For our example, we
focus on the simple and well-studied Prisoner’s Dilemma game $\mathcal{PD}$.
We will set the row player to be the leader and the column player to be the
follower. The first move for both players represents cooperating, while the
second move represents defecting.

$\begin{bmatrix}(3,3)&(0,5)\\\ (5,0)&(1,1)\end{bmatrix}$

######  Lemma 2.

The game $\mathcal{PD}$ repeated for $T$ rounds with $T\geq 3$ exhibits a
constant separation between the Stackelberg value and the leader value
obtained by playing the single-shot game’s Stackelberg strategy in each round.

The intuition is as follows: in the single-round case, a Stackelberg leader
can do no better than get payoff $1$, as the follower has a dominant strategy
of defecting. However, in a multi-round game, the leader can incentivize the
follower to cooperate a majority of the time by promising to occasionally
cooperate themselves, and threatening to defect if the follower does not play
along. We include a full proof of the above lemma, along with further
discussion, in Appendix A.3. We also include an explicit construction of an
approximate Stackelberg GPA for $\mathcal{PD}$ using our techniques in
Appendix E.

##  4 Algorithms for Approximate Stackelberg Equilibrium

We now state and prove the main result of our paper, which gives efficient
algorithms for computing approximate Stackelberg GPAs.

######  Theorem 2.

We give two different efficient algorithms to compute approximate Stackelberg
GPAs for a given bimatrox game repeated for $T$ rounds:

  * •

An algorithm with running time polynomial in $n,\ \log A,\ \log T$ that finds
a $\left(\frac{2^{\text{poly}(n)}\cdot\text{poly}(A)}{T}\right)$-approximate
Stackelberg GPA.

  * •

A randomized algorithm with running time polynomial in $n,\ \log A,\ T$ that
finds a $O\left(\frac{\sqrt{A}}{T^{0}.25}\right)$-approximate Stackelberg GPA
(with high probability).

We begin by describing an LP for any bimatrix game which upper bounds the
value guaranteed by any leader GPA for any $T$. Then, we describe a way to
construct a GPA using the LP solution such that a best-response by the
follower results in a leader payoff closely approximating the LP value. We
observe that, while the setup of our LP is different than that in [34], the
optimal value is always the same (for a certain regime in their paper). The
value of the LP solution in [34] is equal to the value of the optimal SE
strategy in infinite-horizon repeated games. Thus, in finding an approximation
to the LP upper bound here, we are not only approximating the best Stackelberg
strategy for any finite $T$ but also the best Stackelberg straetgy for an
infinite-horizon repeated game.

###  4.1 An LP Upper Bound

We describe the construction of the linear program for any bimatrix game.
First, we precompute the “threat” value $V$ of the column player along with
the associated strategy for the row player $x^{*}$, which we call the threat
strategy. This is defined as the minimum payoff that the column player can
receive by best responding to the row player’s strategy in the static setting
i.e. $V:=\min_{x\in\Delta^{n}}\max_{j}x^{\intercal}M_{2}e_{j}$ (recall that
$M_{2}$ is the payoff matrix of the follower/ column player). Note that this
is equal to the value of a hypothetical zero-sum game between the two players
where the row player’s payoff is changed to be the negative of the payoff of
the column player, and can hence be computed in polynomial time, as can the
associated strategy $x^{*}$ of the row player. The reason we call this the
threat value is that the row player could find a strategy that ensures the
column player can do no better than $V$ against this strategy in any given
round of play.

Next, we compute the solution of a linear program whose variables are weights
$\\{\alpha_{i,j}\\}_{i,j}$ attached to each action pair in $\\{i,j\\}^{2}$.
Intuitively, the point of the linear program is to find a prescribed
probability distribution over the action pairs that maximizes the payoff of
the leader subject to the follower receiving at least their threat value.

$\displaystyle\max\sum_{i,j}M_{1}(i,j)\alpha_{i,j}\qquad\qquad\alpha\in\mathbb{R}^{n}$
subject to $\displaystyle\sum_{i,j}M_{2}(i,j)\alpha_{i,j}\geq V$
$\displaystyle\sum_{i,j}\alpha_{i,j}=1$ $\displaystyle\alpha_{i,j}\geq
0\qquad\qquad\text{ for }i,j\in[n]^{2}$

We observe that the above LP is feasible. In particular, the distribution over
action pairs induced by the threat strategy $x^{*}$ of the leader and the best
response of the follower is by construction a feasible point. Additionally,
since the objective describes the payoff generated for the leader by some
distribution over the action pairs, the LP is bounded above by the maximum
payoff of the leader in the game. Consequently, the LP has a well defined
optimum solution, which we also call $\alpha$ with value $OPT_{LP}$.

######  Lemma 3.

The optimum value $OPT_{LP}$ of the LP upper bounds the expected per-round
payoff of a Stackleberg GPA for any $T$.

The key intuition for this proof is that, no matter how intricate GPA behavior
may be thanks to randomness or adaptability, every pair of leader and follower
GPAs induces _some_ distribution over sequences of move pairs. This
distribution, which is analogous to the frequencies we solve for in our LP,
determines the expected payoff for both players. If the expected payoff for
the follower from this move pair distribution is less than their safety value,
they are certainly not best responding; thus, for this distribution to be
feasible, it must adhere to our LP constraint. Given this constraint, our LP
maximizes the payoff for the leader. Therefore, any induced distribution which
corresponds to expected payoff for the leader cannot get value above our LP. A
full proof is given in Appendix C.1.

###  4.2 Construction of a Stackelberg GPA from the LP

A short description of our candidate Stackelberg GPA is as follows — the
leader prescribes a sequence $\mathcal{A}=a_{1},a_{2},\cdots a_{T}$ of action
pairs for both leader and follower to adhere to. In case the follower ever
deviates from this prescribed sequence, the leader then plays the threat
strategy $x^{*}$ for the remaining rounds. This sequence is built based upon
the LP solution $\alpha$ and has two key properties — first, that the
empirical distribution over action pairs in this sequence approximates the
distribution $\alpha$ and second, that at any point in the sequence, the
follower never gains more by deviating from the sequence than following it.

The LP solution gives us the optimal distribution over action pairs that the
follower would be incentivized to play. If the leader and follower had a
shared source of randomness, they could draw from this joint distribution each
round and preserve both optimality for the leader and incentive compatibility
for the follower. However, in our setting, there is no shared source of
randomness or any mechanism for the leader to pre-signal to the follower what
to play before each round. Therefore in our GPA the leader will prescribe a
$T$-round sequence inspired by the LP solution, which preserves follower
rationality while approximating optimality. We call this GPA
$\mathcal{P}^{*}(\alpha)$.

To aid with explicitly describing this sequence, we introduce some notation.
We know that there is a polynomial time algorithm for solving a linear program
with rational coefficients that outputs a rational solution( [30]). All
coefficients in our linear program are rational — in addition, the threat
value $V$ is also a rational number, since it is itself the optimum of a
linear program with rational coefficients. Therefore, we can assume that each
$\alpha_{i,j}$ can be written in canonical form as $\frac{p_{i,j}}{q_{i,j}}$
where $p_{i,j},q_{i,j}\in\mathbb{N}$ and $gcd(p_{i,j},q_{i,j})=1$. For the
next step, we re-index the action pairs from $1$ to $n^{2}$ such that for any
two action pair $k_{1},k_{2}\in[n^{2}]$ with $k_{1}<k_{2}$, we have
$M_{2}(k_{1})\leq M_{2}(k_{2})$. We use this indexing for the action pairs
henceforth. Let $N=LCM(q_{1},q_{2}\cdots q_{n^{2}})$ and let $T=c\cdot N+r$
where $c$ is a natural number and $r\in\\{1,2,\cdots N-1,N\\}$. We assume $T$
is large enough to ensure $c\geq 1$. Additionally, we refer to $N$ as the
cycle length, for reasons that will be clear from the full description of the
GPA $\mathcal{P}^{*}(\alpha)$.

For each action pair $k$, we calculate the number of times $n_{k}$ to
prescribe playing this action pair in the first $c\cdot N$ rounds,
$n_{k}:=\alpha_{k}\cdot cN=c\frac{p_{k}}{q_{k}}N$. By definition, $N$ is
divisible by $q_{k}$ and hence $n_{k}$ is a natural number. Further, note that
$\sum_{k}n_{k}=\sum_{k}\alpha_{k}\cdot cN=(\sum_{k}\alpha_{k})\cdot cN=cN$.
The prescribed sequence for the first $cN$ moves is to play action pair $1$
for the first $n_{1}$ rounds, action pair $2$ for the next $n_{2}$ rounds and
so on until the end of $cN$ rounds. For all the remaining rounds, the GPA
prescribes the action pair that maximizes the follower’s payoff.

The intuition behind this ordering is that the GPA forces through the more
‘painful’ action pairs for the follower at the beginning while promising
rewards for cooperation and threats for defection. As we have required $r\geq
1$, the final round will always allow the follower to get their optimal
possible payoff if they have obeyed the sequence up to this point, which
resolves any “last-round” incentive concerns.

This completes the description of the candidate Stackelberg GPA’s prescribed
sequence. The logic of the GPA itself will be to play according to the
prescribed sequence, as long as the follower has played according the the
prescribed sequence in all previous rounds. If the follower has ever deviated
from the sequence, instead play $x^{*}$, the threat strategy, for all
remaining rounds. This logic is enforced by the functions the GPA is comprised
of. A detailed example construction, which includes explicitly constructing
the functions for the GPA, is shown in Appendix E.

The following lemma uses backward induction and the ordering of the action
pairs in the prescribed transcript to show that it is in the follower’s best
interest to follow the prescription. The proof of this lemma can be found in
Appendix C.2.

######  Lemma 4.

Following the prescribed sequence for all $T$ rounds of play is a best-
response GPA (for the follower) to the candidate leader GPA described above.

Next, we show a lower bound on the payoff of the leader if the follower
follows the prescribed transcript.

######  Lemma 5.

If the follower obeys the prescribed sequence, the resulting payoff for the
leader will get a $2N/T$ approximation to the optimum value $OPT_{LP}$ of the
LP.

###### Proof.

In the first $cN$ rounds, the empirical frequencies of the action pair in the
resulting transcript (when the follower obeys the prescribed sequence) exactly
equals the probability distribution $\alpha$. Therefore, the average payoff of
the leader in the first $cN$ rounds equals $\sum_{i,j}M_{1}(i,j)\alpha_{i,j}$,
which is the objective of the LP for the optimal solution. In the remaining
rounds, the difference in the average payoff and the LP’s optimum objective is
at most $2$ — therefore, the total payoff is at least $OPT_{LP}.(cN+r)-2r$.
Thus, we have a $2r/T\leq 2N/T$\- approximation to the LP optimum, where the
last inequality comes from $r\leq N$. ∎

Putting together Lemmas 3 and 5, our candidate GPA is shown to guarantee a
payoff to the leader that is a $\frac{2N}{T}$-approximation to the value
generated by any GPA against a rational follower 333The follower may choose
some other equally good best response GPA – however in the definition of
Stackleberg equilbria/ GPA, the follower always picks the best possible option
from the leader’s perspective while breaking ties, so the leader’s candidate
GPA is in fact guaranteed this approximation factor. More generally, our
approximation factor can be rewritten as $\frac{f(n,b)}{T}$ where
$f(n,b)=2^{\text{poly}(n,b)}=2^{\text{poly}(n)}\cdot\text{poly}(A)$ since the
number of bits used to represent $N$ is polynomial in $n$ and $b$ (recall that
$b$ is the number of bits used to represent each payoff value)

Additionally, the algorithm to construct the GPA solves a linear program that
is polynomial in the size of the game, and only does counting operations on
$T$, and is therefore a polynomial in $n,b,\log T$ algorithm 444Finding an
implicit representation of GPA can be done in time polynomial in $\log T$, by,
say, using a for loop. However, explicitly writing the GPA as $T$-functions,
one for each round, would still take time linear in $T$.

We complement this result by showing in Appendix C.4 that it is impossible to
exactly achieve the LP upper bound. Specifically, we show that a
$\frac{1}{T}$-approximation to the LP upper bound is inevitable, showing that
we have reached the limits of the LP based approach with respect to the
dependence upon the time horizon $T$.

###  4.3 Randomization for Faster Convergence

We complete the proof of the theorem by showing that the judicious use of
randomization can guarantee convergence to optimality which is independent of
the number of actions $n$. In our current candidate GPA, the rate of
convergence to optimality depends exponentially upon $n$.

To get better dependence upon $n$, we use randomized sampling — replacing the
probability distribution $\alpha$ by the empirical average of a sufficiently
large number of samples allows us to use standard concentration inequalities
to approximate the leader and follower’s values with high probability (since
both of these are linear functions of the probability distribution). While
simply approximating the leader’s payoff in this way is sufficient, we must
ensure that the follower’s payoff is no lower than in the LP distribution.
Thus, we tweak the empirical distribution slightly to ensure this. Finally, we
need to add an extra “treat” for the follower at the final round in order to
ensure that they are incentivized to behave at every time step. Thus, instead
of drawing $T$ samples, we will draw $T-1$ samples to leave room for this
treat in the GPA construction. Using this approach, we are able to create a
GPA which has strong guarantees for any $T$, independent of $n$ (with high
probability).

Let us define $\widehat{\alpha}$ as the empirical distribution over action
pairs constructed by drawing $T^{\prime}=T-1$ I.I.D samples $a_{1},a_{2}\cdots
a_{T^{\prime}}$ from $\alpha$.

The payoff of both the leader and follower are a linear combination over the
$T^{\prime}$ random variables corresponding to the draws. Thus, we use the
Hoeffding bound and the the union bound to claim that the following two
inequalities hold with high probability (at least $1-\frac{4}{e^{50}}$ ).

$\left|OPT_{LP}-\frac{1}{T^{\prime}}\sum_{k}M_{1}(a_{k})\right|\leq\frac{10}{\sqrt{T^{\prime}}}$
$\left|V-\frac{1}{T^{\prime}}\sum_{k}M_{2}(a_{k})\right|\leq\frac{10}{\sqrt{T^{\prime}}}$

While the first inequality adds to the approximation to optimality, the second
inequality is a more serious matter. This is because the threat offered by the
leader is only credible if the prescribed transcript offers something no worse
than the threat value. In particular, if we already have
$V^{\prime}:=\frac{1}{T^{\prime}}\sum_{k}M_{2}(a_{k})\geq V$, then we can
directly use this empirical distribution (at least for the first $T-1$
rounds). However, the other case demands some modifications to
$\widehat{\alpha}$. In this event, $\widehat{\alpha}$ is tweaked in the
following way: starting with the lowest-value pair for the follower in the
distribution, we will replace move pairs with the optimal move pair for the
follower (which gives the follower value $m$). We will stop when the average
value for the follower over all the move pairs is at least $V$. We refer to
the modified version of $\widehat{\alpha}$ as $\widehat{\alpha}^{\prime}$.

This process will certainly terminate with the follower getting the required
average value, as in the worse case we could simply make $T^{\prime}$ swaps,
resulting in the follower getting expected value $m>V$ 555The case of $m=V$
can be dealt with as a trivial special case. By construction , the follower’s
average value in $\widehat{\alpha}^{\prime}$ is at least $V$.

However, each swap could replace something where the leader gets payoff of up
to $1$ with something where the leader gets payoff of as little as $-1$. Thus,
each swap could contribute up to $2$ to the leader’s total additive loss.
$T^{\prime}$ swaps would imply an additive loss of $2T^{\prime}=2T-2$.
Therefore, in order to retain an approximation for the leader payoff, we must
bound the number of swaps we will make in this process.

Let $c:=m-V$. Note that $c$ is always positive. Now, we will consider two
cases: where $c\geq\frac{\sqrt{10}}{T^{\prime 0.25}\sqrt{A}}$, and where
$c<\frac{\sqrt{10}}{T^{\prime 0.25}\sqrt{A}}$.

In the first case, we claim that if this gap is large enough, then we only
need to do relatively fewer swaps since each swap has a large effect, leading
to a suitably small loss for the leader.

In the other case, where $c<\frac{\sqrt{10}}{T^{\prime 0.25}\sqrt{A}}$, we
argue that the follower’s threat value is so close to their maximum possible
payoff that most of the probability mass of $\widehat{\alpha}$ is already on
the maximum payoff action pair, upper bounding the number of swaps possible.

Based on this reasoning, the following claim bounds the loss in leader payoff
due to the swaps. The proof of this claim can be found in Appendix C.3.

######  Claim 1.

The difference in average-per-round leader payoffs between $\widehat{\alpha}$
and $\widehat{\alpha}^{\prime}$ is at most $\frac{\sqrt{10A}}{T^{\prime
0.25}}$.

Similar to $\mathcal{P}^{*}(\alpha)$, we can now put together a GPA along
similar lines based upon $\widehat{\alpha}^{\prime}$ instead. We will order
$\widehat{\alpha}^{\prime}$ in increasing order of payoff for the follower and
prescribe actions in this order from round $1$ to round $T-1$. A reasonable
question to ask is why we picked $T-1$ pairs instead of directly picking $T$
pairs. As with the construction in section 4.2, we must ensure that follower
is not tempted to deviate at any time step, even if there are few moves left
and deviation will garner a significant payoff on that round. We do this by
adding in a $T$-th move pair, which is another maximum payoff move pair for
the follower (garnering them a payoff of $m$). As in the previous leader GPA
described, the leader will begin playing the threat strategy $x^{*}$ every
round if the follower ever deviates.

Careful analysis along the lines of the proof of Lemma 4 shows that the a
best-responding follower will obey the prescribed actions. Thus, the average
payoff of the leader will be their average payoff over the move pairs included
in the leader GPA. The leader’s payoff for the $T$th added move pair is at
least $-1\geq OPT_{LP}-2\geq OPT_{LP}-2\sqrt{A}\geq OPT_{LP}-\sqrt{10A}$.
Calculating the total average payoff allows us to lower bound it by
$OPT_{LP}-\frac{4\sqrt{10A}}{T^{0.25}}$.

Thus, this sampling based approach completes the proof of Theorem 2.

Not only are both of the GPAs described efficiently computable, they have
efficiently computable best-responses by the follower. A proof of this claim
can be found in the Appendix, in Lemma 11. This is not to be taken for
granted; in Lemmas 9 and 10, we show that for a general leader strategy, even
if it is restricted to run in polynomial time, finding a poly-time best-
response for the follower, and finding the expected value of the resulting
game for the leader, is NP-hard. We prove this hardness by embedding a
3-coloring instance into the repeated two player game problem.

##  5 Hardness of Computing An Approximate Stackelberg GPA in 3-Player Games

While we have thus far considered only two-player Stackelberg games, the
notion of an $n$-player Stackelberg game is also well-defined. In an
$n$-player Stackelberg game, there is a strict ordering among all players. The
first player in order makes a commitment, which all players get to see. Then
the second player in order makes a commitment, and so on until the final
player. In a single-shot game, this commitment is a (possibly mixed) strategy,
while in the repeated games setting this commitment is a GPA. The SE is
achieved when the first player in order commits to something which maximizes
their expected value, given that all the remaining players best-respond in
turn. The added complexity with more than two players is that, when making
commitments, players must now reason about not just how a single follower
might respond to them but how the follower might try to affect players further
down the line. When we discuss additive approximations, we are still referring
only to the approximation to the payoff of the very first player in line. All
followers are assumed to be perfectly best-responding.

We must be careful when discussing hardness in algorithm space; we cannot
simply say that constructing an optimal GPA is hard just because finding the
optimal move commitments in a GPA is hard. This is because GPAs are composed
of algorithms, so the hard computational work could be delegated to the GPA
itself. Thus, our hardness result for three-player approximation tells us two
things: 1) finding the approximate _value_ of a Stackleberg equilibrium in the
three-player setting is hard, and 2) finding an approximately optimal _GPA_
for Player 1 in the three-player setting is hard, as long as all GPAs are
restricted to run in poly-time.

The hardness result we build upon on is from [14], where Conitzer and Sandholm
prove that computing a single-shot SE for three-player games is NP-hard. While
not explicitly mentioned in their top-level results, their proof in fact shows
that approximating a single-shot three-player SE is also hard. This hardness
of approximation result does not immediately imply hardness of approximation
for the repeated setting; as we have previously shown in the two-player case,
the Stackelberg GPA may look very different from the single-shot Stackelberg.
Thus we cannot perform a trivial reduction from the single-shot problem to the
repeated-game problem. However, we can still utilize Conitzer and Sandholm’s
work to our benefit by looking closely at their results, and proving that
their hard instance in fact extends to approximation in repeated games.

######  Theorem 3.

In three-player finite-horizon repeated games over $T$ rounds, there exists no
polynomial in $n,A,T$ time algorithm computing a
$\left(\frac{A^{k}}{T^{\frac{1}{k}}}\right)$-additive approximation 666An
earlier version of this paper incorrectly claimed to rule out algorithms with
a $\Omega\left(\frac{A^{k}}{T^{\frac{1}{k}}}\right)$ additive approximation,
the statement of the result is therefore corrected, although the proof, and
implication, of the result remains unchanged  to the Stackelberg value of the
game unless $P=NP$. Here, $k$ is any natural number.

Conitzer and Sandholm prove hardness for three-player single-shot games via a
reduction from balanced vertex cover. They construct a three-player payoff
matrix from a graph for which Player 1 can get a nonzero payoff iff there
exists a vertex cover in the graph of size $\frac{|V|}{2}$. We present the
input transformation they utilize in the box below:

Function $f$ Input: Graph $G=(V,E)$ with $n$ vertices and $m\leq n^{2}$ edges
Output: A three-player game matrix where Players 1 and 2 have $n$ pure
strategies and Player 3 has $m+n+1$ pure strategies. Construction: Players 1,
2 and 3 will all have a pure strategy associated with every vertex in the
graph: $r_{v}$, $s_{v}$ and $t_{v}$ respectively. In addition, Player 3 will
have a pure strategy associated with every edge in the graph, $t_{e}$.
Finally, Player 3 will have one last strategy $t_{0}$. The utilities are
listed below: $\mu_{1}(r,s,t_{0})=\mu_{2}(r,s,t_{0})=1$
$\mu_{1}(r,s,t_{k})=\mu_{2}(r,s,t_{k})=0$, $k\neq 0$ $\mu_{3}(r,s,t_{0})=1$
$\mu_{3}(r_{v},s_{v},t_{v})=\frac{n}{n-2}$, $t_{v}\neq r_{v}$ and $t_{v}\neq
s_{v}$ $\mu_{3}(r_{v},s_{v},t_{v})=0$, $t_{v}=r_{v}$ and/or $t_{v}=s_{v}$
$\mu_{3}(r_{v},s_{v},t_{e})=\frac{n}{n-2}$, $r_{v}$ not adjacent to $t_{e}$
$\mu_{3}(r_{v},s_{v},t_{e})=0$, $r_{v}$ adjacent to $t_{e}$

Note that this input transformation works in time polynomial in $n$. Conitzer
and Sandholm used this transformation to reduce from Balanced Vertex Cover to
Exact One-Round Three-Player Stackleberg. We will use the same transformation
$f$ in our reduction to reduce from BALANCED-VC, but our correctness proof
will require some additional heavy lifting. We also additionally define $T$ to
be some suitably chosen polynomial in $n$.

Let us formally define the problem BALANCED-VC. The problem takes as input a
graph $G$. It outputs YES if the graph has a vertex cover of size at most
$\frac{n}{2}$. It outputs NO if the graph does not have any vertex covers of
size at most $\frac{n}{2}$. This problem is known to be NP-complete, through a
simple reduction from the Vertex Cover problem [19].

Consider the decision problem APPROX-STACK, that takes as input a three player
game $G$ with $n$ actions per player and playoffs of granularity $1/A$, a time
horizon $T$ and a real number $V$. The problem is to distinguish between games
that have Stackelberg value greater than or equal to $V$ (Yes) and games that
have Stackelberg value less than or equal to $V-\frac{A^{k}}{T^{\frac{1}{k}}}$
(No).

We will now construct a reduction from BALANCED-VC to APPROX-STACK. The
reduction will be as follows: on input graph $G$, apply the transformation $f$
described above to get a game matrix $M$, then define a problem in APPROX-
STACK as $(M,T)$ with value $V=1$ and $T=n^{ck+k^{2}}$ with $c=5$. We note
that the granularity $A$ of the game is $n-2$, upper bounded by $n$. If the
Stackelberg value is greater than or equal to $1$, we answer that there is a
vertex cover of size $\frac{|V|}{2}$ and if the Stackelberg value is less than
$1-\frac{A^{k}}{T^{\frac{1}{k}}}$, we will answer that there is no vertex
cover of size $\frac{|V|}{2}$. Note that
$1-\frac{A^{k}}{T^{\frac{1}{k}}}>1-\frac{n^{k}}{n^{c+k}}=1-\frac{1}{n^{c}}$,
and therefore such an algorithm for APPROX-stack will always answer that there
is a balanced vertex cover if the Stackelberg value is $\geq 1$ and always
answer that there is a no balanced vertex cover if the Stackelberg value is
less than $1-\frac{1}{n^{c}}$.

We will now prove that this is a valid reduction via the following lemmas.

######  Lemma 6.

If there exists a vertex cover of size $\frac{n}{2}$ in $G$, then the game
$M,T$ has a value of at least 1.

The proof of this lemma, the easier half of our proof, builds directly upon
the ideas in [14]. The proof can be found in Appendix D.1.

Proving the other half is significantly harder. To aid in this proof, we first
claim an auxiliary result, the proof of which appears later. This result shows
that when every vertex cover is of size at least $n/2+1$, then Player 3 always
has a response to any strategies employed by the first two players in a given
round that guarantees a payoff that is inverse polynomially better than 1.

######  Lemma 7.

If there exists no vertex cover in $G$ with size $\frac{n}{2}$, then for every
pair of mixed strategies by Players 1 and 2 in a given round, Player 3 can
always play a move that garners them an expected value strictly greater than
$1+\frac{1}{(n-2)(n^{c-1})}$

We use this critical observation to prove the below lemma and complete the
proof of Theorem 3. The proof of this lemma can be found in Appendix D.2.

######  Lemma 8.

If there does not exist a vertex cover in $G$ with size $\frac{n}{2}$, then
the game $M,T$ has Stackelberg value strictly less than $1-\frac{1}{n^{c}}$.

###### Proof.

Consider all of the $n$ moves that Player 1 can play, each associated with a
vertex from the original graph $G$.

Consider any triplet of GPAs that Players 1 and 2 commit to (in order) and
player 3 best responds to. Note that Lemma 7 implies that Player 3 must get
expected value (averaged over the rounds) strictly greater than
$1+\frac{1}{(n-2)(n^{c-1})}$ in this equilibrium (since they could obtain this
value by just picking the best response in each round myopically).

$\mathbb{E}\left[\sum_{t\in T}\textit{Payoff of Player
3}\right]>1+\frac{1}{(n-2)n^{c-1}}$

By linearity of expectation:

$\sum_{t\in T}\mathbb{E}\left[\textit{Payoff of Player
3}\right]>1+\frac{1}{(n-2)n^{c-1}}$

Let Player $3$ play action $t_{0}$ with probability $p_{t}$ in round $t$.
Then, $\frac{1}{T}\sum_{t}p_{t}$ is the fraction of time Player 3 plays
$t_{0}$ and $1-\frac{1}{T}\sum_{t}p_{t}$ is the expected fraction of time
Player 3 does _not_ play $t_{0}$. In the case of Player 3 playing $t_{0}$,
they will get a payoff of $1$. Otherwise, they will get a payoff of at most
$\frac{n}{n-2}$. Thus, we can write

$\mathbb{E}\left[\sum_{t\in T}\textit{Payoff of Player 3}\right]\leq
1\cdot\frac{1}{T}\sum_{t}p_{t}+\frac{n}{n-2}\cdot\left(1-\frac{1}{T}\sum_{t}p_{t}\right)$

Putting our two inequalities together, we have

$1\cdot\frac{1}{T}\sum_{t}p_{t}+\frac{n}{n-2}\cdot\left(1-\frac{1}{T}\sum_{t}p_{t}\right)>1+\frac{1}{(n-2)n^{c-1}}$

Rearranging:

$\left(\frac{2}{n-2}\right)\left(\frac{1}{T}\sum_{t}p_{t}\right)<-1-\frac{1}{(n-2)n^{c-1}}+\frac{n}{n-2}$
$\frac{1}{T}\sum_{t}p_{t}<-\frac{n-2}{2}-\frac{1}{2n^{c-1}}+\frac{n}{2}$
$\frac{1}{T}\sum_{t}p_{t}<1-\frac{1}{2n^{c-1}}$

Note that as Player 1’s payoff every round is determined solely by whether or
not Player 3 plays $t_{0}$, Player 1’s payoff can be written as

$1\cdot\frac{1}{T}\sum_{t}p_{t}$

So, Player 1’s expected average payoff (averaged over $T$ rounds) is strictly
less than $1-\frac{1}{2n^{c-1}}$, which for $c\geq 2$ and $n\geq 2$ is $\leq
1-\frac{1}{n^{c}}$, completing our proof. ∎

######  Observation 2.

For infinite-horizon Stackeleberg games with three players, finding an
approximate equilibrium is NP-hard.

While the mechanics of GPAs are explicitly tailored to deal with finite-
horizon games, we observe that a similar line of reasoning implies hardness of
approximation for the infinite-horizon case, as long as the strategies used by
the players have well-defined limit-averaged payoffs. If there exists a pair
of distributions by Players 1 and 2 that incentivize $t_{0}$ on any single
round, they can commit to playing these distributions infinitely, ensuring
that Player 1 gets an average payoff of $1$. If there does not exist such a
pair of distributions, then by Lemma 7, Player 3’s time-averaged payoff for
playing $t_{0}$ every round will always be well-separated from some other move
by some $\frac{1}{\text{poly}(n)}$. Therefore, they must play moves other than
$t_{0}$ with frequency (in the limit average) $\frac{1}{\text{poly}(n)}$,
which implies that Player 1’s limit-average payoff will be bounded away from
$1$ by $\frac{1}{\text{poly}(n)}$.

## References

  * ATS [17] Bo An, Milind Tambe, and Arunesh Sinha.  Stackelberg security games (ssg) basics and application overview.  Improving Homeland Security Decisions, page 485, 2017.
  * BAH [85] Michel Le Breton, A. Alj, and Alain Haurie.  Sequential stackelberg equilibria in two-person games.  Journal of Optimization Theory and Applications, 59:71–97, 1985\.
  * BBH+ [17] Branislav Bošanský, Simina Brânzei, Kristoffer Arnsfelt Hansen, Troels Bjerre Lund, and Peter Bro Miltersen.  Computation of stackelberg equilibria of finite sequential games.  ACM Trans. Econ. Comput., 5(4), dec 2017.
  * BBHP [15] Maria-Florina Balcan, Avrim Blum, Nika Haghtalab, and Ariel D. Procaccia.  Commitment without regrets: Online learning in stackelberg security games.  In Proceedings of the Sixteenth ACM Conference on Economics and Computation, EC ’15, page 61–78, New York, NY, USA, 2015. Association for Computing Machinery.
  * BCI+ [10] Christian Borgs, Jennifer Chayes, Nicole Immorlica, Adam Tauman Kalai, Vahab Mirrokni, and Christos Papadimitriou.  The myth of the folk theorem.  Games and Economic Behavior, 70(1):34–43, 2010.
  * BEDL [06] Avrim Blum, Eyal Even-Dar, and Katrina Ligett.  Routing without regret: On convergence to nash equilibria of regret-minimizing algorithms in routing games.  In Proceedings of the twenty-fifth annual ACM symposium on Principles of distributed computing, pages 45–52, 2006.
  * BK [85] Jean-Pierre Benoit and Vijay Krishna.  Finitely repeated games.  Econometrica, 53(4):905–922, 1985.
  * Blu [98] Avrim Blum.  On-line algorithms in machine learning.  Online algorithms, pages 306–325, 1998.
  * BM [07] Avrim Blum and Yishay Monsour.  Learning, regret minimization, and equilibria.  2007\.
  * CBL [06] Nicolo Cesa-Bianchi and Gábor Lugosi.  Prediction, learning, and games.  Cambridge university press, 2006.
  * CD [06] Xi Chen and Xiaotie Deng.  Settling the complexity of two-player nash equilibrium.  In 2006 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS’06), pages 261–272. IEEE, 2006.
  * CK [11] Vincent Conitzer and Dmytro Korzhyk.  Commitment to correlated strategies.  In Proceedings of the Twenty-Fifth AAAI Conference on Artificial Intelligence, AAAI’11, page 632–637. AAAI Press, 2011.
  * ČLBA [21] Jakub Černỳ, Viliam Lisỳ, Branislav Bošanskỳ, and Bo An.  Computing quantal stackelberg equilibrium in extensive-form games.  In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 5260–5268, 2021.
  * CS [06] Vincent Conitzer and Tuomas Sandholm.  Computing the optimal strategy to commit to.  In Proceedings of the 7th ACM conference on Electronic commerce, pages 82–90, 2006.
  * DGP [09] Constantinos Daskalakis, Paul W Goldberg, and Christos H Papadimitriou.  The complexity of computing a nash equilibrium.  SIAM Journal on Computing, 39(1):195–259, 2009.
  * FS [99] Yoav Freund and Robert E Schapire.  Adaptive game playing using multiplicative weights.  Games and Economic Behavior, 29(1-2):79–103, 1999.
  * Hic [35] J. R. Hicks.  The Economic Journal, 45(178):334–336, 1935.
  * HPS [14] Joseph Y Halpern, Rafael Pass, and Lior Seeman.  The truth behind the myth of the folk theorem.  In Proceedings of the 5th conference on Innovations in theoretical computer science, pages 543–554, 2014.
  * Kar [72] Richard M Karp.  Reducibility among combinatorial problems.  In Complexity of computer computations, pages 85–103. Springer, 1972.
  * KDB [14] Walid Krichene, Benjamin Drighes, and Alexandre Bayen.  On the convergence of no-regret learning in selfish routing.  In International Conference on Machine Learning, pages 163–171. PMLR, 2014.
  * KM [20] Jan Karwowski and Jecek Mań dziuk.  Double-oracle sampling method for stackelberg equilibrium approximation in general-sum extensive-form games.  Proceedings of the AAAI Conference on Artificial Intelligence, 34(02):2054–2061, apr 2020.
  * LC [10] Joshua Letchford and Vincent Conitzer.  Computing optimal strategies to commit to in extensive-form games.  In Proceedings of the 11th ACM Conference on Electronic Commerce, EC ’10, page 83–92, New York, NY, USA, 2010. Association for Computing Machinery.
  * LGH+ [22] Niklas Lauffer, Mahsa Ghasemi, Abolfazl Hashemi, Yagiz Savas, and Ufuk Topcu.  No-regret learning in dynamic stackelberg games, 2022.
  * LMC+ [12] Joshua Letchford, Liam MacDermed, Vincent Conitzer, Ronald Parr, and Charles L. Isbell.  Computing stackelberg strategies in stochastic games.  SIGecom Exch., 11(2):36–40, dec 2012.
  * LS [05] Michael L Littman and Peter Stone.  A polynomial-time nash equilibrium algorithm for repeated games.  Decision Support Systems, 39(1):55–66, 2005.
  * MTS [12] Janusz Marecki, Gerry Tesauro, and Richard Segal.  Playing repeated stackelberg games with unknown opponents.  In Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems - Volume 2, AAMAS ’12, page 821–828, Richland, SC, 2012. International Foundation for Autonomous Agents and Multiagent Systems.
  * N+ [07] Noam Nisan et al.  Introduction to mechanism design (for computer scientists).  Algorithmic game theory, 9:209–242, 2007.
  * Nas [51] John Nash.  Non-cooperative games.  Annals of mathematics, pages 286–295, 1951.
  * Rub [16] Aviad Rubinstein.  Settling the complexity of computing approximate two-player nash equilibria.  In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 258–265. IEEE, 2016.
  * S+ [03] Alexander Schrijver et al.  Combinatorial optimization: polyhedra and efficiency, volume 24.  Springer, 2003.
  * SC [73] M. Simaan and J. B. Cruz.  On the stackelberg strategy in nonzero-sum games.  J. Optim. Theory Appl., 11(5):533–555, may 1973.
  * vBA [20] Jakub Černý, Branislav Bosanský, and Bo An.  Finite state machines play extensive-form games.  In Proceedings of the 21st ACM Conference on Economics and Computation, EC ’20, page 509–533, New York, NY, USA, 2020. Association for Computing Machinery.
  * VSZ [10] Bernhard Von Stengel and Shmuel Zamir.  Leadership games with convex strategy sets.  Games and Economic Behavior, 69(2):446–457, 2010.
  * ZT [15] Song Zuo and Pingzhong Tang.  Optimal machine strategies to commit to in two-person repeated games.  In AAAI, 2015.

##  Appendix A Proofs from Section 3

###  A.1 Proof of Lemma 1

Let us define the set $S$ to be the set of all deterministic GPAs which pick
output strategies for each input via a lookup table 777The emphasis on lookup
tables is to have a canonical form for deterministic GPAs so as to prevent
redundancies.. Using our precise definition of GPAs, a GPA is in $S$ iff it is
comprised of $T$ finite-time algorithms, where the $i$th algorithm takes as
input a history of play of the past $i-1$ rounds and directly uses their
lookup table to find what move to output. Note that, as none of the algorithms
take random bits as input, no coin flips can be performed and Player 2 is
always playing a pure strategy. This class of GPAs is therefore parameterized
entirely by a lookup table. There are $n^{2(t-1)}$ possible transcripts of
play that could be inputs to the table, and $n$ possible pure strategies that
could be outputs. Thus there are $n^{n^{2(t-1)}}\leq n^{n^{2T}}$ different
possible $f_{t}$. Every GPA has $T$ such algorithms. Thus we can upper bound
the number of GPAs in $S$ by $n^{n^{2T}T}$. Therefore, $S$ is a finite set.

Now we will prove that, for any leader GPA, the follower has a best response
that lies in $S$. We will proceed by backwards induction, proving the claim
that, beginning at any time $i$, the follower has a response maximizing their
payoff for the remainder of the game which uses no randomness. Additionally,
we will also show (as part of the same induction hypothesis) that among all
best responses by the follower, a best response that uses no randomness
beginning at time $i$ is in fact optimal for the leader.

Base case: At round $T$, regardless of the previous transcript of play, there
exists some deterministic strategy for Player 2 which maximizes payoff for the
remainder of the game. Since this is the final round, Player 1 can no longer
adapt to Player 2’s moves. Therefore Player 2 can do no better than maximizing
their payoff, and maximizing Player 1’s payoff subject to the same. Player 2
has access to the leader’s Algorithm at round $T$, called $f_{T}$, to the
transcript of play, and to how Player 1 utilizes randomness in
$f_{1}...f_{T-1}$. Player 2 can therefore compute the distribution over coins
which are used in $f_{T}$. If it is a coin that has never been used before,
then the probability of heads is $\frac{1}{2}$. if it is a coin that has been
used in earlier function(s), then the probability of heads is conditioned on
the realizations of those previous moves. Using this computed distribution on
coin flips, Player 2 can express Player 1’s strategy at round $T$ as a mixed
strategy. It is well known that there exists a pure strategy which is an
optimal response in expectation to any mixed strategy. Therefore, Player 2 can
play a pure strategy at round $T$ which maximizes payoff for the remainder of
the game (and also maximizes Player 1’s payoff subject to the above).

Inductive hypothesis: If there exists some deterministic GPA for Player 2
which maximizes their payoff starting from round $t$, there exists some
deterministic GPA which maximizes their payoff starting from round $t-1$.
Proof: As in round $T$, Player 2 can compute a probability distribution
$s_{1}$ over Player 1’s possible moves at round $t-1$. Using the inductive
hypothesis, for any possible strategy they can play at time $t-1$ and
realization of Player 1’s move, they can also compute a non-random optimal
strategy for rounds $t$ to $T$. The expected payoff of Player 2 from round
$t-1$ to $T$, given they play a (possible mixed) strategy $s_{2}$ at round
$t-1$, will be their expected payoff at round $t-1$, plus the expected
follower payoff $F(O_{t\rightarrow T})$ of their optimal strategy
$O_{t\rightarrow T}$ going forward, conditioned on $s_{2}$ and $s_{1}$. Let
$s^{*}_{1}$ and $s^{*}_{2}$ be the realizations of the distributions. Note
that they are conditionally independent for a fixed $s_{1}$ and $s_{2}$. Then,
the expected payoff of Player 2 can be expressed as

$\sum_{j=1}^{n}\sum_{i=1}^{n}(M_{2}(i,j)+\mathbb{E}[F(O_{t\rightarrow
T})|s_{1}^{*}=i,s_{2}^{*}=j])P(s_{1}^{*}=i)P(s_{2}^{*}=j)$

The outer summation is simply a weighted sum of expected payoffs for all pure
strategies in the support of $s_{2}$. Thus, there is some particular pure
strategy $s^{*}_{2}$ for which $\sum_{i=1}^{k}(M_{2}(i,j)+E[O_{t\rightarrow
T}|s_{1}^{*}=i,s_{2}^{*}=j])P(s_{1}^{*}=i)$ is at least as large as the
expected payoff using $s_{2}$. Therefore, it is optimal for Player 2 to play
this pure strategy in the $t$-th round followed by the optimal deterministic
GPA starting at round $t$, extending the induction hypothesis.

A similar argument can be used to extend the induction hypothesis to include
that there exists an optimal (for Player 1) best response (for Player 2) that
is deterministic — replacing $M_{2}$ by $M_{1}$ allows one to see this. More
explicitly, we have in fact shown that any best response for the follower must
necessarily play one among a set of actions $S$ in the $(t-1)$-th round.
Therefore, we can think of any best response for the follower as playing a
distribution $P(S)$ over actions in $S$ in round $t-1$. By the induction
hypothesis, we know that a leader-optimal best response for the follower
starting at the $t$-th round can be deterministic. Therefore, once the action
$j\in S$ played by the follower in round $t-1$ is fixed, for each action $i$
played by the leader, $O_{t\rightarrow T}$ is a deterministic leader optimal
best response for the follower, with associated payoff $L(O_{t\rightarrow
T})$. Thus, the payoff of the leader is

$\sum_{j\in S}\sum_{i=1}^{n}(M_{1}(i,j)+\mathbb{E}[L(O_{t\rightarrow
T})|s_{1}^{*}=i,s_{2}^{*}=j])P(s_{1}^{*}=i)P(s_{2}^{*}=j)$

Using a similar argument as the one above allows us to conclude that among the
set of best responses, there exists one that is optimal for the leader and is
deterministic in round $t-1$, thus extending the induction hypothesis.

###  A.2 Proof of Theorem 1

Let us assume that our algorithms can draw arbitrarily precise samples from
any real valued distribution. We will show that this assumption is without
loss of generality, even though we only access to a finite number of random
coins.

We begin our proof by observing that every GPA can be rewritten as a
probability distribution over $\mathcal{L}$, the set of deterministic look-up
table GPAs. Since $\mathcal{L}$ is a finite sized set (at most $n^{n^{2T}T}$),
this is a finite support probability distribution. Consequently, the set of
GPAs can be seen to be exactly the probability simplex
$\Delta^{k-1}\in\mathbb{R}^{k}$ where $k=|\mathcal{L}|$ 888The assumption made
at the beginning is key to this statement. To see this, observe that once all
the randomness is realized, we are left with a deterministic GPA, allowing us
to construct a measure over the set of deterministic GPAs. Consequently, the
repeated game can now be viewed as a (large) normal form game where the set of
actions for each player is the respective set of deterministic GPAs.
Therefore, the result of Conitzer and Sandholm [14] implies the existence of a
Stackeleberg Equilibrium for the game. Even more specifically, their
algorithm, built around picking the best solution out of a finite set of
linear programs, implies that there is a optimal distribution for the leader
to play that uses rational weights with a bounded number of bits needed to
represent them. Therefore, we can in fact find a Stackelberg GPA for the
leader that uses only a finite number of random coins, justifying our original
assumption to be without loss of any generality.

###  A.3 Proofs from Section 3.1

We reproduce the $\mathcal{PD}$ matrix here:

$\begin{bmatrix}(3,3)&(0,5)\\\ (5,0)&(1,1)\end{bmatrix}$

The Prisoner’s Dilemma game is a classic illustration of why rational players
may fail to cooperate despite the fact that doing so would lead to mutually
higher payoffs. The only Nash equilibrium is both players defecting and
picking up payoffs $(1,1)$, even though both players would do better by both
cooperating and getting $(3,3)$. These same dynamics remain at play in the
single-round Stackleberg equilibrium because defecting is a strictly dominant
strategy for both players. Thus, regardless of the strategy that the leader
declares, the follower’s best response is always to defect. The leader can
therefore do no better than to commit to defecting themselves and securing a
payoff of $1$.

In a $T$-round repeated game, the leader could simply repeat this strategy to
garner a payoff of $T$. However, they can perform much better by leveraging
the multiple rounds of play. Consider the following leader GPA: cooperate in
every round until the first round that the follower defects. If the follower
ever defects, the leader will defect every round for the remainder of the
game. We show that the follower’s best response GPA is to cooperate for the
first $T-1$ rounds, garnering the leader a payoff of $3(T-1)$.

The follower’s best response GPA is to cooperate for the first $T-1$ rounds
and defect only on the last round, netting the follower a payoff of
$3\cdot(T-1)+5=3T+2$. To prove this is the best response GPA, consider any
other deterministic GPA for the follower (through the proof of Lemma 1, we can
restrict the follower’s selection to deterministic GPAs). If the follower GPA
never has the possibility of defecting at any round, the follower value is
upper bounded by $3T$ and is hence not a best response. Now consider any GPA
for the follower that results in column 2 being played for the first time at
round $t\leq T-1$. The resulting payoff for the follower in such an event is
upper bounded by $3\cdot(t-1)+5+1\cdot(T-t)=T+2t+2$. As $t\leq T-1$, this is
at most $T+2(T-1)+2=3T$. This is again less than the response GPA described
above, completing the optimality proof.

The induced transcript of the game will have both players cooperating until
the last round, where the leader cooperates and the follower defects. This
will get the leader a payoff of $3(T-1)$, which for any $T>1$ is strictly
better than the static Stackelberg strategy.

For any $T>1$, this is strictly better than repeating the single-round
Stackelberg strategy $T$ times. As there exists some multi-round GPA with a
gap in payoff, certainly the multi-round Stackelberg GPA will have at least as
large a gap.

We have now established that the finite-horizon repeated game Stackelberg GPA
is no simple extension of the static Stackleberg strategy. Furthermore, this
example gives us some intuition for what good leader GPAs might look like in
general. The leader was able to leverage a threat (defecting for the remainder
of the game) in order to force the follower to obey a specific move sequence
(follower cooperates, leader cooperates). While implementing this threat would
harm both the leader and the follower, the best-responding follower does
better by obeying the leader than by being exposed to the threat, guaranteeing
that they will follow this sequence. Consequently, the threat will in fact
never be implemented, allowing the leader to reap the rewards of the intended
sequence.

In the above example, the power of multi-round commitments allowed the leader
to force a cooperation strategy which benefited both players approximately
equally. This is similar in spirit to results about Nash Equilibria in
infinite-horizon repeated Prisoner’s Dilemma games. However, the rich space of
GPAs available to the Stackelberg leader in different games includes many
powerful leader strategies which are not in their nature mutually beneficial.
Often, the leader can do better than they would in any coordination strategy
at the expense of the follower. Consider a different leader GPA for the same
Prisoner’s Dilemma game, with two phases: the leader will defect for the first
$\frac{T}{2}$ rounds of play, and cooperate for the final $\frac{T}{2}$ rounds
of play. However, if the follower ever defects in either phase, the leader
will immediately switch to defecting for the remainder of the game. Using a
similar analysis as before, we can see that the follower’s best response is to
defect only on the last round, getting them a payoff of
$3\cdot(\frac{T}{2}-1)+5=\frac{3T}{2}+2$ 999One may observe that while the
follower’s payoff here is lower than in the previous leader strategy, it is
still higher than in the single-round Stackleberg game (where they get value
$T$). This will always be true for Prisoner’s Dilemma Games, as the follower
can always guarantee themselves their equilibrium value no matter what the
leader does. However, it is not generally the case that repeated games benefit
all parties involved; in fact, there exist simple two player repeated games in
which the follower gets arbitrarily worse payoff on average than in the
single-shot case when responding to an optimal Stackelberg leader.. The leader
will now get an improved payoff of
$5\cdot\frac{T}{2}+3\cdot(\frac{T}{2}-1)=4T-3$.

The leader was able to extract more value from the game in this new GPA
because, even though this GPA is worse for the follower than the previous GPA,
playing along with the leader still gets the follower a higher payoff than
disobeying. It is possible for the leader to push it too far, however–if the
leader makes the first phase (in which they defect) last $T-1$ rounds, for
example, then the follower does better by immediately defecting than by
staying silent. Then the leader does no better than they do in the static
Stackleberg strategy. One might wonder exactly how far the leader can push the
envelope and still expect the follower to obey. In section 4, we describe an
LP which solves this sort of optimization problem, and prove that Stackleberg
GPAs constructed this way are optimal. Using the ideas shown there, we can
explicitly construct an approximately optimal Stackelberg strategy for the
finite-horizon repeated Prisoner’s Dilemma game. This construction is shown in
Appendix E.

##  Appendix B General Hardness Of Finding Optimal Response GPAs

When reasoning about the computational complexity of GPAs, we must distinguish
between two types of computational costs: the complexity of constructing a
GPA, and the complexity of actually running that GPA to generate moves. In the
previous sections we have not placed any constraints upon the computational
complexity of the Leader and Follower GPAs, other than to specify that all of
their GPA functions must run in finite time. Furthermore, we have given the
follower arbitrary computational power to construct their best response GPA
after seeing the leader GPA. Despite the rich space of potential GPAs that
this definition allows, we have shown the existence of an approximate
Stackelberg GPA for any game which is computationally efficient in all
possible notions of the word; not only does the leader’s GPA run in polynomial
time, the follower can find a poly-time best response to it in polynomial time
(Lemma 11). Thus, our LP-inspired GPA is not only approximately optimal in the
general setting, but also offers a realistic prediction since both the leader
as well as the follower can convince themselves of the (near) optimality of
their respective GPAs.

This simplicity should not be taken for granted. In general, the problem of
finding an efficient best response GPA is NP-hard. This hardness does not
simply stem from the potential for the leader to construct inscrutable GPAs;
in fact, there exist poly-time, succinctly representable leader GPAs for which
the follower cannot find a poly-time best response, unless P=NP. We give an
example of such a GPA in Lemma 9. To make this problem well defined, we allow
the follower’s GPA to take as input some representation of the leader’s GPA
(in this case a polynomial-time, polynomial-size Turing Machine) and analyze
its run-time in terms of the size of the leader’s GPA and the size of the
game. In particular, we restrict the leader’s GPA to a simple Turing Machine
that checks if a given coloring of a graph is valid (showing that the
complexity does not stem from any sophistication in the leader’s GPA).

######  Lemma 9.

Computing a set of polynomial-time Turing Machines (along with a suitable set
of random coins) that constitute an optimal follower response is NP-hard, even
when the leader’s GPAs are constrained to polynomial-time computable functions
with poly-size representations.

Note:  Here, when we say polynomial time, we mean polynomial time in the size
of the game and $T$.

The proof below also implies the following lemma as well:

######  Lemma 10.

Given a leader GPA which is composed of poly-time computable functions with a
poly-size representation, determining the expected value of the GPA against a
best-responding follower is NP-hard.

###### Proof.

Assume that we have some algorithm $A(P,M,T)$ for the follower which, given
any poly-time leader GPA $\mathcal{P}_{l}$, matrix $M$ and time horizon $T$,
computes some $P_{f}$ which runs in polynomial time. We will show that $A$ is
NP-hard via a reduction from the minimization version of graph coloring.

Consider any graph $G$ with $n$ nodes. The problem is to find the smallest
number of colors needed to color $G$. To do this, we will construct the
following game matrix $M$ and GPA $\mathcal{P}_{l}$ as input to $A$:

$M$ is an $n$ by $n$ game matrix for which $\mu_{2}(i,j)=0$ for all $i,j\neq
n$, and $\mu_{2}(n,n)=1$. Let $T=n$.

Consider the following declared GPA by Player 1, $P_{l}(G)$:

$f_{i}=1\forall i<T$ $\mathbb{P}(f_{T}=n)=\frac{1-g(G,\mathcal{T}[0:T-1])}{n}$
$\mathbb{P}(f_{T}=1)=\frac{g(G,\mathcal{T}[0:T-1])}{n}$

$g(G,\mathcal{T}[0:T-1])$ is defined as follows:

Consider all of Player 2’s moves at time $1:T-1$. If they ever play their
$n$th move, terminate and return $n$. Otherwise, consider the move played at
time $t$ to be a coloring for the $t$th node in $G$. As there are $T-1$ rounds
to represent all vertices, and $n-1=T-1$ valid moves by Player 2 to represent
the maximum number of colors needed, Player 2’s move sequence in the first
$T-1$ rounds may represent any coloring of the graph. Check whether this
represents a valid coloring in $O(n^{2})$ time by checking that Player 2 never
played the same move on rounds representing adjacent vertices. If the coloring
is invalid, return $n$. If the coloring is valid, return the number of unique
moves used by Player 2. This will occur in polynomial time, and, in addition,
the GPA can be represented in a polynomial number of bits.

To find the minimum coloring, we will compute $P_{f}=A(P_{l}(G),M,n)$. Then,
we will simulate running $P_{l}$ against $P_{f}$ to get a transcript. This
will occur in polynomial time, as both $P_{f}$ and $P_{l}$ are poly-time.
Then, we will return the total number of unique moves by Player 2 in the first
$T-1$ rounds as the minimum coloring.

Correctness: Consider the optimal strategy for Player 2 given this GPA. Their
payoff is always $0$ unless Player 1 plays their $n$th move in the final
round. At the final round, Player 2 can never do better than playing their
$n$th move in the hope of getting some nonzero payoff. Thus, Player 2’s
expected payoff for using follower GPA $\mathcal{P}_{f}$ is

$1\cdot\mathbb{P}(f_{T}=n|\mathcal{P}_{f})=\frac{1-\mathbb{E}[g_{G}(\mathcal{T}[0:T-1])|\mathcal{P}_{f}]}{n}$

Therefore the GPA which maximizes Player 2’s payoff is the GPA
$\mathcal{P}_{f}$ which minimizes

$\mathbb{E}[g_{G}(\mathcal{T}[0:T-1])|\mathcal{P}_{f}]$

Note that as $c$ is the smallest number of colors that are needed to color
$G$, there is no way for Player 2 to achieve a smaller value than $c$. This is
because the move sequence for Player 2 in the first $t-1$ rounds must
represent a valid coloring, and there is no valid coloring using less than $c$
colors. In addition, all follower GPAs which achieve a value of $c$ must
represent min colorings of $G$, followed by their $n$th move. Therefore, the
first $T-1$ rounds are a minimum coloring. Furthermore, the number of unique
moves used in these rounds is the number of unique colors used in the min
coloring. Therefore, this reduction correctly outputs the min coloring value.
As we have reduced from an NP-hard problem to $A$, $A$ is NP-hard. ∎

######  Lemma 11.

If the leader’s declared GPA is a candidate (approximate) Stackelberg GPA
constructed by either of the approaches in Theorem 2, then there exists a
linear-time algorithm for Player 2 to find an optimal response GPA.

###### Proof.

The follower can use the following algorithm to find their best-response GPA:
check if deterministically playing the moves prescribed to them by the
leader’s GPA is optimal. If yes, output the GPA doing exactly this, and if no,
output some arbitrary deterministic GPA. By Lemma 4, as long as the leader’s
GPA is constructed as per either of the algorithms in Theorem 2, playing the
moves prescribed is optimal, so the verification will always result in the yes
instance. Now we only need to prove that it is possible to perform this
verification in polynomial time in $n$ and $T$. Similar to the spirit of the
proof of Lemma 4, the follower can proceed by induction on the number of
rounds, proving to themselves that there is no point at which they would
prefer to deviate. This will take linear time in $n$ and $T$. ∎

##  Appendix C Proof from Section 4

###  C.1 Proof of Lemma 3

Assume for contradiction that for $M$, there exists a GPA $L^{*}$ that the
leader can declare such that, when the follower best responds, the expected
average leader payoff is $p^{*}>OPT_{LP}$. Just like the leader’s GPA, the
follower’s GPA can be described as $T$ different functions, where the $t$-th
function takes as input the transcript of play of length $t-1$ and all coin
flips used by the leader and outputs an action drawn from a probability
distribution over pure actions to play in round $t$. So the follower will best
responding to $L^{*}$ with some GPA $F^{*}$. Reasoning about the precise
behavior of these GPAs in tandem might be complex–both GPAs could be
randomized and could be sensitive to different realizations of their or their
opponent’s randomness. But, when played against each other, $(L^{*},F^{*})$
will always produce an output which is a sequence of $T$ move pairs.
Furthermore, this sequence is determined only by the declared GPAs and the
coin flips of each player. Therefore, $(L^{*},F^{*})$ induces a probability
distribution over sequence outcomes.

We can think of this distribution as a vector of all possible $T$-length move
pair sequences. $\mathbb{P}(S=s_{i})$ is the weight in the distribution placed
upon the $i$th sequence $s_{i}$ (for some arbitrary indexing of sequences).
For the $i$-th sequence of move pairs, let $v_{1}(s_{i})$ be the total payoff
of the leader and let $v_{2}(s_{i})$ be the total payoff of the follower. So,
the expected payoff per round for the Leader is

$p^{*}=\frac{1}{T}\sum_{i\in S}v_{1}(s_{i})\cdot\mathbb{P}(S=s_{i})$

$s_{i}$ is some particular sequence of move pairs $x_{i1},...,x_{iT}$, hence
we can rewrite the value $p^{*}$ as

$p^{*}=\frac{1}{T}\sum_{s\in
S}\sum_{t=1}^{T}M_{1}(x_{st})\cdot\mathbb{P}(S=s_{i})$

Even within each sequence, the $x_{st}$’s are not necessarily unique, as a
move pair can appear with some probability at different rounds and in
different sequences. We can rewrite the sum by iterating over each unique move
pair, which we index by $\\{(i,j)\\}$:

$p^{*}=\frac{1}{T}\sum_{t=1}^{T}\left(\sum_{i,j}(M_{1}(i,j)\cdot\sum_{s\in
S}\mathbb{P}(S=s_{i},s[t]=(i,j)))\right)$

For a particular round $t$, the sum of probabilities over all possible move
pairs as part of each possible sequence adds up to 1, i.e., $\sum_{\forall
i,j}\sum_{\forall s\in S}P(S=s_{i},S[t]=(i,j))=1$. Therefore, for every fixed
time $t$, there is a probability distribution over all move pairs. $p^{*}$ is
thus simply the sum of $T$ different distributions over move pairs, divided by
$T$. So $p^{*}$ can also be seen as $M_{1}$ applied to a distribution over
move pairs.

Thus, we know that there exists some distribution over move pairs $\beta$ such
that

$p^{*}=\sum_{i,j}M_{1}(i,j)\beta_{i,j}$

Using the same logic as above, just swapping $M_{2}$ for $M_{1}$, the value
that the follower gets in this game, which we will call $p_{F|L}$, can be
written as

$p_{F|L}=\sum_{i,j}M_{2}(i,j)\beta_{i,j}$

As the follower is best-responding, it must be the case that $p_{F|L}\geq V$.
This is since by definition, the follower can always guarantee themselves $V$
each round (for instance, by simulating the leader’s probability distribution
in each round and picking a best-response pure strategy in expectation).
Consequently, we have some distribution over move pairs $\beta$ such that

$\cdot\sum_{i,j}M_{1}(i,j)\beta_{i,j}=p^{*}>OPT_{LP}$
$\cdot\sum_{i,j}M_{2}(i,j)\beta_{i,j}\geq V$ $\sum_{i,j}\beta_{i,j}=1$
$\beta_{i,j}\geq 0$

Thus, $\beta$ is a valid solution to the LP described in Section 4, and the
objective is larger than $OPT_{LP}$. Therefore we have derived a
contradiction, and there cannot exist a leader GPA $L^{*}$ that garners
expected payoff above $OPT_{LP}$.

###  C.2 Proof of Lemma 4

We prove this by induction on the number of rounds that the follower’s GPA
follows the prescribed sequence. The base case is $t=0$ and is trivially true.
Assume that the follower cooperates for the first $t$ rounds. Consider any
deviation from the prescribed GPA in the $t+1$-th round (where $t+1<=cN$). The
average payoff for the rounds $t+1$ to $cN$ on following the GPA is at least
the threat level $V$ — this is because $\sum_{k}M_{2}(k)\alpha_{k}\geq V$ and
we are following a truncated version of the best part of this distribution
(from the follower’s perspective) when the follower cooperates with the
prescribed GPA. The average payoff in the final $r>0$ rounds equals the
maximum possible payoff $m$. Thus, the total expected payoff is at least

$V\cdot(cN-t)+r\cdot m=V\cdot(cN-t)+m\cdot(r-1)+m$

Now, consider deviating in the $(t+1)$-th round. On this single round, the
follower may get value as high as $m$. In all remaining $T-t-1=c\cdot N-t+r-1$
rounds, the threat will be employed, and thus the follower will get expected
payoff no higher than $V$. So the expected payoff is at most

$m+V\cdot(c\cdot N-t+r-1)=V\cdot(cN-t)+V\cdot(r-1)+m$

As $m\geq V$, the payoff of obeying the prescribed GPA is at least as high as
the payoff of deviating from the prescribed GPA. So the inductive step holds
when $t\leq c\cdot N$.

Finally, consider deviating on any round $t+1>cN$. By construction, for all
remaining rounds the leader prescribes only the action pair which gives the
follower their globally optimal payoff $m$. So, the remaining payoff by
obeying is $m\cdot(T-t)$. As $m$ is the maximum payoff for the follower, no
other move sequence over the next $T-t$ rounds can get them a higher payoff.
Thus, the best response by the follower for all remaining rounds is to obey
the prescribed sequence. So the inductive step also holds when $t>c\cdot N$.
Therefore, the inductive step always holds, so a best-response GPA for the
follower will always follow the prescribed sequence.

###  C.3 Proof of Claim 1

In the first case where $c\geq\frac{\sqrt{10}}{T^{\prime 0.25}\sqrt{A}}$, let
us upper bound the fraction of swaps needed (which we will write as $s$) by
writing an expression for the final value for the follower. As we swap
starting with the lowest values for the follower, their average payoff for the
non-swapped action pairs will be at least their average payoff over all pairs
before and swapping occurs. We know the final value just needs to be greater
than $V$, so it is sufficient to have:

$s\cdot m+(1-s)\left(V-\frac{10}{\sqrt{T^{\prime}}}\right)\geq V$

Rewriting this:

$sm-sV+s\frac{10}{\sqrt{T^{\prime}}}-\frac{10}{\sqrt{T^{\prime}}}\geq 0$

$s(m-V)+s\frac{10}{\sqrt{T^{\prime}}}-\frac{10}{\sqrt{T^{\prime}}}\geq 0$

$s\left(c+\frac{10}{\sqrt{T^{\prime}}}\right)-\frac{10}{\sqrt{T^{\prime}}}\geq
0$

$s\geq\frac{10}{c\sqrt{T^{\prime}}+10}$

Recall that $c\geq\frac{\sqrt{10}}{T^{\prime 0.25}\sqrt{A}}$. So, the largest
that $s$ needs to be is

$s\geq\frac{10}{\frac{\sqrt{10}}{T^{\prime
0.25}\sqrt{A}}\sqrt{T^{\prime}}+10}$

Which is itself upper bounded by

$\frac{10}{\frac{\sqrt{10}}{T^{\prime
0.25}\sqrt{A}}\sqrt{T^{\prime}}}=\frac{\sqrt{10A}}{T^{\prime 0.25}}$

This is sublinear in $T^{\prime}$. Thus, the average per-round loss to the
leader of this adjustment is at most $\frac{2\sqrt{10A}}{T^{\prime 0.25}}$.

Now, consider the other case: $c<\frac{\sqrt{10}}{T^{\prime 0.25}\sqrt{A}}$

We will now write an expression for the follower value $V$ in the optimal LP.
We will let $P_{m}$ represent the fraction of pairs that give the follower
value $m$. All other pairs give the follower value at most $m-\frac{1}{A}$, by
our definition of $A$. Thus, we have:

$V=m-c=\leq P_{m}\cdot m+(1-P_{m})\cdot\left(m-\frac{1}{A}\right)$

Which we can solve to get

$P_{m}\geq 1-Ac$

Recall that in this case, $c<\frac{\sqrt{10}}{T^{\prime 0.25}\sqrt{A}}$. Thus,
it must be that

$P_{m}\geq 1-\frac{\sqrt{10}A}{T^{\prime
0.25}\sqrt{A}}=1-\frac{\sqrt{10A}}{T^{\prime 0.25}}$

Therefore, there are at most $\frac{\sqrt{10A}}{T^{\prime 0.25}}$ fraction of
pairs that do not give the follower value $m$. Note that this is an upper
bound on the fraction of pairs that must be swapped to achieve a value above
$V$ for the follower. Thus, we can upper bound $s$ to be

$s\leq\frac{\sqrt{10A}}{T^{\prime 0.25}}$

So the average additive loss (as compared to the empirical distribution
$\widehat{\alpha}$) contributed in either case case is at most
$\frac{2\sqrt{10A}}{T^{\prime 0.25}}$.

We have seen that, with high probability, $\widehat{\alpha}$ achieves at most
$\frac{10}{\sqrt{T^{\prime}}}$ less value for the leader than $OPT_{LP}$. The
analysis above also tells us that the leader gets at most
$\frac{2\sqrt{10A}}{T^{\prime 0.25}}$ more under $\widehat{\alpha}$ as
compared to $\widehat{\alpha}^{\prime}$. Putting together the bounds from the
analysis above, $\widehat{\alpha}^{\prime}$ assures the leader an average
payoff that is off from $OPT_{LP}$ by at most $\frac{3\sqrt{10A}}{T^{\prime
0.25}}$.

###  C.4 Inevitability of Approximation to LP Upper Bound

One may wonder whether, using a more clever construction, it is possible to
exactly achieve the $OPT_{LP}$ value in every game and for every $T$. In fact,
for many games the exact $OPT_{LP}$ value is unachievable except in the limit.
Below, we show an example game where the difference between the value of the
LP and the average value of the best possible leader GPA is $\frac{1}{T}$. For
simplicity, we present $M_{1}$ and $M_{2}$ in a single matrix, with the
leader’s payoff written first. The leader is playing the rows and the follower
is playing the columns.

$\begin{bmatrix}(1,\frac{1}{2})&(0,1)\\\ (0,0)&(0,0)\end{bmatrix}$

Note that in this case the threat value used in the LP will be $0$, as if the
leader plays the second row the follower will always get value $0$.
Furthermore, the leader only gets a payoff when move pair $(1,1)$ is played.
So, the LP will simply solve the following maximization problem:

$\displaystyle\max 1\cdot\alpha_{1,1}\qquad\qquad\alpha\in\mathbb{R}^{n}$
subject to $\displaystyle\sum_{i,j}M_{2}(i,j)\alpha_{i,j}\geq 0$
$\displaystyle\sum_{i,j}\alpha_{i,j}=1$ $\displaystyle\alpha_{i,j}\geq
0\qquad\qquad\text{ for }i,j\in[n]^{2}$

Note that all $M_{2}(i,j)\geq 0$, and thus this LP is solved by setting
$a_{1,1}=1$ and getting value $1$.

Now, let us upper bound the best possible payoff that a Stackelberg GPA could
achieve over $T$ rounds. Let’s do this by examining the $T$-th round of play.
Because it is the final round, the best that the follower can do is maximize
their expected payoff in this round. They will have the leader’s GPA in hand
and thus will be able to calculate a probability distribution over the
leader’s moves. If the leader will play the first row with any nonzero
probability, then a best responding follower will always play the second
column, giving the leader a payoff of $0$. If the leader will play the second
row with probability $1$, then regardless of what the follower does, the
leader will get a payoff of $0$. Thus, the Stackelberg GPA will always give
the leader a payoff of $0$ in the final round. The best that the leader can do
in the preceeding $T-1$ rounds is get their highest possible payoff of $1$.
Therefore, their average payoff over all the rounds is upper bounded by

$\frac{(T-1)\cdot 1+0}{T}=1-\frac{1}{T}$

We have upper bounded the Stackelberg GPA value for this game to be
$1-\frac{1}{T}$, and shown that $OPT_{LP}$ for this game is $1$. Therefore, we
have lower bounded the gap between the Stackelberg GPA and $OPT_{LP}$ to be
$\frac{1}{T}$.

##  Appendix D Proofs from Section 5

###  D.1 Proof of Lemma 6

If there exists a vertex cover of size at most $\frac{n}{2}$ in $G$, then
consider the following strategies for Players 1 and 2 in a single round:
Player 1 will pick a move uniformly at random which is associated with a
vertex in the cover. Player 2 will pick a move uniformly at random which is
associated with a vertex that is not in the cover. Now, consider the utility
for Player 3 of playing any move $t_{v}$. Their payoff will be $0$ if the
vertex they play is also played by either Player 1 or Player 2. By
construction, every vertex in the graph is either being played by Player 1
w.p. $\frac{2}{n}$, or by Player 2 w.p. $\frac{2}{n}$. Therefore, their
expected payoff for playing any $t_{v}$ will be

$\left(1-\frac{2}{n}\right)\frac{n}{n-2}=1$

Furthermore, let us consider the utility for Player 3 of playing any move
$t_{e}$. As long as Player 1 has played a move associated with an adjacent
vertex to $e$, Player 3 will get value $0$. Because Player 1 is playing moves
uniformly at random from a vertex cover of size $\frac{n}{2}$, there will be
at least one vertex which is adjacent to every edge. So for any particular
$t_{e}$, w.p. at least $1-\frac{2}{n}$, the payoff will be $0$. Thus, Player
3’s expected payoff for playing any $t_{e}$ will also be at most
$\left(1-\frac{2}{n}\right)\frac{n}{n-2}=1$. Therefore, Player 3 has no moves
that get them a payoff greater than $1$. Thus, playing $t_{0}$ is a best
response, which gives all players an expected payoff of $1$. This is the
optimal possible payoff for Player 2, and thus they are certainly best-
responding to Player 1 here. Furthermore, this is the optimal possible payoff
for Player 1, and thus we have a single-round SE where Player 1 gets value 1.

Now, observe the following GPA for Player 1: commit to playing this same
distribution for all $T$ rounds. Player 2 best responds by committing to
playing their corresponding half of the distribution for every round, because
this will ensure that Player 2 gets their optimal payoff of $1$. Then, in each
round, Player 3 is incentivized to play $t_{0}$, and everyone will get payoff
$1$. This is in fact the optimal Stackelberg GPA for Player 1 in this case, as
they are getting on average the maximum possible value they get in the game.

###  D.2 Proof of Lemma 7

We will proceed via proof by contradiction. Assume, for sake of contradiction,
that there is no balanced vertex cover, but there exists some pair of mixed
strategies by Players 1 and 2 such that Player 3 gets expected value no higher
than $1+\frac{1}{(n-2)n^{c-1}}$. Thus, in particular, there is no pure
strategy $s$ that Player 3 can play which gets them greater than
$1+\frac{1}{(n-2)n^{c-1}}$.

Consider taking any distribution by Player 1, and sorting the moves in their
support in decreasing order of likelihood. Then, add all the moves not in the
support at the end of the ordering. Let $p_{1}(x_{i})$ be the probability that
Player 1 will play their $i$-th most likely move. We will now pay particular
attention to their $(\frac{n}{2}+1$)-th most likely move (WLOG, we assume that
$n$ is even). Let us consider two cases:
1) $p_{1}(x_{\frac{n}{2}+1})<\frac{1}{n}-\frac{1}{2n^{c}}$
2) $p_{1}(x_{\frac{n}{2}+1})\geq\frac{1}{n}-\frac{1}{2n^{c}}$

Let us begin with case 1), i.e.,
$p_{1}(x_{\frac{n}{2}+1})<\frac{1}{n}-\frac{1}{2n^{c}}$. Note that, because
there is no vertex cover of size $\frac{n}{2}$, there is some edge $e$ which
is not covered by any of the first $\frac{n}{2}$ vertices in the ordering.
Additionally, by the structure of graphs, there are at most $2$ vertices which
could cover it. By our case assumption, all remaining vertex-associated moves
by Player 1 have probability of strictly less than
$\frac{1}{n}-\frac{1}{2n^{c}}$. Thus, the highest probability with which
Player 1 could play a vertex which covers edge $e$ is strictly less than
$2\cdot(\frac{1}{n}-\frac{1}{2n^{c}})=\frac{2}{n}-\frac{1}{n^{c}}$. Therefore,
if Player 3 plays $t_{e}$, their expected payoff is

$\frac{n}{n-2}\cdot P(r_{v}\textit{ not adjacent to }t_{e})+0\cdot
P(r_{v}\textit{ adjacent to }t_{e})$

$>\frac{n}{n-2}\cdot\left(1-\frac{2}{n}+\frac{1}{n^{c}}\right)$

$=\frac{n-2}{n-2}+\frac{n}{n-2}\cdot\frac{1}{n^{c}}$
$=1+\frac{1}{(n-2)n^{c-1}}$

Thus, in case 1), there is a pure strategy $s$ which gets Player $3$ value
greater than $=1+\frac{1}{(n-2)n^{c-1}}$.

We now proceed to case 2),
$p_{1}(x_{\frac{n}{2}+1})\geq\frac{1}{n}-\frac{1}{2n^{c}}$. To prove a
contradiction in this case, we use the following claim, the proof of which
appears in Appendix D.3. The proof is based upon a careful water-filling
argument that shows how to move probability mass around within Player 1’
strategy while maintaining the assumed conditions as invariant.

######  Claim 2.

If there is any pair of distributions that Players 1 and 2 can play where
$p_{1}(x_{\frac{n}{2}+1})\geq\frac{1}{n}-\frac{1}{2n^{c}}$ such that Player 3
cannot get expected value strictly greater than $1+\frac{1}{(n-2)n^{c-1}}$
then there is a (possibly different) pair of distributions $p^{\prime}_{1}$
and $p^{\prime}_{2}$ that Players 1 and 2 can play and some vertex $x_{i^{*}}$
where $p^{\prime}_{1}(x_{i^{*}})=\frac{1}{n}-\frac{1}{2n^{c}}$ such that
Player 3 cannot get expected value strictly greater than
$1+\frac{1}{(n-2)n^{c-1}}$.

Thus, to prove that there must be a move that gets Player 3 expected value
strictly greater than $1+\frac{1}{(n-2)n^{c-1}}$, it is sufficient to prove
that there must be such a move when
$p_{1}(x_{i^{*}})=\frac{1}{n}-\frac{1}{2n^{c}}$ for some vertex $x_{i^{*}}$.
Assume, for sake of contradiction, that there is no such move. Then, it must
be that the probability that either Player 1 or Player 2 (or both) play a move
associated with any given vertex is at least $\frac{2}{n}-\frac{1}{n^{c}}$,
for all vertices, since otherwise Player 3 could play a vertex move to get an
expected payoff strictly larger than $1+\frac{1}{(n-2)n^{c-1}}$. Let us first
consider all vertices other than $x_{i^{*}}$, and call this set $V^{\prime}$.
Because all the moves are being played with probability
$\frac{2}{n}-\frac{1}{n^{c}}$, the sum of the total probabilities (using the
union bound vertex by vertex) that Players 1 and 2 place on $V^{\prime}$ must
be at least

$(n-1)\left(\frac{2}{n}-\frac{1}{n^{c}}\right)=\frac{2(n-1)}{n}-\frac{n-1}{n^{c}}$

By our assumption, Player 1 is playing $x_{i^{*}+1}$ with probability
$\frac{1}{n}-\frac{1}{2n^{c}}$. Thus, the total probability that Player 1
places in $V^{\prime}$ is $1-\frac{1}{n}+\frac{1}{2n^{c}}$. Thus, Player 2’s
probability of playing a move in $V^{\prime}$ must be at least

$\frac{2(n-1)}{n}-\frac{n-1}{n^{c}}-\left(1-\frac{1}{n}+\frac{1}{2n^{c}}\right)$

Which means that Player 2’s probability of playing $x_{i^{*}}$ must be at most

$1-\left(\frac{2(n-1)}{n}-\frac{n-1}{n^{c}}-\left(1-\frac{1}{n}+\frac{1}{2n^{c}}\right)\right)$
$=1-\frac{2(n-1)}{n}+\frac{n-1}{n^{c}}+1-\frac{1}{n}+\frac{1}{2n^{c}}$
$=\frac{1}{n}+\frac{1}{n^{c-1}}-\frac{1}{2n^{c}}$

Going back to our assumption, Player 1 has a probability of
$\frac{1}{n}-\frac{1}{2n^{c}}$ of playing $x_{i^{*}}$. Recall that there is no
coordination possible in the realizations of this randomness, so once the
probabilities are set, their behavior is independent. So, we can calculate the
total probability that this move is played by either or both players:

$p_{1}(x_{i^{*}})+p_{2}(x_{i^{*}})-p_{1}(x_{i^{*}})p_{2}(x_{i^{*}})=p_{1}(x_{i^{*}})+p_{2}(x_{i^{*}})(1-p_{1}(x_{i^{*}}))$

We show that this value is always less than $\frac{2}{n}-\frac{1}{n^{c}}$, and
therefore Player 3 can play $t_{x_{i^{*}}}$ to get a sufficiently large
payoff, resulting in a contradiction. We wish to prove the following
inequality:

$p_{1}(x_{i^{*}})+p_{2}(x_{i^{*}})-p_{1}(x_{i^{*}})p_{2}(x_{i^{*}})<\frac{2}{n}-\frac{1}{n^{c}}$

Since $p_{1}(x_{i^{*}})$ is constant and smaller than $1$, the left hand side
is upper bounded by replacing $p_{2}(x_{i^{*}})$ by the maximum possible value
it can take. So, we wish to prove the stronger inequality below, which we
prove by rearranging terms:

$\frac{1}{n}-\frac{1}{2n^{c}}+\frac{1}{n}+\frac{1}{n^{c-1}}-\frac{1}{2n^{c}}-\left(\frac{1}{n}-\frac{1}{2n^{c}}\right)\left(\frac{1}{n}+\frac{1}{n^{c-1}}-\frac{1}{2n^{c}}\right)<\frac{2}{n}-\frac{1}{n^{c}}$

$\frac{1}{n^{c-1}}-\left(\frac{1}{n}-\frac{1}{2n^{c}}\right)\left(\frac{1}{n}+\frac{1}{n^{c-1}}-\frac{1}{2n^{c}}\right)<0$

$\frac{1}{n^{c-1}}<\left(\frac{1}{n}-\frac{1}{2n^{c}}\right)\left(\frac{1}{n}+\frac{1}{n^{c-1}}-\frac{1}{2n^{c}}\right)$
$1<\left(n^{c-2}-\frac{1}{2n}\right)\left(\frac{1}{n}+\frac{1}{n^{c-1}}-\frac{1}{2n^{c}}\right)$

$1<\left(n^{c-3}-\frac{1}{2n^{2}}\right)+\left(n^{c-2}-\frac{1}{2n}\right)\left(\frac{1}{n^{c-1}}-\frac{1}{2n^{c}}\right)$

Note that the first two terms on the RHS are always greater than $1$ for
$c>3$, and the two terms being multiplied are always greater than $0$ for
$c\geq 1$. Therefore, this inequality certainly holds. This concludes our
proof by contradiction.

###  D.3 Proof of Claim 2

We will prove this by transforming any pair of distributions where
$p_{1}(x_{\frac{n}{2}+1})\geq\frac{1}{n}-\frac{1}{2n^{c}}$, such that Player 3
cannot get expected value strictly greater than $1+\frac{1}{(n-2)n^{c-1}}$,
into a pair of distributions $p^{\prime}_{1},p^{\prime}_{2}$ for the first two
players where $p^{\prime}_{1}(x_{\frac{n}{2}+1})=\frac{1}{n}-\frac{1}{2n^{c}}$
for the vertex $x_{\frac{n}{2}+1}$ (retaining the same indexing based upon
$p_{1}$), and Player 3 still cannot do better in expectation than this value.

By construction of the reduction, the condition of Player 3 not being able to
get expected value strictly greater than $1+\frac{1}{(n-2)n^{c-1}}$ by playing
vertex moves occurs exactly when the probability that either Player 1 or
Player 2 play a vertex move $x_{i}$ is at least $\frac{2}{n}-\frac{1}{n^{c}}$,
for all $i$. So, assume that we have a pair of distributions $p_{1},p_{2}$ of
this sort. Then, for all $x_{i}$,

$p_{1}(x_{i})+p_{2}(x_{i})-p_{1}(x_{i})p_{2}(x_{i})\geq\frac{2}{n}-\frac{1}{n^{c}}$

Now, consider any two $x_{j}$, $x_{k}$ s.t.
$\frac{2}{n}-\frac{1}{n^{c}}-\epsilon\geq p_{1}(x_{j})\geq
p_{1}(x_{k})\geq\epsilon$, for $\epsilon>0$. Let us construct a new
distribution $p^{\prime}_{1}$ for Player 1, where everything is the same,
except that $p^{\prime}_{1}(x_{j})=p_{1}(x_{j})+\epsilon$, and
$p^{\prime}_{1}(x_{k})=p_{1}(x_{k})-\epsilon$. We claim that there will still
exist a distribution $p^{\prime}_{2}$ that Player 2 can play which satisfies
$p^{\prime}_{1}(x_{i})+p^{\prime}_{2}(x_{i})-p^{\prime}_{1}(x_{i})p^{\prime}_{2}(x_{i})\geq\frac{2}{n}-\frac{1}{n^{c}}$
for all $x_{i}$.

First, note that if $p^{\prime}_{2}(x_{i})=p_{2}(x_{i})$ for all $i\neq j,k$,
then this condition holds for all these $i$. Then, we only need to ensure that
it holds for $j$ and $k$. Player 2 has a total probability of
$p_{2}(x_{j})+p_{2}(x_{k})$ remaining to distribute amongst $p_{2}(x_{j})$ and
$p_{2}(x_{k})$. Thus, it is sufficient to prove that there is a valid choice
of non-negative values for $p^{\prime}_{2}(x_{j})$ and $p^{\prime}_{2}(x_{k})$
such that

$p^{\prime}_{2}(x_{j})+p^{\prime}_{2}(x_{k})\leq p_{2}(x_{j})+p_{2}(x_{k})$

We claim that this condition is satisfied by setting the values as follows:

$p^{\prime}_{2}(x_{j})=\frac{\frac{2}{n}-\frac{1}{n^{c}}-p^{\prime}_{1}(x_{j})}{1-p^{\prime}_{1}(x_{j})}$
$p^{\prime}_{2}(x_{k})=\frac{\frac{2}{n}-\frac{1}{n^{c}}-p^{\prime}_{1}(x_{k})}{1-p^{\prime}_{1}(x_{k})}$

Which can be rewritten as follows:

$p^{\prime}_{2}(x_{j})=\frac{\frac{2}{n}-\frac{1}{n^{c}}-p_{1}(x_{j})-\epsilon}{1-p_{1}(x_{j})-\epsilon}$
$p^{\prime}_{2}(x_{k})=\frac{\frac{2}{n}-\frac{1}{n^{c}}-p_{1}(x_{k})+\epsilon}{1-p_{1}(x_{k})+\epsilon}$

For these values, we have:

$p^{\prime}_{2}(x_{j})+p^{\prime}_{2}(x_{k})=\frac{\frac{2}{n}-\frac{1}{n^{c}}-p_{1}(x_{k})+\epsilon}{1-p_{1}(x_{k})+\epsilon}+\frac{\frac{2}{n}-\frac{1}{n^{c}}-p_{1}(x_{j})-\epsilon}{1-p_{1}(x_{j})-\epsilon}$

For the original distribution, we use the conditions upon $x_{j}$ and $x_{k}$
to get:

$p_{2}(x_{j})+p_{2}(x_{k})\geq\frac{\frac{2}{n}-\frac{1}{n^{c}}-p_{1}(x_{k})}{1-p_{1}(x_{k})}+\frac{\frac{2}{n}-\frac{1}{n^{c}}-p_{1}(x_{j})}{1-p_{1}(x_{j})}$

So, it is sufficient for us to prove that

$\frac{\frac{2}{n}-\frac{1}{n^{c}}-p_{1}(x_{k})+\epsilon}{1-p_{1}(x_{k})+\epsilon}+\frac{\frac{2}{n}-\frac{1}{n^{c}}-p_{1}(x_{j})-\epsilon}{1-p_{1}(x_{j})-\epsilon}\leq\frac{\frac{2}{n}-\frac{1}{n^{c}}-p_{1}(x_{k})}{1-p_{1}(x_{k})}+\frac{\frac{2}{n}-\frac{1}{n^{c}}-p_{1}(x_{j})}{1-p_{1}(x_{j})}$

Rearranging terms:

$\frac{\frac{2}{n}-\frac{1}{n^{c}}-p_{1}(x_{k})+\epsilon}{1-p_{1}(x_{k})+\epsilon}-\frac{\frac{2}{n}-\frac{1}{n^{c}}-p_{1}(x_{k})}{1-p_{1}(x_{k})}\leq+\frac{\frac{2}{n}-\frac{1}{n^{c}}-p_{1}(x_{j})}{1-p_{1}(x_{j})}-\frac{\frac{2}{n}-\frac{1}{n^{c}}-p_{1}(x_{j})-\epsilon}{1-p_{1}(x_{j})-\epsilon}$

$\frac{\epsilon(1-\frac{2}{n}+\frac{1}{n^{c}})}{(1-p_{1}(x_{k})+\epsilon)(1-p_{1}(x_{k}))}\leq\frac{\epsilon(1-\frac{2}{n}+\frac{1}{n^{c}})}{(1-p_{1}(x_{j}))(1-p_{1}(x_{j})-\epsilon)}$

Because we know that $1/2>p_{1}(x_{j})\geq p_{1}(x_{k})\geq\epsilon$, all
these terms are positive, so we can multiply to get:

$(1-p_{1}(x_{j})-\epsilon)(1-p_{1}(x_{j}))\leq(1-p_{1}(x_{k})+\epsilon)(1-p_{1}(x_{k}))$

Note that the first term on the LHS is no larger than the first term on the
RHS, and the second term on the LHS is no larger than the second term on the
RHS. Therefore, this statement is always true. This means we have proven that
there exists a satisfying distribution $p^{\prime}_{2}$.

For our given distribution pair $(p_{1},p_{2})$, we know that
$p_{1}(x_{i})+p_{2}(x_{i})-p_{1}(x_{1})p^{\prime}_{2}(x_{i})\geq\frac{2}{n}-\frac{1}{n^{c}}$
for all $i$, and $p_{1}(x_{\frac{n}{2}+1})\geq\frac{1}{n}-\frac{1}{2n^{c}}$.
Assume that this is a valid distribution pair that ensures that Player 3
cannot get expected value strictly greater than $1+\frac{1}{(n-2)n^{c-1}}$.

We show that we can use the above primitive of moving probability weights
repeatedly to get our desired result. Specifically, we show that we can move
probability mass from vertex $x_{\frac{n}{2}+1}$ to vertices in the set
$V_{1/2}=\\{x_{1},x_{2},\cdots x_{\frac{n}{2}}\\}$. To do so, we need to argue
that that there are a sufficient number of vertices in $V_{1/2}$ with
probability sufficiently below $\delta:=\frac{2}{n}-\frac{1}{n^{c}}$ (since
this is a necessary condition to be able to move probability mass from a lower
probability vertex to a higher probability vertex). Specifically, let
$p_{1}(x_{\frac{n}{2}+1})=\delta/2+\gamma$ where $\gamma>0$ (if $\gamma=0$, we
are already done). A simple averaging argument shows that $\gamma<\delta/2$.
Assume otherwise, for sake of contradiction. Then, we have
$p_{1}(x_{\frac{n}{2}+1})\geq\delta$ implying that $p_{1}(x_{i})\geq\delta$
for all $i\in\left[\frac{n}{2}+1\right]$. Thus the sum
$\sum_{i}p_{1}(x_{i})\geq\left(\frac{n}{2}+1\right)\delta=1+\frac{2}{n}-\frac{1}{2n^{c-1}}-\frac{1}{n^{c}}>1$,
resulting in a contradiction.

Next, we argue that it suffices to show that
$\sum_{i=1}^{n/2}p(x_{i})\leq\frac{n}{2}\delta-\delta/2$.

We know, by definition of indexing over the $x$’s, that $p_{1}(x_{1})\geq
p_{1}(x_{2})\geq p_{1}(x_{3})\cdots p_{1}(x_{n})$. Let $i^{\prime}$ be the
largest index such that $p_{1}(x_{i^{\prime}})\geq\delta$ (with $i^{\prime}=0$
if there is no such index). Then, we know that we can move probability mass
upto $\delta-p_{1}(x_{i})$ into each vertex $x_{i}$ where
$i\in\\{i^{\prime}+1,i^{\prime}+2,\cdots\frac{n}{2}\\}$. Let us write
$\gamma_{i}=\delta-p_{1}(x_{i})$ for all $i\in\left[\frac{n}{2}\right]$. Since
we assume that $\sum_{i=1}^{n/2}p(x_{i})\leq\frac{n}{2}\delta-\delta$, we know
that $sum_{i=1}\gamma_{i}\geq\delta$. This sum can be split into negative and
positive parts, which are $\sum_{i=1}^{i^{\prime}}\gamma_{i}$ and
$\sum_{i=i^{\prime}+1}^{\frac{n}{2}}\gamma_{i}$, implying that
$\sum_{i=i^{\prime}+1}^{\frac{n}{2}}\gamma_{i}\geq\delta$. We start by moving
mass from $x_{\frac{n}{2}+1}$ into $x_{i^{\prime}+1}$, continue until the
probability on $x_{i^{\prime}+1}$ is $\delta$, and then move onto
$x_{i^{\prime}+2}$ and so on. Since we only need to move $\gamma<\delta/2$
mass away from $x_{\frac{n}{2}+1}$, we will always be able to complete this
procedure. At each step, we maintain the invariant that the probability on
$x_{\frac{n}{2}+1}$ is less than or equal to the probability on $x_{i}$ for
$i\in[\frac{n}{2}]$. Thus, to complete the proof, we only need to justify the
assumption that $\sum_{i=1}^{n/2}p(x_{i})\leq\frac{n}{2}\delta-\delta$.

Since there is no vertex cover of size $\frac{n}{2}$, at least one edge $e$ is
left uncovered by the set $V_{1/2}$ (which is a set of $\frac{n}{2}$
vertices). Since, no edge move gets Player 3 a payoff greater than
$1+\frac{1}{(n-2)n^{c-1}}$, there must be at least $\delta$ probability mass
of Player 1 picking a vertex that covers edge $e$. Therefore,
$\sum_{i=1}^{n/2}p(x_{i})\leq 1-\delta$. We prove the stronger result that

$\displaystyle\sum_{i=1}^{n/2}p(x_{i})$ $\displaystyle\leq
1-\delta\leq\frac{n}{2}\delta-\delta/2$

To see that the last inequality is true, we substitute the value of $\delta$
on both sides to get :

$1-\frac{2}{n}+\frac{1}{n^{c}}\leq
1-\frac{1}{n}-\frac{1}{2n^{c-1}}+\frac{1}{2n^{c}}$

Rearranging terms gives us :

$\frac{1}{2n^{c}}+\frac{1}{2n^{c-1}}\leq\frac{1}{n}$

Which is true for $c\geq 3$, completing the proof.

Therefore, any valid solution with the constraint given on
$p_{1}(x_{\frac{n}{2}+1})$ implies a valid solution where
$p^{\prime}_{1}(x_{\frac{n}{2}}+1)=\frac{1}{n}-\frac{1}{2n^{c}}$.

##  Appendix E Construction of Approximately Optimal GPA for Prisoner’s
Dilemma

In this section, we will use the ideas in Section 4 to complete the analysis
in Section 3.1, constructing an approximately optimal Stackelberg strategy for
finite-horizon repeated Prisoner’s Dilemma. To truly make this construction
explicit, we will need to choose a specific $T$. In this case we will pick
$T=11$, a value which is not precisely optimal for the coefficients and thus
shows off the use of approximation.

We reproduce the matrix here, scaling down the entries so that payoffs are
bounded between $-1$ and $1$:

$\begin{bmatrix}(\frac{3}{5},\frac{3}{5})&(0,1)\\\
(1,0)&(\frac{1}{5},\frac{1}{5})\end{bmatrix}$

As described in section 4, constructing the GPA involves three main parts: 1)
finding the safety value for the follower, 2) solving an LP to find a
distribution, and 3) constructing a GPA from that distribution for the
particular value of $T$.

To find the safety value, we can consider the following game matrix which only
has the follower’s payoffs, and solve the minimax of the game:

$\begin{bmatrix}\frac{3}{5}&1\\\ 0&\frac{1}{5}\end{bmatrix}$

The solution is $\frac{1}{5}$, and thus we set $V=\frac{1}{5}$. As a sanity
check, note that this is the payoff to the follower when both players defect,
which is indeed the highest payoff they can always guarantee themselves. This
also gives us the explicit threat that the leader can use to hit this safety
value, which is to play their second move (defect).

To solve the LP shown in section 4.1, we simply substitute in the values of
$V$ and of the Prisoner’s Dilemma payoff matrix (i.e.,
$M_{1}(1,1)=\frac{3}{5}$, $M_{2}(1,1)=\frac{3}{5}$, and so on). There will be
$4$ $\alpha$ variables, as there are $4$ different possible move pairs. This
leaves us with the following linear program:

$\displaystyle\max\ \
\frac{3}{5}\alpha_{1,1}+\alpha_{2,1}+\frac{1}{5}\alpha_{2,2}$ subject to
$\displaystyle\frac{3}{5}\alpha_{1,1}+\alpha_{1,2}+\frac{1}{5}\alpha_{2,2}\geq\frac{1}{5}$
$\displaystyle\sum_{i,j}\alpha_{i,j}=1$ $\displaystyle\alpha_{i,j}\geq
0\qquad\qquad\text{ for }i,j\in[n]^{2}$

Solving this linear program gives us the following values:

$\alpha_{1,1}=\frac{1}{3}$ $\alpha_{1,2}=0$ $\alpha_{2,1}=\frac{2}{3}$
$\alpha_{2,2}=0$

The value of the LP objective is $\frac{13}{15}$, which also gives us our LP
upper bound on the average SE value.

We are now ready to proceed to the third step, where we construct a GPA of
size $11$ from this distribution using the tools from section 4.2. Note that
all of the coefficients in the linear program can be written in the form
$\frac{p_{i,j}}{3}$, where $p_{i,j}\in\mathbb{N}$. So the cycle length $N$,
the LCM of the denominators of $p_{1,1},...p_{2,2}$, is simply $3$. As the LCM