The truth behind the myth of the folk theorem

DOI10.1145/2554797.2554847zbMath1366.68095arXiv1312.1017OpenAlexW2051773680WikidataQ127954818 ScholiaQ127954818MaRDI QIDQ5892456

Joseph Y. Halpern, Lior Seeman, Rafael Pass

Publication date: 19 May 2017

Published in: Games and Economic Behavior, Proceedings of the 5th conference on Innovations in theoretical computer science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1312.1017

zbMATH Keywords

repeated gamesbounded rationalityfolk theoremequilibrium computationcomputation of Nash equilibrium

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Noncooperative games (91A10) Games in extensive form (91A18) Multistage and repeated games (91A20)

Related Items (1)

A complete characterization of infinitely repeated two-player games having computable strategies with no computable best response under limit-of-means payoff

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Correlation through bounded recall strategies
• Equilibrium in supergames with the overtaking criterion
• Computing equilibria: a computational complexity perspective
• The myth of the folk theorem
• Probabilistic encryption
• A hierarchy of polynomial time lattice basis reduction algorithms
• Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
• Unmediated communication in repeated games with imperfect monitoring.
• Internal correlation in repeated games
• Online concealed correlation and bounded rationality
• (Leveled) fully homomorphic encryption without bootstrapping
• Homomorphic Encryption from Learning with Errors: Conceptually-Simpler, Asymptotically-Faster, Attribute-Based
• Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller
• Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP
• The complexity of computing a Nash equilibrium
• Trapdoors for hard lattices and new cryptographic constructions
• Toward Basing Fully Homomorphic Encryption on Worst-Case Hardness
• Evaluating Branching Programs on Encrypted Data
• Bounds for Width Two Branching Programs
• New directions in cryptography
• Sequential Equilibria
• A method for obtaining digital signatures and public-key cryptosystems
• A Pseudorandom Generator from any One-way Function
• Foundations of Cryptography
• The Folk Theorem in Repeated Games with Discounting or with Incomplete Information
• Fully homomorphic encryption using ideal lattices
• Public-key cryptosystems from the worst-case shortest vector problem
• Pseudorandom Knapsacks and the Sample Complexity of LWE Search-to-Decision Reductions
• Probability Inequalities for Sums of Bounded Random Variables
• New lattice-based cryptographic constructions
• Computational Complexity and Communication: Coordination in Two-Player Games
• Efficient Fully Homomorphic Encryption from (Standard) LWE
• On lattices, learning with errors, random linear codes, and cryptography
• On lattices, learning with errors, random linear codes, and cryptography

This page was built for publication: The truth behind the myth of the folk theorem