| paper | d4-conf-aaai-2010-0248 |
| 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 belongs to \(\mathrm{P}\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 3
statement extracted from the paper’s text layer
Given an initial candidate set \(X\), three new candidates \(Y\), a target \(x^\star\in X\), and a rational distribution \(\mu\) over rankings of \(X\), is there a completion plan \(q_{t,\pi}\ge 0\) such that \(\sum_{\pi:\,\pi|_X=t}q_{t,\pi}=1\) for each type \(t\), and \(x^\star\) is a \(4\)-approval winner under the resulting mass \(\bar\mu_\pi=\sum_t\mu_tq_{t,\pi}\), with favorable tie-breaking?
A population with mass \(\mu_t\) on each observed ranking type \(t\); variables \(q_{t,\pi}\) split each type’s mass among complete extensions \(\pi\); feasibility requires \(x^\star\)'s \(4\)-approval score to be at least every other candidate’s score.
The proposed mirrors cover Propositions 3 and 5. They leave Propositions 1, 2, and 4 and the paper’s other rule and parameter cases unaddressed.
The strongest mirror is the possible-winner question when new candidates are added, with the voter population represented by mass over the rankings already known. It keeps the paper’s central question intact: can a given initial candidate win under some completion of the voters’ preferences over the new candidates?
Let \(X\) be the initial candidate set, \(Y\) the \(k\) new candidates, and \(\mu\) a rational distribution over the observed rankings of \(X\). Each ranking \(t\) is a type: voters sharing it have the same known preference and the same set of possible extensions to \(X\cup Y\). For each type \(t\), choose a distribution \(q_{t,\pi}\) over complete rankings \(\pi\) of \(X\cup Y\) whose restriction to \(X\) is \(t\). Require \(q_{t,\pi}\geq 0\) and \(\sum_\pi q_{t,\pi}=1\). The resulting mass on ranking \(\pi\) is \(\bar\mu_\pi=\sum_t\mu_tq_{t,\pi}\).
The question is whether there is such a \(q\) for which the target \(x^\star\) has at least the score of every other candidate, using the paper’s favorable tie-breaking assumption. A solution is the completion plan \(q\). There is no cost objective in the paper’s underlying problem; this is a feasibility question. Voters still receive complete, integral rankings, but a type’s mass can divide among different extensions. The population is what becomes continuous; the candidates and rankings remain discrete.
This is plausible in a large asynchronous poll over a modest menu of meeting slots: participants have ranked the available slots, more slots later become available, and the poll only asks whether a candidate *could* win under some completion. In a sufficiently large electorate, many voters may share exact rankings, so \(n\) can greatly exceed the number \(\tau\) of observed types. The mirror does not assume voters have identical hidden preferences for the new slots. It asks whether some aggregate assignment of those unknown preferences makes the target win, just as the paper asks whether some individual completion does.
My lead anchor is Proposition 3, proved in this paper. It says that deciding whether \(x^\star\) is a possible winner under \(4\)-approval when exactly three new candidates are added is NP-complete. The proof reduces from restricted \(3\)-dimensional matching, with each element appearing in two or three triples. The mirror is Fractional \(4\)-Approval Possible Winner with Three Added Candidates: given \(\mu\) over rankings of \(X\), three new candidates, and \(x^\star\in X\), decide whether a completion plan \(q\) makes \(x^\star\) a winner under \(4\)-approval. I expect this mirror to be tractable. For each old ranking, there are only
\[
\frac{(m+3)!}{m!}=(m+1)(m+2)(m+3)
\]
ways to interleave the three new candidates. Listing those extensions for each of the \(\tau\) types gives a polynomial-size LP: the variables are the \(q_{t,\pi}\), with one score inequality per candidate. It is solvable in time polynomial in \(m,\tau,L\). This is a direct, finite formulation, not an appeal to a pricing oracle.
A second, independent hardness anchor is Proposition 5, also proved here. For the scoring rule \(r_\Delta\) with vector \((3,2,1,0,\ldots,0)\), deciding whether \(x^\star\) is a possible winner when exactly one new candidate is added is NP-complete. Its proof also reduces from restricted \(3\)-dimensional matching. The corresponding Fractional \(r_\Delta\) Possible Winner with One Added Candidate uses the same input and completion variables, with \(r_\Delta\) scores in place of \(4\)-approval scores. I again expect tractability: each old ranking has \(m+1\) possible insertions for the new candidate, so the feasibility LP has \(O(\tau m)\) completion variables and a linear number of score constraints. This anchor shows that the proposed mirror is not limited to the paper’s three-candidate hardness result, though its scoring rule is more specialized.
The LPs predict that both discrete hardness results dissolve in the continuous version. That is a meaningful outcome for the programme: in the reductions, combinatorial choices of whole voters encode a matching, whereas a continuous type mass can split across completions. Follow-up questions include whether the \(m^k\) extension enumeration for fixed \(k\) can be improved to an FPT algorithm in \(k\); what happens when \(k\) is part of the input; and how much score slack is needed to round a fractional completion back to a finite electorate. I am relying on Propositions 3 and 5 as my anchors, not claiming that these two mirrors settle the paper’s other results.
The weakest point is also the core of the case: fractional completion is not the paper’s exact finite-voter question. In particular, allowing mass to split may erase the integral matching structure behind Proposition 3. The authors could reasonably ask whether the mirror still captures their problem if a type’s voters cannot divide across extensions. I think it does capture a legitimate high-multiplicity version: the known rankings, candidate additions, scoring rules, and possible-winner test are all preserved, and the relaxation changes precisely the population granularity that the continuization programme is designed to examine. It is a good case for a tractable continuous mirror, not a claim that the paper’s NP-completeness result disappears for real finite elections.
The strongest objection is that the proposed LP chooses how the unknown preferences are distributed. Its variables \(q_{t,\pi}\) do not describe a fully specified society over complete voter types; they describe a completion of the observed rankings that makes the target win. One could require the input to give masses over complete rankings, but then there are no unknown rankings left to complete. That makes the mirror less like computing the outcome of a known continuous society and more like asking whether *some* continuous society consistent with partial information would elect \(x^\star\).
That is a real modeling distinction, but it does not defeat either anchor under ChoCo’s stated scope. The discrete paper also asks whether some completion is possible. In an atomless population, splitting the mass with a known old ranking among different full rankings is a coherent way to represent the range of possible completions. A large poll over meeting times or other finite alternatives supplies a plausible high-multiplicity setting; voters’ identities need not matter to this question. And the paper contains named computational results: Propositions 3 and 5 are NP-completeness results, so the “no result to mirror” objection does not apply.
Both anchors survive that test. For Proposition 3, with three added candidates, enumerating extensions takes \((m+1)(m+2)(m+3)\) possibilities per old ranking. For Proposition 5, with one added candidate, it takes \(m+1\). The resulting feasibility LPs have polynomially many variables and score constraints. That is a simple and likely quick Class A result, but its simplicity is the answer the continuous question is meant to discover: the finite voters’ indivisible choices encode the reductions, while mass can split across completions. Calling that outcome too easy to merit priority is the best negative case I can make. It is not a reason the mirror is ill-posed or already done, and the paper provides no continuous treatment that collides with it.
I therefore can’t honestly make the requested universal case. The proposed mirrors may be modest, immediate results, and the LP models a set of possible continuous completions rather than a single fully observed society. But under the programme’s definition, Proposition 3 and Proposition 5 each yield a sensible continuous-population question. Both anchors survive the strongest objections I can support.
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.