Misplaced Pages

#354645

54-488: A common method for determining subgame perfect equilibria in the case of a finite game is backward induction . Here one first considers the last actions of the game and determines which actions the final mover should take in each possible circumstance to maximize his/her utility . One then supposes that the last actor will do these actions, and considers the second to last actions, again choosing those that maximize that actor's utility. This process continues until one reaches

108-404: A salary of $ 100 {\displaystyle \$ 100} or a 'bad' job offering a salary of $ 44 {\displaystyle \$ 44} . Each job type has an equal probability of being offered. Upon accepting a job, the individual will maintain that particular job for the entire remainder of the ten-year duration. This scenario is simplified by assuming that

162-403: A "carrot and stick" structure. One player can use the one stage-game Nash equilibrium to incentivize playing the non-Nash equilibrium action, while using a stage-game Nash equilibrium with lower payoff to the other player if they choose to defect. Reinhard Selten proved that any game which can be broken into "sub-games" containing a sub-set of all the available choices in the main game will have

216-420: A 'bad' offer should only be accepted if the person is still unemployed at t = 9 {\displaystyle t=9} or t = 10 {\displaystyle t=10} ; a bad offer should be rejected at any time up to and including t = 8 {\displaystyle t=8} . Generalizing this example intuitively, it corresponds to the principle that if one expects to work in

270-427: A Nash equilibrium in each decision-making process (subgame) constitutes as perfect subgame equilibria. Thus, these strategy profiles that depict subgame perfect equilibria exclude the possibility of actions like incredible threats that are used to "scare off" an entrant. If the incumbent threatens to start a price war with an entrant, they are threatening to lower their prices from a monopoly price to slightly lower than

324-534: A dollar with Player 2, which Player 2 then accepts or rejects. This is called the ultimatum game . Player 1 acts first by splitting the dollar however they see fit. Next, Player 2 either accepts the portion they have been offered by Player 1 or rejects the split. If Player 2 accepts the split, then both Player 1 and Player 2 get the payoffs matching that split. If Player 2 decides to reject Player 1's offer, then both players get nothing. In other words, Player 2 has veto power over Player 1's proposed allocation, but applying

378-493: A generalized procedure of backward induction produces all subgame perfect equilibria in games that may have infinite length, infinite actions as each information set, and imperfect information if a condition of final support is satisfied. The interesting aspect of the word "credible" in the preceding paragraph is that taken as a whole (disregarding the irreversibility of reaching sub-games) strategies exist which are superior to subgame perfect strategies, but which are not credible in

432-454: A given game tree . It develops the implications of rationality via individual information sets in the extensive-form representation of a game. In order to solve for a subgame perfect equilibrium with backwards induction, the game should be written out in extensive form and then divided into subgames . Starting with the subgame furthest from the initial node, or starting point, the expected payoffs listed for this subgame are weighed, and

486-467: A given game is always a subset of the set of Nash equilibria for that game. In some cases the sets can be identical. The ultimatum game provides an intuitive example of a game with fewer subgame perfect equilibria than Nash equilibria. Determining the subgame perfect equilibrium by using backward induction is shown below in Figure 1. Strategies for Player 1 are given by {Up, Uq, Dp, Dq}, whereas Player 2 has

540-517: A job for a long time, it is worth picking carefully. A dynamic optimization problem of this kind is called an optimal stopping problem because the issue at hand is when to stop waiting for a better offer. Search theory is a field of microeconomics that applies models of this type to matters such as shopping, job searches, and marriage. In game theory , backward induction is a solution methodology that follows from applying sequential rationality to identify an optimal action for each information set in

594-517: A proposer, Player 1, very rarely offers $ 0 and the responder, Player 2, sometimes rejects offers greater than $ 0. What is deemed acceptable by Player 2 varies with context. The pressure or presence of other players and external implications can mean that the game's formal model cannot necessarily predict what a real person will choose. According to Colin Camerer , an American behavioral economist, Player 2 "rejects offers of less than 20 percent of X about half

