Markov perfect equilibrium

Last updated
Markov perfect equilibrium
A solution concept in game theory
Relationship
Subset of Subgame perfect equilibrium
Significance
Proposed by Eric Maskin, Jean Tirole
Used for tacit collusion; price wars; oligopolistic competition

A Markov perfect equilibrium is an equilibrium concept in game theory. It is the refinement of the concept of subgame perfect equilibrium to extensive form games for which a pay-off relevant state space can be readily identified. The term appeared in publications starting about 1988 in the work of economists Jean Tirole and Eric Maskin. [1] It has since been used, among else, in the analysis of industrial organization, macroeconomics and political economy.

Contents

Definition

In extensive form games, and specifically in stochastic games, a Markov perfect equilibrium is a set of mixed strategies for each of the players which satisfy the following criteria:

Focus on symmetric equilibria

In symmetric games, when the players have strategy and action sets which are mirror images of one another, often the analysis focuses on symmetric equilibria, where all players play the same mixed strategy. As in the rest of game theory, this is done both because these are easier to find analytically and because they are perceived to be stronger focal points than asymmetric equilibria.

Lack of robustness

Markov perfect equilibria are not stable with respect to small changes in the game itself. A small change in payoffs can cause a large change in the set of Markov perfect equilibria. This is because a state with a tiny effect on payoffs can be used to carry signals, but if its payoff difference from any other state drops to zero, it must be merged with it, eliminating the possibility of using it to carry signals.

Examples

For examples of this equilibrium concept, consider the competition between firms which have invested heavily into fixed costs and are dominant producers in an industry, forming an oligopoly. The players are taken to be committed to levels of production capacity in the short run, and the strategies describe their decisions in setting prices. The firms' objectives are modeled as maximizing the present discounted value of profits. [3]

Airfare game

Often an airplane ticket for a certain route has the same price on either airline A or airline B. Presumably, the two airlines do not have exactly the same costs, nor do they face the same demand function given their varying frequent-flyer programs, the different connections their passengers will make, and so forth. Thus, a realistic general equilibrium model would be unlikely to result in nearly identical prices.

Both airlines have made sunk investments into the equipment, personnel, and legal framework, thus committing to offering service. They are engaged, or trapped, in a strategic game with one another when setting prices.

Consider the following strategy of an airline for setting the ticket price for a certain route. At every price-setting opportunity:

This is a Markov strategy because it does not depend on a history of past observations. It satisfies also the Markov reaction function definition because it does not depend on other information which is irrelevant to revenues and profits.

Assume now that both airlines follow this strategy exactly. Assume further that passengers always choose the cheapest flight and so if the airlines charge different prices, the one charging the higher price gets zero passengers. Then if each airline assumes that the other airline will follow this strategy, there is no higher-payoff alternative strategy for itself, i.e. it is playing a best response to the other airline strategy. If both airlines followed this strategy, it would form a Nash equilibrium in every proper subgame, thus a subgame-perfect Nash equilibrium. [note 1]

A Markov-perfect equilibrium concept has also been used to model aircraft production, as different companies evaluate their future profits and how much they will learn from production experience in light of demand and what others firms might supply. [4]

Discussion

Airlines do not literally or exactly follow these strategies, but the model helps explain the observation that airlines often charge exactly the same price, even though a general equilibrium model specifying non-perfect substitutability would generally not provide such a result. The Markov perfect equilibrium model helps shed light on tacit collusion in an oligopoly setting, and make predictions for cases not observed.

One strength of an explicit game-theoretical framework is that it allows us to make predictions about the behaviors of the airlines if and when the equal-price outcome breaks down, and interpreting and examining these price wars in light of different equilibrium concepts. [5] In contrasting to another equilibrium concept, Maskin and Tirole identify an empirical attribute of such price wars: in a Markov strategy price war, "a firm cuts its price not to punish its competitor, [rather only to] regain market share" whereas in a general repeated game framework a price cut may be a punishment to the other player. The authors claim that the market share justification is closer to the empirical account than the punishment justification, and so the Markov perfect equilibrium concept proves more informative, in this case. [6]

