What Is Game Theory? Definition, History, Examples and Uses

By Dawid Siedlarz · · 12 min read

Play Four in a Row free →

Short answer: Game theory is the branch of mathematics that studies decisions which depend on what other people decide. A "game" is any situation with several players, each choosing a strategy and receiving a payoff that depends on everyone's choices. The field was founded by John von Neumann (minimax theorem, 1928) and the book Theory of Games and Economic Behavior he wrote with Oskar Morgenstern (1944); John Nash added the Nash equilibrium in 1950. Today it is used in economics, auctions, politics, biology, security and artificial intelligence.

Most decisions are not made alone. The price a shop sets depends on what the shop across the street charges, a penalty taker's best corner depends on where the goalkeeper will dive, and a country's defence budget depends on its neighbours'. In each case the right choice depends on a guess about someone else's choice, and the other side is making the same kind of guess about you. Game theory is the toolkit for thinking about exactly that loop, and it is why the word "game" covers price wars and peace talks as well as chess.

What is game theory? A definition

Game theory is the study of strategic interaction: situations in which the outcome for each participant depends not only on their own decision but also on the decisions of others. To analyse such a situation, game theorists describe it with four ingredients:

  1. Players: the decision makers. They can be people, companies, countries, animals or computer programs.
  2. Strategies: the options each player can choose from, or a complete plan for every situation the player might face.
  3. Payoffs: what each player gets for every combination of strategies, written as numbers (money, years in prison, points, offspring).
  4. Information: what each player knows when choosing. In chess you see the whole board; in poker you do not see your opponent's cards.

Once a situation is written down like this, the question becomes: what should each player do, and what will happen if everybody reasons carefully? The answers are often surprising, because the choice that is best for each player alone can lead to a result that is worse for all of them.

Key ideas in game theory

Zero-sum and non-zero-sum games

In a zero-sum game one player's gain is exactly the other's loss: the payoffs always add up to zero. Chess, poker between two people and a penalty kick are zero-sum. In a non-zero-sum game both sides can win or both can lose. Trade, negotiations and most of economic life are non-zero-sum, which is why game theory is about much more than winning.

Dominant strategy

A strategy is dominant if it is the best choice whatever the other players do. When a player has a dominant strategy, the analysis is easy: they should play it. Many famous games are interesting precisely because the dominant strategies of all players together lead to a poor result.

Nash equilibrium

A Nash equilibrium is a set of strategies, one for each player, in which nobody can do better by changing only their own choice. It is a stable point: once players are there, no one has a reason to move alone. Two cars meeting on a road are in equilibrium when both drive on the right, and also when both drive on the left; that is why a country only needs to agree on one of them. The concept is named after John Nash, who proved in 1950 that every game with a finite number of players and strategies has at least one equilibrium.

Mixed strategies

Sometimes any predictable choice can be exploited. In rock-paper-scissors, a player who always picks rock loses to paper every time. The equilibrium is to play each option at random with probability one in three. Choosing at random according to fixed probabilities is called a mixed strategy, and allowing them is what makes Nash's theorem work for every finite game. Penalty takers and goalkeepers behave in roughly this way: a kicker who always picks the same side is easy to read.

Simultaneous and sequential games

In a simultaneous game players choose at the same time without seeing each other's choices (a sealed-bid auction, rock-paper-scissors). In a sequential game they take turns and can react to earlier moves (chess, a negotiation with offers and counter-offers). Sequential games are drawn as a game tree and solved by backward induction: start from the end, work out the best final move, then the best move before it, and so on back to the start.

Cooperative and non-cooperative games

Non-cooperative game theory studies players who each choose for themselves; this is where the Nash equilibrium belongs. Cooperative game theory asks what groups (coalitions) of players can achieve together and how to share the result fairly. The Shapley value, introduced by Lloyd Shapley in 1953, is its best-known answer to the sharing question, and today it is also used to explain which inputs drove a machine learning model's prediction.

The prisoner's dilemma: the most famous game

Two suspects are arrested and questioned in separate rooms. Each can stay silent or betray the other. If both stay silent, each gets one year in prison. If one betrays and the other stays silent, the traitor goes free and the silent one gets three years. If both betray, each gets two years.

B stays silentB betrays
A stays silent1 year eachA: 3 years, B: free
A betraysA: free, B: 3 years2 years each

Look at it from A's side. If B stays silent, betraying gets A out free instead of one year. If B betrays, betraying gives A two years instead of three. Whatever B does, betraying is better for A: it is a dominant strategy. The same holds for B. So both betray and serve two years each, even though both staying silent would have given them one year each. The only Nash equilibrium is worse for both players than an outcome they could have reached by trusting each other.

