Sequential game
In game theory, a sequential game is a game where one player chooses their action before the others choose theirs.[1] The other players must have information on the first player's choice so that the difference in time has no strategic effect. Sequential games are governed by the time axis and represented in the form of decision trees.
Sequential games with perfect information can be analysed mathematically using combinatorial game theory.
Decision trees are the extensive form of dynamic games that provide information on the possible ways that a given game can be played. They show the sequence in which players act and the number of times that they can each make a decision. Decision trees also provide information on what each player knows or does not know at the point in time they decide on an action to take. Payoffs for each player are given at the decision nodes of the tree. Extensive form representations were introduced by Neumann and further developed by Kuhn in the earliest years of game theory between 1910–1930.[2]
Repeated games are an example of sequential games. Players perform a stage game and the results will determine how the game continues. At every new stage, both players will have complete information on how the previous stages had played out. A discount rate between the values of 0 and 1 is usually taken into account when considering the payoff of each player. Repeated games illustrate the psychological aspect of games, such as trust and revenge, when each player makes a decision at every stage game based on how the game has been played out so far.[2]
Unlike sequential games, simultaneous games do not have a time axis so players choose their moves without being sure of the other players' decisions. Simultaneous games are usually represented in the form of payoff matrices. One example of a simultaneous game is rock-paper-scissors, where each player draws at the same time not knowing whether their opponent will choose rock, paper, or scissors. Extensive form representations are typically used for sequential games, since they explicitly illustrate the sequential aspects of a game. Combinatorial games are also usually sequential games.
Games such as chess, infinite chess, backgammon, tic-tac-toe and Go are examples of sequential games. The size of the decision trees can vary according to game complexity, ranging from the small game tree of tic-tac-toe, to an immensely complex game tree of chess so large that even computers cannot map it completely.[3]
Games can be either strictly determined or determined. A strictly determined game only has one individually rational payoff profile in the 'pure' sense. For a game to be determined it can have only one individually rational payoff profile in the mixed sense.[4]
In sequential games with perfect information, a subgame perfect equilibrium can be found by backward induction.[5]
See also
References
- ^ Brocas; Carrillo; Sachdeva (2018). "The Path to Equilibrium in Sequential and Simultaneous Games". Journal of Economic Theory. 178: 246–274. doi:10.1016/j.jet.2018.09.011. S2CID 12989080.
- ^ a b Aumann, R. J. Game Theory.[full citation needed]
- ^ Claude Shannon (1950). "Programming a Computer for Playing Chess" (PDF). Philosophical Magazine. 41 (314).
- ^ Aumann, R.J. (2008), Palgrave Macmillan (ed.), "Game Theory", The New Palgrave Dictionary of Economics, London: Palgrave Macmillan UK, pp. 1–40, doi:10.1057/978-1-349-95121-5_942-2, ISBN 978-1-349-95121-5, retrieved 2021-12-08
- ^ Aliprantis, Charalambos D. (August 1999). "On the backward induction method". Economics Letters. 64 (2): 125–131. doi:10.1016/s0165-1765(99)00068-3.
- v
- t
- e
- Congestion game
- Cooperative game
- Determinacy
- Escalation of commitment
- Extensive-form game
- First-player and second-player win
- Game complexity
- Graphical game
- Hierarchy of beliefs
- Information set
- Normal-form game
- Preference
- Sequential game
- Simultaneous game
- Simultaneous action selection
- Solved game
- Succinct game
concepts
- Bayes correlated equilibrium
- Bayesian Nash equilibrium
- Berge equilibrium
- Core
- Correlated equilibrium
- Epsilon-equilibrium
- Evolutionarily stable strategy
- Gibbs equilibrium
- Mertens-stable equilibrium
- Markov perfect equilibrium
- Nash equilibrium
- Pareto efficiency
- Perfect Bayesian equilibrium
- Proper equilibrium
- Quantal response equilibrium
- Quasi-perfect equilibrium
- Risk dominance
- Satisfaction equilibrium
- Self-confirming equilibrium
- Sequential equilibrium
- Shapley value
- Strong Nash equilibrium
- Subgame perfection
- Trembling hand
of games
- Go
- Chess
- Infinite chess
- Checkers
- Tic-tac-toe
- Prisoner's dilemma
- Gift-exchange game
- Optional prisoner's dilemma
- Traveler's dilemma
- Coordination game
- Chicken
- Centipede game
- Lewis signaling game
- Volunteer's dilemma
- Dollar auction
- Battle of the sexes
- Stag hunt
- Matching pennies
- Ultimatum game
- Rock paper scissors
- Pirate game
- Dictator game
- Public goods game
- Blotto game
- War of attrition
- El Farol Bar problem
- Fair division
- Fair cake-cutting
- Cournot game
- Deadlock
- Diner's dilemma
- Guess 2/3 of the average
- Kuhn poker
- Nash bargaining game
- Induction puzzles
- Trust game
- Princess and monster game
- Rendezvous problem
figures
- Albert W. Tucker
- Amos Tversky
- Antoine Augustin Cournot
- Ariel Rubinstein
- Claude Shannon
- Daniel Kahneman
- David K. Levine
- David M. Kreps
- Donald B. Gillies
- Drew Fudenberg
- Eric Maskin
- Harold W. Kuhn
- Herbert Simon
- Hervé Moulin
- John Conway
- Jean Tirole
- Jean-François Mertens
- Jennifer Tour Chayes
- John Harsanyi
- John Maynard Smith
- John Nash
- John von Neumann
- Kenneth Arrow
- Kenneth Binmore
- Leonid Hurwicz
- Lloyd Shapley
- Melvin Dresher
- Merrill M. Flood
- Olga Bondareva
- Oskar Morgenstern
- Paul Milgrom
- Peyton Young
- Reinhard Selten
- Robert Axelrod
- Robert Aumann
- Robert B. Wilson
- Roger Myerson
- Samuel Bowles
- Suzanne Scotchmer
- Thomas Schelling
- William Vickrey
- All-pay auction
- Alpha–beta pruning
- Bertrand paradox
- Bounded rationality
- Combinatorial game theory
- Confrontation analysis
- Coopetition
- Evolutionary game theory
- First-move advantage in chess
- Glossary of game theory
- List of game theorists
- List of games in game theory
- No-win situation
- Solving chess
- Topological game
- Tragedy of the commons
- Tyranny of small decisions