An Introduction to Game Theory Content from the guide to life, the universe and everything

An Introduction to Game Theory

3 Conversations

Game Theory has been incorporated as an important tool to understanding aspects of several subjects in the last fifty years. Basically it attempts to allow calculation of the best thing to do when confronted with a range of choices. This entry hopefully provides the basics of what Game Theory is, who developed it and why, and what problems in economics, psychology and evolutionary biology it has helped to understand.

Striking The Best Bargain

Game Theory is about understanding rational strategies1. John von Neumann, and the mathematical economist Oskar Morgenstern, were the first to develop the theory systematically, in order to assist understanding of economics (specifically neoclassical economics). The first important book on the subject was by them: The Theory of Games and Economic Behaviour, published in 1944. Although this is the starting point for much of the theory that follows it can be argued that aspects of Game Theory have been around since the 18th Century - or even (though without mathematical explanation of the reasoning) in the Babylonian Talmud2.

In making economic decisions many factors can exist that affect the rational strategies that a person, business or government might wish to use. The difficulty for neoclassical economics is that it only considered what was rational from a single viewpoint, interacting with nebulous 'market conditions'.

It is assumed in neoclassical economics that 'everyone acting rationally is attempting to maximize their own rewards'. People (acting through the market) aim to gain profits, income or other benefits for themselves. Game Theory removes the indirect dealing with a market and uses direct interactions between players in games to draw conclusions about rational strategies.

Simple games are used as a metaphor for interactions between two or more competitors (or since we are talking about games these are often called players), where the outcome of the game depends upon the combination of strategies chosen by the players, with each player wanting to achieve the best outcome for themselves that they can. Here, unlike in the neoclassical view, what makes a rational strategy also depends on what other players choose as their strategies.

In Game Theory, strategies and their payoffs are usually summarised in a payoff table, an example of which can be seen later, where the Prisoners' Dilemma is discussed.

The most rational strategy for a game will depend on various conditions - some of the most important of which are:

  • What the potential pay-offs are for different strategies

  • Whether the players can communicate with each other

  • How many players there are

  • Whether they will play one game, a fixed number, or indefinite number of games

