game theory

What is game theory?
Game theory is the formal study of conflict and cooperation. Game theoretic concepts
apply whenever the actions of several agents are interdependent. These agents may be
individuals, groups, firms, or any combination of these. The concepts of game theory
provide a language to formulate, structure, analyze, and understand strategic scenarios
History and impact of game theory
The earliest example of a formal game-theoretic analysis is the study of a duopoly by
Antoine Cournot in 1838. The mathematician Emile Borel suggested a formal theory of
games in 1921, which was furthered by the mathematician John von Neumann in 1928
in a “theory of parlor games.” Game theory was established as a field in its own right
after the 1944 publication of the monumental volume Theory of Games and Economic
Behavior by von Neumann and the economist Oskar Morgenstern. This book provided
much of the basic terminology and problem setup that is still in use today.
In 1950, John Nash demonstrated that finite games have always have an equilibrium
point, at which all players choose actions which are best for them given their opponents’
choices. This central concept of noncooperative game theory has been a focal point of
analysis since then. In the 1950s and 1960s, game theory was broadened theoretically
and applied to problems of war and politics. Since the 1970s, it has driven a revolution
4
in economic theory. Additionally, it has found applications in sociology and psychology,
and established links with evolution and biology. Game theory received special attention
in 1994 with the awarding of the Nobel prize in economics to Nash, John Harsanyi, and
Reinhard Selten.
At the end of the 1990s, a high-profile application of game theory has been the design
of auctions. Prominent game theorists have been involved in the design of auctions for allocating
rights to the use of bands of the electromagnetic spectrum to the mobile telecommunications
industry. Most of these auctions were designed with the goal of allocating
these resources more efficiently than traditional governmental practices, and additionally
raised billions of dollars in the United States and Europe.
Zero-sum games and computation
The extreme case of players with fully opposed interests is embodied in the class of twoplayer
zero-sum (or constant-sum) games. Familiar examples range from rock-paperscissors
to many parlor games like chess, go, or checkers.
A classic case of a zero-sum game, which was considered in the early days of game
theory by von Neumann, is the game of poker. The extensive game in Figure 10, and
its strategic form in Figure 11, can be interpreted in terms of poker, where player I is
dealt a strong or weak hand which is unknown to player II. It is a constant-sum game
since for any outcome, the two payoffs add up to 16, so that one player’s gain is the other
player’s loss. When player I chooses to announce despite being in a weak position, he
is colloquially said to be “bluffing.” This bluff not only induces player II to possibly sell
out, but similarly allows for the possibility that player II stays in when player I is strong,
increasing the gain to player I.
Mixed strategies are a natural device for constant-sum games with imperfect information.
Leaving one’s own actions open reduces one’s vulnerability against malicious
responses. In the poker game of Figure 10, it is too costly to bluff all the time, and better
to randomize instead. The use of active randomization will be familiar to anyone who has
played rock-paper-scissors.
Zero-sum games can be used to model strategically the computer science concept of
“demonic” nondeterminism. Demonic nondeterminism is based on the assumption that,
when an ordering of events is not specified, one must assume that the worst possible sequence
will take place. This can be placed into the framework of zero-sum game theory
by treating nature (or the environment) as an antagonistic opponent. Optimal randomization
by such an opponent describes a worst-case scenario that can serve as a benchmark.
33
A similar use of randomization is known in the theory of algorithms as Rao’s theorem,
and describes the power of randomized algorithms. An example is the well-known quicksort
algorithm, which has one of the best observed running times of sorting algorithms in
practice, but can have bad worst cases. With randomization, these can be made extremely
unlikely.
Randomized algorithms and zero-sum games are used for analyzing problems in online
computation. This is, despite its name, not related to the internet, but describes the
situation where an algorithm receives its input one data item at a time, and has to make
decisions, for example in scheduling, without being able to wait until the entirety of the
input is known. The analysis of online algorithms has revealed insights into hard optimization
problems, and seems also relevant to the massive data processing that is to be
expected in the future. At present, it constitutes an active research area, although mostly
confined to theoretical computer science (see Borodin and El-Yaniv, Online Computation
and Competitive Analysis, Cambridge University Press, 1998).
Mixed strategies
A game in strategic form does not always have a Nash equilibrium in which each player
deterministically chooses one of his strategies. However, players may instead randomly
select from among these pure strategies with certain probabilities. Randomizing one’s
own choice in this way is called a mixed strategy. Nash showed in 1951 that any finite
strategic-form game has an equilibrium if mixed strategies are allowed. As before, an
equilibrium is defined by a (possibly mixed) strategy for each player where no player
can gain on average by unilateral deviation. Average (that is, expected) payoffs must be
considered because the outcome of the game may be random.