SECTION 10

#1732855734355

648-495: A range and sum their choices until a target number is reached. Hitting the target earns that player a prize; the other loses. Partway through a series of games, a small prize was introduced. The majority of players then performed limited backward induction, as they solved for the small prize rather than for the original prize. Only a small fraction of players considered both prizes at the start. Most tests of backward induction are based on experiments, in which participants are only to

702-399: A rational player will select the option with the higher payoff for themselves. The highest payoff vector is selected and marked. To solve for the subgame perfect equilibrium, one should continually work backwards from subgame to subgame until the starting point is reached. As this process progresses, the initial extensive form game will become shorter and shorter. The marked path of vectors is

756-446: A series of decisions and identifying the optimal process or action required to arrive at that point. This process continues backward until the best action for every possible point along the sequence is determined. Backward induction was first utilized in 1875 by Arthur Cayley , who discovered the method while attempting to solve the secretary problem . In dynamic programming , a method of mathematical optimization , backward induction

810-401: A situation that contains two guilty culprits. When they are interrogated, they have the option to stay quiet or defect. If both culprits stay quiet, they both serve a short sentence. If both defect, they both serve a moderate sentence. If they choose opposite options, then the culprit that defects is free and the culprit who stays quiet serves a long sentence. Ultimately, using backward induction,

864-516: A small extent incentivized to perform the task well, if at all. However, violations of backward induction also appear to be common in high-stakes environments. A large-scale analysis of the American television game show The Price Is Right , for example, provides evidence of limited foresight. In every episode, contestants play the Showcase Showdown , a sequential game of perfect information for which

918-416: A subgame perfect Nash Equilibrium strategy (possibly as a mixed strategy giving non-deterministic sub-game decisions). Subgame perfection is only used with games of complete information . Subgame perfection can be used with extensive form games of complete but imperfect information . The subgame-perfect Nash equilibrium is normally deduced by " backward induction " from the various ultimate outcomes of

972-573: A thesis on the evaluation of n-person games. He was a visiting professor at Berkeley and taught from 1969 to 1972 at the Free University of Berlin and, from 1972 to 1984, at the University of Bielefeld . He then accepted a professorship at the University of Bonn . There he built the BonnEconLab, a laboratory for experimental economic research, where he was active even after his retirement. Selten

1026-621: Is a perfect information game. The normal-form matrices for these games are: The extensive form of this multi-stage game can be seen to the right. The steps for solving this game with backward induction are as follows: Backward induction can be applied to only limited classes of games. The procedure is well-defined for any game of perfect information with no ties of utility. It is also well-defined and meaningful for games of perfect information with ties. However, in such cases it leads to more than one perfect strategy. The procedure can be applied to some games with nontrivial information sets, but it

1080-512: Is a deviation from fully rational backward induction. It involves enacting the regular process of backward induction without perfect foresight. Theoretically, this occurs when one or more players have limited foresight and cannot perform backward induction through all terminal nodes. Limited backward induction plays a much larger role in longer games as the effects of limited backward induction are more potent in later periods of games. Experiments have shown that in sequential bargaining games, such as

1134-443: Is a subgame. Player 2's nodes are not a subgame as they are part of the same information set. The first normal-form game is the normal form representation of the whole extensive-form game. Based on the provided information, (UA, X), (DA, Y), and (DB, Y) are all Nash equilibria for the entire game. The second normal-form game is the normal form representation of the subgame starting from Player 1's second node with actions A and B. For

SECTION 20

#1732855734355

1188-489: Is not applicable in general. It is best suited to solve games with perfect information. If all players are not aware of the other players' actions and payoffs at each decision node, then backward induction is not so easily applied. A second example demonstrates that even in games that formally allow for backward induction in theory, it may not accurately predict empirical game play in practice. This example of an asymmetric game consists of two players: Player 1 proposes to split

