HOME

TheInfoList



OR:

In
game theory Game theory is the study of mathematical models of strategic interactions. It has applications in many fields of social science, and is used extensively in economics, logic, systems science and computer science. Initially, game theory addressed ...
, the centipede game, first introduced by Robert Rosenthal in 1981, is an
extensive form game In game theory, an extensive-form game is a specification of a game allowing for the explicit representation of a number of key aspects, like the sequencing of players' possible moves, their choices at every decision point, the (possibly imperfec ...
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, but after an additional switch the potential payoff will be higher. Therefore, although at each round a player has an incentive to take the pot, it would be better for them to wait. Although the traditional centipede game had a limit of 100 rounds (hence the name), any game with this structure but a different number of rounds is also called a centipede game. The unique
subgame perfect equilibrium In game theory, a subgame perfect equilibrium (SPE), or subgame perfect Nash equilibrium (SPNE), is a refinement of the Nash equilibrium concept, specifically designed for dynamic games where players make sequential decisions. A strategy profil ...
(and every
Nash equilibrium In game theory, the Nash equilibrium is the most commonly used solution concept for non-cooperative games. A Nash equilibrium is a situation where no player could gain by changing their own strategy (holding all other players' strategies fixed) ...
) of these games results in the first player taking the pot on the first round of the game; however, in
empirical Empirical evidence is evidence obtained through sense experience or experimental procedure. It is of central importance to the sciences and plays a role in various other fields, like epistemology and law. There is no general agreement on how t ...
tests, relatively few players do so, and as a result, achieve a higher payoff than in the subgame perfect and Nash equilibria. These results are taken to show that subgame perfect equilibria and Nash equilibria fail to predict human play in some circumstances. The Centipede game is commonly used in introductory game theory courses and texts to highlight the concept of
backward induction Backward induction is the process of determining a sequence of optimal choices by reasoning from the endpoint of a problem or situation back to its beginning using individual events or actions. Backward induction involves examining the final point ...
and the iterated elimination of dominated strategies, which show a standard way of providing a solution to the game.


Play

One possible version of a centipede game could be played as follows: The addition of coins is taken to be an
externality In economics, an externality is an Indirect costs, indirect cost (external cost) or indirect benefit (external benefit) to an uninvolved third party that arises as an effect of another party's (or parties') activity. Externalities can be conside ...
, as it is not contributed by either player.


Formal definition

The centipede game may be written as \mathcal(N,~m_,~m_) where N, m_, m_\in\mathbb and m_>m_. Players I and II alternate, starting with player I, and may on each turn play a move from \ with a maximum of N rounds. The game terminates when \mathrm is played for the first time, otherwise upon N moves, if \mathrm is never played. Suppose the game ends on round t\in\ with player p\in\ making the final move. Then the outcome of the game at round t is defined as follows: * If p played \mathrm, then p gains 2^m_ coins and p^ gains 2^m_. * If p played \mathrm, then p gains 2^m_ coins and p^ gains 2^m_. Here, p^\in\ denotes the other player.


Equilibrium analysis and backward induction

