Program equilibria and discounted computation time

ABSTRACT

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 the result of 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 the existence of equilibrium in other games not covered by the earlier work.

REFERENCES

• 1: Robert Abbott , Hector Garcia-Molina, Scheduling real-time transactions, ACM SIGMOD Record, v.17 n.1, p.71-81, March, 1988 [doi>10.1145/44203.44209]
• 2: {Fortnow 08} L. Fortnow. Discounted Time. Computational Complexity Weblog, August 2008. http://tinyurl.com/discountedtime.
• 3: {Halpern 08} J. Halpern&R. Pass. Game Theory with Costly Computation. Rapport technique arXiv:0909.0024vl, arXiv, 2008.
• 4: {Kalai 07} A. Kalai, E. Kalai, E. Lehrer&D. Samet. A commitment folk theorem. Manuscript., 2007.
• 5: {Kleene 38} S. Kleene. On notation for ordinal numbers. Journal of Symbolic Logic, vol. 3, pages 150--155, 1938.
• 6: {Monderer 06} D. Monderer&M. Tennenholtz. Strong mediated equilibrium. Manuscript., 2006.
• 7: {Peters 08} M. Peters&B. Szentes. Definable and contractible contracts. Manuscript., 2008.
• 8: {Tennenholtz 04} M. Tennenholtz. Program Equilibrium. Games and Economic Behavior, vol. 49, no. 2, pages 363--373, November 2004.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Computational logic

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Logic programming
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Theory