The first condition is at the heart of a division between types of games - whether the game is Zero Sum or Non-Zero Sum. A Zero Sum game is one where, whatever strategies are chosen, the total winnings match the total losses (winnings - losses = Zero). In a two-player game this means whatever amount one player wins the other has lost (chess is often given as an example of a zero sum game, but it isn't simple enough to summarise in a pay-off matrix). A Non-Zero Sum game by contrast can pay out more or less dependant on the players strategies - sometimes all players can end up winners (or losers). A Zero Sum game can be identified if for every cell3 in its pay-off matrix the sum of the pay-offs is zero.

Von Neumann proved that in all two-player Zero Sum games there is a solution that allows both players to choose the rational 'maximin' strategy. The maximin strategy is the one that maximizes the minimum pay-off, and this strategy is the rational one - the one which provides the maximum pay-off whatever strategy is adopted by the other player. Unfortunately, this solution only applies in Zero Sum games, and in real life very few interactions can be characterized as Zero Sum - most of them being games created by people, rather than real life interactions.

The second condition, whether the players can bargain with each other directly, can determine whether a Non-Zero Sum4 game will be played in a Cooperative or Non-Cooperative style - in other words either negotiating to get the best overall deal for all players, or each player competing to get the best deal for themselves.

The third condition boils down to complexity - two-player games are easiest to analyse and explain.

The fourth condition adds another layer of strategy5, where results of earlier games can affect the strategy for later ones, and can lead to the development of altruism. This is key to the use of Game Theory in evolutionary biology and development of Evolutionary Stable Strategies (ESSs).

This might all seem a trifle hard to grasp. Some aspects will become clearer with an example

The Prisoners' Dilemma

Various games have been devised to model different types of interaction. One of the most famous is The Prisoners'6 Dilemma, which was created in 1950 by AW Tucker at Stanford University to show a group of psychologists the difficulties in analyzing certain kinds of game.

This game has two players and each must make a choice between either trusting or not trusting the other player. It is based on the scenario of two criminals (Tucker called them Al and Bob) who have been arrested as suspects for a burglary. Each is interviewed separately, and can either confess (implicating the other criminal) or stay quiet.

This leads to four possible outcomes:

  • Both confess (in which case they both get convicted with a moderate sentence).

  • Al confesses, Bob doesn't (in which case Al gets off free (for collaborating with the police), and Bob is convicted and receives the maximum sentence).

  • Bob confesses, Al doesn't (in which case Bob gets off free (for collaborating with the police), and Al is convicted and receives the maximum sentence).

  • Both say nothing (in which case neither can be convicted of the burglary due to insufficient evidence, and both only face the lesser punishment for carrying a concealed weapon).

These strategies and their pay-offs, as mentioned earlier, are usually summarised in a payoff matrix, as below:

(In each cell Al's pay-off comes first, followed by Bob's)

Prisoners' Dilemma Pay-off Matrix
 Bob
ConfessDon't Confess
AlConfess-10, -10 0, -20
Don't Confess-20, 0 -1, -1

You may be asking yourself 'What is the dilemma?' Consider the position of Al choosing his strategy - should Al confess or not? There are two situations Al has to consider - is Bob going to squeal or is he not? In this game the pay-offs are actually penalties (time spent in prison), so a player's rational strategy should be to minimise their length of sentence.

  • If Bob confesses (the first column) Al's best strategy is to confess as well, otherwise Al will go to prison for a much longer time.

  • But if Bob doesn't confess (second column) Al's rational strategy is again to confess, as Al can then get off free rather than spend a year in jail.

So whatever Bob does Al's rational strategy should be to confess. This is called a dominant strategy. A dominant strategy is one which is best against all strategies the player might face. The same reasoning applies for Bob. If this strategy is followed it results in both 'rational' players spending 10 years in prison, whereas if they had trusted the other player to keep quiet they could both have got out after only a year. So in this game each player's individual rational action led to inferior results for both! When both players have a dominant strategy the combination where they both choose their own dominant strategy is known as a dominant strategy equilibrium. When Al and Bob both confess we are seeing the dominant strategy equilibrium in action.

Reviewing the conditions mentioned earlier, the Prisoners' Dilemma is a Non-Zero Sum, Non-Cooperative, two-player single game.

Von Neumann had made discoveries that applied in the relatively simple solutions of Zero Sum games - that every two-player Zero Sum game had a maximin solution. This extended the well-defined 'rational policy' of neoclassical economics (maximisation of reward), but left unclear what could be considered as rational in the more realistic category of non-zero sum games.

A significant leap in understanding Non-Zero Sum games came with the insights that came from work on Non-Cooperative games.

Nash Equilibria

John Forbes Nash, a student of Tucker, built on the work by von Neumann and Morgenstern. His 1950 thesis Non-Cooperative Games developed several key concepts, and one of these was the idea of the Nash Equilibrium.

If there is a set of strategies with the property that no player can benefit by changing their strategy while the other players keep their strategies unchanged, then that set of strategies and the corresponding pay-offs constitute the Nash Equilibrium.

The development of this idea brought much better understanding of what is a rational strategy in a Non-Zero Sum game. Skipping the complexities of multiple player games (about which there is not much that can be written in a simple introduction to the subject), the final condition affecting strategies - playing the same game over and over again (iterating the game)- has had the most publicity in recent years.

Iterated Games and Super-Rationality

The Prisoners' Dilemma becomes much more applicable to real life situations when it is considered as an iterated game. This entry on the ramifications of the iterated game approaches it from a moralistic interpretation, and states the dilemma not as a paradoxical failure of rational strategy to give the best results, but as an argument for 'super-rational' responses.

Super-rationality can be thought of as recognition of the benefits of mutual altruism over short-term selfishness. It comes into its own in iterated games when players can develop trust in each other. Many interactions between organisms can be modelled using iterated games of Prisoners' Dilemma. This makes it a valuable tool for explaining how altruism could evolve.

Indeed Game Theory can provide a framework for testing many interactions between organisms and understanding how their behavioural strategies could have developed as Non-Cooperative iterated games, without the necessity of the organisms consciously 'negotiating'. This has been excellently popularised by Richard Dawkins, in particular with 'Nice Guys Finish First' a BBC Horizon documentary and chapter in his book The Blind Watchmaker.

Further Reading

  • Game Theory is a series of articles by Roger A. McCain that go into greater depth without requiring too much knowledge of economics, from which the definition of Nash Equilibria in this entry was taken.

  • Do you want to play an iterated game of Prisoners' Dilemma? Serendip provides a simple version as one of their brain games.

1By 'rational' is meant 'logical' or 'decided by reasoning' - one that makes sense if one assumes that all strategists are aiming to choose the most beneficial course of action for themselves.2See the Chronology in the References.3Each cell represents the pay-offs of a particular combination of strategies.4In a two-player Zero Sum game communication has less effect, as collaboration cannot provide a better pay-off than competition.5The iterative strategy, that is involving repetition.6Whether the apostrophe goes before or after the 's' depends upon whether the dilemma is being seen from the viewpoint of one prisoner, or that the same dilemma is facing both prisoners - in the literature both variants exist.

Bookmark on your Personal Space


Edited Entry

A1148069

Infinite Improbability Drive

Infinite Improbability Drive

Read a random Edited Entry


Written by

Edited by

h2g2 Editors

References

h2g2 Entries

External Links

Not Panicking Ltd is not responsible for the content of external internet sites

Write an Entry

"The Hitchhiker's Guide to the Galaxy is a wholly remarkable book. It has been compiled and recompiled many times and under many different editorships. It contains contributions from countless numbers of travellers and researchers."

Write an entry
Read more