| paper | d4-conf-aaai-2018-0923 |
| 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 · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 3
statement extracted from the paper’s text layer
Given a finite alternative set \(A\), a finite-support rational distribution \(\mu\) over complete rankings of \(A\), a target \(c\), and rational pair thresholds \(\lambda_{\{a,b\}}\in[0,1]\), choose masses \(x_{t,R}\ge 0\) assigning each ranking type \(t\)'s mass among partial orders \(R\) consistent with \(t\), with \(\sum_R x_{t,R}=\mu_t\). Let \(\nu_R=\sum_t x_{t,R}\); require at least \(\lambda_{\{a,b\}}\) total mass to report \(a\) and \(b\) as comparable for every pair. Is there such an assignment for which \(c\) uniquely minimizes maximum plurality regret, where regret is maximized over all completions that distribute each \(\nu_R\) among complete rankings extending \(R\)?
A population with ranking types \(t\) carrying rational masses \(\mu_t\). The decision variables \(x_{t,R}\) split each type’s mass among consistent partial reports; pairwise coverage is measured as a share of total mass, and the feasibility objective is to make the target the unique minimax-regret plurality winner against adversarial completions.
The mirror covers Theorem 3’s plurality case and the no-threshold plurality version of Theorem 1; it leaves the 2-approval case, results for other voting rules, and possible- and necessary-winner problems unmirrored.
The strongest mirror is the paper’s plurality attack with candidate-pair limits. Consider a large recommendation or ranking platform with a fixed slate of alternatives. Users have complete rankings, but the platform chooses which comparisons to elicit. Let a type \(t\) be a complete ranking, and let \(\mu_t\) be the fraction of users with that ranking. In a high-multiplicity regime, the platform has many users but comparatively few distinct ranking types: for example, coarse preference segments may each contain many users. The platform can choose different elicitation patterns for different portions of a type. That is the continuous version of the paper’s per-voter choice, not a change to the underlying manipulation question.
Here is a precise continuous problem for plurality. The input is a finite-support rational distribution \(\mu\) over rankings of the alternatives \(A\), a target \(c\), and rational thresholds \(\lambda_{\{a,b\}}\in[0,1]\) for each pair of alternatives. For each ranking \(t\), choose nonnegative masses \(x_{t,R}\), where \(R\) ranges over partial orders consistent with \(t\), and require \(\sum_R x_{t,R}=\mu_t\). The resulting mass of partial report \(R\) is \(\nu_R=\sum_t x_{t,R}\). The elicitation must make \(a,b\) comparable for at least \(\lambda_{\{a,b\}}\) of the population: \(\sum_{R:\,aRb\text{ or }bRa}\nu_R\ge\lambda_{\{a,b\}}\).
To evaluate the reports, a completion assigns each mass \(\nu_R\) among complete rankings extending \(R\). Let \(\mathrm{sc}(a)\) be the resulting plurality mass for \(a\) at the top of the ranking. Define
\[
\mathrm{MR}_{\nu}(a)=\max_{\text{completions}}\max_{b\in A}
\bigl(\mathrm{sc}(b)-\mathrm{sc}(a)\bigr).
\]
The question is whether there is a mass assignment \(x\) satisfying all pair thresholds for which \(\mathrm{MR}_{\nu}(c)<\mathrm{MR}_{\nu}(a)\) for every \(a\ne c\). A solution is such an assignment of population mass to elicitation patterns. The objective is feasibility: can the platform make \(c\) the unique minimax-regret winner while meeting its comparison-coverage requirements?
My lead anchor is Theorem 3, proved in this paper. It says that MANIPULATIVE ELICITATION WITH CANDIDATE PAIR LIMIT is NP-complete for both plurality and 2-approval. Its input is a set of alternatives, a complete profile of \(n\) voters, a target alternative, and an integer lower bound \(f(\{a,b\})\) for each pair; it asks whether there is a consistent partial profile meeting every lower bound in the number of reports where the pair is comparable and making the target the unique minimax-regret winner. The paper proves hardness for plurality by reduction from X3C. Replacing voter counts and pair-count bounds with proportions gives the continuous problem above directly. Coverage fractions are a natural co-modification once population is measured as mass.
I would provisionally expect the continuous plurality problem to be Class B, with hardness driven by the alternatives and the set-cover structure rather than by a large number of voters. That is a reason to expect hardness to survive population continuization, not a proof that it does. In particular, continuous mass can be split across elicitation patterns, whereas the reduction in Theorem 3 reasons about whole voters. A prover would need to establish that this fractional freedom does not wash out the combinatorics—or show that it does and give an algorithm. The open question is meaningful either way.
A useful companion anchor is Theorem 1, also proved here. For every monotone, neutral, worst-efficient score-based voting rule, it proves that MANIPULATIVE ELICITATION is polynomial-time solvable: given a complete profile and target, decide whether some consistent partial profile makes the target the unique minimax-regret winner. Its continuous mirror is the same mass-assignment question with no pair thresholds. For rules extended naturally to mass-weighted societies, I expect this version to remain tractable by the paper’s extremal-score argument: the test is whether the target already has the rule’s worst possible score for total population mass one. This is Class A. Together, the anchors ask where the pair-coverage constraints change the tractability of the same population-level manipulation.
The scenario is plausible, though not universal. In a platform with many users and a manageable number \(\tau\) of observed ranking types, \(\mu_t\) is a more natural description than counts such as “547 users”; the platform can control which comparisons it asks users to report. Minimum pairwise coverage is credible as a product or audit requirement, though requiring a threshold for every pair may be a less common operational policy. The paper’s setting of incomplete preferences and elicitation is preserved, and the continuous object is the society itself. This mirror does not cover the paper’s other possible-winner or necessary-winner questions.
The weakest point is the gap between integer voters and divisible mass. Theorem 3 does not itself establish hardness for the continuous question. I would ask whether continuous YES answers coincide with the discrete answers when \(\mu_t=n_t/n\) and \(\lambda_{\{a,b\}}=f(\{a,b\})/n\); if not, how large the gap can be; and whether the fractional problem admits a polynomial algorithm in \(m,\tau\), and the input bit length. Those are the complexity questions the mirror puts on the table.
The strongest negative case is about marginal value and operational fit, rather than a fatal flaw in the model.
Theorem 3’s plurality result is the best anchor, and its pair limits are a demanding policy input: the decision maker must specify a minimum comparison rate for every pair of alternatives. The problem then asks whether selective elicitation can make a target the unique minimax-regret winner, with no cost for designing or administering the elicitation. In many real systems, the decision maker cannot tailor questions to each person’s complete latent ranking—the very information elicitation is meant to uncover. That makes the proposed type-by-type allocation hard to implement in some plausible settings. Still, platforms with historical preference data could route users into different survey modules, and pairwise coverage requirements could serve as audit rules. With that scenario, the continuous version is well-posed. Whether fractional mass preserves the reduction’s combinatorics is a substantive question, not a reason to dismiss the mirror.
Theorem 1 is a weaker research anchor. Its discrete algorithm turns on whether the target already has the worst possible score. For common rules, the same extremal-score argument appears likely to extend directly to rational type masses. That suggests a modest result. Yet the extension still asks about a population input compressed by support size and binary bit length, and the programme counts tractability results as part of the landscape. A likely easy answer does not make the question invalid.
A plausible mirror survives both objections. Take an election or preference platform with many users and a manageable number of complete ranking types. The platform can distribute each type’s mass among consistent partial reports, require a minimum population share to compare each pair, and ask whether a target becomes the unique minimax-regret winner. The population is the continuous object; the manipulation and computational questions remain recognizable. Existing finite-population work on minimax regret is not itself a continuous treatment of this problem.
So I cannot honestly defeat every version of the mirror. The pair-limit model may fit only a narrow class of elicitation settings, and the unconstrained version may be quick to settle. Those are real reasons to expect limited payoff. They do not support the universal claim that no worthwhile scenario or continuous question 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.