2010/02/08 by Andriy Burkov, Burkov, Andriy, Brahim Chaib-draa +1
Decision Sciences · Economics, Econometrics and Finance · #Computer Science and Game Theory (cs.GT) #Economic theories and models #FOS: Computer and information sciences #Game Theory and Applications #Game Theory and Voting Systems #I.2.1 #I.2.11
paper · pdf · doi:10.48550/arxiv.1002.1718
openalex publication_date 2010/02/08 · openalex created_date 2022/09/05 · openalex updated_date 2026/07/28
This paper presents a technique for approximating, up to any precision, the\nset of subgame-perfect equilibria (SPE) in discounted repeated games. The\nprocess starts with a single hypercube approximation of the set of SPE. Then\nthe initial hypercube is gradually partitioned on to a set of smaller adjacent\nhypercubes, while those hypercubes that cannot contain any point belonging to\nthe set of SPE are simultaneously withdrawn.\n Whether a given hypercube can contain an equilibrium point is verified by an\nappropriate mathematical program. Three different formulations of the algorithm\nfor both approximately computing the set of SPE payoffs and extracting players'\nstrategies are then proposed: the first two that do not assume the presence of\nan external coordination between players, and the third one that assumes a\ncertain level of coordination during game play for convexifying the set of\ncontinuation payoffs after any repeated game history.\n A special attention is paid to the question of extracting players' strategies\nand their representability in form of finite automata, an important feature for\nartificial agent systems.\n