| paper | d4-conf-atal-2015-0014 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: Polynomial-time solvable. · discrete side: polynomial · adjudication: proved
full proof & adversarial review →
Corollary 5
statement extracted from the paper’s text layer
Given a DAG \(D=(R,A)\) and rational masses \(\mu_{r,b}\ge 0\) for roles \(r\in R\) and initial opinions \(b\in\{0,1\}\), with \(\sum_{r,b}\mu_{r,b}=1\), each member of role \(r\) is influenced by every member of each predecessor role \(u\) with \((u,r)\in A\). Starting from \(x_r^0=\mu_{r,1}\), let \(q_r=\mu_{r,0}+\mu_{r,1}\); at each step, role \(r\) adopts opinion \(1\) if predecessor opinion-1 mass is a strict majority, adopts \(0\) if it is a strict minority, and retains its current opinion mass on a tie. Compute the exact terminal opinion masses \(x_r^*\) and \(q_r-x_r^*\) for all roles.
Types are \((r,b)\), where \(r\) is a role in the DAG and \(b\in\{0,1\}\) is initial opinion, with rational population mass \(\mu_{r,b}\). The input also gives the DAG \(D=(R,A)\); all members of a role share its predecessor cohorts as influencers and use majority updates with tie retention. The task is to compute the exact terminal mass of each opinion in each role, with running time polynomial in \(|R|\), \(|A|\), the support size \(\tau\), and the input bit length \(L\).
The mirror’s rational-mass algorithm is a direct compressed simulation and does not engage the continuous-optimization toolbox that motivates part of ChoCo; this may limit its priority, though it does not undermine the model fit.
fatal: False
Covers Corollary 5 for single-issue majority updates on block-structured DAGs, with role and initial opinion defining types. It leaves the corollary’s arbitrary acyclic influence graphs and other ballot-monotonic aggregation procedures, as well as the paper’s cyclic-network results and majoritarian source formula, outside the mirror.
The strongest honest mirror is the paper’s computation of opinion diffusion on acyclic networks. The paper gives no named NP-hardness result, so there is no hardness anchor here: Corollary 5 is an algorithmic result, proved in the paper from its convergence theorem and algorithm.
Continuous DAG Opinion Diffusion. Consider a large organization debating one yes/no policy question. Its members occupy a finite set of roles \(R\), connected by a directed acyclic graph \(D\). Every member of role \(r\) is influenced by every member of the same predecessor roles, \(\mathrm{Pred}(r)\), and updates by majority; on a tie, they retain their current opinion. A type is a role and an initial opinion, \((r,b)\) with \(b\in\{0,1\}\). Its mass \(\mu_{r,b}\) is the fraction of the whole population of that type, with rational masses summing to \(1\). Thus \(q_r=\mu_{r,0}+\mu_{r,1}\) is the population share of role \(r\), and the support size \(\tau\) is at most \(2|R|\).
At time \(t\), let \(x_r^t\) be the mass in role \(r\) currently holding opinion \(1\). If \(r\) has predecessors, compare \(\sum_{u\in\mathrm{Pred}(r)}x_u^{t-1}\) with half the total predecessor mass. A strict majority sets \(x_r^t\) to \(q_r\) or \(0\); a tie leaves \(x_r^t=x_r^{t-1}\). Roles with no predecessors retain their initial opinions. The problem is to compute the exact final mass of each opinion in each role. There is no optimization objective: the computational task is to find the population state at convergence.
The anchor is Corollary 5, proved here: if the influence graph \(E\) is acyclic and the aggregation rule \(F\) is ballot-monotonic and polynomial-time computable, then the opinion profile \(B^*\) at convergence can be computed in polynomial time. The mirror uses its single-issue majority case. It keeps the paper’s binary opinions, discrete update times, majority behavior, and final-state computation; it continuizes the population. With the role graph and rational masses as input, a prover can simulate the mass update for at most \(|R|+1\) rounds, summing and comparing rational masses. This gives a polynomial-time algorithm in \(|R|\), \(|D|\), \(\tau\), and the input bit length \(L\). I expect this mirror to be Class A: tractable.
The regime is a large membership organization or workforce with, say, hundreds of thousands of members but only dozens of reporting roles. Members in the same role share the same incoming channels and update rule; their initial yes/no stances are represented by two masses. This is a high-multiplicity setting: the population is large while the number of types is small. The fit to the authors’ problem is direct. For any common denominator of the input masses, expand each mass into that many discrete agents and connect every predecessor cohort to every recipient in the role. The resulting individual-level graph is a DAG, and its majority updates reproduce exactly the normalized mass dynamics. The continuous version is therefore a compressed form of their convergence-computation problem, not continuous opinions or continuous time.
The scope is deliberately limited to the acyclic computation result. It does not cover their results about cyclic networks, general multi-issue constraints, or the formula for majoritarian diffusion on resolute DAGs. The next questions would be whether useful mass-based convergence conditions extend to cyclic role graphs, and how the mirror changes when roles have different aggregation rules or different influence channels across issues.
The weakest point is the shared-neighborhood assumption. This mirror fits organizations where everyone in a role receives input from whole predecessor cohorts; it does not preserve arbitrary person-by-person influence networks. That restriction narrows the result, but it describes a recognizable regime and matches the paper’s acyclic-network problem closely. The result would establish efficient computation in that high-multiplicity regime; since the paper gives no hardness anchor, it would not show that continuization removes discrete hardness.
The strongest case against this mirror is its narrowness. Corollary 5 covers arbitrary acyclic influence graphs and ballot-monotonic update rules. The proposed mirror keeps only one issue, majority updates, and networks where everyone in a role has the same incoming cohorts. It replaces the paper’s individual-level profile with masses, so the algorithm is essentially a layer-by-layer simulation on the quotient graph. That is a modest result, with little reach into arbitrary influence networks and no apparent need for the continuous-optimization tools ChoCo hopes to bring into view.
That limits the mirror’s scope, but it does not defeat it. A large organization with a small number of roles and shared broadcast channels is a plausible high-multiplicity regime. Role and initial opinion are enough to describe the types; tie retention is captured by retaining the mass of each opinion. For rational masses, expanding them using a common denominator yields a finite DAG whose updates reproduce the mass dynamics exactly. The final type-level opinion masses remain meaningful and need not be trivial.
A stronger version could define types by role, initial opinion, and update rule, with each role receiving input from whole predecessor types. This preserves the same exact compression while allowing more heterogeneity. The restriction to block-structured networks remains, but the programme treats high multiplicity as an instance regime, so that restriction alone is not disqualifying. Existing analytic work on opinion dynamics also does not settle this computational question.
So the negative case can make this a low-priority or narrow mirror. It cannot honestly establish that no worthwhile continuous mirror exists: the Corollary 5 mirror survives the strongest objections available here.
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.