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