d4-conf-ijcai-2011-0420 (d4-conf-ijcai-2011-0420)

Given a candidate set \(C\), a rational distribution \(\nu\) over nonmanipulator rankings with total mass \(1-\varepsilon\), a strategic type of mass \(\varepsilon>0\) with true ranking \(R^\star\) and utility \(u\), rational \(q\), and rational \(\alpha\in[0,1]\), does there exist a ranking \(L\) for the strategic type such that the average utility of the Copeland\(_\alpha\) winners under the resulting society \(\mu_L=\nu+\varepsilon\delta_L\) is at least \(q\)? Pairwise contests are decided by comparing ranking masses, with equal masses counted as ties.

Let \(C\) be a nonempty candidate set with \(m=|C|\); all rankings are strict linear orders. A society is given by its support: the list of its \(\tau\) types with positive mass, each mass a binary rational; \(\tau\) is support size, not the number of possible rankings.
The input consists of a nonmanipulator society \(\nu\) of total mass \(1-\varepsilon\), rational \(0<\varepsilon\leq1\), a strategic type with true ranking \(R^\star\), binary-encoded utilities \(u:C\to\mathbb Z_{\geq0}\), rational \(q\geq0\), and rational \(\alpha\in[0,1]\). Require \(a\succ_{R^\star}b\Rightarrow u(a)\geq u(b)\); equal utilities are allowed.
The strategic type submits one strict ranking \(L\) for its entire mass, producing \(\mu_L=\nu+\varepsilon\delta_L\), where \(\delta_L\) is unit mass at \(L\). Pairwise contests compare the masses ranking either candidate above the other, with equal masses counted as ties.
Use Copeland\(_\alpha\), and let \(W(L)\) be all candidates attaining the maximum score. Select uniformly from \(W(L)\), giving expected utility \(\frac{1}{|W(L)|}\sum_{c\in W(L)}u(c)\).
Decide whether some \(L\) gives expected utility at least \(q\). Here \(\tau=|\operatorname{supp}\nu|\), and \(L_{\mathrm{bits}}\) is the total input bit length; state running times in \(m,\tau,L_{\mathrm{bits}}\).

Is this decision problem solvable in polynomial time in \(m,\tau,L_{\mathrm{bits}}\), or is it NP-hard?

