Dating game economics
Nash proved in 1950 that even large, complicated games like this one do always have an equilibrium (at least, if the concept of a strategy is broadened to allow random choices, such as you choosing the Chinese restaurant with 60 percent probability).
But Nash — who died in a car crash in 2015 — gave no recipe for how to calculate such an equilibrium.
By diving into the nitty-gritty of Nash’s proof, Babichenko and Rubinstein were able to show that in general, there’s no guaranteed method for players to find even an approximate Nash equilibrium unless they tell each other virtually everything about their respective preferences.
And as the number of players in a game grows, the amount of time required for all this communication quickly becomes prohibitive.
For example, in the 100-player restaurant game, there are 2.
Its influence on economic theory “is comparable to that of the discovery of the DNA double helix in the biological sciences,” wrote Roger Myerson of the University of Chicago, another economics Nobelist.
After all, in each round, the players learn only a bit of new information about each other: how happy they are with the single dinner arrangement that got played.
So it will take on the order of 2 rounds before they know everything about one another’s values (by which time, presumably, the Chinese and Italian restaurants will have gone out of business).
“Economists have proposed mechanisms for how you can converge [quickly] to equilibrium,” said Aviad Rubinstein, who is finishing a doctorate in theoretical computer science at the University of California, Berkeley.
But for each such mechanism, he said, “there are simple games you can construct where it doesn’t work.” Now, Rubinstein and Yakov Babichenko, a mathematician at the Technion-Israel Institute of Technology in Haifa, have explained why.When players are at equilibrium, no one has a reason to stray.