AAAI Publications, Twenty-Fourth AAAI Conference on Artificial Intelligence

Font Size: 
An Approximate Subgame-Perfect Equilibrium Computation Technique for Repeated Games
Andriy Burkov, Brahim Chaib-draa

Last modified: 2010-07-04


This paper presents a technique for approximating, up to any precision, the set of subgame-perfect equilibria (SPE) in repeated games with discounting. The process starts with a single hypercube approximation of the set of SPE payoff profiles. Then the initial hypercube is gradually partitioned on to a set of smaller adjacent hypercubes, while those hypercubes that cannot contain any SPE point are gradually withdrawn. Whether a given hypercube can contain an equilibrium point is verified by an appropriate mixed integer program. A special attention is paid to the question of extracting players' strategies and their representability in form of finite automata.


multiagent systems; game theory; repeated games; subgame-perfect equilibrium; computation

Full Text: PDF