| paper | d4-journals-mss-2012-0067 |
| 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: The continuous possible-cowinner problem is in \(\mathsf{P}\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Proposition 7
Given a candidate set \(X\), target \(x^\star \in X\), integers \(K \geq 3\) and \(k \geq 3\), and supported rankings \(\sigma_t\) of \(X\) with rational masses \(\mu_t\) summing to \(1\), let \(Y\) be \(k\) new candidates. For each full ranking \(\pi\) of \(X \cup Y\) extending \(\sigma_t\), choose \(q_{t,\pi} \geq 0\) with \(\sum_{\pi:\,\pi|_X=\sigma_t} q_{t,\pi}=\mu_t\). Is there an assignment such that \(x^\star\)’s aggregate \(K\)-approval score is at least every candidate’s score?
A society has \(\tau\) ranking types with masses \(\mu_t\). Decision variables \(q_{t,\pi}\) distribute each type’s mass among its full ranking extensions; the question is linear feasibility of the mass equalities and aggregate cowinner score inequalities. For \(K\)-approval, pricing can enumerate the number of new candidates in the top \(K\) and select the best candidates for each case.
The mirror covers Proposition 7’s \(K\)-approval hardness regime; it leaves Proposition 9’s \(r_\Delta\) result and the paper’s other scoring rules unaddressed.
My lead is the hardness behind Proposition 7, proved in this paper: for every \(K\geq 3\) and \(k\geq 3\), deciding whether a designated initial candidate can be a cowinner under \(K\)-approval after \(k\) new candidates are added is NP-complete. The paper establishes this through a 3-dimensional matching construction and reductions that propagate hardness across approval thresholds and numbers of new candidates.
A plausible high-multiplicity setting is a large membership organisation polling online about meeting times or venues. Many thousands of members rank the currently available options, while a relatively small number \(\tau\) of distinct rankings occur; a new time or venue becomes available before the decision is final. The paper itself uses this kind of changing-candidate situation. Each type \(t\) is a complete ranking of the initial set \(X\), and its mass \(\mu_t\) is the fraction of members with that ranking. The new options and \(K\) remain discrete. The continuum is the population: fractions of a type’s mass can receive different completions when preferences over the new options are still unknown.
I would hand a prover this problem:
Continuous \(K\)-Approval Possible Cowinner with New Candidates (lead). An instance consists of \(X\), a target \(x^\star\in X\), integers \(K\geq3\) and \(k\geq3\), and a list of \(\tau\) rankings \(\sigma_t\) of \(X\) with nonnegative rational masses \(\mu_t\) summing to \(1\). Let \(Y\) be a set of \(k\) new candidates. For each full ranking \(\pi\) of \(X\cup Y\) whose restriction to \(X\) is \(\sigma_t\), choose a mass \(q_{t,\pi}\geq0\), with
\[
\sum_{\pi:\,\pi|_X=\sigma_t}q_{t,\pi}=\mu_t.
\]
Does there exist such an assignment for which \(x^\star\)’s aggregate \(K\)-approval score is at least the score of every candidate in \(X\cup Y\)? A solution is the mass assignment \(q\); there is no separate cost objective because the paper’s anchor is an existential decision problem.
I expect this continuous problem to be tractable. Its constraints are linear score comparisons and type-mass equalities. The LP has exponentially many completion variables, but its pricing problem appears polynomial: for a type and dual score weights, if \(j\) new candidates occupy the top \(K\) positions, the other \(K-j\) approved candidates must be the first \(K-j\) candidates in that type’s ranking. For each \(j\), choose the \(j\) new candidates with the best dual weights. Trying the possible values of \(j\) solves pricing in polynomial time, giving an exact LP feasibility algorithm. This is the kind of mirror in which the discrete hardness may come from choosing indivisible voters’ completions, while fractional population mass makes the aggregate feasibility question an LP.
A second, distinct anchor is Proposition 9, also proved here: for the scoring rule with vector \(\langle3,2,1,0,\ldots,0\rangle\), deciding whether a designated initial candidate can be a cowinner after adding exactly one new candidate is NP-complete. The paper proves this by reduction from restricted 3-dimensional matching, whose NP-completeness it cites to Garey and Johnson.
The corresponding Continuous \(r_\Delta\) Possible Cowinner with One New Candidate has the same mass input and extension variables, now with one new candidate \(y\). Each full ranking gives 3 points to its first candidate, 2 to its second, 1 to its third, and 0 to the rest. The question is whether mass can be assigned to extensions of the listed rankings so that \(x^\star\)’s aggregate score is at least every other candidate’s. I also expect this version to be tractable: for each type, the pricing problem checks the possible insertion positions of \(y\) in its ranking, then selects the position with the best dual-weighted score. There are only \(|X|+1\) positions.
Both mirrors are computational questions about the continuous population. Their solutions can be written with polynomially many nonzero mass assignments even though all possible completions are available in principle. They cover the two named hardness results, not the entire paper. The authors should recognise the formulation: it keeps their target, scoring rules, unknown extensions, and cowinner criterion, while replacing voter counts with fractions of the population. A large asynchronous poll is a stronger high-multiplicity scenario than the small meeting committee that motivates parts of the paper.
The bridge to the discrete problem is real but one-way in general. Any discrete extension of a profile with type counts \(n_t\) gives a continuous solution by setting \(\mu_t=n_t/n\) and dividing extension counts by \(n\). The reverse direction is a fractional relaxation; rounding can perturb scores, and an exact tie may disappear. Thus a continuous algorithm would not by itself prove an exact discrete algorithm, and the margin needed for reliable rounding is a natural further question. Other follow-ups are whether these LPs have useful integrality properties, how their complexity depends on \(\tau\), and whether pricing remains tractable for other scoring rules or richer models of unknown preferences.
My weakest point is that the paper’s application does not guarantee the needed regime: a small meeting poll can have as many distinct rankings as voters. The case works when the poll is large and rankings over existing options repeat substantially. There is also a genuine modelling step in allowing members with the same observed ranking to split across completions. Here that split represents the paper’s existential quantifier over unknown preferences for new candidates; it does not assume a probability of any election outcome. Still, the resulting problem is a high-multiplicity relaxation, and its relationship to finite-profile answers—especially on tied instances—needs to be made explicit.
The strongest skeptical case is about research priority: both mirrors look close to a generic convexification of the paper’s witness problem. For each initial ranking type \(t\), let \(q_{t,\pi}\) distribute its mass among full extensions \(\pi\). The score constraints are linear, so feasibility asks whether a sum of scaled convex hulls of attainable score vectors meets the cowinner region. For \(r_\Delta\) with one new candidate, there are only \(|X|+1\) insertion positions per type, giving an explicit polynomial-size LP. For \(K\)-approval, the completion space is larger, but pricing can choose how many new candidates enter the top \(K\), then select the best candidates for that choice. The proposed results may therefore require little rule-specific optimization machinery.
That is a reason to rank these mirrors below problems whose pricing problems expose new structure. It does not defeat either anchor: the question asks whether a computational mirror is worthwhile, and a generic method can still reveal a useful discrete-to-continuous change. Nor can I dismiss the applications as lacking a high-multiplicity regime. A large membership poll with many repeated rankings over a limited set of existing options is credible.
The sharper modelling concern is that \(q_{t,\pi}\) lets members sharing an initial ranking split across preferences about the new candidates. If those preferences are fixed agent attributes, the population’s complete types would need to include them. But the paper asks whether *some* extension makes the target a cowinner; allowing mass to split across extensions is a natural nonatomic version of that existential question. It does not invalidate the mirror.
So I cannot honestly defeat Proposition 7’s \(K\)-approval anchor or Proposition 9’s \(r_\Delta\) anchor. Both are named computational results, both have clear population mirrors, and neither is already treated continuously in the supplied paper. The negative case is weak: at most, these may be low-priority examples because their continuous formulations appear technically direct. There is no sound basis here for the universal claim that no worthwhile mirror exists.
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.