Game Development Reference
In-Depth Information
8
Beyond Nash Equilibrium: Solution Concepts for
the 21st Century
Joseph Y. Halpern
Cornell University, Ithaca, NY
Abstract
Nash equilibrium is the most commonly-used notion of equilibrium in game
theory. However, it suffers from numerous problems. Some are well known
in the game theory community; for example, the Nash equilibrium of the
repeated prisoner's dilemma is neither normatively nor descriptively reason-
able. However, new problems arise when considering Nash equilibrium from
a computer science perspective: for example, Nash equilibrium is not robust
(it does not tolerate 'faulty' or 'unexpected' behaviour), it does not deal
with coalitions, it does not take computation cost into account, and it does
not deal with cases where players are not aware of all aspects of the game.
Solution concepts that try to address these shortcomings of Nash equilibrium
are discussed.
8.1 Introduction
Nash equilibrium is the most commonly-used notion of equilibrium in game
theory. Intuitively, a Nash equilibrium is a strategy profile (a collection of
strategies, one for each player in the game) such that no player can do better
by deviating. The intuition behind Nash equilibrium is that it represents a
possible steady state of play. It is a fixed-point where each player holds correct
beliefs about what other players are doing, and plays a best response to those
beliefs. Part of what makes Nash equilibrium so attractive is that in games
where each player has only finitely many possible deterministic strategies,
and we allow mixed (i.e., randomised) strategies, there is guaranteed to be a
Nash equilibrium [Nash, 1950a] (this was, in fact, the key result of Nash's
thesis).
c
ACM, 2010. This is a minor revision of the work published in Proceedings of the twenty-seventh
ACM symposium on Principles of Distributed Computing (PODC '08). ACM, New York, NY,
USA, 1-10. http://doi.acm.org/10.1145/1400751.1400752 . Republished here by permission of
Search Nedrilad ::




Custom Search