1242-473: Is predominantly attributed to the presence of social factors. However, data-driven model predictions for sequential bargaining games (using the cognitive hierarchy model ) have highlighted that in some games the presence of limited backward induction can play a dominant role. Within repeated public goods games, team behavior is impacted by limited backward induction; where it is evident that team members' initial contributions are higher than contributions towards

1296-581: Is used for solving the Bellman equation . In the related fields of automated planning and scheduling and automated theorem proving , the method is called backward search or backward chaining . In chess, it is called retrograde analysis . In game theory , a variant of backward induction is used to compute subgame perfect equilibria in sequential games . The difference is that optimization problems involve one decision maker who chooses what to do at each point of time. In contrast, game theory problems involve

1350-500: The Centipede game , subjects deviate from theoretical predictions and instead engage in limited backward induction. This deviation occurs as a result of bounded rationality , where players can only perfectly see a few stages ahead. This allows for unpredictability in decisions and inefficiency in finding and achieving subgame perfect Nash equilibria . There are three broad hypotheses for this phenomenon: Violations of backward induction

1404-514: The 1994 Nobel Memorial Prize in Economic Sciences (shared with John Harsanyi and John Nash ). Selten was Germany's first and, at the time of his death, only Nobel winner for economics. He is also well known for his work in bounded rationality , and can be considered one of the founding fathers of experimental economics . With Gerd Gigerenzer he edited the book Bounded Rationality: The Adaptive Toolbox (2001). He developed an example of

1458-468: The Nash Equilibria by mutual best response of Subgame 1. Then use backwards induction and plug in (A,X) → (3,4) so that (3,4) become the payoffs for Subgame 2. The dashed line indicates that player 2 does not know whether player 1 will play A or B in a simultaneous game. Player 1 chooses U rather than D because 3 > 2 for Player 1's payoff. The resulting equilibrium is (A, X) → (3,4). Thus,

1512-419: The book which established game theory as a field of study. Consider a person evaluating potential employment opportunities for the next ten years, denoted as times t = 1 , 2 , 3 , . . . , 10 {\displaystyle t=1,2,3,...,10} . At each t {\displaystyle t} , they may encounter a choice between two job options: a 'good' job offering

1566-450: The end. Limited backward induction also influences how regularly free-riding occurs within a team's public goods game. Early on, when the effects of limited backward induction are low, free riding is less frequent, whilst towards the end, when effects are high, free-riding becomes more frequent. Limited backward induction has also been tested for within a variant of the race game. In the game, players would sequentially choose integers inside

1620-498: The entrant does not enter, it does not matter what the incumbent chooses to do in the hypothetical case that the entrant does enter. Hence the strategy profile in which the incumbent fights if the entrant enters, but the entrant does not enter is also a Nash equilibrium. However, were the entrant to deviate and enter, the incumbent's best response is to accommodate—the threat of fighting is not credible. This second Nash equilibrium can therefore be eliminated by backward induction. Finding

1674-425: The entrant enters, the incumbent can "fight" or "accommodate" the entrant. It will fight by lowering its price, running the entrant out of business (and incurring exit costs—a negative payoff) and damaging its own profits. If it accommodates the entrant it will lose some of its sales, but a high price will be maintained and it will receive greater profits than by lowering its price (but lower than monopoly profits). If

Subgame perfect equilibrium - Misplaced Pages Continue

1728-490: The entrant will not be convinced of the incumbent's threat knowing that it was not a best response in the strategy profile. The unexpected hanging paradox is a paradox related to backward induction. The prisoner described in the paradox uses backwards induction to reach a false conclusion. The description of the problem assumes it is possible to surprise someone who is performing backward induction. The mathematical theory of backward induction does not make this assumption, so

1782-469: The entrant's, which would be impractical, and incredible, if the entrant knew a price war would not actually happen since it would result in losses for both parties. Unlike a single-agent optimization which might include suboptimal or infeasible equilibria, a subgame perfect equilibrium accounts for the actions of another player, ensuring that no player reaches a subgame mistakenly. In this case, backwards induction yielding perfect subgame equilibria ensures that

