Open problem MAIS-O17 · posed in MAIS-A1 as Question 4.9 · Status: open.
Tags: cooperative AI · open-source game theory · program equilibrium · Löbian cooperation · bounded rationality · logic · complexity theory. Difficulty: ★★.
Authored by: Claude Fable 5 directed by Lionel Levine · Audited by: GPT 5.6 Sol.
Two copies of Critch's $\mathrm{FairBot}_k$ [C19] — the agent that searches all proofs of at most $k$ symbols for a proof that its opponent cooperates against it, cooperating if the search succeeds and defecting otherwise — cooperate in the Prisoner's Dilemma once the proof budget $k$ passes a threshold. That is one point of a landscape: over all pairs of transparent agents of bounded description length, how fast does the cooperation threshold grow? If the threshold grows polynomially, mutual source-code transparency is a workable mechanism for cooperation between AI systems; if it explodes, transparency alone does not scale.
The setting is the program game version of the Prisoner's Dilemma: each player is an algorithm handed the other's source code, playing $\mathsf{C}$ (cooperate) or $\mathsf{D}$ (defect), with provability read in a fixed efficient proof system $S$ and all proof lengths counted in symbols. Löbian cooperation of unbounded such agents is due to Barász et al. [BCFH+14]; Critch's bounded criterion [C19] applies to agents that are fair relative to a proof-budget function $G$: the agent provably cooperates whenever its opponent's cooperation has a proof within the budget that $G$ allots. For agent families $A = (A_k)$ and $B = (B_k)$, a uniform $G$-fairness implication for $A$ is this criterion certified once for the whole family: a single $S$-proof that for every $k$, if $B_k(A_k) = \mathsf{C}$ has an $S$-proof of at most $G(k)$ symbols, then $A_k(B_k) = \mathsf{C}$.
In the statement, $G$ is such a budget function, implemented as a term of the agenda's search-free budget algebra $\mathcal{B}$ — explicit arithmetic terms in $k$, with no proof-search operators, whose totality and monotonicity $S$ proves; the exact grammar is in MAIS-A1. The quantities $\mathcal{E}_S$ and $d_S$ are the system's expansion and diagonalization costs — the worst-case proof-length price of internalizing "$\varphi$ has a proof of at most $m$ symbols," and of the fixed-point equivalences the diagonal lemma produces; determining both constants is MAIS-O12, which states the definitions in full. In the statement's last sentence, $\mathcal{E}$ without a subscript denotes a chosen expansion function with an $S$-verifiable presentation, and $f \succ g$ means $f$ eventually dominates every constant multiple of $g$.
Question (MAIS-A1, Question 4.9). Fix a canonical $\mathcal{B}$-term implementation of $G$. A uniform agent family is one generator program taking $k$ as input. For a pair of such families $(A, B)$, let $r(A,B)$ be the least $K$ such that $A_k(B_k) = B_k(A_k) = \mathsf{C}$ for all $k \ge K$. Let $r_G(\ell, L)$ be the maximum of $r(A,B)$ over pairs whose two generators have at most $\ell$ symbols and whose uniform $G$-fairness implications have proofs of at most $L$ symbols, with maximum of the empty set equal to $0$.
Once the repaired cooperation theorem applies, $r_G(\ell, L)$ is finite because only finitely many generators and certificate proofs meet these bounds. Give an effective upper bound, and decide whether it is polynomial in $\ell + L$ under polynomial bounds on $\mathcal{E}_S$ and $d_S$. Compare the published condition $G(\ell) \succ \mathcal{E}(O(\ell))$ with the stronger proof-internal inequality in the earlier arXiv argument; in either form, use internal certificates rather than external growth alone.
In words: $r_G(\ell, L)$ is the worst cooperation threshold over all mutually fair agent pairs describable in $\ell$ symbols and certifiable in $L$; the question is whether transparency scales — whether the budget needed for cooperation grows only polynomially in the complexity of the agents. The repaired cooperation theorem is the certificate form of Critch's robust-cooperation theorem, with its budget comparisons proved inside $S$ rather than assumed from outside; it is what makes each $r(A, B)$ in the maximum finite, since the unrepaired form admits proof-search-dependent counterexamples. The refutation and repair are proved in MAIS-P2 [S26]. The closing comparison is between the journal version's external growth condition, quoted in the statement, and the stronger inequality internal to Critch's earlier arXiv argument; either is to be supplied as a certificate proved in $S$. For the cooperation theorem, the certificate conventions, and Critch's criterion, see MAIS-A1.
References
- [C19] A. Critch, A parametric, resource-bounded generalization of Löb's theorem, and a robust cooperation criterion for open-source game theory, Journal of Symbolic Logic 84 (2019), no. 4, 1368–1381. arXiv:1602.04184
- [BCFH+14] M. Barász, P. Christiano, B. Fallenstein, M. Herreshoff, P. LaVictoire, and E. Yudkowsky, Robust cooperation in the Prisoner's Dilemma: program equilibrium via provability logic, 2014. arXiv:1401.5577
- [S26] GPT 5.6 Sol, A refutation and a repair of Critch's PBL theorem, with an application to program cooperation, research note MAIS-P2, July 2026.
Related: MAIS-O16 (the single FairBot pair this generalizes) · MAIS-O15 (explicit thresholds in the underlying theorem) · MAIS-O20 (the same game for Payor's handshake).