For finite unweighted electorates with one manipulating voter and uniform selection among Copeland\(_\alpha\) winners, the corresponding decision problem is NP-complete for every fixed rational \(\alpha\in[0,1]\). [Discrete result](https://comsoc-community.org/assets/proceedings/comsoc-2012/Obraztsova.pdf)
No result for exactly the rational-mass problem stated above was identified in the literature search.

Result

The decision problem is \(\mathrm{NP}\)-complete, both when \(\alpha\) is part of the input and for every fixed rational \(\alpha\in[0,1]\). Consequently, it has no polynomial-time algorithm in \(m,\tau,L_{\mathrm{bits}}\) unless \(\mathrm{P}=\mathrm{NP}\).

The proof uses the discrete hardness theorem supplied in the question and an exact, polynomial-size reduction to the stated support representation.

1. Membership in \(\mathrm{NP}\)

Write \(B=L_{\mathrm{bits}}\). A certificate is a strict ranking \(L\), represented as a permutation of \(C\), using \(O(m\log m)\) bits.

Suppose the nonmanipulator support consists of rankings \(R_1,\ldots,R_\tau\) with masses \(w_1,\ldots,w_\tau\). For distinct candidates \(a,b\), define \(\sigma_R(a,b)=1\) if \(a\succ_R b\), and \(\sigma_R(a,b)=-1\) otherwise. The pairwise margin after submitting \(L\) is
\[ \Delta_L(a,b)=\sum_{i=1}^{\tau}w_i\sigma_{R_i}(a,b)+\varepsilon\sigma_L(a,b). \]
Its sign determines whether \(a\) wins, ties, or loses against \(b\).

All these signs can be computed exactly in polynomial time. Specifically, let \(D\) be the product of the denominators of the support masses and \(\varepsilon\). Its bit length is \(O(B)\), because the sum of those denominator bit lengths is bounded by the input length. Multiplying each margin by \(D\) reduces its sign computation to integer arithmetic on \(O(B)\)-bit integers. There are \(O(m^2)\) candidate pairs.

Write \(\alpha=h/k\), with integers \(k>0\) and \(0\leq h\leq k\). If candidate \(c\) has \(v_c\) pairwise victories and \(t_c\) pairwise ties, its Copeland score is \((kv_c+ht_c)/k\). Thus \(W(L)\) is obtained by comparing the integers \(kv_c+ht_c\).

Finally, write \(q=p/r\), with integers \(p\geq0\) and \(r>0\). Since \(C\) is nonempty, \(W(L)\) is nonempty. The required utility comparison is exactly
\[ r\sum_{c\in W(L)}u(c)\ \geq\ p\,|W(L)|. \]
This also uses polynomial-bit-length integers.

Using ordinary quadratic-time integer arithmetic, a conservative verification bound is \(O((\tau+1)m^2B^2)\) bit operations. Hence the problem belongs to \(\mathrm{NP}\), including when \(\alpha\) is an input rational.

2. Exact reduction from the discrete problem

Fix any rational \(\alpha\in[0,1]\). The supplied discrete result states that manipulation by one voter, with expected utility under uniform selection from the Copeland winners, is \(\mathrm{NP}\)-complete for this fixed \(\alpha\). This is Theorem 4.8 of [Obraztsova, Zick, and Elkind, *On the Complexity of Voting Manipulation under Randomized Tie-Breaking*](https://comsoc-community.org/assets/proceedings/comsoc-2012/Obraztsova.pdf).

Take an instance of that discrete problem with \(n\geq1\) voters, where the last voter manipulates. Denote the nonmanipulator rankings by \(R_1,\ldots,R_{n-1}\).

Retain the candidate set, utilities, threshold, and Copeland parameter. Define
\[ \varepsilon=\frac1n, \qquad \nu=\frac1n\sum_{i=1}^{n-1}\delta_{R_i}. \]
Choose \(R^\star\) by sorting candidates in nonincreasing utility order, breaking equal-utility ties arbitrarily. This gives a strict ranking satisfying the required utility consistency condition. Its particular choice does not affect the evaluation of a submitted ranking \(L\).

Validity and encoding size

The constructed instance has \(0<\varepsilon\leq1\) and nonmanipulator mass \((n-1)/n=1-\varepsilon\).

To produce its support representation, group identical nonmanipulator rankings. If ranking \(R\) occurs \(k_R>0\) times, give it mass \(k_R/n\). Therefore \(\tau\leq n-1\), and every mass has a binary numerator and denominator of \(O(\log n)\) bits.

Grouping and writing these entries takes polynomial time in the explicitly listed discrete input. The reduction lists only rankings that occur; it never enumerates all possible rankings.

Preservation of every possible outcome

For every submitted strict ranking \(L\) and every distinct \(a,b\), the rational-mass margin is
\[ \Delta_L(a,b) = \frac1n \left( \sum_{i=1}^{n-1}\sigma_{R_i}(a,b)+\sigma_L(a,b) \right). \]
The parenthesized expression is exactly the discrete pairwise margin after the manipulating voter submits \(L\).

Multiplication by the positive number \(1/n\) preserves positive, zero, and negative margins. Hence every pairwise victory, tie, and loss is identical in the two instances. Their Copeland scores and winner sets consequently coincide.

The utilities are unchanged, so uniform selection from these identical winner sets gives identical expected utility. Thus, for every \(L\), the discrete instance meets its threshold precisely when the constructed instance does. This proves a polynomial-time many-one reduction.

3. If “binary rational” means dyadic rational

The reduction also works if masses must have denominators that are powers of two.

Let \(N\) be the least power of two satisfying \(N\geq n\). Set \(\varepsilon=1/N\) and give every original nonmanipulator vote mass \(1/N\). Choose any strict ranking \(H\), and let \(\overline H\) be its reverse. Add to \(\nu\) mass \((N-n)/(2N)\) at each of \(H\) and \(\overline H\), omitting these entries when their mass is zero and merging duplicate rankings.

The resulting nonmanipulator mass is
\[ \frac{n-1}{N}+2\frac{N-n}{2N}=1-\frac1N. \]
All masses are dyadic. For each distinct pair \(a,b\), the added rankings cancel because \(\sigma_H(a,b)+\sigma_{\overline H}(a,b)=0\). Thus the final margin is exactly the original discrete margin divided by \(N\). The outcome-preservation proof remains unchanged.

There are at most \(n+1\) support entries, each with \(O(\log n)\)-bit masses, so this construction is also polynomial.

4. Running times and conclusion

The reduction proves \(\mathrm{NP}\)-hardness for every fixed rational \(\alpha\); the verifier proves membership in \(\mathrm{NP}\). Allowing \(\alpha\) as input preserves membership and includes any fixed-\(\alpha\) hard subclass.

For completeness, an exact deterministic algorithm can enumerate all \(m!\) submitted rankings. Precomputing the nonmanipulator margins once gives the conservative running-time bound
\[ O\!\left((\tau+1+m!)m^2L_{\mathrm{bits}}^2\right). \]
The polynomial verification bound is \(O((\tau+1)m^2L_{\mathrm{bits}}^2)\). A polynomial deterministic bound in all three stated parameters exists if and only if \(\mathrm{P}=\mathrm{NP}\).

⟨structured verdict parsed — rendered above⟩

The prover’s conclusion is correct: the stated rational-mass decision problem is \(\mathrm{NP}\)-complete for every fixed rational \(\alpha\in[0,1]\), and also when \(\alpha\) is part of the input. The reduction preserves every submitted ranking’s outcome exactly. No major or minor mathematical issues were found.

1. The cited discrete hardness theorem

The cited paper’s Theorem 4.8 states that Copeland\(_\alpha\)-RANDMANIPULATION is \(\mathrm{NP}\)-complete for every rational \(\alpha\in[0,1]\). Its model uses explicitly listed strict rankings, one manipulating voter, binary-encoded integer utilities, a nonnegative rational threshold, and uniform selection from the winning set. These are the source-problem hypotheses needed by the reduction. The source’s positive integer utilities are permitted by the target’s nonnegative integer domain. [Definitions and Theorem 4.8](https://comsoc-community.org/assets/proceedings/comsoc-2012/Obraztsova.pdf).

The theorem is applicable as cited. Its proof is omitted in that proceedings paper, but the discrete result is expressly supplied as a premise of USER_TASK; the prover does not need to reprove it.

2. Membership in \(\mathrm{NP}\)

Each step is valid.

• Certificate. A permutation of the candidates specifies exactly one admissible strict ranking for the strategic type’s entire mass. Its encoding has polynomial length. For the single-candidate case, the certificate is trivial.

• Pairwise margins. The expression

\(\Delta_L(a,b)=\sum_i w_i\sigma_{R_i}(a,b)+\varepsilon\sigma_L(a,b)\)
is exactly the difference between the masses favoring the two candidates. Its sign correctly distinguishes victories, ties, and losses.

• Exact arithmetic. The product \(D\) of the input denominators is a common denominator, even when the fractions are unreduced. Its bit length is bounded by the sum of their denominator bit lengths, hence by \(O(B)\). The scaled margins are integers. Because the total mass is one, the scaled contributions have total absolute value at most \(D\), so their sums also fit within \(O(B)\) bits.

• Copeland scores. Comparing \(kv_c+ht_c\) is equivalent to comparing the Copeland scores because every candidate’s score has the same positive denominator \(k\). This includes \(\alpha=0\) and \(\alpha=1\).

• Expected utility. The winning set is nonempty because the candidate set is finite and nonempty. Multiplication by the positive quantities \(r\) and \(|W(L)|\) makes the threshold test exactly

\(r\sum_{c\in W(L)}u(c)\ge p|W(L)|\).
The required sums and products have polynomial bit length.

• Running time. The bound \(O((\tau+1)m^2B^2)\) is a valid conservative bound using ordinary quadratic-time integer arithmetic and precomputed ranking positions.

3. Validity and size of the reduction

The constructed masses satisfy all target conditions:

• \(\varepsilon=1/n\) is rational and lies in \((0,1]\).
• The nonmanipulator mass is \((n-1)/n=1-\varepsilon\).
• Grouping identical rankings produces precisely a support list with positive masses \(k_R/n\).
• Each mass has \(O(\log n)\)-bit numerator and denominator.
• Grouping, sorting candidates by utility, and writing the output all take polynomial time in the explicitly listed source input.

The choice of \(R^\star\) satisfies the required weak utility consistency, including equal utilities. Its particular ordering cannot affect the decision predicate, which evaluates the submitted ranking \(L\) against the retained utilities.

The case \(n=1\) is also valid: \(\varepsilon=1\) and the nonmanipulator support is empty. USER_TASK does not require that support to be nonempty.

4. Preservation of outcomes

The decisive equality is correct: for every strict ranking \(L\) and every distinct pair \(a,b\), the target margin equals the source margin divided by \(n\).

Since \(n>0\), this preserves positive, negative, and zero margins. Thus it preserves every pairwise result, every Copeland score, and the entire winning set. Retaining the utilities preserves the average utility of that set.

The preservation holds for every admissible \(L\), in both directions. Consequently, existence of a ranking meeting the threshold is equivalent in the source and target instances. This establishes a polynomial-time many-one reduction.

5. Optional dyadic construction

This additional construction is correct.

The least power of two \(N\ge n\) has \(O(\log n)\) bits. The padding masses are nonnegative dyadic rationals, and their total makes the nonmanipulator mass exactly \(1-1/N\).

For every distinct pair, a ranking and its reverse contribute opposite signs. Their equal padding masses therefore cancel exactly. The resulting margin is the original discrete margin divided by \(N\), so ties are preserved as well.

Zero padding is omitted, duplicate rankings can be merged, and the stated bound of at most \(n+1\) support entries is valid.

6. Final complexity claims

Hardness for each fixed rational \(\alpha\), together with the verified membership argument, establishes the claimed \(\mathrm{NP}\)-completeness. The version with input \(\alpha\) contains any fixed-\(\alpha\) hard subclass.

The exhaustive-search bound \(O((\tau+1+m!)m^2L_{\mathrm{bits}}^2)\) is valid after precomputing nonmanipulator margins. The claim that a polynomial deterministic algorithm exists exactly when \(\mathrm{P}=\mathrm{NP}\) follows.

No repair or additional clarification is required.

⟨structured verdict parsed — rendered above⟩