Repeated Games Algorithm
This page hosts rgsolve , a Java implementation of Dilip Abreu and Yuliy Sannikov’s algorithm for computing equilibrium payoffs of two-player infinitely repeated discounted games with perfect monitoring and public randomization. The program was developed by Dilip Abreu, Benjamin Brooks, Richard Katzwer, Yuliy Sannikov, and Rohit Lamba. The Java implementation was written by Richard Katzwer.
To use the program package, simply download the zip file rgsolve.zip. * The rgsolve user guide [.pdf] is in this folder, but can also be accessed here.
The following is a demonstration of how the algorithm works, for the example depicted above. With a discount factor of 0.3, the algorithm takes 50 iterations and 0.013 seconds to converge. The image below shows the first four iterations. The criterion for convergence is that the extreme points do not move by more than 2.2e(-16).
Some rgsolve resources can be found here, including
- Online documentation (javadocs) for the rgsolve package.
- An online rgsolve applet which runs directly in the browser (with some reduced I/O functionality).
- A user guide [.pdf]
rgsolve is based on algorithms found in the following papers:
- Dilip Abreu and Yuliy Sannikov, "An algorithm for two player repeated games with perfect monitoring". Theoretical Economics , 2013 [T.E.]
- Dilip Abreu, David Pearce and Ennio Stachetti, "Toward a Theory of Discounted Repeated Games with Imperfect Monitoring". Econometrica , Vol 58, No. 5 (Sep. 1990), pp. 1041-1063. [jstor].
* rgsolve is written in 100% Java, and has been tested on Java 6 and Java 7 on Windows, Mac and Linux machines. To download install a Java Runtime Environment, go here.