Preferences Single-Peaked on a Circle (d4-conf-aaai-2017-0442)

Given finite alternatives \(A\), a common circle \(\mathcal C\), a finite support \(T\) of complete rankings single-peaked on \(\mathcal C\), rational masses \(\mu_t\ge0\) with \(\sum_{t\in T}\mu_t=1\), and rational \(q\), decide whether there exists a ranking \(r\) such that \(\sum_{t\in T}\mu_t\lvert\{(x,y)\in A^2:x\succ_t y\ \land\ x\succ_r y\}\rvert\ge q\).

A circular interval of a circle Π on \(A\) is a contiguous arc of Π. A ranking \(t\) is single-peaked on Π if every strict top-initial segment of \(t\) is a circular interval.

Given \(A\), a circle Π, a finite set \(T\) of rankings single-peaked on Π, rational masses \(\mu_t\geq0\) with \(\sum_{t\in T}\mu_t=1\), and rational \(q\), decide whether a ranking \(r\) satisfies \(\sum_{t\in T}\mu_t|\{(x,y)\in A^2:x\succ_t y\land x\succ_r y\}|\geq q\).

Target. Is this continuous Kemeny decision problem solvable in polynomial time, or is it NP-hard?

For finite voter profiles of rankings single-peaked on a common circle, the corresponding Kemeny decision problem is NP-complete. No continuous-side result is stated here.

Under the intended existential interpretation—whether there exists a ranking \(r\) meeting the threshold—the problem is \(\mathrm{NP}\)-complete. This follows from the finite-profile hardness stated in the question.

Reduction from finite profiles. Let a finite-profile instance consist of a candidate set \(A\), its supplied circle \(\Pi\), rankings \(t_1,\ldots,t_N\) single-peaked on \(\Pi\), and an agreement threshold \(K\), with \(N\geq 1\). Define
\[ a(t,r)=\left|\{(x,y)\in A^2:x\succ_t y\text{ and }x\succ_r y\}\right|. \]
The finite-profile question is whether some ranking \(r\) satisfies
\[ \sum_{i=1}^{N}a(t_i,r)\geq K. \]

Let \(T\) be the set of distinct rankings occurring in the profile. For each \(t\in T\), let \(m_t\) be its multiplicity, and set
\[ \mu_t=\frac{m_t}{N}, \qquad q=\frac{K}{N}. \]
Retain \(A\) and \(\Pi\). Every member of \(T\) is single-peaked on \(\Pi\), and the masses are nonnegative rationals satisfying
\[ \sum_{t\in T}\mu_t=\frac{\sum_{t\in T}m_t}{N}=1. \]
For every ranking \(r\),
\[ \sum_{t\in T}\mu_t a(t,r) =\frac{1}{N}\sum_{i=1}^{N}a(t_i,r). \]
Because \(N>0\), the constructed instance meets its threshold exactly when the original instance meets its threshold.

The construction takes polynomial time for an explicitly listed finite profile: duplicate rankings can be grouped by comparison, and each multiplicity and denominator requires only \(O(\log(N+1))\) bits. The rational threshold also has polynomial encoding length. Thus the stated finite-profile hardness implies \(\mathrm{NP}\)-hardness of the rational-mass problem.

If the finite-profile problem is instead expressed using a total Kendall disagreement bound \(D\), the same reduction applies with \(K=N\binom{|A|}{2}-D\). Indeed, for each voter and each unordered candidate pair, the two strict rankings either agree or disagree, so their agreement and disagreement counts sum to \(\binom{|A|}{2}\).

Membership in \(\mathrm{NP}\). A certificate is a permutation \(r\) of \(A\). Verify that it is a permutation, then compute each integer \(a(t,r)\) by checking all unordered candidate pairs. This requires \(O(|T||A|^2)\) comparisons.