The game was devised in 1950 by Merrill Flood and Melvin Dresher at the RAND Corporation; the mathematician Albert Tucker gave it the prison story and its name. The same structure appears in price wars, arms races, overfishing and climate agreements: each side gains by defecting, and everyone loses if all do.

What happens when the game repeats

Played once, the prisoner's dilemma favours betrayal. Played many times with the same partner, things change, because today's betrayal can be punished tomorrow. Around 1980 the political scientist Robert Axelrod invited researchers to submit computer programs that played the repeated game against each other. The winner was one of the simplest entries, tit for tat, sent by Anatol Rapoport: cooperate in the first round, then copy whatever the opponent did last time. Axelrod described the results in The Evolution of Cooperation (1984). The lesson he drew: strategies that are nice (never betray first), retaliate, forgive and are easy to understand tend to do well.

Other classic games

  • Chicken (hawk-dove): two drivers race towards each other; whoever swerves loses face, but if neither swerves both crash. There are two equilibria, each with one player giving way, and much of the game is about convincing the other side you will not.
  • Stag hunt: two hunters can hunt a stag together (a big prize that needs both) or a hare alone (small but certain). Both hunting the stag and both hunting hares are equilibria; which one happens depends on trust.
  • Matching pennies: one player wins if two coins match, the other if they differ. There is no stable choice, only the mixed strategy of choosing heads or tails with probability one half. It is the simplest zero-sum game.

When was game theory created? A short history

People reasoned strategically long before anyone wrote equations for it, but game theory as a mathematical field is about a hundred years old. The main steps:

YearMilestone
1838Antoine Augustin Cournot models two firms choosing how much to produce; his solution is an early example of what is now called a Nash equilibrium.
1913Ernst Zermelo shows that in chess either White can force a win, Black can force a win, or both sides can force at least a draw.
1921Emile Borel publishes papers on mixed strategies in games.
1928John von Neumann proves the minimax theorem for two-player zero-sum games.
1944Von Neumann and Oskar Morgenstern publish Theory of Games and Economic Behavior, usually treated as the birth of the field.
1950John Nash defines the Nash equilibrium; Flood and Dresher create the prisoner's dilemma at RAND.
1953Lloyd Shapley introduces the Shapley value for sharing gains in a coalition.
1962David Gale and Lloyd Shapley publish the deferred acceptance algorithm for stable matching.
1973John Maynard Smith and George Price introduce the evolutionarily stable strategy, bringing game theory into biology.
1984Robert Axelrod's The Evolution of Cooperation reports his repeated prisoner's dilemma tournaments.
1994John Nash, John Harsanyi and Reinhard Selten receive the Nobel Memorial Prize in Economic Sciences.
2005Robert Aumann and Thomas Schelling receive the prize for analysing conflict and cooperation.
2012Alvin Roth and Lloyd Shapley receive the prize for stable allocations and market design.
2020Paul Milgrom and Robert Wilson receive the prize for improvements to auction theory and new auction formats.

So if you need one date, it is 1944, the year of von Neumann and Morgenstern's book; if you need the first theorem, it is von Neumann's minimax theorem of 1928. Nash's life later became the subject of the film A Beautiful Mind (2001).

The minimax theorem

Von Neumann's 1928 result says that in every two-player zero-sum game with finitely many strategies, there is a value v and a (possibly mixed) strategy for each player such that the first player can guarantee at least v on average and the second can hold the first to at most v. In other words, "maximise your worst case" and "minimise the opponent's best case" meet at the same number. It is the reason a zero-sum game has a well-defined "correct" way to play, and the same idea, applied move by move, is how chess programs think.

What is game theory used for?

Economics and business

Game theory is now part of the basic toolkit of economics. It models competition between a few large firms (oligopoly), pricing and entry into markets, bargaining between unions and employers, and contracts written when one side knows more than the other. A related field, mechanism design (Nobel prize 2007 for Leonid Hurwicz, Eric Maskin and Roger Myerson), works backwards: it starts from the outcome you want and designs the rules of the game so that players reach it while following their own interests.

Auctions

Auctions are games, and their rules change how people bid. Governments use auction designs from game theory to sell radio spectrum to mobile operators: the simultaneous multiple-round auction that Milgrom and Wilson helped design was first used by the US Federal Communications Commission in 1994. Every time you see an online ad, a fast automated auction among advertisers has usually decided which one appears.

Matching markets: doctors and kidneys

Some markets cannot use prices: you cannot buy a place at a school or a kidney. The Gale-Shapley algorithm finds a stable matching, one in which no two parties would both prefer each other to the partners they were given. A version of it, redesigned by Alvin Roth in the 1990s, matches graduating medical students to hospital residency programmes in the United States. Roth also helped build kidney exchanges, where incompatible donor-patient pairs swap donors so that more transplants can take place.

Politics and international relations

