Practical exact algorithm for trembling-hand equilibrium refinements in games
Nash equilibrium strategies have the known weakness that they do not prescribe rational play in situations that are reached with zero probability according to the strategies themselves, for example, if players have made mistakes. Tremblinghand refinements-such as extensive-form perfect equilibria and quasi-perfect equilibria-remedy this problem in sound ways. Despite their appeal, they have not received attention in practice since no known algorithm for computing them scales beyond toy instances. In this paper, we design an exact polynomial-time algorithm for finding trembling-hand equilibria in zero-sum extensive-form games. It is several orders of magnitude faster than the best prior ones, numerically stable, and quickly solves game instances with tens of thousands of nodes in the game tree. It enables, for the first time, the use of trembling-hand refinements in practice.
*** POST-REBUTTAL *** Despite the missing appendices, I had tried to work out the authors' proofs based on the sketches they provided in the main paper: whatever questions I had, they addressed in the rebuttal (I upgraded my assessment from 6 to 7 to indicate just this). As far as I can tell, the authors' analysis is sound and I believe the paper clears the bar for acceptance.   *** PRE-REBUTTAL  *** In this paper, the authors propose a novel algorithm for calculating trembling-hand equilibria in two-player zero-sum games in extensive form. In a nutshell, the authors reformulate the zero-sum game at hand as a linear program (a standard trick), and they then describe an oracle mechanism for deciding whether a basis of the resulting linear program is stable or not. When such a basis is computed, the algorithm lets the magnitude of the trembles go to zero and ultimately outputs a trembling hand equilibrium.  I found the paper to be overall well-written, clearly structured, and the analysis morally sound (at least, to the best of my understanding). At the same time however, there are some important points where I found the authors' presentation unsatisfactory. In particular, I have the following concerns:  - A good amount of the authors' analysis relies on the optimality certificate  t_B of a given basis being an analytic function of epsilon (the perturbation magnitude). From what I could gather, the polynomial (in epsilon) nature of the LP has to do with the fact that the underlying game is finite (though the specifics of how epsilon enters the various expressions are not particularly well-explained either). However, given that the expression for t_B involves the inverse of B (which is a rational function of its components), it is not clear why the resulting function does not have a pole at 0 (or below the perturbation threshold predicted by Theorem 7 for that matter). This is further compounded by the last sentence of Section 5 which states that "this task is easy after having computed the Laurent [as opposed to Taylor] series of x(epsilon)", which also seems to suggest that t_B is meromorphic - not holomorphic. This is a central point in the authors' reasoning so I would expect a more rigorous and more detailed treatment.  - Regarding the algorithm's runtime: the authors claim that it is polynomial, but there's a couple of points that are not clear to me:     1. The lowest non-zero term in the Taylor expansion of t_B might have an exponentially high degree: in that case, the algorithm would need to go through exponentially many derivatives before getting to the order of the expansion. [To be clear: I am not claiming that this is the case, I am just saying that this cannot be a priori excluded.] The authors need to show that this cannot happen, otherwise I fail to see why the algorithm would terminate in polynomial time.     2. The number of bases that need to be checked might also be super-polynomial: why is this not the case?  All in all, statements like the one in L244 ("the optimality certificate is extremely easy to deal with") seem too cavalier to me, especially when considering subtle complexity issues as the authors are doing.  - The argument in p.2 that "no NE refinement was used [in Libratus] to capitalize on the opponent's mistakes" is vague at best, misleading at worst. Even though I appreciate the algorithmic importance of calculating NE refinements (trembling hand/sub-game perfect, QRE or otherwise), this statement is neither correct nor sufficient to single out the relevance of trembling hand equilibria. The cited book of van Damme (1984) contains many other refinements that coud "capitalize on mistakes" (basically, any Nash equilibrium that is not supported on weakly dominated strategies would do a fine job at exploiting mistakes).  All in all, I'm on the fence about this submission: I did like it, but some points could be better explained and I also feel a better venue for it would be a conference like EC, SODA or FOCS.