Program Equilibria and Discounted Computation Time
AbstractTennenholtz (GEB 2004) developed Program Equilibrium to model play in a finite two-player game where each player can base their strategy on the other player's strategies. Tennenholtz's model allowed each player to produce a "loop-free" computer program that had access to the code for both players. He showed a folk theorem where any mixed-strategy individually rational play could be an equilibrium payo in this model even in a one-shot game. Kalai et al. gave a general folk theorem for correlated play in a more generic commitment model. We develop a new model of program equilibrium using general computational models and discounting the payo s based on the computation time used. We give an even more general folk theorem giving correlated-strategy payoffs down to the pure minimax of each player. We also show equilibrium in other games not covered by the earlier work.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoPaper provided by Northwestern University, Center for Mathematical Studies in Economics and Management Science in its series Discussion Papers with number 1473.
Date of creation: Nov 2008
Date of revision:
Contact details of provider:
Postal: Center for Mathematical Studies in Economics and Management Science, Northwestern University, 580 Jacobs Center, 2001 Sheridan Road, Evanston, IL 60208-2014
Web page: http://www.kellogg.northwestern.edu/research/math/
More information through EDIRC
Find related papers by JEL classification:
- C72 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Noncooperative Games
- C78 - Mathematical and Quantitative Methods - - Game Theory and Bargaining Theory - - - Bargaining Theory; Matching Theory
- L13 - Industrial Organization - - Market Structure, Firm Strategy, and Market Performance - - - Oligopoly and Other Imperfect Markets
This paper has been announced in the following NEP Reports:
- NEP-ALL-2009-04-05 (All new papers)
- NEP-CMP-2009-04-05 (Computational Economics)
- NEP-GTH-2009-04-05 (Game Theory)
You can help add them by filling out this form.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: (Fran Walker).
If references are entirely missing, you can add them using this form.