During the Cold War, game theory was used to think about nuclear deterrence: how a threat can be made believable, and why a second-strike capability makes a first strike pointless. Thomas Schelling's The Strategy of Conflict (1960) showed how commitment, credible threats and "focal points" (solutions people pick without talking, such as meeting at noon under the station clock) shape negotiations. Voting, coalition building and climate agreements are analysed with the same tools.

Biology and evolution

Animals do not calculate payoffs, but natural selection does it for them: strategies that earn more offspring spread. Maynard Smith and Price's 1973 paper used the hawk-dove game to explain why most fights between animals of the same species are ritual displays rather than fights to the death. An evolutionarily stable strategy is one that, once common in a population, cannot be invaded by a rare alternative. The same ideas are used to study cooperation, the sex ratio and how bacteria and viruses compete.

Computer science, AI and security

Game-playing programs search a game tree with the minimax rule: assume the opponent will always reply with their best move, and choose the move whose worst case is best. In 2017 the poker program Libratus, from Carnegie Mellon University, beat top professionals at heads-up no-limit Texas hold'em, and in 2019 its successor Pluribus won at six-player poker; both computed strategies close to an equilibrium instead of copying human play. Game theory also guides security patrols: since 2007 the police at Los Angeles International Airport have used software built on Stackelberg security games to randomise checkpoints and patrols so that attackers cannot predict them.

Everyday life

You do not need equations to use the main lessons. Before a decision that involves others, ask what they will do in response. Look for a dominant strategy. Notice when everyone acting in their own interest leads to a worse result for all (a prisoner's dilemma), and when it does, look for ways to make cooperation stick: repeated contact, reputation, agreements that are enforced. Splitting a bill, choosing a queue at the supermarket and deciding whether to haggle are all small games.

Game theory and the games on this site

Game theory and recreational games meet most clearly in two-player games of pure skill such as tic-tac-toe, Connect Four and checkers. They have no dice and no hidden cards, so, as Zermelo showed for chess, each has a fixed result with perfect play. Our article solved games explains which ones computers have cracked: tic-tac-toe is a draw, Connect Four is a first-player win and checkers is a draw.

The computer opponents in our games use exactly the minimax idea from von Neumann's theorem, cut off at a limited depth. In Four in a Row the computer on Hard looks four moves ahead (counting both players' moves) with minimax and alpha-beta pruning, which skips moves that cannot change the result. In Checkers it searches eight moves deep on Hard, in Reversi five and in Mancala nine. Because the search stops early, the computer is not a perfect player, which is why it can be beaten: set a trap that only pays off beyond its horizon. The Connect 4 strategy guide shows how.

A separate branch, combinatorial game theory, studies exactly these games of perfect information with no chance, such as Nim, Go endgames and Hex. It began with Charles Bouton's solution of Nim in 1901 and is a different subject from the economic game theory described above, although the two share the idea of reasoning backwards from the end of the game.

Common misconceptions

  • "Game theory assumes everyone is selfish." It assumes players pursue their payoffs, but payoffs can include caring about others, fairness or reputation. The theory says how to act given what you value, not what you should value.
  • "An equilibrium is the best outcome." Not necessarily. The prisoner's dilemma shows an equilibrium that is worse for everyone than another outcome.
  • "Real people play like the theory says." Often they do not. In experiments such as the ultimatum game, people reject unfair offers even though rejecting costs them money. Behavioural game theory studies these differences.
  • "It is only for mathematicians." The core ideas (players, strategies, payoffs, thinking about the other side's reply) need no maths at all, and they apply to any decision that involves other people.

Frequently asked questions

What is game theory in simple terms?

Game theory is the mathematics of decisions that depend on other people's decisions. It describes a situation as players, the strategies each can choose and the payoff each gets for every combination of choices, then asks what a sensible player should do and what outcome to expect.

Who invented game theory?

The mathematician John von Neumann is usually called its founder. He proved the minimax theorem in 1928, and his 1944 book Theory of Games and Economic Behavior, written with the economist Oskar Morgenstern, turned game theory into a field of its own. Ernst Zermelo (1913) and Emile Borel (1921) wrote important earlier papers.

What is a Nash equilibrium?

A Nash equilibrium is a combination of strategies in which no player can do better by changing only their own choice while the others keep theirs. John Nash proved in 1950 that every finite game has at least one, if players are allowed to mix their choices at random.

What is game theory used for?

It is used to design auctions and matching systems (for example the matching of doctors to hospitals and kidney exchanges), to study competition between firms, arms races and negotiations, to explain cooperation and conflict in animals, to plan security patrols, and in artificial intelligence for games such as chess and poker.

Is game theory about video games?

No. A game in game theory is any situation where several decision makers affect each other's results, such as a price war or a negotiation. Board games and video games are only one small example, although the minimax idea from game theory is how computer opponents in games like Connect Four and checkers choose their moves.