[Math Lair] Game Theory

Math Lair Home > Topics > Game Theory

Game theory was designed as a decision-making tool to be used in situations in which there are factors other than chance and your choice. In game theory related problems, while decision makers are trying to manipulate their environment, their environment (which may include other decision makers) is trying to manipulate them.

Basic Terminology

A situation.
A complete plan of action for a game.
Intelligent entities (usually at least two), who pick strategies.
Rewards and/or punishments for each player.
Player 2 chooses strategy APlayer 2 chooses strategy B
Player 1 chooses strategy A 2, −3−1, 4
Player 1 chooses strategy B −3, 14, 0

There are several ways to represent games. One of these ways is in what is called "normal form." A game represented in normal form is represented in a matrix, where each row represents each strategy chosen by the first player, each column represents the strategy chosen by the second player, and each cell of the matrix gives the playoffs for each player. Note that a "strategy" can encapsulate multiple "moves" in a game. The table on the right is a simple example of a simple game expressed in normal form. If, say, player 1 chose strategy A and player 2 chose strategy B, player 1 would get −1 (the first number in the corresponding cell) and player 2 would get 4.

Note that, in the above example, the gains for one player do not equal the losses of the other player. Such a game is called a non-zero-sum game. A game where the losses and gains do balance out is called a zero-sum game. Both have many practical applications. For example, the relations between two countries might be modelled with a non-zero-sum game. If both countries decide to, say, wage nuclear war on each other, they will both suffer great losses, while if they engage in peaceful co-operation, it may be to their mutual benefit. On the other hand, if two parties are competing for a fixed amount of a resource (e.g. money), one's gain will be the other's loss.

In general, each player in a game will have a strategy that maximizes his payoff in the long run. The goal of many game theory scenarios is to find that strategy, given the players, payoffs, available information, and possible actions.

Things aren't always so simple when applying that strategy to real life, because people don't always act in accordance with what mathematically appears to be the best strategy. Consider a game in which you must choose between the following two possibilities:

  1. You get $1.
  2. A coin is flipped. If it comes up heads, you get $10. Otherwise you get nothing.

Most people would go for option 2; this choice is rational, since this option maximizes a player's average return ($5 versus $1). Now consider the following game in which you must choose between the following two possibilities:

  1. You get $1,000,000.
  2. A coin is flipped. If it comes up heads, you get $10,000,000. Otherwise you get nothing.

Now most people will choose option 1, even though this option leads to a smaller average return ($1,000,000 versus $5,000,000). This is because most people perceive both $1,000,000 and $10,000,000 as "huge sums of money", so the difference is not comprehended as easily as the difference between $1 and $10. Most people want a sure "large sum" rather than a 50% chance of getting nothing. This also relates to the economic concept of utility.

Here are some interesting applications of game theory:

Combinatorial Games

Combinatorial game theory is another theory of games. In the examples above, note that flipping a coin involves an element of chance, while Prisoner's Dilemma involves hidden information (the two prisoners do not know what option the other has chosen). In contrast, combinatorial games (1) have what is known as perfect information (no chance is involved and no player can hide information about the game state from other players) and (2) they are sequential (one player makes a move, then another, and so on). For more information on combinatorial games, see Combinatorial Games.