| paper | d4-conf-atal-2008-0113 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: Polynomial-time solvable: the problem is in \(\mathrm{P}\) for fixed \(m=3\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 8
statement extracted from the paper’s text layer
Given candidates \(A,B,C\), the cup agenda, a target, and the paper’s target-favourable tie rule, let each type \(t\) have rational mass \(\mu_t\), initial ranking \(r_t\), and a set \(M_t\) of comparisons the campaign may change. Let \(R_t\) be the total rankings that preserve all comparisons outside \(M_t\). Does there exist an allocation \(x_{t,r}\ge 0\), for \(r\in R_t\), with \(\sum_{r\in R_t}x_{t,r}=\mu_t\) for every type, such that the resulting population elects the target?
A nonstrategic campaign acts on a society of mass \(1\), represented by rational masses \(\mu_t\) over types \(t=(r_t,M_t)\). Variables \(x_{t,r}\) assign portions of each type to permitted final rankings; the objective is feasibility subject to the target winning the cup over aggregate pairwise comparisons. This is a population-mass extension of preference manipulation, not a change to the voting outcome space or a shift between strategic equilibrium concepts.
Covers Theorem 8’s preference-manipulation hardness for the three-candidate cup, including its balanced agenda; leaves the coalition-manipulation result and the paper’s other theorems unaddressed.
The strongest mirror I believe in is preference manipulation under the cup rule, in a large campaign where many voters share the same current ranking and the same comparisons that can be changed. A type records those two facts; its mass is the fraction of the population with that type. The campaign can split that mass among different final rankings. This treats the population as the continuous object: the final election is still a cup over ordinary total rankings, not a lottery over outcomes.
My anchor is Theorem 8. It states that, for the cup rule on weighted votes, constructive manipulation by a coalition is polynomial for any number of candidates, while preference manipulation is NP-complete with three or more candidates. The paper cites Conitzer and Sandholm for the coalition-manipulation result and proves the preference-manipulation hardness here by reduction from number partitioning. Its proof also establishes hardness for balanced cups. I mirror the preference-manipulation result; the coalition result is useful context but is not a second mirror.
Here is the continuous problem I would hand to a prover: Continuous Three-Candidate Cup Preference Manipulation. The input is three candidates \(A,B,C\), a cup agenda in which \(A\) plays \(B\) and the winner plays \(C\), a target candidate, a fixed tie rule, and a finite set of types with positive rational masses \(\mu_t\) summing to \(1\). Each type \(t\) records an initial ranking \(r_t\) and a set \(M_t\) of pairwise comparisons the campaign may change. Its permitted final rankings are exactly the total rankings that preserve \(r_t\)'s comparisons outside \(M_t\). The question is whether there are nonnegative allocations \(x_{t,r}\), for permitted rankings \(r\), with \(\sum_r x_{t,r}=\mu_t\) for every type, such that the aggregate final population elects the target. A solution is such an allocation; it says what fraction of each type ends with each permitted ranking.
The regime is a large election or public campaign over three finalists: perhaps hundreds of thousands of voters but only a modest number of combinations of current ranking and campaign flexibility. For three candidates there are at most \(48\) such types. A continuous campaign can persuade some members of a type one way and others another way, so this mass allocation captures individual responses within a large, otherwise homogeneous group.
For this stated problem I expect Class A. There are at most \(6\tau\) allocation variables, and each pairwise contest is determined by a linear sum of allocated mass. The target’s cup-winning condition has only a constant number of possible paths through this three-candidate agenda. Testing each path reduces to linear feasibility, with the tie rule included in the inequalities. That gives an algorithm polynomial in the input bit length. The number-partitioning reduction in Theorem 8 relies on assigning each weighted bloc wholly to one ranking; a continuous type can divide its mass, so those indivisible subset choices disappear. The resulting question remains preference manipulation under the cup rule, rather than manipulation of whole votes.
This case covers the paper’s three-candidate preference-manipulation hardness, including the balanced-agenda case. It does not claim a result for arbitrary numbers of candidates. A natural next question is whether the same mass-allocation formulation remains tractable when the candidate set is part of the input, or whether the ranking and agenda structure creates continuum-specific hardness. Adding costs for changing each type into each ranking would yield a related minimum-cost campaigning problem.
My weakest point is the change in how weighted votes are treated. The paper’s reduction uses weighted votes as indivisible blocks; this mirror lets people in a block respond separately. That is plausible for a population-scale campaign in which respondents share the same opportunities but need not react identically. If the intended setting requires every weighted bloc to move as one, the mirror would miss that correlation constraint. The continuous question is strongest when the agents’ individual responses—not bloc-level all-or-nothing decisions—are the object of study.
The strongest objection to the proponent’s anchor, Theorem 8, is that its hardness comes from indivisible weighted blocks. The reduction asks whether whole blocks of sizes \(2k_i\) can be assigned to rankings to form an equal partition. In the proposed continuous model, each type’s mass can be split among its permitted rankings. With three candidates there are only six rankings, so the target-winning conditions can be checked by enumerating the cup’s possible winning paths and solving a linear feasibility problem with at most \(6\tau\) variables. That is a sound mirror, but it looks like an immediate fractional relaxation rather than a new complexity landscape.
That objection is limited, though. The result would identify whether Theorem 8’s hardness is caused by population multiplicity, and a tractable answer is exactly the kind of finding ChoCo seeks. Nor does the stronger version rescue the negative case: with the number of candidates unbounded, the same mass-allocation model becomes an LP over permitted rankings, and its pricing problem may expose real complexity. The fact that the difficulty could come from ranking or agenda structure is not a reason to dismiss the question; a hardness result would also be informative.
So I cannot honestly make the universal claim that no worthwhile mirror exists. The three-candidate mirror may be technically routine, but it is a plausible population-scale campaign question and directly tests the source of the paper’s partition hardness. The objection is about likely research yield, not whether the continuous problem is well-posed or worth asking.
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.