The DOI matches its Crossref record; 3 of the 3 references it cites were found in a registry or an index.
A PARAMETRIC, RESOURCE-BOUNDED GENERALIZATION OF LÖB’S THEOREM, AND A ROBUST COOPERATION CRITERION FOR OPEN-SOURCE GAME THEORY
Abstract
This article presents two theorems: (1) a generalization of Löb’s Theorem that applies to formal proof systems operating with bounded computational resources, such as formal verification software or theorem provers, and (2) a theorem on the robust cooperation of agents that employ proofs about one another’s source code as unexploitable criteria for cooperation. The latter illustrates a capacity for outperforming classical Nash equilibria and correlated equilibria, attaining mutually cooperative program equilibrium in the Prisoner’s Dilemma while remaining unexploitable, i.e., sometimes achieving the outcome (Cooperate, Cooperate), and never receiving the outcome (Cooperate, Defect) as player 1.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Citations
Cites
Boolos, G. (1984) · Cambridge University Press eBooks · doi:10.1017/cbo9780511625183 · Cited by 437
Pudlák, P. (1998) · Studies in logic and the foundations of mathematics · doi:10.1016/s0049-237x(98)80023-2 · Cited by 130
Program equilibria and discounted computation time
Fortnow, L. (2009) · doi:10.1145/1562814.1562833 · Cited by 14
Flagged first, then by citations
Cited by
Sorted by citations
Open Problems in Cooperative AI
Dafoe, A., Hughes, E., Bachrach, Y., Collins, T., McKee, K. R., Leibo, J. Z., Larson, K., & Graepel, T. (2020) · arXiv · doi:10.48550/arxiv.2012.08630 · Cited by 93
The alignment problem from a deep learning perspective
Ngo, R., Chan, L., & Mindermann, S. (2022) · arXiv · doi:10.48550/arxiv.2209.00626 · Cited by 68
“Three specific gaps exist in frameworks which this work aims to address: firstly, real-world agents act in environments which may contain copies of themselves [Critch, 2019, Levinstein and Soares, 2020].”
BackgroundSafe Pareto improvements for delegated game playing
Oesterheld, C., & Conitzer, V. (2022) · Autonomous Agents and Multi-Agent Systems · doi:10.1007/s10458-022-09574-6 · Cited by 4
“We could similarly use the variant proposed by Fortnow [15], techniques based on Löb’s theorem [5, 13], or -grounded mutual simulation [36] or even (meta) Assurance Game preferences (see Appendix 2).”
BackgroundMethodGame-theoretic Models of Moral and Other-Regarding AgentsPreprint
Istrate, G. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2012.09759 · Cited by 3
Learning in two-player games between transparent opponentsPreprint
Hutter, A. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2012.02671 · Cited by 5
Game-Theoretic Models of Moral and Other-Regarding Agents (extended abstract)
Istrate, G. (2021) · Electronic Proceedings in Theoretical Computer Science · doi:10.4204/eptcs.335.19 · Cited by 1
The Social Contract, the Game of Life and the Shadow of the Future
Skyrms, B. (2022) · Homo Oeconomicus · doi:10.1007/s41412-022-00119-6
Metadata
- Authors
- CRITCH, A.
- Affiliations
- Machine Intelligence Research Institute (US)
- Corresponding author
- CRITCH, ANDREW
- Venue
- The Journal of Symbolic Logic
- Publisher
- Cambridge University Press (CUP)
- Published
- 2019-04-02
- Volume
- 84
- Issue
- 4
- Pages
- 1368-1381
- ISSN
- 0022-4812 (ISSN-L)
- 1943-5886
- OpenAlex
- W2932862961
- Cited by
- 6
- References
- 3
- Citations by year
- 2022: 2 · 2021: 1 · 2020: 3
- FWCI
- 0.69
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- Journal of Symbolic Logic (publishedVersion)
- Topics
- Physical Sciences › Computer Science › Artificial Intelligence › Logic, Reasoning, and Knowledge
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Computability, Logic, AI Algorithms
- Social Sciences › Decision Sciences › Management Science and Operations Research › Game Theory and Applications
- Keywords
- Löb's theorem, formal proof systems, formal verification, theorem provers, prisoner's dilemma, Nash equilibrium, correlated equilibrium, game theory
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
