Supplementary reading S4

Sequential irrationality and perfect equilibria

As we discussed on multiple occasions, Nash equilibrium strategies encode the idea of playing optimally against the strongest possible opponent. Even when the opponent is only close to optimal (for example, in the poker competitions where the opponent were top professional poker players), playing a Nash equilibrium is often the safe choice, as professional players are very quick at exploiting suboptimal strategies, making opponent modeling risky. However, as we reveal today, not all Nash equilibria are equally strong in extensive-form games when playing against players that might make mistakes.

S4.1 Sequential irrationality

Nash equilibrium strategies are only optimized for the strongest possible opponent. Because of that, they are completely indifferent to what happens in parts of the game tree that are reached only if a player makes a mistake.

In Guess-the-Ace, at the start a standard 52-card deck is perfectly shuffled, face down, by a dealer. Then, Player \(1\) can decide whether to immediately end the game, at which point no money is transferred between the players, or offer $1000 to Player \(2\) if they can correctly guess whether the top card of the shuffled deck is the ace of spaces or not. If Player \(2\) guesses correctly, the $1000 get transferred from Player \(1\) to Player \(2\); if not, no money is transferred. The game tree is summarized in Example S4.1.

Clearly, the only Nash equilibrium strategy for Player \(1\) is to quit immediately, or they are guaranteed to lose money. Since Player \(2\) does not get to play, any strategy for Player \(2\) is a Nash equilibrium strategy.

In particular, both highlighted equilibria in Example S4.1 are Nash equilibria. However, the two equilibria are significantly different from a practical point of view. Imagine that Player \(2\) is a bot playing against opponents in the real world, blindly following the Nash equilibrium strategy it has precomputed. If Player \(1\) makes a mistake and decides to offer the $1000 instead of immediately quitting, the Nash equilibrium that bets that the top card is not the ace of space has an expected utility of \(>\) $980 whereas the Nash equilibrium that bets that the top card is the ace of spade only has an expected utility of \(<\) $20.

So, while both strategy profiles in Example S4.1 are Nash equilibria, only one of the two is “sensible”.

Formalizing this subtle notion of rationality within the set of Nash equilibria has been a major endeavor for the game-theoretic literature in the 70s and 80s. Today, we say that the equilibrium in Example S4.1 (Left) is sequentially irrational, while the one on the right is sequentially rational. The takeaway lesson is:

The goal of this lecture is to investigate how one can rule out sequential irrationality and compute a sequentially-rational Nash equilibrium in a two-player zero-sum imperfect-information game.

S4.2 Undomination is not the solution

One might believe that the problem of sequential irrationality is that of picking dominated strategies. So, one might be inclined to look into the problem of finding a Nash equilibrium whose support does not include any (weakly) dominated strategy (the concept is not immediately well defined, but for the purposes of this discussion let’s restrict ourselves to Nash equilibria in deterministic strategies).

Unfortunately, domination of strategies is not the root cause of sequential irrationality, and therefore undomination is not its solution. Indeed, as much as undomination does get rid of the undesirable behavior of Example S4.1 (Right), since action `A\(♠\)’ is strictly dominated by action `\(¬\)A\(♠\)’, it does not prevent sequential irrationality in more complex settings, such as Example S4.3.

S4.3 Trembling-hand refinements

The issue of sequential irrationality stems from the fact that some parts of the game tree are unreachable at equilibrium. For those excluded parts of the game tree, any strategy can be picked without affecting the equilibrium. The idea behind trembling-hand refinements is simple: to avoid sequential irrationality, it forces all players to explore the whole game tree. It does so by forcing the players to tremble, that is, by constraining them to play all actions at all decision points with a strictly positive lower bound probability that grows as a function of a hyperparameter \(\epsilon > 0\). For each \(\epsilon > 0\), a Nash equilibrium subject to the trembling constraints is found. A trembling-hand refinements is then any limit points of such Nash equilibria as \(\epsilon \to 0^{+}\).

