Matching pennies

This article is about the two-person game studied in game-theory. For the confidence trick, see coin-matching game. For other variants, see morra (game).

	Heads	Tails
Heads	+1, −1	−1, +1
Tails	−1, +1	+1, −1
Matching pennies

Matching pennies is the name for a simple game used in game theory. It is played between two players, Even and Odd. Each player has a penny and must secretly turn the penny to heads or tails. The players then reveal their choices simultaneously. If the pennies match (both heads or both tails), then Even keeps both pennies, so wins one from Odd (+1 for Even, −1 for Odd). If the pennies do not match (one heads and one tails) Odd keeps both pennies, so receives one from Even (−1 for Even, +1 for Odd).

Theory

Matching Pennies is a zero-sum game, since one player's gain is exactly equal to the other player's loss.

The game can be written in a payoff matrix (pictured right). Each cell of the matrix shows the two players' payoffs, with Even's payoffs listed first.

Matching pennies is used primarily to illustrate the concept of mixed strategies and a mixed strategy Nash equilibrium.^[1]

This game has no pure strategy Nash equilibrium since there is no pure strategy (heads or tails) that is a best response to a best response. In other words, there is no pair of pure strategies such that neither player would want to switch if told what the other would do. Instead, the unique Nash equilibrium of this game is in mixed strategies: each player chooses heads or tails with equal probability.^[2] In this way, each player makes the other indifferent between choosing heads or tails, so neither player has an incentive to try another strategy. The best response functions for mixed strategies are depicted on the figure 1 below:

Figure 1. Best response correspondences for players in the matching pennies game. The leftmost mapping is for the Even player, the middle shows the mapping for the Odd player. The sole Nash equilibrium is shown in the right hand graph. x is a probability of playing heads by Odd player, y is a probability of playing heads by Even. The unique intersection is the only point where the strategy of Even is the best response to the strategy of Odd and vice versa.

When either player plays the equilibrium, everyone's expected payoff is zero.

Variants

	Heads	Tails
Heads	+7, -1	-1, +1
Tails	-1, +1	+1, -1
Matching pennies

Varying the payoffs in the matrix can change the equilibrium point. For example, in the table shown on the right, Even has a chance to win 9 if both he and Odd play Heads. To calculate the equilibrium point in this game, note that a player playing a mixed strategy must be indifferent between his two actions (otherwise he would switch to a pure strategy). This gives us two equations:

For the Even player, the expected payoff when playing Heads is $+7\cdot x-1\cdot (1-x)$ and when playing Tails $-1\cdot x+1\cdot (1-x)$ , and these must be equal, so $x=0.2$ .
For the Odd player, the expected payoff when playing Heads is $+\cdot y-1\cdot (1-y)$ and when playing Tails $-1\cdot y+1\cdot (1-y)$ , and these must be equal, so $y=0.5$ .

Note that $x$ is the Heads-probability of Odd and $y$ is the Heads-probability of Even. So the change in Even's payoff effects Odd's strategy and not his own strategy.

Laboratory experiments

Human players do not always play the equilibrium strategy. Laboratory experiments reveal several factors that make players deviate from the equilibrium strategy, especially if matching pennies is played repeatedly:

