d4-conf-aaai-2006-0154 (d4-conf-aaai-2006-0154)

Given a candidate set \(C\) and a finite support of strict rankings \(t\), each with positive binary-rational mass \(\mu_t\) summing to \(1\), and with no pair tied in the population, compute a ranking \(\succ\) minimizing the number of unordered candidate pairs that \(\succ\) orders opposite to their population pairwise-majority direction.

Let \(C\) be a finite nonempty candidate set, with \(m=|C|\). A society is given by its support: a list of \(\tau\) distinct strict rankings \(t\) of \(C\), each with positive binary-rational mass \(\mu_t\), where \(\sum_t\mu_t=1\). Here \(\tau\) is the support size, not the number \(m!\) of possible rankings; let \(L\) be the total input bit length.
For distinct candidates, define \(a\to b\) when \(\sum_{t:a\succ_t b}\mu_t>1/2\). Promise that no pair has mass exactly \(1/2\) in either direction.
For a strict ranking \(\succ\) of \(C\), its disagreement count is \(D(\succ)=|\{(a,b)\in C^2:a\succ b\text{ and }b\to a\}|\); each unordered pair contributes at most one. Compute a ranking minimizing \(D\), allowing any minimizer when several exist.

Is computing an optimal ranking for this society possible in time polynomial in \(m,\tau,L\), or is it NP-hard?

For finite lists of voters with strict rankings, computing a Slater ranking is NP-hard even without pairwise ties.

Conclusion

Computing an optimal ranking is \(\text{NP-hard}\). This holds even when every mass is a dyadic rational, meaning a rational with denominator a power of two. Consequently, a polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).

Starting hardness result