The weighted sum can be compared with \(q\) using exact integer arithmetic. Explicitly, write \(\mu_t=u_t/v_t\) and \(q=b/c\), with positive denominators, and take
\[ L=c\prod_{t\in T}v_t. \]
The required comparison is equivalent to
\[ \sum_{t\in T}u_t\frac{L}{v_t}a(t,r)\geq b\frac{L}{c}. \]
The bit length of \(L\) is at most the sum of the input denominators’ bit lengths, up to a constant. All integers in this comparison therefore have polynomial bit length, and verification takes polynomial time. This proves membership in \(\mathrm{NP}\), completing the proof.

Wording distinction. If \(r\) is itself supplied as part of the input and the task is merely to check its score, the verification procedure above is a polynomial-time algorithm. The \(\mathrm{NP}\)-completeness result concerns finding whether a qualifying ranking exists.

⟨structured verdict parsed — rendered above⟩

The prover’s argument is correct for the existential decision problem. It also correctly handles the alternative reading in which the ranking \(r\) is supplied. No major or minor mathematical issues were found.

• Interpretation of the target. The task’s phrase “whether a ranking \(r\) satisfies” leaves the quantification of \(r\) implicit. The prover explicitly distinguishes existence of a qualifying ranking from evaluation of a supplied ranking. Its conclusions address both readings without conflating them.

• Use of the supplied hardness result. The prover invokes precisely the finite-profile hardness provided in the task: rankings single-peaked on a supplied common circle. No additional structural hardness theorem is required. Restricting to nonempty profiles is harmless, since empty profiles have a constant score and are decidable immediately.

• Validity of the constructed instance. Grouping identical rankings into the set \(T\) preserves their rankings and the supplied circle. Multiplicities satisfy \(\sum_{t\in T}m_t=N\), so the assigned masses \(\mu_t=m_t/N\) are nonnegative and sum to one. Every supported ranking remains single-peaked on \(\Pi\).

• Equivalence of the decision instances. The identity

\[ \sum_{t\in T}\mu_t a(t,r)=\frac{1}{N}\sum_{i=1}^{N}a(t_i,r) \]
holds for every ranking \(r\), because grouping preserves each ranking’s multiplicity. Since \(N>0\), comparison with \(q=K/N\) preserves the threshold inequality in both directions. Consequently, existence of a qualifying ranking is preserved.

• Polynomial size and construction time. For an explicitly listed profile, grouping duplicate permutations is polynomial-time. Each multiplicity and the denominator \(N\) has logarithmic bit length in \(N+1\). The representation of \(K/N\) has polynomial length in the source input. The reduction therefore meets the required computational bound.

• Agreement versus disagreement. For strict rankings, each unordered pair contributes exactly once to either agreement or disagreement. The identity underlying \(K=N\binom{|A|}{2}-D\) is correct. The ordered-pair notation in the task does not introduce a factor of two: only one orientation of an unordered pair can satisfy \(x\succ_t y\).

• Certificate verification. A permutation of \(A\) is a polynomial-size certificate. Checking all unordered pairs computes each agreement count correctly. Rank positions can be obtained directly from the input permutations, so the asserted polynomial comparison bound is justified. The candidate ranking \(r\) need not itself be single-peaked, and the verifier correctly imposes no such restriction.

• Exact arithmetic. The proposed integer \(L=c\prod_{t\in T}v_t\) is positive and divisible by every denominator. Multiplication by \(L\) therefore preserves the inequality and yields the stated integer comparison. Its bit length is bounded by the combined denominator bit lengths. Including the input numerators, agreement counts, and summation still gives polynomial-size integers. Thus verification is polynomial-time in the full binary input length, including for negative or out-of-range thresholds.

• Conclusion and repair feedback. The reduction establishes NP-hardness, and the certificate argument establishes membership in NP. The existential problem is therefore NP-complete under the explicit rational-mass representation in the task. Evaluating a supplied ranking is polynomial-time. No repair or additional clarification is needed beyond the interpretation distinction already present in the output.

⟨structured verdict parsed — rendered above⟩