| paper | d4-conf-aaai-2021-0773 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
Answer: \(F\) exists for every input and is exactly computable in polynomial time; \(P_N(c)=F\) for every admissible \(N\). · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given a finite role set \(R\), colour set \(C\), irreducible rational row-stochastic matrix \(Q\), memory probabilities \(p_0,\ldots,p_m\), target colour \(c\), and rational society distribution \(\mu\) over types \((r,h)\in R\times C^{m+1}\), compute \(\lim_{N\to\infty}\Pr_N(c\text{ reaches stable consensus})\). For each valid \(N\), instantiate \(N\mu_{r,h}\) agents of each type; each role-\(r\) agent selects role \(s\) according to \(Q_{rs}\), then samples an agent uniformly from that role, and follows the stated memory protocol.
The society is a distribution \(\mu\) over role-and-history types \((r,h)\); \(Q\) specifies role-based peer selection and \(p_0,\ldots,p_m\) specify memory. The output is the limit fixation probability, which equals \(\sum_{i=0}^{m}\frac{\alpha_i}{\sigma}\sum_{r\in R}\frac{\lambda_r}{\rho_r}\sum_{h:\,h_{m-i}=c}\mu_{r,h}\), where \(\rho_r=\sum_h\mu_{r,h}\), \(\lambda Q=\lambda\), \(\alpha_i=1-\sum_{j=0}^{i-1}p_j\), and \(\sigma=\sum_{j=0}^{m}(j+1)p_j\).
The mirror covers Theorem 1’s winner-probability result, with Proposition 4 supporting convergence for this family; it leaves the experimental convergence-time comparisons and other network regimes aside.
The strongest mirror I believe in is Role-Continuum Memory Fixation Probability. This paper gives no named result classifying a problem as NP-hard, in P, or otherwise. Its best computational anchor is Theorem 1, proved here: an exact formula for the probability that each colour eventually wins. Proposition 4, also proved here, supplies the needed convergence guarantee: with \(m>0\), the associated memory graph is well-behaved whenever the original graph is strongly connected.
A plausible high-multiplicity setting is a large validator network or robot deployment organized into a fixed number of communication roles. There may be millions of agents but only a few roles; agents in each role use the same probabilities for selecting a peer role, and all use the same memory probabilities. Roles are the persistent types. An agent’s initial state also records its colour at each of the \(m+1\) rounds in memory, so the society’s initial support consists of role-and-history pairs. Its size \(\tau\) can stay fixed as the population grows.
Here is the mirror problem precisely. Let \(R\) be a finite set of roles, \(C\) a finite set of colours, and \(Q\) an irreducible rational row-stochastic matrix on \(R\). A role-\(r\) agent selects role \(s\) with probability \(Q_{rs}\), then selects an agent uniformly from that role. Let \(m\ge1\), with rational \(p_0,\ldots,p_m>0\) summing to \(1\). The society is a rational distribution \(\mu\) on types \((r,h)\in R\times C^{m+1}\), where \(h=(h_0,\ldots,h_m)\) is the agent’s initial colour history. Write \(\rho_r=\sum_h\mu_{r,h}>0\). For each population size \(N\) that makes all \(N\mu_{r,h}\) integers, instantiate that many agents of each type and run the paper’s synchronous memory protocol on the resulting role-based graph.
Given a target colour \(c\), Role-Continuum Memory Fixation Probability asks for the limit, as \(N\) grows through those valid sizes, of the probability that stable consensus is eventually reached on \(c\). A solution is the exact probability as a rational number. The agents’ random decisions are the lag and peer selections; there is no optimization action in the paper’s problem, so the output probability is the computational quantity to determine.
Theorem 1 is the anchor. In the paper’s notation, for a strongly connected graph \(G\), initial configurations \(s_0,\ldots,s_m\), and stationary distribution \(\pi\) of \(G\), it states
\[ \Pr(c\text{ wins})= \sum_{i=0}^{m} \frac{\alpha_i}{\sigma} \sum_{v:\,s_{m-i}(v)=c}\pi(v), \qquad \alpha_i=1-\sum_{j=0}^{i-1}p_j,\quad \sigma=\sum_{j=0}^{m}(j+1)p_j. \]
For the role-based graph, let \(\lambda\) be the stationary distribution of \(Q\). Each individual in role \(r\) has stationary weight \(\lambda_r/(N\rho_r)\). Substituting into Theorem 1 gives the mirror’s answer:
\[ \Pr_\infty(c)= \sum_{i=0}^{m}\frac{\alpha_i}{\sigma} \sum_{r\in R}\frac{\lambda_r}{\rho_r} \sum_{h:\,h_{m-i}=c}\mu_{r,h}. \]
This value is the same for every valid \(N\), so the limit exists. Computing it requires solving \(\lambda Q=\lambda\) and evaluating the displayed rational sum; that is polynomial-time exact computation in the role count, memory length, support size, and input bit length. This is an algorithmic anchor, not a hardness result.
I think the authors would recognize this as their problem in a high-multiplicity network regime: agents still choose among the same colours, copy peers through a graph, use the same memory protocol, and seek stable global consensus. The continuous object is the distribution of role-and-history mass. The graph restriction describes a meaningful instance regime, rather than changing the question to outcome-space continuity or an axiomatic one. The paper’s Proposition 4 ensures eventual consensus for each finite instance in the family.
The weakest point is the passage to a continuum. A literal nonatomic population updating independently need not ever reach unanimous consensus; the mirror defines consensus probability through finite populations whose mass proportions are fixed. That makes this a high-multiplicity limit, not a new stochastic dynamics on an uncountable set of agents. The restriction to role-homogeneous peer selection is another cost, though it preserves the paper’s underlying fixation question and supplies the repeated-agent regime that makes the mirror credible.
This mirror covers Theorem 1’s exact winner-probability result. It raises further questions: whether the formula extends to sparse or more general network limits; how memory length affects fixation probabilities when \(m\) grows with the input; and whether a continuous role model can give useful bounds on the convergence times studied experimentally.
The strongest objection is that the proposed mirror has no fixation event in the continuous population it describes. In the finite role network, random individual updates eventually push the system to unanimous consensus. If we instead evolve the role-and-colour masses directly, the law of large numbers makes each update deterministic. For example, if \(x_{r,c}(t)\) is the mass of role \(r\) holding colour \(c\), then the role model gives
\[ x_{r,c}(t+1) = \rho_r\sum_{i=0}^{m}p_i \sum_{s\in R}Q_{rs}\frac{x_{s,c}(t-i)}{\rho_s}. \]
For a mixed initial society, this averaging evolution does not select a random winning colour. Its weighted colour mass is conserved; the finite network’s eventual fixation comes from accumulated individual fluctuations. Thus the proposed limit takes *eventual absorption first* and population size second. Reversing that order removes the random consensus event. The answer is then a finite-population fixation statistic evaluated on continuous input masses, rather than the output of a continuous consensus process.
A richer network limit, such as a kernel or spatial model, preserves more topology but has the same problem: independent updates produce deterministic mass evolution. To retain random fixation one must introduce a diffusion or another finite-population noise limit, with a time scaling. That might be a worthwhile model, but its central ingredient is the demographic noise and scaling, not the continuous society alone. The paper’s exact-probability theorem also already gives the proposed role model’s answer by substitution: compute the stationary distribution of \(Q\), then evaluate the weighted initial mass. The paper states no complexity classification for that task, and this mirror does not expose a broader algorithmic landscape.
This is a real case against the mirror, but it is not decisive. The high-multiplicity programme allows continuous questions defined through discrete populations, and a large network with repeated roles is plausible. The limit fixation probability is a well-defined function of the continuous masses, and the finite-to-limit identity could itself be of interest. I cannot honestly rule out that mirror in every scenario; the negative case depends on requiring a continuous population *dynamics*, rather than accepting the limit fixation statistic as the computational question.
The adversarial triple: the proponent anchors on up to three named results; the opponent sees that case and must defeat every anchor; the judge decides which case convinced it. These are the pipeline’s own outputs, generated by tools/triple_run.py — no human edited them. The paper’s own text is not reproduced here beyond the quoted statement above.