| paper | d4-conf-atal-2015-0310 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
P→P discrete result → its continuous mirror
Answer: The feasibility problem is in \(\mathrm P\): every promised instance admits an intervention with \(m\tau\) cohorts that reaches a stable profile with strict global winner \(\omega\) after one simultaneous update. · discrete side: polynomial · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given a known poll, target candidate \(\omega\), and a finite distribution of positive mass over voter types that specify strict rankings and bounded integer counts of initial neighbors by type, find a finite split into cohorts and an integer balanced table of added links so that the paper’s update process reaches a stable profile in which \(\omega\) wins. Consider societies where each candidate has positive mass of first-round supporters and more than \(1/m\) of the population does not rank \(\omega\) last.
A finite-type population with rational masses; each individual keeps a ranking, an integer local view, and the paper’s strategic update rule. The organizer chooses balanced links among cohorts, while the winner is determined by aggregate ballot mass. Individuals still have finite neighborhoods, so the strategic solution concept does not shift to a nonatomic or Wardrop game.
The finite construction uses a vanishing set of seeds whose degrees can grow with population size; replacing them with positive-mass roles changes that regime, and reproducing the construction with balanced links remains to be shown.
fatal: False
The mirror covers Theorem 3’s known-poll INFLUENCE result under bounded-degree and positive-mass supporter conditions. It leaves Theorem 6’s unknown-poll result, the heuristic, and the experiments aside.
My lead is a known-poll, role-symmetric continuum version of INFLUENCE. The scenario is a large party electorate or platform community: there are many voters but relatively few recurring combinations of preference and network role. A type records a voter’s complete ranking and the finite local information profile that determines how the voter responds: for example, the number of initial neighbors of each type. Agents of the same type are interchangeable for everything this model uses. The organizer still changes communication links, and voters still cast ordinary Plurality ballots.
Here is the continuous problem I would hand to a prover. The input has a finite set of types \(T\), rational masses \(\mu_t>0\) summing to \(1\), a candidate set and tie-breaking order, and a known poll score \(s_{\mathrm{poll}}(c)\) for each candidate \(c\). Each type \(t\) has a strict ranking and an integer vector of initial neighbor counts by type. These counts must describe a realizable undirected, finite-degree network: the mass-weighted number of links from type \(t\) to type \(u\) equals the mass-weighted number in the reverse direction. The intended regime has a bounded initial degree for every type.
Call the problem Typed Continuum INFLUENCE. An intervention may split a type’s mass into finitely many rational-mass cohorts, then specify an integer number of new neighbors each cohort member gets from every other cohort. The link counts must balance in both directions, so they can be realized as simple networks in sufficiently large finite blow-ups. Starting with sincere ballots, every cohort follows the paper’s update rule using the exact integer count of its neighbors’ votes plus the public poll. A solution is such a link plan whose process reaches a stable profile and whose winner by total ballot mass is \(\omega\), with the paper’s tie-breaking rule. The direct problem is to find any such finite-cost plan. Its natural optimization companion minimizes added link mass per voter, \(K=\frac12\sum_{a,b}\nu_a k_{ab}\), where \(\nu_a\) is cohort \(a\)’s mass and \(k_{ab}\) its new-neighbor count from cohort \(b\). The optimization companion is not what the theorem below claims.
This keeps the strategic details that matter. Each individual still has finitely many neighbors and casts one ballot; the poll remains a finite score vector; only the society’s aggregate size is continuous. Fractional cohort masses describe population shares, not fractional voters. The added-link table is a type-symmetric way to express the organizer’s edge choices without naming individuals.
The anchor is Theorem 3, proved in this paper using Algorithm 2. For known-poll Plurality INFLUENCE, the input is a finite voter set with preferences, an initial social network, poll scores, and a target candidate \(\omega\); the task is to find edges to add so that \(\omega\) wins the iterative process. The theorem states that this can be done in polynomial time under three conditions. With \(d\) the degree bound, \(z=\max(6(m-1),2(\max\Delta+d+1))\), and \(n'=n-zm^3\): (1) at least a fraction \(p\) of affected voters have degree at most \(d\), where \(1-2\max\Delta/n'<p\leq1\); (2) at least a fraction \(p_\omega\) of affected voters have degree at most \(d\) and do not rank \(\omega\) last, where \(p_\omega>\max(1/m,1-p)\); and (3) each candidate has at least \(zm^2\) bounded-degree first-round supporters, with at least a \(1/m\) fraction of those supporters having no neighbor of degree greater than \(d\). This is a result proved here, not a cited theorem.
The continuous mirror covers that known-poll influence result in a high-multiplicity regime with positive mass for each candidate’s supporter types. For fixed \(m\) and poll, \(n'\) grows with \(n\), so the first condition pushes \(p\) toward \(1\); the cleanest regime is that essentially all initial degrees are bounded. The second condition becomes a strict share condition: more than \(1/m\) of the population does not rank \(\omega\) last. Positive supporter mass for every candidate supplies the finite supporter sets required by the theorem in sufficiently large blow-ups. A plausible setting is a large election where voters fall into a modest number of preference and communication-role classes, and an organizer can introduce voters across those classes. This is a property of that regime, not a claim about every social network.
I expect the promised, type-symmetric version to be tractable. The finite theorem already gives a constructive intervention on every sufficiently large blow-up satisfying the strict mass conditions. A continuous proof would need to turn those constructions into balanced link tables while preserving each cohort’s integer local view and stable behavior. That seems like the right Class A question for this anchor. The theorem itself does not establish polynomial-time solvability for the table-encoded continuum problem, and it does not minimize \(K\).
The weakest point is substantive: Algorithm 2 uses a finite stock of supporters as seeds and reuses them to affect many voters. In finite instances those seed voters can acquire degree proportional to \(n\). A continuum model with only positive-mass types cannot represent a finite set of influential agents as ordinary population mass. The mirror above addresses this by allowing positive-mass supporter cohorts and balanced link allocation, but showing that this reproduces the seed construction without changing its strategic effect is required work. If the authors require an exact scaling limit of every finite instance covered by Theorem 3, this case is weaker. If they accept a regularized, high-multiplicity regime of the same link-addition problem, it remains a credible continuous analogue.
The scope is deliberately narrow: this mirrors Theorem 3’s known-poll INFLUENCE result. The paper’s heuristic aims to reduce the number of added edges, but it is not the anchor here; nor am I claiming to mirror the separate unknown-poll theorem. The other continuous objects are unchanged: candidates and ballots stay discrete, Plurality stays the rule, and the population is the object represented by masses.
Theorem 3 is a genuine computational result, so there is no decisive “nothing here to mirror” objection. The strongest case against its mirror is that the theorem’s mechanism is unusually tied to a few exceptional vertices and their individual links.
For fixed \(m\) and a fixed poll, \(z m^2\) is constant, so Theorem 3 requires only a constant number of first-round supporters for each candidate. Its degree condition also forces the fraction of affected voters with degree above \(d\) to be \(O(1/n)\). The construction can therefore use a vanishing set of seed voters to influence a linear number of ordinary voters. A distribution over positive-mass types does not represent those seeds as stated: it replaces them with positive-mass supporter cohorts and a regular pattern of links. That is a legitimate regime, but it is a more symmetric network-design problem than the one that makes this theorem striking.
The best repair is to give the seed roles a small positive mass and allow them high, but fixed, degree. For any fixed seed share \(\varepsilon>0\), the organizer can potentially reproduce the construction with degrees on the order of \(1/\varepsilon\), while the seed votes contribute only \(\varepsilon\) to the electorate. That makes the proposed mirror plausible, and the authors could reasonably recognize it as INFLUENCE. But it does not reproduce the theorem’s vanishing-seed regime in a single continuous instance: taking \(\varepsilon\) to zero also sends those role degrees to infinity. The mirror must either accept a fixed positive seed share or add exceptional zero-mass agents whose degree grows with population size.
There is a second squeeze. The proponent’s balanced link tables capture a carefully symmetric setting where every member of a cohort has the same local view. For a general sparse network, the process depends on how neighbors are arranged and on their later behavior, not just on aggregate link counts. Preserve that topology and the type support can grow with the electorate, losing the compression that motivates continuization. Replace it with a table or graphon and the question becomes one about regular or dense network structure, with different local information and potentially different poll scaling. Those are reasonable modelling choices, but neither follows automatically from making the population continuous.
So the negative case is that the most faithful mirror needs a hybrid population with a few exceptional agents, while the cleanest finite-type mirror restricts the network enough that it may mainly re-express the paper’s construction. This is not airtight: a small positive mass of high-degree roles is plausible, and its compressed complexity could itself be worth studying. The case against is therefore weak on the programme’s own standard. Theorem 3 has a credible continuous mirror; the concern is that its most distinctive behavior may be lost or require extra graph structure in the passage to mass types.
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.