Equilibrium Refinement for the Age of Machines: The One-Sided Quasi-Perfect Equilibrium
Authors: Gabriele Farina
Tuomas Sandholm
Venue: NeurIPS 2021 Poster (2021)
Keywords: extensive-form game
Nash equilibrium
equilibrium refinement

Abstract: In two-player zero-sum extensive-form games, Nash equilibrium prescribes optimal strategies against perfectly rational opponents. However, it does not guarantee rational play in parts of the game tree that can only be reached by the players making mistakes. This can be problematic when operationalizing equilibria in the real world among imperfect players. Trembling-hand refinements are a sound remedy to this issue, and are subsets of Nash equilibria that are designed to handle the possibility that any of the players may make mistakes. In this paper, we initiate the study of equilibrium refinements for settings where one of the players is perfectly rational (the ``machine'') and the other may make mistakes. As we show, this endeavor has many pitfalls: many intuitively appealing approaches to refinement fail in various ways. On the positive side, we introduce a modification of the classical quasi-perfect equilibrium (QPE) refinement, which we call the one-sided quasi-perfect equilibrium. Unlike QPE, one-sided QPE only accounts for mistakes from one player and assumes that no mistakes will be made by the machine. We present experiments on standard benchmark games and an endgame from the famous man-machine match where the AI Libratus was the first to beat top human specialist professionals in heads-up no-limit Texas hold'em poker. We show that one-sided QPE can be computed more efficiently than all known prior refinements, paving the way to wider adoption of Nash equilibrium refinements in settings with perfectly rational machines (or humans perfectly actuating machine-generated strategies) that interact with players prone to mistakes. We also show that one-sided QPE tends to play better than a Nash equilibrium strategy against imperfect opponents. 

Equilibrium Refinement for the Age of Machines: The One-Sided Quasi-Perfect Equilibrium
Gabriele Farina
Tuomas Sandholm Computer Science Department, CMU Strategy Robot, Inc. Strategic Machine, Inc. Optimized Markets, Inc. sandholm@cs. cmu edu
Computer Science Department Carnegie Mellon University gfarina@cs. cmu. edu
Abstract
In two-player zero-sum extensive-form games, Nash equilibrium prescribes optimal strategies against perfectly rational opponents. However, it does not guarantee rational play in parts of the game tree that can only be reached by the players making mistakes. This can be problematic when operationalizing equilibria the real world among imperfect players. Trembling-hame refinements are sound remedy this issue, and are subsets of Nash equílibria that are designed to handle the possibility that any of the players may make mistakes. In this paper, we initiate the study of equilibrium refinements for settings where one of the players is perfectly rational (the "machine") and the other may make mistakes. As we show, this endeavor has many pitfalls: many intuitively appealing approaches to refinement fail in various ways. On the positive side, we introduce modification the classical quasi-perfect equilibrium (QPE) refinement, which we call the one-sided quasi-perfes equilibrium. Unlike QPE, one- sided QPE only accounts for mistakes from one player and assumes that no mistakes will be made by the machine. We present experiments standard benchmark games and an endgame from the famous man-machine match where the Al Libratus was the first to beat top human specialist professionals in heads-up no-limit Texas hold' em poker. We show that one-sided QPE can be computed more efficiently than all known prior refinements, paving the way to wider adoption of Nash equilibrium refinements in settings with perfectly rational machines (or humans perfectly actuating machine- generated strategies) that interact with players prone mistakes. We also show that one-sided QPE tends to play better than a Nash equilibrium strategy against imperfect opponents.
Introduction
The Nash equilibrium solution concept prescribes optimal strategies against perfectly rational oppo- nents. However, it is well known that it has serious shortcomings when used to prescribe strategies be deployed against imperfect opponents who may make mistakes. Even two-player zero-sum games, it does not guarantee rational play in parts of the game tree that can only be reached if the players make mistakes. As a very simple perfect-information- game example, consider the game in Figure (l.ft). The bold lines show one of the Nash equilibria of the game. It does not matter whether the white player acting B chooses move or move because never gets to move if the black player acting at A plays rationally. So, in Nash equilibrium, the white player can choose move I. However, if the black player makes a mistake and chooses move b, it would be better for the white player to choose move r (thus getting payoff of 5 instead of 0). So, in that part of the game where the black player has made the mistake, the white player's Nash equilibrium strategy is not rational.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

