Hardness of Consistent Low-Dimensional Approximation for Ranking Prediction

We initiate a property elicitation-informed study of ranking prediction over $n$ items, framing the prediction task as estimating a property of an underlying distribution over the $n!$ rankings. We identify a natural, well-motivated target property -- the pairwise-distance property -- and show that a popular $n$-dimensional surrogate loss, the permutahedron loss, cannot achieve consistency with respect to this target. Instead, a different surrogate loss, the $\binom{n}{2}$-dimensional Kendall-Tau loss, is consistent with respect to the pairwise-distance property, and furthermore achieves the lower bound of the convex calibration dimension needed to satisfy this property. Because the Kendall-Tau loss is difficult to optimize, we give conditions under which the permutahedron loss achieves exact and approximate consistency with the pairwise-distance property.