Backward Induction for Repeated Games
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, an...
| Main Author: | |
|---|---|
| Format: | Conference item |
| Published: |
Open Publishing Association
2018
|
| _version_ | 1797054054539460608 |
|---|---|
| author | Hedges, J |
| author_facet | Hedges, J |
| author_sort | Hedges, J |
| collection | OXFORD |
| description | 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 ´o 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. |
| first_indexed | 2024-03-06T18:52:10Z |
| format | Conference item |
| id | oxford-uuid:109c72e1-ed94-4292-ba56-5c1dc137b6b1 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T18:52:10Z |
| publishDate | 2018 |
| publisher | Open Publishing Association |
| record_format | dspace |
| spelling | oxford-uuid:109c72e1-ed94-4292-ba56-5c1dc137b6b12022-03-26T09:57:18ZBackward Induction for Repeated GamesConference itemhttp://purl.org/coar/resource_type/c_5794uuid:109c72e1-ed94-4292-ba56-5c1dc137b6b1Symplectic Elements at OxfordOpen Publishing Association2018Hedges, JWe 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 ´o 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. |
| spellingShingle | Hedges, J Backward Induction for Repeated Games |
| title | Backward Induction for Repeated Games |
| title_full | Backward Induction for Repeated Games |
| title_fullStr | Backward Induction for Repeated Games |
| title_full_unstemmed | Backward Induction for Repeated Games |
| title_short | Backward Induction for Repeated Games |
| title_sort | backward induction for repeated games |
| work_keys_str_mv | AT hedgesj backwardinductionforrepeatedgames |