The Babylonian Talmud
is the compilation of ancient law and tradition set down during the first five
centuries A.D. which serves as the basis of Jewish religious, criminal and
civil law. One problem discussed in the Talmud is the socalled marriage
contract problem: a man has three wives whose marriage contracts specify that
in the case of this death they receive 100, 200 and 300 respectively. The
Talmud gives apparently contradictory recommendations. Where the man dies
leaving an estate of only 100, the Talmud recommends equal division. However,
if the estate is worth 300 it recommends proportional division (50,100,150),
while for an estate of 200, its recommendation of (50,75,75) is a complete
mystery. This particular Mishna has baffled Talmudic scholars for two
millennia. In 1985, it was recognised that the Talmud anticipates the modern
theory of cooperative games. Each solution corresponds to the nucleolus of an
appropriately defined game.
In a letter dated 13 November 1713
James Waldegrave provided the first, known, minimax mixed strategy solution to
a two-person game. Waldegrave wrote the letter, about a two-person version of
the card game le Her, to Pierre-Remond de Montmort who in turn wrote to
Nicolas Bernoulli, including in his letter a discussion of the Waldegrave
solution. Waldegrave's solution is a minimax mixed strategy equilibrium, but
he made no extension of his result to other games, and expressed concern that
a mixed strategy "does not seem to be in the usual rules of play" of games of
Publication of Francis Ysidro Edgeworth's Mathematical
Psychics: An Essay on the Application of Mathematics to the Moral
Sciences.Edgeworth proposed the contract curve as a solution to the
problem of determining the outcome of trading between individuals. In a world
of two commodities and two types of consumers he demonstrated that the
contract curve shrinks to the set of competitive equilibria as the number of
consumers of each type becomes infinite. The concept of the core is a
generalisation of Edgeworth's contract curve.
Emile Borel published four
notes on strategic games and an erratum to one of them. Borel gave the
first modern formulation of a mixed strategy along with finding the minimax
solution for two-person games with three or five possible strategies.
Initially he maintained that games with more possible strategies would not
have minimax solutions, but by 1927, he considered this an open question as he
had been unable to find a counterexample.
John von Neumann proved the minimax theorem in his article Zur
Theorie der Gesellschaftsspiele. It states that every two- person zero-sum
game with finitely many pure strategies for each player is determined, ie:
when mixed strategies are admitted, this variety of game has precisely one
individually rational payoff vector. The proof makes involved use of some
topology and of functional calculus. This paper also introduced the extensive
form of a game.
gives the first elementary, but still partially topological, proof of the
minimax theorem. Von Neumann and Morgenstern's (1944) proof of the theorem is
a revised, and more elementary, version of Ville's proof.
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.
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.
Two-Person Dilemma, (memo, Stanford University). Howard Raiffa
independently conducted, unpublished, experiments with the Prisoner's Dilemma.
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.
The Ford Foundation and the University of Michigan sponsor a seminar on
Experiments in Decision Processes" in Santa Monica.This was the first
experimental economics/ experimental game theory conference.
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.
Lloyd Shapley in his paper A Value
for N-PersonGames 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.
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, ie: the strategies are stationary.
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.
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
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.
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.
In their paper College
Admissions and the Stability of Marriage, D. Gale and L. Shapley asked
whether it is possible to match m women with m men so that there is no pair
consisting of a woman and a man who prefer each other to the partners with
whom they are currently matched. Game theoretically the question is, does the
appropriately defined NTU coalitional game have a non-empty core? Gale and
Shapley proved not only non-emptiness but also provided an algorithm for
finding a point in it.
An early use of game theory in insurance is Karl Borch's paper Application
of Game Theory to Some Problems in Automobile Insurance. The article
indicates how game theory can be applied to determine premiums for different
classes of insurance, when required total premium for all classes is given.
Borch suggests that the Shapley value will give reasonable premiums for all
classes of risk.
O. N. Bondareva established that for a TU game its core is non-empty iff
it is balanced. The reference, which is in Russian, translates as Some
Applications of Linear Programming Methods to the Theory of Cooperative Games.
In their paper A Limit
Theorem on the Core of an Economy G. Debreu and H. Scarf generalised
Edgeworth, in the context of a NTU game, by allowing an arbitrary number of
commodities and an arbitrary but finite number of types of traders.
The idea of the Bargaining Set was introduced and discussed in the paper
by R. J.Aumann and M. Maschler, The
Bargaining Set for Cooperative Games. The bargaining set includes the core
but unlike it, is never empty for TU games.
Carlton E. Lemke and J.T. Howson, Jr., describe an algorithm for finding a
Nash equilibrium in a bimatrix game, thereby giving a constructive proof of
the existence of an equilibrium point, in their paper Equilibrium
Points in Bimatrix Games. The paper also shows that, except for degenerate
situations, the number of equilibria in a bimatrix game is odd.
In his paper A General
Theory of Rational Behavior in GameSituations John Harsanyi gave the, now,
most commonly used definition to distinguish between cooperative and
non-cooperative games. A game is cooperative if commitments--agreements,
promises, threats--are fully binding and enforceable. It is non-cooperative if
commitments are not enforceable.
David Schmeidler introduced the Nucleolus in this paper The
Nucleolus of a Characteristic Game. The Nucleolus always exists, is
unique, is a member of the Kernel and for any non- empty core is always in it.
For a coalitional game to be a market game it is necessary that it and all
its subgames have non-empty cores, ie: that the game be totally balanced. In
Games L. S. Shapley and Martin Shubik prove that this necessary condition
is also sufficient.
The concept of an Evolutionarily Stable Strategy (ESS), was introduced to
evolutionary game theory by John Maynard Smith in an essay Game
Theory and The Evolution of Fighting. The ESS concept has since found
increasing use within the economics (and biology!) literature.
In the traditional view of strategy randomization, the players use a
randomising device to decide on their actions. John Harsanyi was the first to
break away from this view with his paper Games
with Randomly Disturbed Payoffs: A New Rationale for Mixed Strategy
Equilibrium Points. For Harsanyi nobody really randomises. The appearance
of randomisation is due to the payoffs not being exactly known to all; each
player, who knows his own payoff exactly, has a unique optimal action against
his estimate of what the others will do.
E. Kalai and M. Smorodinsky, in their article Other
Solutions to Nash's Bargaining Problem, replace Nash's independence of
irrelevant alternatives axiom with a monotonicity axiom. The resulting
solution is known as the Kalai-Smorodinsky solution.
In his paper Cross-Subsidization:
Pricing in Public Enterprises, G. Faulhaber shows that the set of
subsidy-free prices are those prices for which the resulting revenue (ri =
piqi for given demand levels qi) vector lies in the core of the cost
An event is common knowledge among a set of agents if all know it and all
know that they all know it and so on ad infinitum. Although the idea first
appeared in the work of the philosopher D. K.
Lewis in the late 1960s it was not until its formalisation in Robert
to Disagree that game theorists and economists came to fully appreciate
S. C. Littlechild and G. F. Thompson are among the first to apply the
nucleolus to the problem of cost allocation with their article Aircraft
Landing Fees:A Game Theory Approach. They use the nucleolus, along with
the core and Shapley value, to calculate fair and efficient landing and
take-off fees for Birmingham airport.
R. J. Aumann published a Survey of
Repeated Games.This survey firstly proposed the idea of applying the
notion of an automaton to describe a player in a repeated game. A second idea
from the survey is to study the interactive behaviour of bounded players by
studying a game with appropriately restricted set of strategies. These ideas
have given birth to a large and growing literature.
David M. Kreps and Robert Wilson extend the idea of a subgame perfect
equilibrium to subgames in the extensive form that begin at information sets
with imperfect information.They call this extended idea of equilibrium
sequential. It is detailed in their paper Sequential
A. Rubinstein considered a non-cooperative approach to bargaining in his
Perfect Equilibrium in a Bargaining Model. He considered an
alternating-offer game were offers are made sequentially until one is
accepted. There is no bound on the number of offers that can be made but there
is a cost to delay for each player.Rubinstein showed that the subgame perfect
equilibrium is unique when each player's cost of time is given by some
discount factor delta.
For a Bayesian game the question arises as to whether or not it is
possible to construct a situation for which there is no sets of types large
enough to contain all the private information that players are supposed to
have. In their paper,
Formulation of Bayesian Analysis for Games with Incomplete Information,
J.-F. Mertens and S. Zamir show that it is not possible to do so.
In their paper On the
Strategic Stability of EquilibriaElon Kohlberg and Jean-Francois Mertens
deal with the problem of he refinement of Nash equilibria in the normal form,
rather than the extensive form of a game as with the Selten and Kreps and
Wilson papers. This paper is also one of the first, published, discussions of
the idea of forward induction.
John C. Harsanyi and Reinhard Selten produced the first general theory of
selecting between equilibria in their book A General
Theory of Equilibrium Selection in Games. They provide criteria for
selecting one particular equilibrium point for any non-cooperative or
One interpretation of the Nash equilibrium is to think of it as an
accepted (learned) 'standard of behaviour' which governs the interaction of
various agents in repetitions of similar situations. The problem then arises
of how agents learn the equilibrium. One of the earliest works to attack the
learning problem was Drew Fudenberg and David Kreps's A Theory of Learning,
Experimentation and Equilibria, (MIT and Stanford Graduate School of Business,
unpublished), which uses an learning process similar to Brown's fictitious
play, except that players occasionally experiment by choosing strategies at
random, in the context of iterated extensive form games. Evolutionary game
models are also commonly utilised within the learning literature.
In the article Equilibrium
without Independence Vincent Crawford discusses mixed strategy Nash
equilibrium when the players preferences do not satisfy the assumptions
necessary to be represented by expected utility functions.
On Waldegrave see Kuhn, H. W.(1968), Preface to Waldegrave's Comments:
Excerpt from Montmort's Letter to Nicholas Bernoulli, pp. 3-6 in Precursors in
Mathematical Economics: An Anthology (Series of Reprints of Scarce Works on
Political Economy, 19) (W. J. Baumol and S. M. Goldfeld,eds.), London: London
School of Economics and Political Science and Waldegrave's Comments: Excerpt
from Montmort's Letter to Nicholas Bernoulli, pp. 7-9 in Precursors in
Mathematical Economics: An Anthology (Series of Reprints of Scarce Works on
Political Economy, 19) (W. J. Baumol and S. M. Goldfeld, eds.), London: London
School of Economics and Political Science, 1968.
Cournot, Augustin A. (1838),Recherches sur les Principes
Mathematiquesde la Theorie des Richesses. Paris: Hachette. (English
translation: Researches into the Mathematical Principles of the Theory of
Wealth. New York: Macmillan, 1897. (Reprinted New York: Augustus M. Kelley,
Zermelo, E. (1913), Uber eine Anwendung der Mengenlehre auf die Theorie
des Schachspiels, pp. 501-504 in Proceedings of the Fifth International
Congress of Mathematicians, Volume II (E. W. Hobson and A. E. H. Love, eds.),
Cambridge: Cambridge University Press.
This follows Dimand, Robert W. and Mary Ann Dimand (1992), The Early
History of the Theory of Games from Waldegrave to Borel, pp. 15-27 in Toward a
History of Game Theory (Annual Supplement to Volume 24 History of Political
Economy) (E. Roy Weintraub, ed.), Durham: Duke University Press. Frechet,
Maurice (1953), Emile Borel, Initiator of the Theory of Psychological games
and its Application, Econometrica 21, 95-96, credits Borel with seven notes on
game theory between 1921 and 1927. The Frechet seven are: (1) La theorie du
jeu et les equations integrales a noyan symetrique gauche, Comptes Rendus
Academie des Sciences, Vol. 173, 1921, pp. 1304-1308. (2) Sur les jeux ou
interviennent l'hasard et l'habilete des joueurs, Association Francaise pour
l'Advancement des Sciences,1923, pp. 79-85. (3) Sur les jeux ou interviennent
l'hasard et l'habilete des joueurs, Theorie des Probabilites. Paris: Librairie
Scientifique, J. Hermann, (1924), pp. 204-224. (4) Un theoreme sur les
systemes de formes lineaires a determinant symetrique gauche, Comptes Rendus
Academie des Sciences, Vol. 183, 1926, pp. 925-927, avec erratum, p. 996 .
(5)Algebre et calcul des probabilites, Comptes Rendus Academie des Sciences,
Vol. 184, 1927,pp. 52-53. (6) Traite du calcul des probabilites et de ses
applications, Applications des jeux de hasard. Paris: Gauthier-Villars, Vol.
IV, 1938, Fascicule 2, 122 pp. (7) Jeux ou la psychologie joue un role
fondamental, see (6) pp. 71-87. Dimand and Dimand note that (6) and (7) are
dated 1938 and so are outside the 1921-1927 time frame while article (2) has
the same title as the chapter from the book (3). Three of Borel's notes were
translated and published in Econometrica 21(1953). (1) was published as Theory
of Play and Integral Equations with Skew Symmetric Kernels, pp. 91-100. (3)
was published as On Games that involve Chance and the Skill of the Players,
pp. 101-115. (5) was published as On Systems of Linear Forms of Skew Symmetric
Determinant and the General Theory of Play, pp.116-117.
von Neumann, J. (1928), Zur Theorie der Gesellschaftsspiele, Mathematische
Annalen100, 295-320. (Translated as "On the Theory of Games of Strategy",
pp.13-42 in Contributions to the Theory of Games, Volume IV (Annals of
Mathematics Studies, 40) (A.W. Tucker and R. D. Luce, eds.), Princeton
University Press, Princeton, 1959).
Zeuthen, F. (1930), Problems of Monopoly and Economic Warfare. London:
George Routledge and Sons. The mathematical equivalence of Zeuthen's and
Nash's solutions was shown by Harsanyi, J. C. (1956), Approaches to the
Bargaining Problem Before and After the Theory of Games: A Critical Discussion
of Zeuthen's, Hicks' and Nash's Theories, Econometrica 24, 144-157.
Ville, Jean (1938), Note sur la theorie generale des jeux ou intervient
l'habilite desjouers, pp. 105-113 in Applications aux jeux de hasard, Tome IV,
Fascicule II of Traite du calcul des probabilities et de ses applications
(Emile Borel), Paris: Gauthier-Villars.
Gillies published version of the core concept appears in his paper,
Gillies, D. B. (1959), Solutions to General Non-Zero-Sum Games, pp. 47-85 in
Contributions to the Theory of Games, Volume IV (Annals of Mathematics
Studies, 40) (A. W. Tucker and R. D. Luce, eds.), Princeton:Princeton
Shapley, L. S. (1953), A Value for n-Person Games, pp. 307-317 in
Contributions to the Theory of Games, Volume II (Annals of Mathematics
Studies, 28) (H. W. Kuhn and A. W.Tucker, eds.), Princeton: Princeton
Kuhn, H. W. (1953), Extensive Games and the Problem of Information, pp.
193-216 in Contributions to the Theory of Games, Volume II (Annals of
Mathematics Studies, 28) (H.W. Kuhn and A. W. Tucker, eds.), Princeton:
Princeton University Press.
Aumann, R. J. (1959), Acceptable Points in General Cooperative N-Person
Games, pp.287-324 in Contributions to the Theory of Games, Volume IV (Annals
of Mathematics Studies, 40) (A. W. Tucker and R. D. Luce, eds.), Princeton:
Princeton University Press.
Shubik, M. (1959), Edgeworth Market Games, pp. 267-278 in Contributions to
the Theory of Games, Volume IV (Annals of Mathematics Studies, 40) (A. W.
Tucker and R. D.Luce, eds.), Princeton: Princeton University Press.
Aumann, R. J. and M. Maschler (1964), The Bargaining Set for Cooperative
Games, pp.443-476 in Advances in Game Theory (Annals of Mathematics Studies,
52) (M. Dresher, L. S. Shapley and A. W. Tucker, eds.), Princeton: Princeton
Shapley, L. S. (1969), Utility Comparison and the Theory of Games, pp.
251-263 in La Decision, Paris: Editions du Centre National de la Recherche
Scientifique. (Reprinted on pp.307-319 of The Shapley Value (Alvin E. Roth,
ed.), Cambridge: Cambridge University Press,1988).
Kohlberg, Elon (1981), Some Problems with the Concept of Perfect
Equilibria, Rapporteurs' Report of the NBER Conference on the Theory of
General Economic Equilibrium by Karl Dunz and Nirvikar Sing, University of
Aumann, R. J. (1981), Survey of Repeated Games, pp.11-42 in Essays in Game
Theory and Mathematical Economics in Honor of Oskar Morgenstern (R. J. Aumann
et al), Zurich: Bibliographisches Institut. (This paper is a slightly revised
and updated version of a paper originally presented as background material for
a one-day workshop on repeated games that took place at the Institute for
Mathematical Studies in the Social Sciences (Stanford University) summer
seminar on mathematical economics on 10 August 1978.) (A slightly revised and
updated version of the 1981 version is reprinted as Repeated Games on
pp.209-242 of Issues in Contemporary Microeconomics and Welfare (George R
Feiwel, ed.), London: Macmillan.)