Branches of Mathematic

Game Theory

Also Known As Theory of Games

Mathematical Physics, Biology and Game Theory

The mathematical study of strategic decision-making among agents whose outcomes depend on each other's choices. John von Neumann proved the minimax theorem for two-player zero-sum games in 1928, showing a rational optimal strategy always exists in such a game, and with the economist Oskar Morgenstern gave the field its first general mathematical formulation in Theory of Games and Economic Behavior (1944). John Nash extended the framework beyond zero-sum, two-player settings in 1950, defining the solution concept now called the Nash equilibrium, a set of strategies from which no single player can improve their own outcome by changing strategy alone. A separate strand, combinatorial game theory, grew out of the study of two-player games of perfect information with no chance element: John Conway developed it while analyzing Go endgames at Cambridge, publishing the theory, and the surreal numbers that fell out of it, in On Numbers and Games (1976). Both strands meet chess and Go directly. Chess is the standard worked example of minimax search over a game tree; Claude Shannon estimated the lower bound of that tree's own complexity at roughly 10 to the 120th power of possible games in his own 1950 paper Programming a Computer for Playing Chess, a number still cited as the reason brute-force solution is impossible. Go endgames are where combinatorial game theory itself began.

Facts

Central Question

Given that every player's own best choice depends on what every other player chooses, does a stable, rational strategy exist at all, and if so, what is it? 2

Key Debate

Whether the field's own core assumption, that players are rational actors maximizing a well-defined payoff, describes how people and institutions actually behave, or is a simplifying idealization useful chiefly as a benchmark; the gap between predicted equilibria and observed play in laboratory and real-world settings is itself an active field, behavioral game theory. 2

Classification

Pure or Applied

Applied Mathematics 1

Learn More

A Number Ten to the 120th

This article records tradition as it has been passed down and reported. Its sources are not yet part of the atlas's verified catalogue.

In 1950, Claude Shannon published a paper with a modest title, Programming a Computer for Playing Chess, that founded computer chess as a field before a single working chess program existed to test it against. Buried in the paper is a calculation Shannon almost certainly meant as an aside: an estimate of how many distinct games of chess are possible, arrived at from roughly 30 legal choices per move and a typical game running 40 moves per side. The number that falls out, on the order of 10 to the 120th power, is now called the Shannon number, and it is not a claim about how many games have been played or ever will be. It is a claim about why a certain kind of solution to chess was never going to work. A player, or a computer, considering the full game tree, every possible sequence of moves from the current position to the end of the game, cannot simply enumerate all of them and pick the best line, because there are more of them than there are atoms usually estimated to exist in the observable universe. Shannon's own point was not that chess is unsolvable in principle; two-player games of perfect information with no chance element are, in a strict mathematical sense established well before Shannon wrote, always solvable by exhaustive search given enough time. His point was that no amount of raw computing power anyone would ever plausibly build could do that exhaustive search directly, which meant a chess-playing program would have to evaluate positions heuristically rather than by looking all the way to the end. Every chess engine built since, from the first primitive programs of the 1950s through the systems that eventually beat human world champions, has been an answer to the problem Shannon's own number stated rather than solved.

Numbers That Fell Out of a Board Game

This article records tradition as it has been passed down and reported. Its sources are not yet part of the atlas's verified catalogue.

John von Neumann and John Nash built the branch of game theory most people mean by the term: players with defined payoffs, choosing strategies, converging or failing to converge on an equilibrium. John Conway built a different one almost by accident, while trying to understand the endgame of Go. Late-stage Go positions often break into several independent regions of the board where play barely interacts, and Conway, analyzing how the value of each region combines with the others, found that the combining itself obeyed rules that looked exactly like arithmetic on a new and much larger kind of number. He worked out the theory properly and published it in 1976 as On Numbers and Games, and the numbers themselves came to be called surreal numbers: a system vast enough to contain every real number, every ordinal number, and infinitely many infinitesimal and infinite quantities besides, all constructed from nothing but the recursive idea of a game position and its possible moves. This is combinatorial game theory, and it is a genuinely different animal from the von Neumann and Nash tradition. Von Neumann and Nash games typically involve simultaneous choices, incomplete information about the other player's intentions, and payoffs that can require compromise or bluffing to navigate. Conway games are sequential, perfect-information, no-chance contests like Go, chess endings, or Nim, where the entire question is which player, moving optimally, forces a win. The two traditions share a name and a founding motivation, understanding strategic play mathematically, and very little else about their machinery. That a Cambridge mathematician found a new kind of number by staring hard enough at a Go endgame is, on its own terms, one of the stranger origin stories in modern mathematics.

Game Theory

1 entry

Origin Era

Zero-Sum Game

Game Theory

Connections

Associated With

Applied and Computational Mathematics

Algorithmic game theory, computing equilibria and analyzing the computational complexity of finding them, is a substantial modern subfield shared with applied and computational mathematics.

Source The Stanford Encyclopedia of Philosophy

John von Neumann

