| paper | d4-journals-jair-2021-0005 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→NP-hard discrete result → its continuous mirror
Answer: Every strictly positive multiplicative approximation factor \(0<\rho(m,\tau,L)\leq1\) is NP-hard, already for \(m=3\); no such polynomial-time approximation exists unless \(\mathrm{P}=\mathrm{NP}\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 10
statement extracted from the paper’s text layer
Given a finite set of voter types \(T\), rational masses \(\mu_t>0\) summing to \(1\), strict score vectors, a positive-mass seed cohort sending one positive article on \(c_2\), a rational baseline contact-density matrix \(Q^0\), and an eligibility mask, choose a rational matrix \(Q\) with \(Q_{tu}\in[Q^0_{tu},1]\) on eligible pairs and \(Q_{tu}=Q^0_{tu}\) elsewhere. Interpret \(Q_{tu}\) as the probability that each possible directed contact from type \(t\) to type \(u\) is present, with certain transmission. In the dense-population limit, a type receives the article exactly when reachable from seed mass along type pairs with positive density. Maximize the gain in \(c_0\)’s vote margin over \(Q^0\), with complexity measured in \(|T|\) and the input bit length.
A population represented by masses \(\mu_t\) on voter types, with type-level baseline and eligible contact densities \(Q\). The platform chooses \(Q\); reachability determines which type masses receive the article, and the objective is the resulting increase in \(c_0\)’s plurality margin.
Theorem 10’s individual-edge reduction does not establish that its Set Cover construction preserves feasibility and approximation gains under dense type blocks: positive contact density saturates activation, and the finite seed set must become positive seed mass.
fatal: False
The mirror covers Theorem 10’s three-candidate, single-news-article, unitary-score-distance, unlimited-budget edge-addition result. It leaves the paper’s seeding and edge-removal results, other edge-addition settings, reoptimization results, and influence-optimization results outside the mirror.
My lead is Type-Block Edge-Addition Election Control. The anchor is Theorem 10, proved in this paper by reduction from Set Cover: for every constant \(\rho>0\), unless \(P=NP\), no polynomial-time algorithm achieves a \(\rho\)-approximation for maximizing the expected increase in margin of victory by edge addition—even with three candidates, single-news-article messages, unitary score distances, and unlimited budget. The paper’s reduction uses a single positive article on \(c_2\).
A plausible regime is a large platform with many voters in each of a modest number of cohorts. A type records a voter’s score vector, whether they seed or receive the article, their baseline links to every other type, and which type-to-type links the platform may add. Those are complete types for this problem: voters of one type are indistinguishable in every respect the model uses. The platform chooses connections between cohorts, while the election counts fractions of the population. In a hardness family, the number of types may grow with the instance, but each type can contain many identical voters: \(N=r\tau\), with \(r\) large.
Here is the continuous problem to hand a prover. The instance has three candidates \(C=\{c_0,c_1,c_2\}\), rational type masses \(\mu_t>0\) summing to \(1\), strict score vectors \(\pi_t\), fixed seed mass sending one positive article on \(c_2\), and a baseline directed contact-density matrix \(Q^0\). An addition-eligibility mask specifies which entries the platform may increase. Choose a matrix \(Q\) with \(Q_{tu}\in[Q^0_{tu},1]\) on eligible pairs and \(Q_{tu}=Q^0_{tu}\) elsewhere; there is no total-addition budget.
Give this matrix its dense block interpretation: in a population with \(N\mu_t\) voters of type \(t\), each possible directed edge from type \(t\) to type \(u\) is present with probability \(Q_{tu}\), and transmissions succeed. In the continuum limit, a type receives the article exactly when it is reachable from positive seed mass through type pairs with \(Q_{tu}>0\). Let \(\alpha_t(Q)\) be \(1\) if type \(t\) receives the article and \(0\) otherwise, and let \(w_t^b\) be its top candidate under scores \(\pi_t+b e_2\), using the paper’s tie-breaking convention. Its vote mass for candidate \(c\) is
\[ V_c(Q)=\sum_{t\in T}\mu_t\left[(1-\alpha_t(Q))\mathbf{1}\{w_t^0=c\}+\alpha_t(Q)\mathbf{1}\{w_t^1=c\}\right]. \]
The task is to maximize \(M(Q)-M(Q^0)\), where \(M(Q)=V_{c_0}(Q)-\max\{V_{c_1}(Q),V_{c_2}(Q)\}\). The prover must return an eligible matrix \(Q\) and its gain; the complexity question is whether this problem has a polynomial-time constant-factor approximation in the number of types and the input bit length.
I expect hardness to transfer in this regime. Theorem 10’s combinatorics are in the incidence pattern of set roles and in which links the platform adds. Lift each voter role in its reduction to a type containing \(r\) identical copies; existing links become type-pair densities, and each optional edge becomes a choice of density on an eligible type pair. Any positive density from a reached block reaches the whole target block in the dense limit, so its support has the same role as selecting that edge in the reduction. Vote margins scale with the number of copies, preserving approximation ratios. Thus the hardness is driven by the type-interaction structure, not by the number of individual voters. This mirrors only Theorem 10’s three-candidate edge-addition result, not the paper’s full set of results.
The weakest point is the dense-contact regime. It models cohort-level exposure well for some platform recommendations, but individual social graphs are often sparse. In a sparse limit, contact rates could yield partial activation of a type, and fractional edge intensities might relax the Set Cover structure. The type-level question remains worth asking, but I would not claim that this argument settles sparse networks. A natural follow-up is to compare the dense model above with a sparse continuous model and determine where the hardness survives.
Theorem 10 is a real computational result, so the negative case has to be about whether its population can meaningfully become continuous. The strongest objection is that the theorem’s key objects are individual network positions and individual edges. A complete type for this problem must capture a voter’s preferences, seed status, baseline neighborhood, and eligible additions. In arbitrary instances, those network details can make almost every voter a distinct type, leaving support size \(\tau\) close to the population size.
The proposed block model avoids that by restricting the network to cohorts with shared contact patterns. But its dense limit changes the cascade sharply. If an active type has mass \(\mu_t>0\), and each of its members has an independent probability \(Q_{tu}>0\) of contacting a target voter, that voter receives the article with probability \(1-(1-Q_{tu})^{N\mu_t}\), which tends to \(1\). Any positive block density therefore activates the whole target type; zero density activates none of it. The value of \(Q_{tu}\) disappears, and the continuum problem reduces to choosing which type pairs to connect. Meanwhile, a finite seed set has zero mass and disappears; retaining its influence requires scaling it up to a positive-mass seed cohort.
That makes the proposed lift a credible model of platform interventions between large cohorts, but not a faithful limit of the paper’s individual-edge, independent-cascade instances. A sparse scaling such as \(Q_{tu}=\beta_{tu}/N\) could preserve partial exposure and finite expected degree. It would also require specifying a new contact-intensity model and scaling the intervention so that each type-level choice changes order \(N\) edges. That could be worthwhile research, but it is a different, more structured network-design problem.
This is the best case against the anchor: the population limit either erases finite seeds and saturates dense cascades, or requires a new sparse-network model whose assumptions are not in Theorem 10. But it does not defeat every plausible mirror. Large cohorts with shared contact patterns are a sensible high-multiplicity regime, and the programme allows the network model to co-evolve when that is needed. The honest negative case is therefore weak: the proponent’s exact lift is not established as a faithful limit, but a block-level version of Theorem 10 remains a plausible continuous mirror.
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.