research-article

Program equilibria and discounted computation time

Author:

Lance FortnowAuthors Info & Claims

TARK '09: Proceedings of the 12th Conference on Theoretical Aspects of Rationality and Knowledge

Pages 128 - 133

https://doi.org/10.1145/1562814.1562833

Published: 06 July 2009 Publication History

Get Access

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]

{Abbott 88} R. Abbott&H. Garcia-Molina. Scheduling real-time transacations. ACM SIGMOD Record, vol. 17, no. 1, pages 71--81, March 1988.

Digital Library

Google Scholar

[2]

{Fortnow 08} L. Fortnow. Discounted Time. Computational Complexity Weblog, August 2008. http://tinyurl.com/discountedtime.

Google Scholar

[3]

{Halpern 08} J. Halpern&R. Pass. Game Theory with Costly Computation. Rapport technique arXiv:0909.0024vl, arXiv, 2008.

Google Scholar

[4]

{Kalai 07} A. Kalai, E. Kalai, E. Lehrer&D. Samet. A commitment folk theorem. Manuscript., 2007.

Google Scholar

[5]

{Kleene 38} S. Kleene. On notation for ordinal numbers. Journal of Symbolic Logic, vol. 3, pages 150--155, 1938.

Crossref

Google Scholar

[6]

{Monderer 06} D. Monderer&M. Tennenholtz. Strong mediated equilibrium. Manuscript., 2006.

Google Scholar

[7]

{Peters 08} M. Peters&B. Szentes. Definable and contractible contracts. Manuscript., 2008.

Google Scholar

[8]

{Tennenholtz 04} M. Tennenholtz. Program Equilibrium. Games and Economic Behavior, vol. 49, no. 2, pages 363--373, November 2004.

Google Scholar

Cited By

View all

Kovařík VOesterheld CConitzer VElkind E(2023)Game theory with simulation of other playersProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/312(2800-2807)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/312
Istrate G(2021)Game-Theoretic Models of Moral and Other-Regarding Agents (extended abstract)Electronic Proceedings in Theoretical Computer Science10.4204/EPTCS.335.19335(213-227)Online publication date: 22-Jun-2021
https://doi.org/10.4204/EPTCS.335.19
Peters MTroncoso-Valverde C(2013)A folk theorem for competing mechanismsJournal of Economic Theory10.1016/j.jet.2013.01.001148:3(953-973)Online publication date: May-2013
https://doi.org/10.1016/j.jet.2013.01.001
Show More Cited By

Index Terms

Program equilibria and discounted computation time
1. Computing methodologies
  1. Artificial intelligence
    1. Knowledge representation and reasoning
      1. Logic programming and answer set programming
  2. Modeling and simulation
    1. Model development and analysis
      1. Modeling methodologies
2. Theory of computation
  1. Logic
    1. Constraint and logic programming

Recommendations

Computing equilibria in discounted dynamic games

Game theory (GT) is an essential formal tool for interacting entities; however computing equilibria in GT is a hard problem. When the same game can be played repeatedly over time, the problem becomes even more complicated. The existence of multiple game ...
Set-valued games and mixed-strategy equilibria in discounted supergames
Abstract
This paper examines the subgame-perfect mixed-strategy equilibria in discounted supergames. We present a method that finds all the equilibrium payoffs without public correlation in 2 × 2 games. The method makes it possible to solve and ...
Computing Equilibria in Discounted 2 × 2 Supergames

This article examines the subgame perfect pure strategy equilibrium paths and payoff sets of discounted supergames with perfect monitoring. The main contribution is to provide methods for computing and tools for analyzing the equilibrium paths and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

TARK '09: Proceedings of the 12th Conference on Theoretical Aspects of Rationality and Knowledge

July 2009

272 pages

ISBN:9781605585604

DOI:10.1145/1562814

Program Chair:
Aviad Heifetz
The Open University of Israel

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 July 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Funding Sources

Conference

TARK '09

TARK '09: The 11th conference on Theoretical aspects of rationality and knowledge

July 6 - 8, 2009

California

Acceptance Rates

TARK '09 Paper Acceptance Rate 29 of 77 submissions, 38%;

Overall Acceptance Rate 61 of 177 submissions, 34%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
144
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 07 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Kovařík VOesterheld CConitzer VElkind E(2023)Game theory with simulation of other playersProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/312(2800-2807)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/312
Istrate G(2021)Game-Theoretic Models of Moral and Other-Regarding Agents (extended abstract)Electronic Proceedings in Theoretical Computer Science10.4204/EPTCS.335.19335(213-227)Online publication date: 22-Jun-2021
https://doi.org/10.4204/EPTCS.335.19
Peters MTroncoso-Valverde C(2013)A folk theorem for competing mechanismsJournal of Economic Theory10.1016/j.jet.2013.01.001148:3(953-973)Online publication date: May-2013
https://doi.org/10.1016/j.jet.2013.01.001
van der Hoek WWitteveen CWooldridge M(2011)Program equilibrium—a program reasoning approachInternational Journal of Game Theory10.1007/s00182-011-0314-642:3(639-671)Online publication date: 11-Dec-2011
https://doi.org/10.1007/s00182-011-0314-6
Chen H(2011)Bounded rationality, strategy simplification, and equilibriumInternational Journal of Game Theory10.1007/s00182-011-0293-742:3(593-611)Online publication date: 19-Jul-2011
https://doi.org/10.1007/s00182-011-0293-7

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Computing equilibria in discounted dynamic games

Set-valued games and mixed-strategy equilibria in discounted supergames

Computing Equilibria in Discounted 2 × 2 Supergames