show players how to efficiently reach an
equilibrium? After more than 65 years of
researchers’ studying that question, the
answer turns out to be no, there is not.
That means economists had better start
rethinking some of their models.
WHEN JOHN NASH won the Nobel Prize in eco- nomics in 1994 for his contribution to game theory, it was for an el-
egant theorem. Nash had shown that
in any situation where two or more
people were competing, there would
always be an equilibrium state in
which no player could do better than
he was already doing. That theorem
has since been used to model all sorts
of competitive systems, from markets
to nuclear strategy to living creatures
competing for finite resources.
“In some sense, it started not just
game theory, but also modern economics,” says Christos Papadimitriou, a
professor of computer science at Columbia University. Nash’s idea gave
economists the ability to create hypoth-eses about market design, for instance.
They could now ask what happened
when a market reached equilibrium.
Nash’s theorem is also an essential
component of game theory, which had
first been developed by computing pio-
neer John von Neumann. “Games are a
mathematical thought experiment and
we study them just because we want to
understand how strategic rational play-
ers would behave in situations of con-
flict,” Papadimitriou says. “And that’s
important because all of society is full
of such situations.”
Though Nash proved that at least one
such Nash equilibrium existed for all
games, what he did not do was predict
how an equilibrium might be reached in
a given situation. Was there, scientists
wanted to know, an algorithm that would
Always Out of Balance
Computational theorists prove there is no easy algorithm to find
Nash equilibria, so game theory will have to look in new directions.
Science | DOI: 10.1145/3185519 Neil Savage