Program Equilibria and Discounted Computation Time
Tennenholtz (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.
|Date of creation:||Nov 2008|
|Date of revision:|
|Contact details of provider:|| Postal: |
Web page: http://www.kellogg.northwestern.edu/research/math/Email:
More information through EDIRC
|Order Information:|| Email: |
When requesting a correction, please mention this item's handle: RePEc:nwu:cmsems:1473. See general information about how to correct material in RePEc.
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.