Backward Induction for Repeated Games

Jules Hedges
(University of Oxford)

We present a method of backward induction for computing approximate subgame perfect Nash equilibria of infinitely repeated games with discounted payoffs. This uses the selection monad transformer, combined with the searchable set monad viewed as a notion of 'topologically compact' nondeterminism, and a simple model of computable real numbers. This is the first application of Escardó and Oliva's theory of higher-order sequential games to games of imperfect information, in which (as well as its mathematical elegance) lazy evaluation does nontrivial work for us compared with a traditional game-theoretic analysis. Since a full theoretical understanding of this method is lacking (and appears to be very hard), we consider this an 'experimental' paper heavily inspired by theoretical ideas. We use the famous Iterated Prisoner's Dilemma as a worked example.

In Robert Atkey and Sam Lindley: Proceedings of the 7th Workshop on Mathematically Structured Functional Programming (MSFP 2018), Oxford, UK, 8th July 2018, Electronic Proceedings in Theoretical Computer Science 275, pp. 35–52.
Published: 10th July 2018.

ArXived at: bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to:
For website issues: