Raisonnement rétrograde | EPFL Graph Search

Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?

Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur GraphSearch.

Découvrez-en plus sur les applications Graph.

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).

À propos de ce résultat

Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.

Concepts associés (13)

Cours associés (3)

Séances de cours associées (13)

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

FIN-620: Game Theory

Game theory deals with multiperson strategic decision making. Major fields of Economics, such as Microeconomics, Corporate Finance, Market Microstructure, Monetary Economics, Industrial Organization,

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.

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.

Équilibre de Nash

vignette|Le dilemme du prisonnier : chacun des deux joueurs dispose de deux stratégies : D pour dénoncer, C pour ne pas dénoncer. La matrice présente le gain des joueurs. Si les deux joueurs choisissent D (se dénoncent), aucun ne regrette son choix, car s'il avait choisi C, alors que l'autre a opté pour D, sa « tristesse » aurait augmenté. C'est un équilibre de Nash — il y a « non-regret » de son choix par chacun, au vu du choix de l'autre.

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".

Tarification des actifs et couverture sur les marchés complets FIN-609: Asset Pricing

Couvre la tarification des actifs, la couverture, les réclamations américaines, les temps d'arrêt et la programmation dynamique en finance.

Méthodes Monte-Carlo pour l'apprentissage par renforcement CS-456: Artificial neural networks/reinforcement learning

Explore les méthodes de Monte-Carlo pour l'apprentissage par renforcement, en les comparant avec les méthodes TD et en mettant l'accent sur l'efficacité des méthodes TD dans la propagation de l'information.

Théorie des jeux : la prise de décision dans des environnements interdépendants MGT-454: Principles of microeconomics

Explore la théorie des jeux, la prise de décision dans des environnements interdépendants, les concepts d'équilibre et les applications économiques en gestion.