d4-conf-aaai-2018-1085 (d4-conf-aaai-2018-1085)

Given a finite candidate set \(C\), a distribution \(\mu\) over complete rankings of \(C\) with \(\tau\) positive-mass types, and fixed \(k\ge3\), decide whether \(C\) can be partitioned into \(k\) sets such that, after restricting the rankings to each set and aggregating identical projections, the positive-mass rankings can be ordered so that each preference direction for every candidate pair occupies an interval.

Let \(C\) contain \(m\) candidates, and fix an integer \(k\ge 3\), with \(m\ge k\). Rankings are strict total orders.
A society is given by its support: a list of \(\tau\) distinct rankings with positive binary-rational masses summing to \(1\). Here \(\tau\) is the support size, not the number of possible rankings; let \(L\) be the total input bit length.
For \(S\subseteq C\), restrict every ranking to \(S\), aggregate identical restrictions by summing their masses, and retain the resulting positive-mass rankings.
Call this restricted society single-crossing if its rankings admit a linear order such that, for every distinct \(a,b\in S\), both the rankings preferring \(a\) to \(b\) and those preferring \(b\) to \(a\) form intervals; empty intervals are allowed.
The decision problem asks whether \(C\) can be partitioned into exactly \(k\) nonempty sets whose restricted societies are single-crossing. Each set may use its own ordering of rankings.

For every fixed \(k\ge 3\), is this decision problem solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?

For finite voter profiles, candidate partition into \(k\) single-crossing sets is NP-complete for every fixed \(k\ge 3\) (Jaeckle, Peters, and Elkind, 2018). Recognition of a single-crossing finite profile is polynomial-time.

Result

For every fixed \(k\ge 3\), the decision problem is \(\mathrm{NP}\)-complete. The essential point is that deleting duplicate rankings preserves single-crossingness, including duplicates created by restricting candidates.

1. Duplicate rankings do not affect single-crossingness

For a finite profile \(P\), let \(D(P)\) contain exactly one copy of each distinct ranking occurring in \(P\).

Lemma. The profile \(P\) is single-crossing if and only if \(D(P)\) is single-crossing.

Proof. For any candidate pair, record its comparison along an ordering of the voters as a binary sequence. Both comparison classes are intervals exactly when this sequence changes value at most once: two or more changes would give three positions with values \(x,1-x,x\), violating the interval condition for value \(x\).

Suppose \(P\) has a single-crossing ordering. Keep one occurrence of each distinct ranking and delete the others. Each pair’s comparison sequence becomes a subsequence, so it still changes value at most once. The induced ordering therefore witnesses single-crossingness of \(D(P)\).

Conversely, suppose \(D(P)\) has a single-crossing ordering. Replace each ranking by a consecutive block containing all its occurrences in \(P\). For every candidate pair, this merely repeats each binary value consecutively and introduces no additional change. This witnesses single-crossingness of \(P\). \(\square\)

Now let \(P|_S\) denote restriction of a finite profile to \(S\). If a society’s support consists of the distinct rankings occurring in \(P\), its aggregated restriction has support exactly \(D(P|_S)\). Indeed, both contain precisely the distinct rankings obtained by restricting rankings occurring in \(P\); positivity ensures that aggregation removes none of them.

Consequently, for every \(S\subseteq C\), the restricted society is single-crossing if and only if \(P|_S\) is single-crossing. The numerical values of the positive masses play no role.

2. Polynomial reduction from finite profiles

