| paper | d4-conf-ijcai-2007-0371 |
| 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→NP-hard discrete result → its continuous mirror
Answer: \(\mathrm{NP}\text{-complete}\) · discrete side: hardness · adjudication: proved_with_minor_gaps
full proof & adversarial review →
Theorem 1
statement extracted from the paper’s text layer
Given candidates \(C\), a finite support \(\mathcal T\) of incomplete total-order types with positive rational masses \(\mu_P\) summing to \(1\), a target \(c^\star\), and a fixed elimination tie priority, is there an allocation \(x_{P,\pi}\ge 0\) over consistent complete rankings \(\pi\in\mathcal L(P)\), satisfying \(\sum_{\pi\in\mathcal L(P)}x_{P,\pi}=\mu_P\) for every \(P\), such that STV on the resulting ranking masses elects \(c^\star\), using a strict-majority quota of \(1/2\)?
The society is a distribution over incomplete ranking templates. Each template’s mass can be split among consistent complete rankings; STV runs on the resulting fractional ballot masses, with a strict-majority quota and fixed tie priority. The computational task is to decide whether some such completion allocation elects the target.
The mirror covers Theorem 1’s NP-completeness result for possible winners under STV. It leaves the necessary-winner and approximation hardness results, combined-result results, and preference-elicitation results unaddressed.
The strongest mirror is a high-multiplicity version of possible-winner under STV. Theorem 1, proved in this paper, says that PossibleWinner is NP-complete: given an incomplete profile and a candidate \(a\), decide whether some completion makes \(a\) win under STV. The paper’s hardness proof reduces from the NP-complete STV problem EFFECTIVE PREFERENCE, where one vote is unknown; that hardness result is cited from Bartholdi and Orlin (1991). The paper also states that its result holds when the ballots are incomplete total orders.
A plausible regime is a large membership vote or platform election where many people use the same partially specified ranking template—for example, because preferences are still being elicited. The agents are the voters; a type is one such incomplete ranking, and its mass is the fraction of the electorate with that template. There may be millions of voters but only \(\tau\) distinct templates. This mirrors the paper’s uncertainty about rankings, rather than making outcomes or probabilities continuous.
I would ask the authors to study \(\textsc{STV-PossibleWinner}_{\infty}\). An instance consists of candidates \(C\), a finite support \(\mathcal T\) of incomplete total-order types, rational masses \(\mu_P>0\) summing to \(1\), a target \(c^\star\), and a fixed priority for resolving elimination ties. For each type \(P\), let \(\mathcal L(P)\) be its consistent complete rankings. The decision variables are masses \(x_{P,\pi}\ge 0\), for \(P\in\mathcal T\) and \(\pi\in\mathcal L(P)\), with
\[
\sum_{\pi\in\mathcal L(P)}x_{P,\pi}=\mu_P.
\]
These variables specify how the type’s population mass is distributed among completions of its unknown comparisons. Run STV on the resulting ranking masses, using a strict-majority quota \(1/2\) and the stated tie priority. The question is whether some feasible \(x\) makes \(c^\star\) win. A solution is such a completion allocation together with its STV elimination sequence; this is a feasibility question, with no separate cost objective. Its natural complexity parameters are \(m=|C|\), \(\tau\), and the input bit length \(L\).
I predict hardness transfers (Class B): STV’s branching over candidate elimination orders remains when voter mass becomes divisible, so the hard combinatorics appear to live in \(m\), not just in the number of individual voters. For a fixed elimination order, the relevant first-choice masses are linear functions of \(x\), making feasibility an LP; enumerating orders gives an \(m!\,\mathrm{poly}(\tau,L)\) route and suggests an FPT question in \(m\). That is a reason to expect hardness may persist, not a proof of transfer.
The main weakness is exactly the gap between expectation and proof. Theorem 1’s reduction uses a single unknown vote, while this mirror lets a type’s mass split across many completions. That can create fractional runoff trajectories unavailable to any discrete completion, so the discrete reduction does not automatically embed. The mirror still asks the paper’s authors’ question—whether the target can win under a completion of incomplete STV preferences—but whether its NP-hardness survives is the central open question for this anchor. This case covers Theorem 1 only; I would not stretch it to the paper’s approximation or tractability results.
The strongest objection to the proposed mirror is semantic: the paper’s PossibleWinner problem asks whether some completion of each individual ballot makes the target win. Divisible mass can instead split one incomplete type across several completions, turning uncertainty about individual rankings into a choice of population distribution. That is a real change in the model.
But it does not defeat the best version of the mirror. Consider a large membership vote where many voters submit the same partially completed ranking template. The hidden rankings of those voters can differ while remaining consistent with the template. Since STV is anonymous and depends on aggregate ballot counts, a distribution of that type’s mass among consistent completions captures exactly the relevant information. One can also describe the input as a population distribution over complete rankings constrained by the reported partial orders. Both are plausible high-multiplicity models of the paper’s question.
So there is a named computational result to mirror—Theorem 1’s NP-completeness result—and a credible population regime in which its question remains meaningful. The paper’s reduction does not by itself establish that hardness transfers to the continuous version, but that is not a reason to reject a well-posed mirror. I cannot honestly defeat this anchor under the programme’s criteria; the negative case is weak here.
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.