| paper | d4-conf-ijcai-2020-0592 |
| 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: \(\mathrm{NP}\)-complete for each fixed rule \(\mathrm{CSR}\) and \(\mathrm{LSR}\), already with equal masses. · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3 (∗)
statement extracted from the paper’s text layer
Given a finite type set \(T\), positive rational masses \(\mu_t\) summing to \(1\), a binary qualification matrix \(q:T\times T\to\{0,1\}\), target types \(P\subseteq T\), a rule \(r\in\{\mathrm{CSR},\mathrm{LSR}\}\), and a rational budget \(B\), is there a set \(D\subseteq T\times T\) of type-pair qualifications to flip, with cost \(\sum_{(t,u)\in D}\mu_t\mu_u\le B\), such that every target type is eventually socially qualified under \(r\)?
A society is a distribution \(\mu\) over qualification types. Every member of type \(t\) has the same qualification relation to every type \(u\), encoded by \(q(t,u)\); a decision flips whole ordered type-pair blocks, and its cost is the affected mass \(\mu_t\mu_u\). CSR and LSR operate on the resulting type-level qualification graph, and the goal is to make all target types socially qualified within budget.
The paper allows individual link flips, while the mirror changes whole type-pair blocks at once, and the supplied paper extract does not show that its SET COVER reduction survives this change.
fatal: False
Covers constructive link bribery under CSR and LSR when members of each type share qualification relations and interventions change whole ordered type-pair blocks; it leaves destructive and exact bribery, agent bribery, and the consent rule aside.
The strongest positive case is a narrow mirror of constructive link bribery under the CSR and LSR rules. A plausible regime is a very large professional association whose members fall into a small number \(\tau\) of credential or role classes. Within a class, members share the same qualification judgments toward every other class. The population is a distribution \(\mu\) over those classes, with \(\mu_t\) the fraction in class \(t\). This is a genuine high-multiplicity setting: the number of people can be enormous while the number of distinct qualification types stays modest. Revising a qualification policy between two classes then changes a mass of pairwise judgments.
My lead anchor is Theorem 3 (*), proved in this paper. It says that, for both CSR and LSR, the decision problem CONST-LINK BRIBERY is NP-complete and W[2]-hard parameterized by \(\ell\). In the paper’s problem, the input is a qualification profile, a target set \(A^+\), and a budget \(\ell\); the question is whether at most \(\ell\) individual qualifications can be flipped so that every member of \(A^+\) becomes socially qualified. The paper identifies a reduction from SET COVER. The starred proof is omitted from the supplied extract, so the reduction’s details would need checking before claiming a formal lift.
The continuous question I would hand to a prover is Type-Block Constructive Link Bribery. Its input is a finite set \(T\) of qualification types, positive rational masses \(\mu_t\) summing to \(1\), a binary qualification matrix \(q:T\times T\to\{0,1\}\), a target set \(P\subseteq T\), a rule \(r\in\{\mathrm{CSR},\mathrm{LSR}\}\), and a rational budget \(B\). Here \(q(t,u)=1\) means every member of type \(t\) qualifies every member of type \(u\). A solution is a set \(D\subseteq T\times T\) of type-pair qualifications to flip. Its cost is the affected mass of ordered pairs, \(\sum_{(t,u)\in D}\mu_t\mu_u\).
For the resulting matrix \(q_D\), LSR starts with \(S_0=\{t:q_D(t,t)=1\}\); CSR starts with \(S_0=\{u:q_D(t,u)=1\text{ for every }t\in T\}\). Both rules then repeatedly add \(u\) whenever some \(t\) already in the set has \(q_D(t,u)=1\). The question is whether there is a \(D\) of cost at most \(B\) for which every target type is eventually added. The output is the set of type-pair flips. Since every supported type has positive mass, the type-level reachability rule captures the intended idea that qualified members of a class can qualify members of another class.
I expect this problem to be hardness-transfer territory. The SET COVER combinatorics identified by Theorem 3 live in the qualification-role graph, which remains explicit in the type set even when each type has a continuum of members. On equal-mass instances, each type-pair flip costs \(1/\tau^2\), so a budget of \(\ell\) flips corresponds to \(B=\ell/\tau^2\). That makes a lift of the reduction credible: the population size does not erase the set-cover choices. This is an expectation to prove, not a consequence already established by Theorem 3.
The mirror covers constructive link bribery for the two iterative rules. It does not claim to continuize the paper’s consent-rule results, agent bribery, exact bribery, or destructive bribery. A useful next question is whether the mass-weighted version is fixed-parameter tractable in the number \(|P|\) of target types, and whether allowing interventions on arbitrary fractions of a type-pair block changes the answer.
The weak point is the symmetry of the intervention: the paper permits flipping individual links, while this mirror flips a whole type-pair block uniformly. That is plausible when qualifications are category-wide policies, but it is a real restriction on the action space. If the authors regard individually edited links as essential even in the proposed regime, this mirror needs a more flexible formulation.
Theorem 3 is a real computational anchor: it proves NP-completeness and W[2]-hardness for constructive link bribery under CSR and LSR. The strongest objection is that the proposed mirror changes what a link-bribery action is. To keep the number of types small, members of a type must share the same qualification relations to every other type. Flipping a type-pair block then changes every qualification between those classes, at cost \(\mu_t\mu_u\). The paper’s briber can instead flip one particular ordered pair. In a society of \(n\) people, that single edit has normalized cost \(1/n^2\), while a whole-block edit has cost proportional to the two class masses. The block model is coherent when an institution changes a shared policy between roles, but it is a policy-level problem rather than a high-multiplicity version of the paper’s individual-link problem. The supplied text says the hardness reduction comes from SET COVER, but does not include its proof, so it also does not establish that the reduction lifts to this altered action space.
Allowing edits to arbitrary fractions of a block preserves more of the original action space, but qualification densities alone do not determine the resulting CSR or LSR outcome. Reachability depends on where the changed links lie, and CSR’s “qualified by everyone” condition is sensitive even to a single exception. An atomless model needs an explicit relation or graphon and a choice between pointwise and almost-everywhere semantics; LSR also needs a separate convention for self-qualification, since the diagonal has measure zero. Such a model may be worth studying, but it requires additional structure whose computational input is no longer the paper’s finite type list and masses.
Refining types to include target status, self-qualification, and qualification patterns can help with the representation problem. It does not resolve the intervention mismatch: individual link edits can make people who began in one type behave differently, while uniform type-pair edits rule that out. Conversely, permitting those individuals to split into new types can make the number of types grow with the instance. These are substantial obstacles to calling the proposed question a direct continuous mirror of Theorem 3.
Still, I cannot honestly defend the universal claim that no worthwhile mirror exists in any scenario. A large association with role-based qualification policies could make whole-block edits and mass-weighted costs a sensible computational problem. That scenario survives the objection that the specific link-bribery theorem has not been carried over. The negative case is therefore strongest against the claimed mirror’s fidelity, and weak against the broader claim that some continuous-population formulation of group identification is worth pursuing.
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.