Game theory

In denegerate games, the players' payoffs only depend on their own actions. For example, in competitive markets (competitive market equilibrium), it is enough that each player optimizes regardless of the behavior of other traders. As soon as a small number of agents is involved in an economic transaction, however, the payoffs to each of them depend on the other agents' actions. For example in an oligopolistic industry or in a cartel, the price or the quantity set optimally by each firm depends crucially on the prices or quantities set by the competing firms. Similarly, in a market with a small number of traders, the equilibrium price depends on each trader's own actions as well as the one of his fellow traders (see auctions).

Whenever an optimizing agent expects a reaction from other agents to his own actions, his payoff is determined by other player's actions as well, and he is playing a game. Game theory provides general methods of dealing with interactive optimization problems; its methods and concepts, particularly the notion of strategy and strategic equilibrium find a vast number of applications throughout social sciences (including biology). Although the word 'game' suggests peaceful and 'kind' behavior, most situations revelant in politics, psychology, biology, and economics involve rather strong conflicts of interest, competition, and cheating, apart from leaving room for cooperation or mutually benefically actions.

Based on a model of optimizing agents that plan individually optimal course of play, knowing that her opponents will do so as well, the basic objects of interest in strategic (or 'non-cooperative') game theory are the players' strategies. A player's strategy is a complete plan of actions to be taken when the game is actually played; it must be completely specified before the actual play of the game starts, and it prescribe the course of play for each decision that a player might be called upon to take, for each possible piece of information that the player may have at each time where he might be called upon to act. A strategy may also include random moves. It is generally assumed that the players evaluate uncertain payoffs according to von Neumann Morgenstern utility. In addition to the strategic branch of game theory, there is another one that focuses on the interactions of groups of players that jointly strive to maximize their surplus. While this second branch represents the analysis of coalitional games, which centers around notions of 'coalitionally stable' payoff configurations, we focus here on strategic game theory (from which coalitional games are derived).

Given a strategic game, a profile of strategies results in a profile of (expected) utility payoffs. A certain payoff allocation, or a profile of final moves of the players is called an outcome of the game. An outcome is called an equilibrium outcome if no player can unilaterally improve the outcome (in terms of his own payoff) given that the other players stick to their equilibrium strategies. A profile of strategies is called a (strategic) equilibrium if, given that all players conform to the prescribed strategies, no player can gain from unilaterally switching to another strategy. Alternatively, a profile of strategies forms an equilibrium if the strategies form best responses to one another. (Unfortunately, it is impossible to describe what is an equilibrium other than in such a self-referential way. The best way to understand this definition is then to take it literally.) Only equilibrium outcomes are reasonable outcomes for games, because outside an equilibrium there is at least one player that can improve by playing according to another strategy. An implicit assumption of game theory is that the players, being rational, are able to reproduce any equilibrium calculations of anybody else. In particular, all the equilibrium strategies must be known to (as they are computed by) the players. Similarly, it is assumed that the whole structure of the game, in much the same way as the players' social context, is known by each player (and that this knowledge itself is known etc.)

Normal form vs. extensive form game: In normal (or strategic) form games, the players move (choose their actions) simultaneously. Whenever the strategy spaces of the players are discrete (and finite), the game can be represented compactly as an NxM-game (see below). By contrast, a game in extensive form specifies the complete order of moves (along the direction of time), typically in a game tree (see below), in addition to the complete list of payoffs and the available information at each point in time and under each contingency. As any normal form can be 'inflated' to an extensive form game, concepts of strategic equilibrium in general relate to extensive form games. Whenever the exact timing of actions is irrelevant to the payoffs, however, a game is represented with more parsimony in normal form.

NxM game: A normal form game for two players, where one player has N possible actions and the other one has M possible actions. In such a game, the payoffs pairs to any strategy combination can be neatly arranged in a matrix, and the game is easily analyzable. NxM-games thus provide an easy way to gain an idea of what the structure of a more complex game looks like.

Prisoners' dilemma: Consider the following story. Two suspects in a crime are put into separate cells. If they both confess, each will be sentenced to three years. If only one of them confesses, he will be freed and used to witness against the other, who will receive a sentence of ten years. If neither confesses, they will both convicted of a minor offense and spend just a year in prison. This game is easily put in matrix form as a 2x2 game (see above). Once this is done, it is pretty obvious that each prisoner (player) has a dominant strategy to confess. The unique equilibrium of this game thus leads to the (Pareto) inefficient outcome (efficiency). This provides the most famous example that strategic equilibrium typically implies inefficient outcomes, and even can lead to the worst possible outcome (any other outcome is pareto-dominating the equilibrium outcome.) The prisoners' dilemma game illustrates the structure of interaction in an oil cartel, or any oligolistic industry of quantity competition, where each firm has an incentive to 'spoil' the market by unilaterally increasing its own output. The same structure of interaction characterizes the problem of providing public goods (free rider problem), i.e. of voluntarily paying taxes.

Matching pennies: Extremely simplistic, symmetric, two player 2x2 game (which is said to be played by children), in which each player chooses either Head or Tail. If the choices differ, player 1 pays a dollar to player 2; if they are the same, player 2 pays player 1 a dollar. This game does not have an equilibrium in pure strategies, but the unique equilibrium involves each player selecting one of the two actions with equal probability. The game illustrates that interactively optimizing behavior may create the need to take actions randomly, in order not to be predictable by the opponent. For the exact determination of mixed equilibrium strategies, the assumption of expected utility is important. For a real-world situation closely resembling this game, think of penalty shooting in sports: both the goal-keeper and the player who shoots the ball play randomized strategies. They randomize their actions (left or right, upper corner or not) in a way such that the other player cannot improve by either action he takes, given the own probabilities of selecting the actions.

Constant-sum games: Games in which for every combination of strategies the sum of players' payoff is the same. For example, auction games for risk neutral bidders and a risk-neutral seller are constant-sum games, where a fixed social surplus from exchange is to be divided between the bidders and the bid-taker. More generally, all exchange situations which do neither allow for production nor for destruction of resources are constant-sum games.

Coordination games: Normal form game where the players have the same number of strategies, which can be indexed such that it is always a strict Nash equilibrium for both players to play strategies having the same index.

Game tree: Time structure of possible moves describing an extensive form game. A game tree is a set of nodes some which are linked by edges. A tree is a connected graph with no cycles. The first move of the game is identified with a distinguished node that is called the root of the tree. A play of the game consists of a connected chain of edges starting at the root of the tree and ending, if the game is finite, at a terminal node. The nodes in the tree represent the possible moves in the game. The edges leading away from a node represent the choices or actions available at that move. Each node other than the terminal node is assigned a player's name so that it is known who makes the choice at that move. Each terminal node must be labeled with the consequences for each player if the game ends in the outcome corresponding to that terminal node.

Repeated game: 'Super'-game where a fixed group of players plays a given game repeatedly, with the outcome of all previous plays observed before the next play begins. Repetition vastly enlargens the set of possible equilibrium outcomes in a game, as it opens possibilities to 'punish' or 'reward' later actions such that certain strategies form an equilibrium which would not form one in the single, unrepeated ('one-shot') game. For example, repeating the prisoners' dilemma game (often enough) gives rise to many equilibria where both prisoners never confess.

Literature: Binmore (1992), Fudenberg & Tirole (1992), Gibbons (1992), Osborne & Rubinstein (1994)

Entry by: Aner Sela and Jan Vleugels

December 1, 1997 Direct questions and comments to: Glossary master