High-Multiplicity Election Problems (d4-conf-atal-2018-0249)

Given candidates \(C\), a target candidate \(p\), four complete ranking types \(t_1,\ldots,t_4\), and rational masses \(\mu_1,\ldots,\mu_4\) summing to \(1\), does some consensus order \(\pi\) minimizing \(\sum_i \mu_i d_{\mathrm{KT}}(\pi,t_i)\) rank \(p\) first?

Given a finite candidate set \(C\), let \(m=|C|\) and \(p\in C\). A society is given by its support: \(\tau=4\) distinct strict total orders \(t_1,\ldots,t_4\) on \(C\), each with a positive binary rational mass \(\mu_i\), where \(\sum_{i=1}^4\mu_i=1\). Here \(\tau\) is the support size, not the number \(m!\) of possible types; let \(L\) be the total input bit length.
A consensus is a strict total order \(\pi\) minimizing \(\sum_{i=1}^4\mu_i d_{\mathrm{KT}}(\pi,t_i)\), using Kendall tau distance. Accept precisely when some minimizing order ranks \(p\) first; no tie-breaking selects among minimizing orders.

Is this decision problem in \(\mathrm{P}\), with running time polynomial in \(m,\tau,L\), or is it \(\mathrm{NP}\)-hard?

For four votes with positive binary integer weights or multiplicities, Kemeny winner determination is \(\Theta_2^p\)-complete; with four unweighted voters it is also \(\Theta_2^p\)-complete. [Source](https://mathcs.holycross.edu/~zfitzsim/papers/Fitzsimmons-Hemaspaandra2019_Article_High-multiplicityElectionProbl.pdf).

Result

The problem is \(\Theta_2^p\)-complete, hence \(\mathrm{NP}\)-hard. Hardness holds even when all four masses equal \(\frac14\) and the four support orders are distinct. Consequently, a running time polynomial in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).

1. Known hardness theorem

