| paper | Dominating Manipulations in Voting with Partial Information |
| authors | Vincent Conitzer, T. Walsh, Lirong Xia |
| venue | AAAI 2011 |
| filed under | voting · incomplete-info |
| judged by | gpt-5.6-luna / xhigh (triple__luna__xhigh__c6r1) |
| judge confidence | high |
| authors would recognise it | yes |
Answer: Polynomial-time solvable; the problem belongs to \(\mathsf{P}\). · discrete side: hardness · adjudication: proved
full proof & adversarial review →
Theorem 4
statement extracted from the paper’s text layer
Given candidates \(C\), a fixed tie-breaking order, a finite set of partial-order types \(T\) with at most four unknown pairs each, rational masses \(\mu_t\), a distinguished manipulator with true ranking \(V_M\), and ballots \(V,U\), does \(U\) dominate \(V\) over every admissible mass allocation among the linear extensions of each type, with strict improvement for at least one allocation?
A high-multiplicity electorate is represented by masses \(\mu_t\) of partial-order types, with decision variables \(x_{t,\ell}\geq 0\) satisfying \(\sum_{\ell\in L(t)}x_{t,\ell}=\mu_t\); Borda scores are induced by these masses plus either one distinguished atomic manipulator or a fixed-weight representative bloc, and domination compares winners under \(U\) and \(V\) universally and existentially over feasible allocations.
A single manipulator becomes negligible when the non-manipulator population is normalized and multiplicities grow; assigning fixed positive mass to the manipulator changes the one-voter model into bloc manipulation.
fatal: False
The mirror covers Theorem 4's Borda domination hardness, and potentially its dominating-manipulation variant, but not the paper's immunity results, WMG reductions, plurality or veto algorithms, or unbounded partial-order uncertainty.
The strongest positive case is a deliberately narrow one: mirror the Borda domination result in Theorem 4.
Theorem 4 states that, with partial orders as the manipulator’s information representation, both domination and dominating manipulation are NP-hard for Borda, even when every partial order contains at most four unknown pairs. This is an in-paper result. The supplied text gives the X3C reduction for domination; it states that the dominating-manipulation proof is analogous but omits it for space. I rely on the domination half as the lead anchor.
Call the continuous problem Borda-Partial-Information Domination\(_\infty\). An instance contains candidates \(C\), a fixed tie-breaking order, a finite set \(T\) of partial-order types, a rational mass distribution \(\mu\) over \(T\), the manipulator’s true ranking \(V_M\), and two ballots \(V\) and \(U\). Each type \(t\in T\) is a partial order \(O_t\), with at most four undetermined pairs. Its mass \(\mu_t\) is the fraction of non-manipulator society known only to have information type \(O_t\).
For every \(t\), let \(L(t)\) be the set of linear extensions of \(O_t\). A possible aggregate realization is a collection of masses \(x_{t,\ell}\geq 0\), satisfying
\[ \sum_{\ell\in L(t)}x_{t,\ell}=\mu_t \]
for every \(t\). Thus a type’s mass may be distributed fractionally among its possible complete rankings. The resulting Borda score of candidate \(c\), when the manipulator votes \(W\), is
\[ S_x^W(c) = \sum_{t\in T}\sum_{\ell\in L(t)} x_{t,\ell}\bigl(m-\operatorname{pos}_{\ell}(c)\bigr) + \lambda\bigl(m-\operatorname{pos}_{W}(c)\bigr), \]
where \(\lambda\) is the manipulator’s voting weight relative to the normalized population. Setting \(\lambda=1/N\) gives the direct analogue of one manipulator among \(N\) voters; a fixed \(\lambda\) models a small representative bloc.
The question is whether \(U\) dominates \(V\): for every admissible completion \(x\), the Borda winner under \(U\) is at least as preferred by \(V_M\) as the winner under \(V\), and for at least one admissible \(x\), it is strictly preferred. The objective is therefore exactly the paper’s robust ordinal objective—not expected utility, randomized voting, or an average completion.
This is a natural high-multiplicity regime. Imagine a large electorate partitioned into demographic or survey cohorts. Many voters share the same disclosed partial-ranking pattern, while the manipulator knows only those patterns and not each individual’s complete ranking. Here \(N\) is large, \(\tau=|T|\) is comparatively small, and \(N\mu_t\) is the number of voters in cohort \(t\). A partial order is a complete type description for this problem: two voters of the same type are indistinguishable with respect to the information available to the manipulator.
The authors should recognize this as their problem. The candidates, Borda rule, truthful ballot, alternative ballot, partial-order information, and universal/existential definition of domination are unchanged. Only the profile representation has been replaced by masses of repeated information types. In the finite high-multiplicity version, \(x_{t,\ell}\) would be integral counts; the continuum permits fractional counts. That is precisely the relaxation being tested.
I expect this continuous problem to be in Class A in the bounded-uncertainty regime of Theorem 4. Since each \(O_t\) has at most four unknown pairs, it has at most \(2^4\) consistent linear extensions. To test whether \(U\) can produce a strict improvement over \(V\), enumerate candidate winners \(a,b\) with \(a\succ_{V_M}b\), and ask whether there is an \(x\) such that \(a\) wins under \(U\) and \(b\) wins under \(V\). Mass conservation and all Borda winner conditions are linear inequalities in the variables \(x_{t,\ell}\). Hence each case is a polynomial-size linear program. \(U\) dominates \(V\) exactly when some forward improvement is feasible and no reverse improvement is feasible.
The X3C hardness in Theorem 4 is therefore a strong reason to study this mirror. Its reduction uses integral choices: each partial-order vote must be completed in one way, and the selected completions encode an exact cover. In the continuous problem, mass belonging to one type can be split fractionally among its extensions. The exact-cover constraints become fractional covering constraints, which the LP can solve. The discrete NP-hardness may consequently dissolve—not because Borda or domination has been changed, but because population multiplicity was the source of the integrality.
This mirror deliberately covers only Theorem 4’s domination result. The existential variant, asking whether some ballot \(U\) dominates the truthful ballot \(V_M\), is a further question: the population is continuous but the manipulator’s action remains a discrete ranking. It may have a different complexity classification. Likewise, if partial orders are allowed to have many unknown pairs, the number of extensions may become exponential and continuum-specific hardness could survive in the pricing problem.
The weakest point is that Theorem 4’s own X3C construction uses many distinct partial orders—one for each 3-set—so its hard instances do not themselves demonstrate a regime with \(\tau\ll N\). The proposed mirror depends on a plausible repeated-template electorate rather than on the paper’s particular reduction instances. A formal high-multiplicity dictionary, including how ties behave when aggregate scores lie exactly on boundaries, would still be needed. But that is a limitation of the evidence, not a failure of the model: the continuous question preserves the paper’s strategic problem while exposing exactly the integral population structure that may be responsible for its hardness.
The strongest objection is that the proposed mirror does not preserve the paper’s central strategic object. The paper has one manipulator casting one ballot against a finite profile. If the non-manipulators are normalized to mass \(1\), that ballot has mass \(1/N\); as multiplicities grow, its influence tends to zero. Away from exact score ties, changing \(V\) to \(U\) then changes no winner, so domination becomes generically vacuous. The continuous limit has erased the strategic agent.
The proposed repair, a fixed \(\lambda>0\), is not innocuous. It replaces one manipulator by a positive-mass bloc whose members act identically. That may be a sensible weighted-manipulation problem, but it is no longer the one-voter domination problem of Theorem 4. The paper’s universal quantification over completions of individually existing voters has been replaced by a collective action against a continuum.
There is also a more substantive semantic change. In the paper, an information set is a Cartesian product of completions: every voter has one fixed but unknown linear order. The variables \(x_{t,\ell}\) instead let a single partial-order type be fractionally split among several completions. This convexifies the set of possible profiles. For Borda scores that looks harmless because scores are linear, but domination is about winners, tie-breaking, and strict ordinal improvement; those are discontinuous at score boundaries. Thus the LP is not automatically a continuous version of the paper’s decision problem. It is a new robust optimization problem over a convexified uncertainty set, and a limiting theorem would be needed to justify that replacement.
Theorem 4 itself provides little evidence that population multiplicity is the relevant source of difficulty. In its X3C construction, each set \(S_j\) creates a different partial order \(O_j\), and the hard instance uses those distinct orders essentially once. The combinatorics live in selecting compatible completions of many different information states, not in allocating mass among repeated voter types. Repeating the whole construction creates a high-multiplicity instance, but then the proposed fractional model precisely relaxes away the integral choices responsible for the reduction. That may be an interesting result, but it is not evidence that the original theorem was computationally about population multiplicity.
Still, this does not support the requested universal negative. A stronger formulation can retain a continuum of non-manipulators together with a distinguished atomic manipulator, or replace the manipulator by a small representative bloc. With that convention, the paper’s authors would plausibly recognize the model: Borda, partial-order information, the same robust domination relation, and only the electorate’s repeated structure changed. For boundedly many unknown pairs, the extension variables really do give a polynomial-size LP. The fact that the answer may be an easy Class A result is not an objection under this programme.
So the negative case can reject the proponent’s exact normalization as either degenerate or semantically altered, and can show that Theorem 4 is not naturally a high-multiplicity hardness result. But it cannot honestly defeat the repaired atomic-or-bloc mirror. The anchor therefore survives, and the universal claim that no worthwhile continuous mirror exists is too strong.
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.