Fix \(k\ge 3\). Use the finite-profile candidate-partition problem stated in the question, which is \(\mathrm{NP}\)-complete for this fixed \(k\). Its single-crossing definition and allowance of a separate voter ordering for each part agree with the present problem. See [Jaeckle, Peters, and Elkind (2018), Theorem 7](https://dominik-peters.de/publications/nearlysc.pdf).

Given an explicitly listed finite profile \(P=(v_1,\ldots,v_n)\), compute its distinct rankings \(r_1,\ldots,r_\tau\). Here \(\tau\le n\), and deduplication takes polynomial time.

Assign positive dyadic masses as follows. Let \(q=\lceil\log_2\tau\rceil\), and set
\[ w_j=\frac{1}{2^q}\quad(1\le j<\tau),\qquad w_\tau=\frac{2^q-\tau+1}{2^q}. \]
All masses are positive because \(2^q\ge\tau\), and their sum is
\[ \sum_{j=1}^{\tau}w_j =\frac{\tau-1+2^q-\tau+1}{2^q}=1. \]
This also covers \(\tau=1\), giving mass \(1\). Each mass requires \(O(\log(\tau+1))\) bits, so the resulting society has polynomial encoding length. This construction works even if “binary-rational” is interpreted as requiring a finite binary expansion.

Keep the candidate set and \(k\) unchanged. For every partition \(C=S_1\mathbin{\dot\cup}\cdots\mathbin{\dot\cup}S_k\) into nonempty sets, Section 1 gives, separately for each part,
\[ P|_{S_i}\text{ is single-crossing} \quad\Longleftrightarrow\quad \text{the constructed society restricted to }S_i \text{ is single-crossing}. \]
Thus the construction preserves both yes-instances and no-instances and is a polynomial many-one reduction. The support problem is therefore \(\mathrm{NP}\)-hard.

The requirement of *exactly* \(k\) nonempty parts introduces no discrepancy if the finite-profile theorem is phrased using at most \(k\) parts. Single-crossingness is hereditary under candidate restriction: the same voter ordering works for any subset of candidates, and the lemma permits subsequent aggregation. When \(m\ge k\), any partition into fewer than \(k\) nonempty valid parts can repeatedly split a part of size at least two until exactly \(k\) parts remain. Such a part must exist whenever the current number of parts is less than \(k\).

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

A certificate consists of a partition into \(k\) nonempty candidate sets and, for each part, a permutation of the \(\tau\) original support indices.

For each part, the verifier restricts all support rankings to that part without aggregating duplicates. It then checks, for every candidate pair in the part, that its comparison sequence along the certified permutation changes value at most once.

By the lemma, an ordering passing these checks exists exactly when the aggregated restricted society is single-crossing. Each part has its own certified ordering, as required. The certificate has polynomial length, and all checks take polynomial time in \(m,\tau,L\). No expansion of rational masses into voters is needed.

Combining membership with the reduction proves the claimed \(\mathrm{NP}\)-completeness. In particular, a polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).

⟨structured verdict parsed — rendered above⟩

The prover’s argument resolves the task: the support-based problem is NP-complete for every fixed \(k\ge 3\). No substantive or minor mathematical gaps were found.

• Duplicate-ranking lemma. The binary-sequence characterization is correct for the task’s definition, which requires both comparison classes to be intervals. A sequence with at most one change has this property; two or more changes produce an alternating three-position subsequence, violating an interval condition.

Both directions of the lemma are valid. Deleting occurrences produces subsequences and cannot increase the number of changes. Replacing each distinct ranking by a consecutive block of its occurrences also introduces no additional changes. Neither argument assumes that duplicate rankings were consecutive in the original witnessing order.

• Restriction and aggregation. The asserted equality of supports is correct: restricting all occurrences and then deduplicating yields precisely the distinct restrictions obtained from the original support. Positive masses ensure that every such restriction survives aggregation. Applying the lemma to the restricted profile therefore establishes the equivalence for every candidate subset, including singleton subsets, where the pairwise conditions are vacuous.

The conclusion that mass values play no role follows from the given definition: only the positive-mass rankings and their possible ordering enter single-crossingness.

• Finite-profile hardness premise. The prover explicitly invokes the finite-profile NP-completeness premise supplied by USER_TASK, for the same fixed parameter and strict-ranking domain. Its assertion about independently chosen voter orders agrees with the cited paper’s formulation. The paper also defines single-crossingness using intervals for both comparison classes, matching the task. [Jaeckle, Peters, and Elkind, Sections 2 and 5](https://dominik-peters.de/publications/nearlysc.pdf).

• Mass construction and encoding. The construction is valid. For positive support size \(\tau\), the chosen denominator satisfies \(2^q\ge\tau\), so every numerator is positive. The displayed summation correctly gives total mass \(1\). The explicitly handled case \(\tau=1\) gives \(q=0\) and mass \(1\).

Numerators and denominators have \(O(\log(\tau+1))\) bits. Together with \(\tau\le n\) and explicitly listed rankings, this establishes polynomial output length and polynomial construction time. The dyadic choice also satisfies the stricter finite-binary-expansion interpretation.

• Preservation of answers. The equivalence is established separately for every part of every partition. Consequently, the reduction preserves both yes-instances and no-instances. It keeps the candidate set and fixed parameter unchanged and does not require preserving voter multiplicities as masses.

• Exactly \(k\) nonempty parts. The stated refinement argument is correct under the task’s assumption \(m\ge k\). Candidate restriction preserves the witnessing comparison conditions; aggregation is covered by the duplicate lemma. Whenever fewer than \(k\) nonempty parts cover \(m\) candidates, some part has at least two candidates and can be split. Thus the discussion correctly handles an at-most formulation of the source problem.

• NP membership. The certificate is sufficient and polynomial in length. An ordinary partition certificate can be checked for coverage, disjointness, and nonemptiness; each certified permutation can likewise be checked for validity. Testing comparison changes verifies precisely the required single-crossing condition on the unaggregated restrictions.

The duplicate lemma supplies both soundness and completeness relative to aggregated restrictions. For fixed \(k\), the permutations require \(O(k\tau\log(\tau+1))\) bits, and the pairwise checks take polynomial time. No arithmetic expansion proportional to mass denominators is involved.

The conclusion follows from the verified reduction and NP membership. No repair or additional clarification is required.

⟨structured verdict parsed — rendered above⟩