We use the following supplied result: determining whether a candidate ranks first in some Kemeny-optimal order for an election with four unweighted voters is \(\Theta_2^p\)-complete. This is Theorem 19 of [Fitzsimmons–Hemaspaandra, *High-multiplicity election problems*](https://mathcs.holycross.edu/~zfitzsim/papers/Fitzsimmons-Hemaspaandra2019_Article_High-multiplicityElectionProbl.pdf).

The four voters’ orders might repeat. Thus, applying this theorem to the present problem requires ensuring four distinct support orders.

2. Reduction to four distinct orders

Let a source instance have candidate set \(C\), distinguished candidate \(p\), and four orders \(v_1,\ldots,v_4\), possibly repeated. Its objective is

\(F(\sigma)=\sum_{i=1}^4 d_{\mathrm{KT}}(\sigma,v_i)\).

Introduce three fresh candidates \(D=\{a,b,c\}\), disjoint from \(C\). Choose four distinct orders on \(D\):

\(s_1=(a,b,c),\quad s_2=(a,c,b),\quad s_3=(b,a,c),\quad s_4=(b,c,a)\).

For each \(i\), construct \(t_i\) by listing \(C\) in order \(v_i\), followed by \(D\) in order \(s_i\). Set \(\mu_i=\frac14\).

These are four distinct strict total orders: their restrictions to \(D\) are distinct. Their masses are positive binary rationals summing to \(1\). The construction adds only three candidates and has polynomial output length.

3. Exact preservation of optimality and winners

Kendall tau distance counts unordered candidate pairs whose relative orders disagree.

For an order \(\pi\) on \(C\cup D\), let \(\pi_C\) and \(\pi_D\) denote its restrictions to \(C\) and \(D\). Define

\(G(\rho)=\frac14\sum_{i=1}^4 d_{\mathrm{KT}}(\rho,s_i)\),

and let \(I(\pi)\) be the number of pairs \((x,d)\in C\times D\) for which \(\pi\) ranks \(d\) above \(x\).

Every \(t_i\) ranks every original candidate above every fresh candidate. Partitioning candidate pairs into pairs within \(C\), within \(D\), and between the two sets therefore gives the exact identity

\(F'(\pi):=\frac14\sum_{i=1}^4 d_{\mathrm{KT}}(\pi,t_i)=\frac14F(\pi_C)+G(\pi_D)+I(\pi)\).

Let

\(K=\min_{\sigma\text{ on }C}F(\sigma),\qquad H=\min_{\rho\text{ on }D}G(\rho)\).

Both minima exist because the sets of orders are finite. Since \(I(\pi)\geq 0\), every order satisfies

\(F'(\pi)\geq \frac14K+H\).

Equality is attainable: concatenate an order attaining \(K\) with an order attaining \(H\). This concatenation has \(I(\pi)=0\). Consequently,

\(\min_{\pi\text{ on }C\cup D}F'(\pi)=\frac14K+H\).

Moreover, if \(\pi\) minimizes \(F'\), then

\(0=\frac14\bigl(F(\pi_C)-K\bigr)+\bigl(G(\pi_D)-H\bigr)+I(\pi)\).

All three summands are nonnegative, so each equals zero. In particular, \(\pi_C\) minimizes the original objective.

We now obtain both directions of winner preservation:

• If some original minimizing order ranks \(p\) first, concatenate it with a minimizing order on \(D\). The resulting order minimizes \(F'\) and ranks \(p\) first.
• If some minimizing order for the constructed instance ranks \(p\) first, its restriction to \(C\) is an original minimizing order and still ranks \(p\) first.

Thus the reduction preserves acceptance exactly, including the existential treatment of tied optimal orders. The known theorem proves \(\Theta_2^p\)-hardness.

4. Membership in \(\Theta_2^p\)

This upper bound also accommodates arbitrary binary rational masses.

Write \(\mu_i=a_i/b_i\), with positive binary integers \(a_i,b_i\). Set

\(Q=\prod_{i=1}^4b_i,\qquad w_i=a_i\prod_{j\neq i}b_j\).

Then \(Q\mu_i=w_i\), so multiplying the objective by \(Q>0\) preserves every minimizing order. These integers have bit length polynomial in \(L\).

Let \(N=\binom m2\). Every order’s integer objective belongs to the explicitly enumerable set

\(S=\left\{\sum_{i=1}^4w_i k_i:\ (k_1,k_2,k_3,k_4)\in\{0,\ldots,N\}^4\right\}\).

This set has at most \((N+1)^4\) elements, each of polynomial bit length.

For every \(s\in S\), ask in one parallel round two \(\mathrm{NP}\) queries: whether an order has objective at most \(s\), and whether such an order exists with \(p\) first. A certificate is the order itself; its score and first candidate can be checked in polynomial time.

The smallest accepted threshold in each family is its corresponding optimum, because both optima belong to \(S\). Acceptance is exactly equality of these two optima. Hence the problem lies in \(\mathrm{P}^{\mathrm{NP}}_{\parallel}=\Theta_2^p\).

Together with the reduction, this proves \(\Theta_2^p\)-completeness.

⟨structured verdict parsed — rendered above⟩

The prover resolves the task correctly. The reduction handles the requirement of exactly four distinct support orders, and the upper bound applies to arbitrary positive binary rational masses. No major or minor mathematical issues were found.

• The cited hardness theorem applies.

Theorem 19 states that Kemeny winner determination for four unweighted voters is \(\Theta_2^p\)-complete. The paper defines a winner as a candidate ranked first in some minimizing consensus, matching the task’s existential treatment of tied optimal orders. Thus the prover states the relevant theorem correctly. [Fitzsimmons–Hemaspaandra, definition in Section 6 and Theorem 19](https://mathcs.holycross.edu/~zfitzsim/papers/Fitzsimmons-Hemaspaandra2019_Article_High-multiplicityElectionProbl.pdf).

The theorem does not itself require four distinct orders. The prover explicitly recognizes and addresses this hypothesis mismatch.

• The constructed instance satisfies every input restriction.

The three fresh candidates are disjoint from the original candidate set. Each constructed vote is a strict total order formed by concatenating two strict total orders.

The four listed orders on the fresh candidates are pairwise distinct. Consequently, the four constructed votes remain distinct even if original votes repeat.

Each mass is \(\frac14\), a positive binary rational, and the masses sum to \(1\). Adding three candidates and writing four extended orders requires polynomial output length and construction time.

• The objective decomposition is exact.

Pairs within the original candidate set contribute \(\frac14F(\pi_C)\). Pairs within the fresh candidate set contribute \(G(\pi_D)\).

For a cross pair, every constructed vote ranks the original candidate above the fresh candidate. Reversing this pair in the consensus therefore incurs disagreement in all four votes, with total mass \(1\). Hence its contribution is exactly the corresponding unit counted by \(I(\pi)\).

The identity
\[ F'(\pi)=\frac14F(\pi_C)+G(\pi_D)+I(\pi) \]
is correct for every order, including orders that interleave the two candidate sets.

• The optimality argument is valid.

Both minima exist over finite, nonempty sets of orders. Each restricted objective is bounded below by its respective minimum, and \(I(\pi)\) is nonnegative.

Concatenating minimizing restrictions attains the asserted lower bound because it creates no reversed cross pairs. Thus the stated optimum value is exact.

For any minimizing constructed order, the displayed sum of three nonnegative terms equals zero. Each term must therefore vanish. In particular, its restriction to the original candidates minimizes the original objective. There is no cancellation or unstated assumption in this inference.

• Winner preservation holds in both directions.

An original minimizing order with \(p\) first extends by concatenation to a constructed minimizing order with \(p\) first.

Conversely, restricting a constructed minimizing order with \(p\) first preserves both original optimality and the first position of \(p\).

These statements preserve the existence of a suitable minimizing order; they introduce no tie-breaking requirement. Together with the polynomial construction, they establish the claimed hardness.

• Clearing rational denominators is valid and efficient.

The formulas for \(Q\) and \(w_i\) give \(Q\mu_i=w_i\) exactly. Since \(Q>0\), scaling preserves all minimizing orders.

The products involve only four input denominators. Their bit lengths, and those of the resulting weights, are polynomial in \(L\). No expansion into individual voters is required.

• The parallel-query upper bound is correct.

Each Kendall tau distance is an integer between \(0\) and \(N=\binom m2\). Therefore every attainable integer objective belongs to \(S\).

The set need not contain only attainable scores: the argument requires only that it contain both optima. Its cardinality is at most \((N+1)^4\), polynomial because the support size is fixed at four. Its entries have polynomial bit length and can be enumerated in polynomial time.

Both threshold predicates are in \(\mathrm{NP}\): a certificate is a permutation of the candidates, whose validity, score, and first candidate can be checked in polynomial time. All thresholds are constructed before querying the oracle, so the queries are genuinely parallel.

Each query family has an accepted threshold because its optimum belongs to \(S\). Its smallest accepted threshold is exactly that optimum. Equality of the unrestricted optimum and the optimum restricted to orders with \(p\) first is precisely the required acceptance condition.

The invoked characterization \(\mathrm{P}^{\mathrm{NP}}_{\parallel}=\Theta_2^p\) is standard and is also stated in the cited paper’s complexity preliminaries. [Section 2.2](https://mathcs.holycross.edu/~zfitzsim/papers/Fitzsimmons-Hemaspaandra2019_Article_High-multiplicityElectionProbl.pdf).

• The conclusion has the correct scope.

The proof establishes \(\Theta_2^p\)-completeness for the specified problem with \(\tau=4\), including hardness at equal masses. It does not claim that the enumeration bound is polynomial for variable support size.

Since \(\Theta_2^p\)-hardness implies \(\mathrm{NP}\)-hardness, the stated consequence for a polynomial-time algorithm is valid. No additional clarification or repair is needed.

⟨structured verdict parsed — rendered above⟩