Characterising Simulation-Based Program Equilibria

The strongest honest case is narrow, and it rests on Theorem 4, proved in this paper (with the full proof in Appendix K of the long version). The theorem says that correlated \(\epsilon_i\)Grounded\(\pi_i\)Bots can have infinite expected runtime without memoization when at least two \(\epsilon_i<1/2\), but with memoization their expected runtime is finite and polynomial in \(1/\min_i\epsilon_i\), assuming the policies run in polynomial time in the simulated history length.

The paper has no named NP-hardness, membership-in-P, FPT, or approximation-complexity theorem. Its Corollary 1, Theorem 7, and Theorem 8 are important equilibrium-existence and impossibility results, but under ChoCo’s strict anchor rule they are not computational anchors. I would therefore use only Theorem 4 and avoid padding the case.

A plausible high-multiplicity regime is a large deployment of mutually transparent AI agents or smart contracts. There are \(n\) roles in each interaction, and millions of instances of each role are deployed in parallel. Agents in the same role share the same source code, \(\epsilon\), policy, randomisation convention, and execution environment. A public randomness beacon supplies the shared random sequence required by the correlated version. The number of agents is enormous, but the number of distinct program types is small.

Here is the concrete mirror I would propose:

Runtime-Constrained Simulation-Program Mass Design\(_\infty\).

For each role \(i\), the input gives a finite set \(T_i\) of certified program types. A type contains the complete source code of a correlated \(\epsilon\)Grounded\(\pi\)Bot, its rational \(\epsilon>0\), its policy, and whether memoization is installed. The input also gives a rational baseline population distribution \(\bar\mu_i\in\Delta(T_i)\), reprogramming costs \(\gamma_i(t,t')\), a payoff floor \(v_i\), a runtime budget \(B\), and a cost bound \(K\).

A match samples one type \(t_i\) independently from each role’s distribution. The programs then interact exactly as in the paper: they see the other programs’ source codes, recursively simulate them, and receive the shared random sequence. The population distribution is not revealed to the programs.

The decision variable is a mass-transfer matrix \(x^i_{t,t'}\), where \(x^i_{t,t'}\) is the fraction of role-\(i\) agents reprogrammed from \(t\) to \(t'\). This induces

\[ \mu_i'(t)=\bar\mu_i(t)-\sum_{t'}x^i_{t,t'}+\sum_{t'}x^i_{t',t}. \]

The objective is to minimize

\[ \sum_{i,t,t'}\gamma_i(t,t')x^i_{t,t'}. \]

The resulting population must satisfy three conditions.

First, it must be a population program equilibrium. If \(U_i(q;\mu'_{-i})\) denotes the expected payoff of a role-\(i\) agent that submits program type \(q\) against independently sampled opponent types, then every type with positive mass must be a best response:

\[ \mu_i'(q)>0 \quad\Longrightarrow\quad U_i(q;\mu'_{-i})=\max_{r\in T_i}U_i(r;\mu'_{-i}). \]

A deviation still changes the source code seen by the opponents, so this preserves the paper’s central source-transparency feature.

Second, the average payoff \(V_i(\mu')\) of every role must be at least \(v_i\).

Third, the expected simulation work per match must be at most \(B\):

\[ R(\mu')= \sum_{t_1,\ldots,t_n} \left(\prod_i\mu_i'(t_i)\right) \mathbb E\!\left[ \sum_i\operatorname{time}_{\mathrm{memo}} (p_{t_1},\ldots,p_{t_n}) \right] \le B. \]

A solution is the transfer matrix \(x\), together with the induced type masses, satisfying these conditions and having cost at most \(K\).

This is a genuine population model rather than fractionalising an individual action. Each agent still submits one complete program and outputs one ordinary game action. Only the fraction of deployed agents of each program type is continuous. Clearing denominators in \(\mu_i\) gives a finite fleet of identical clones, so the high-multiplicity bridge is explicit.

Theorem 4 gives this problem a real computational foothold. If a positive-mass set of matches contains two low-\(\epsilon\) uncached bots, the aggregate expected runtime inherits the theorem’s infinite-runtime branch. With memoization, every selected profile has finite expected runtime bounded polynomially in the smallest \(\epsilon\), subject to the paper’s policy-runtime assumption. Thus the population question has a meaningful operational boundary: a tiny mass of dangerous program types can create infinite expected service cost, while memoization removes that recursion explosion.

I would expect the fixed-profile runtime-evaluation subproblem to be Class A when \(n\), the type catalogue, and polynomial runtime certificates are fixed or explicitly bounded. The full mass-design problem is more plausibly a Class C/open problem: its expected runtime and equilibrium constraints are multilinear in the type masses, and the source-dependent deviations may require a configuration or separation formulation. Theorem 4 does not prove polynomial solvability of this new optimization problem.

The weakest point is substantial: the original paper studies one \(n\)-player program game, whereas this mirror introduces random matching among many role-specific populations. It is therefore an author-recognisable extension, not a direct replacement of player counts by masses. The atomless equilibrium notion also needs care: an individual deviation does not change the population distribution, so the finite-\(N\) interpretation should require convergence or clone-stability, not merely invoke ordinary Nash equilibrium.

Still, the extension is grounded in the paper’s own motivating applications—large populations of transparent AI agents, prompts, and smart contracts—and it preserves the paper’s distinctive computational object: recursive source-code simulation with nontrivial halting and runtime behaviour. If ChoCo requires a named discrete decision/complexity theorem rather than an algorithmic runtime theorem, then the paper has no qualifying anchor; under that stricter reading, this remains a worthwhile follow-up problem but not a fully anchored mirror.