Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: 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.

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.

I 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?

The 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?

Lastly, 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?

It seems intuitive that every (Miltersen-Sorensen) QPE should also be a one-sided QPE. Is that correct?

A few possible typos:
Line 230: “... will be central ...”
Line 258: “... the trembling linear program from Proposition 1 ...”
Def 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.
Lemma 1. … any solution to (3) is a one-sided \eps-quasi-perfect strategy profile.

Overall, I am convinced the manuscript represents a quality work that deserves publication. 

### After rebuttal

I 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.

limitations_and_societal_impact: Could you mention some more concrete arguments why QPE is considered superior to EFPE besides computability?
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: 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.
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.

Clarity: The paper is very well written, with intuitive examples and clear language. It was a pleasure to read. 

Quality: The technical claims in the paper are sound and clear. However, some of the more general terms are overstated. I have two main concerns:

(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). 

(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.

Significance: 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.

References:

[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.
[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.
[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.

Detailed comments:

line 139: the definition is not clear about what happens if more actions have probability over \epsilon

line 146: the notion of “optimality” used here is most likely not defined

line 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.


After 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.

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_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: 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.

This 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).

main_review: Overall, I'm very enthusiastic about this paper.

The 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.

The 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.

* 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.

* 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?
limitations_and_societal_impact: The authors address the technical limitations of their work quite carefully.

Regarding 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_title: null

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)