In game-theoretic terms, it is not sequentially rational. This is problematic when operationalizing
B
B
B
(1,
(1, 1)
(0, 2)
(0,0)
()
(0,0) (-5,5) (-1,1)(-5,5)
(-1,
(1.1)
Figure I: Small extensive- form games which a non sequentialll-rationnn Nash equilibrium highlighted. The first payoff of each outcome is assigned to the black player, the second to the white player.
cquilibria in the real world among imperfect players. While in the particular example of Figure ! (Left) the issue could be resolved by using an equilibrium refinement called subgame perfect Nash equilibrium, that solution concept does not refine solutions much in imperfect-infoon infffcct-information games, where few subgames (nodes of the game tree that alone in their information set) exist. For example, consider the example in Figure [] (Center); the white player acting at information set B does not have any subgame, and therefore the highlighted eqquentiall-iiraatinn subgame perfect. Another refinement of Nash equilibrium is undominated Nash equilibrium ( (UNE), that is, Nash equilibrium where the pure strategies in the support of the equilibrium do not include strongly dominated strategies. UNE would remove the unreasonable Nash equilibria in the games of Figure [ (Left and Center), but there are other games where UNEs can be sequentially irrational [21]. In general, undomination and sequential rationality are incomparable in the sense that neither implies the other 21
Nash equilibrium is
For imwerfect- information games, the main family of equilibrium refinements (for example against sequential irrationality) is trembling-hune -hand refinements, which are significantly more intricate than subgame perfection [28] [2 31. Trembling-hane equilibria are a subset of Nash equilibria that are designed to handle the possibility that any of the players may make mistakes. Roughly speaking, each player is assumed to make every mistake with some small probability, and trembling-hen equilibria are the limit points of the sequence that arises that trembling (that is, mistake) probability approaches zero. As we will summarize later, there are multiple trembling-hand hand refinements that differ based on how the trembling constraints are set up.
In this paper, we initiate the study of equilibrium refinements for settings where one the players is perfectly rational (the "machine") and only the other may make mistakes. We will conventionally refer to the latter player as the "imperfect" player. This is a setting that is becoming increasingly common in AI applications such as recreational games, military settings, and business [23 12 As we show, this endeavor has many pitfalls: intuitively appealing approaches to refinement fail in various ways. On the positive side, we introduce modification of the classical quasi-perfect equilibrium (QPE) refinement, which we call the one-sided quasi-perfect equilibrium. Unlike QPE, one-sided QPE only accounts for mistakes from the imperfect player and assumes that no mistakes will be made by the machine. We present extensive experiments on standard benchmark games and an endgame from the famous man-machine match where the AI Libratus was the first beat top human specialist professionals in heads-up nimit Texas hold em poker. We show that one-sided QPE can be computed more efficiently than any prior trembling hand refinements, paving the way to wider adoption of Nash equilibrium refinements in settings with perfectly rational machines (or humans perfectly actuating strategies) that interact with imperfect players prone to mistakes. We also show that one-sided QPE tends to play better than Nash equilibrium strategy against imperfect opponents.
2 Extensive-form games
In this section we review standard concepts in the theory of extensive-fore (that is, tree-form) games. We will focus on two-player games with perfect recall and (potentially) imperfect information. An extensive-for formm game is game played on finite tree with payoffs at the leaves. Each node in the tree belongs to exactly one of the two players (which we call as Player 1 and Player 2), or belongs to a fictitious third player-calles the nature player-whose actions are sampled from a known distribution. We will sometimes denote the opponent of Player i E (1,2) with the symbol -i. The set of nodes that belong to the same player i {1,2} is split into partition I, called the information

---

partition of Player i. Each set I in the partition is called an information set: two nodes belong to the same information set when the player cannot distinguish between them when he or she needs act at them. When all information sets for all players are singleton sets, the player has no uncertainty about where in the game tree the are; in that case, the game is said to have perfect information. In this paper we only consider perfect-recal games. This means that the information partition of both players is such that any two nodes in the same information set share the same sequence of actions of that player from the root to those nodes. Intuitively, this means that the players do not forget about their past actions and observations in the game. Given two information sets 1', I E I, for the same player i, we say that I' is successor of I, written I' >= I, if the sequence of actions of Player i on the path from the root to any node in passes through some node in I'. Let A() denote the set of actions available at any of the nodes in the information set I E I₁ The set of sequences for Player is defined as the set of all information set-action pairs a E {(T,a) T E I, a E A(T)}. Each sequence o = =(T,a) uniquely identifies path from the root of the game tree down action a and information set T. The length |a| is defined as the number of Player i's actions on that path. Conceptually, a strategy in an extensive form games specifies a probability distribution over the set of actions ((T) available at each information set 1 E Zi We will represent strategies as vectors using the sequence-form 26 In that representation, the vector corresponding coordinate per each sequence of the player, indicating the product of the probabilities of the player's actions in that sequence. is well-known that under that representation. the set of all well-formed sequence-ford form strategies for the player is a convex polytope F,z: = f: for a suitable pair of sparse matrix and vector F,, fr encoding probability mass-conservation constraints (called sequence-form constraints). A strategy æ; for Player i is a best response to given strategy -- of the opponent if no other strategy for Player gives to Player strictly greater expected utility against --
representation [15 32
strategy has one
3 Nash equilibrium and its refinements
Nash equilíbrium is the most widely used solution concept game theory. A pair of strategies (æ) .22) for two players in a game is a Nash equilibrium if neither player is (strictly) better off by deviating to any other strategy if the opponent does not deviate. In the special case of zero-sum games, it is celebrated result that the set of Nash equilibria (æ1, x22 is the set of solutions to the bilinear saddle point optimization problem
min x. *TA, 222
max F Fi fi
Fa
20
#=20
In the rest of the paper will focus zero-sum games. There, any strategy that is part of Nash equilibrium is an optimal strategy against any Nash equilibrium strategy of the opponent, that is, against any rational opponent. Furthermore, if the opponent plays any strategy other than an equilibrium strategy, that can only increase our expected utility.
However, we illustrated in Figure [] Nash equilibrium suffers from the severe issue of being unable to capitalize on opponent mistakes when the opponent is, in fact, not perfectly rational. This true already in the zero-sum game setting, which is the focus of this paper[" While this issue is easy to avoid in perfect-inforration games by restricting attention to subgame-perfer Nash equilibria, the informatttnnooo case has been significantly more nuanced historically. The introduction of sequential rationality was a seminal step down that avenue [6].
We devote the rest of this section to the standard solution concepts that guarantee sequential ratio- nality (thereby soundly remedying the shortcomings of Nash equilibrium), that is, trembling-hand equilibrium refinements. The fundamental idea behind nembling-hande equilibria is to modify the Nash equilibrium optimization problem by adding constraints that force lower bounds of some forms on all action probabilities so as to force all parts of the game tree to be taken into consideration. A trembling hendllig-haadd hand equilibrium is then a limit point of those constrained Nash equilibria as the lower bounds approach zero. Two different classes of trembling- hand refinements are known, and they differ in the way they force the lower bounds. The extensive-form perfect equilibrium concept (Section 3.T enforces that each action be picked with at least some probability. That is, there is uniform lower
In non-zero-sun sum games, this issue is only exacerbated further. For example, non con-credible threats can be supported in Nash equilibrium, See also Section 4.3
3

---

bound on all action probabilities. The quasi-perfect equilibrium concept (Section 3.2 changes this by requiring lower bounds on sequences of actions rather than individual actions.
3.1 Extensive-form perfect equilibrium. Given a game r, the idea behind extensive-form perfect equilibria (EFPEs) is introduce parameter e > 0 (the trembling magnitude), and consider the perturbed game (e( ) in which each player can only play strategies that put probability mass 2 E on every action. An EFPE is then any limit point of Nash equilibria for the games I'(e) as + 0f (28). It is well-known (e.g., Kreps and Wilson [6]] that every game has at least one EFPE, and that EFPEs are sequentially rational.
3.2 Quasi-perfect equilibrium. Quasi-perfection, introduced by van Damme 33 is significantly more intricate to define than extensive-fome perfection. Instead of giving an explicit lower bound on the probability with which each action needs to be selected, the definition of quasi-perfect equilibrium (QPE) relies on refined notion of best response. We now give one of the multiple known equivalent definitions, and we present it for the special case of two-player games only. Several equivalent definitions that apply to more general games can be found in the original work by van Damme, as well as in the work by Miltersen and Sørensen [22) and Gatti et al. M
Definition (I-local purification). Let E {1,2} be a player, π be a strategy for Player i, and let I E I, be an information set. We say that strategy n' for Player is an I-local purification of if T is deterministic at any information set I' > I, and coincides with π at any other information set. When x' is an I-local purification of n, we further say that
n²' assigns probubility only to actions that have is e-consistent with π if, for all P probability 2 in
n' is optimal against a given strategy of the opponent if no other I-local purification of π achieves (stricily) higher expected utility against said stralegy of the opponent.
Definition 2 (e-quasi-perfect best response). A strategy π. is an e-quasi-perfect best response to the opponent strategy - (i) π assigns strictly positive probability to all actions of Player i; and (ii) for all information sets I E I, of Player i, every e-consistent I-local purifications of π, (Definition) 7 optimal for nH A strategy profile (T1, T22) where each strategy is an eqqusii-peffee best response to the opponent's 's strategy is called an e-quasi-perfect strategy profile.
Definition 3 (Quasi-perfect equilibrium), A quasi-perfect equilibrium is any limit point of e-quasi-
perfect strategy profiles as e 0+.
It is known since the work by Miltersen and Sørensen 22 that some QPEs (we call them Miltersen- Sorensen QPEs) can be computed in any two-player game as the limit point of Nash equilibria of perturbed games I'(e). akin to EFPE. The subtlety is that while in EFPE each perturbed game I'(e) mandates lower bound of c on the probability of playing each action, in the case of a Miltersen- Sorensen QPE the lower bounds are given on the probability of each sequence of actions. Specifically,
for any e > 0 and for each player i [1,2), let l, : E Ee denote the vector parametrized on and indexed on the sequences Σ, of Player i, whose entries are defined as
[[{)[o]= cd
Vo E Ex.
(1)
where |o| denotes the number of actions for Player i in the sequence Miltersen and Sørensen prove that any limit point of the solution to the perturbed optimization problem
22
min x TAA.22.
max F1 fi P3 fa
#1 (2
is a (Miltersenn-Sreensen)) QPE
3.3 A word of caution: Not all natural vanishing perturbations lead to sequential rationality
We found a potential pitfall when introducing lower bounds on sequence probabilities with the hope of computing trembling-hamn refinement. Not all vanishing perturbations &1 (2()) in the QPE formulation lead
sinieentiall--aationn equilibrium. For example, it is natural to wonder
Recentlyy Gatti et al. [|] took this construction further, and showed that any QPE can be expressed as a 2 as long as more general vectors of polynomials L,, l2 are used than in (I) In this perturbation defined in 1
limit point of solutions to
paper will focus

---

whether it is really necessary to consider lower bounds of the form elal instead of, for example, the uniform lower bound for all sequences. After all, surely a uniform lower bound of would still force the whole game to be explored, wouldn't it? While appealing on the surface, such uniform lower bound might result in solution that not even subgame perfect, much less sequentially rational! In particular, consider the perfect-recall game in Figure 2
We prove in the appendix that for any choice of E [0, 3/1], the only Nash equilibrium of the perturbed game assigns probability 1 - to action r of Player 2, and probability 1/2 to actions and d of Player 1. So, as - 0+, any limit point sees Player 2 pick action r with probability and Player 1 randomizing uniformly between actions e 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 make the mistake of picking action b instead of a at the root The resulting equilibrium is not subgame perfect, and consequently [66 Proposition 3).
cannot be sequentially rational
Action Probability
(2,-2) -2)
a
4e
b
4e
C
D
C, d, P.g
1/2
d
r
1
(1,-1) (-2 (0 (0,0)
8
Figure 2: Small perfect-information game that illustrates that uniform lower bounds can induce irrational behavior. Black nodes belong Player 1, the white node belongs Player 2.
4 One-sided quasi-perfect equilibrium
All of the trembling-hame hand equilibrium refinements summarized in Section are two sided, in the sense that both players are trembling. That two-sidedness comes at a computational cost: both the domain of the maximization and minimization problem in the saddle point formulations (for example, Equation (2) in the case of QPE) of the refinements are perturbed, making the computation of a limit point computationally expensive. Yet, in many strategic interactions of interest, a player might be concerned about being able to capitalize on the opponent's 's mistakes, but not about making mistakes of her own. After all, the age of machines, that player might well be a bot interacting strategically (for example, playing a poker tournament) against imperfect opponents. In that situation, the player in question might therefore seek, in the interest of lowering the computational requirement of computing a robust strategy, to find equilibrium points that are robust to perturbations of the opponent's 's strategy only, thereby breaking the two-sidedness of all known trembling hand equilibrium refinements.
In this paper, we introduce the first one-sided trembling- hand refinement, which we coin one-sided quasi-perfect equälibriun. Because of the asymmetric role of the players, from now we stop referring to the players as Player 1 and 2, and adopt the terms machine player and imperfect player to highlight their asymmetric role. The machine player is assumed to never make mistakes: lower bounds on the probability of play (the "trembling hands") are only introduced for the imperfect player. Accordingly, from now on we will drop subscripts and denote quantities that belong to the players, and will use m and h for quantities belonging to the machine and the imperfect player, respectively.
4.1 Definition and preliminary considerations. In order to formally define the one-sided quasi- perfect equilibrium solution concept, we start by removing some of the symmetry between the two players in Definition 2
In particular, we introduce the following notion.
Definition& 4 (One-sided quasi-perfect equilibrium). We call a strategy profile (Tm, Th)) one-sided -quasi-perfece strategy profile if hh is an c-quasi-perfer best response (Definition 2 to Ti and T. is a best response to nh We say that (Tm. nτ)) is an one-sided quasi- equilibrium if it is the limit point of one-sided e-quasi-perfers strategy profiles, as - 0++
equilibria do indeed form refinement of the Nash equilibrium, as we establish in the next theorem (see the appendix for a proof).
One-sided
Theorem 1. Every one-sided quasi- perfect equilibrium is Nash equilibrium.
5

---

At this stage it is still technically unclear whether one-sided quasi-perfect equilibria exist at all. To show existence, as a first step we slightly extend the result by Miltersen and Sørensen [22] that we mentioned in Section 3.2 and show that one-sided e-quasi-perfect strategies exist, and that one can be computed as the solution to a bilinear saddle point problem.
Lemma 1. Consider the bilinear saddle point problem
max Fm Rm fm Fy =fn
min
Im Am
(3)
2n (e)
where (x( is as in Equation ( Then, for any E for which the domain of the minimization problem is nonempty, any solution (3) is a one-sided e-quasi-perfect strategy profile.
From here, the existence of one-sided quasi causi-perfect equilibria equiiittu can be established with a straightforward compactness argument. The domain of the minimization problem of (3 becomes nonempty for small enough values of the trembling magnitude e > 0. Therefore, for small enough e the domains of the maximization and minimization problem in 3 compact and nonempty. That, combined with the fact that the objective function bilinear, immediately guarantees that (3) admits a solution for any small enough e > 0. Furthermore, such a solution belongs to the Cartesian product of the two players' sequence-fone polytopes-a compact sel-thereby guaranteeing that a limit point as + 0+ exists as valid strategy profile. So, Lemma T
immeeditell implies the following corollary.
Corollary 1. Every two-player zero-sum extensive-form game with perfect recall has at least one one-sided quasi-perfect equilibrium.
4.2 One-sided QPEs as trembling linear programs. In this subsection, we show that the problem of computing one-sided perffete equilibrium strategy &m. for the machine player can be cast to a linear program parameterized by the trembling magnitude e. We call such a linear program a trembling linear program, in concordance with nomenclature in the prior work by Farina et al. [7]. Specifically, the following result, which follows by linear programming duality, will be central in our discussion. An elementary proof is offered in the appendix.
Proposition 1. Any limit point of solutions to the trembling linear program
arg max (c)) am + (fr- - (e))
Zm
s.l. 1 xm F.
P(e)= =
Fmnm
= fm
0, free.
as the trembling magnitude - 0+ a one-sided quasi-perfect equilibrium strategy for the machine player.
4.3 A second word of caution: One-sided QPE is inappropriate for general-sum games. Se- quential irrationality occurs in both zero-sum and general-sum games because the Nash equilibrium concept does not consider mistakes by the players. In general-sum games, sequential irrationality is exacerbated further by the presence of non- non-credible threats (which cannot occur in zero-sum games because there are no actions that hurt both players). For example, consider the highlighted Nash equilibrium in the small general-sum game of Figure (Right). If the black player acting at A were play 1, which hurts both players.
to actually play b, it would be irrational for the white player Effectively, the white player is "threatening" to play / instead of r to force the black player's hand and push the black player to settle for an inferior payoff of 0. By forcing all players account for mistakes, even their own, trembling- hand equilibria are able to prevent the irrationality stemming from non-credible threats. Indeed, when action b is played with probability at least equilibrium would support action 7 for the white player. Hence, the equilibrium in Figure IT (Right) cannot be an EFPE or QPE, which are limit points of Nash equilibria of perturbed games. However, because in one-sided QPEs only trembles from one player are considered, the one-sided QPE concept generally unable to prevent non-credible threats. Specifically, if the black player were the machine player, and the white player the imperfect player, the highlighted equilibrium in Figure [ (Rihht) would be a one-sided QPE. This should serve as cautionary tale against using one-sided QPE in general-sun snneral-sumaa settings.
no Nash

---

5 Computation of one-sided QPEs
While QPEs and EFPEs can in theory be computed in polynomial time (in the size of the game) in two-player zero-sum games [22 6), their computation is fraught with difficulties that have his- torically slowed down their adoption. First, trembling-hand refinements are limit points, and not just the solution to a numeric optimization problem. Second, finding a Nash equilibrium subject to trembling constraints (i.e., constraints that enforce actions are played with given lower bounds on probability) becomes numerically unstable when e is small. In this section we show that while the computation of one-sided QPEs is still nontrivial task, one-sided QPEs have nice property that makes their computation comparatively easier and more numerically stable than QPEs and EFPEs. Specifically, the trembling linear program Proposition T differentiating property that only appears in the objective function and not in the constraints. As summarized in the table, neither EFPEs nor (two-sided) QPEs enjoy this property. Indeed, the trembling LP formula- tion of EFPE needs to express the constraint that each action is picked with probability 2 e. That is expressed by constraints of the form [T[(T, a)] (x (7) for all information sets I and actions a E Ar, and for that reason the known trembling LP formulations of EFPE have appear in the left-hand side (LHS) of the constraint matrix 66 7.. On the other hand, the trembling LP formulation of regular, two-sided MMiltersen-Sorensen) QPE has a component
defined in Section 4.2 has the convenient,
Depends on c? LHS RHS Obj
Equilibrium
EFPE
x
QPE
X
One-sided QPE
X
x
lower bound on the vector Ims i.e., constraints of the form 2m 2 Lm (c). So, in QPE appears also in the right-hand side (RHS) of the constraints [22]. Part of the high complexity in practice associated with the computation of EFPE and QPE is related to where appears. As a rule of thumb, having terms in the constraint (left-hand side) matrix makes the problem the hardest, as those terms impact the numerical stability of the basis matrix, which needs to be inverted (more precisely, factorized) after every pivoting step of the simplex algorithm. That is avoided in the somewhat easier case where only appears on the right-hand size of the constraints, though that case is still hard, given that the feasible set still depends on e, thereby making the task of maintaining feasibility as E + 0+ nontrivial. One-sided QPE avoids both of these issues, by only having dependence in the objective function: the feasible set of P(E) is constant, and only the coefficients of the objective function change (continuously) as e < -* 0+.
Currently, the only known algorithm for finding limit solutions to trembling linear programs (of which QPEs, one-sided QPEs, and EFPEs are examples) is via the algorithm of Farina et al. 7 That
algorithm computes limit point of solutions of any trembling linear program, such as P(c)) given in Section 4.2 At a high level operates as follows. First, a value for e* is chosen arbitrarily. Then, the linear program (LP) Pcc)) is solved numerically to optimality by using the simplex method, and an optimal basis for the LP is computed. A stasiiitaabilit oracle is then run, to check whether the basis that was computed numerically is stable, that is, whether it would remain optimal so, the algorithm terminates, otherwise the value of E* is reduced (typically by a multiplicative factor). The procedure is repeated for the new value of e", and so on. The loop continues until stability of the basis is established. While the details of the basis stability oracle are complex and beyond the scope of this paper, in the rest of the section we point out few computational shortcuts that enabled by the fact fact- discussed above-thee that the trembling linear program for one-sided QPE exhibits dependence on e only in the objective function. In the discussion, assume some familiarity with the simplex algorithm and the concept of basic and non-basic columns.
0+: if
The feasible set in the trembling linear program for one-sided QPEs is independent of Hence, the optimal basis computed for the numeric perturbation value e" remains feasible even after the e* is reduced. So, at each iteration of the algorithm by Farina et al. 77]. we can very effectively warm start the simplex method with the basis computed in the previous iteration, cutting through the first phase of the simplex algorithm (computation of feasible basic solution), and jumping straight to pivoting until a new optimal basis is found. This shortcut is not possible in QPEs and EFPÉS.
Similarly, when evaluating whether computed basis remains optimal when the limit is taken, we can soundly skip verifying feasibility in the limit: since the computed basis is optimal for a given
1 'Other algorithms provide approximate solutions to approximate solution concepts. For example, Farina al. g and Kroer et al. [17] propose methods based on regret mininization and the excessive gap technique (25). re- spectively, to approximate solutions to games subject to trembling constraints for specific trembling magnitude. They do not provide any guarantee of actually finding (or even approximating) actual QPEs EFPEs.
7

---

numeric value of c², it must be feasible. Because the feasible set does not change as é goes to 0, the basis must remain feasible in the limit. The same cannot be said for QPEs and EFPEs, for which instead it is necessary to investigate feasibility of the basis in the limit at every iteration.
A consequence of the previous point is that only the reduced costs of the nonbasic columns matter when evaluating whether a given basis is optimal in the limit. Because é does not appear in the constraint matrix that defines the trembling linear program for QPE and one-sided QPE, the reduced cost of every nonbasic column is polynomial function of e, as opposed to rational function like in the more general case. This greatly simplifies the implementation of the basis stability oracle for one-sided QPEs. Specifically, none of the discussion in the original paper by Farina et al. 7 about handling singular basis matrices and Laurent series applies to one-sided QPE. The same property applies to QPEs, but not to EFPEs. In the latter case, the stability oracle need to be implemented by taking into account the dependence of the constraint matrix
reduced costs using
In the experiments (Section 6), we implemented the algorithm by Farina et al. 7 by taking advantage of the computational shorteuts we just described. As we show empirically, the three considerations above translate into a reduced computational burden when computing one-sided QPEs compared to (regular, two-sided) QPEs and EFPEs.
6 Experimental evaluation
We compare one-sided QPEs against EFPE and MMiltersen-Sorenseee QPE, along two metrics: I) the time required to compute the refinement, and 2) how the refinement fares against imperfect opponents, when compared to an exact but potentially unrefined Nash equilibrium computed by the two state-of-the-art linear programming solvers CPLEX and Gurobi. We implemented from scratch the algorithm by Farina et al. 77] to solve the trembling linear programs corresponding to the three equilibrium refinements. Our implementation takes the computational shortcuts described in Section for one-sided QPES (and for QPEs as well where applicable, that is, the third bullet point of that section). The algorithm is single-threaded, was implemented in C++, and was run on a machine with 32GB of RAM and an Intel processor running at a nominal speed of 2.4GHz per core.
As mentioned in Section 5 the algorithm computes, optimal basis of each trembling linear program where the perturbation magnitude e has been set to a numerical value c". We start from the value e* 10-6 and use Gurobi to solve the linear program. After the first iteration, the basis is not stable, we re-solve the linear program, again for c" 10-6 using Google's open-source linear programming solver (GLOP), which we modified 1000-digit precision floating point numbers via GNU's MPFR library. From there onward, after every unsuccessful iteration of the algorithm (that is, where the basis is not stable), the value of e is decreased by a factor 1000 and solved again with our modified version of GLOP, until a stable basis is found. Unlike the original paper by Farina et al. 7. we do not employ a rational precision implementation (that is, one that represents all numbers as ratios of integers to achieve an exact preenittepreciiion" solution) of the simplex algorithm. Instead, we found our 1000-digit precision modified GLOP solver to be drastically faster, and we use it across the board in place of the rational simplex. The basis stability oracle is implemented using rational precision, as described in the original paper 77. We use the GNU's GMP library to implement rational arithmetic. Therefore, our answer is exact (i.e., infinite-precisionn even though the intermediate steps are not.
intermediate step every iteration, an
to use
6.1 Computation time. We compare the compute time required to find a one-sided QPE strategy, (two-sided) QPE strategy, and EFPE strategy in six standard benchmark games: three instances of Ledue poker (29] of increasing size, one relatively large Goofspiel game (27), Liar's Dice, and one real river endgame from the "Brains vs A/" competition that was played by the Libratus AI. A description of each game is available in the appendix. To scale computation to the river endgame tractable, we solved the endgame using a coarser betting abstraction than the one used by Libratus. To our knowledge, it is the first time that ssquentially-rationne poker endgames. The dimensions of each game are listed in Table [[eft)) Runtimes for each of the solution concepts are given in Table [ (Right). We observe that one-sided QPE can be computed consistently faster (roughly by a factor 4-3x) than two-sided QPE, and the latter usually twice as fast as EFPE. This is consistent with our discussion in Section 5 In the river endgame we implemented the sparsification technique described in Zhang and Sandholm [x] to bring down the number of nonzeros of the payoff matrix from 21 million to roughly 167 thousand combined nonzeros in the sparsification
equilibria are investigated in real
8

---

when solving the linear program at each iteration (see the appendix for more details). In the river endgame, only one-sided QPE could be computed for both players. A (two-sided) strateyy could only be computed for Player 2, as Gurobi terminated abnormally due to numeric instability when solving for Player None of the EFPE strategies could be computed, due to numerical instability in GLOP, which terminated with an error due to the basis being singular to working precision. With its 21 million terminal states, a one-sided QPE in the river endgame represents the upper limit of what equilibrium refinement technology can handle today. The numerical instability witnessed in QPE and EFPE for that benchmark game is well consistent with our discussion in Section S
Information sets
One-sided
Game instance
Sequences
Leaves
Player
QPE
QPE
EFPE
Player 1
222ms
915ms
1.70s
Ledue poker (5 ranks)
780
1822
5500
Player 2
387ms
593ms
1.11s
Player 1
1.58s
5.81s
12.70s
Ledue poker (9 ranks)
2484
3798
32724
Player 2
2.65s
6.73s
14.95s
Player 1
8.37s
42.698
1m 36s
Ledue poker (13 ranks)
5148
12014
989956
Player 2
17.35s
38.94s
1m 42s
Goofspiel (4 ranks)
423
21 298
13824
Player 1
5.50s
25.68s
55.67s
Player 2
5.58s
27.29s
53.97s
Liar's dice
24576
49 142
147 420
Player I
26. 86s
2m 18s
11m 02s
Player
28.36s
10m 25x
Player Player
19m 3Gs
failure
failure
River endgume
17 700
494178
21 999
10m 14s
11m
failure
Table I: (Left) Game instances we experiment on, and their size. (Right) Compute time necessary to find optimal strategies according to different solution concepts.
6.2 Game-theoretic performance. We compare the game-theoreee performance of the (refined)
one-sided QPE strategies computed in Section against the (unrefined) Nash equilibrium strategies computed by Gurobi and CPLEX, the two leading linear programming solvers. To do so, we generated sequence of imperfect opponents by collecting the strategies output by CFR [4 popular self-play algorithm that converges to Nash equilibrium in extensive- form games. We ran CFR for 10000 iterations. Then, we let our one-sided QPE strategies and the two unrefined Nash strategies (one from Gurobi and one from CPLEX) play against each of the imperfect opponents, and measured the difference in expected utility achieved by the strategies, normalized by the absolute value of the game. Results for the four largest games are shown in Figure 3 (plots for the two remaining games are the appendix). For each game, the top plot shows the difference in expected utility (normalized by the absolute value of the game) obtained by our refined one-sided QPE strategy for machine Player 1 when compared to the Nash equilibrium strategy for Player 1 computed by Gurobi (solid blue line) and CPLEX (dashed orange line). The bottom plot shows the same, in the case where the machine player is set to Player 2 instead. The x-axis in each plot measures the exploitability of the imperfect player, normalized by the absolute value of the game. In the river endgame, the strategies computed by CPLEX are dual-infcasible (likely due to numeric instability). which explains why the curves do not pass through the origin. Our preliminary analysis suggests that refined strategies might indeed offer benefits over non-refined Nash equilibrium strategies. However, we point out that sometimes Gurobi and CPLEX happened to compute a strategy that was more exploitative than one-sided QPE for the specific irrationality of the CFR agents at that level of exploitability (for instance, in Liar's dice for exploitability up to R 3). This is consistent with the theory: nothing prevents Gurobi or CPLEX terminate on a sequentially-
strategies despite no constraints in that direction being imposed. As the experiments overall show, such an occurrence appears to be rare.
7 Conclusions, discussion, and future research
In this paper, we introduced refined solution concept- the one-sided quasi-perfcee equilibrium suitable for zero-sum games where "machine" player is not concerned by the possibility of making mistakes, but wants to make sure to account for the possible mistakes of an imperfect opponent. Along the way, we gave several fundamental results, and warned against common pitfalls. We showed that our refinement can be computed more effectively than the known existing alternatives in practice, and provided evidence that refined strategies might indeed outperform unrefined strategies, even

---

Leduc poker (13 ranks)
Goolspiel (4 ranks)
Liar's ' dice
River endgame
(One-sided sideddddddddd QPE. NNshh) |Game
(Machine pl:
1009%
1.00%
100%
0.509
250%6
1059
0%
0.00%
(Mashine pt: 2)
1.00%
50%
100%
5056
0.504
0%
0%
0.00%
09%
10
01.11
0.1
0.2
10
10
Opponzat's explonabilitt
Opponest's explaitisilitt (nonmalized)
Opponent's exploinbility (normalizzd)
Oppanenn's exploitaillity (sormalized)
(nomallzzdd
Figure 3: Increase in expected utility achieved by (refined) one-sided QPE stralegies compared to the (unrefined) Nash equilibrium strategy for the game computed by Gurobi (solid blue line) and CPLEX (dashed orange line).
in benchmark games of interest including-for the first time-a real poker endgame. However, significantly more work needs to be done before refinements can be regarded as an appealing drop-in replacement of Nash equilibrium as prescriptive tool. More work certainly remains to be done to enable computation of refined Nash equilibrium strategies remains a challenging problem (in our experiments, the computation of refined strategies was 1-2 orders of magnitude slower than the computation of unrefined strategies using commercial solvers).
Some readers might be wondering why we opted only consider the one-sided version of quasi- perfect equilibrium, and not, say, also the one-sided version of extensive- perfect equilibrium. The first reason stems from computational considerations: QPEs have the advantage over EFPEs that the trembling magnitude e does not appear in the constraint matrix of the trembling linear program (see also Section 5) and that property carries over to their one-sided versions. The second reason is that there is consensus in the literature that QPEs are superior refinements than EFPEs 20 13 [2] (i) an EFPE may prescribe the players to play weakly dominated strategies, while a QPE never does; and (ii) in two-player games, a QPE is also a perfect equilibrium of the normal form, whereas EFPE is not. This led Mertens [20] to write: "Observe that the "quasi-perfect" equilibria [..] are still sequential-and sequential equilibria have all buckward-induction properties (e.g., Kohlberg and Mertens [[4])-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" "rrasii"-concen -concept seems in fact far superior to the original unqualified perfection itself.". We leave the task of defining and exploring the theoretical and practical aspects of one-sided EFPES and other one-sided equilibrium refinements as future research.
We remark that our one-sided QPE notion does not satisfy the traditional notion of sequential rationality, which is two-sided. In future work it might be interesting to define one-sided notions of sequential rationality and prove that our solution concept satisfies them. We observe that it is also possible to straightforwardy define one- sided notions of undominated Nash equilibrium. Among two-sided concepts, it has been shown experimentally that undominated equilibrium performs better than unrefined Nash equilibrium in reasonably-sizee sized poker games g and even as well as trembling- hand refinements [5). at fraction of the computational cost. However, the analysis was performed on small games only due to the scalability limitations of trembling- The solution concept and algorithms introduced in this paper open the door for comparing one-sided QPE against one- and two-sided undominated Nash equilibrium at significantly larger scale.
equilibrium finding at the time.
Finally, we mention that empirically studying how much the theoretical benefit of trembling-hand solution concepts translates into practical performance against humans would be interesting. However, an appropriate analysis would require setting up human experiments, which is notoriously a complex undertaking. We leave that as a possible direction for future research. The analysis in our paper can be viewed as a first smoke test (in fact, the first of its kind, and on games significantly larger than anything prior refinement technology could scale to), but should not be taken as proof that refinements bring significant advantages compared to unrefined Nash strategies against human opponents. Our primary goal with this paper was to help scale up refinement computation technology to even start to enable those further experiments and investigations such important topic.
10

---

Acknowledgments
This material is based work supported by the National Science Foundation under grants IIS- 1718457, IIS-1901403, and CCF-1733556, and the ARO under award 191200010881 Gabriele Farina supported by Facebook fellowship.
References
[1] Michael Bowling, Neil Burch, Michael Johanson, and Oskari Tammelin. 2015. Heads-up Limit Hold' em Poker is Solved. Science 347, 6218 (Jan. 2015).
[2] Noam Brown and Tuomas Sandholm. 2017. Superhuman Al for heads-up no-limit poker: Libratus beats top professionals. Science (Dec. 2017), eaao1733.
[3] Noam Brown and Tuomas Sandholm. 2019. Solving imperfecttinfooration games via dis- counted regret minimization. In AAAI Conference Artificial Intelligence (AAAI).
[4] Noam Brown and Tuomas Sandholm. 2019. Superhuman AI for multiplayer poker. Science 365, 6456 (2019), 885-890.
[5] Jifí Čermák, Branislav Bošanský, and Viliam Lisy. 2014. Practical performance of refinements of Nash equilibria in extensive-form zero-sum games. In European Conference on Artificial Intelligence (ECAI).
[6] Gabriele Farina and Nicola Gatti. 2017. Extensive-Form Perfect Equilibrium Computation in Two-Player Games. In AAAI Conference on Artificial Intelligence (AAAI).
[7] Gabriele Farina, Nicola Gatti, and Tuomas Sandholm. 2018. Practical Exact Algorithm for Trembling-Hand Equilibrium Refinements in Games. Neural Information Processing Systems (NIPS).
[8] Gabriele Farina, Christian Kroer, and Tuomas Sandholm. 2017. Regret Minimization in Sahaviorally-Constriiinn Zero-Sum Games. In International Conference on Machine Learning (ICML).
[9] Sam Ganzfried and Tuomas Sandholm. 2013. Improving Performance in Imperfect- Games with Large State and Action Spaces by Solving Endgames. In AAAI Workshop on Computer Poker and Imperfect Information.
[10] Sam Ganzfried and Tuomas Sandholm. 2015, Safe Opponent Exploitation. ACM Transaction on Economics and Computation (TEAC) 3, 2 (2015), 8:1-28. Best of EC-12 special issue.
[11] Nicola Gatti, Mario Gilli, and Alberto Marchesi. 2020. A characterization of quasi-perfect equilibria. Games and Economic Behavior 122 (2020), 240-255.
[12] Srihari Govindan and Robert Wilson. 2012. Axiomatic Equilibrium Selection for Generie Two-Player Games. Econometrica 80, (2012), 1639-1699.
[13] Srihari Govindan and Robert B Wilson. 2006. Sufficient conditions for stable equilibria. Theoretical Economics 1, 2 (2006), 167-206.
[14] Elon Kohlberg and Scan-Framconi Mertens. 1986. On the strategic stability of equilibria. Econometrica 54 (1986), 1003-1037.
[15] Daphne Koller, Nimrod Megiddo, and Bernhard von Stengel. 1996. Efficient Computation of Equilibria for Extensive Two-Person Games. Games and Economic Behavior 14, (1996).
[16] David M. Kreps and Robert Wilson. 1982. Sequential Equilibria. Econometrica 50, 4 (1982), 063-894.
[17] Christian Kroer, Gabriele Farina, and Tuomas Sandholm. 2017. Smoothing Method for Ap- proximate Extensive-Fonn Perfect Equilibrium. In International Joint Conference on Artificial Intelligence (IJCAI).
[18] Marc Lanctot, Kevin Waugh, Martin Zinkevich, and Michael Bowling. 2009. Monte Carlo Sampling for Regret Minimization in Extensive Games. In Neural Information Processing Systems (NIPS).
[19] Viliam Lisy, Mare Lanctot, and Michael Bowling. 2015. Online Monte Carlo counterfactual regret minimization for search in imperfect information games. In Autonomous Agents and Agent Systems.

---

[20] J-F Mertens. 1995. Two examples of strategic equilibrium. Games and Economic Behavior 8, 2 (1995), 378-388.
[21] Peter Bro Miltersen and Troels Bjerre Sørensen. 2006. Computing Proper Equilibria of Zero- Sum Games. In Computers and Games.
[22] Peter Bro Miltersen and Troels Bjerre Sørensen. 2010. Computing a Quasi-Perfect Equilibrium of Two-Player Game. Economic Theory 42, 1 (2010).
[23] Matej Moravčík, Martin Schmid, Neil Burch, Viliam Lisý, Dustin Morrill, Nolan Bard, Trevor Davis, Kevin Waugh, Michael Johanson, and Michael Bowling. 2017. DeepStack: Expert-level artificial intelligence in heads-up no-limit poker. Science (May 2017).
[24] Roger B. Myerson. 1978. Refinements of the Nash equilibrium concept. International Journal of Game Theory 15 (1978), 133-154.
[25] Yurii Nesterov. 2005. Excessive Gap Technique in Nonsmooth Convex Minimization. SIAM Journal of Optimization 16, (2005).
[26] Romanovskii. 1962. Reduction of a Game with Complete Memory a Matrix Game Soviet Mathematics (1962).
[27] Sheldon M Ross. 1971. Goofspiel- game of pure strategy. Journal of Applied Probability (1971), 621-625.
[28] Reinhard Selten. 1975. Reexamination of the perfectness concept for equilibrium points in extensive games. International journal of game theory (1975).
[29] Finnegan Southey, Michael Bowling, Bryce Larson, Carmelo Piccione, Neil Burch, Darse Billings, and Chris Rayner. 2005. Bayes' Bluff: Opponent Modelling in Poker. In Conference on Uncertainty in Artificial Intelligence (UAI).
[30] Eric van Damme. 1984. A relation between perfect equilibria in extensive form games and proper equilibria in normal form games. International Journal of Game Theory (1984).
[31] Eric van Damme. 1991. Stability and perfection of Nash equilibria. Vol. 339. Springer.
[32] Bernhard von Stengel. 1996. Efficient Computation of Behavior Strategies. Games and Economic Behavior 14, 2 (1996), 220-246.
[33] Brian H. Zhang and Tuomas Sandholm. 2020. Sparsified Linear Programming for Zero-Sum Equilibrium Finding. In International Conference on Machine Learning (ICML).
[34] Martin Zinkevich, Michael Bowling, Michael Johanson, and Carmelo Piccione. 2007. Regret Minimization Games with Incomplete Information. In Neural Information Processing Systems (NIPS).
12


Reviews:
[{"review_id": "ympW6Y_puQI", "reviewer": "Reviewer_gGTR", "summary": "In zero-sum games, playing any Nash equilibrium guarantees optimal performance against an optimal opponent.  However, if the opponent plays suboptimally, playing according to Nash equilibrium may not take full advantage of their mistakes; this is because Nash equilibrium does not require optimal behavior at states that are not reached by mutually optimal play.  Multiple \"trembling hand\" refinements exist that require optimal play at all states, even those that can be reached only if one or the other of the players play suboptimally.  However, these refinements are typically the limit of equilibria of perturbed games in which each action is played with positive probability, as this probability is sent to 0; this can make them expensive to compute.\n\nThis paper considers a special case of the quasi-perfect equilibrium refinement, which it calls the one-sides quasi-perfect equilibrium.  In this refinement, only one agent (the \"human\") is assumed to tremble; the other agent (the \"machine\") is assumed to always play optimally; thus, the machine player does not need to account for the possibility that they themselves will err, only that their opponent will err.  The paper shows that it is possible to under these assumptions to efficiently compute a refined equilibrium strategy for the machine player, and demonstrate empirically that a refined strategy will perform substantially better against a suboptimal player (where suboptimal players are taken by intermediate steps of a CFR self-play training run).\n", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, I'm very enthusiastic about this paper.\n\nThe problem that the paper studies is a long-standing issue in computational game theory.  The one-sided solution is novel (and very clever!), and the paper does an excellent job of giving an intuition for why it enables faster computation.  The empirical results are taken with respect to relatively toy domains, but I find them very convincing evidence that refinements really matter in zero-sum domains.\n\nThe paper is very clearly written and well-organized.  The minor exception is the introductory material in section 2, which I found somewhat rushed; if I were not already familiar with sequence-form strategies for imperfect information games, I'm not sure I would have been able to figure it out from this section.  I have a couple of specific suggestions below, but really the whole section could stand to be edited for clarity.\n\n* p.2: \"the sequence of actions of Player i on the path from the root to any node in I passes is a superset of the set of actions of the same player on the path from the root to any node in I'.\": This is very confusingly written.  Once you have defined sequences it might be simpler to say that any sequence in I' contains an action at I.\n\n* p.3: \"containing the probability of all of the player's actions in that sequence\": This is unclear; perhaps the product of the probabilities of the player's actions in that sequence?", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors address the technical limitations of their work quite carefully.\n\nRegarding societal impact, it would probably be wise to engage a bit more with the fact that the whole premise of the paper is exploiting suboptimal opponents.  In poker this is a morally uncomplicated goal, but if the authors envision this algorithm being used outside the domain of literal games, it becomes more problematic.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "kfFdl8qhmV", "reviewer": "Reviewer_K3jG", "summary": "This paper investigates a trembling-hand refinement of Nash equilibrium in sequential games in which one of the players is considered entirely rational (i.e., a machine), while the second player makes mistakes the first player should account for (i.e., a human). The authors discuss two most commonly studied two-sided variants of trembling equilibria in sequential games - extensive-form perfect equilibrium (EFPE) and quasi-perfect equilibrium (QPE) - and argue that QPE is more suitable for introducing the one-sided variant, as it is both more efficiently computable and considered superior to EFPE in the literature. The paper proves that every one-sided QPE is a Nash equilibrium, and it is guaranteed to exist in every two-player zero-sum sequential game with perfect recall. Moreover, it introduces a so-called trembling linear program the one-sided QPE is a limit of, as the trembling magnitude approaches zero. The solution of the trembling linear program is reached via an algorithm described in the previous work [5], which the authors adapt to take advantage of specific properties of the program for one-sided QPE. In the last part of the manuscript, the performance of one-sided QPE strategies is evaluated (i) against the EPFE and regular QPE strategies in terms of computational time, and (ii) against unrefined Nash strategies in terms of expected utility when the opponent adopts an imperfect strategy computed by CFR. The results suggest that the one-sided QPE could be computed 4-5x (8-10x) faster than two-sided QPE (EFPE) and achieve higher expected utilities than unrefined Nash strategies, especially when the opponent is more exploitable.\n", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The prose of the paper is elegant and natural; the authors managed to introduce all the necessary notions comprehensively and with just enough examples. The paper's motivation is clear, and I believe the one-sided QPE is an equilibrium that deserves to be studied. The authors fittingly discuss the related concepts and how their results fit into the existing literature on trembling-hand equilibria. I find the presented theoretical results sound and conceptually interesting, even though they do not seem too difficult to prove. I appreciate the two \"words of caution\" in the main text that explain how intuition might sometimes fail us when perfection is one-sided. The experimental results are sufficient to show how the theoretical advantage of one-sided QPE of having the trembling magnitude only in the criterion translates into the faster computation. I also have a few minor questions relating primarily to the experimental part.\n\nI wondered how long did cplex or gurobi take to compute the ordinary Nash strategies compared to the trembling-hand concepts? Also, according to the results, the unrefined Nash strategies sometimes achieve even higher expected utility than one-sided QPE. It is understandable that when the opponent is unexploitable, both approaches should perform about the same. However, I fail to find a reason why would some unrefined Nash strategies outperform the one-sided quasi-perfect strategies for exploitable opponents, as seen, e.g., in the Liar's dice when the exploitability is lower than (roughly) 3. Did the authors attempt to explain such findings?\n\nThe text mentions that the CFR ran for 10k iterations. How were the opponents of different exploitability generated? Were they sampled from the CFR strategies up to 10k  (e.g., for 3k, 5k, etc.), or somehow differently? And in case the CFR strategies strayed off the equilibrial path where no behavioral strategy may be defined by the solutions computed by cplex or gurobi, which actions did the machine player take?\n\nLastly, the motivation brought up consistently across the paper is to compute entirely rational strategies against humans. In the experiments, the imperfect human strategies are modeled by a limited number of CFR iterations. I agree that CFR indeed produces imperfect strategies when the number of iterations is low; still, I am unsure if the CFR strategies actually model human behavior well. Were the imperfections CFR produces ever shown to represent human decision-making well?\n\nIt seems intuitive that every (Miltersen-Sorensen) QPE should also be a one-sided QPE. Is that correct?\n\nA few possible typos:\nLine 230: “... will be central ...”\nLine 258: “... the trembling linear program from Proposition 1 ...”\nDef 4. We say that (\\pi_m, pi_h) is a one-sided quasi-perfect equilibrium if it is the limit point of one-sided \\eps-quasi-perfect strategy profiles.\nLemma 1. … any solution to (3) is a one-sided \\eps-quasi-perfect strategy profile.\n\nOverall, I am convinced the manuscript represents a quality work that deserves publication. \n\n### After rebuttal\n\nI would like to thank the authors for answering all my questions. My impression of the paper remains unchanged, I believe it is a good work.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Could you mention some more concrete arguments why QPE is considered superior to EFPE besides computability?", "review_text": "", "extra_scores": {"ethical_concerns": "I do not have any ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "25"}, "extra_text": {}}, {"review_id": "BW79EhHM2YH", "reviewer": "Reviewer_S3wD", "summary": "The paper introduces a novel refinement of Nash equilibrium for the case where one player is rational and the other may make mistakes. It is a one-sided variant of quasi-perfect equilibrium (QPE). Basic properties, such as existence and correctness of its definition are proven.  The paper further argues that this refinement is simpler to compute than the full QPE and shows how the recent advances in solving trembling LPs can be used to find the solution. In the experimental evaluation, the paper shows that the one-sided QPE can be computed faster than full QPE on a variety of games and that it provides a better value against a suboptimal opponent, in comparison to an arbitrary NE.", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Originality: The concept of one-sided equilibrium refinements is novel. However, there has been quite some work on one-sided solution concepts in general, where only one of the players is assumed to be irrational, which is not mentioned. Also, the solution technique is a quite straightforward simplification of the solution technique for the full QPE.\n\nClarity: The paper is very well written, with intuitive examples and clear language. It was a pleasure to read. \n\nQuality: The technical claims in the paper are sound and clear. However, some of the more general terms are overstated. I have two main concerns:\n\n(1) Suitability against humans. I completely agree with the paper in that it is important to study solution concepts where one of the players is rational and the other is not and in particular, if she is a human. However, the paper fails to argue why an equilibrium refinement is desirable in this context and why just not to model the opponent’s irrationality based on quantal response, prospect theory, or a similar model of human decision making. I am not aware of any behavioral economics literature that would suggest that humans play equilibrium refinements. A much more careful positioning w.r.t. computational game theory works taking this approach should be provided (e.g., [A] and the many follow-ups). \n\n(2) Undominated equilibria.  The paper completely ignores the NE refinement of undominated equilibrium, which is much easier to compute than one-sided QPE, has been shown to perform at least as well against imperfect opponents [B], and has been applied in realistic poker endgames [C]. This equilibrium also assumes that one of the players is rational and should have been used as a baseline in the experiments.\n\nSignificance: I think the significance of the paper is limited. If I could use LP solving techniques against a human opponent, I would probably not use a NE refinement. If I really wanted to do it, even after reading this paper, I would use the undominated equilibrium. Hence the only remaining significance could be in the theory. Since the computational techniques are quite straightforward generalizations of previous techniques for computing QPE, it is not likely to bring much new reusable knowledge. There is definitely some value in the definition, existence and connection to trembling LPs, but that is in my opinion not enough for a NeurIPS publication.\n\nReferences:\n\n[A] Yang, Rong, Kiekintveld, C., Ordonez, F., Tambe, M., & John, R.  \"Improving resource allocation strategy against human adversaries in security games.\" Twenty-Second International Joint Conference on Artificial Intelligence. 2011.\n[B] Čermák, Jiří, Branislav Bošanský, and Viliam Lisý. \"Practical performance of refinements of nash equilibria in extensive-form zero-sum games.\" ECAI 2014. IOS Press, 2014. 201-206.\n[C] Ganzfried, Sam, and Tuomas Sandholm. \"Improving performance in imperfect-information games with large state and action spaces by solving endgames.\" Workshops at the twenty-seventh AAAI conference on artificial intelligence. 2013.\n\nDetailed comments:\n\nline 139: the definition is not clear about what happens if more actions have probability over \\epsilon\n\nline 146: the notion of “optimality” used here is most likely not defined\n\nline 376: Why is it meaningful to normalize by the game value? It can be shifted arbitrarily without strategically changing the game and it can be 0, which is not even defined.\n\n\nAfter the discussion with the authors, I believe that the authors will make a substantial effort to try to mitigate the concerns above. However, since there is no other round of reviews, I would still lean towards not accepting the paper at the moment, with a strong encouragement to resubmit a modified version. On the other hand, I will not further argue against accepting it either and I have reflected it in my score.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors nicely addressed some limitations, such as the inability to address non-credible threats, but missed some even more important limitations discussed in the review.  For the societal impact, the goal of the paper is to create strategies that are more effective against humans in zero-sum games, so there might have been some discussion on whether it is a good idea. However, I personally did not miss it there. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper presents a refinement of Nash equilibrium for cases where one player is rational and the other is not. Some nice properties have been presented about the one-sided quasi-perfect equilibrium (QPE). The paper is well-written with very valuable insights. Most concerns raised in the reviews have been addressed by the authors. The contents are solid enough to justify for a publication, although the significance of the work highly relies on whether we can find practical scenarios of one-sided QPE. 
Decision: Accept (Poster)