| paper | d4-conf-atal-2016-0278 |
| 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→P discrete result → its continuous mirror
Answer: Polynomial-time solvable. · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 3.4
Given candidates \(C\), a bipartite action graph \(A\), a rational campaign mass \(\gamma>0\), a target \(c^\star\), a fixed tie-breaking priority, and a finite-support background society \(\mu\) of total mass \(1-\gamma\) over pairwise reports, does there exist a distribution \(\nu\) of total mass \(\gamma\) over strict orientations of every edge in \(A\) such that \(c^\star\) wins under pBorda? Campaign members share a utility ranking that places \(c^\star\) above the current winner; cycles in their reports are permitted.
The society consists of background report types with masses \(\mu\), plus a campaign type of mass \(\gamma\) whose members share utility and reporting constraints. The decision variable is a distribution \(\nu\) over strict orientations of \(A\); equivalently, use one directional mass variable per edge. The objective is feasibility: make \(c^\star\) win under pBorda with the stated tie-breaking priority. Since cycles are allowed, every vector of edge marginals in \([0,\gamma]^{|A|}\) is realizable, and the pBorda score constraints are linear.
The mirror covers the bipartite, strict-preference pBorda case of Theorem 3.4; it does not cover the theorem's general-graph case or the paper's other pBorda, Copeland, and axiomatic results.
My lead is Theorem 3.4, which says: *pBorda-Manipulation is NP-complete when the manipulator’s action graph \(A\) is bipartite or general, and the preference type is strict.* Here, “strict” means the manipulator must orient every allowed pair; cycles are still permitted. This theorem is proved in the paper, through a reduction from its Mixed-Elimination problem and restricted 3-D Matching. I would mirror its bipartite case.
A plausible regime is a large recommendation platform that solicits head-to-head comparisons only across two product groups, so the permitted comparison graph is bipartite. A coordinated cohort of users wants the same candidate elected and has the same reporting interface. The rest of the population has many users but relatively few recurring pairwise-report types: for example, millions of users represented by hundreds or thousands of distinct profiles. A background voter’s type is their full pairwise report; a campaign member’s underlying type records their shared utility and reporting constraints, while their submitted report is their action. This is a population regime, not a claim that all recommendation settings have this structure.
Call the mirror Bipartite Strict Mass-pBorda Manipulation. An instance gives candidates \(C\), a bipartite action graph \(A\), a rational campaign mass \(\gamma>0\), a target \(c^\star\), a fixed tie-breaking priority, and a finite-support background society \(\mu\) of rational pairwise-report masses totaling \(1-\gamma\). The campaign members share a utility ranking that puts \(c^\star\) above the current winner. Each must submit a strict orientation of every edge in \(A\), with no comparisons outside \(A\); their reports may contain cycles, as in Theorem 3.4. The question is whether there is a distribution \(\nu\) of total mass \(\gamma\) over those reports such that \(c^\star\) wins under pBorda. A solution is a list of reports and their rational masses. Thus only the population is continuized: the candidate set, pairwise-report space, and winner objective remain discrete.
This mirror appears tractable, in Class A. For each edge \(e=\{i,j\}\in A\), let \(x_e\in[0,\gamma]\) be the campaign mass reporting \(i\succ j\); the remaining mass \(\gamma-x_e\) reports \(j\succ i\). If the background contributes masses \(a_e\) and \(b_e\) to those directions, their pBorda contributions after manipulation are
\[
\frac{a_e+x_e}{a_e+b_e+\gamma}
\quad\text{and}\quad
\frac{b_e+\gamma-x_e}{a_e+b_e+\gamma}.
\]
Each denominator is fixed, so every candidate’s pBorda score is affine in the \(x_e\). Every vector in the box \([0,\gamma]^{|A|}\) is realizable: because cycles are allowed, every orientation of \(A\) is a valid report, and any edge-wise marginals can be realized by a distribution over orientations. The fixed priority tie-break gives linear weak or strict score inequalities. The resulting rational feasibility problem is solvable by linear programming, in time polynomial in \(|C|\), the background support size \(\tau\), \(|A|\), and the input bit length \(L\). A feasible marginal vector can also be represented by a mixture of at most \(|A|+1\) reports.
The key change is divisibility. A single finite manipulator must choose one indivisible orientation of all edges; the paper’s theorem shows that this can encode NP-hard combinatorics. A mass of strategists can split those choices across users, and pBorda depends only on the resulting pairwise masses. So this is a concrete way the hardness might dissolve. It does not solve Theorem 3.4 itself: the finite one-manipulator instance corresponds to a campaign distribution concentrated on one report, while the continuous mirror permits mixtures.
The scope is deliberately narrow: the bipartite, strict-pBorda case of Theorem 3.4. I am not extending the conclusion to the paper’s acyclic-report cases, its Copeland results, or its axiomatic result.
The weakest point is also the central modelling choice: the paper studies one manipulator, while this mirror gives a positive mass of coordinated manipulators who may submit different reports. That is a genuine high-multiplicity extension, not a reinterpretation of the single-manipulator problem. Its case rests on the authors recognizing mass-coalitional pBorda manipulation as their underlying winner-manipulation question. The mirror keeps their candidates, pBorda rule, target, action graph, and strict pairwise-report constraint, which makes that recognition plausible in a large platform with coordinated users.
The mirror also raises useful follow-up questions: how does the minimum campaign mass vary with \(\gamma\), and how well can a continuous solution be rounded to \(K\) discrete campaign members? What happens if reports must be acyclic, where the aggregate edge marginals may no longer be freely chosen? And do analogous mass formulations for Copeland\(_\alpha\) remain tractable, or retain hardness?
The strongest negative case is the gap between the paper’s one manipulator and the proposed positive mass of strategists. In a normalized population, one voter has mass \(1/n\), which tends to zero as \(n\) grows. Changing that voter’s report then leaves every pairwise mass, and hence every pBorda score, unchanged in the limit. The direct continuous version of Theorem 3.4 therefore has no meaningful individual action.
The proposed repair gives a campaign mass \(\gamma>0\) and lets its members submit different reports. The LP appears sound: for each edge, the campaign’s directional mass determines affine score contributions, and arbitrary edge marginals can be realized because cycles are allowed. But this is a continuous coalitional manipulation problem. Its key input is a divisible bloc of strategists, and its solution can allocate different orientations to different portions of that bloc. Theorem 3.4 instead asks whether one manipulator can choose a single orientation of the action graph. The mirror’s tractability answers a new question about coordinated campaigns; it does not preserve that unilateral question.
That distinction is the best argument against treating this anchor as a mirror. It is also where the negative case weakens: coalitional manipulation is a natural extension, and a large, coordinated group with shared preferences is a plausible high-multiplicity regime. The paper’s authors may well recognize the campaign question as part of their problem family. Given the programme’s scope, I cannot honestly rule out that scenario or claim this anchor has been defeated.
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.