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 payos 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)
New Economics Papers: this item is included in nep-cmp and nep-gth
Date: 2008-11

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: http://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
Address: 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.
Series data maintained by Fran Walker ().