Different equilibrium notions differ as to how the lower bounds are set as a function of \(\epsilon\). We will see two, which are the two best known: extensive-form perfect equilibrium and quasi-perfect equilibrium.

S4.3.1 Extensive-form perfect equilibrium (EFPE)

Extensive-form perfect equilibrium (EFPE), due to Selten [Sel75[Sel75] Selten, R. (1975). Reexamination of the perfectness concept for equilibrium points in extensive games. International Journal of Game Theory.], is conceptually the simplest of the two. In an EFPE, the trembles are behavioral: given \(\epsilon > 0\), the perturbed game simply mandates that every action at every decision point must be picked with probability at least \(\epsilon\).

Since our game solving formalism is based around the sequence-form representation of strategies, it is important to check that those behavioral trembling constraints can be expressed in the sequence form. That is the case: asking that action \(a\) at decision point \(j\) of Player \(1\) be selected with probability at least \(\epsilon\) corresponds to the sequence-form constraint

Collecting all sequence-form trembling constraints (1) constraints across all decision points \(j \in J\) and actions \(a \in A_{j}\) of Player \(1\), we can express the whole set of trembling constraints in matrix form as \(M_{1} ( \epsilon ) x \ge m_{1} ( \epsilon )\). (An analogous statement holds for Player \(2\)). So, given any \(\epsilon > 0\), and indicating with \(F_{1} x = f_{1} , x \ge 0\) and \(F_{2} y = f_{2} , y \ge 0\) the polytope of sequence form strategies of Player 1 and Player 2 respectively, a Nash equilibrium strategy for Player \(1\) under the trembling constraints can be expressed as the saddle point problem

We will look into how to compute a limit point of solutions to 2 as \(\epsilon \to 0^{+}\) in Section S4.4.

S4.3.2 Quasi-perfect equilibrium (QPE)

Quasi-perfected equilibrium (QPE), introduced by van Damme [Van84[Van84] van Damme, E. (1984). A relation between perfect equilibria in extensive form games and proper equilibria in normal form games. International Journal of Game Theory.], is a bit more intricate than EFPE. Specifically, while in an EFPE each trembling constraints mandates a lower bound of \(\epsilon\) on the probability of playing each action, in the case of a QPE the lower bounds are given on the probability of each sequence of actions. More precisely, for any \(\epsilon > 0\) and player \(i \in \{1 , 2\}\), let \(ℓ_{i} : \mathbb{R}_{> 0} \to \mathbb{R}_{> 0}^{Σ_{i}}\) denote the vector parametrized on \(\epsilon\) and indexed on the sequences \(Σ_{i}\) of Player \(i\), whose entries are defined as

where \(| \sigma |\) denotes the number of actions for Player \(i\) in the sequence \(\sigma\). Miltersen and S [MS10[MS10] Miltersen, P. B., & Sørensen, T. B. (2010). Computing a Quasi-Perfect Equilibrium of a Two-Player Game. Economic Theory, 42(1).] proved that any limit point of the solution to the perturbed optimization problem

is a QPE. (Recently, Gatti, Gilli and Marchesi [GGM20[GGM20] Gatti, N., Gilli, M., & Marchesi, A. (2020). A characterization of quasi-perfect equilibria. Games and Economic Behavior, 122, 240–255.] took this construction further, and showed that any QPE can be expressed as a limit point of solutions to 4, as long as more general vectors of polynomials \(ℓ_{1} , ℓ_{2}\) are used than in (3). In this paper we will focus on Miltersen-Sørensen-style perturbation as defined in (3).)

Once again, we will discuss how to compute a limit point of solutions to 4 as \(\epsilon \to 0^{+}\) in Section S4.4.

S4.3.3 Relationships between the equilibria

We already know from Section S4.2 that undomination does not imply sequential rationality. Interestingly, the converse also is not true in general. So, undomination and sequential rationality are actually incomparable concepts, in the sense that neither implies the other.

