Program Equilibria and Discounted Computation Time

Lance Fortnow

No 1473, Discussion Papers from Northwestern University, Center for Mathematical Studies in Economics and Management Science

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 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.

Keywords: brokers; applied mechanism design; linear commission fees; optimal indirect mechanisms; internet auctions; auction houses. (search for similar items in EconPapers)
JEL-codes: C72 C78 L13 (search for similar items in EconPapers)
Date: 2008-11
New Economics Papers: this item is included in nep-cmp and nep-gth
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.kellogg.northwestern.edu/research/math/papers/1473.pdf main text (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:nwu:cmsems:1473

Ordering information: This working paper can be ordered from

Access Statistics for this paper

More papers in Discussion Papers from Northwestern University, Center for Mathematical Studies in Economics and Management Science Center for Mathematical Studies in Economics and Management Science, Northwestern University, 580 Jacobs Center, 2001 Sheridan Road, Evanston, IL 60208-2014. Contact information at EDIRC.
Bibliographic data for series maintained by Fran Walker ( this e-mail address is bad, please contact ).