| paper | Determining Possible and Necessary Winners under Common Voting Rules Given Partial Orders |
| authors | Lirong Xia, Vincent Conitzer |
| venue | AAAI 2008 |
| filed under | voting · incomplete-info |
| judged by | gpt-5.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 →
Corollary 1
statement extracted from the paper’s text layer
Given candidates \(C\), a rational distribution \(\mu\) over partial-order types \(O\) on \(C\), each with at most four undetermined pairs, and target \(c^\star\), decide whether there are masses \(x_{O,V}\ge0\) for linear extensions \(V\supseteq O\) such that \(\sum_{V\supseteq O}x_{O,V}=\mu_O\) for every \(O\), and \(\sum_{O,V}x_{O,V}s_{\mathrm{Borda}}(V,c^\star)\ge\sum_{O,V}x_{O,V}s_{\mathrm{Borda}}(V,a)\) for every \(a\ne c^\star\).
A high-multiplicity Borda possible-co-winner LP: partial orders \(O\) are voter types with masses \(\mu_O\), \(x_{O,V}\) assigns each type’s mass to integral linear completions \(V\), and the Borda margin constraints determine feasibility; equivalently maximize \(\delta\) subject to \(S_x(c^\star)-S_x(a)\ge\delta\).
The mirror covers the bounded-uncertainty possible-winner and possible-co-winner results for Borda and fixed \(k\)-approval; it leaves necessary-winner results, other rules, and unrestricted partial-order pricing unmirrored.
The strongest positive case is a high-multiplicity mirror of the paper’s possible-co-winner problem, with partial orders as voter types and completed rankings as the population-level decision.
Imagine a large population of users evaluating \(m\) policies or products. Each user is queried only on a fixed set of comparisons. Users with the same answers have the same partial order \(O\), and hence are indistinguishable for the paper’s problem. Let \(\mu_O\) be the fraction of the population with partial-order type \(O\). There may be millions of users but only \(\tau\) distinct answer-patterns, with \(n\gg\tau\). This is especially plausible in preference elicitation, one of the paper’s own motivations.
The action is to complete each partial order into a linear order. In the continuum, this is represented by \(x_{O,V}\), the mass of type \(O\) assigned completion \(V\), where \(V\) is a linear extension of \(O\). Every infinitesimal voter still receives an integral ranking; \(x\) only records the aggregate distribution of completed rankings. For Borda, define
\[ S_x(a)=\sum_O\sum_{V\supseteq O}x_{O,V}s_{\mathrm{Borda}}(V,a), \]
where \(s_{\mathrm{Borda}}(V,a)=m-\operatorname{rank}_V(a)\). The objective is to maximize the target’s minimum score margin:
\[ \begin{aligned} \max\quad &\delta\\ \text{s.t.}\quad &\sum_{V\supseteq O}x_{O,V}=\mu_O &&\text{for every type }O,\\ &x_{O,V}\ge 0,\\ &S_x(c^\star)-S_x(a)\ge\delta &&\text{for every }a\neq c^\star. \end{aligned} \]
Call this problem \(\mathrm{Borda\text{-}PcW}_\infty\). It asks whether \(\delta^\star\ge 0\); a solution is the mass-assignment \(x\). Requiring \(\delta^\star>0\) gives the unique-winner version.
My lead anchor is Corollary 1, proved in this paper as a specialization of Theorem 1. It states that possible winner and possible co-winner are NP-complete for Borda, even when every partial order has at most four undetermined pairs. More precisely, given an unweighted finite profile of partial orders, an alternative \(c\), and the Borda rule, it is NP-complete to decide whether there exists a completion of every partial order in which \(c\) is the unique winner, and also whether there exists a completion in which \(c\) is a co-winner. The four-undetermined-pairs restriction remains in force.
The continuous question above is a direct population analogue of that result. It retains the same alternatives, Borda scores, partial-order uncertainty, existential completion question, and winner notion. It changes only the electorate from finitely many individually listed voters to mass distributed over repeated partial-order types.
For the restricted regime used in Corollary 1, this continuous problem is in polynomial time. If \(O\) has at most four undetermined pairs, it has only constantly many linear extensions—at most \(2^4\) possible orientations of those pairs. We can enumerate them and solve the displayed LP explicitly. Thus the discrete NP-hardness plausibly dissolves into a polynomial-time continuous optimization problem: the combinatorial difficulty in the finite problem is the integral choice of one completion for each voter, whereas the continuum permits the population of a repeated type to split across its feasible completions.
This is a genuine high-multiplicity relaxation, not merely an analogy. A finite profile with \(n_O\) voters of type \(O\) gives \(\mu_O=n_O/n\). Conversely, any rational solution \(x\) can be realized by sufficiently many copies of each type, using \(nx_{O,V}\) voters with completion \(V\). Duplicating every vote \(r\) times leaves the discrete possible-winner answer unchanged while making \(n\) arbitrarily larger than the number of types. The continuous problem is therefore the limiting version of precisely the kind of repeated-voter regime the programme targets.
A second worthwhile anchor is Theorem 2, also proved in the paper. For every fixed \(k\ge 2\), possible winner and possible co-winner are NP-complete for \(k\)-approval, even when every partial order has at most four undetermined pairs. The reduction is from 3-SAT. The continuous counterpart, \(\mathrm{k\text{-}Approval\text{-}PcW}_\infty\), has the same input \((C,\{(O,\mu_O)\},c^\star)\), the same mass-assignment variables \(x_{O,V}\), and scores
\[ S_x(a)=\sum_O\sum_{V\supseteq O}x_{O,V} \mathbf{1}\{\operatorname{rank}_V(a)\le k\}. \]
The question is whether some feasible \(x\) makes \(c^\star\) a \(k\)-approval co-winner. Again, with at most four undetermined pairs per type, this is an explicit polynomial-size LP. This second mirror is useful because the phenomenon is not peculiar to Borda’s additive rank scores: the same continuous relaxation removes the finite-population integrality barrier for a broad approval-based rule.
The expected classification of both restricted mirrors is therefore Class A. The unrestricted version, allowing arbitrary partial orders, remains an interesting boundary question. Its formulation has exponentially many completion variables, and the dual pricing problem may itself encode a difficult weighted-linear-extension problem. That could produce a continuum-specific hardness result rather than invalidate the mirror.
The authors should recognize these questions as their own problem. The paper is explicitly about completing partial orders to determine possible winners; the mirror does not replace that question by lotteries over outcomes, probabilistic social choice, or noise. Candidates remain discrete, each completed vote remains a linear order, and the winner is determined deterministically from aggregate Borda or \(k\)-approval scores. Only the population is continuized.
The weakest point is that mass-splitting can look stronger than the paper’s semantics: several voters with the same partial order may be allowed to use different completions, whereas someone might interpret a type as requiring one common completion. But that objection is not compelling for the paper’s possible-winner problem. Its finite definition already permits each voter’s partial order to be completed independently. A large group sharing \(O\) should therefore be allowed to contain different latent rankings, and \(x_{O,V}\) is simply their limiting empirical distribution. If a referee accepts that high-multiplicity interpretation, Corollary 1 supplies a particularly clean mirror: a named NP-complete discrete problem whose bounded-uncertainty continuous counterpart becomes an LP.
I cannot honestly sustain the requested universal negative. The strongest objection is that the proposed LP might be viewed as fractionalizing the paper’s existential completion witness rather than continuizing the population: one partial-order type can split its mass among several incompatible completions. But that objection fails under the programme’s own semantics. The paper completes each voter independently, and a large group sharing the same partial order can naturally contain different latent rankings. Every individual still receives an integral ranking; only the aggregate mass is represented by \(x_{O,V}\).
For Corollary 1, the correspondence is exact. A finite profile with \(n_O\) voters of type \(O\) has integer variables \(z_{O,V}\), with \(\sum_V z_{O,V}=n_O\). The proposed continuum replaces these by nonnegative masses \(x_{O,V}\), with \(\sum_V x_{O,V}=\mu_O\). Borda winner constraints remain linear. With at most four incomparable pairs per type, each type has at most \(2^4\) extensions, so the continuous problem is an explicit polynomial-size LP. Rational solutions are realized by sufficiently many repeated voters. This is precisely a high-multiplicity relaxation, not outcome-space continuity or a noise model.
The same defence defeats Theorem 2. For fixed \(k\)-approval, the score is also linear in the completion masses:
\[ S_x(a)=\sum_{O,V\supseteq O}x_{O,V} \mathbf{1}\{\operatorname{rank}_V(a)\le k\}. \]
Again, the four-undetermined-pairs restriction makes the extension set constant-sized per type, and the continuous possible-co-winner problem is an LP. The fact that the discrete reduction encodes 3-SAT through integral completion choices does not undermine the mirror; removing precisely that population-level integrality is the computational question.
A more demanding version with arbitrary partial orders would introduce an exponential completion space and a pricing problem over linear extensions. That may be hard, but it would be a legitimate boundary or Class C result, not evidence that the mirror is pointless. Nor is the mirror already present in the paper: the paper studies individually listed finite votes, not distributions over repeated partial-order types.
Thus the negative case has only a limited modelling concern: one must explain explicitly why agents of the same partial-order type may receive different completions. Once that is stated, both anchors survive. I therefore cannot responsibly claim that no worthwhile continuous 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.