At this point, one might naturally wonder whether a refinement that is both undominated and sequentially-rational can be devised. The answer is yes: a nice property of QPE is that not only it is sequentially rational, but it is also undominated! The same cannot be said of EFPE. So, as Mertens [Mer95[Mer95] Mertens, J.-F. (1995). Two examples of strategic equilibrium. Games and Economic Behavior, 8(2), 378–388.] noted, a quasi-perfect equilibrium is nowadays considered superior to EFCE.

« Observe that the “quasi-perfect” equilibria \([\)..\(]\) are still sequential—and sequential equilibria have all backward-induction properties (e.g., Kohlberg and Mertens, 1986)—but are at the same time normal form perfect—which can be viewed as the strong version of undominated. (And every proper equilibrium is quasi-perfect.) Thus, by some irony of terminology, the “quasi”-concept seems in fact far superior to the original unqualified perfection itself. »

(from Mertens [Mer95])

The relationships among the different refinements is summarized in the Venn diagram of Figure 1.

S4.3.4 Computational complexity

Perhaps surprisingly, finding an EFPE or a QPE in a two-player game is not harder than finding a Nash equilibrium. In particular, in zero-sum games, an EFPE and a QPE can be found in polynomial time in the size of the input game. Table 1 summarizes the computational complexity of computing the Nash equilibrium refinements mentioned so far in two-player games.

S4.4 Trembling linear programs and computation of QPE and EFPE

We can compute a limit point of solutions to 2 and 4 using the same machinery. As a first step, just like what we did for the Nash equilibrium, we convert the bilinear saddle-point formulations 2, 4 into linear programs by dualizing the internal minimization problems. This gives us a linear program where the constraints matrix and the objective function depend polynomially on \(\epsilon\). In particular, for both QPE and EFPE we end up with a linear program of the form

where \(c , A\) and \(b\) are polynomial functions of \(\epsilon\) with rational coefficients. We will call an object of that form a trembling linear program (TLP), and a limit point of solutions to \(P ( \epsilon )\) as \(\epsilon \to 0^{+}\) a limit solution of the TLP. With this formalism, we can reframe the computation of an EFPE or a QPE as the problem of finding a limit solution to their corresponding TLPs.