Source MacTutor History of Mathematics Archive

Probability and Statistics

Game theory shares its expected-value and optimization machinery with probability and statistics; mixed strategies are themselves probability distributions over pure strategies.

Source The Stanford Encyclopedia of Philosophy

Includes

Albert W. Tucker

Source Albert W. Tucker (Wikipedia)

Allan Gibbard

Source Allan F. Gibbard curriculum vitae (University of Michigan)

Anatol Rapoport

Source Anatol Rapoport (Wikipedia)

Arrow's Impossibility Theorem

Aumann's Agreement Theorem

Bishop-Cannings Theorem

Source Bishop-Cannings theorem (Wikipedia)

Bondareva-Shapley Theorem

Source Bondareva-Shapley theorem - Wikipedia

Combinatorial Game Theory

Combinatorial game theory grew out of, and remains a distinct part of, the wider study of game theory that von Neumann and Nash founded; it does not itself originate the whole game-theory branch.

Source MacTutor History of Mathematics Archive

David Blackwell

Source David Blackwell (Wikipedia)

David Wolpert

Source David Wolpert (Wikipedia)

Debreu's Theorems

Source Debreu's representation theorems (Wikipedia)

Dictator Game

Source Wolfram MathWorld: Dictator Game

Duggan-Schwartz Theorem

Source Duggan-Schwartz theorem (Wikipedia)

Éva Tardos

Source Éva Tardos (Wikipedia)

Folk Theorem (Game Theory)

Gale-Shapley Theorem

Source Gale-Shapley algorithm (Wikipedia)

Gibbard's Theorem

Source Gibbard's theorem - Wikipedia

Gibbard-Satterthwaite Theorem

Harold W. Kuhn

Source Harold W. Kuhn (Wikipedia)

Harsanyi's Purification Theorem

Source Purification theorem - Wikipedia

Hawk-Dove Game

Source Chicken (game) (Wikipedia)

Herbert Scarf

Source Herbert Scarf (Wikipedia)

Jennifer Tour Chayes

Source Jennifer Tour Chayes (Wikipedia)

John Conway

Source MacTutor History of Mathematics Archive

John Nash

Source Nash, Non-Cooperative Games (1951)John Nash

John von Neumann

Source von Neumann, Zur Theorie der Gesellschaftsspiele (1928)John von Neumann

Kuhn's Theorem

Source Kuhn's theorem (Wikipedia)

Lloyd Shapley

Source Wikipedia: Lloyd Shapley

Mark Satterthwaite

Source Mark Satterthwaite faculty profile (Kellogg School of Management)

Martin Nowak

Source Martin Nowak (Wikipedia)

May's Theorem

Source Wolfram MathWorld: May's Theorem

McKelvey-Schofield Chaos Theorem

Source McKelvey-Schofield chaos theorem, Wikipedia

Melvin Dresher

Source Wikipedia: Melvin Dresher

Minimax Theorem

Source von Neumann, Zur Theorie der Gesellschaftsspiele (1928)John von Neumann

Mixture-Space Theorem

Source Mixture-space theorem - Wikipedia

Myerson-Satterthwaite Theorem

Nash Equilibrium

Source Nash, Non-Cooperative Games (1951)John Nash

Nash's Bargaining Theorem

Source Cooperative bargaining (Wikipedia)

Olga Bondareva

Source Wikipedia: Olga Bondareva

Prisoner's Dilemma

Source Wikipedia: Prisoner's dilemma

Replicator Equation

Source Replicator equation (Wikipedia)

Revelation Principle

Robert Aumann

Source Nobel Prize Outreach: Robert J. Aumann Facts

Rubinstein Bargaining Model

Source Rubinstein bargaining model (Wikipedia)

Shapley-Folkman Theorem

Shapley's Theorem

Source Shapley value (Wikipedia)

Sprague-Grundy Theorem

Stag Hunt

Source Stag hunt (Wikipedia)

Tit for Tat

Source Tit for Tat (Wikipedia)

Vickrey-Clarke-Groves Theorem

Source Vickrey-Clarke-Groves mechanism (Wikipedia)

Showing 1 to 50 of 53 in Includes, page 1 of 2.

Long-Form Articles

A Number Ten to the 120th

Numbers That Fell Out of a Board Game

In the Other Atlases

Is Discussed By

Chess

Also in Sport and Games Atlas: which discusses this subject.

Sources

1. Wikipedia: Game Theory

Wikimedia Foundation

Theory and methodology
Unlike traditional econometric models that are descriptive (in the sense of predicting future outcomes based on historical data and statistical trends between variables) and optimisation algorithms (which assume static environments and generally address single-objective problems within predefined constraints), game theory is inherently dynamic and accounts for the strategic interactions among participants.
Lead section, pure or applied classification
Game theory is the field of applied mathematics that models interactions between multiple agents as "games" of strategy between "players".
In Group: Strategic Interaction and Games, lead paragraph
Game theory is the field of applied mathematics that models interactions between multiple agents