I realized there had to be a better way
You may recall the origin of the holiday Festivus in Seinfeld, as described by Frank Costanza:
FRANK: Many Christmases ago, I went to buy a doll for my son. I reach for the last one they had — but so did another man. As I rained blows opon him, I realized there had to be another way!
KRAMER: What happened to the doll?
FRANK: It was destroyed. But out of that, a new holiday was born. “A Festivus for the rest of us!”
So recently I submitted the paper Fast Complete Algorithm for Multiplayer Nash Equilibrium to the Conference on Economics and Computation. The paper describes a new algorithm I came up with, based on a non-convex quadradic program formulation, for computing Nash equilibrium in multiplayer games. Nash equilibrium is the central solution concept in game theory, and computing one in games with more than two players is a very challenging computational problem. The algorithm is guaranteed to always find a solution, and experimentally outperforms the best prior approaches on a variety of game sizes and realistic domains. Exciting breakthrough stuff!
Here are some excerpts from the rejection email I received:
“The most obvious benchmark is missing from the experimental results: comparing this formulation to the original MILP formulation of Sandholm et al. as solved by Gurobi. Without this, we don’t even know if the QCP formulation actually is better.” -Reviewer 1
Reviewer 1 is saying that we failed to run experiments against the original MILP formulation from prior work, which he says is the most obvious benchmark. That original MILP formulation is for computing Nash equilibrium in two players games, while our algorithm is for computing Nash equilibrium in games with three or more players. It doesn’t make any sense to compare the approaches because they are for solving different problems.
“From their report, when N is 3 or 4, the authors’ running times improve upon Berg and Sandholm’s running times from a factor of 5 to 1000. However, this comparison is made by quoting the running times reported by Berg and Sandholm, which was 3 years ago. The comparison is not totally fair since Gurobi is likely to improve its solvers’ speed in the past 3 years.” -Reviewer 3
Reviewer 3 is saying that our comparison against the approach of Berg and Sandholm is not fair because we quote their running times from 3 years ago and Gurobi has likely improved its solvers’ speed since then. But Berg and Sandholm’s algorithm does not even use Gurobi! It is a custom algorithm that has not changed in the last 3 years. And even if you want to argue that it has changed, the results aren’t even close. If you look at Tables 3 and 4, our algorithm takes a fraction of a second for all game classes, while Berg and Sandholm’s takes 35,000 seconds on one, 880 seconds on another, etc.
“The reviewers agree that the programming formulation is straightforward and that quoting running times from a 3-year old paper does not provide a good basis for comparison. Moreover, even if those comparisons were done correctly, the contribution would still not be interesting enough” -Metareview
OH SNAP! Not only are the comparisons not fair, but even if they were done “correctly,” then the paper would still not be “interesting enough”!!
As I blasted profanities about the reviewers, I realized there had to be a better way! Out of that rejection, a new conference was born. AIGT for you and me.