Humans are not good at randomizing. They may try to produce "random" sequences by switching their actions from Heads to Tails and vice versa, but they switch their actions too often (due to a gambler's fallacy). This makes it possible for expert players to predict their next actions with more than 50% chance of success. In this way, a positive expected payoff might be attainable.
Humans are trained to detect patterns. They try to detect patterns in the opponent's sequence, even when such patterns do not exist, and adjust their strategy accordingly.^[3]
Humans' behavior is affected by framing effects.^[4] When the Odd player is named "the misleader" and the Even player is named "the guesser", the former focuses on trying to randomize and the latter focuses on trying to detect a pattern, and this increases the chances of success of the guesser. Additionally, the fact that Even wins when there is a match gives him an advantage, since people are better at matching than at mismatching (due to the Stimulus-Response compatibility effect).

Moreover, when the payoff matrix is asymmetric, other factors influence human behavior even when the game is not repeated:

Players tend to increase the probability of playing an action which gives them a higher payoff. E.g, in the payoff matrix above, Even will tend to play more Heads. This is intuitively understandable, but it is not a Nash equilibrium: as explained above, the mixing probability of a player should depend only on the other player's payoff, not his own payoff. This deviation can be explained as a quantal response equilibrium.^[5]^[6] In a quantal-response-equilibrium, the best-response curves are not sharp as in a standard Nash equilibrium. Rather, they change smoothly from the action whose probability is 0 to the action whose probability 1 (in other words, while in a Nash-equilibrium, a player chooses the best response with probability 1 and the worst response with probability 0, in a quantal-response-equilibrium the player chooses the best response with high probability that is smaller than 1 and the worst response with smaller probability that is higher than 0). The equilibrium point is the intersection point of the smoothed curves of the two players, which is different than the Nash-equilibrium point.
The own-payoff effects are mitigated by risk aversion.^[7] Players tend to under-estimate high gains and over-estimate high losses; this moves the quantal-response curves and changes the quantal-response-equilibrium point. This apparently contradicts theoretical results regarding the irrelevance of risk-aversion in finitely-repeated zero-sum games.^[8]

Real-life data

The conclusions of laboratory experiments have been criticized on several grounds.^[9]^[10]

Games in lab experiments are artificial and simplistic, and do not mimic real-life behavior.
The payoffs in lab experiments are small, so subjects do not have much incentive to play optimally. In real-life, the market may "punish" such irrationality and cause players to behave more rationally.
Subjects have other considerations than maximizing monetary payoffs, such as to avoid looking foolish or to please the experimenter.
Lab experiments are short, and subjects do not have sufficient time to learn the optimal strategy.

To overcome these difficulties, several authors have done statistical analysis of professional sports games. These are zero-sum games with very high payoffs, and the players have devoted their lives to become experts. Often such games are strategically similar to matching pennies:

In soccer penalty kicks, the kicker has two options - kick left or kick right, and the goalie has two options - jump left or jump right.^[11] The kicker's probability of scoring a goal is higher when the choices do not match, and lower when the choices match. In general, the payoffs are asymmetric because each kicker has a stronger leg (usually the right leg) and his chances are better when kicking to the opposite direction (left). In a close examination of the actions of kickers and goalies, it was found^[9]^[10] that their actions do not deviate significantly from the prediction of a Nash equilibrium.
In tennis serve-and-return plays, the situation is similar. Here, it was found^[12] that the win rates are consistent with the minimax hypothesis, but, the players' choices are not random: even professional tennis players are not good at randomizing, and switch their actions too often.

References

↑ Gibbons, Robert (1992). Game Theory for Applied Economists. Princeton University Press. pp. 29–33. ISBN 0-691-00395-5.
↑ "Matching Pennies". GameTheory.net.
↑ Mookherjee, Dilip; Sopher, Barry (1994). "Learning Behavior in an Experimental Matching Pennies Game". Games and Economic Behavior. 7: 62. doi:10.1006/game.1994.1037.
↑ Eliaz, Kfir; Rubinstein, Ariel (2011). "Edgar Allan Poe's riddle: Framing effects in repeated matching pennies games". Games and Economic Behavior. 71: 88. doi:10.1016/j.geb.2009.05.010.
↑ Ochs, Jack (1995). "Games with Unique, Mixed Strategy Equilibria: An Experimental Study". Games and Economic Behavior. 10: 202. doi:10.1006/game.1995.1030.
↑ McKelvey, Richard; Palfrey, Thomas (1995). "Quantal Response Equilibria for Normal Form Games". Games and Economic Behavior. 10: 6–38. doi:10.1006/game.1995.1023.
↑ Goeree, Jacob K.; Holt, Charles A.; Palfrey, Thomas R. (2003). "Risk averse behavior in generalized matching pennies games". Games and Economic Behavior. 45: 97. doi:10.1016/s0899-8256(03)00052-6.
↑ Wooders, John; Shachat, Jason M. (2001). "On the Irrelevance of Risk Attitudes in Repeated Two-Outcome Games". Games and Economic Behavior. 34 (2): 342. doi:10.1006/game.2000.0808.
1 2 Chiappori, P.; Levitt, S.; Groseclose, T. (2002). "Testing Mixed-Strategy Equilibria When Players Are Heterogeneous: The Case of Penalty Kicks in Soccer" (PDF). American Economic Review. 92 (4): 1138–1151. doi:10.1257/00028280260344678. JSTOR 3083302.
1 2 Palacios-Huerta, I. (2003). "Professionals Play Minimax". Review of Economic Studies. 70 (2): 395–415. doi:10.1111/1467-937X.00249.
↑ There is also the option of kicking/standing in the middle, but it is less often used.
↑ "Minimax Play at Wimbledon". JSTOR 2677937.

Topics in game theory

Definitions	Normal-form game Extensive-form game Escalation of commitment Graphical game Cooperative game Succinct game Information set Hierarchy of beliefs Preference

Equilibrium concepts	Nash equilibrium Subgame perfection Mertens-stable equilibrium Bayesian Nash equilibrium Perfect Bayesian equilibrium Trembling hand Proper equilibrium Epsilon-equilibrium Correlated equilibrium Sequential equilibrium Quasi-perfect equilibrium Evolutionarily stable strategy Risk dominance Core Shapley value Pareto efficiency Gibbs equilibrium Quantal response equilibrium Self-confirming equilibrium Strong Nash equilibrium Markov perfect equilibrium

Strategies	Dominant strategies Pure strategy Mixed strategy Tit for tat Grim trigger Collusion Backward induction Forward induction Markov strategy

Classes of games	Symmetric game Perfect information Simultaneous game Sequential game Repeated game Signaling game Screening game Cheap talk Zero-sum game Mechanism design Bargaining problem Stochastic game n-player game Large Poisson game Nontransitive game Global games Strictly determined game Potential game

Games	Prisoner's dilemma Traveler's dilemma Coordination game Chicken Centipede game Volunteer's dilemma Dollar auction Battle of the sexes Stag hunt Matching pennies Ultimatum game Rock-paper-scissors Pirate game Dictator game Public goods game Blotto games War of attrition El Farol Bar problem Fair division Fair cake-cutting Cournot game Deadlock Diner's dilemma Guess 2/3 of the average Kuhn poker Nash bargaining game Prisoners and hats puzzle Trust game Princess and monster game Monty Hall problem Rendezvous problem

Theorems	Minimax theorem Nash's theorem Purification theorem Folk theorem Revelation principle Arrow's impossibility theorem

Key figures	Albert W. Tucker Amos Tversky Ariel Rubinstein Daniel Kahneman David K. Levine David M. Kreps Donald B. Gillies Drew Fudenberg Eric Maskin Harold W. Kuhn Herbert Simon Hervé Moulin Jean Tirole Jean-François Mertens John Harsanyi John Maynard Smith John Nash John von Neumann Kenneth Arrow Kenneth Binmore Leonid Hurwicz Lloyd Shapley Melvin Dresher Merrill M. Flood Oskar Morgenstern Paul Milgrom Peyton Young Reinhard Selten Robert Aumann Robert B. Wilson Roger Myerson Samuel Bowles Thomas Schelling William Vickrey

See also	All-pay auction Alpha–beta pruning Bertrand paradox Bounded rationality Combinatorial game theory Confrontation analysis Coopetition List of game theorists List of games in game theory No-win situation Topological game Tragedy of the commons Tyranny of small decisions

This article is issued from Wikipedia - version of the 11/21/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.