NeurIPS 2020

Small Nash Equilibrium Certificates in Very Large Games

Meta Review

The paper proposes novel concepts, epsilon-certificates and pseudo-games, for finding bounds on utilities of (approximate) Nash equilibria in game. Overall, the reviewers agree that this is a interesting novel contribution. The paper shows positive and negative results, but more negative than positive. This was a major point of discussion, but in the end, all the reviewers agreed that knowing these negative results is of important value to the community. Another question that arose was on the value of small certificates. This was largely cleared up by the author response and the discussion that followed. However, I encourage the authors to revise the paper based on these initial reactions, i.e. possibly move some arguments from the author response to the paper itself to clarify these points. There remain several issues pointed out by the reviewers that authors should address in their final version. Consider adding a citation to existing literature on bounding support sizes as pointed out by Reviewer #3. Also, the point of redundant theory made by Reviewer #4 is important and could affect the long-term impact.