Complexity of Manipulation with Partial Information in Voting (d4-conf-ijcai-2016-0516)

Given candidates \(C\), fixed \(k>1\), rational masses \(\mu_p\) over partial-vote types \(p\) with at most four undetermined pairs, manipulator mass \(\lambda>0\), and preferred candidate \(c\), decide whether there exist a bloc vote \(v\in L(C)\) and nonnegative masses \(x_{p,\rho}\) satisfying \(\sum_{\rho\succeq p}x_{p,\rho}=\mu_p\) such that \(c\) is the unique \(k\)-approval winner of the completion masses plus mass \(\lambda\) voting \(v\).

Fix an integer \(k>1\). Let \(C\) have \(m>k\) candidates and let \(c\in C\).
A society is given by its support: a list of \(\tau\geq1\) partial-order types \(p\), each with positive mass \(\mu_p\) encoded as a binary rational; \(\tau\) is the support size, not the number of possible types. Masses need not sum to one.
Each \(p\) has at most four incomparable unordered candidate pairs. Let \(L(C)\) denote the strict linear orders on \(C\), and write \(\rho\succeq p\) when \(\rho\) extends \(p\).
The input also contains a positive binary-rational manipulator mass \(\lambda\). This entire mass must cast one common vote \(v\in L(C)\).
A completion assigns real masses \(x_{p,\rho}\geq0\) to extensions, with \(\sum_{\rho\succeq p}x_{p,\rho}=\mu_p\) for every support type.
Apply \(k\)-approval with scores weighted by these masses and by \(\lambda\) for vote \(v\). Success means that \(c\)'s score is strictly greater than every rival's; ties do not count as success.
Let \(L\) be the total binary input length. State running times in \(m,\tau,L\), with \(k\) fixed.

Is deciding whether there exist such a bloc vote and completion making \(c\) the unique \(k\)-approval winner in \(\mathrm{P}\), or is it \(\mathrm{NP}\)-hard, for each fixed \(k>1\)?

