Solution
= Solution
Measure all <payoffs> in millions of dollars, in the order (Ann, Bob). Since both players maximize expected money, those numbers are already their <expected utility> scale.
In the <extensive-form game>, Ann moves first. Staying out terminates at $(2,6)$. Entering leads to Bob's observed decision between fighting, with terminal <payoffs> $(1,1)$, and acquiescing, with terminal <payoffs> $(3,3)$. Each decision node is its own <information set>, so this is a <perfect-information game>.
\Image[/past-exam-of-the-msc-in-advanced-computer-science-course-of-the-university-of-oxford/2023/computational-game-theory-entry-tree.png]
{title=The entry decision as a <perfect-information game>}
The corresponding <normal-form game> gives Ann the <pure strategies> $O$ (stay out) and $E$ (enter), and Bob the complete contingent <pure strategies> $F$ (fight if entry occurs) and $A$ (acquiesce if entry occurs). The <payoff matrix> is
$$
\begin{array}{c|cc}
&F&A\\ \hline
O&(2,6)&(2,6)\\
E&(1,1)&(3,3)
\end{array}.
$$
The <pure strategy> <Nash equilibria> are \b[$(O,F)$ and $(E,A)$]. Against $F$, Ann prefers $O$; against $A$, Ann prefers $E$. When Ann stays out, Bob's contingent response does not affect his <payoff>, so $F$ is a <best response> there.
There is exactly one <subgame perfect equilibrium>, \b[$(E,A)$]. In the subgame following entry, Bob strictly prefers $3$ to $1$, so <backward induction> selects acquiescence; Ann then strictly prefers entering for $3$ to staying out for $2$. The threat supporting $(O,F)$ is not optimal in that one-shot subgame.
For infinite repetition, the paper specifies no discount factor. First take the <long-run average payoff> convention, with all past actions observed. The <feasible payoff set> is the <convex hull>
$$
\mathcal F=\operatorname{conv}\{(2,6),(1,1),(3,3)\}.
$$
Ann can guarantee $2$ in every stage by staying out; Bob can guarantee at least $3$ in every stage by acquiescing whenever entry occurs. These guarantees are also their <minmax payoffs>: fighting holds Ann's best possible stage <payoff> to $2$, and entering holds Bob's best possible stage <payoff> to $3$.
Therefore the sustainable <Nash equilibrium> average <payoffs> are exactly the feasible, weakly <individually rational payoffs in a repeated game>:
$$
\boxed{\mathcal F\cap\{(a,b):a\ge2,\ b\ge3\}
=\{(a,b):2\le a\le3,\ 3\le b\le12-3a\}.}
$$
This is the closed triangle with vertices $(2,3),(2,6),(3,3)$.
Here is a direct sufficiency argument for this particular game. Choose a publicly known sequence of stage outcomes whose frequencies give the target point. Before any observed deviation, follow that sequence. After an Ann deviation, Bob fights forever, so Ann can thereafter obtain at most $2$ per stage. After a Bob deviation, Ann enters forever, so Bob can thereafter obtain at most $3$ per stage. A finite prefix has no effect on <long-run average payoff>, so no <unilateral deviation> improves a target with $a\ge2,b\ge3$. Rational frequencies can be implemented periodically; arbitrary real frequencies can be implemented by a deterministic sequence with convergent frequencies. Thus even the weak boundary is covered here. In particular, \b[staying out forever and entry followed by acquiescence forever are sustainable; fighting forever is not].
\Image[/past-exam-of-the-msc-in-advanced-computer-science-course-of-the-university-of-oxford/2023/computational-game-theory-repeated-payoffs.png]
{title=The <feasible payoff set> and sustainable <long-run average payoffs>}
For discounted <payoffs> $(1-\delta)\sum_{t\ge0}\delta^t u_i^t$, the <folk theorem for repeated games> instead gives the usual patience qualification: every feasible point with $a>2,b>3$ can be sustained for all sufficiently large $\delta<1$. It does not classify the whole region for an unspecified fixed $\delta$. The two one-shot <Nash equilibrium> outcomes remain sustainable for every $\delta$.<Lecture 15: Repeated Games by Asu Ozdaglar>[Slides 19–20 and 24–27: feasibility, minmax bounds, discounted Nash folk theorem and punishment construction]{ref}
Finally consider the particular history-dependent pair in the paper. Initially Bob has never acquiesced, so Ann stays out. That preserves the same condition forever, giving <payoffs> $(2,6)$. \b[The pair is a <Nash equilibrium>.] Holding Bob's strategy fixed, Ann cannot induce an acquiescence: he fights whenever she enters, and his rule never changes unless he has previously acquiesced. Every entry would give her $1$ instead of $2$, so no <unilateral deviation> helps. Holding Ann's strategy fixed, Bob never reaches a decision node because she stays out; changing his strategy alone cannot create a history in which he actually acquiesces. Hence he also cannot improve.
This direct argument works for both discounted and <long-run average payoffs>. The outcome gives Ann exactly her <minmax payoff> and Bob more than his, so it is compatible with the <folk theorem for repeated games>. A version requiring \i[strict] gains above both <minmax payoffs> is a sufficient condition, and cannot be used to rule out this boundary example.