4pm Thursday, 24th of February, 2009
Room 4.31/4.33, Informatics Forum
Abstract
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.