Standard game theoretic tools predict that the first player will defect on the first round, taking the pile of coins for himself. In the centipede game, a
pure strategy In game theory, a move, action, or play is any one of the options which a player can choose in a setting where the optimal outcome depends ''not only'' on their own actions ''but'' on the actions of others. The discipline mainly concerns the actio ...
consists of a set of actions (one for each choice point in the game, even though some of these choice points may never be reached) and a
mixed strategy In game theory, a move, action, or play is any one of the options which a player can choose in a setting where the optimal outcome depends ''not only'' on their own actions ''but'' on the actions of others. The discipline mainly concerns the actio ...
is a probability distribution over the possible pure strategies. There are several pure strategy
Nash equilibria In game theory, the Nash equilibrium is the most commonly used solution concept for non-cooperative games. A Nash equilibrium is a situation where no player could gain by changing their own strategy (holding all other players' strategies fixed) ...
of the centipede game and infinitely many mixed strategy Nash equilibria. However, there is only one
subgame perfect equilibrium In game theory, a subgame perfect equilibrium (SPE), or subgame perfect Nash equilibrium (SPNE), is a refinement of the Nash equilibrium concept, specifically designed for dynamic games where players make sequential decisions. A strategy profil ...
(a popular refinement to the Nash equilibrium concept). In the unique subgame perfect equilibrium, each player chooses to defect at every opportunity. This, of course, means defection at the first stage. In the Nash equilibria, however, the actions that would be taken after the initial choice opportunities (even though they are never reached since the first player defects immediately) may be cooperative. Defection by the first player is the unique
subgame perfect equilibrium In game theory, a subgame perfect equilibrium (SPE), or subgame perfect Nash equilibrium (SPNE), is a refinement of the Nash equilibrium concept, specifically designed for dynamic games where players make sequential decisions. A strategy profil ...
and required by any
Nash equilibrium In game theory, the Nash equilibrium is the most commonly used solution concept for non-cooperative games. A Nash equilibrium is a situation where no player could gain by changing their own strategy (holding all other players' strategies fixed) ...
, it can be established by
backward induction Backward induction is the process of determining a sequence of optimal choices by reasoning from the endpoint of a problem or situation back to its beginning using individual events or actions. Backward induction involves examining the final point ...
. Suppose two players reach the final round of the game; the second player will do better by defecting and taking a slightly larger share of the pot. Since we suppose the second player will defect, the first player does better by defecting in the second to last round, taking a slightly higher payoff than she would have received by allowing the second player to defect in the last round. But knowing this, the second player ought to defect in the third to last round, taking a slightly higher payoff than he would have received by allowing the first player to defect in the second to last round. This reasoning proceeds backwards through the
game tree In the context of combinatorial game theory, a game tree is a graph representing all possible game states within a sequential game that has perfect information. Such games include chess, checkers, Go, and tic-tac-toe. A game tree can be us ...
until one concludes that the best action is for the first player to defect in the first round. The same reasoning can apply to any node in the game tree. For a game that ends after four rounds, this reasoning proceeds as follows. If we were to reach the last round of the game, Player ''2'' would do better by choosing ''d'' instead of ''r'', receiving 4 coins instead of 3. However, given that ''2'' will choose ''d'', ''1'' should choose ''D'' in the second to last round, receiving 3 instead of 2. Given that ''1'' would choose ''D'' in the second to last round, ''2'' should choose ''d'' in the third to last round, receiving 2 instead of 1. But given this, Player ''1'' should choose ''D'' in the first round, receiving 1 instead of 0. There are a large number of
Nash equilibria In game theory, the Nash equilibrium is the most commonly used solution concept for non-cooperative games. A Nash equilibrium is a situation where no player could gain by changing their own strategy (holding all other players' strategies fixed) ...
in a centipede game, but in each, the first player defects on the first round and the second player defects in the next round frequently enough to dissuade the first player from passing. Being in a Nash equilibrium does not require that strategies be rational at every point in the game as in the subgame perfect equilibrium. This means that strategies that are cooperative in the never-reached later rounds of the game could still be in a Nash equilibrium. In the example above, one Nash equilibrium is for both players to defect on each round (even in the later rounds that are never reached). Another Nash equilibrium is for player 1 to defect on the first round, but pass on the third round and for player 2 to defect at any opportunity.


Empirical results

Several studies have demonstrated that the Nash equilibrium (and likewise, subgame perfect equilibrium) play is rarely observed. Instead, subjects regularly show partial cooperation, playing "R" (or "r") for several moves before eventually choosing "D" (or "d"). It is also rare for subjects to cooperate through the whole game. For examples see McKelvey and Palfrey (1992), Nagel and Tang (1998) or Krockow et al. (2016) for a survey. Scholars have investigated the effect of increasing the stakes. As with other games, for instance the
ultimatum game The ultimatum game is a popular experimental economics game in which two players interact to decide how to divide a sum of money, first described by Nobel laureate John Harsanyi in 1961. The first player, the proposer, proposes a division of the ...
, as the stakes increase the play approaches (but does not reach) Nash equilibrium play. Since the empirical studies have produced results that are inconsistent with the traditional equilibrium analysis, several explanations of this behavior have been offered. To explain the experimental data, we either need some altruistic agents or some bounded rational agents.


Preference-based explanation

One reason people may deviate from equilibrium behavior is if some are
altruistic Altruism is the concern for the well-being of others, independently of personal benefit or reciprocity. The word ''altruism'' was popularised (and possibly coined) by the French philosopher Auguste Comte in French, as , for an antonym of egoi ...
. The basic idea is that you have a certain probability at each game to play against an altruistic agent and if this probability is high enough, you should defect on the last round rather than the first. If enough people are altruists, sacrificing the payoff of first-round defection is worth the price in order to determine whether or not your opponent is an altruist. McKelvey and Palfrey (1992) create a model with some altruistic agents and some rational agents who will end up playing a mixed strategy (i.e. they play at multiple nodes with some probability). To match well the experimental data, around 5% of the players need to be altruistic in the model. Elmshauser (2022) shows that a model including altruistic agents and uncertainty-averse agents (instead of rational agents) explain even better the experimental data. Some experiments tried to see whether players who passing a lot would also be the most altruistic agents in other games or other life situations (see for instance Pulford et al or Gamba and Regner (2019) who assessed Social Value Orientation). Players passing a lot were indeed more altruistic but the difference wasn't huge.


Bounded rationality explanation

Rosenthal (1981) suggested that if one has reason to believe his opponent will deviate from Nash behavior, then it may be advantageous to not defect on the first round. Another possibility involves error. If there is a significant possibility of error in action, perhaps because your opponent has not reasoned completely through the backward induction, it may be advantageous (and rational) to cooperate in the initial rounds. The quantal response equilibrium of McKelvey and Palfrey (1995) created a model with agents playing
Nash equilibrium In game theory, the Nash equilibrium is the most commonly used solution concept for non-cooperative games. A Nash equilibrium is a situation where no player could gain by changing their own strategy (holding all other players' strategies fixed) ...
with errors and they applied it to the Centipede game. Another modelling able to explain behaviors in the centipede game is the level-k model, which is a cognitive hierarchy theory : a L0 player plays randomly, the L1 player best responds to the L0 player, the L2 player best responds to the L1 player and so on. In many games, scholars observed that most of the player were L2 or L3 players, which is consistent with the centipede game experimental data. Garcia-Pola et al. (2020) concluded from an experiment that most of the players either play following a Level-k logic or a Quantal response logic. However, Parco, Rapoport and Stein (2002) illustrated that the level of financial incentives can have a profound effect on the outcome in a three-player game: the larger the incentives are for deviation, the greater propensity for learning behavior in a repeated single-play experimental design to move toward the Nash equilibrium. Palacios-Huerta and Volij (2009) find that expert
chess Chess is a board game for two players. It is an abstract strategy game that involves Perfect information, no hidden information and no elements of game of chance, chance. It is played on a square chessboard, board consisting of 64 squares arran ...
players play differently from college students. With a rising Elo, the probability of continuing the game declines; all Grandmasters in the experiment stopped at their first chance. They conclude that chess players are familiar with using backward induction reasoning and hence need less learning to reach the equilibrium. However, in an attempt to replicate these findings, Levitt, List, and Sadoff (2010) find strongly contradictory results, with zero of sixteen Grandmasters stopping the game at the first node. Qualitative research by Krockow et al., which employed think-aloud protocols that required players in a Centipede game to vocalise their reasoning during the game, indicated a range of decision biases such as
action bias Action bias is the psychological phenomenon where people tend to favor action over inaction, even when there is no indication that doing so would point towards a better result. It is an automatic response, similar to a reflex or an impulse and i ...
or completion bias, which may drive irrational choices in the game.


Significance

Like the
prisoner's dilemma The prisoner's dilemma is a game theory thought experiment involving two rational agents, each of whom can either cooperate for mutual benefit or betray their partner ("defect") for individual gain. The dilemma arises from the fact that while def ...
, this game presents a conflict between self-interest and mutual benefit. If it could be enforced, both players would prefer that they both cooperate throughout the entire game. However, a player's self-interest or players' distrust can interfere and create a situation where both do worse than if they had blindly cooperated. Although the Prisoner's Dilemma has received substantial attention for this fact, the Centipede Game has received relatively less. Additionally, Binmore (2005) has argued that some real-world situations can be described by the Centipede game. One example he presents is the exchange of goods between parties that distrust each other. Another example Binmore (2005) likens to the Centipede game is the mating behavior of a hermaphroditic sea bass which takes turns exchanging eggs to fertilize. In these cases, we find cooperation to be abundant. Since the payoffs for some amount of cooperation in the Centipede game are so much larger than immediate defection, the "rational" solutions given by
backward induction Backward induction is the process of determining a sequence of optimal choices by reasoning from the endpoint of a problem or situation back to its beginning using individual events or actions. Backward induction involves examining the final point ...
can seem paradoxical. This, coupled with the fact that experimental subjects regularly cooperate in the Centipede game, has prompted debate over the usefulness of the idealizations involved in the backward induction solutions, see Aumann (1995, 1996) and Binmore (1996).


See also

*
Backward induction Backward induction is the process of determining a sequence of optimal choices by reasoning from the endpoint of a problem or situation back to its beginning using individual events or actions. Backward induction involves examining the final point ...
*
Experimental economics Experimental economics is the application of experimental methods to study economic questions. Data collected in experiments are used to estimate effect size, test the validity of economic theories, and illuminate market mechanisms. Economic expe ...
*
Traveler's dilemma In game theory, the traveler's dilemma (sometimes abbreviated TD) 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 highbal ...
*
Unexpected hanging paradox The unexpected hanging paradox or surprise test paradox is a paradox about a person's expectations about the timing of a future event which they are told will occur at an unexpected time. The paradox is variously applied to a prisoner's hanging or ...


References

* * * * * * * * * * *


External links


EconPort article on the Centipede Game
- AMS column about the centipede game
Online experiment in VeconLab
on gametheorygame.nl {{Game theory Non-cooperative games