Seminar: March 2, 2009

Lance Fortnow, Northwestern University

Program Equilibria and Discounted Computation Time

Tennenholtz 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 payoff 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 payoffs 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.