We use the supplied premise: computing a Slater ranking from an explicitly listed finite electorate of strict rankings is \(\text{NP-hard}\), even without pairwise ties. This is also established in [Conitzer’s paper](https://cdn.aaai.org/AAAI/2006/AAAI06-098.pdf).

Let such an instance have candidates \(C\) and voters with rankings \(v_1,\ldots,v_N\), where \(N\geq 1\). For distinct candidates \(a,b\), put
\[ p_{ab}=\frac{|\{i:a\succ_{v_i}b\}|}{N}. \]
The absence of ties implies
\[ \left|p_{ab}-\frac12\right| =\frac{\left|2|\{i:a\succ_{v_i}b\}|-N\right|}{2N} \geq\frac{1}{2N}, \]
because the numerator is a nonzero integer.

We construct a support-list society with exactly the same pairwise majority relation.

Construction with dyadic masses

Choose the smallest power of two \(Q\) satisfying \(Q>2N^2\). Then \(Q\leq 4N^2\). Write
\[ Q=Nq+r,\qquad 0\leq r<N. \]
Assign voter \(i\) the temporary mass
\[ w_i= \begin{cases} (q+1)/Q,&1\leq i\leq r,\\ q/Q,&r<i\leq N. \end{cases} \]
Since \(Q>N\), we have \(q\geq1\), so every mass is positive. Moreover,
\[ \sum_{i=1}^Nw_i =\frac{r(q+1)+(N-r)q}{Q}=1. \]
Each mass approximates the original uniform mass:
\[ \left|w_i-\frac1N\right|\leq\frac1Q. \]
Indeed, for the two possible values of \(w_i\), the differences are respectively \((N-r)/(NQ)\) and \(r/(NQ)\).

Now merge identical rankings. For each distinct ranking \(t\) appearing among the voters, define
\[ \mu_t=\sum_{\{i:v_i=t\}}w_i. \]
These masses are positive dyadic rationals and sum to one. The resulting support has \(\tau\leq N\) distinct rankings.

Preservation of every majority edge

For distinct candidates \(a,b\), the constructed society’s mass preferring \(a\) to \(b\) is
\[ p'_{ab} =\sum_{\{t:a\succ_tb\}}\mu_t =\sum_{\{i:a\succ_{v_i}b\}}w_i. \]
Consequently,
\[ |p'_{ab}-p_{ab}| \leq\sum_{\{i:a\succ_{v_i}b\}}\left|w_i-\frac1N\right| \leq\frac NQ <\frac1{2N}. \]
The original probability \(p_{ab}\) lies at distance at least \(1/(2N)\) from \(1/2\). Thus this perturbation cannot reach or cross \(1/2\). It follows that
\[ p'_{ab}>\frac12 \quad\Longleftrightarrow\quad p_{ab}>\frac12. \]
The constructed society therefore satisfies the no-ties promise and has exactly the original majority tournament.

For every output ranking \(\succ\), its disagreement count consequently equals its Slater disagreement count in the original electorate. Hence every minimizer for the constructed society is a Slater ranking for the original instance.

Polynomial size and hardness transfer

The electorate is explicitly listed, so \(N\) is bounded by its input length. Grouping identical rankings and calculating their masses take polynomial time.

Every merged mass has the form \(A_t/Q\), with \(1\leq A_t\leq Q\). Since \(Q\leq4N^2\), its numerator and denominator require \(O(\log(N+1))\) bits. There are at most \(N\) support entries, each containing one original ranking. Thus the constructed input length \(L\), candidate count \(m\), and support size \(\tau\) are all polynomially bounded in the original input length.

A hypothetical algorithm polynomial in \(m,\tau,L\), applied to this construction, would therefore compute a Slater ranking in polynomial time for every instance of the supplied hard problem. This proves the claimed \(\text{NP-hardness}\).

⟨structured verdict parsed — rendered above⟩

Verification report

The prover resolves the assigned problem correctly. The reduction produces a valid support-list society of polynomial size, preserves every pairwise majority direction, and therefore preserves the entire disagreement objective. No major or minor mathematical issues were found.

1. Starting hardness premise

The prover uses precisely the hardness premise supplied in USER_TASK: computing a Slater ranking from an explicitly listed finite electorate of strict rankings is NP-hard even without pairwise ties.

The required hypotheses are stated: the source instance consists of strict rankings \(v_1,\ldots,v_N\), with \(N\geq1\), and has no pairwise ties. Repeated rankings are permitted in this source representation.

The linked [Conitzer paper](https://cdn.aaai.org/AAAI/2006/AAAI06-098.pdf) also states NP-hardness of computing an optimal Slater ranking without pairwise ties and defines the Slater objective consistently with the task. The proof may rely directly on the supplied premise; no additional external theorem is needed.

Assessment: Valid starting premise and application.

2. Original majority margin

For any distinct candidates \(a,b\), let \(k=|\{i:a\succ_{v_i}b\}|\). The prover’s computation
\[ \left|p_{ab}-\frac12\right|=\frac{|2k-N|}{2N} \]
is correct.

The no-ties hypothesis gives \(2k-N\neq0\). Since this is an integer, its absolute value is at least \(1\), establishing the claimed lower bound \(1/(2N)\). This applies uniformly to every distinct pair.

Assessment: Correct computation, with all hypotheses satisfied.

3. Choice of denominator and temporary masses

The smallest power of two \(Q>2N^2\) exists. Its predecessor \(Q/2\) is at most \(2N^2\), so \(Q\leq4N^2\), including when \(2N^2\) itself is a power of two.

Euclidean division gives \(Q=Nq+r\), with \(0\leq r<N\). Since \(N\geq1\) and \(Q>2N^2\), the stated implication \(Q>N\) holds, and \(q\geq1\). Thus every assigned temporary mass is positive.

The normalization calculation is exact:
\[ r(q+1)+(N-r)q=Nq+r=Q. \]

The two approximation errors are also correct:
\[ \frac{q+1}{Q}-\frac1N=\frac{N-r}{NQ}, \qquad \frac1N-\frac qQ=\frac r{NQ}. \]
Both are at most \(1/Q\). When \(r=0\), the first branch is unused and all temporary masses equal \(1/N\); this causes no exception to the argument.

Assessment: All constants, inequalities, and boundary cases are correct.

4. Merging identical rankings

The construction defines one support entry for each ranking actually occurring in the electorate. Consequently, the support rankings are distinct and \(\tau\leq N\).

Each merged mass is a sum of positive temporary masses, so it is positive. Merging preserves the total mass \(1\). Since every temporary mass has denominator \(Q\), each merged mass has the form \(A_t/Q\) with an integer numerator. As \(Q\) is a power of two, these are dyadic rationals and satisfy the binary-rational input requirement.

Assessment: The constructed society satisfies the support and mass requirements.

5. Preservation of majority directions and the promise

The equality
\[ p'_{ab}=\sum_{\{i:a\succ_{v_i}b\}}w_i \]
follows directly from grouping voters by identical rankings.

The triangle inequality and the individual error bounds give
\[ |p'_{ab}-p_{ab}|\leq\frac NQ<\frac1{2N}. \]
The strict inequality follows from \(Q>2N^2\).

This perturbation is strictly smaller than the original distance from \(1/2\). Hence a probability originally above \(1/2\) remains above it, and one originally below remains below it. Equality with \(1/2\) is also excluded.

Thus the construction preserves every majority edge and satisfies the target’s no-ties promise.

Assessment: Correct; no pair or direction is omitted.

6. Preservation of the optimization objective

The target disagreement count and the source Slater disagreement count use the same ranking and the same majority relation. Since that relation is preserved, their values coincide for every strict ranking of \(C\).

Therefore their sets of minimizers coincide. The prover explicitly establishes preservation for every minimizer, which addresses the task’s allowance that an algorithm may return any optimal ranking.

Assessment: Exact objective preservation; the hardness transfer does not depend on tie-breaking among optimal rankings.

7. Polynomial construction and encoding size

The source electorate is explicitly listed, so \(N\) is bounded by its input length. Grouping identical rankings, computing \(Q,q,r\), and accumulating integer numerators are polynomial-time operations.

Every merged numerator satisfies \(1\leq A_t\leq Q\). Because \(Q\leq4N^2\), both numerator and denominator have \(O(\log(N+1))\) bits. This also bounds a terminating binary representation of each dyadic mass.

There are at most \(N\) support entries, and their rankings are taken from the source input. Hence the output length \(L\), candidate count \(m\), and support size \(\tau\) are polynomially bounded in the source input length.

A polynomial-time target algorithm would consequently solve the supplied NP-hard source problem in polynomial time.

Assessment: Valid polynomial-time reduction and hardness conclusion.

8. Edge cases and final adjudication

For \(N=1\), the construction chooses \(Q=4\), produces total mass \(1\), and satisfies every stated bound. For \(m=1\), all pairwise statements are vacuous and the objective is zero; the construction remains valid. Such trivial instances do not affect hardness over the full input family.

The claimed NP-hardness is fully established, including the stronger restriction to dyadic masses. No repair or additional clarification is required.

⟨structured verdict parsed — rendered above⟩