1416:
1205:
1308:. 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 the veto eliminates any reward for both players.
1364:
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 the entrant will not be convinced of the incumbent's threat knowing that it was not a best response in the strategy profile.
1346:"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).
96:. 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.
1399:, 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
1355:
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.
1289:
strategy. The procedure can be applied to some games with nontrivial information sets, but it 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.
1476:, a sequential game of perfect information for which 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.
1312:
order to gain the largest portion of the split. Player 1 giving Player 2 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.
1316:
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
1463:
Limited backward induction has also been tested for within a variant of the race game. In the game, players would sequentially choose integers inside 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
1459:
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 the end. Limited backward induction also influences how regularly free-riding occurs within a team's public
1386:
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
1354:
consistent with backward induction. However, if the incumbent is going to fight, the best response for the entrant is to not enter, and if 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
1345:
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 the entrant enters, the incumbent can "fight" or
1315:
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 a proposer, Player 1, very rarely offers $ 0 and
1288:
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
1358:
Finding 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
1323:
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
1311:
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
33:
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 a series of decisions and identifying the optimal process or action required to arrive at that point. This
1411:
Limited backward induction 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
1303:
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 a dollar with Player 2, which Player 2 then
1031:
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 the
1363:
with an entrant, they are threatening to lower their prices from a monopoly price to slightly lower than 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
1250:
For example, in the first subgame, the choice "go to movie" offers a payoff of 9 since the decision tree terminates at the reward (9, 11), considering Player 2's previously established choice. Meanwhile, "stay home" offers a payoff of 1 since it ends at (1, 9), so Player 1 would choose "go to
1467:
Most tests of backward induction are based on experiments, in which participants are only to 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
1464:
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.
1349:
If 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
256:
This scenario is simplified by assuming that 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
1027:. Starting with the subgame furthest from the initial node, or starting point, the expected payoffs listed for this subgame are weighed, and a rational player will select the option with the higher payoff for themselves. The highest payoff
871:
1460:
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.
615:
1259:
For example, Player 2 would choose "Joker" for the first subgame in the next iteration because a payoff of 11 ending in (9, 11) is greater than "Terminator" with a payoff of 6 at (6, 6).
1233:
For example, considering the first subgame, Player 2's payoff of 11 for "go to movie" is higher than his payoff of 7 for "stay at home." Player 2 would therefore choose "go to movie."
253:. 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.
708:
458:
746:
1452:
Violations of backward induction is predominantly attributed to the presence of social factors. However, data-driven model predictions for sequential bargaining games (using the
496:
181:
1412:
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.
1804:
Marco
Mantovani, 2015. "Limited backward induction: foresight and behavior in sequential games," Working Papers 289, University of Milano-Bicocca, Department of Economics
1241:
Once Player 2's optimal decisions have been determined (bolded green lines in the extensive form diagram), analysis starts for Player 1's decisions in her 4 subgames.
565:
345:
228:
542:
368:
251:
1004:, backward induction is a solution methodology that follows from applying sequential rationality to identify an optimal action for each information set in a given
953:
769:
519:
391:
322:
292:
979:
927:
897:
821:
795:
670:
641:
420:
201:
981:. Generalizing this example intuitively, it corresponds to the principle that if one expects to work in a job for a long time, it is worth picking carefully.
34:
process continues backward until the best action for every possible point along the sequence is determined. Backward induction was first utilized in 1875 by
1262:
Player 1, at the initial node, would select "Terminator" because it offers a higher payoff of 11 at (11, 9) than Joker, which has a reward of 9 at (9, 11).
1341:
in which 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
1247:
Subgames that would not be chosen by Player 2 in the previous step are no longer considered because they are ruled out by the assumption of rational play.
1320:, an American behavioral economist, Player 2 "rejects offers of less than 20 percent of X about half the time, even though they end up with nothing."
1431:, where players can only perfectly see a few stages ahead. This allows for unpredictability in decisions and inefficiency in finding and achieving
393:. Therefore, if they are still unemployed in the last period, they should accept whatever job they are offered at that time for greater income.
1981:
1666:
1565:
1538:
110:
2880:
1070:
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.
1427:, subjects deviate from theoretical predictions and instead engage in limited backward induction. This deviation occurs as a result of
2697:
2232:
2030:
1768:
Rust J. (2008) Dynamic
Programming. In: Palgrave Macmillan (eds) The New Palgrave Dictionary of Economics. Palgrave Macmillan, London
2516:
2335:
903:
By continuing to work backwards, it can be verified that a 'bad' offer should only be accepted if the person is still unemployed at
58:
1865:
Qu, Xia; Doshi, Prashant (1 March 2017). "On the role of fairness and limited backward induction in sequential bargaining games".
2137:
1432:
2606:
1415:
2147:
2476:
92:
who chooses what to do at each point of time. In contrast, game theory problems involve the interacting decision of several
1274:
In this example, Player 1 chooses "Terminator" and Player 2 also chooses "Terminator." Then they both choose "go to movie."
1216:
of this multi-stage game can be seen to the right. The steps for solving this game with backward induction are as follows:
2657:
2075:
2050:
3053:
3043:
3007:
2433:
2187:
2177:
2112:
992:
is a field of microeconomics that applies models of this type to matters such as shopping, job searches, and marriage.
2227:
2207:
1268:
1016:
826:
2692:
570:
2941:
2662:
2320:
2162:
2157:
1453:
1379:
1373:
2977:
2900:
2636:
2192:
2117:
1974:
62:
50:
2992:
2725:
2611:
2408:
2202:
2020:
1400:
2795:
899:, total expected earnings are higher if the person waits for the next offer rather than accepting a 'bad' job.
2997:
2596:
2566:
2222:
2010:
2931:
1456:) have highlighted that in some games the presence of limited backward induction can play a dominant role.
1040:
The application of backward induction in game theory can be demonstrated with a simple example. Consider a
675:
425:
3022:
3002:
2982:
2601:
2506:
2365:
2315:
2310:
2242:
2212:
2132:
2060:
1928:
1581:
1555:
713:
1230:
Player 2 would make 8 possible comparisons in total, choosing the option with the highest payoff in each.
463:
268:
Whether the person in question should accept a 'bad' job can be decided by reasoning backwards from time
127:
Consider a person evaluating potential employment opportunities for the next ten years, denoted as times
2040:
2481:
2466:
1604:
1204:
3048:
2815:
2800:
2687:
2682:
2586:
2571:
2536:
2501:
2100:
2045:
1967:
1933:
130:
2972:
2591:
2541:
2378:
2305:
2285:
2142:
2025:
1428:
1213:
1082:
1020:
1009:
70:
46:
1900:
Cox, Caleb A.; Stoddard, Brock (May 2018). "Strategic thinking in public goods games with teams".
1244:
The process is similar to step 2, comparing Player 1's payoffs in order to anticipate her choices.
2951:
2810:
2641:
2621:
2471:
2350:
2182:
2127:
1882:
1847:
1751:
1473:
1469:
81:
2936:
2905:
2860:
2755:
2626:
2581:
2556:
2486:
2360:
2290:
2280:
2172:
2122:
2070:
1662:
1561:
1534:
1472:, for example, provides evidence of limited foresight. In every episode, contestants play the
1056:
101:
66:
39:
3017:
3012:
2946:
2910:
2890:
2850:
2820:
2775:
2730:
2715:
2672:
2526:
2167:
2104:
2090:
2055:
1909:
1874:
1837:
1827:
1787:
1778:
Aumann, Robert J. (January 1995). "Backward induction and common knowledge of rationality".
1743:
1710:
1351:
1086:
1041:
985:
547:
327:
262:
210:
97:
54:
524:
460:
because that job will last for two years. The total earnings from accepting a 'bad' job is
350:
233:
2915:
2875:
2830:
2745:
2740:
2461:
2413:
2300:
2065:
2035:
2005:
932:
751:
501:
373:
301:
271:
89:
85:
20:
2780:
1271:, one needs to identify a route that selects an optimal subgame at each information set.
958:
906:
876:
800:
774:
649:
620:
399:
1948:
Klein
Teeselink, Bouke; van Dolder, Dennie; van den Assem, Martijn; Dana, Jason (2022).
2855:
2845:
2835:
2770:
2760:
2750:
2735:
2531:
2511:
2496:
2491:
2451:
2418:
2403:
2398:
2388:
2197:
1424:
1305:
1298:
1050:
186:
1791:
3037:
2895:
2885:
2840:
2825:
2805:
2631:
2576:
2551:
2423:
2393:
2383:
2370:
2275:
2217:
2152:
2085:
1593:
Drew
Fudenberg and Jean Tirole, "Game Theory", Section 3.5, page 92. MIT Press, 1991.
1317:
1008:. It develops the implications of rationality via individual information sets in the
989:
258:
93:
35:
1886:
2870:
2865:
2720:
2295:
1851:
1387:
assumption, so the paradox does not call into question the results of this theory.
1338:
1913:
1505:
2987:
2790:
2785:
2765:
2561:
2546:
2355:
2325:
2260:
2250:
2080:
2015:
1991:
1396:
1001:
77:
203:, they may encounter a choice between two job options: a 'good' job offering a
2616:
2270:
1878:
988:
problem because the issue at hand is when to stop waiting for a better offer.
1731:
2521:
2441:
2265:
1360:
1005:
1715:
1698:
1081:
For this example, payoffs are added across different stages. The game is a
1842:
1506:"Non-credible threats, subgame perfect equilibrium and backward induction"
2956:
2456:
1747:
1342:
1074:
As in the first stage, Player 1 chooses whether to go to the movie first.
105:
30:
1959:
1423:
Experiments have shown that in sequential bargaining games, such as the
2677:
2667:
2345:
1755:
1485:
1383:
1256:
The process repeats for each player until the initial node is reached.
1224:
1024:
1028:
771:
now plus the total expected earnings from waiting for a job offer at
204:
1949:
1445:
The presence of non-social factors (e.g. limited backward induction)
1063:
Player 1 will buy a ticket first and tell Player 2 about her choice.
114:(1944), the book which established game theory as a field of study.
1832:
1815:
2446:
1203:
1627:
von
Neumann, John; Morgenstern, Oskar (1953). "Section 15.3.1.".
955:; a bad offer should be rejected at any time up to and including
1661:. The New Palgrave Dictionary of Economics: Palgrave Macmillan.
1533:. The New Palgrave Dictionary of Economics: Palgrave Macmillan.
1963:
1686:(3 ed.). New York: W.W. Norton & Company. p. 188.
521:
now plus the value of the next job offer, which will either be
1646:(3 ed.). New York: W.W. Norton & Company. p. 63.
1227:
from the final nodes to choose "go to movie" or "stay home".
1077:
After observing Player 1's choice, Player 2 makes his choice.
498:. The total expected earnings from rejecting a job offer are
1277:
The subgame perfect equilibrium leads to a payoff of (11,9).
1019:
with backwards induction, the game should be written out in
748:. The total expected earnings from rejecting a job offer is
567:
with 1/2 probability, for an average ('expected') value of
88:. The difference is that optimization problems involve one
1512:, Cambridge University Press, pp. 317–332, 2012-05-31
38:, who discovered the method while attempting to solve the
984:
A dynamic optimization problem of this kind is called an
823:
should be accepted and the expected value of doing so is
370:; the total earnings from rejecting the available job is
1557:
Dynamic
Economics: Quantitative Methods and Applications
1324:
effects rather than immediate potential monetary gains.
1927:
Mantovani, Marco (2013). "Limited backward induction".
108:, two-person formal games through this method in their
1438:
There are three broad hypotheses for this phenomenon:
961:
935:
909:
879:
829:
803:
777:
754:
716:
678:
652:
623:
573:
550:
527:
504:
466:
428:
402:
376:
353:
330:
304:
274:
236:
213:
189:
133:
80:, a variant of backward induction is used to compute
672:, the total earnings from accepting a 'good' job is
422:, the total earnings from accepting a 'good' job is
324:, the total earnings from accepting a 'good' job is
2965:
2924:
2706:
2650:
2432:
2334:
2241:
2099:
1998:
1419:
A four-stage sequential game with a foresight bound
710:; the total earnings from accepting a 'bad' job is
1395:Backward induction works only if both players are
1044:involving two players planning to go to a movie.
973:
947:
921:
891:
865:
815:
789:
763:
740:
702:
664:
635:
609:
559:
536:
513:
490:
452:
414:
385:
362:
339:
316:
286:
245:
222:
195:
175:
1867:Annals of Mathematics and Artificial Intelligence
866:{\displaystyle {\frac {\$ 200+\$ 88}{2}}=\$ 144}
1554:Adda, Jerome; Cooper, Russell W. (2003-08-29).
610:{\displaystyle {\frac {\$ 100+\$ 44}{2}}=\$ 72}
1442:The presence of social factors (e.g. fairness)
1975:
1631:(Third ed.). Princeton University Press.
53:, backward induction is used for solving the
8:
1950:"High-Stakes Failures of Backward Induction"
1584:", Section 7.3.1, page 164. MIT Press, 2002.
1208:Extensive form for the Joker-Terminator game
1582:Applied Computational Economics and Finance
1982:
1968:
1960:
65:, the method is called backward search or
16:Process of reasoning backwards in sequence
1932:
1841:
1831:
1714:
960:
934:
908:
878:
830:
828:
802:
776:
753:
715:
677:
651:
622:
574:
572:
549:
526:
503:
465:
427:
401:
375:
352:
329:
303:
273:
235:
212:
188:
132:
1684:Strategy: an introduction to game theory
1644:Strategy: an introduction to game theory
1414:
1147:
1091:
797:. As previously concluded, any offer at
347:; the value of accepting a 'bad' job is
1816:"Boundedly rational backward induction"
1497:
1304:accepts or rejects. This is called the
1236:The method continues for every subgame.
1703:Studies in Logic, Grammar and Rhetoric
1699:"Backward Induction: Merits And Flaws"
111:Theory of Games and Economic Behaviour
1629:Theory of Games and Economic Behavior
1603:MacQuarrie, John. "4, Fundamentals".
1220:Analysis starts from the final nodes.
703:{\displaystyle 3\times \$ 100=\$ 300}
453:{\displaystyle 2\times \$ 100=\$ 200}
7:
1732:"Progress in Behavioral Game Theory"
1730:Camerer, Colin F (1 November 1997).
741:{\displaystyle 3\times \$ 44=\$ 132}
230:or a 'bad' job offering a salary of
1066:Next, Player 2 will buy his ticket.
491:{\displaystyle 2\times \$ 44=\$ 88}
2031:First-player and second-player win
857:
842:
833:
755:
732:
723:
694:
685:
617:. Therefore, the job available at
601:
586:
577:
551:
528:
505:
482:
473:
444:
435:
377:
354:
331:
237:
214:
14:
1580:Mario Miranda and Paul Fackler, "
59:automated planning and scheduling
2138:Coalition-proof Nash equilibrium
1736:Journal of Economic Perspectives
29:is the process of determining a
1657:Rust, John (9 September 2016).
1529:Rust, John (9 September 2016).
1433:subgame perfect Nash equilibria
1391:Common knowledge of rationality
2148:Evolutionarily stable strategy
1148:
1092:
1089:matrices for these games are:
1054:, and Player 2 wants to watch
176:{\displaystyle t=1,2,3,...,10}
1:
2076:Simultaneous action selection
1914:10.1016/j.jpubeco.2018.03.007
1792:10.1016/S0899-8256(05)80015-6
1032:subgame perfect equilibrium.
3008:List of games in game theory
2188:Quantal response equilibrium
2178:Perfect Bayesian equilibrium
2113:Bayes correlated equilibrium
2477:Optional prisoner's dilemma
2208:Self-confirming equilibrium
1902:Journal of Public Economics
1780:Games and Economic Behavior
1697:Kamiński, Marek M. (2017).
1269:subgame perfect equilibrium
1017:subgame perfect equilibrium
1012:representation of a game.
57:. In the related fields of
3070:
2942:Principal variation search
2658:Aumann's agreement theorem
2321:Strategy-stealing argument
2233:Trembling hand equilibrium
2163:Markov perfect equilibrium
2158:Mertens-stable equilibrium
1609:. University of St Andrews
1407:Limited backward induction
1380:unexpected hanging paradox
1374:Unexpected hanging paradox
1371:
1368:Unexpected hanging paradox
1296:
82:subgame perfect equilibria
18:
2978:Combinatorial game theory
2637:Princess and monster game
2193:Quasi-perfect equilibrium
2118:Bayesian Nash equilibrium
1879:10.1007/s10472-015-9481-7
1454:cognitive hierarchy model
69:. In chess, it is called
63:automated theorem proving
51:mathematical optimization
2993:Evolutionary game theory
2726:Antoine Augustin Cournot
2612:Guess 2/3 of the average
2409:Strictly determined game
2203:Satisfaction equilibrium
2021:Escalation of commitment
1223:Player 2 will observe 8
1048:Player 1 wants to watch
1015:In order to solve for a
544:with 1/2 probability or
123:Optimal-stopping problem
19:Not to be confused with
2998:Glossary of game theory
2597:Stackelberg competition
2223:Strong Nash equilibrium
261:of zero and a constant
118:Decision-making example
3023:Tragedy of the commons
3003:List of game theorists
2983:Confrontation analysis
2693:Sprague–Grundy theorem
2213:Sequential equilibrium
2133:Correlated equilibrium
1716:10.1515/slgr-2017-0016
1420:
1333:Entry-decision problem
1209:
1023:and then divided into
975:
949:
923:
893:
867:
817:
791:
765:
742:
704:
666:
637:
611:
561:
560:{\displaystyle \$ 100}
538:
515:
492:
454:
416:
387:
364:
341:
340:{\displaystyle \$ 100}
318:
288:
247:
224:
223:{\displaystyle \$ 100}
197:
177:
2796:Jean-François Mertens
1820:Theoretical Economics
1682:Watson, Joel (2002).
1642:Watson, Joel (2002).
1606:Mathematics and Chess
1468:television game show
1418:
1359:threatens to start a
1207:
976:
950:
924:
894:
868:
818:
792:
766:
743:
705:
667:
638:
612:
562:
539:
537:{\displaystyle \$ 44}
516:
493:
455:
417:
388:
365:
363:{\displaystyle \$ 44}
342:
319:
289:
248:
246:{\displaystyle \$ 44}
225:
198:
178:
2925:Search optimizations
2801:Jennifer Tour Chayes
2688:Revelation principle
2683:Purification theorem
2622:Nash bargaining game
2587:Bertrand competition
2572:El Farol Bar problem
2537:Electronic mail game
2502:Lewis signaling game
2046:Hierarchy of beliefs
1814:Ke, Shaowei (2019).
1748:10.1257/jep.11.4.167
959:
948:{\displaystyle t=10}
933:
907:
877:
827:
801:
775:
764:{\displaystyle \$ 0}
752:
714:
676:
650:
621:
571:
548:
525:
514:{\displaystyle \$ 0}
502:
464:
426:
400:
386:{\displaystyle \$ 0}
374:
351:
328:
317:{\displaystyle t=10}
302:
287:{\displaystyle t=10}
272:
234:
211:
187:
131:
3054:Inductive reasoning
3044:Dynamic programming
2973:Bounded rationality
2592:Cournot competition
2542:Rock paper scissors
2517:Battle of the sexes
2507:Volunteer's dilemma
2379:Perfect information
2306:Dominant strategies
2143:Epsilon-equilibrium
2026:Extensive-form game
1659:Dynamic Programming
1531:Dynamic Programming
1448:Cultural difference
1429:bounded rationality
1152:
1096:
1083:perfect information
974:{\displaystyle t=8}
922:{\displaystyle t=9}
892:{\displaystyle t=8}
816:{\displaystyle t=9}
790:{\displaystyle t=9}
665:{\displaystyle t=8}
643:should be accepted.
636:{\displaystyle t=9}
415:{\displaystyle t=9}
71:retrograde analysis
47:dynamic programming
2952:Paranoid algorithm
2932:Alpha–beta pruning
2811:John Maynard Smith
2642:Rendezvous problem
2482:Traveler's dilemma
2472:Gift-exchange game
2467:Prisoner's dilemma
2384:Large Poisson game
2351:Bargaining problem
2256:Backward induction
2228:Subgame perfection
2183:Proper equilibrium
1470:The Price Is Right
1421:
1210:
971:
945:
919:
889:
863:
813:
787:
761:
738:
700:
662:
633:
607:
557:
534:
511:
488:
450:
412:
383:
360:
337:
314:
284:
243:
220:
193:
173:
104:suggested solving
27:Backward induction
3031:
3030:
2937:Aspiration window
2906:Suzanne Scotchmer
2861:Oskar Morgenstern
2756:Donald B. Gillies
2698:Zermelo's theorem
2627:Induction puzzles
2582:Fair cake-cutting
2557:Public goods game
2487:Coordination game
2361:Intransitive game
2291:Forward induction
2173:Pareto efficiency
2153:Gibbs equilibrium
2123:Berge equilibrium
2071:Simultaneous game
1668:978-1-349-95121-5
1567:978-0-262-01201-0
1540:978-1-349-95121-5
1474:Showcase Showdown
1202:
1201:
1146:
1145:
852:
596:
196:{\displaystyle t}
102:Oskar Morgenstern
67:backward chaining
40:secretary problem
3061:
3018:Topological game
3013:No-win situation
2911:Thomas Schelling
2891:Robert B. Wilson
2851:Merrill M. Flood
2821:John von Neumann
2731:Ariel Rubinstein
2716:Albert W. Tucker
2567:War of attrition
2527:Matching pennies
2168:Nash equilibrium
2091:Mechanism design
2056:Normal-form game
2011:Cooperative game
1984:
1977:
1970:
1961:
1954:
1953:
1945:
1939:
1938:
1936:
1924:
1918:
1917:
1897:
1891:
1890:
1862:
1856:
1855:
1845:
1835:
1811:
1805:
1802:
1796:
1795:
1775:
1769:
1766:
1760:
1759:
1727:
1721:
1720:
1718:
1694:
1688:
1687:
1679:
1673:
1672:
1654:
1648:
1647:
1639:
1633:
1632:
1624:
1618:
1617:
1615:
1614:
1600:
1594:
1591:
1585:
1578:
1572:
1571:
1551:
1545:
1544:
1526:
1520:
1519:
1518:
1517:
1502:
1401:common knowledge
1352:Nash equilibrium
1153:
1097:
1042:multi-stage game
1036:Multi-stage game
986:optimal stopping
980:
978:
977:
972:
954:
952:
951:
946:
928:
926:
925:
920:
898:
896:
895:
890:
873:. Therefore, at
872:
870:
869:
864:
853:
848:
831:
822:
820:
819:
814:
796:
794:
793:
788:
770:
768:
767:
762:
747:
745:
744:
739:
709:
707:
706:
701:
671:
669:
668:
663:
642:
640:
639:
634:
616:
614:
613:
608:
597:
592:
575:
566:
564:
563:
558:
543:
541:
540:
535:
520:
518:
517:
512:
497:
495:
494:
489:
459:
457:
456:
451:
421:
419:
418:
413:
392:
390:
389:
384:
369:
367:
366:
361:
346:
344:
343:
338:
323:
321:
320:
315:
293:
291:
290:
285:
263:marginal utility
252:
250:
249:
244:
229:
227:
226:
221:
202:
200:
199:
194:
182:
180:
179:
174:
98:John von Neumann
86:sequential games
55:Bellman equation
3069:
3068:
3064:
3063:
3062:
3060:
3059:
3058:
3034:
3033:
3032:
3027:
2961:
2947:max^n algorithm
2920:
2916:William Vickrey
2876:Reinhard Selten
2831:Kenneth Binmore
2746:David K. Levine
2741:Daniel Kahneman
2708:
2702:
2678:Negamax theorem
2668:Minimax theorem
2646:
2607:Diner's dilemma
2462:All-pay auction
2428:
2414:Stochastic game
2366:Mean-field game
2337:
2330:
2301:Markov strategy
2237:
2103:
2095:
2066:Sequential game
2051:Information set
2036:Game complexity
2006:Congestion game
1994:
1988:
1958:
1957:
1947:
1946:
1942:
1934:10.1.1.399.8991
1926:
1925:
1921:
1899:
1898:
1894:
1864:
1863:
1859:
1813:
1812:
1808:
1803:
1799:
1777:
1776:
1772:
1767:
1763:
1729:
1728:
1724:
1696:
1695:
1691:
1681:
1680:
1676:
1669:
1656:
1655:
1651:
1641:
1640:
1636:
1626:
1625:
1621:
1612:
1610:
1602:
1601:
1597:
1592:
1588:
1579:
1575:
1568:
1553:
1552:
1548:
1541:
1528:
1527:
1523:
1515:
1513:
1504:
1503:
1499:
1494:
1482:
1409:
1393:
1376:
1370:
1335:
1330:
1301:
1295:
1286:
1162:
1160:
1158:
1106:
1104:
1102:
1038:
998:
957:
956:
931:
930:
905:
904:
875:
874:
832:
825:
824:
799:
798:
773:
772:
750:
749:
712:
711:
674:
673:
648:
647:
619:
618:
576:
569:
568:
546:
545:
523:
522:
500:
499:
462:
461:
424:
423:
398:
397:
372:
371:
349:
348:
326:
325:
300:
299:
270:
269:
232:
231:
209:
208:
185:
184:
129:
128:
125:
120:
24:
21:Backpropagation
17:
12:
11:
5:
3067:
3065:
3057:
3056:
3051:
3046:
3036:
3035:
3029:
3028:
3026:
3025:
3020:
3015:
3010:
3005:
3000:
2995:
2990:
2985:
2980:
2975:
2969:
2967:
2963:
2962:
2960:
2959:
2954:
2949:
2944:
2939:
2934:
2928:
2926:
2922:
2921:
2919:
2918:
2913:
2908:
2903:
2898:
2893:
2888:
2883:
2881:Robert Axelrod
2878:
2873:
2868:
2863:
2858:
2856:Olga Bondareva
2853:
2848:
2846:Melvin Dresher
2843:
2838:
2836:Leonid Hurwicz
2833:
2828:
2823:
2818:
2813:
2808:
2803:
2798:
2793:
2788:
2783:
2778:
2773:
2771:Harold W. Kuhn
2768:
2763:
2761:Drew Fudenberg
2758:
2753:
2751:David M. Kreps
2748:
2743:
2738:
2736:Claude Shannon
2733:
2728:
2723:
2718:
2712:
2710:
2704:
2703:
2701:
2700:
2695:
2690:
2685:
2680:
2675:
2673:Nash's theorem
2670:
2665:
2660:
2654:
2652:
2648:
2647:
2645:
2644:
2639:
2634:
2629:
2624:
2619:
2614:
2609:
2604:
2599:
2594:
2589:
2584:
2579:
2574:
2569:
2564:
2559:
2554:
2549:
2544:
2539:
2534:
2532:Ultimatum game
2529:
2524:
2519:
2514:
2512:Dollar auction
2509:
2504:
2499:
2497:Centipede game
2494:
2489:
2484:
2479:
2474:
2469:
2464:
2459:
2454:
2452:Infinite chess
2449:
2444:
2438:
2436:
2430:
2429:
2427:
2426:
2421:
2419:Symmetric game
2416:
2411:
2406:
2404:Signaling game
2401:
2399:Screening game
2396:
2391:
2389:Potential game
2386:
2381:
2376:
2368:
2363:
2358:
2353:
2348:
2342:
2340:
2332:
2331:
2329:
2328:
2323:
2318:
2316:Mixed strategy
2313:
2308:
2303:
2298:
2293:
2288:
2283:
2278:
2273:
2268:
2263:
2258:
2253:
2247:
2245:
2239:
2238:
2236:
2235:
2230:
2225:
2220:
2215:
2210:
2205:
2200:
2198:Risk dominance
2195:
2190:
2185:
2180:
2175:
2170:
2165:
2160:
2155:
2150:
2145:
2140:
2135:
2130:
2125:
2120:
2115:
2109:
2107:
2097:
2096:
2094:
2093:
2088:
2083:
2078:
2073:
2068:
2063:
2058:
2053:
2048:
2043:
2041:Graphical game
2038:
2033:
2028:
2023:
2018:
2013:
2008:
2002:
2000:
1996:
1995:
1989:
1987:
1986:
1979:
1972:
1964:
1956:
1955:
1940:
1919:
1892:
1873:(1): 205–227.
1857:
1843:2027.42/147808
1833:10.3982/TE2402
1826:(1): 103–134.
1806:
1797:
1770:
1761:
1742:(4): 167–188.
1722:
1689:
1674:
1667:
1649:
1634:
1619:
1595:
1586:
1573:
1566:
1546:
1539:
1521:
1496:
1495:
1493:
1490:
1489:
1488:
1481:
1478:
1450:
1449:
1446:
1443:
1425:Centipede game
1408:
1405:
1392:
1389:
1372:Main article:
1369:
1366:
1334:
1331:
1329:
1326:
1306:ultimatum game
1299:Centipede game
1294:
1293:Ultimatum game
1291:
1285:
1282:
1281:
1280:
1279:
1278:
1275:
1267:To identify a
1265:
1264:
1263:
1260:
1254:
1253:
1252:
1248:
1245:
1239:
1238:
1237:
1234:
1231:
1221:
1214:extensive form
1200:
1199:
1196:
1193:
1187:
1186:
1183:
1180:
1174:
1173:
1168:
1163:
1159:
1156:
1144:
1143:
1140:
1137:
1131:
1130:
1127:
1124:
1118:
1117:
1112:
1107:
1103:
1100:
1079:
1078:
1075:
1068:
1067:
1064:
1061:
1051:The Terminator
1037:
1034:
1021:extensive form
1010:extensive-form
997:
994:
970:
967:
964:
944:
941:
938:
918:
915:
912:
901:
900:
888:
885:
882:
862:
859:
856:
851:
847:
844:
841:
838:
835:
812:
809:
806:
786:
783:
780:
760:
757:
737:
734:
731:
728:
725:
722:
719:
699:
696:
693:
690:
687:
684:
681:
661:
658:
655:
644:
632:
629:
626:
606:
603:
600:
595:
591:
588:
585:
582:
579:
556:
553:
533:
530:
510:
507:
487:
484:
481:
478:
475:
472:
469:
449:
446:
443:
440:
437:
434:
431:
411:
408:
405:
394:
382:
379:
359:
356:
336:
333:
313:
310:
307:
283:
280:
277:
242:
239:
219:
216:
192:
172:
169:
166:
163:
160:
157:
154:
151:
148:
145:
142:
139:
136:
124:
121:
119:
116:
90:decision maker
49:, a method of
15:
13:
10:
9:
6:
4:
3:
2:
3066:
3055:
3052:
3050:
3047:
3045:
3042:
3041:
3039:
3024:
3021:
3019:
3016:
3014:
3011:
3009:
3006:
3004:
3001:
2999:
2996:
2994:
2991:
2989:
2986:
2984:
2981:
2979:
2976:
2974:
2971:
2970:
2968:
2966:Miscellaneous
2964:
2958:
2955:
2953:
2950:
2948:
2945:
2943:
2940:
2938:
2935:
2933:
2930:
2929:
2927:
2923:
2917:
2914:
2912:
2909:
2907:
2904:
2902:
2901:Samuel Bowles
2899:
2897:
2896:Roger Myerson
2894:
2892:
2889:
2887:
2886:Robert Aumann
2884:
2882:
2879:
2877:
2874:
2872:
2869:
2867:
2864:
2862:
2859:
2857:
2854:
2852:
2849:
2847:
2844:
2842:
2841:Lloyd Shapley
2839:
2837:
2834:
2832:
2829:
2827:
2826:Kenneth Arrow
2824:
2822:
2819:
2817:
2814:
2812:
2809:
2807:
2806:John Harsanyi
2804:
2802:
2799:
2797:
2794:
2792:
2789:
2787:
2784:
2782:
2779:
2777:
2776:Herbert Simon
2774:
2772:
2769:
2767:
2764:
2762:
2759:
2757:
2754:
2752:
2749:
2747:
2744:
2742:
2739:
2737:
2734:
2732:
2729:
2727:
2724:
2722:
2719:
2717:
2714:
2713:
2711:
2705:
2699:
2696:
2694:
2691:
2689:
2686:
2684:
2681:
2679:
2676:
2674:
2671:
2669:
2666:
2664:
2661:
2659:
2656:
2655:
2653:
2649:
2643:
2640:
2638:
2635:
2633:
2630:
2628:
2625:
2623:
2620:
2618:
2615:
2613:
2610:
2608:
2605:
2603:
2600:
2598:
2595:
2593:
2590:
2588:
2585:
2583:
2580:
2578:
2577:Fair division
2575:
2573:
2570:
2568:
2565:
2563:
2560:
2558:
2555:
2553:
2552:Dictator game
2550:
2548:
2545:
2543:
2540:
2538:
2535:
2533:
2530:
2528:
2525:
2523:
2520:
2518:
2515:
2513:
2510:
2508:
2505:
2503:
2500:
2498:
2495:
2493:
2490:
2488:
2485:
2483:
2480:
2478:
2475:
2473:
2470:
2468:
2465:
2463:
2460:
2458:
2455:
2453:
2450:
2448:
2445:
2443:
2440:
2439:
2437:
2435:
2431:
2425:
2424:Zero-sum game
2422:
2420:
2417:
2415:
2412:
2410:
2407:
2405:
2402:
2400:
2397:
2395:
2394:Repeated game
2392:
2390:
2387:
2385:
2382:
2380:
2377:
2375:
2373:
2369:
2367:
2364:
2362:
2359:
2357:
2354:
2352:
2349:
2347:
2344:
2343:
2341:
2339:
2333:
2327:
2324:
2322:
2319:
2317:
2314:
2312:
2311:Pure strategy
2309:
2307:
2304:
2302:
2299:
2297:
2294:
2292:
2289:
2287:
2284:
2282:
2279:
2277:
2276:De-escalation
2274:
2272:
2269:
2267:
2264:
2262:
2259:
2257:
2254:
2252:
2249:
2248:
2246:
2244:
2240:
2234:
2231:
2229:
2226:
2224:
2221:
2219:
2218:Shapley value
2216:
2214:
2211:
2209:
2206:
2204:
2201:
2199:
2196:
2194:
2191:
2189:
2186:
2184:
2181:
2179:
2176:
2174:
2171:
2169:
2166:
2164:
2161:
2159:
2156:
2154:
2151:
2149:
2146:
2144:
2141:
2139:
2136:
2134:
2131:
2129:
2126:
2124:
2121:
2119:
2116:
2114:
2111:
2110:
2108:
2106:
2102:
2098:
2092:
2089:
2087:
2086:Succinct game
2084:
2082:
2079:
2077:
2074:
2072:
2069:
2067:
2064:
2062:
2059:
2057:
2054:
2052:
2049:
2047:
2044:
2042:
2039:
2037:
2034:
2032:
2029:
2027:
2024:
2022:
2019:
2017:
2014:
2012:
2009:
2007:
2004:
2003:
2001:
1997:
1993:
1985:
1980:
1978:
1973:
1971:
1966:
1965:
1962:
1951:
1944:
1941:
1935:
1930:
1923:
1920:
1915:
1911:
1907:
1903:
1896:
1893:
1888:
1884:
1880:
1876:
1872:
1868:
1861:
1858:
1853:
1849:
1844:
1839:
1834:
1829:
1825:
1821:
1817:
1810:
1807:
1801:
1798:
1793:
1789:
1785:
1781:
1774:
1771:
1765:
1762:
1757:
1753:
1749:
1745:
1741:
1737:
1733:
1726:
1723:
1717:
1712:
1708:
1704:
1700:
1693:
1690:
1685:
1678:
1675:
1670:
1664:
1660:
1653:
1650:
1645:
1638:
1635:
1630:
1623:
1620:
1608:
1607:
1599:
1596:
1590:
1587:
1583:
1577:
1574:
1569:
1563:
1560:. MIT Press.
1559:
1558:
1550:
1547:
1542:
1536:
1532:
1525:
1522:
1511:
1507:
1501:
1498:
1491:
1487:
1484:
1483:
1479:
1477:
1475:
1471:
1465:
1461:
1457:
1455:
1447:
1444:
1441:
1440:
1439:
1436:
1434:
1430:
1426:
1417:
1413:
1406:
1404:
1402:
1398:
1390:
1388:
1385:
1381:
1375:
1367:
1365:
1362:
1356:
1353:
1347:
1344:
1340:
1332:
1327:
1325:
1321:
1319:
1318:Colin Camerer
1313:
1309:
1307:
1300:
1292:
1290:
1283:
1276:
1273:
1272:
1270:
1266:
1261:
1258:
1257:
1255:
1249:
1246:
1243:
1242:
1240:
1235:
1232:
1229:
1228:
1226:
1222:
1219:
1218:
1217:
1215:
1206:
1197:
1194:
1192:
1189:
1188:
1184:
1181:
1179:
1176:
1175:
1172:
1169:
1167:
1164:
1155:
1154:
1151:
1141:
1138:
1136:
1133:
1132:
1128:
1125:
1123:
1120:
1119:
1116:
1113:
1111:
1108:
1099:
1098:
1095:
1090:
1088:
1084:
1076:
1073:
1072:
1071:
1065:
1062:
1059:
1058:
1053:
1052:
1047:
1046:
1045:
1043:
1035:
1033:
1030:
1026:
1022:
1018:
1013:
1011:
1007:
1003:
995:
993:
991:
990:Search theory
987:
982:
968:
965:
962:
942:
939:
936:
916:
913:
910:
886:
883:
880:
860:
854:
849:
845:
839:
836:
810:
807:
804:
784:
781:
778:
758:
735:
729:
726:
720:
717:
697:
691:
688:
682:
679:
659:
656:
653:
645:
630:
627:
624:
604:
598:
593:
589:
583:
580:
554:
531:
508:
485:
479:
476:
470:
467:
447:
441:
438:
432:
429:
409:
406:
403:
395:
380:
357:
334:
311:
308:
305:
297:
296:
295:
281:
278:
275:
266:
264:
260:
259:interest rate
254:
240:
217:
206:
190:
170:
167:
164:
161:
158:
155:
152:
149:
146:
143:
140:
137:
134:
122:
117:
115:
113:
112:
107:
103:
99:
95:
91:
87:
83:
79:
74:
72:
68:
64:
60:
56:
52:
48:
43:
41:
37:
36:Arthur Cayley
32:
28:
22:
2871:Peyton Young
2866:Paul Milgrom
2781:Hervé Moulin
2721:Amos Tversky
2663:Folk theorem
2374:-player game
2371:
2296:Grim trigger
2255:
1943:
1922:
1905:
1901:
1895:
1870:
1866:
1860:
1823:
1819:
1809:
1800:
1783:
1779:
1773:
1764:
1739:
1735:
1725:
1706:
1702:
1692:
1683:
1677:
1658:
1652:
1643:
1637:
1628:
1622:
1611:. Retrieved
1605:
1598:
1589:
1576:
1556:
1549:
1530:
1524:
1514:, retrieved
1509:
1500:
1466:
1462:
1458:
1451:
1437:
1422:
1410:
1394:
1377:
1357:
1348:
1339:dynamic game
1336:
1322:
1314:
1310:
1302:
1287:
1211:
1190:
1177:
1170:
1165:
1149:
1134:
1121:
1114:
1109:
1093:
1080:
1069:
1055:
1049:
1039:
1014:
999:
983:
902:
267:
255:
126:
109:
75:
44:
26:
25:
3049:Game theory
2988:Coopetition
2791:Jean Tirole
2786:John Conway
2766:Eric Maskin
2562:Blotto game
2547:Pirate game
2356:Global game
2326:Tit for tat
2261:Bid shading
2251:Appeasement
2101:Equilibrium
2081:Solved game
2016:Determinacy
1999:Definitions
1992:game theory
1786:(1): 6–19.
1709:(1): 9–24.
1510:Game Theory
1284:Limitations
1178:Go to Movie
1166:Go to Movie
1087:normal-form
1002:game theory
996:Game theory
78:game theory
3038:Categories
2632:Trust game
2617:Kuhn poker
2286:Escalation
2281:Deterrence
2271:Cheap talk
2243:Strategies
2061:Preference
1990:Topics of
1613:2023-11-25
1516:2024-04-04
1297:See also:
1135:Terminator
1115:Terminator
1085:game. The
265:of money.
183:. At each
2816:John Nash
2522:Stag hunt
2266:Collusion
1929:CiteSeerX
1908:: 31–43.
1361:price war
1328:Economics
1191:Stay Home
1171:Stay Home
1006:game tree
858:$
843:$
834:$
756:$
733:$
724:$
721:×
695:$
686:$
683:×
602:$
587:$
578:$
552:$
529:$
506:$
483:$
474:$
471:×
445:$
436:$
433:×
378:$
355:$
332:$
238:$
215:$
2957:Lazy SMP
2651:Theorems
2602:Deadlock
2457:Checkers
2338:of games
2105:concepts
1887:23565130
1480:See also
1397:rational
1343:monopoly
1225:subgames
1161:Player 1
1157:Player 2
1105:Player 1
1101:Player 2
1025:subgames
106:zero-sum
31:sequence
2709:figures
2492:Chicken
2346:Auction
2336:Classes
1852:9053484
1756:2138470
1486:Minimax
1384:paradox
1251:movie."
1198:-2, -2
1150:Stage 2
1094:Stage 1
94:players
1931:
1885:
1850:
1754:
1665:
1564:
1537:
1195:-2, 4
1185:4, -2
1029:vector
205:salary
2447:Chess
2434:Games
1883:S2CID
1848:S2CID
1752:JSTOR
1492:Notes
1382:is a
1182:6, 6
1142:5, 3
1139:1, 1
1129:0, 0
1126:3, 5
1122:Joker
1110:Joker
1057:Joker
2128:Core
1663:ISBN
1562:ISBN
1535:ISBN
1378:The
1212:The
100:and
61:and
2707:Key
1910:doi
1906:161
1875:doi
1838:hdl
1828:doi
1788:doi
1744:doi
1711:doi
1000:In
929:or
861:144
837:200
736:132
698:300
689:100
646:At
581:100
555:100
448:200
439:100
396:At
335:100
298:At
218:100
207:of
84:in
76:In
45:In
3040::
2442:Go
1904:.
1881:.
1871:79
1869:.
1846:.
1836:.
1824:14
1822:.
1818:.
1782:.
1750:.
1740:11
1738:.
1734:.
1707:50
1705:.
1701:.
1508:,
1435:.
1403:.
1337:A
943:10
846:88
727:44
605:72
590:44
532:44
486:88
477:44
358:44
312:10
294:.
282:10
241:44
171:10
73:.
42:.
2372:n
1983:e
1976:t
1969:v
1952:.
1937:.
1916:.
1912::
1889:.
1877::
1854:.
1840::
1830::
1794:.
1790::
1784:8
1758:.
1746::
1719:.
1713::
1671:.
1616:.
1570:.
1543:.
1060:.
969:8
966:=
963:t
940:=
937:t
917:9
914:=
911:t
887:8
884:=
881:t
855:=
850:2
840:+
811:9
808:=
805:t
785:9
782:=
779:t
759:0
730:=
718:3
692:=
680:3
660:8
657:=
654:t
631:9
628:=
625:t
599:=
594:2
584:+
509:0
480:=
468:2
442:=
430:2
410:9
407:=
404:t
381:0
309:=
306:t
279:=
276:t
191:t
168:,
165:.
162:.
159:.
156:,
153:3
150:,
147:2
144:,
141:1
138:=
135:t
23:.
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.