Contents 1 History 1.1 Prize-winning achievements 2 Game types 2.1
3 Representation of games 3.1 Extensive form 3.2 Normal form 3.3 Characteristic function form 4 General and applied uses 4.1 Description and modeling
4.2 Prescriptive or normative analysis
4.3
5 In popular culture 6 See also 7 Notes 8 References and further reading 8.1 Textbooks and general references 8.2 Historically important texts 8.3 Other print references 9 External links History[edit] John von Neumann John Nash Early discussions of examples of two-person games occurred long before
the rise of modern, mathematical game theory. The first known
discussion of game theory occurred in a letter written by Charles
Waldegrave, an active Jacobite, and uncle to James Waldegrave, a
British diplomat, in 1713.[2] In this letter, Waldegrave provides a
minimax mixed strategy solution to a two-person version of the card
game le Her, and the problem is now known as Waldegrave problem. James
Madison made what we now recognize as a game-theoretic analysis of the
ways states can be expected to behave under different systems of
taxation.[3][4] In his 1838 Recherches sur les principes
mathématiques de la théorie des richesses (Researches into the
Mathematical Principles of the Theory of Wealth), Antoine Augustin
Cournot considered a duopoly and presents a solution that is a
restricted version of the Nash equilibrium.
In 1913,
E F E 1, 2 0, 0 F 0, 0 1, 2 An asymmetric game Main article: Symmetric game A symmetric game is a game where the payoffs for playing a particular strategy depend only on the other strategies employed, not on who is playing them. If the identities of the players can be changed without changing the payoff to the strategies, then a game is symmetric. Many of the commonly studied 2×2 games are symmetric. The standard representations of chicken, the prisoner's dilemma, and the stag hunt are all symmetric games. Some[who?] scholars would consider certain asymmetric games as examples of these games as well. However, the most common payoffs for each of these games are symmetric. Most commonly studied asymmetric games are games where there are not identical strategy sets for both players. For instance, the ultimatum game and similarly the dictator game have different strategies for each player. It is possible, however, for a game to have identical strategies for both players, yet be asymmetric. For example, the game pictured to the right is asymmetric despite having identical strategy sets for both players. Zero-sum / Non-zero-sum[edit] A B A –1, 1 3, –3 B 0, 0 –2, 2 A zero-sum game Main article: Zero-sum game
Zero-sum games are a special case of constant-sum games, in which
choices by players can neither increase nor decrease the available
resources. In zero-sum games the total benefit to all players in the
game, for every combination of strategies, always adds to zero (more
informally, a player benefits only at the equal expense of
others).[12]
Sequential Simultaneous Normally denoted by Decision trees Payoff matrices Prior knowledge of opponent's move? Yes No Time axis? Yes No Also known as Extensive-form game Extensive game Strategy game Strategic game
A game of imperfect information (the dotted line represents ignorance on the part of player 2, formally called an information set) An important subset of sequential games consists of games of perfect
information. A game is one of perfect information if all players know
the moves previously made by all other players. Most games studied in
game theory are imperfect-information games.[citation needed] Examples
of perfect-information games include tic-tac-toe, checkers, infinite
chess, and Go.[13][14][15][16]
Many card games are games of imperfect information, such as poker and
bridge.[17]
An extensive form game The extensive form can be used to formalize games with a time sequencing of moves. Games here are played on trees (as pictured here). Here each vertex (or node) represents a point of choice for a player. The player is specified by a number listed by the vertex. The lines out of the vertex represent a possible action for that player. The payoffs are specified at the bottom of the tree. The extensive form can be viewed as a multi-player generalization of a decision tree.[32] To solve any extensive form game, backward induction must be used. It involves working backwards up the game tree to determine what a rational player would do at the last vertex of the tree, what the player with the previous move would do given that the player with the last move is rational, and so on until the first vertex of the tree is reached.[33] The game pictured consists of two players. The way this particular game is structured (i.e., with sequential decision making and perfect information), Player 1 "moves" first by choosing either F or U (Fair or Unfair). Next in the sequence, Player 2, who has now seen Player 1's move, chooses to play either A or R. Once Player 2 has made his/ her choice, the game is considered finished and each player gets their respective payoff. Suppose that Player 1 chooses U and then Player 2 chooses A: Player 1 then gets a payoff of "eight" (which in real-world terms can be interpreted in many ways, the simplest of which is in terms of money but could mean things such as eight days of vacation or eight countries conquered or even eight more opportunities to play the same game against other players) and Player 2 gets a payoff of "two". The extensive form can also capture simultaneous-move games and games with imperfect information. To represent it, either a dotted line connects different vertices to represent them as being part of the same information set (i.e. the players do not know at which point they are), or a closed line is drawn around them. (See example in the imperfect information section.) Normal form[edit] Player 2 chooses Left Player 2 chooses Right Player 1 chooses Up 4, 3 –1, –1 Player 1 chooses Down 0, 0 3, 4 Normal form or payoff matrix of a 2-player, 2-strategy game Main article: Normal-form game
The normal (or strategic form) game is usually represented by a matrix
which shows the players, strategies, and payoffs (see the example to
the right). More generally it can be represented by any function that
associates a payoff for each player with every possible combination of
actions. In the accompanying example there are two players; one
chooses the row and the other chooses the column. Each player has two
strategies, which are specified by the number of rows and the number
of columns. The payoffs are provided in the interior. The first number
is the payoff received by the row player (Player 1 in our example);
the second is the payoff for the column player (Player 2 in our
example). Suppose that Player 1 plays Up and that Player 2 plays Left.
Then Player 1 gets a payoff of 4, and Player 2 gets 3.
When a game is presented in normal form, it is presumed that each
player acts simultaneously or, at least, without knowing the actions
of the other. If players have some information about the choices of
other players, the game is usually presented in extensive form.
Every extensive-form game has an equivalent normal-form game, however
the transformation to normal form may result in an exponential blowup
in the size of the representation, making it computationally
impractical.[34]
Characteristic function form[edit]
Main article:
C displaystyle mathbf C appears, it works against the fraction ( N C ) displaystyle left( frac mathbf N mathbf C right) as if two individuals were playing a normal game. The balanced payoff of C is a basic function. Although there are differing examples that help determine coalitional amounts from normal games, not all appear that in their function form can be derived from such. Formally, a characteristic function is seen as: (N,v), where N represents the group of people and v : 2 N → R displaystyle v:2^ N to mathbf R is a normal utility.
Such characteristic functions have expanded to describe games where
there is no removable utility.
General and applied uses[edit]
As a method of applied mathematics, game theory has been used to study
a wide variety of human and animal behaviors. It was initially
developed in economics to understand a large collection of economic
behaviors, including behaviors of firms, markets, and consumers. The
first use of game-theoretic analysis was by Antoine Augustin Cournot
in 1838 with his solution of the Cournot duopoly. The use of game
theory in the social sciences has expanded, and game theory has been
applied to political, sociological, and psychological behaviors as
well.
Although pre-twentieth century naturalists such as
A four-stage centipede game The primary use of game theory is to describe and model how human
populations behave. Some[who?] scholars believe that by finding the
equilibria of games they can predict how actual human populations will
behave when confronted with situations analogous to the game being
studied. This particular view of game theory has been criticized. It
is argued that the assumptions made by game theorists are often
violated when applied to real world situations. Game theorists usually
assume players act rationally, but in practice, human behavior often
deviates from this model. Game theorists respond by comparing their
assumptions to those used in physics. Thus while their assumptions do
not always hold, they can treat game theory as a reasonable scientific
ideal akin to the models used by physicists. However, empirical work
has shown that in some classic games, such as the centipede game,
guess 2/3 of the average game, and the dictator game, people regularly
do not play Nash equilibria. There is an ongoing debate regarding the
importance of these experiments and whether the analysis of the
experiments fully captures all aspects of the relevant situation.[38]
Some game theorists, following the work of
Cooperate Defect Cooperate -1, -1 -10, 0 Defect 0, -10 -5, -5 The Prisoner's Dilemma Some scholars, like Leonard Savage,[citation needed] see game theory
not as a predictive tool for the behavior of human beings, but as a
suggestion for how people ought to behave. Since a strategy,
corresponding to a
Hawk Dove Hawk 20, 20 80, 40 Dove 40, 80 60, 60 The hawk-dove game Main article: Evolutionary game theory
Unlike those in economics, the payoffs for games in biology are often
interpreted as corresponding to fitness. In addition, the focus has
been less on equilibria that correspond to a notion of rationality and
more on ones that would be maintained by evolutionary forces. The best
known equilibrium in biology is known as the evolutionarily stable
strategy (ESS), first introduced in (Smith & Price 1973). Although
its initial motivation did not involve any of the mental requirements
of the Nash equilibrium, every ESS is a Nash equilibrium.
In biology, game theory has been used as a model to understand many
different phenomena. It was first used to explain the evolution (and
stability) of the approximate 1:1 sex ratios. (Fisher 1930) suggested
that the 1:1 sex ratios are a result of evolutionary forces acting on
individuals who could be seen as trying to maximize their number of
grandchildren.
Additionally, biologists have used evolutionary game theory and the
ESS to explain the emergence of animal communication.[57] The analysis
of signaling games and other communication games has provided insight
into the evolution of communication among animals. For example, the
mobbing behavior of many species, in which a large number of prey
animals attack a larger predator, seems to be an example of
spontaneous emergent organization. Ants have also been shown to
exhibit feed-forward behavior akin to fashion (see Paul Ormerod's
Butterfly Economics).
Biologists have used the game of chicken to analyze fighting behavior
and territoriality.[58]
According to Maynard Smith, in the preface to
Stag Hare Stag 3, 3 0, 2 Hare 2, 0 2, 2 Stag hunt
Based on the book by Sylvia Nasar,[73] the life story of game theorist
and mathematician John Nash was turned into the biopic A Beautiful
Mind starring Russell Crowe.[74]
"Games theory" and "theory of games" are mentioned in the military
science fiction novel
See also[edit] Chainstore paradox Collective intentionality Combinatorial game theory Confrontation analysis Glossary of game theory Intra-household bargaining Kingmaker scenario Parrondo's paradox Quantum game theory Quantum refereed game Rationality Reverse game theory Self-confirming equilibrium Zermelo's theorem Tragedy of the commons Law and economics Lists List of cognitive biases List of emerging technologies List of games in game theory Outline of artificial intelligence Notes[edit] ^ a b Myerson, Roger B. (1991). Game Theory: Analysis of Conflict,
Harvard University Press, p. 1. Chapter-preview links, pp.
vii–xi.
^ Bellhouse, David (2007), "The Problem of Waldegrave" (PDF), Journal
Électronique d'Histoire des Probabilités et de la Statistique, 3
(2)
^ James Madison, Vices of the Political System of the United States,
April 1787.
^ Jack Rakove, "
1992. v. 1; 1994. v. 2; 2002. v. 3. ^ Game-theoretic model to examine the two tradeoffs in the acquisition
of information for a careful balancing act Research paper INSEAD
^ Options Games: Balancing the trade-off between flexibility and
commitment Archived 20 June 2013 at the Wayback Machine..
Europeanfinancialreview.com (15 February 2012). Retrieved on
2013-01-03.
^ (Downs 1957)
^ Steven J. Brams,
References and further reading[edit] Wikiquote has quotations related to: Game theory Wikimedia Commons has media related to Game theory. Textbooks and general references[edit] Aumann, Robert J (1987), "game theory", The New Palgrave: A Dictionary
of Economics, 2, pp. 460–82 .
Camerer, Colin (2003), "Introduction", Behavioral Game Theory:
Experiments in Strategic Interaction, Russell Sage Foundation,
pp. 1–25, ISBN 978-0-691-09039-9 , Description.
Dutta, Prajit K. (1999), Strategies and games: theory and practice,
MIT Press, ISBN 978-0-262-04169-0 . Suitable for
undergraduate and business students.
Fernandez, L F.; Bierman, H S. (1998),
Published in Europe as Gibbons, Robert (2001), A Primer in Game Theory, London: Harvester Wheatsheaf, ISBN 978-0-7450-1159-2 . Gintis, Herbert (2000),
Historically important texts[edit] Aumann, R.J. and Shapley, L.S. (1974), Values of Non-Atomic Games, Princeton University Press Cournot, A. Augustin (1838), "Recherches sur les principles mathematiques de la théorie des richesses", Libraire des sciences politiques et sociales, Paris: M. Rivière & C.ie Edgeworth, Francis Y. (1881), Mathematical Psychics, London: Kegan Paul Farquharson, Robin (1969), Theory of Voting, Blackwell (Yale U.P. in the U.S.), ISBN 0-631-12460-8 Luce, R. Duncan; Raiffa, Howard (1957), Games and decisions: introduction and critical survey, New York: Wiley reprinted edition: R. Duncan Luce ;
Maynard Smith, John (1982),
Other print references[edit] Ben David, S.; Borodin, Allan; Karp, Richard; Tardos, G.; Wigderson,
A. (1994), "On the Power of Randomization in On-line Algorithms"
(PDF), Algorithmica, 11 (1): 2–14, doi:10.1007/BF01294260
Downs, Anthony (1957), An Economic theory of Democracy, New York:
Harper
Gauthier, David (1986), Morals by agreement, Oxford University Press,
ISBN 978-0-19-824992-4
Allan Gibbard, "Manipulation of voting schemes: a general result",
Econometrica, Vol. 41, No. 4 (1973), pp. 587–601.
Grim, Patrick; Kokalis, Trina; Alai-Tafti, Ali; Kilb, Nicholas; St
Denis, Paul (2004), "Making meaning happen", Journal of Experimental
& Theoretical Artificial Intelligence, 16 (4): 209–243,
doi:10.1080/09528130412331294715
Harper, David; Maynard Smith, John (2003), Animal signals, Oxford
University Press, ISBN 978-0-19-852685-8
Lewis, David (1969), Convention: A Philosophical Study ,
ISBN 978-0-631-23257-5 (2002 edition)
McDonald, John (1950–1996), Strategy in Poker, Business & War,
W. W. Norton, ISBN 0-393-31457-X . A layman's introduction.
Papayoanou, Paul (2010), Game Theory for Business: A Primer in
Strategic Gaming, Probabilistic, ISBN 978-0964793873 .
Quine, W.v.O (1967), "Truth by Convention", Philosophica Essays for
A.N. Whitehead, Russel and Russel Publishers,
ISBN 978-0-8462-0970-6
Quine, W.v.O (1960), "Carnap and Logical Truth", Synthese, 12 (4):
350–374, doi:10.1007/BF00485423
Mark A. Satterthwaite, "Strategy-proofness and Arrow's Conditions:
Existence and Correspondence Theorems for Voting Procedures and Social
n displaystyle n -person games in partition function form", Naval Research Logistics
Quarterly, 10 (4): 281–298, doi:10.1002/nav.3800100126
Dolev, Shlomi; Panagopoulou, Panagiota; Rabie, Mikael; Schiller, Elad
Michael; Spirakis, Paul (2011), "
External links[edit] Look up game theory in Wiktionary, the free dictionary. Wikiversity has learning resources about Game Theory Wikibooks has a book on the topic of: Introduction to Game Theory James Miller (2015): Introductory Game Theory Videos.
Hazewinkel, Michiel, ed. (2001) [1994], "Games, theory of",
Encyclopedia of Mathematics, Springer Science+Business Media B.V. /
Kluwer Academic Publishers, ISBN 978-1-55608-010-4
Paul Walker: History of Game Theory Page.
David Levine: Game Theory. Papers, Lecture Notes and much more stuff.
Alvin Roth:"Game Theory and Experimental
v t e Topics in game theory Definitions
Equilibrium concepts Nash equilibrium Subgame perfection Mertens-stable equilibrium Bayesian Nash equilibrium Perfect Bayesian equilibrium Trembling hand Proper equilibrium Epsilon-equilibrium Correlated equilibrium Sequential equilibrium Quasi-perfect equilibrium Evolutionarily stable strategy Risk dominance Core Shapley value Pareto efficiency Gibbs equilibrium Quantal response equilibrium Self-confirming equilibrium Strong Nash equilibrium Markov perfect equilibrium Strategies Dominant strategies Pure strategy Mixed strategy Strategy-stealing argument Tit for tat Grim trigger Collusion Backward induction Forward induction Markov strategy Classes of games Symmetric game
Perfect information
Repeated game
Signaling game
Screening game
Cheap talk
Zero-sum game
Mechanism design
Games Chess Infinite chess Checkers Tic-tac-toe Prisoner's dilemma Optional prisoner's dilemma Traveler's dilemma Coordination game Chicken Centipede game Volunteer's dilemma Dollar auction Battle of the sexes Stag hunt Matching pennies Ultimatum game Rock–paper–scissors Pirate game Dictator game Public goods game Blotto game War of attrition El Farol Bar problem Fair division Fair cake-cutting Cournot game Deadlock Diner's dilemma Guess 2/3 of the average Kuhn poker Nash bargaining game Prisoners and hats puzzle Trust game Princess and Monster game Rendezvous problem Theorems
Key figures Albert W. Tucker Amos Tversky Ariel Rubinstein Claude Shannon Daniel Kahneman David K. Levine David M. Kreps Donald B. Gillies Drew Fudenberg Eric Maskin Harold W. Kuhn Herbert Simon Hervé Moulin Jean Tirole Jean-François Mertens John Harsanyi John Maynard Smith Antoine Augustin Cournot John Nash John von Neumann Kenneth Arrow Kenneth Binmore Leonid Hurwicz Lloyd Shapley Melvin Dresher Merrill M. Flood Oskar Morgenstern Paul Milgrom Peyton Young Reinhard Selten Robert Axelrod Robert Aumann Robert B. Wilson Roger Myerson Samuel Bowles Thomas Schelling William Vickrey See also All-pay auction Alpha–beta pruning Bertrand paradox Bounded rationality Combinatorial game theory Confrontation analysis Coopetition First-move advantage in chess Game mechanics Glossary of game theory List of game theorists List of games in game theory No-win situation Solving chess Topological game Tragedy of the commons Tyranny of small decisions v t e Areas of mathematics outline topic lists Branches Arithmetic History of mathematics
Algebra Number theory Elementary Linear Multilinear Abstract Combinatorics Group theory Calculus Analysis Differential equations / Dynamical systems Numerical analysis Optimization Functional analysis Geometry Discrete Algebraic Analytic Differential Finite Topology Trigonometry Applied Probability
Mathematical physics
Mathematical statistics
Statistics
Computer science
Game theory
Recreational mathematics
Divisions Pure Applied Discrete Computational Category Portal Commons WikiProject v t e Property By owner Communal land Marital property (USA) Cooperative Estate in land Private Public State Crown land By nature Croft Intangible Intellectual indigenous Personal Tangible immovable real Common resources Common land Common-pool resource Digital Global Information Knowledge Theory Bundle of rights Commodity fictitious commodities Common good (economics) Excludability First possession appropriation homestead principle Free rider problem Game theory Georgism Gift economy Labor theory of property Law of rent rent-seeking Legal plunder Natural rights Ownership common customary self state
primogeniture usufruct women's Right to property Rivalry Tragedy of the commons anticommons Applications
alienation easement restraint on alienation real estate title Rights Air Fishing Forest-dwelling (India) Freedom to roam Grazing pannage Hunting Land aboriginal indigenous squatting Littoral Mineral Bergregal Right of way Water prior-appropriation riparian Disposession/ redistribution Bioprospecting Collectivization Eminent domain Enclosure Eviction Expropriation Farhud Forced migration population transfer Illegal fishing Illegal logging Land reform Legal plunder Piracy Poaching Primitive accumulation Privatization Regulatory taking Slavery bride-buying human trafficking wage wife selling Tax inheritance poll progressive property Theft Scholars (key work) Frédéric Bastiat Ronald Coase Henry George Garrett Hardin David Harvey John Locke Two Treatises of Government Karl Marx Marcel Mauss The Gift John Stuart Mill Elinor Ostrom Karl Polanyi The Great Transformation Pierre-Joseph Proudhon What Is Property? David Ricardo Murray N. Rothbard The
Jean-Jacques Rousseau The Social Contract Adam Smith The Wealth of Nations Categories: Property
by country Authority control LCCN: sh85052941 GND: 40562 |