| paper | d4-conf-atal-2011-0057 |
| authors | — |
| venue | ? |
| filed under | unclassified |
| judged by | gpt-6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | medium |
| authors would recognise it | yes |
other→P discrete result → its continuous mirror
Answer: Polynomial-time solvable: both equalities hold for every valid instance. · discrete side: other · adjudication: proved
full proof & adversarial review →
Theorem 10
statement extracted from the paper’s text layer
Given candidates, rational masses over partial-order types, and a fixed priority for pairwise ties, determine whether the profile-based possible and necessary Condorcet-winner sets equal the corresponding sets computed from the incomplete weighted majority graph. For the profile-based sets, feasible completions allocate each type’s mass among its compatible linear orders; the incomplete graph records pairwise majorities forced by the type masses.
Represent the society by a finite support \(T\) of partial-order types with rational masses \(\mu_t\). Use variables \(x_{t,\pi}\ge 0\) for the mass of type \(t\) assigned to compatible linear order \(\pi\), with \(\sum_{\pi\supseteq t}x_{t,\pi}=\mu_t\); derive pairwise outcomes from these allocations using a fixed tie priority, then compare the resulting profile-based winner sets with those from the incomplete weighted majority graph.
The Condorcet mirror may reduce to a routine weighted-majority calculation and offer little need for continuous-optimization machinery.
fatal: False
The mirror covers Theorem 10’s equality for possible and necessary Condorcet winners in voting trees; it leaves the other winner notions and the recursive algorithms’ behavior on general voting trees aside.
The strongest positive case is a large electorate whose members fall into a small number of partially elicited preference types. For example, a large consultation might use the same questionnaire for everyone, yielding millions of respondents but only dozens of distinct patterns of known comparisons. Here \(\tau\), the number of partial-order types, is much smaller than the population.
Let \(t\) be a partial order on the candidates, and let \(\mu_t\) be its share of the population. A completion allocates each type’s mass among its compatible strict rankings: \(x_{t,\pi}\ge 0\), with \(\sum_{\pi\supseteq t}x_{t,\pi}=\mu_t\). The mass assigned to each ranking determines every pairwise majority and hence the winner of a given voting tree. The decision variable is this allocation \(x\); the objective is to determine possible or necessary winners, rather than to optimize a cost. A “yes” answer says the candidate has the requested winner property; a feasible completion witnessing failure is a counterexample.
A continuum can have an exact half-and-half pairwise split, unlike the paper’s odd-sized electorates. I would make a fixed public tie-breaking priority part of the model. This is a small co-modification needed to define the voting rule at the boundary, and it preserves the paper’s central object: winners under pairwise voting over a population.
The paper contains no named theorem classifying a winner problem as NP-hard, in P, FPT, or another complexity class. Its named results are computationally relevant correctness and representation results. I use those as anchors, without presenting them as complexity classifications.
Lead — Continuous Necessary Winner for a Fixed Tree. Theorem 6, proved here, says there is an incomplete profile \(P\) and a simple voting tree \(T\) for which a candidate \(A\) wins for every completion of \(P\), while \(A\) is not a necessary winner from the incomplete majority graph \(M(P)\). In the paper’s witness there are six candidates and five voters; only one voter is incomplete. The tree matches \(C\) against \(F\), \(E\) against \(D\), their winners against each other, then the winner against \(B\), and finally against \(A\). The majority-graph algorithm finds both \(A\) and \(B\) possible, so it finds no necessary winner; nevertheless, \(A\) wins the tree under every profile completion.
The mirror, Continuous Necessary Winner for a Fixed Tree, takes a candidate set, a fixed simple tree, a finite support of partial-order types with rational masses, and a target candidate. It asks whether the target wins under every feasible mass allocation to linear extensions. I would investigate the variable-\(m\) problem as a Class C candidate: a fixed pattern of pairwise outcomes can be checked with linear constraints, but choosing a feasible pattern that makes the target lose couples many majority comparisons through the same ranking distribution. A reduction would be needed to establish hardness; Theorem 6 itself provides none. A tractability result, or a classification in \(m,\tau,L\) and tree size, would be the immediate next question.
Continuous Necessary Schwartz Winner. Theorem 1, also proved here, says there is an incomplete profile \(P\) with \(A\in\mathrm{NecS}(P)\) but \(A\notin\mathrm{NecS}(M(P))\): in every completion of the profile, some simple tree makes \(A\) win, although the majority-graph notion does not classify \(A\) as a necessary Schwartz winner. The witness uses five candidates, \(\{A,A_1,B_1,B_2,B_3\}\), and five voters, only one of whom has incomplete preferences. The proof uses a characterization of majority-graph winners cited from [5].
The continuous question takes the same mass-based input and asks whether, for every feasible completion, there exists a simple voting tree in which the target wins; the tree may vary with the completion. My working expectation is again Class C, with even more caution: the question has a universal completion quantifier and an existential agenda quantifier, while choices about pairwise outcomes remain linked by the common completion. It is worth asking whether this can be reduced to a continuous optimization problem, and whether it is fixed-parameter tractable in \(m\). The paper’s finite counterexample motivates that question; it does not establish the continuous answer.
Continuous Condorcet Consistency. Theorem 10 states that, for voting trees, the profile-based and majority-graph-based sets of possible Condorcet winners are equal, and the same is true of necessary Condorcet winners. The theorem is stated here; its proof follows the argument of [8] and applies it to general voting trees.
The mirror asks, for a mass distribution over partial-order types, whether the possible and necessary Condorcet-winner sets computed from feasible population completions agree with those computed from the incomplete majority graph. I expect this problem to be Class A. For each target, one can ask whether the population can be completed to put the target above all opponents, or whether every completion does so. A type can be completed to place the target above every candidate it does not force above the target; that choice handles all pairwise comparisons involving the target at once. This gives a direct route to testing the two winner notions in time polynomial in \(m,\tau,L\). A useful follow-up is to formalize the exact graph summary under the tie-breaking convention and determine whether Theorem 10’s equality survives unchanged.
These questions cover the paper’s results on necessary winners, necessary Schwartz winners, and Condorcet winners. They do not attempt to mirror the paper’s separate results about the recursive algorithm on general voting trees.
The weak point is real: allowing mass from one partial-order type to split among its linear extensions is more permissive than completing one finite voter’s ballot. It may erase the particular five-voter discrepancies in Theorems 1 and 6. I would not claim those witnesses transfer. The case for a mirror is that the underlying population regime is sensible, and the resulting questions preserve the paper’s central computation—winner determination from uncertain pairwise preferences—while making the continuum’s effect on those results something precise to prove.
The strongest case against is about what this paper contributes. Its named results compare winner sets computed from an incomplete profile with those computed from its majority graph, and establish when particular algorithms give exact answers or approximations. The paper does not classify a continuous or discrete winner problem by complexity. So the proposed mirrors would launch a new line of complexity questions from this paper’s setting; they would not continue a complexity result the paper established. That weakens the claim that these are natural ChoCo targets, but it does not rule them out.
The fixed-tree necessary-winner question is the hardest anchor to defeat. The proposed type space—partial-order ballots with rational masses—and allocations of each type’s mass among its linear extensions is a coherent high-multiplicity model. A large survey with repeated patterns of known comparisons is plausible, and the fixed-tree question remains well-defined with a stated tie rule. Theorem 6’s five-voter witness does not by itself show what happens in that model: splitting mass among completions can create aggregate pairwise patterns unavailable in the finite witness. But that is a transfer question, not a modeling objection. More damaging to the case against, those coupled pairwise outcomes give a real computational question: a common distribution over rankings must satisfy the tree’s winner conditions. I cannot honestly show that no useful continuous mirror exists here.
The necessary-Schwartz mirror is less independent. Its \(\forall\) completion, \(\exists\) tree quantifiers make it a more complicated cousin of the fixed-tree question, not a separate demonstration that continuization is valuable. Theorem 1’s witness likewise does not establish a continuous result. Still, a population with repeated partial-order types could ask whether every feasible completion permits some agenda under which the target wins. Calling this unpromising because the agenda search may carry substantial combinatorics would amount to saying the answer might be hard; that is not a valid objection under the programme’s criteria.
The Condorcet mirror is the best target for a negative argument. With a fixed tie rule, whether a candidate can or must beat each opponent can be checked from type masses and which pairwise comparisons each type forces. This looks like a direct weighted version of the paper’s equality, with little need for continuous-optimization machinery. It may be too small to justify a project on its own. But a simple result is still a result, and it does not defeat the fixed-tree anchor.
So the honest negative case is a case about priority: this paper supplies a useful model and representation question, but no named complexity classification, and its Condorcet result may yield only an elementary mass calculation. I cannot make the stronger universal claim that no scenario produces a worthwhile mirror. A large population with repeated partial preference patterns is credible, and the fixed-tree question survives the strongest objections I can make.
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.