We will now discuss the complexity of solving a TLP, and two different computational approaches. Both of them are based on the concept of basis stability (Recall that a basis of an LP is a subset of the program’s variables such that when only those columns of matrix \(A\) that correspond to those variables are included in a new matrix \(A\), the new matrix \(A\) is invertible [BT97[BT97] Bertsimas, D., & Tsitsiklis, J. (1997). Introduction to linear optimization., page 55].

If a stable basis were to be found, from there a limit solution of \(P ( \epsilon )\) could be computed in polynomial time. As it turns out, a stable basis always exists, and can be computed in polynomial time.

S4.4.1 Negligible Positive Perturbations (NPP)

Farina, Gatti and Sandholm [FGS18[FGS18] Farina, G., Gatti, N., & Sandholm, T. (2018). Practical Exact Algorithm for Trembling-Hand Equilibrium Refinements in Games. Neural Information Processing Systems (Neurips).], extending prior work by Miltersen and S [MS10] and Farina and Gatti [FG17], showed the following.

So, at least in principle, a solution to a TLP \(P ( \epsilon )\) could be computed as follows:

• First, compute the value of the NPP \(\epsilon^{∗}\) using the constructive proof of Theorem S4.5.
• Then, solve the numerical linear program \(P (\epsilon^{∗})\) to optimality. Since the bit complexity of \(\epsilon^{∗}\) is polynomial in the size of the TLP, the numerical LP can be solved to optimality in polynomial time, and a basis \(B\) can be extracted. From Theorem S4.5, such a basis is stable (Definition S4.4).
• Finally, extract the limit solution to the TLP from the stable basis.

The algorithm just described has polynomial complexity in the TLP size. In the case of the TLP arising form QPE and EFPE, that translates into a polynomial-time algorithm to find an exact EFPE and QPE in a two-player zero-sum game (see also Table 1).

S4.4.2 A significantly more scalable approach

While technically polynomial, the NPP-based algorithm described in the previous subsection is mostly of conceptual interest. In practice, because the value of the NPP is so small, any linear programming solver that wants to have a chance at solving the numerical linear program \(P (\epsilon^{∗})\) must—as a minimum—use rational arithmetic, rendering the algorithm extremely slow.

A significantly more scalable algorithm for solving TLPs, due to Farina, Gatti and Sandholm [FGS18], avoids the pessimistically small numerical NPP \(\epsilon^{∗}\) of Theorem S4.5 by using an efficient stability-checking oracle for checking if a basis is stable or not.

The iterative algorithm repeatedly picks a numerical perturbation \(\hat{\epsilon}\), computes an optimal basis for the perturbed LP \(P (\hat{\epsilon})\), and queries the basis-stability oracle. If the basis is not stable, the algorithm concludes that the perturbation value \(\hat{\epsilon}\) was too optimistic, and a new iteration is performed with a smaller perturbation reduced by a multiplicative constant (for example, divide it by \(\mathord{1000}\)). On the other hand, if the basis is stable, the algorithm takes the limit of the LP solution and returns it as the limit solution of the TLP. Correctness and termination are guaranteed by the following observation.

The practical algorithm is 3-4 orders of magnitude faster than the conceptual algorithm described in Section S4.4.1, and is the current state-of-the-art algorithm for computing QPE and EFPE.

S4.5 Bibliography for this lecture

S4.A Why not uniform lower bounds in QPE?

Not all vanishing perturbations \(ℓ_{1} ( \epsilon ) , ℓ_{2} ( \epsilon )\) in the QPE formulation 4 lead to a sequentially-rational equilibrium. For example, it is natural to wonder whether it is really necessary to consider lower bounds of the form \(\epsilon^{\sigma}\) instead of, for example, the uniform lower bound \(\epsilon\) for all sequences. After all,

surely a uniform lower bound of \(\epsilon\) would still force the whole game to be explored, wouldn’t it? While appealing on the surface, such a uniform lower bound might result in a solution that is not even subgame perfect, much less sequentially rational!

We illustrate this point with an example.

For any choice of \(\epsilon \in [ 0 , 1 / 4 ]\), we now argue that the only Nash equilibrium of the perturbed game assigns probability \(1 - \epsilon\) to action r of Player \(2\), and probability \(1 / 2\) to actions c and d of Player \(1\). Indeed, action a strictly dominates b, since all payoffs for the black player (Player \(1\)) are strictly lower in the subtree rooted at b. Hence, the black player must minimize the probability mass put on the sequences that contain action b, compatibly with lower bounds. Because we are using uniform lower bounds \(\epsilon\) on the probability of each sequence, the black player will need to put at least probability \(\epsilon\) on the four sequences bc, bd, bp, bq. This can be achieved when c, d, p, q are each selected with probability \(1 / 2\) and action b with probability \(4 \epsilon\). From the point of view of the white player (Player 2), information set C guarantees an expected utility of \(- 1 ⋅ 1 / 2 + 2 ⋅ 1 / 2 = 1 / 2\), while information set D guarantees and expected utility of \(0\). So, it is rational for the white player to put as much probability mass as allowed by the lower bounds to action r. This is achieved when action r is selected with probability \(1 - \epsilon\), and action \(s\) with probability \(\epsilon\).

So, as \(\epsilon \to 0^{+}\), any limit point sees Player \(2\) pick action r with probability \(1\) and Player \(1\) randomizing uniformly between actions c and d, despite action d being strictly dominated. Thus, both players will act irrationally (with Player \(1\) not even playing a best response in the subtree rooted at C) should Player \(1\) make the mistake of picking action b instead of a at the root A. The resulting equilibrium is not sequentially rational. (In fact, it’s not even subgame perfect, which is even stronger [KW82[KW82] Kreps, D. M., & Wilson, R. (1982). Sequential Equilibria. Econometrica, 50(4), 863–894.].)