News

An infinite beautiful mind

Theorem identifies games with infinite choices having at least one Nash equilibrium

By
12:00pm, October 10, 2008
Sponsor Message

Life’s a game, or at least treating it like a game mathematically can be a powerful way to explain the choices people make. John Nash, the mentally troubled mathematician depicted in the book and movie A Beautiful Mind, discovered one of the bedrock theories for understanding competitive interactions (generically called “games”) in which the players have a limited set of choices.

Now mathematicians are expanding Nash’s ideas for cases when the players’ options are infinite. Under certain conditions even infinite-choice games are guaranteed to have at least one scenario for which each player gets the best deal possible (given everyone else’s choices), according to a mathematical proof to be published in the February 2009 Nonlinear Analysis.

Such a scenario — or set of choices for each player — is called a Nash equilibrium and is stable because no player can do any better by changing strategy (unless he or she forms a cartel to collude with other players, which isn’t allowed). Like a rock resting at the bottom of a valley, once the game reaches this stable scenario it will tend to stay that way. In a sense, it’s the fate of the game to end up at a Nash equilibrium, and this predictive power is why Nash’s ideas have become widely used in economics and other social sciences.

Nash proved that there is always at least one such equilibrium for games with a finite number of possible strategic choices. But not all imaginable games are so limited.

“There are many economically important games in which the sets of pure strategies are infinite,” comments Andrew McLennan, a mathematician and economist who studies game theory at the University of Queensland in, St. Lucia, Australia. McLennan offers the example of an auction in which each bidder can bid any amount — mathematically, an infinite set of numbers. Of course, enormous bids would be very poor strategies in real life, but mathematical tools that model these situations need to be able to take all possible strategies into account.

A general theory that could always predict whether a game with infinite choices will have a Nash equilibrium still eludes mathematicians. In the new work, Jinlu Li, a mathematician at ShawneeStateUniversity in Portsmouth, Ohio, and his colleagues deal with a more limited, specialized case. If all the possible scenarios for a game taken together are “compact” — meaning that they are constrained in some ways even if there are infinitely many of them — the game will have at least one Nash equilibrium, the team shows.

“This paper is still far away from completely solving this problem,” Li says. The new rule doesn’t fully predict which infinite-choice games will have an equilibrium; some games that aren’t compact also will have one. “Our dream is we want to find the necessary and sufficient condition, a characteristic of the game that will always guarantee that it has an equilibrium.”

The work is also based on a simplified situation: A game with only two players in which, for one player to win, the other must lose. Nash’s theorem for finite-choice games works for much more complex games involving many players and the possibility of mutual benefit. Eventually mathematicians will have to expand Li and his colleagues’ work to include these more complicated games.

“It is part of a large and rapidly growing literature concerned with ... extensions of Nash’s theorem,” McLennan says.

More from Science News