Notes

  1. This kind of extreme simplification is necessary to get through the example but could be relaxed in a more thorough study. A more complete specification of the game, including payoffs, would be necessary to show that these strategies can form a subgame-perfect Nash equilibrium. For illustration let us suppose however that the strategies do form such an equilibrium and therefore that they also constitute a Markov perfect equilibrium.

Related Research Articles

Game theory The study of mathematical models of strategic interaction between rational decision-makers

Game theory is the study of mathematical models of strategic interaction among rational decision-makers. It has applications in all fields of social science, as well as in logic, systems science and computer science. Originally, it addressed zero-sum games, in which each participant's gains or losses are exactly balanced by those of the other participants. Today, game theory applies to a wide range of behavioral relations, and is now an umbrella term for the science of logical decision making in humans, animals, and computers.

In game theory, the Nash equilibrium, named after the mathematician John Forbes Nash Jr., is a proposed solution of a non-cooperative game involving two or more players in which each player is assumed to know the equilibrium strategies of the other players, and no player has anything to gain by changing only their own strategy.

In game theory, the best response is the strategy which produces the most favorable outcome for a player, taking other players' strategies as given. The concept of a best response is central to John Nash's best-known contribution, the Nash equilibrium, the point at which each player in a game has selected the best response to the other players' strategies.

In game theory, the centipede game, first introduced by Robert Rosenthal in 1981, is an extensive form game in which two players take turns choosing either to take a slightly larger share of an increasing pot, or to pass the pot to the other player. The payoffs are arranged so that if one passes the pot to one's opponent and the opponent takes the pot on the next round, one receives slightly less than if one had taken the pot on this round. Although the traditional centipede game had a limit of 100 rounds, any game with this structure but a different number of rounds is called a centipede game.

In game theory, a subgame is any part of a game that meets the following criteria :

  1. It has a single initial node that is the only member of that node's information set.
  2. If a node is contained in the subgame then so are all of its successors.
  3. If a node in a particular information set is in the subgame then all members of that information set belong to the subgame.

In game theory, a player's strategy is any of the options which he or she chooses in a setting where the outcome depends not only on their own actions but on the actions of others. A player's strategy will determine the action which the player will take at any stage of the game.

Solution concept formal rule for predicting how a strategic game will be played

In game theory, a solution concept is a formal rule for predicting how a game will be played. These predictions are called "solutions", and describe which strategies will be adopted by players and, therefore, the result of the game. The most commonly used solution concepts are equilibrium concepts, most famously Nash equilibrium.

In game theory, a Perfect Bayesian Equilibrium (PBE) is an equilibrium concept relevant for dynamic games with incomplete information. It is a refinement of Bayesian Nash equilibrium (BNE). A PBE has two components - strategies and beliefs:

Backward induction is the process of reasoning backwards in time, from the end of a problem or situation, to determine a sequence of optimal actions. It proceeds by first considering the last time a decision might be made and choosing what to do in any situation at that time. Using this information, one can then determine what to do at the second-to-last time of decision. This process continues backwards until one has determined the best action for every possible situation at every point in time. It was first used by Zermelo in 1913, to prove that chess has pure optimal strategies.

In game theory, trembling hand perfect equilibrium is a refinement of Nash equilibrium due to Reinhard Selten. A trembling hand perfect equilibrium is an equilibrium that takes the possibility of off-the-equilibrium play into account by assuming that the players, through a "slip of the hand" or tremble, may choose unintended strategies, albeit with negligible probability.

In game theory, folk theorems are a class of theorems about possible Nash equilibrium payoff profiles in repeated games. The original Folk Theorem concerned the payoffs of all the Nash equilibria of an infinitely repeated game. This result was called the Folk Theorem because it was widely known among game theorists in the 1950s, even though no one had published it. Friedman's (1971) Theorem concerns the payoffs of certain subgame-perfect Nash equilibria (SPE) of an infinitely repeated game, and so strengthens the original Folk Theorem by using a stronger equilibrium concept subgame-perfect Nash equilibria rather than Nash equilibrium.

In game theory, a repeated game is an extensive form game that consists of a number of repetitions of some base game. The stage game is usually one of the well-studied 2-person games. Repeated games capture the idea that a player will have to take into account the impact of his or her current action on the future actions of other players; this impact is sometimes called his or her reputation. Single stage game or single shot game are names for non-repeated games.

