**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.

Concept# Backward induction

Summary

Backward induction is the process of reasoning backwards in time, from the end of a problem or situation, to determine a sequence of optimal actions. It proceeds by examining the last point at which a decision is to be made and then identifying what action would be most optimal at that moment. Using this information, one can then determine what to do at the second-to-last time of decision. This process continues backwards until one has determined the best action for every possible situation (i.e. for every possible information set) at every point in time. Backward induction was first used in 1875 by Arthur Cayley, who uncovered the method while trying to solve the infamous Secretary problem.
In the mathematical optimization method of dynamic programming, backward induction is one of the main methods for solving the Bellman equation. In game theory, backward induction is a method used to compute subgame perfect equilibria in sequential games. The only difference is that optimization involves just one decision maker, who chooses what to do at each point of time, whereas game theory analyzes how the decisions of several players interact. That is, by anticipating what the last player will do in each situation, it is possible to determine what the second-to-last player will do, and so on. 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.
Backward induction has been used to solve games as long as the field of game theory has existed. John von Neumann and Oskar Morgenstern suggested solving zero-sum, two-person games by backward induction in their Theory of Games and Economic Behavior (1944), the book which established game theory as a field of study.
Consider an unemployed person who will be able to work for ten more years t = 1,2,...,10. Suppose that each year in which they remain unemployed, they may be offered a 'good' job that pays $100, or a 'bad' job that pays$44, with equal probability (50/50).

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts (12)

Related courses (2)

Related publications (34)

Related people (5)

Related lectures (13)

Bellman equation

A Bellman equation, named after Richard E. Bellman, is a necessary condition for optimality associated with the mathematical optimization method known as dynamic programming. It writes the "value" of a decision problem at a certain point in time in terms of the payoff from some initial choices and the "value" of the remaining decision problem that results from those initial choices. This breaks a dynamic optimization problem into a sequence of simpler subproblems, as Bellman's “principle of optimality" prescribes.

Extensive-form game

In game theory, an extensive-form game is a specification of a game allowing (as the name suggests) 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 imperfect) information each player has about the other player's moves when they make a decision, and their payoffs for all possible game outcomes. Extensive-form games also allow for the representation of incomplete information in the form of chance events modeled as "moves by nature".

Sequential game

In game theory, a sequential game is a game where one player chooses their action before the others choose theirs. 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.

MGT-300: Game theory and strategic decisions

Game theory studies the strategic interactions between rational agents. It has a myriad of applications in politics, business, sports. A special branch of Game Theory, Auction Theory, has recently g

ME-429: Multi-agent learning and control

Students will be able to formulate a multi-agent decision-making problem as a game and apply relevant mathematical theories and algorithms to analyze the interaction of the agents and predict the outc

Asset Pricing and Hedging in Complete Markets

Covers asset pricing, hedging, American claims, stopping times, and dynamic programming in finance.

Efstratios Panteleimon Skoulakis

In this paper we provide a novel and simple algorithm, Clairvoyant Multiplicative Weights Updates (CMWU), for convergence to \textit{Coarse Correlated Equilibria} (CCE) in general games. CMWU effectively corresponds to the standard MWU algorithm but where ...

2022Michel Bierlaire, Virginie Janine Camille Lurkin, Stefano Bortolomiol

Oligopolistic competition occurs in various transportation markets. In this paper, we introduce a framework to find approximate equilibrium solutions of oligopolistic markets in which demand is modeled at the disaggregate level using discrete choice models ...

Bryan Alexander Ford, Verónica del Carmen Estrada Galiñanes, Louis-Henri Manuel Jakob Merino, Haoqian Zhang, Mahsa Bastankhah

Blockchain systems often rely on rationality assumptions for their security, expecting that nodes are motivated to maximize their profits. These systems thus design their protocols to incentivize nodes to execute the honest protocol but fail to consider ou ...