Aggregation over Metric Spaces: Proposing and Voting in Elections, Budgeting, and Legislation (d4-journals-jair-2021-0022)

Given \(m\) alternatives and an explicitly listed finite-support rational distribution \(\mu\) over complete rankings \(\pi\in S_m\), output an integral ranking \(\rho\in S_m\) minimizing \(F_\mu(\rho)=\sum_{\pi\in S_m}\mu_\pi d_{\mathrm{KT}}(\pi,\rho)\); equivalently, decide whether \(\min_{\rho\in S_m}F_\mu(\rho)\le B\).

Let \(m\geq 1\) alternatives be given, and let \(S_m\) denote their strict complete rankings. A society is given by its support: a list of \(\tau\geq 1\) distinct rankings \(\pi_i\in S_m\), each with positive binary rational mass \(\mu_i\), where \(\sum_{i=1}^{\tau}\mu_i=1\). Here \(\tau\) is the support size, not the number of possible rankings. Let \(L\) be the total input bit length, including a binary rational threshold \(B\geq 0\).
Use the standard, unnormalized Kendall–tau distance \(d_{\mathrm{KT}}\). The output ranking must belong to \(S_m\); any minimizer is acceptable. Define \(F_\mu(\rho)=\sum_{i=1}^{\tau}\mu_i d_{\mathrm{KT}}(\pi_i,\rho)\).

Is deciding whether \(\min_{\rho\in S_m}F_\mu(\rho)\leq B\) solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?

