Answer: \(\mathrm{NP}\text{-complete}\), even for \(\tau\le 8\) with all masses integer multiples of \(1/8\).
Theorem 6.9 — class: hardness
PDF text-layer excerpt — equations and symbol order may be approximateGlobal Swaps Single-Peaked Consistency is NP-complete.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given candidates \(C\), ranking types \(T\), a rational distribution \(\mu\) over \(T\), and a rational budget \(b\), decide whether there exist an axis \(A\) and nonnegative transfers \(x_{\pi,\rho}\) such that \(\sum_{\rho}x_{\pi,\rho}=\mu_\pi\), \(x_{\pi,\rho}=0\) whenever \(\rho\notin\operatorname{SP}(A)\), and \(\sum_{\pi,\rho}d_K(\pi,\rho)x_{\pi,\rho}\le b\).
Let \(C\) contain \(m\ge 2\) candidates, and let \(\mathcal R(C)\) be all strict total rankings of \(C\). An axis \(A\) is a total order on \(C\); \(\operatorname{SP}(A)\) denotes the rankings single-peaked with respect to \(A\). Write \(d_K\) for the unnormalized Kendall tau distance, with unit cost per adjacent swap.
A society is given by its support: a list \(T\subseteq\mathcal R(C)\) of \(\tau\) types with positive binary-rational masses \(\mu_\pi\), where \(\sum_{\pi\in T}\mu_\pi=1\). Here \(\tau\) is the support size, not the number of possible rankings. The input also includes a binary-rational budget \(b\ge 0\); let \(L\) be the total input bit length.
Decide whether there exist one common axis \(A\) and real transfers \(x_{\pi,\rho}\ge 0\), indexed by \(\pi\in T\) and \(\rho\in\mathcal R(C)\), satisfying \(\sum_{\rho\in\mathcal R(C)}x_{\pi,\rho}=\mu_\pi\), \(x_{\pi,\rho}=0\) whenever \(\rho\notin\operatorname{SP}(A)\), and \(\sum_{\pi\in T,\rho\in\mathcal R(C)}d_K(\pi,\rho)x_{\pi,\rho}\le b\). Destination rankings need not belong to \(T\); their masses are unconstrained.
Is this decision problem solvable in polynomial time in \(m,\tau,L\), or is it NP-hard?
For finite lists of voters, Global Swaps Single-Peaked Consistency is NP-complete, even with eight voters; with a supplied axis, evaluation takes \(O(nm^3)\) time for \(n\) voters. [Erdélyi, Lackner, and Pfandler (2017)](https://arxiv.org/pdf/1211.2627).
No result settling this exact mass-transfer formulation was located in the literature search.
The decision problem is \(\mathrm{NP}\)-complete, even when \(\tau\le 8\) and every mass is an integer multiple of \(1/8\). Consequently, a polynomial-time algorithm in \(m,\tau,L\) would imply \(\mathrm{P}=\mathrm{NP}\).
For an axis \(A\) and a ranking \(\pi\), define
\(\displaystyle \delta_A(\pi):=\min_{\rho\in\operatorname{SP}(A)}d_K(\pi,\rho).\)
This minimum exists: \(\operatorname{SP}(A)\) is finite and nonempty. Indeed, if \(A\) orders the candidates as \(a_1,\ldots,a_m\), the ranking \(a_1\succ\cdots\succ a_m\) is single-peaked on \(A\).
Lemma. For a fixed axis \(A\), the minimum feasible transfer cost equals
\(\displaystyle F(A):=\sum_{\pi\in T}\mu_\pi\delta_A(\pi).\)
Proof. Let \(x\) satisfy the mass and destination constraints for \(A\). For each \(\pi\in T\), only destinations in \(\operatorname{SP}(A)\) can receive positive mass. Therefore,
\(\displaystyle \sum_{\rho\in\mathcal R(C)}d_K(\pi,\rho)x_{\pi,\rho} \ge \delta_A(\pi)\sum_{\rho\in\mathcal R(C)}x_{\pi,\rho} =\mu_\pi\delta_A(\pi).\)
Summing over \(\pi\) proves that every feasible transfer has cost at least \(F(A)\).
For the reverse inequality, choose a minimizer \(\rho_\pi\in\operatorname{SP}(A)\) for each \(\pi\), and set
\(\displaystyle x_{\pi,\rho}= \begin{cases} \mu_\pi,&\rho=\rho_\pi,\\ 0,&\rho\ne\rho_\pi. \end{cases}\)
These transfers satisfy every mass and destination constraint and have cost exactly \(F(A)\). There are no destination-mass constraints coupling the choices for different types. This proves the lemma.
Thus the original decision question is exactly whether
\(\displaystyle \min_A F(A)\le b.\)
In particular, allowing real transfers and splitting a type among several destinations does not reduce the optimum.
We use the following established result: Global Swaps Single-Peaked Consistency is \(\mathrm{NP}\)-complete even for profiles consisting of eight voters. Here the budget counts adjacent swaps across all voters, and the resulting rankings must be single-peaked on one common axis. This is Theorem 6.9 and Remark 6.10 of [Erdélyi, Lackner, and Pfandler (2017)](https://arxiv.org/pdf/1211.2627).
Take an instance of this restricted problem: a candidate set \(C\), a profile \(P=(\pi_1,\ldots,\pi_8)\), and a nonnegative integer swap budget \(K\).
Construct the mass-transfer instance as follows. Keep the same candidate set, let \(T\) contain precisely the distinct rankings occurring in \(P\), and define
\(\displaystyle r_\pi:=|\{i\in\{1,\ldots,8\}:\pi_i=\pi\}|,\qquad \mu_\pi:=\frac{r_\pi}{8},\qquad b:=\frac K8.\)
This is a valid instance. Each mass is positive, their sum is one, and \(\tau\le 8\). Both the masses and the budget have finite binary expansions. Aggregating the eight rankings takes polynomial time, and encoding \(K/8\) increases the bit length of \(K\) by at most a constant.
For any fixed axis \(A\), the minimum number of adjacent swaps needed to make the profile single-peaked on \(A\) is
\(\displaystyle S(A):=\sum_{i=1}^{8}\delta_A(\pi_i).\)
To justify this equality, any resulting single-peaked ranking for voter \(i\) requires at least \(\delta_A(\pi_i)\) swaps. Conversely, a minimizing destination for each voter can be reached in exactly its Kendall distance, because \(d_K\) is the minimum number of adjacent swaps. The choices for different voters are independent once \(A\) is fixed.
Grouping identical input rankings gives
\(\displaystyle F(A) =\sum_{\pi\in T}\frac{r_\pi}{8}\delta_A(\pi) =\frac18\sum_{i=1}^{8}\delta_A(\pi_i) =\frac{S(A)}8.\)
Consequently,
\(\displaystyle \exists A:\ S(A)\le K \quad\Longleftrightarrow\quad \exists A:\ F(A)\le K/8 \quad\Longleftrightarrow\quad \text{the constructed mass-transfer instance is feasible}.\)
The last equivalence follows from the lemma. This proves a polynomial-time many-one reduction and hence \(\mathrm{NP}\)-hardness, including the stated restriction \(\tau\le 8\).
A certificate consists of one axis \(A\) and one destination ranking \(\rho_\pi\) for every \(\pi\in T\). Its size is \(O((\tau+1)m\log m)\).
The verifier first checks that each supplied order is a permutation of \(C\). It then checks that every \(\rho_\pi\) is single-peaked on \(A\). Explicitly, write \(A=(a_1,\ldots,a_m)\), and let \(a_p\) be the top-ranked candidate of \(\rho_\pi\). Check that
These are exactly the required monotonicity conditions on the two sides of the peak, and can be checked in \(O(m^2)\) time.
Finally, the verifier computes the Kendall distances by counting candidate pairs ordered differently and checks
\(\displaystyle \sum_{\pi\in T}\mu_\pi d_K(\pi,\rho_\pi)\le b.\)
This rational comparison takes polynomial time in the input bit length: a common denominator obtained by multiplying the encoded denominators has bit length at most their total encoded length.
If the certificate passes, sending all mass \(\mu_\pi\) to \(\rho_\pi\) supplies feasible transfers. Conversely, if feasible real transfers exist, the lemma provides minimizing destinations whose deterministic transfers also satisfy the budget. Hence every yes-instance has such a certificate.
Together with the reduction, this proves \(\mathrm{NP}\)-completeness.
⟨structured verdict parsed — rendered above⟩
The proof is correct and resolves the task. It establishes \(\mathrm{NP}\)-completeness, including the restriction \(\tau\le 8\) with every mass an integer multiple of \(1/8\). No major or minor mathematical issues were found.
The definition of \(\delta_A(\pi)\) is valid. There are finitely many destination rankings, and \(\operatorname{SP}(A)\) is nonempty: the ranking following the axis from one endpoint to the other is single-peaked with its peak at that endpoint.
The lower-bound inequality is correct. For destinations in \(\operatorname{SP}(A)\), the distance is at least \(\delta_A(\pi)\); destinations outside that set have zero transfer. Nonnegativity of transfers therefore permits the termwise inequality, and the mass constraint gives the stated lower bound \(\mu_\pi\delta_A(\pi)\).
The proposed deterministic transfers attain that bound. Each source sends exactly its prescribed mass to an allowed destination. Different sources may choose the same destination because destination masses are unconstrained.
Consequently, the fixed-axis optimum is exactly \(F(A)\). This is an attained minimum, not merely an infimum. There are also finitely many axes, so the subsequent expression \(\min_A F(A)\) is justified.
Finding: The lemma and the equivalence between transfer feasibility and \(\min_A F(A)\le b\) are rigorous. Real-valued splitting introduces no advantage.
The external result is accurately identified. Theorem 6.9 establishes \(\mathrm{NP}\)-completeness of Global Swaps Single-Peaked Consistency, and Remark 6.10 explicitly gives the eight-voter restriction. Definition 3.6 uses a total budget of swaps of consecutive candidates across the profile and requires a common axis. These are precisely the source-problem features used in the reduction. [Erdélyi, Lackner, and Pfandler (2017), Definition 3.6, Theorem 6.9, and Remark 6.10](https://arxiv.org/pdf/1211.2627).
Finding: The theorem is stated sufficiently precisely, and its hypotheses match the reduction.
Aggregating identical source rankings produces a support of size at most eight. Each retained type has positive multiplicity \(r_\pi\), so its mass \(r_\pi/8\) is positive. The multiplicities sum to eight, proving normalization.
All constructed masses and the budget \(K/8\) are binary-rational. Their encoding lengths are polynomial in the source input length; dividing the integer budget by eight adds only constant encoding overhead under the usual rational representation.
The construction preserves the candidate set and strict total rankings. No requirement forces destinations to lie in the support.
Finding: The constructed instance meets every input restriction, and the transformation is polynomial-time.
For a fixed axis, each voter needs at least \(\delta_A(\pi_i)\) adjacent swaps. Conversely, each minimizing destination can be reached in exactly its Kendall distance, by the stipulated unit-cost adjacent-swap interpretation of \(d_K\). Since the voters’ modifications are independent once the axis is fixed, their minima add to \(S(A)\).
Grouping repeated rankings correctly gives \(F(A)=S(A)/8\). Thus the same axis meets the source budget exactly when it meets the constructed budget. Taking the existential quantifier over axes preserves both directions of the equivalence.
Aggregation does not discard relevant flexibility: the fixed-axis lemma already establishes that identical source rankings gain nothing by being split among different destinations.
Finding: The many-one reduction proves the claimed restricted \(\mathrm{NP}\)-hardness.
An axis and one destination ranking per support type form a polynomial-size certificate.
The permutation checks establish that all supplied orders are valid. The two stated monotonicity conditions exactly characterize strict single-peakedness on the supplied axis. They impose no unnecessary comparisons between opposite sides of the peak. At an endpoint peak, one side’s conditions are vacuous, as required.
Counting discordant candidate pairs computes the unnormalized Kendall distance. The weighted sum can be compared with the budget using exact rational arithmetic in polynomial time. The denominator-product bit-length bound is valid; including the budget denominator preserves that bound.
Soundness follows by sending each type’s entire mass to its certified destination. Completeness follows from the fixed-axis lemma: any feasible transfers imply the existence of deterministic minimizing destinations within budget.
The argument also covers \(b=0\) and \(m=2\) without exceptions.
Finding: Membership in \(\mathrm{NP}\) is fully established.
No additional lemma, clarification, or correction is needed. The output establishes the stronger \(\mathrm{NP}\)-completeness claim and therefore answers the requested polynomial-time-versus-hardness question.
⟨structured verdict parsed — rendered above⟩
Tier: machine-proved, adversarially reviewed by an independent model. No human has checked this proof. Generated from pipeline artifacts by tools/atlas_build.py.