# Matching pennies

Last updated
 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 because each participant's gain or loss of utility is exactly balanced by the losses or gains of the utility of the other participants. If the participants' total gains are added up and their total losses subtracted, the sum will be zero.

The game can be written in a payoff matrix (pictured right - from Even's point of view). 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 in Figure 1 below:

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 7 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 ${\displaystyle +7\cdot x-1\cdot (1-x)}$ and when playing Tails ${\displaystyle -1\cdot x+1\cdot (1-x)}$, and these must be equal, so ${\displaystyle x=0.2}$.
• For the Odd player, the expected payoff when playing Heads is ${\displaystyle +1\cdot y-1\cdot (1-y)}$ and when playing Tails ${\displaystyle -1\cdot y+1\cdot (1-y)}$, and these must be equal, so ${\displaystyle y=0.5}$.

Note that ${\displaystyle x}$ is the Heads-probability of Odd and ${\displaystyle y}$ is the Heads-probability of Even. So the change in Even's payoff affects 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 underestimate high gains and overestimate 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. 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.

• Odds and evens - a game with the same strategic structure, that is played with fingers instead of coins.
• Rock paper scissors - a similar game in which each player has three strategies instead of two.
• Parity game - an unrelated (and much more complicated) two-player logic game, played on a colored graph.

## Related Research Articles

In game theory and economic theory, a zero-sum game is a mathematical representation of a situation in which each participant's gain or loss of utility is exactly balanced by the losses or gains of the utility of the other participants. If the total gains of the participants are added up and the total losses are subtracted, they will sum to zero. Thus, cutting a cake, where taking a larger piece reduces the amount of cake available for others as much as it increases the amount available for that taker, is a zero-sum game if all participants value each unit of cake equally.

The prisoner's dilemma is a standard example of a game analyzed in game theory that shows why two completely rational individuals might not cooperate, even if it appears that it is in their best interests to do so. It was originally framed by Merrill Flood and Melvin Dresher while working at RAND in 1950. Albert W. Tucker formalized the game with prison sentence rewards and named it "prisoner's dilemma", presenting it as follows:

Two members of a criminal gang are arrested and imprisoned. Each prisoner is in solitary confinement with no means of communicating with the other. The prosecutors lack sufficient evidence to convict the pair on the principal charge, but they have enough to convict both on a lesser charge. Simultaneously, the prosecutors offer each prisoner a bargain. Each prisoner is given the opportunity either to betray the other by testifying that the other committed the crime, or to cooperate with the other by remaining silent. The possible outcomes are:

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, 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.

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:

In game theory, a Bayesian game is a game in which players have incomplete information about the other players. For example, a player may not know the exact payoff functions of the other players, but instead have beliefs about these payoff functions. These beliefs are represented by a probability distribution over the possible payoff functions.

In game theory, rationalizability is a solution concept. The general idea is to provide the weakest constraints on players while still requiring that players are rational and this rationality is common knowledge among the players. It is more permissive than Nash equilibrium. Both require that players respond optimally to some belief about their opponents' actions, but Nash equilibrium requires that these beliefs be correct while rationalizability does not. Rationalizability was first defined, independently, by Bernheim (1984) and Pearce (1984).

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 describing an abundance of 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 equilibria.

In game theory, a correlated equilibrium is a solution concept that is more general than the well known Nash equilibrium. It was first discussed by mathematician Robert Aumann in 1974. The idea is that each player chooses their action according to their observation of the value of the same public signal. A strategy assigns an action to every possible observation a player can make. If no player would want to deviate from the recommended strategy, the distribution is called a correlated equilibrium.

Quantal response equilibrium (QRE) is a solution concept in game theory. First introduced by Richard McKelvey and Thomas Palfrey, it provides an equilibrium notion with bounded rationality. QRE is not an equilibrium refinement, and it can give significantly different results from Nash equilibrium. QRE is only defined for games with discrete strategies, although there are continuous-strategy analogues.

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.

Proper equilibrium is a refinement of Nash Equilibrium due to Roger B. Myerson. Proper equilibrium further refines Reinhard Selten's notion of a trembling hand perfect equilibrium by assuming that more costly trembles are made with significantly smaller probability than less costly ones.

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.

In game theory, the traveler's dilemma is a non-zero-sum game in which each player proposes a payoff. The lower of the two proposals wins; the lowball player receives the lowball payoff plus a small bonus, and the highball player receives the same lowball payoff, minus a small penalty. Surprisingly, the Nash equilibrium is for both players to aggressively lowball. The traveler's dilemma is notable in that naive play appears to outperform the Nash equilibrium; this apparent paradox also appears in the centipede game and the finitely-iterated prisoner's dilemma.

Quantum pseudo-telepathy is the fact that in certain Bayesian games with asymmetric information, players who have access to a shared physical system in an entangled quantum state, and who are able to execute strategies that are contingent upon measurements performed on the entangled physical system, are able to achieve higher expected payoffs in equilibrium than can be achieved in any mixed-strategy Nash equilibrium of the same game by players without access to the entangled quantum system.

In game theory a Poisson game is a game with a random number of players, where the distribution of the number of players follows a Poisson random process. An extension of games of imperfect information, Poisson games have mostly seen application to models of voting.

M equilibrium is a set valued solution concept in game theory that relaxes the rational choice assumptions of perfect maximization and perfect beliefs. The concept can be applied to any normal-form game with finite and discrete strategies. M equilibrium was first introduced by Jacob K. Goeree and Philippos Louis.

## References

1. Gibbons, Robert (1992). Game Theory for Applied Economists. Princeton University Press. pp. 29–33. ISBN   978-0-691-00395-5.
2. "Matching Pennies". GameTheory.net. Archived from the original on 2006-10-01.
3. Mookherjee, Dilip; Sopher, Barry (1994). "Learning Behavior in an Experimental Matching Pennies Game". Games and Economic Behavior. 7: 62–91. doi:10.1006/game.1994.1037.
4. Eliaz, Kfir; Rubinstein, Ariel (2011). "Edgar Allan Poe's riddle: Framing effects in repeated matching pennies games". Games and Economic Behavior. 71: 88–99. doi:10.1016/j.geb.2009.05.010.
5. Ochs, Jack (1995). "Games with Unique, Mixed Strategy Equilibria: An Experimental Study". Games and Economic Behavior. 10: 202–217. doi:10.1006/game.1995.1030.
6. McKelvey, Richard; Palfrey, Thomas (1995). "Quantal Response Equilibria for Normal Form Games". Games and Economic Behavior. 10: 6–38. CiteSeerX  . doi:10.1006/game.1995.1023.
7. Goeree, Jacob K.; Holt, Charles A.; Palfrey, Thomas R. (2003). "Risk averse behavior in generalized matching pennies games" (PDF). Games and Economic Behavior. 45: 97–113. doi:10.1016/s0899-8256(03)00052-6.
8. 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. S2CID   2401322.
9. 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. CiteSeerX  . doi:10.1257/00028280260344678. JSTOR   3083302.
10. Palacios-Huerta, I. (2003). "Professionals Play Minimax". Review of Economic Studies . 70 (2): 395–415. CiteSeerX  . doi:10.1111/1467-937X.00249.
11. There is also the option of kicking/standing in the middle, but it is less often used.
12. Walker, Mark; Wooders, John (2001). "Minimax Play at Wimbledon". The American Economic Review. 91 (5): 1521–1538. CiteSeerX  . doi:10.1257/aer.91.5.1521. JSTOR   2677937.