Interesting article, actually.
I think game theory has the potential to be a powerful tool for any
cypherpunk to have in his or her mental arsenal, (so to speak.) For those
of you who haven't been introduced to game theory, how it works, and what
it's used for, here's a modified excerpt from an essay outlining the
basics...
Game theory can be described as the study of interactive decision making.
Although game theory is relevant to parlor games such as poker or bridge,
most research in game theory focuses on how groups of people interact.
There are two main branches of game theory: cooperative and noncooperative
game theory. Noncooperative game theory deals largely with how intelligent
individuals interact with one another in an effort to achieve their own
goals.
Decision theory can be viewed as a theory of one person games, or a game of
a single player against nature. The focus is on preferences and the
formation of beliefs. The most widely used form of decision theory argues
that preferences among risky alternatives can be described by the
maximization the expected value of a numerical utility function, where
utility may depend on a number of things, but in situations of interest to
economists often depends on money income. Probability theory is heavily
used in order to represent the uncertainty of outcomes, and Bayes Law is
frequently used to model the way in which new information is used to revise
beliefs. Decision theory is often used in the form of decision analysis,
which shows how best to acquire information before making a decision.
General equilibrium theory can be viewed as a specialized branch of game
theory that deals with trade and production, and typically with a
relatively large number of individual consumers and producers. It is widely
used in the macroeconomic analysis of broad based economic policies such as
monetary or tax policy, in finance to analyze stock markets, to study
interest and exchange rates and other prices. In recent years, political
economy has emerged as a combination of general equilibrium theory and game
theory in which the private sector of the economy is modeled by general
equilibrium theory, while voting behavior and the incentive of governments
is analyzed using game theory. Issues studied include tax policy, trade
policy, and the role of international trade agreements such as the European
Union.
Mechanism design theory differs from game theory in that game theory takes
the rules of the game as given, while mechanism design theory asks about
the consequences of different types of rules. Naturally this relies heavily
on game theory. Questions addressed by mechanism design theory include the
design of compensation and wage agreements that effectively spread risk
while maintaining incentives, and the design of auctions to maximize
revenue, or achieve other goals.
An Instructive Example
One way to describe a game is by listing the players (or individuals)
participating in the game, and for each player, listing the alternative
choices (called actions or strategies) available to that player. In the
case of a two-player game, the actions of the first player form the rows,
and the actions of the second player the columns, of a matrix. The entries
in the matrix are two numbers representing the utility or payoff to the
first and second player respectively. A very famous game is the Prisoner's
Dilemma game. In this game the two players are partners in a crime who have
been captured by the police. Each suspect is placed in a separate cell, and
offered the opportunity to confess to the crime. The game can be
represented by the following matrix of payoffs:
not confess confess
not confess 5,5 0,10
confess 10,0 1,1
Note that higher numbers are better (more utility). If neither suspect
confesses, they go free, and split the proceeds of their crime which we
represent by 5 units of utility for each suspect. However, if one prisoner
confesses and the other does not, the prisoner who confesses testifies
against the other in exchange for going free and gets the entire 10 units
of utility, while the prisoner who did not confess goes to prison and gets
nothing. If both prisoners confess, then both are given a reduced term, but
both are convicted, which we represent by giving each 1 unit of utility:
better than having the other prisoner confess, but not so good as going
free.
This game has fascinated game theorists for a variety of reasons. First, it
is a simple representation of a variety of important situations. For
example, instead of confess/not confess we could label the
strategies "contribute to the common good" or "behave selfishly." This
captures a variety of situations economists describe as public goods
problems. An example is the construction of a bridge. It is best for
everyone if the bridge is built, but best for each individual if someone
else builds the bridge. This is sometimes refered to in economics as an
externality. Similarly this game could describe the alternative of two
firms competing in the same market, and instead of confess/not confess we
could label the strategies "set a high price" and "set a low price."
Naturally is is best for both firms if they both set high prices, but best
for each individual firm to set a low price while the opposition sets a
high price.
A second feature of this game, is that it is self-evident how an
intelligent individual should behave. No matter what a suspect believes his
partner is going to do, is is always best to confess. If the partner in the
other cell is not confessing, it is possible to get 10 instead of 5. If the
partner in the other cell is confessing, it is possible to get 1 instead of
0. Yet the pursuit of individually sensible behavior results in each player
getting only 1 unit of utility, much less than the 5 units each that they
would get if neither confessed. This conflict between the pursuit of
individual goals and the common good is at the heart of many game theoretic
problems.
A third feature of this game is that it changes in a very significant way
if the game is repeated, or if the players will interact with each other
again in the future. Suppose for example that after this game is over, and
the suspects either are freed or are released from jail they will commit
another crime and the game will be played again. In this case in the first
period the suspects may reason that they should not confess because if they
do not their partner will not confess in the second game. Strictly
speaking, this conclusion is not valid, since in the second game both
suspects will confess no matter what happened in the first game. However,
repetition opens up the possibility of being rewarded or punished in the
future for current behavior, and game theorists have provided a number of
theories to explain the obvious intuition that if the game is repeated
often enough, the suspects ought to cooperate.
One of the most entertaining intro books is "The Compleat Strategist: Being
a Primer on the Theory of Games of Strategy", (J.D. Williams, McGraw-Hill,
New York 1966.) David Levine recommends "Thinking Strategically" by A.
Dixit and B. Nalebuff (Norton, 1991) as good general reading. If you're
interested in getting deeper into the subject you should try Game Theory
with Economic Applications by H. Bierman and L. Fernandez (Addison-Wesley,
1993). The next step up is the graduate level text Game Theory by D.
Fudenberg and J. Tirole from MIT Press. There are also two other advanced
textbooks worth taking a look at: "Fun and Games: A Text on Game Theory by
K. Binmore" (D.C. Heath, 1992), a very focused and mathematical treatment...
---------------------
"Golden Age" History
---------------------
1944
"Theory of Games and Economic Behavior" by John von Neumann and Oskar
Morgenstern is published. As well as expounding two-person zero sum theory
this book is the seminal work in areas of game theory such as the notion of
a cooperative game, with transferable utility (TU), its coalitional form
and its von Neumann-Morgenstern stable sets. It was also the account of
axiomatic utility theory given here that led to its wide spread adoption
within economics.
1945
Herbert Simon writes the first review of von Neumann-Morgenstern.
1946
The first entirely algebraic proof of the minimax theorem is due to L. H.
Loomis's,On a Theorem of von Neumann, paper.
1950
Contributions to the Theory of Games I, H. W. Kuhn and A. W. Tucker eds.,
published.
1950
In January 1950 Melvin Dresher and Merrill Flood carry out, at the Rand
Corporation, the experiment which introduced the game now known as the
Prisoner's Dilemma. The famous story associated with this game is due to A.
W. Tucker, A Two-Person Dilemma, (memo, Stanford University). Howard Raiffa
independently conducted, unpublished, experiments with the Prisoner's
Dilemma.
1950-53
In four papers between 1950 and 1953 John Nash made seminal contributions
to both non-cooperative game theory and to bargaining theory. In two
papers, "Equilibrium Points in N- Person Games" (1950) and "Non-cooperative
Games" (1951), Nash proved the existence of a strategic equilibrium for non-
cooperative games - the Nash equilibrium - and proposed the"Nash program",
in which he suggested approaching the study of cooperative games via their
reduction to non-cooperative form. In his two papers on bargaining theory,
The Bargaining Problem (1950) and Two-Person Cooperative Games (1953), he
founded axiomatic bargaining theory, proved the existence of the Nash
bargaining solution and provided the first execution of the Nash program.
1951
George W. Brown described and discussed a simple iterative method for
approximating solutions of discrete zero-sum games in his paper Iterative
Solutions of Games by Fictitious Play.
1952
The first textbook on game theory: John Charles C. McKinsey, "Introduction
to the Theory of Games".
1952
Merrill Flood's report, (Rand Corporation research memorandum, Some
Experimental Games, RM-789, June), on the 1950 Dresher/Flood experiments
appears.
1952
The Ford Foundation and the University of Michigan sponsor a seminar on
the"Design of Experiments in Decision Processes" in Santa Monica.This was
the first experimental economics/ experimental game theory conference.
1952-53
The notion of the Core as a general solution concept was developed by L. S.
Shapley (Rand Corporation research memorandum, Notes on the N-Person Game
III: Some Variants of the von-Neumann-Morgenstern Definition of Solution,
RM- 817, 1952) and D.B. Gillies (Some Theorems on N-Person Games, Ph.D.
thesis, Department of Mathematics, Princeton University, 1953). The core is
the set of allocations that cannot be improved upon by any coalition.
1953
Lloyd Shapley in his paper A" Value for N-Person Games" characterised, by a
set of axioms, a solution concept that associates with each coalitional
game,v, a unique out- come, v. This solution in now known as the Shapley
Value.
1953
Lloyd Shapley's paper "Stochastic Games" showed that for the strictly
competitive case, with future payoff discounted at a fixed rate, such games
are determined and that they have optimal strategies that depend only on
the game being played, not on the history or even on the date, i.e.: the
strategies are stationary.
1953
Extensive form games allow the modeller to specify the exact order in which
players have to make their decisions and to formulate the assumptions about
the information possessed by the players in all stages of the game. H. W.
Kuhn's paper, "Extensive Games and the Problem of Information" includes the
formulation of extensive form games which is currently used, and also some
basic theorems pertaining to this class of games.
1953
"Contributions to the Theory of Games II," H. W. Kuhn and A. W. Tucker
eds., published.
1954
One of the earliest applications of game theory to political science is L.
S. Shapley and M. Shubik with their paper "A Method for Evaluating the
Distribution of Power in a Committee System." They use the Shapley value to
determine the power of the members of the UN Security Council.
1954-55
Differential Games were developed by Rufus Isaacs in the early 1950s. They
grew out of the problem of forming and solving military pursuit games. The
first publications in the area were Rand Corporation research memoranda, by
Isaacs, RM-1391 (30 November 1954), RM-1399 (30 November 1954), RM-1411 (21
December 1954) and RM-1486 (25 March 1955) all entitled, in part,
Differential Games.
1955
One of the first applications of game theory to philosophy is R. B.
Braithwaite's "Theory of Games as a Tool for the Moral Philosopher."
1957
"Games and Decisions: Introduction and Critical Survey" by Robert Duncan
Luce and Howard Raiffa published.
1957
Contributions to the Theory of Games III, M. A.Dresher, A. W. Tucker and P.
Wolfe eds., published.
1959
The notion of a Strong Equilibrium was introduced by R. J. Aumann in the
paper Acceptable Points in General Cooperative N-Person Games.
1959
The relationship between Edgeworth's idea of the contract curve and the
core was pointed out by Martin Shubik in his paper Edgeworth Market Games.
One limitation with this paper is that Shubik worked within the confines of
TU games whereas Edgeworth's idea is more appropriately modelled as an NTU
game.
1959
Contributions to the Theory of Games IV, A. W.Tucker and R. D. Luce eds.,
published.
1959
Publication of Martin Shubik's "Strategy and Market Structure: Competition,
Oligopoly, and the Theory of Games". This was one of the first books to
take an explicitly non-cooperative game theoretic approach to modelling
oligopoly. It also contains an early statement of the Folk Theorem.
Late 50's
Near the end of this decade came the first studies of repeated games. The
main result to appear at this time was the Folk Theorem. This states that
the equilibrium outcomes in an infinitely repeated game coincide with the
feasible and strongly individually rational outcomes of the one-shot game
on which it is based. Authorship of the theorem is obscure.
