Dynamic Programming for Pure-Strategy Subgame Perfection in an Arbitrary Game

Peter Streufert

No 20233, University of Western Ontario, Departmental Research Report Series from University of Western Ontario, Department of Economics

Abstract: This paper uses value functions to characterize the pure-strategy subgame-perfect equilibria of an arbitrary, possibly infinite-horizon game. It specifies the game’s extensive form as a pentaform (Streufert 2023p, arXiv:2107.10801v4), which is a set of quintuples formalizing the abstract relationships between nodes, actions, players, and situations (situations generalize information sets). Because a pentaform is a set, this paper can explicitly partition the game form into piece forms, each of which starts at a (Selten) subroot and contains all subsequent nodes except those that follow a subsequent subroot. Then the set of subroots becomes the domain of a value function, and the piece-form partition becomes the framework for a value recursion which generalizes the Bellman equation from dynamic programming. The main results connect the value recursion with the subgame-perfect equilibria of the original game, under the assumptions of upper- and lower-convergence. Finally, a corollary characterizes subgame perfection as the absence of an improving one-piece deviation.

Keywords: Bellman equation; value function; upper-convergence; lower-convergence; pentaform (search for similar items in EconPapers)
JEL-codes: C61 C73 (search for similar items in EconPapers)
Date: 2023
New Economics Papers: this item is included in nep-gth
References: Add references at CitEc
Citations:

Downloads: (external link)
https://ir.lib.uwo.ca/cgi/viewcontent.cgi?article=1859&context=economicsresrpt (application/pdf)
Our link check indicates that this URL is bad, the error code is: 403 Forbidden

Related works:
Working Paper: Dynamic Programming for Pure-Strategy Subgame Perfection in an Arbitrary Game (2023)
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:uwo:uwowop:20233

Ordering information: This working paper can be ordered from
https://economics.uw ... itting_ordering.html
The price is Paper copy available by mail at a cost of $10.00 Canadian each.

Access Statistics for this paper

More papers in University of Western Ontario, Departmental Research Report Series from University of Western Ontario, Department of Economics Department of Economics, Social Science Centre, University of Western Ontario, London, Ontario, Canada N6A 5C2.
Bibliographic data for series maintained by ().