Answer: —
Theorem 1 — class: algorithmic
PDF text-layer excerpt — equations and symbol order may be approximateGiven n noisy rankings at an average distance of at most t from an unknown true ranking σ∗according to a distance metric d, it is always possible to find a ranking at distance at most 2t from σ∗according to d.
statement extracted from the paper’s text layer; consult the paper for the exact wording
Given \(m\) alternatives, a support \(S\) of \(\tau\) ranking types with positive binary-rational masses \(\mu_\sigma\) summing to \(1\), one of the paper’s distance metrics \(d\), and a bound \(t\), promised that \(G_d(\mu,t)=\{\sigma^*\in\mathcal L(A):\sum_{\sigma\in S}\mu_\sigma d(\sigma,\sigma^*)\le t\}\) is nonempty, compute a ranking \(\hat\sigma\) minimizing \(\max_{\sigma^*\in G_d(\mu,t)}d(\hat\sigma,\sigma^*)\), and its minimum radius.
Let \(A\) contain \(m\geq 1\) alternatives, and let \(\mathcal L(A)\) be its strict total orders.
A society is given by its support: a list \(S\subseteq\mathcal L(A)\) of \(\tau\) types with positive binary-rational masses \(\mu_\sigma\) summing to \(1\). Here \(\tau\) is the support size, not the number of possible rankings.
Choose \(d\) from the unnormalized Kendall tau, Spearman footrule, maximum displacement, and Cayley distances; maximum displacement is \(d(\rho,\sigma)=\max_{a\in A}|\operatorname{pos}_\rho(a)-\operatorname{pos}_\sigma(a)|\).
The input includes a positive binary-rational bound \(t\), with the promise that \(G_d(\mu,t)=\{\rho\in\mathcal L(A):\sum_{\sigma\in S}\mu_\sigma d(\sigma,\rho)\leq t\}\) is nonempty.
Compute a ranking \(\hat\sigma\in\mathcal L(A)\) attaining \(r_d(\mu,t)=\min_{\eta\in\mathcal L(A)}\max_{\rho\in G_d(\mu,t)}d(\eta,\rho)\), and compute this radius exactly. Any minimizing ranking is acceptable.
Let \(L\) be the total binary input length; state running times in \(m,\tau,L\).
For each of the four fixed metrics, is this promised exact computation solvable in time polynomial in \(m,\tau,L\), or is it NP-hard?
For finite profiles, a ranking within \(2t\) of every feasible ground truth always exists; this is an existence guarantee without a polynomial running-time assertion. A weaker \(3t\) guarantee is achievable in polynomial time. [Procaccia, Shah, and Zick](https://procaccia.info/wp-content/uploads/2020/03/error.pdf)
No result settling the exact computation for the rational-mass formulation was identified in the literature search.
The following classifications are established:
| Metric | Promised exact computation |
|---|---|
| Unnormalized Kendall tau | $\mathrm{NP}$-hard |
| Spearman footrule | Unresolved here |
| Maximum displacement | $\mathrm{NP}$-hard |
| Cayley | $\mathrm{NP}$-hard |
For each of the three hardness results, deciding whether the radius is positive is already $\mathrm{NP}$-hard, and the reduction supplies a known feasible ranking.
The additional results for footrule are:
For all four metrics, a society with one support type admits polynomial-time exact computation.
All results used below are proved here, except for one precisely stated complexity theorem concerning Kemeny consensus recognition.
A ranking $\rho$ is represented by the bijection
$$
p_\rho:A\longrightarrow\{1,\ldots,m\},
\qquad
p_\rho(a)=\operatorname{pos}_\rho(a).
$$
The footrule distance is
$$
d_{\mathrm{FR}}(\rho,\sigma)
=
\sum_{a\in A}|p_\rho(a)-p_\sigma(a)|.
$$
The Cayley distance counts arbitrary transpositions. Kendall tau counts unordered pairs whose relative order differs.
Initially, “binary-rational” means a rational represented by binary numerator and denominator. Explicit constructions below also handle the stricter interpretation of dyadic rationals.
For running-time bounds, put
$$
B=L+m\left\lceil\log_2(m+1)\right\rceil.
$$
Exact arithmetic can use a common denominator obtained by multiplying the input denominators. Its binary length is at most their total encoding length. Thus the integer quantities arising from feasibility computations have $O(B)$ bits. We use conservative $O(B^2)$ bounds for arithmetic operations.
When $m=1$, every metric is identically zero, so the unique ranking and radius zero solve the problem. The remaining discussion concerns variable $m\geq2$.
Let $d$ be an integer-valued metric on rankings, with diameter at most $D$. Suppose an instance specifies positive integer weights $w_\sigma$, the objective
$$
C(\rho)=\sum_\sigma w_\sigma d(\sigma,\rho),
$$
and a baseline ranking $\eta_0$ satisfying
$$
C_0=C(\eta_0)>0.
$$
Define
$$
W=\sum_\sigma w_\sigma,\qquad
K=D+1,\qquad
Z=KW+1.
$$
Multiply every original weight by $K$, add weight $1$ at $\eta_0$, combine duplicate rankings, and normalize by $Z$. Set
$$
t=\frac{KC_0}{Z}.
$$
The new expected-distance objective is
$$
F(\rho)=\frac{KC(\rho)+d(\eta_0,\rho)}{Z}.
$$
Since $F(\eta_0)=t$, the output satisfies the nonemptiness promise and has positive threshold.
If $C(\rho)<C_0$, integrality implies $C(\rho)\leq C_0-1$, and therefore
$$
KC(\rho)+d(\eta_0,\rho)
\leq K(C_0-1)+D
=KC_0-1.
$$
Thus every strict improvement is feasible.
If $\rho\neq\eta_0$ and $C(\rho)\geq C_0$, then
$$
KC(\rho)+d(\eta_0,\rho)>KC_0,
$$
because a metric assigns positive distance to distinct rankings. Consequently,
$$
G_d(\mu,t)
=
\{\eta_0\}\cup\{\rho:C(\rho)<C_0\}.
$$
For any nonempty finite set $G$ in a metric space, its minimax radius is zero exactly when $G$ is a singleton. Indeed, radius zero requires every member of $G$ to equal the center; conversely, a singleton has its member as a zero-radius center. Hence
$$
r_d(\mu,t)>0
\quad\Longleftrightarrow\quad
\exists\rho:\ C(\rho)<C(\eta_0).
$$
The construction increases the support size by at most one. All weights, masses and thresholds have polynomial encoding length.
Moreover, two distinct feasible rankings certify positive radius. Both feasibility checks take polynomial time using exact rational arithmetic. Thus the positive-radius decision problem has polynomially checkable certificates on promised inputs.
Here is a rounding procedure that will also be useful later.
Given positive rational masses $q_1,\ldots,q_s$ summing to one, choose a power of two $N$ such that
$$
Nq_i\geq2
\quad\text{for every }i.
$$
Let
$$
c_i=\lfloor Nq_i\rfloor,\qquad
h=N-\sum_i c_i.
$$
Since
$$
h=\sum_i(Nq_i-\lfloor Nq_i\rfloor),
$$
$h$ is an integer satisfying $0\leq h<s$. Add $1$ to any $h$ of the integers $c_i$, obtaining $c_i'$. Then
$$
q_i'=\frac{c_i'}N>0,\qquad
\sum_iq_i'=1,\qquad
\sum_i|q_i'-q_i|<\frac{s}{N}.
$$
For the reduction above, choose also
$$
N>4DZs,
$$
and redefine the threshold as
$$
t'=F'(\eta_0),
$$
where $F'$ uses the rounded masses.
For $\rho\neq\eta_0$, the original difference
$$
F(\rho)-F(\eta_0)
$$
has absolute value at least $1/Z$: its numerator is a nonzero integer. Its change under rounding is bounded by
$$
\begin{aligned}
\big|
(F'(\rho)-F'(\eta_0))-(F(\rho)-F(\eta_0))
\big|
&\leq
\sum_i|q_i'-q_i|
\,|d(\sigma_i,\rho)-d(\sigma_i,\eta_0)|\\
&\leq D\sum_i|q_i'-q_i|\\
&<\frac1{4Z}.
\end{aligned}
$$
Every sign is therefore preserved, and the feasible set is unchanged. The threshold remains positive because $C_0>0$ and every rounded mass remains positive.
A suitable power of two has polynomial binary length: the binary lengths of $D,Z,s$ and $1/\min_iq_i$ are polynomial in the reduction input length.
The external theorem used here is:
Given an explicitly listed electorate of strict total orders and a specified total order, recognizing whether that order minimizes the sum of unnormalized Kendall tau distances is $\mathrm{coNP}$-complete under polynomial-time many-one reductions.
This is Theorem 5 of Fitzsimmons and Hemaspaandra, [*Kemeny Consensus Complexity*](https://www.ijcai.org/proceedings/2021/0028.pdf).
Taking complements, recognition of a strict improvement over the specified order is $\mathrm{NP}$-complete. The hypotheses match our setting: votes and the specified ranking are strict total orders, and the score is the sum of unnormalized Kendall tau distances.
Combine duplicate votes into integer multiplicities. This preserves the score and produces a weighted support of polynomial size.
If the specified score is zero, no strict improvement exists. Map this case to the fixed instance on two alternatives with one support ranking of mass $1$ and threshold $1/2$. Its feasible set is a singleton.
Otherwise apply Section 2 with
$$
D=\binom m2.
$$
The resulting instance is promised nonempty, and has positive radius exactly when a strict improvement exists.
Therefore promised exact computation for Kendall tau is $\mathrm{NP}$-hard. Its positive-radius decision problem is $\mathrm{NP}$-complete on promised instances.
We establish two auxiliary hardness results without relying on optimal-solution recognition results for those problems.
Start with a Boolean satisfiability instance. Construct a circuit using AND and NOT gates, introduce a variable for each gate output, and denote the circuit output by $y$.
For an AND gate with inputs $x,z$ and output $w$, use
$$
P_{\mathrm{AND}}(x,z,w)
=
xz-2xw-2zw+3w.
$$
If $w=0$, this is $xz$. If $w=1$, its values for
$$
(x,z)=(0,0),(1,0),(0,1),(1,1)
$$
are respectively $3,1,1,0$. Thus it is nonnegative and vanishes exactly when $w=xz$.
For a NOT gate, use
$$
P_{\mathrm{NOT}}(x,w)=(x+w-1)^2.
$$
It is nonnegative and vanishes exactly when $w=1-x$. On Boolean variables, replacing squares by their variables makes this expression quadratic.
Let $P$ be the sum of all gate penalties. Introduce a selector bit $s$ and define
$$
f=s-2s(1-y)-2P.
$$
Choose arbitrary input bits, evaluate every gate correctly, and set $s=0$. This specifies a baseline assignment $x^0$ with $f(x^0)=0$.
The following cases establish the reduction:
Consequently,
$$
\exists x:\ f(x)>f(x^0)
\quad\Longleftrightarrow\quad
\text{the original formula is satisfiable}.
$$
The circuit, objective and baseline have polynomial encoding length.
Expand $f$ and simplify Boolean squares. A positive linear or quadratic monomial is already a positive reward for a pattern requiring one or two bits to equal $1$.
For negative monomials, use
$$
-kx=k(1-x)-k
$$
and
$$
-kxz
=
k(1-x)(1-z)+kx(1-z)+k(1-x)z-k.
$$
The latter identity follows because the three pattern indicators sum to $1-xz$.
It follows that we can construct
$$
R(x)=\sum_Pw_P\,\mathbf1[x\text{ matches }P],
$$
where each $w_P$ is a positive integer and each pattern specifies at most two bits, such that $R-f$ is constant.
Thus deciding whether the specified assignment $x^0$ admits a strict improvement for $R$ is $\mathrm{NP}$-hard. It belongs to $\mathrm{NP}$ because a proposed assignment can be evaluated in polynomial time.
Write the simplified objective as
$$
f(x)=c+\sum_i h_ix_i+\sum_{i<j}J_{ij}x_ix_j.
$$
Introduce a reference vertex $0$, and interpret $x_i$ as whether vertex $i$ lies opposite vertex $0$.
Since
$$
2x_ix_j=x_i+x_j-(x_i\oplus x_j),
$$
we have
$$
2(f(x)-c)
=
\sum_i\left(2h_i+\sum_{j\neq i}J_{ij}\right)x_i
-
\sum_{i<j}J_{ij}(x_i\oplus x_j).
$$
The right-hand side is a cut objective with signed integer edge weights.
Replace a negative edge of weight $-k$ joining $u,v$ by a path $u,z,v$ whose two edges have positive weight $k$. For fixed endpoint sides, the best placement of $z$ contributes
$$
\begin{cases}
2k,&u,v\text{ are on the same side},\\
k,&u,v\text{ are on opposite sides}.
\end{cases}
$$
This is
$$
2k-k\,\mathbf1[u,v\text{ are on opposite sides}],
$$
the original negative-edge contribution plus a constant.
The new vertices belong to separate gadgets, so they can be optimized independently. Extend the specified baseline cut by optimizing each gadget vertex.
If an assignment improves $f$, its optimal extension improves the positive-weight cut objective. Conversely, an arbitrary improved cut has value at most the optimal extension of its original vertices. That optimal extension must therefore improve the baseline, yielding an improvement of $f$.
Hence strict-improvement recognition for positive-integer-weight Max-Cut with a specified cut is $\mathrm{NP}$-complete.
Reduce the pattern-reward problem from Section 4.2.
Suppose there are $N$ Boolean variables. Create a block of six alternatives for each variable. In the base ranking, its distinguished alternatives $a_i,b_i$ occupy the third and fourth positions, denoted $p_i,p_i+1$.
The canonical ranking $\eta(x)$ preserves all blocks and fillers, and swaps $a_i,b_i$ exactly when $x_i=1$.
Add four blocks of five alternatives, with distinguished alternatives $z,u_1,u_2,u_3$ initially at their middle positions. Denote the position of $z$ by $q$. Thus
$$
m=6N+20.
$$
A local move places one distinguished alternative at another position within its block, shifting intervening alternatives by one position.
For each of $a_i,b_i$, construct two variable-part guards placing that alternative respectively at
$$
p_i+2,\qquad p_i-1.
$$
Construct two further guards placing $z$ at $q+2$ and $q-2$. There are
$$
g=4N+2
$$
such guards.
Replace each guard by three full rankings whose extra-block distinguished displacements are respectively
$$
(-2,0,2),\qquad (2,-2,0),\qquad (0,2,-2).
$$
Any pair in a triple has maximum displacement distance $4$: one extra distinguished alternative differs by four positions, while all other positional differences are at most four.
For any ranking $\rho$, let its distances to a triple be $d_1,d_2,d_3$. The triangle inequality gives
$$
d_1+d_2\geq4,\qquad
d_2+d_3\geq4,\qquad
d_3+d_1\geq4.
$$
Adding yields
$$
d_1+d_2+d_3\geq6.
$$
Equality holds exactly when $d_1=d_2=d_3=2$: if the sum is six, each pairwise inequality forces the remaining distance to be at most two.
Every canonical ranking has distance exactly two to every guard ranking. Extra distinguished displacements supply distance two; the local moves and canonical swaps produce no larger displacement.
Suppose $\rho$ attains equality for every guard triple. Its distance to every guard ranking is then two. For either distinguished alternative in variable block $i$, the two guards imply
$$
p_\rho(a_i),p_\rho(b_i)
\in
[p_i,p_i+4]\cap[p_i-3,p_i+1]
=
[p_i,p_i+1].
$$
Their positions are distinct, so they occupy exactly those two slots, encoding a bit $x_i(\rho)$.
Similarly,
$$
p_\rho(z)
\in[q,q+4]\cap[q-4,q]
=
\{q\}.
$$
No restriction on fillers is needed.
For each pattern $P$, construct $\sigma_P$ by:
For a canonical ranking, $z$ contributes displacement two. An active $a_i$ has displacement two when its requirement is matched and three otherwise. All other displacements are at most two. Hence
$$
d_{\mathrm{MD}}(\sigma_P,\eta(x))
=
3-\mathbf1[x\text{ matches }P].
$$
For any ranking satisfying all guard equalities, its distinguished positions alone give
$$
d_{\mathrm{MD}}(\sigma_P,\rho)
\geq
3-\mathbf1[x(\rho)\text{ matches }P].
$$
Uncontrolled fillers cannot reduce this lower bound.
Let
$$
Q=\sum_Pw_P,\qquad H=3Q+1.
$$
Give every guard ranking weight $H$ and every pattern ranking weight $w_P$. For the resulting objective,
$$
C_{\mathrm{MD}}(\eta(x))
=
6gH+3Q-R(x).
$$
If some guard triple fails equality, its integer distance sum is at least seven. Thus
$$
C_{\mathrm{MD}}(\rho)\geq6gH+H>6gH+3Q,
$$
so $\rho$ cannot improve any canonical baseline.
Otherwise $\rho$ encodes $x(\rho)$ and satisfies
$$
C_{\mathrm{MD}}(\rho)
\geq6gH+3Q-R(x(\rho)).
$$
Therefore
$$
\exists\rho:\ C_{\mathrm{MD}}(\rho)
<
C_{\mathrm{MD}}(\eta(x^0))
\quad\Longleftrightarrow\quad
\exists x:\ R(x)>R(x^0).
$$
The construction uses polynomially many alternatives and rankings, with polynomial weight encoding length. Its baseline score is positive because the guard contribution is positive.
Applying Section 2 with $D=m-1$ proves $\mathrm{NP}$-hardness of promised exact maximum-displacement computation, and $\mathrm{NP}$-completeness of positive-radius recognition.
Take the positive-weight Max-Cut strict-improvement instance from Section 4.3, with vertices $1,\ldots,N$, edge weights $w_e$, and specified cut $x^0$.
Create alternatives $a_i,b_i$ for each vertex. Identify rankings with permutations relative to a base ranking, and put
$$
t_i=(a_i\,b_i),\qquad
T=\prod_{i=1}^Nt_i,\qquad
\eta(x)=\prod_{i:x_i=1}t_i.
$$
There are $m=2N$ alternatives.
For a permutation $\pi$, its Cayley distance from the identity is $m-c(\pi)$, where $c(\pi)$ counts cycles, including fixed points. A transposition changes the cycle count by one, giving the lower bound; decomposing each cycle of length $\ell$ into $\ell-1$ transpositions attains it. This also shows that the metric is invariant under left and right multiplication.
The triangle inequality gives
$$
d_{\mathrm{CY}}(\mathrm{id},\rho)
+
d_{\mathrm{CY}}(T,\rho)
\geq N.
$$
Equality holds exactly for the canonical permutations $\eta(x)$.
To prove necessity, concatenate shortest transposition paths from $\mathrm{id}$ to $\rho$ and from $\rho$ to $T$. Under equality, the path has length $N$. The cycle count decreases from $2N$ to $N$, so every step must merge cycles.
The cycle partitions therefore only coarsen. A step cannot merge elements from distinct final pairs $\{a_i,b_i\}$, since no later step could separate them. Every step must swap one prescribed pair. Thus every intermediate permutation, including $\rho$, is a product of a subset of the $t_i$.
Conversely, a product of $k$ selected pair swaps has distances $k$ and $N-k$ from the anchors, so equality holds.
For $e=\{i,j\}$, define
$$
p_e=(a_i\,a_j)(b_i\,b_j),
\qquad
q_e=p_et_i.
$$
On the four indicated alternatives, cycle counting gives
$$
\begin{array}{c|cccc}
(x_i,x_j)&(0,0)&(0,1)&(1,0)&(1,1)\\ \hline
d_{\mathrm{CY}}(\eta(x),q_e)&3&2&2&3.
\end{array}
$$
For verification, write $a=a_i,b=b_i,c=a_j,d=b_j$. With rightmost composition first,
$$
q_e=(a\,d\,b\,c),
$$
a four-cycle. Multiplication by either prescribed pair transposition yields two transposition cycles; multiplication by both yields another four-cycle.
Outside this block, each selected pair contributes one. Since $T^2=\mathrm{id}$, right invariance gives
$$
d_{\mathrm{CY}}(\eta(x),q_eT)
=
d_{\mathrm{CY}}(\eta(x)T,q_e),
$$
and
$$
\eta(x)T=\eta(\mathbf1-x).
$$
The selected and complementary pairs outside the edge contribute a combined $N-2$. The two edge-block contributions sum to six for equal bits and four for different bits. Therefore
$$
d_{\mathrm{CY}}(\eta(x),q_e)
+
d_{\mathrm{CY}}(\eta(x),q_eT)
=
N+4-2\mathbf1[x_i\neq x_j].
$$
Put
$$
Q=\sum_ew_e,\qquad H=Q(N+4)+1.
$$
Give each anchor weight $H$, and give each of $q_e,q_eT$ weight $w_e$. Then
$$
C_{\mathrm{CY}}(\eta(x))
=
HN+Q(N+4)-2\operatorname{Cut}(x).
$$
A noncanonical ranking has integer anchor-distance sum at least $N+1$, so
$$
C_{\mathrm{CY}}(\rho)
\geq H(N+1)
>
HN+Q(N+4).
$$
It cannot improve a canonical baseline. For canonical rankings, improvement is precisely improvement of the cut:
$$
\exists\rho:\ C_{\mathrm{CY}}(\rho)
<
C_{\mathrm{CY}}(\eta(x^0))
\quad\Longleftrightarrow\quad
\exists x:\ \operatorname{Cut}(x)>\operatorname{Cut}(x^0).
$$
The support has at most $2|E|+2$ types before duplicates are combined. The construction is polynomial, and its baseline score is positive.
Applying Section 2 with $D=m-1$ proves $\mathrm{NP}$-hardness of promised exact Cayley computation, and $\mathrm{NP}$-completeness of positive-radius recognition.
For footrule define the assignment costs
$$
c_{aj}
=
\sum_{\sigma\in S}\mu_\sigma|p_\sigma(a)-j|.
$$
Then
$$
F_{\mathrm{FR}}(\rho)
=
\sum_ac_{a,p_\rho(a)}.
$$
Thus minimizing expected footrule distance is a minimum-cost perfect matching between alternatives and positions.
A minimum-cost assignment can be found by the Hungarian algorithm in $O(m^3)$ arithmetic operations. Costs and the threshold can first be scaled to integers with $O(B)$ bits.
Find a minimum-cost ranking $\rho_0$. The promise ensures that it is feasible.
For every alternative $a$ and position $j\neq p_{\rho_0}(a)$, compute the minimum assignment cost subject to $p_\rho(a)=j$. This is done by fixing that edge, deleting its row and column, and solving the residual assignment problem.
If one such optimum is at most $t$, its assignment is a second feasible ranking, so the radius is positive.
Conversely, every $\rho\neq\rho_0$ differs from $\rho_0$ on some alternative. It therefore appears in one of these constrained problems. If every constrained optimum exceeds $t$, $\rho_0$ is the only feasible ranking and the radius is zero.
There are at most $m^2$ constrained problems. A conservative bit-operation bound is
$$
O\!\left(
L^3+(\tau m^2+m^5)B^2
\right).
$$
The same computations determine every feasible positional choice:
$$
(a,j)\text{ occurs in some feasible ranking}
\quad\Longleftrightarrow\quad
\min_{\rho:p_\rho(a)=j}F_{\mathrm{FR}}(\rho)\leq t.
$$
This proves that positive-radius recognition for footrule is polynomial-time solvable. Consequently, the strict-improvement reduction used for the other metrics cannot establish footrule hardness through the positive-radius test unless $\mathrm P=\mathrm{NP}$.
Let $C=(C_{aj})$ be any rational $m\times m$ matrix, with $m\geq2$, and let $b$ be a rational budget. Assume at least one permutation satisfies
$$
\sum_aC_{a,p_\rho(a)}\leq b.
$$
We construct a footrule profile whose feasible rankings are exactly those satisfying this budget.
Let
$$
\overline C_j=\frac1m\sum_aC_{aj},
\qquad
C'_{aj}=C_{aj}-\overline C_j,
$$
and define
$$
E_{aj}
=
C'_{aj}-\frac{C'_{a1}+C'_{am}}2.
$$
Then
$$
\sum_aE_{aj}=0,\qquad E_{a1}+E_{am}=0.
$$
Indeed, every column of $C'$ sums to zero, so the subtracted row constants have total zero.
Writing
$$
K=\sum_j\overline C_j=\frac1m\sum_{a,j}C_{aj},
$$
we obtain, for every permutation,
$$
\sum_aE_{a,p_\rho(a)}
=
\sum_aC_{a,p_\rho(a)}-K.
$$
Put
$$
u(j)=\frac1m\sum_{k=1}^m|j-k|,
\qquad
f_a(j)=u(j)+\varepsilon E_{aj}.
$$
For $1\leq j<m$, write
$$
\Delta f_a(j)=f_a(j+1)-f_a(j).
$$
Define
$$
P_{a1}=\frac{1+\Delta f_a(1)}2,
$$
$$
P_{ak}
=
\frac{\Delta f_a(k)-\Delta f_a(k-1)}2
\quad(2\leq k\leq m-1),
$$
and
$$
P_{am}=\frac{1-\Delta f_a(m-1)}2.
$$
At $\varepsilon=0$, all entries equal $1/m$. Each entry has the form
$$
P_{ak}=\frac1m+\varepsilon e_{ak},
$$
where $e_{ak}$ is a rational linear combination of entries of $E$. Let
$$
M=\max_{a,k}|e_{ak}|,
\qquad
\varepsilon=\frac1{2m(M+1)}.
$$
Then
$$
P_{ak}
\geq\frac1m-\varepsilon M
>\frac1{2m}>0.
$$
The choice has polynomial rational encoding length.
The row sums telescope to one. The column sums also equal one, because the perturbations sum to zero across alternatives, using $\sum_aE_{aj}=0$. Thus $P$ is doubly stochastic.
We claim that
$$
f_a(j)=\sum_kP_{ak}|j-k|.
$$
For the right-hand side, its difference between $j+1$ and $j$ is
$$
2\sum_{k\leq j}P_{ak}-1,
$$
which equals $\Delta f_a(j)$ by the definitions of $P$. The two functions therefore differ by a constant.
Their endpoint sums agree:
$$
\sum_kP_{ak}\bigl(|1-k|+|m-k|\bigr)=m-1,
$$
while
$$
f_a(1)+f_a(m)
=
u(1)+u(m)+\varepsilon(E_{a1}+E_{am})
=
m-1.
$$
Their constant difference is consequently zero.
We give a constructive decomposition of $P$ into permutation matrices.
At any stage, the residual nonnegative matrix has a common row and column sum $\beta$. If $\beta>0$, its positive support has a perfect matching. To check Hall’s condition, let $X$ be a row set and $Y$ its neighbor set. All mass from $X$ lies in $Y$, so
$$
|X|\beta\leq|Y|\beta,
$$
and therefore $|X|\leq|Y|$.
Find a perfect matching in this support and subtract the smallest entry along that matching from each matched entry. At least one positive entry disappears. No positive entry is created. Hence at most $m^2$ iterations occur.
Each matching defines a ranking, and its subtracted quantity is its positive mass. The masses sum to one.
The arithmetic has polynomial encoding length. In particular, put all initial entries over one common denominator; every subsequent subtraction then operates on integer numerators over that same denominator.
The positional marginals of the resulting profile are $P$, so
$$
\begin{aligned}
F_{\mathrm{FR}}(\rho)
&=\sum_af_a(p_\rho(a))\\
&=\frac{m^2-1}{3}
+\varepsilon\left(
\sum_aC_{a,p_\rho(a)}-K
\right).
\end{aligned}
$$
Here
$$
\begin{aligned}
\sum_{j=1}^mu(j)
&=\frac1m\sum_{j,k}|j-k|\\
&=\frac2m\sum_{h=1}^{m-1}h(m-h)\\
&=\frac{m^2-1}{3}.
\end{aligned}
$$
Thus the desired budget is exactly equivalent to feasibility at
$$
t=\frac{m^2-1}{3}+\varepsilon(b-K).
$$
The threshold is positive. Every ranking has strictly positive expected distance because every positional marginal is positive and $m\geq2$. A ranking satisfying the assignment budget has expected distance at most $t$, so $t>0$.
The construction has at most $m^2$ support types and takes polynomial time in the encoding length of $C,b$ and in $m$.
Scale $C,b$ by a positive common denominator, obtaining integer costs and an integer budget without changing the feasible rankings. Apply the preceding construction, but use threshold
$$
t_*=\frac{m^2-1}{3}+\varepsilon\left(b+\frac12-K\right).
$$
Integrality ensures that the feasible set remains precisely the assignments of cost at most $b$. Moreover, every ranking satisfies
$$
|F_{\mathrm{FR}}(\rho)-t_*|\geq\frac{\varepsilon}{2}.
$$
Let $s$ be the constructed support size and let $D=m(m-1)$, a valid footrule diameter bound. Use the rounding procedure from Section 2 with a power of two $N$ satisfying
$$
Nq_i\geq2\quad\text{for every mass }q_i,
\qquad
N>\frac{8Ds}{\varepsilon}.
$$
Then
$$
|F'_{\mathrm{FR}}(\rho)-F_{\mathrm{FR}}(\rho)|
<
\frac{\varepsilon}{8}.
$$
Set
$$
t'=\frac{\lceil Nt_*\rceil}{N}.
$$
Since $D,s\geq1$, the chosen precision also gives
$$
0\leq t'-t_*<\frac{\varepsilon}{8}.
$$
The combined perturbation is less than $\varepsilon/4$, smaller than the feasibility margin $\varepsilon/2$. Every feasibility decision is preserved.
Both masses and threshold are now positive dyadic rationals with polynomial encoding length.
The polynomial computation of feasible positions in Section 7 does not extend directly to exact footrule centers.
We prove this with a family whose discrepancy grows with the number of alternatives.
Let $m=2n$, where $n\geq2$. Partition the alternatives into ordered pairs
$$
(a_1,b_1),\ldots,(a_n,b_n).
$$
A canonical ranking preserves the pair blocks and chooses either orientation within each block. Encode it by $x\in\{0,1\}^n$. For canonical rankings,
$$
d_{\mathrm{FR}}(\eta(x),\eta(y))
=
2|\{i:x_i\neq y_i\}|.
$$
Consider
$$
G_1=\{\eta(0)\}\cup\{\eta(e_i):1\leq i\leq n\},
$$
where $e_i$ is the $i$th unit vector, and
$$
G_2=\{\eta(x):x\in\{0,1\}^n\}.
$$
For both sets, each alternative in block $i$ can occupy exactly positions $2i-1$ and $2i$. Thus the sets have identical feasible positional choices, not merely identical extrema.
For $G_1$, use assignment costs
$$
C_{a_i,2i-1}=C_{b_i,2i}=C_{b_i,2i-1}=0,
\qquad
C_{a_i,2i}=1,
$$
and assign cost $n+1$ to every position outside an alternative’s own block. Set the budget to one.
Any cross-block placement already exceeds the budget. A canonical ranking has cost equal to its number of swapped blocks, so the feasible set is exactly $G_1$.
For $G_2$, give all within-block edges cost zero, all other edges cost $n+1$, and set the budget to zero.
Section 8 realizes both sets as promised footrule instances.
The base ranking is at distance at most two from every member of $G_1$, so
$$
r_{\mathrm{FR}}(G_1)\leq2.
$$
Every footrule distance is even: because $|z|\equiv z\pmod2$,
$$
d_{\mathrm{FR}}(\rho,\sigma)
\equiv
\sum_a(p_\rho(a)-p_\sigma(a))
=0\pmod2.
$$
Since $G_1$ is not a singleton, its radius cannot be zero. Therefore
$$
r_{\mathrm{FR}}(G_1)=2.
$$
For $G_2$, we first show that any center can be replaced by a canonical center without increasing its distance to any member of $G_2$.
Suppose a center places an alternative from an earlier block at position $p$ and one from a later block at position $q$, with $q<p$. In every canonical ranking, their target positions satisfy $r<s$. The inequality
$$
|q-r|+|p-s|
\leq
|p-r|+|q-s|
$$
shows that swapping the two alternatives cannot increase footrule distance. To verify the inequality, the function
$$
h(z)=|z-r|-|z-s|
$$
is nondecreasing for $r<s$, so $h(q)\leq h(p)$.
Repeatedly swapping adjacent block inversions sorts the blocks. Every swap has the stated property for every member of $G_2$. The resulting center is canonical.
For each canonical center $\eta(x)$, the complementary ranking $\eta(\mathbf1-x)$ belongs to $G_2$ and has distance $2n$. All distances between canonical rankings are at most $2n$. Consequently,
$$
r_{\mathrm{FR}}(G_2)=2n.
$$
Thus identical feasible positional choices are compatible with radii $2$ and $2n$. Positional information alone cannot determine the exact footrule radius.
Let $h\geq0$ be an integer. We give an algorithm deciding whether
$$
r_{\mathrm{FR}}(\mu,t)\leq h
$$
and returning a center when one exists.
Compute a feasible ranking $\rho_0$ by minimizing expected footrule distance.
Any center $\eta$ of radius at most $h$ must satisfy
$$
d_{\mathrm{FR}}(\eta,\rho_0)\leq h.
$$
Therefore at most $h$ alternatives can change position: each changed position contributes at least one to the distance.
Choose the changed alternatives and permute them among their original positions, fixing all other alternatives. This enumerates every possible center in the ball. The number of candidates is at most
$$
\sum_{k=0}^{\min(h,m)}\binom mk k!
\leq(h+1)m^h.
$$
Discard candidates whose actual distance from $\rho_0$ exceeds $h$.
Fix a candidate $\eta$. A feasible ranking $\rho$ violates its radius bound exactly when
$$
\sum_a|p_\eta(a)-p_\rho(a)|>h.
$$
If this occurs, select alternatives with positive contributions until their accumulated contribution first exceeds $h$. Since the contributions are positive integers, at most $h+1$ alternatives are selected.
Accordingly, enumerate all injective partial assignments
$$
a\longmapsto j_a
$$
on at most $h+1$ alternatives whose contributions satisfy
$$
\sum_a|p_\eta(a)-j_a|>h.
$$
For each, minimize expected footrule distance subject to the specified positions, using a residual assignment problem.
If some constrained optimum is feasible, it supplies a violating ranking. Conversely, every violating ranking supplies one of the enumerated partial assignments. Thus these tests are complete.
There are at most
$$
(h+2)m^{2(h+1)}
$$
partial assignments, each requiring $O(m^3)$ arithmetic operations. A conservative total bound is
$$
O\!\left(
L^3+
\left[
\tau m^2+(h+2)^2m^{3h+5}
\right]B^2
\right).
$$
For a given integer $R$, run this procedure for $h=0,\ldots,R$ and stop at the first success. If the optimum is at most $R$, this returns its exact radius and a minimizing ranking. Otherwise it certifies that the optimum exceeds $R$. A bound is
$$
O\!\left(
L^3+
\left[
\tau m^2+(R+2)^3m^{3R+5}
\right]B^2
\right).
$$
One can skip odd radii because footrule distances are even.
This establishes polynomial-time exact computation for every fixed radius bound. It does not establish polynomial time when the radius varies with the input.
Suppose $\tau=1$, with supported ranking $\sigma$ of mass one. Then
$$
G_d(\mu,t)=\{\rho:d(\sigma,\rho)\leq t\}.
$$
We use a finite metric-space observation.
Suppose a finite integer-valued metric space is homogeneous: for any two points, an isometry maps one to the other. Ball cardinalities then depend only on radius.
Let
$$
R=\max\{d(\sigma,\rho):d(\sigma,\rho)\leq t\}.
$$
The feasible set is the ball $B_d(\sigma,R)$, and $\sigma$ has radius $R$ over this set.
If another center had radius less than $R$, integrality would imply
$$
B_d(\sigma,R)\subseteq B_d(\eta,R-1).
$$
Homogeneity gives
$$
|B_d(\eta,R-1)|=|B_d(\sigma,R-1)|.
$$
But a point at distance exactly $R$ exists, so
$$
|B_d(\sigma,R-1)|<|B_d(\sigma,R)|,
$$
contradicting the containment. Thus $\sigma$ is an optimal center with radius $R$. The case $R=0$ is immediate.
All four ranking metrics are homogeneous under relabeling alternatives. Relabeling preserves pair disagreements, positional displacement sums and maxima, and transposition distances. Any ranking can be mapped to any other by such a relabeling.
It remains to determine the attainable distances.
For Kendall tau, every integer from zero to $\binom m2$ occurs. A sequence of adjacent swaps that reverses the base order can increase its inversion count by one at each step.
For maximum displacement, every integer $k$ from zero to $m-1$ occurs by swapping positions $1$ and $k+1$.
For Cayley distance, every integer $k$ from zero to $m-1$ occurs using a cycle of length $k+1$, leaving other alternatives fixed.
For footrule, the attainable distances are precisely
$$
0,2,\ldots,2\left\lfloor\frac{m^2}{4}\right\rfloor.
$$
Parity was proved in Section 9.
For the upper bound, let $c_j$ count alternatives lying before cut $j$ in the base ranking and after it in the other ranking. The same number cross in the opposite direction. Counting all crossings gives
$$
d_{\mathrm{FR}}(\sigma,\rho)
=
2\sum_{j=1}^{m-1}c_j
\leq
2\sum_{j=1}^{m-1}\min(j,m-j)
=
2\left\lfloor\frac{m^2}{4}\right\rfloor.
$$
Reversal attains equality.
To prove that every even value in this interval occurs, let
$$
f(m)=\left\lfloor\frac{m^2}{4}\right\rfloor.
$$
Inductively, fixing the first alternative realizes every half-distance in $[0,f(m-1)]$. Swapping the first and last alternatives, then permuting the interior, realizes every half-distance in
$$
[m-1,m-1+f(m-2)].
$$
The upper endpoint is $f(m)$. For $m\geq3$,
$$
f(m-1)\geq m-2,
$$
so the intervals overlap or are adjacent. The cases $m=1,2$ are immediate. This completes the induction.
The supported ranking $\sigma$ is an optimal center, with radius
| Metric | Radius for $\tau=1$ |
|---|---|
| Kendall tau | $\min\{\lfloor t\rfloor,\binom m2\}$ |
| Maximum displacement | $\min\{\lfloor t\rfloor,m-1\}$ |
| Cayley | $\min\{\lfloor t\rfloor,m-1\}$ |
| Footrule | $2\min\{\lfloor t/2\rfloor,\lfloor m^2/4\rfloor\}$ |
These values and the supported ranking can be returned in $O(B^3)$ bit operations.
For each alternative, define its feasible positional extremes
$$
\ell_a=\min_{\rho\in G_{\mathrm{MD}}(\mu,t)}p_\rho(a),
\qquad
u_a=\max_{\rho\in G_{\mathrm{MD}}(\mu,t)}p_\rho(a).
$$
Nonemptiness ensures that these are defined.
For every center $\eta$,
$$
\max_{\rho\in G_{\mathrm{MD}}(\mu,t)}d_{\mathrm{MD}}(\eta,\rho)
=
\max_a\max\{p_\eta(a)-\ell_a,\ u_a-p_\eta(a)\}.
$$
The maxima over alternatives and feasible rankings commute because both sets are finite; for a fixed alternative, maximum absolute displacement occurs at an extreme feasible position.
Hence a center of radius at most $r$ exists exactly when the bipartite graph with edges
$$
(a,j)\quad\text{such that}\quad
u_a-r\leq j\leq\ell_a+r
$$
has a perfect matching. Binary search over integer radii $0,\ldots,m-1$ finds the exact radius and a matching supplies the center.
To compute the extremes, enumerate
$$
k\in\{0,\ldots,m-1\}^{\tau}
$$
and retain those satisfying
$$
\sum_{\sigma\in S}\mu_\sigma k_\sigma\leq t.
$$
For each retained vector, create the bipartite graph with edges satisfying
$$
|p_\sigma(a)-j|\leq k_\sigma
\quad\text{for every }\sigma\in S.
$$
Every perfect matching in this graph is feasible. Conversely, every feasible ranking occurs in such a graph by choosing its actual distance vector.
Test whether each edge belongs to a perfect matching by fixing it and matching the remaining vertices. The positions appearing in any successful test determine $\ell_a,u_a$.
There are $m^\tau$ vectors, at most $m^2$ fixed-edge tests per graph, and $O(m^3)$ arithmetic operations per matching test. A conservative bound is
$$
O\!\left(
L^3+
\left[
m^\tau(\tau m^2+m^5)
+
m^3\log(m+1)
\right]B^2
\right).
$$
Thus the exact computation takes
$$
m^{\tau+O(1)}\operatorname{poly}(\tau,L)
$$
time, and is polynomial for every fixed support size.
All four metrics admit exhaustive exact computation.
Enumerate the $m!$ rankings and retain those whose expected distance is at most $t$, using exact rational arithmetic. Then enumerate every possible center and evaluate its largest distance to the retained rankings. Select a center with minimum such value.
Distances are integers, so this returns the exact integer radius. A conservative bit-operation bound is
$$
O\!\left(
L^3+
\left[
m!\,\tau+(m!)^2
\right]m^2B^2
\right).
$$
The reductions establish the three hardness classifications with polynomial support sizes, positive masses and thresholds, and guaranteed nonempty feasible sets. They do not establish hardness for a fixed support size.
For footrule, the results above settle singleton recognition, fixed-radius computation, and one-type societies, and give an exact representation of arbitrary assignment budget sets. They do not settle whether the unrestricted promised exact minimax computation is polynomial-time solvable or $\mathrm{NP}$-hard.
In particular, hardness of center computation for an explicitly listed collection of rankings would require an additional reduction showing how the relevant collection can be realized as an assignment budget set. Section 8 alone does not provide that reduction.
⟨structured verdict parsed — rendered above⟩
The output establishes $\mathrm{NP}$-hardness for Kendall tau, maximum displacement, and Cayley distance. The reductions preserve the nonemptiness promise, use positive thresholds, and have polynomial encoding length. The additional footrule results are also sound.
However, the four-metric task remains only partially resolved: unrestricted exact computation for footrule is explicitly left open. I found no central false step. There is one minor notation issue in the Cayley calculation.
The definitions agree with USER_TASK, including unnormalized Kendall tau and the stated maximum displacement metric. The output correctly treats $\tau$ as the number of supported rankings and combines duplicate types where necessary.
The rational arithmetic discussion is adequate. Multiplying input denominators produces a common denominator with polynomial binary length. Scaling feasibility comparisons to integers therefore permits exact polynomial-time arithmetic. The conservative arithmetic bounds are sufficient for the algorithms described.
The case $m=1$ is handled correctly. The separate dyadic constructions also address the stricter possible interpretation of “binary-rational.”
Section 2 is correct.
With $K=D+1$, an integer strict improvement saves at least $K$ in the original weighted objective, while the added baseline-distance term costs at most $D$. Thus every strict improvement satisfies the new threshold.
Conversely, a distinct ranking with original score at least the baseline score exceeds the threshold because its distance from the baseline is positive. Consequently, the asserted identity
$$
G_d(\mu,t)=\{\eta_0\}\cup\{\rho:C(\rho)<C(\eta_0)\}
$$
is justified.
The baseline supplies a known feasible ranking. The hypothesis $C_0>0$ ensures that the threshold is positive. The singleton characterization of zero radius is valid because the center must have distance zero from every feasible ranking.
The dyadic implementation is also correct:
The required precision has polynomial binary length. Hence this reduction supports both rational and dyadic input interpretations.
The cited theorem is accurately stated and applicable. The paper defines Kemeny consensus using the sum of Kendall tau distances over voters’ strict total orders, and its Theorem 5 establishes $\mathrm{coNP}$-completeness of consensus recognition under the stated reduction convention. [Fitzsimmons and Hemaspaandra, *Kemeny Consensus Complexity*](https://www.ijcai.org/proceedings/2021/0028.pdf)
Taking complements gives the required $\mathrm{NP}$-complete strict-improvement problem. Combining identical votes into positive integer multiplicities preserves the objective.
The zero-score branch correctly maps to a promised singleton instance: on two alternatives, the other ranking has Kendall distance one and is excluded by threshold $1/2$. Otherwise, Section 2 applies with diameter $\binom m2$.
Finding: Kendall tau hardness is established. Positive-radius recognition has the claimed polynomial certificates on promised inputs.
Both gate penalties have the stated behavior. The AND penalty is nonnegative and vanishes precisely on consistent Boolean gate assignments. The NOT penalty has the same property for negation.
The baseline is explicitly constructible and has objective zero. The three selector cases exhaust all possibilities. Since $P$ is a nonnegative integer, positivity in the final case requires $P=0$. This gives exactly the stated satisfiability equivalence.
The negative-monomial identities are correct. After simplifying repeated Boolean variables, the resulting indicators specify at most two distinct bits. All reward weights are positive integers, and the objective differs from the quadratic objective only by a constant.
The baseline and strict-improvement equivalence are preserved. The transformation has polynomial size.
The conversion to a signed cut objective is algebraically correct. The reference vertex encodes all Boolean assignments, up to the irrelevant simultaneous reversal of cut sides.
Each negative-edge gadget has the stated optimal contribution for fixed endpoint sides. The internal vertices are independent, and the baseline optimizes their placements. The argument handles arbitrary improved cuts correctly: their optimal extensions cannot have smaller value.
Finding: Both auxiliary strict-improvement hardness results are established.
The construction is internally consistent.
The six-position variable blocks accommodate all specified local moves. The extra blocks accommodate displacements of two positions in either direction. Within a guard triple, the extra distinguished alternatives ensure pairwise maximum displacement four.
The triangle inequalities imply a total distance of at least six. Equality forces all three distances to equal two. Canonical rankings attain those equalities.
The paired guards constrain both distinguished alternatives in each variable block to the two designated positions. Distinctness then encodes a Boolean value. The guards on $z$ force its base position. The proof correctly avoids claiming that the fillers are fixed.
For a canonical ranking, each pattern distance is exactly two when all requirements match and three otherwise. For an arbitrary guard-equality ranking, the distinguished alternatives supply the asserted lower bound regardless of filler placement.
The separation weight $H=3Q+1$ suffices. Any failed guard equality adds at least $H$, which exceeds the entire upper bound $3Q$ on the canonical pattern contribution. For guard-equality rankings, the reward comparison yields the claimed strict-improvement equivalence.
The construction has polynomial support and encoding length, and its baseline score is positive.
Finding: Maximum displacement hardness is established.
The cycle-count formula and its applicability to arbitrary transpositions are correct. The asserted invariance under left and right multiplication is valid.
The anchor argument is sound. Under equality, the concatenated shortest path has exactly $N$ transpositions and decreases the cycle count by $N$. Every step must therefore merge cycles. Since cycle partitions cannot subsequently separate, no step can join different final pairs. This forces the intermediate ranking to be canonical.
The four-alternative edge calculation gives local distances $3,2,2,3$. The subsequent accounting of selected pairs outside the edge and complementary pairs gives the stated combined contribution
$$
N+4-2\mathbf1[x_i\neq x_j].
$$
The separation weight excludes every noncanonical ranking from improving a canonical baseline. Canonical improvement is precisely cut improvement. Polynomial size and positive baseline score are justified.
Minor issue: The table in Section 6.2 displays $d_{\mathrm{CY}}(\eta(x),q_e)$, although its entries are only the contribution on the four edge alternatives. Full distance also depends on selected pairs outside the edge. The introductory phrase and subsequent paragraph make the intended reading clear, so this does not invalidate the reduction.
Minimum clarification: Label the table entries explicitly as restricted four-alternative distances or local contributions.
Finding: Cayley hardness is established, subject to this minor notation clarification.
The expected footrule objective is correctly expressed as a linear assignment cost.
The minimum-cost ranking is feasible by the promise. Every distinct feasible ranking changes at least one alternative’s position, so the fixed-edge assignment tests detect exactly whether a second feasible ranking exists.
The same reasoning correctly characterizes all feasible positional choices. The number of assignment problems and the conservative bit-operation bound are consistent with the described algorithm.
Finding: Polynomial-time zero-radius recognition is established. The conclusion about the limitations of the positive-radius reduction follows.
The matrix normalization is correct. Column subtraction changes every permutation cost by the same constant, and the additional row constants have total zero.
The constructed positional marginals have positive entries. Their row sums telescope to one, and the zero column sums of the perturbation give column sums one.
The reconstruction of each expected absolute-position cost is justified by matching successive differences and endpoint sums. The constructive permutation decomposition satisfies Hall’s condition and terminates after at most $m^2$ subtractions. Its common-denominator argument gives polynomial arithmetic length.
The expected-distance formula, including $(m^2-1)/3$, is correct. The threshold is positive because an assumed feasible assignment exists and every ranking has positive expected distance under the constructed positive marginals.
The dyadic version correctly introduces a half-unit budget margin before rounding. Both objective and threshold perturbations remain below that margin, preserving every feasibility decision.
Finding: The assignment-budget representation theorem is established. As the output acknowledges, it does not itself establish minimax hardness.
Both proposed sets are correctly realized as assignment-budget sets.
For $G_1$, the base ranking gives radius at most two. Footrule distances are even, and the feasible set is not a singleton, so its radius is exactly two.
For $G_2$, the stated uncrossing inequality is correct. Sorting block inversions cannot increase distance to any canonical ranking. Every resulting canonical center has its complementary ranking in $G_2$ at distance $2n$.
Finding: The radii are correctly computed, and feasible positional choices alone do not determine the footrule radius.
Every admissible center lies within distance $h$ of the computed feasible ranking. The candidate enumeration covers all such centers, and its cardinality bound is valid.
A violating ranking has a witness consisting of at most $h+1$ positive displacement contributions. Enumerating injective partial assignments and solving constrained assignment problems therefore detects every violation and introduces no false violations.
The operation counts support the displayed bounds. Searching successive integer radii returns the exact optimum whenever it is at most the supplied bound.
Finding: The fixed-radius result is established. Its dependence on the radius does not yield a polynomial-time algorithm for unrestricted inputs.
The homogeneous-ball argument is valid, including its treatment of radius zero. Relabeling alternatives provides the required homogeneity for all four metrics.
The attainable-distance claims are correct. For footrule, parity, the cut-crossing upper bound, reversal attaining the bound, and the induction covering every intermediate even distance are all justified. The small cases and interval endpoints are handled correctly.
Finding: All four single-support formulas and their polynomial-time computation are established.
The exchange of finite maxima is valid, so feasible positional extremes determine the objective for any center.
The perfect-matching criterion exactly expresses the allowed center positions for a proposed radius. Enumerating distance-bound vectors covers every feasible ranking and admits only feasible rankings. Fixed-edge matching tests recover precisely the positions needed for the extremes.
The stated running time is conservative and polynomial for each fixed $\tau$.
Finding: This additional algorithm is established and is consistent with hardness when support size varies.
The exhaustive algorithm computes both requested outputs exactly. Its conservative running-time bound accommodates feasibility checks and all center–ground-truth comparisons.
The substantive remaining issue is scope: USER_TASK requests a polynomial-time or hardness classification for each metric. The footrule results do not supply either classification for unrestricted promised inputs.
This is an explicitly acknowledged unresolved target, rather than a false claim of completion. Resolving it requires an additional argument; expositional clarification alone cannot complete the assignment.
⟨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.