Discrete weak manipulation is \(\mathrm{NP}\)-complete for every fixed \(k>1\), even with one manipulator and at most four undetermined pairs per partial vote. [Verified source](https://arxiv.org/pdf/1604.04359v2)
No result settling this exact divisible-mass completion problem was identified in the literature search.

Result

The problem is in \(\mathrm{P}\) for every fixed \(k>1\).

A running-time bound is
\(O(\tau m^3)+\binom{m-1}{k-1}\operatorname{poly}(m+\tau+L)\),
where the polynomial is independent of \(k\). The algorithm preserves the requirement that the entire manipulator mass casts one common vote.

1. Enumerating each type’s extensions

For a support type \(p\), let \(I_p\) be its set of incomparable unordered candidate pairs. By assumption, \(|I_p|\leq4\).

Every linear extension specifies one orientation of each pair in \(I_p\). These orientations, together with the comparisons already specified by \(p\), determine the comparison of every distinct candidate pair. Consequently, distinct linear extensions give distinct orientation assignments, and
\(|\{\rho\in L(C):\rho\succeq p\}|\leq2^{|I_p|}\leq16\).

We can enumerate the extensions as follows:

• Compute the transitive closure of the supplied order relation.
• Enumerate all orientations of its incomparable pairs.
• For each assignment, test the resulting directed graph for acyclicity.

The graph in the last step specifies exactly one direction between every distinct pair. If it is acyclic, its topological order is unique: the edge between any two candidates determines their relative positions. This order extends \(p\). Conversely, every linear extension produces an acyclic assignment and is therefore enumerated.

Write \(E_p\) for the resulting extension set. Transitive closure takes \(O(m^3)\) time per type, and each of the at most \(16\) acyclicity tests takes \(O(m^2)\) time. Thus preprocessing takes \(O(\tau m^3)\) time, and
\(\sum_p|E_p|\leq16\tau\).

2. Enumerating the bloc’s approval sets

We may restrict attention to bloc votes approving \(c\).

Indeed, suppose a successful bloc vote does not approve \(c\). Exchange \(c\)’s position with that of any approved candidate \(d\), keeping the completion fixed. This increases \(c\)’s score by \(\lambda\), decreases \(d\)’s score by \(\lambda\), and leaves every other score unchanged. Every winning margin remains strictly positive.

Under \(k\)-approval, only the set of candidates in the first \(k\) positions matters. We therefore enumerate sets
\(S\subseteq C\setminus\{c\}\) with \(|S|=k-1\),
and let the bloc approve exactly \(\{c\}\cup S\).

There are \(\binom{m-1}{k-1}\) possibilities. Every such set is realized by a single linear-order vote: put its candidates in the first \(k\) positions and order the remaining candidates arbitrarily.

3. An exact linear program for one approval set

Fix an enumerated set \(S\). For every \(p\), \(\rho\in E_p\), and candidate \(a\), define
\(A_{p,\rho}(a)=1\) if \(\rho\) ranks \(a\) among its first \(k\) positions, and \(A_{p,\rho}(a)=0\) otherwise.

Introduce variables \(x_{p,\rho}\) for the completion masses and a variable \(\delta\) for a common winning margin. Maximize \(\delta\), subject to:

• \(x_{p,\rho}\geq0\) for every \(p\) and \(\rho\in E_p\);
• \(\sum_{\rho\in E_p}x_{p,\rho}=\mu_p\) for every \(p\);
• \(0\leq\delta\leq\lambda\);
• for every rival \(a\neq c\),

\(\sum_p\sum_{\rho\in E_p}\bigl(A_{p,\rho}(c)-A_{p,\rho}(a)\bigr)x_{p,\rho}+\lambda\bigl(1-\mathbf{1}_{a\in S}\bigr)\geq\delta\).

Here \(\mathbf{1}_{a\in S}\) denotes the indicator of membership in \(S\). The last constraint states exactly that \(c\)’s total score exceeds \(a\)’s total score by at least \(\delta\).

Claim. The approval set \(\{c\}\cup S\) permits success if and only if this linear program is feasible and its optimum is strictly positive.

Proof. Suppose a successful completion exists. Since there are finitely many rivals, the minimum winning margin
\(g=\min_{a\neq c}\bigl(\operatorname{score}(c)-\operatorname{score}(a)\bigr)\)
is strictly positive. Its completion masses, together with \(\delta=\min\{g,\lambda\}>0\), satisfy every constraint.

Conversely, any feasible solution with \(\delta>0\) supplies completion masses satisfying all support-mass requirements and gives \(c\) a strictly positive margin over every rival.

Finally, whenever feasible, the program attains its optimum. Its feasible region is closed and bounded: the mass constraints imply \(0\leq x_{p,\rho}\leq\mu_p\), and \(0\leq\delta\leq\lambda\). Thus a positive optimum yields the required feasible solution. \(\square\)

This handles strict victory without imposing an arbitrary minimum margin.

4. Bit complexity and correctness

Each program has at most \(16\tau+1\) variables and \(O(m+\tau)\) constraints. Its constraint coefficients belong to \(\{-1,0,1\}\), and its right-hand sides use only \(0\), \(\lambda\), and the input masses \(\mu_p\). Its binary encoding length is therefore polynomial in \(m+\tau+L\).

The standard polynomial-time theorem for rational linear programming applies: feasibility and, when feasible, the exact rational optimum can be computed in time polynomial in the program’s encoding length. In particular, comparison of the optimum with zero is exact. This theorem optimizes over real variables, so it applies directly to the permitted real completion masses.

The algorithm accepts if some enumerated program has positive optimum. Section 2 shows that every successful instance has a successful enumerated approval set; Section 3 proves that its program has positive optimum. Conversely, every accepted program supplies a successful completion and a realizable common bloc vote.

The total running time is therefore
\(O(\tau m^3)+\binom{m-1}{k-1}\operatorname{poly}(m+\tau+L)\).
Since \(\binom{m-1}{k-1}\leq m^{k-1}\), this is polynomial for every fixed \(k>1\). No normalization of the masses is needed.

5. Relation to discrete hardness

The cited discrete problem is \(\mathrm{NP}\)-complete under the same four-pair restriction. [Dey, Misra, and Narahari, Theorem 1](https://arxiv.org/pdf/1604.04359v2)

In that setting, each partial vote must select one extension. Here each type may distribute its mass among extensions, making the completion constraints linear. The bloc retains a discrete choice, but for fixed \(k\) its relevant approval sets can be exhaustively enumerated in polynomial time.

⟨structured verdict parsed — rendered above⟩

Verification report

Verdict: proved. The output establishes a polynomial-time algorithm for every fixed \(k>1\). The extension enumeration, restriction on bloc votes, and rational linear program are correct. No major or minor mathematical issues were found.

1. Enumeration of extensions

The bound \(|E_p|\leq 16\) is justified. An extension fixes the orientation of every incomparable pair; the partial order already fixes every other comparison. Two different linear orders therefore cannot produce the same orientation assignment.

The enumeration procedure is also correct:

• Taking transitive closure identifies incomparability in the partial order, rather than merely missing edges in its representation.
• Orienting every incomparable pair produces a directed graph with exactly one direction for every distinct candidate pair.
• An acyclic such graph has a unique topological order, because every pair’s relative order is prescribed.
• Every extension of \(p\) produces one of the tested acyclic assignments.

Thus the procedure enumerates exactly \(E_p\). The stated preprocessing bound \(O(\tau m^3)\) accommodates transitive closure, all orientation tests, and extraction of the orders. The case of a fully specified type is covered by the single empty orientation assignment.

2. Restriction to bloc votes approving \(c\)

The exchange argument is valid with the completion held fixed.

If the bloc initially approves \(d\) but not \(c\), exchanging their positions increases \(c\)’s score by \(\lambda\) and decreases \(d\)’s score by \(\lambda\). Consequently, the margin against \(d\) increases by \(2\lambda\), and every other rival’s margin increases by \(\lambda\). Strict victory is preserved.

There is an approved candidate available for this exchange, since \(k>1\). After the exchange, the bloc still casts one common linear-order vote.

Enumerating the \(\binom{m-1}{k-1}\) sets \(S\) therefore covers all relevant bloc choices. Each approval set \(\{c\}\cup S\) is realizable by a single vote. The assumption \(m>k\) ensures that the requested set sizes are valid.

3. Linear-program formulation

The completion variables correspond exactly to the allowed extensions, and their nonnegativity and mass equalities reproduce the task’s completion requirements.

For each rival \(a\), the expression
\[ \sum_p\sum_{\rho\in E_p} \bigl(A_{p,\rho}(c)-A_{p,\rho}(a)\bigr)x_{p,\rho} +\lambda\bigl(1-\mathbf{1}_{a\in S}\bigr) \]
is exactly \(c\)’s score minus \(a\)’s score. The bloc contribution is zero when it approves both candidates and \(\lambda\) when it approves only \(c\).

The common-margin formulation handles strict victory correctly:

• A successful completion has finitely many strictly positive rival margins, so their minimum \(g\) is positive.
• Since \(\lambda>0\), the choice \(\delta=\min\{g,\lambda\}\) is positive and feasible.
• Conversely, a feasible point with \(\delta>0\) makes every rival’s score strictly smaller than \(c\)’s.

The upper bound \(\delta\leq\lambda\) does not exclude any successful completion; it only caps the auxiliary margin variable.

The attainment argument is valid. The feasible region is closed, and each mass variable lies in \([0,\mu_p]\), while \(\delta\in[0,\lambda]\). Thus, whenever feasible, the continuous objective attains its maximum. Infeasible programs and feasible programs with optimum zero are correctly rejected.

4. Exact computation and running time

There are at most \(16\tau+1\) variables. Including nonnegativity constraints, the number of constraints remains \(O(m+\tau)\).

All coefficients and constants are rational, with binary encoding length polynomial in \(m+\tau+L\). In particular, the algorithm does not expand a binary-encoded mass into individual voters.

The invoked rational linear-programming theorem is stated sufficiently precisely: feasibility and an exact rational optimum can be computed in polynomial time in the encoded program size. Its hypotheses hold here. Feasible programs are bounded, so there is no unbounded-objective case to resolve. Exact comparison with zero is consequently justified; floating-point tolerances are not being substituted for strict victory.

The combined running time
\[ O(\tau m^3)+\binom{m-1}{k-1}\operatorname{poly}(m+\tau+L) \]
follows from preprocessing once and solving one program per approval set. Since \(\binom{m-1}{k-1}\leq m^{k-1}\), this is polynomial for each fixed \(k\). Neither normalization of masses nor integrality of completion variables is required.

5. Correctness and discrete-hardness comparison

Both directions of the algorithm’s correctness follow from the established equivalences: every successful instance has an enumerated successful approval set, and every accepted program supplies an admissible completion and a realizable common bloc vote.

The ancillary citation is accurate: Theorem 1 states discrete weak-manipulation NP-completeness for every constant \(k>1\), with one manipulator and at most four undetermined pairs per vote; the paper explicitly uses unique winners. [Dey, Misra, and Narahari](https://arxiv.org/pdf/1604.04359v2)

That discrete result does not contradict this algorithm. The output correctly identifies that divisible completion masses permit linear constraints, while the remaining bloc choices are polynomially enumerable for fixed \(k\).

Repair feedback: No additional mathematical clarification is needed.

⟨structured verdict parsed — rendered above⟩