1836-465: The first move of the game. The strategies which remain are the set of all subgame perfect equilibria for finite-horizon extensive games of perfect information. However, backward induction cannot be applied to games of imperfect or incomplete information because this entails cutting through non-singleton information sets . A subgame perfect equilibrium necessarily satisfies the one-shot deviation principle . The set of subgame perfect equilibria for

1890-399: The game (making his opponent swerve away), and the opponent's threat to suicidally follow suit is not credible. 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 in

1944-426: The game, eliminating branches which would involve any player making a move that is not credible (because it is not optimal) from that node . One game in which the backward induction solution is well known is tic-tac-toe , but in theory even Go has such an optimum strategy for all players. The problem of the relationship between subgame perfection and backward induction was settled by Kaminski (2019), who proved that

1998-402: The incumbent accommodates given the case that the entrant enters, the best response for the entrant is to enter (and gain profit). Hence the strategy profile in which the entrant enters and the incumbent accommodates if the entrant enters is a Nash equilibrium consistent with backward induction. However, if the incumbent is going to fight, the best response for the entrant is to not enter, and if

2052-496: The individual's entire concern is their total expected monetary earnings, without any variable preferences for earnings across different periods. In economic terms, this is a scenario with an implicit interest rate of zero and a constant marginal utility of money. Whether the person in question should accept a 'bad' job can be decided by reasoning backwards from time t = 10 {\displaystyle t=10} . By continuing to work backwards, it can be verified that

2106-572: The interacting decision of several players . In this situation, it may still be possible to apply a generalization of backward induction, since it may be possible to determine what the second-to-last player will do by predicting what the last player will do in each situation, and so on. This variant of backward induction has been used to solve formal games from the beginning of game theory. John von Neumann and Oskar Morgenstern suggested solving zero-sum , two-person formal games through this method in their Theory of Games and Economic Behaviour (1944),

2160-491: The last subgame in a finitely repeated Prisoner's dilemma requires players to play the unique Nash equilibrium (both players defecting). Because of this, all games prior to the last subgame will also play the Nash equilibrium to maximize their single-period payoffs. If a stage-game in a finitely repeated game has multiple Nash equilibria, subgame perfect equilibria can be constructed to play non-stage-game Nash equilibrium actions, through

2214-420: The optimal strategy can be found through backward induction. The frequent and systematic deviations from optimal behavior suggest that a sizable proportion of the contestants fail to properly backward induct and myopically consider the next stage of the game only. Reinhard Selten Reinhard Justus Reginald Selten ( German: [ˈʁaɪnhaʁt ˈzɛltn̩] ; 5 October 1930 – 23 August 2016)

Subgame perfect equilibrium - Misplaced Pages Continue

2268-525: The paradox does not call into question the results of this theory. Backward induction works only if both players are rational , i.e., always select an action that maximizes their payoff. However, rationality is not enough: each player should also believe that all other players are rational. Even this is not enough: each player should believe that all other players know that all other players are rational, and so on, ad infinitum. In other words, rationality should be common knowledge . Limited backward induction

2322-406: The players are an incumbent firm in an industry and a potential entrant to that industry is to be considered. As it stands, the incumbent has a monopoly over the industry and does not want to lose some of its market share to the entrant. If the entrant chooses not to enter, the payoff to the incumbent is high (it maintains its monopoly) and the entrant neither loses nor gains (its payoff is zero). If

2376-403: The second normal-form game, the Nash equilibrium of the subgame is (A, X). For the entire game Nash equilibria (DA, Y) and (DB, Y) are not subgame perfect equilibria because the move of Player 2 does not constitute a Nash equilibrium. The Nash equilibrium (UA, X) is subgame perfect because it incorporates the subgame Nash equilibrium (A, X) as part of its strategy. To solve this game, first find

