| paper | Determining Possible and Necessary Winners Given Partial Orders |
| authors | Lirong Xia, Vincent Conitzer |
| venue | JAIR 2011 |
| filed under | voting · incomplete-info |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
NP-hard→P discrete result → its continuous mirror
Answer: Both deciding \(\delta^\star>0\) and deciding \(\delta^\star\ge 0\) are 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\), rational masses \(\mu_i\) over \(\tau\) partial-order types \(O_i\), each with at most \(4\) undetermined pairs, and target \(c\), choose nonnegative masses \(x_{i,V}\) over linear extensions \(V\in E_i\) satisfying \(\sum_{V\in E_i}x_{i,V}=\mu_i\), and decide whether the maximum \(\delta\) satisfying \(\sum_{i,V}x_{i,V}\bigl(s_{\mathrm{Borda}}(V,c)-s_{\mathrm{Borda}}(V,a)\bigr)\ge\delta\) for every \(a\ne c\) is \(>0\) or \(\ge0\).
A nonatomic electorate with candidate set \(C\), where mass \(\mu_i\) shares partial-order information type \(O_i\); each unit receives one compatible linear ranking \(V\), while \(x_{i,V}\) records the mass assigned to \(V\), maximizing the target's Borda winning margin.
The repeated partial-order cohort regime is asserted rather than grounded in a paper-specific application, and the \(4\)-pair promise removes precisely the integral coordination that drives the paper's NP-hardness.
fatal: False
The mirror covers only Corollary 1's Borda possible-winner and possible co-winner hardness under the at-most-\(4\)-undetermined-pairs promise; it leaves the other voting rules, necessary-winner results, and unrestricted extension pricing untouched.
The strongest mirror is a high-multiplicity version of Borda possible-winner determination with partial-order information. This is my lead case.
The paper’s best anchor is Corollary 1, proved in this paper as an application of Theorem 1. It states that Possible Winner and Possible co-Winner for Borda are NP-complete, even when every vote has at most four undetermined pairs. Thus, given unweighted partial orders and a candidate \(c\), it is NP-complete to decide whether some completion makes \(c\) the unique winner, or whether some completion makes \(c\) a co-winner. The reduction is from X3C; the difficulty lies in coordinating the completions of many partially specified votes.
A natural continuous population consists of a large electorate divided into \(\tau\) recurring information cohorts. A type \(O_i\) is a partial-order pattern over the candidates: for example, all voters in one cohort may know that \(a\succ b\succ d\), while being unable to compare \(c\) and \(d\). The mass \(\mu_i\) is the fraction of society with that information type, with \(\sum_i\mu_i=1\). The regime is \(N\gg\tau\): millions of voters, but only tens or hundreds of repeated elicitation patterns generated by common questionnaires, demographic cohorts, or recurring policy bundles. Each type is a complete description for the partial-order problem; agents with the same \(O_i\) are interchangeable in every respect the instance uses.
Name the mirror Continuous Borda Possible Winner with Partial-Order Types, \(\mathrm{Borda\text{-}PW}_{\infty}^{(4)}\). An instance consists of candidates \(C\), partial-order types \(O_1,\ldots,O_\tau\), rational masses \(\mu_1,\ldots,\mu_\tau\), and a target candidate \(c\). Let \(E_i\) be the set of linear extensions of \(O_i\). The decision variable is
\[ x_{i,V}\ge 0 \qquad (V\in E_i), \]
where \(x_{i,V}\) is the mass of type \(O_i\) whose completed ranking is \(V\). It must satisfy
\[ \sum_{V\in E_i}x_{i,V}=\mu_i \qquad\text{for every }i. \]
Thus every unit of population receives one integral ranking; only the aggregate masses are fractional. Define the Borda score of candidate \(a\) by
\[ S_x(a)=\sum_{i=1}^{\tau}\sum_{V\in E_i} x_{i,V}\bigl(m-\operatorname{pos}_V(a)\bigr). \]
The optimization version maximizes the target’s minimum winning margin:
\[ \max \delta \]
subject to
\[ S_x(c)-S_x(a)\ge \delta \qquad\text{for every }a\ne c. \]
The continuous possible-unique-winner question asks whether the optimum satisfies \(\delta>0\); the possible-co-winner version asks whether it satisfies \(\delta\ge0\). A solution is the mass allocation \(x\), equivalently a completed continuum society witnessing the target’s victory.
This is a genuine high-multiplicity analogue, not an outcome-space lottery or an evaluation problem. A rational solution \(x\) can be realized exactly by a sufficiently large finite electorate: choose a common denominator \(N\), create \(Nx_{i,V}\) voters of type \(O_i\) with completion \(V\), and recover the original finite election. Conversely, every finite completion induces such an \(x\). The continuous model is therefore the limiting version in which completion mass is no longer restricted to individual-voter granularity.
For the same promise as Corollary 1—at most four undetermined pairs per partial order—each \(O_i\) has at most \(2^4\) linear extensions. The formulation above is therefore a polynomial-size linear program, solvable in polynomial time in \(m\), \(\tau\), and the encoding length of the masses. I would expect this mirror to be Class A under that promise: the paper’s discrete NP-hardness dissolves when a large cohort can split its mass among compatible completions. The interesting unrestricted version has exponentially many extensions per type and becomes exactly the sort of column-generation or pricing problem that the continuization programme is designed to expose.
The authors should recognize this as their problem. It retains Borda, partial orders, possible-winner semantics, the target candidate, and the paper’s strongest four-undetermined-pairs promise. The only change is replacing a list of individually indexed unweighted voters by a distribution of repeated partial-order types and replacing integral completion counts by mass. It does not trivialize the question by changing the voting rule or making candidates fractional.
The mirror covers Corollary 1 only; I would not stretch it to claim that the entire paper has been continuized. It generates several further questions: whether unrestricted partial orders admit an efficient pricing algorithm; whether the corresponding necessary-winner problem has a clean robust optimization formulation; and how finely a finite \(N\)-voter election must approximate the continuous optimum before the winner is preserved.
The weakest point is the regime. The mirror is convincing for a large election with repeated information patterns, but not for a seven-person committee whose voters have idiosyncratic partial orders. Also, the polynomial result uses both continuization and the paper’s four-unknown-pairs promise: bounded uncertainty makes the extensions enumerable. That is a limitation, but not a fatal one. The promise is inherited directly from the paper’s hardness theorem, while the mass allocation is precisely the high-multiplicity operation the programme is meant to study.
The strongest negative case is that Corollary 1 does not naturally describe a high-multiplicity society. In its X3C reduction, each partial order is essentially a set-specific gadget: the \(O_i\) encode different sets \(S_i\). Preserving that combinatorial instance requires \(\tau\) to grow with the number of gadgets, with little repetition. Thus the paper’s hardness construction is not population-multiplicity hardness in disguise; it is a collection of individually tailored information states.
The proposed mirror becomes polynomial under the four-undetermined-pairs promise because every \(O_i\) has only constantly many extensions. Once those extensions are listed, the problem is simply a fractional feasibility LP. The continuous population contributes little beyond replacing integral completion counts by real variables. In particular, the claimed “tens or hundreds of recurring cohorts” is not the regime represented by the reduction: the reduction needs a separate cohort for essentially every set.
A stronger version does not fully repair this objection. One can duplicate every \(O_i\) many times, but then the mass-splitting operation is exactly what destroys the X3C gadget: “choose \(q/3\) sets without overlap” becomes a divisible fractional allocation. That may be an interesting relaxation, but it is no longer a continuous version of the paper’s source of difficulty so much as the ordinary LP relaxation of an integral witness problem. If one instead insists that all members of a type share a genuine complete preference, then the type should be a linear ranking, not a partial order; the unresolved ranking is information about the agent, not the agent’s type.
The unrestricted variant is formally more interesting: one obtains an LP over all linear extensions of each partial order, with a pricing problem over extensions. But that is a new optimization problem whose relevance depends on treating epistemic uncertainty as divisible population mass. The paper itself does not motivate such a population regime, and the proposed application supplies only a generic story about repeated questionnaires rather than evidence that partial-order information is actually repeated at high multiplicity.
Still, this negative case does not meet the stated burden. Corollary 1 is a genuine named computational result; possible-winner feasibility depends only on aggregate scores and not voter identity; and a society of many agents sharing recurring partial-order information patterns is entirely coherent. The LP is not an outcome-space lottery, and allowing each unit of mass to receive an integral completion is compatible with the programme. Thus the objections show that this may be a modest, promise-dependent mirror, but they do not establish 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.