An Edgeworth price cycle is cyclical pattern in prices characterized by an initial jump, which is then followed by a slower decline back towards the initial level. The term was introduced by Maskin and Tirole (1988) in a theoretical setting featuring two firms bidding sequentially and where the winner captures the full market.

In game theory, a Manipulated Nash equilibrium or MAPNASH is a refinement of subgame perfect equilibrium used in dynamic games of imperfect information. Informally, a strategy set is a MAPNASH of a game if it would be a subgame perfect equilibrium of the game if the game had perfect information. MAPNASH were first suggested by Amershi, Sadanand, and Sadanand (1988) and has been discussed in several papers since. It is a solution concept based on how players think about other players' thought processes.

In game theory, a subgame perfect equilibrium is a refinement of a Nash equilibrium used in dynamic games. A strategy profile is a subgame perfect equilibrium if it represents a Nash equilibrium of every subgame of the original game. Informally, this means that if the players played any smaller game that consisted of only one part of the larger game, their behavior would represent a Nash equilibrium of that smaller game. Every finite extensive game with perfect recall has a subgame perfect equilibrium.

Risk dominance and payoff dominance are two related refinements of the Nash equilibrium (NE) solution concept in game theory, defined by John Harsanyi and Reinhard Selten. A Nash equilibrium is considered payoff dominant if it is Pareto superior to all other Nash equilibria in the game. When faced with a choice among equilibria, all players would agree on the payoff dominant equilibrium since it offers to each player at least as much payoff as the other Nash equilibria. Conversely, a Nash equilibrium is considered risk dominant if it has the largest basin of attraction. This implies that the more uncertainty players have about the actions of the other player(s), the more likely they will choose the strategy corresponding to it.

In game theory, an epsilon-equilibrium, or near-Nash equilibrium, is a strategy profile that approximately satisfies the condition of Nash equilibrium. In a Nash equilibrium, no player has an incentive to change his behavior. In an approximate Nash equilibrium, this requirement is weakened to allow the possibility that a player may have a small incentive to do something different. This may still be considered an adequate solution concept, assuming for example status quo bias. This solution concept may be preferred to Nash equilibrium due to being easier to compute, or alternatively due to the possibility that in games of more than 2 players, the probabilities involved in an exact Nash equilibrium need not be rational numbers.

Mertens stability is a solution concept used to predict the outcome of a non-cooperative game. A tentative definition of stability was proposed by Elon Kohlberg and Jean-François Mertens for games with finite numbers of players and strategies. Later, Mertens proposed a stronger definition that was elaborated further by Srihari Govindan and Mertens. This solution concept is now called Mertens stability, or just stability.

In microeconomics, the Bertrand–Edgeworth model of price-setting oligopoly looks at what happens when there is a homogeneous product where there is a limit to the output of firms which they are willing and able to sell at a particular price. This differs from the Bertrand competition model where it is assumed that firms are willing and able to meet all demand. The limit to output can be considered as a physical capacity constraint which is the same at all prices, or to vary with price under other assumptions.

The one-shot deviation principle is the principle of optimality of dynamic programming applied to game theory. It says that a strategy profile of a finite extensive-form game is a subgame perfect equilibrium (SPE) if and only if there exist no profitable one-shot deviations for each subgame and every player. In simpler terms, if no player can increase their payoffs by deviating a single decision, or period, from their original strategy, then the strategy that they have chosen is a SPE. As a result, no player can profit from deviating from the strategy for one period and then reverting to the strategy.

References

  1. Tirole (1988) and Maskin and Tirole (1988)
  2. We shall define a Markov Perfect Equilibrium (MPE) to be a subgame perfect equilibrium in which all players use Markov strategies. Eric Maskin and Jean Tirole. 2001. Markov Perfect Equilibrium Archived 2011-10-05 at the Wayback Machine . Journal of Economic Theory 100, 191-219. doi : 10.1006/jeth.2000.2785, available online at http://www.idealibrary.com
  3. Tirole (1988), p. 254
  4. C. Lanier Benkard. 2000. Learning and forgetting: The dynamics of aircraft production. American Economic Review 90:4, 1034–1054. (jstor)
  5. See for example Maskin and Tirole, p.571
  6. Maskin and Tirole, 1988, p.592

Bibliography