2430-428: The sense that a threat to carry them out will harm the player making the threat and prevent that combination of strategies. For instance in the game of " chicken " if one player has the option of ripping the steering wheel from their car they should always take it because it leads to a "sub game" in which their rational opponent is precluded from doing the same thing (and killing them both). The wheel-ripper will always win

2484-498: The smallest unit of money and keeping the rest for themselves is the unique subgame-perfect equilibrium. The ultimatum game does have several other Nash Equilibria which are not subgame perfect and therefore do not arise via backward induction. The ultimatum game is a theoretical illustration of the usefulness of backward induction when considering infinite games, but the ultimatum games theoretically predicted results do not match empirical observation. Experimental evidence has shown that

2538-436: The strategies among {TL, TR, BL, BR}. There are 4 subgames in this example, with 3 proper subgames. Using the backward induction, the players will take the following actions for each subgame: Thus, the subgame perfect equilibrium is {Dp, TL} with the payoff (3, 3). An extensive-form game with incomplete information is presented below in Figure 2. Note that the node for Player 1 with actions A and B, and all succeeding actions

2592-416: The subgame perfect equilibrium through backwards induction is (UA, X) with the payoff (3, 4). For finitely repeated games, if a stage game has only one unique Nash equilibrium, the subgame perfect equilibrium is to play without considering past actions, treating the current subgame as a one-shot game. An example of this is a finitely repeated Prisoner's dilemma game. The Prisoner's dilemma gets its name from

2646-424: The subgame perfect equilibrium. The application of backward induction in game theory can be demonstrated with a simple example. Consider a multi-stage game involving two players planning to go to a movie. Once they both observe the choices, the second stage begins. In the second stage, players choose whether to go to the movie or stay home. For this example, payoffs are added across different stages. The game

2700-434: The time, even though they end up with nothing." While backward induction assuming formal rationality would predict that a responder would accept any offer greater than zero, responders in reality are not formally rational players and therefore often seem to care more about offer 'fairness' or perhaps other anticipations of indirect or external effects rather than immediate potential monetary gains. A dynamic game in which

2754-421: The veto eliminates any reward for both players. Considering the choice and response of Player 2 given any arbitrary proposal by Player 1, formal rationality prescribes that Player 2 would accept any payoff that is greater than or equal to $ 0. Accordingly, by backward induction Player 1 ought to propose giving Player 2 as little as possible in order to gain the largest portion of the split. Player 1 giving Player 2

SECTION 50

#1732855734355

2808-676: Was a German economist , who won the 1994 Nobel Memorial Prize in Economic Sciences (shared with John Harsanyi and John Nash ). He is also well known for his work in bounded rationality and can be considered one of the founding fathers of experimental economics . Selten was born in Breslau (Wrocław) in Lower Silesia , now in Poland , to a Jewish father, Adolf Selten (a blind bookseller; d. 1942 ), and Protestant mother, Käthe Luther. Reinhard Selten

2862-619: Was professor emeritus at the University of Bonn , Germany, and held several honorary doctoral degrees. He had been an Esperantist since 1959 and met his wife through the Esperanto movement. He was a member and co-founder of the International Academy of Sciences San Marino . For the 2009 European Parliament election , he was the top candidate for the German wing of Europe – Democracy – Esperanto . For his work in game theory , Selten won

2916-916: Was raised as Protestant. After a brief family exile in Saxony and Austria, Selten returned to Hesse, Germany, after the war and, in high school, read an article in Fortune magazine about game theory by the business writer John D. McDonald . He recalled later, he would occupy his "mind with problems of elementary geometry and algebra" while walking back and forth to school during that time. He studied mathematics at Goethe University Frankfurt and obtained his diploma in 1957. He then worked as scientific assistant to Heinz Sauermann until 1967. In 1959, he married with Elisabeth Langreiner. They had no children. In 1961, he also received his doctorate in Frankfurt in mathematics with

#354645