For finite electorates, minimizing total Kendall–tau distance is Kemeny aggregation and is NP-hard, even with four complete rankings ([Dwork et al., Rank Aggregation Revisited](https://cs.brown.edu/courses/csci2531/papers/rank2.pdf)). No separate result specifically formulated with binary rational probability masses was verified.

Result

The decision problem is \(\mathrm{NP}\)-complete, even when the support size satisfies \(\tau\leq 4\) and every mass is an integer multiple of \(\frac14\). Thus a polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).

Reduction from finite-electorate Kemeny aggregation

We use the following known result: given four strict complete rankings \(\sigma_1,\ldots,\sigma_4\) of the same alternatives and a nonnegative integer threshold \(K\), deciding whether there exists \(\rho\in S_m\) with
\(\sum_{j=1}^{4}d_{\mathrm{KT}}(\sigma_j,\rho)\leq K\)
is \(\mathrm{NP}\)-complete. This is the four-list case of Theorem 14 in Appendix A of [Dwork et al., *Rank Aggregation Revisited*](https://cs.brown.edu/courses/csci2531/papers/rank2.pdf). Their distance on complete rankings is the unnormalized Kendall–tau distance used here.

Take an instance of this problem. Let \(\pi_1,\ldots,\pi_\tau\) be the distinct rankings occurring among \(\sigma_1,\ldots,\sigma_4\), and define their multiplicities by
\[ n_i=\bigl|\{j\in\{1,2,3,4\}:\sigma_j=\pi_i\}\bigr|. \]
Set \(\mu_i=n_i/4\) and \(B=K/4\).

These data satisfy every requirement of the target problem:

• The support rankings are distinct, and \(1\leq\tau\leq4\).
• Every \(\mu_i\) is positive, and \(\sum_i\mu_i=\frac14\sum_i n_i=1\).
• The masses and threshold are binary-encodable rationals. Indeed, they are dyadic rationals, so the reduction also works if “binary rational” requires a terminating binary expansion.

For every admissible output ranking \(\rho\in S_m\), grouping equal input rankings gives
\[ F_\mu(\rho) =\sum_{i=1}^{\tau}\frac{n_i}{4}d_{\mathrm{KT}}(\pi_i,\rho) =\frac14\sum_{j=1}^{4}d_{\mathrm{KT}}(\sigma_j,\rho). \]
Consequently,
\[ \min_{\rho\in S_m}F_\mu(\rho)\leq B \quad\Longleftrightarrow\quad \min_{\rho\in S_m}\sum_{j=1}^{4}d_{\mathrm{KT}}(\sigma_j,\rho)\leq K. \]

The construction takes polynomial time: comparing and grouping four rankings is polynomial in their explicit encoding length, each mass has constant encoding length, and encoding \(K/4\) adds only a constant number of bits to the encoding of \(K\). This is therefore a polynomial-time many-one reduction, proving \(\mathrm{NP}\)-hardness.

Membership in \(\mathrm{NP}\)

A certificate is a ranking \(\rho\), encoded as a permutation of the alternatives using \(O(m\log(m+1))\) bits. A verifier first checks that every alternative occurs exactly once.

For each support ranking, compute
\(D_i=d_{\mathrm{KT}}(\pi_i,\rho)\)
by counting unordered pairs whose relative orders disagree. This takes \(O(\tau m^2)\) pair checks, and \(0\leq D_i\leq\binom m2\).

Write the input rationals as \(\mu_i=a_i/b_i\) and \(B=c/d\), where the denominators are positive integers. Define
\[ Q=d\prod_{i=1}^{\tau}b_i. \]
Since \(Q\) is positive and divisible by every denominator, the required comparison is exactly the integer comparison
\[ \sum_{i=1}^{\tau}a_iD_i\frac{Q}{b_i} \leq c\frac{Q}{d}. \]

The bit length of \(Q\) is bounded by the sum of the input denominator bit lengths, hence is \(O(L)\). The products and sums in this comparison have bit lengths polynomial in \(L,\log(m+1),\log(\tau+1)\). Standard exact integer arithmetic therefore performs the verification in polynomial time.

Thus the problem belongs to \(\mathrm{NP}\), completing the proof of \(\mathrm{NP}\)-completeness. No separate hardness theorem for rational probability masses is needed: normalization and merging duplicate rankings preserve the objective exactly up to the factor \(\frac14\).

⟨structured verdict parsed — rendered above⟩

The output fully resolves the assigned question. The reduction is valid, the cited theorem applies, and the exact-arithmetic verifier establishes membership in \(\mathrm{NP}\). No mathematical issues or additional clarifications are needed.

• The cited hardness result is correctly stated and applicable.

Theorem 14 in Appendix A explicitly establishes hardness for an even number of complete lists, including four, and states that the corresponding decision problem is \(\mathrm{NP}\)-complete. The paper defines the objective as the sum of pairwise disagreement counts over permutations, matching the task’s unnormalized Kendall–tau distance. Thus the prover uses the correct decision theorem, input domain, and distance convention. [Dwork et al., *Rank Aggregation Revisited*, definition on page 2 and Theorem 14 on page 13](https://cs.brown.edu/courses/csci2531/papers/rank2.pdf).

• The constructed instance satisfies the target’s support requirements.

Grouping equal rankings among four inputs produces distinct support rankings with \(1\leq\tau\leq4\). Each multiplicity \(n_i\) is a positive integer, and \(\sum_i n_i=4\). Consequently, \(\mu_i=n_i/4>0\) and \(\sum_i\mu_i=1\).

This correctly distinguishes support size from electorate size. Duplicate source rankings cause no difficulty.

• The threshold and masses have valid encodings.

Every constructed mass is an integer multiple of \(1/4\), and \(B=K/4\geq0\). These values admit binary rational encodings, including terminating binary expansions. The construction therefore does not depend on an ambiguous interpretation of “binary rational.”

• The objective identity and decision equivalence are exact.

For every \(\rho\in S_m\), grouping equal source rankings gives precisely the stated identity
\[ F_\mu(\rho)=\frac14\sum_{j=1}^{4}d_{\mathrm{KT}}(\sigma_j,\rho). \]

Both minimizations range over the same set \(S_m\). Scaling the objective and threshold by the same positive factor preserves the decision answer in both directions. No claim about uniqueness or a particular minimizer is needed.

• The reduction has polynomial running time and output length.

Comparing and grouping four explicitly encoded rankings is polynomial time. The masses have constant encoding length. Representing \(K/4\) requires only constant additional overhead relative to the binary encoding of \(K\). Thus the stated construction is a polynomial-time many-one reduction and establishes the claimed restricted \(\mathrm{NP}\)-hardness.

• The certificate and distance verification are valid.

A permutation has the stated polynomial certificate length, and checking that each alternative appears exactly once enforces the required output domain.

Counting unordered pairs with disagreeing relative orders computes the unnormalized Kendall–tau distance. The bound \(0\leq D_i\leq\binom m2\) is correct. The stated number of pair checks is polynomial; constructing position tables for the rankings is routine.

• The rational comparison has polynomial bit complexity.

The integer \(Q=d\prod_i b_i\) is positive and divisible by every denominator. Multiplication by \(Q\) therefore preserves the inequality and makes every displayed quotient integral.

Its bit length is bounded by the total denominator encoding length. The remaining products and sums also have polynomial bit length, so exact integer arithmetic verifies the comparison in polynomial time. The argument does not confuse numerical magnitude with encoding length.

• The conclusion and boundary cases are consistent.

Combining hardness with membership proves \(\mathrm{NP}\)-completeness. The cases \(m=1\), zero threshold, and repeated source rankings do not invalidate any step. Easy individual instances do not conflict with worst-case hardness.

The prover’s conclusion that a polynomial-time algorithm would imply \(\mathrm{P}=\mathrm{NP}\) is appropriately conditional.

⟨structured verdict parsed — rendered above⟩