Ordinal Reconstruction and Optimal Matching on the Line

This direction is merged into another direction: ordinal-cardinal information gap. Its last version stays readable and citable here.

Version 1 of 18 papers15 conceptsfrozen 2026-10-04

In many optimization problems, we assume we need precise "cardinal" data—exact distances, costs, or coordinates—to find an optimal solution. However, a growing body of research suggests that when agents and candidates are arranged on a one-dimensional line, the underlying geometry is so rigid that simple "ordinal" information (who is closer to whom) is often enough to achieve perfect or near-perfect results.

This phenomenon, often explored through the lens of metric distortion, reveals a fundamental "dimensionality gap": problems that are computationally hard or mathematically imprecise in 2D or 3D become elegantly solvable on the line.

The Monotonicity Principle

The core intuition behind 1D optimality starts with matching. Suppose you have two sets of points on a line and want to pair them to minimize the total distance between pairs. If the cost of matching two points is a convex function of the distance between them, the optimal solution is surprisingly simple: sort both sets and match them in order.

Sergio Caracciolo and Gabriele Sicuro have shown that this "monotonic assignment" strategy reduces complex combinatorial searches to a basic sorting task. In One-dimensional Euclidean matching problem: Exact solutions, correlation functions, and universality, they demonstrate that the total cost of such a matching can be mapped to the properties of a Brownian bridge. By treating the discrete points as fluctuations in a continuous stochastic process, Caracciolo, Sicuro, and Matteo d'Achille derived exact scaling laws for these costs in Random Euclidean matching problems in one dimension.

The takeaway is that in 1D, the relative spatial ordering (the "rank") is a perfect proxy for the optimal global structure.

Reconstructing Geometry from Rankings

If the optimal solution depends on the linear order, can we find that order if we don't have coordinates? In social choice theory, we often only have "ordinal preferences"—voters ranking candidates from favorite to least favorite.

On a line (representing, for example, a political spectrum), these rankings contain hidden geometric signals. Negar Babashah and colleagues in Distortion of Multi-Winner Elections on the Line Metric: The Polar Comparison Rule show that by filtering out "Pareto-dominated" candidates—those who are further away from every single voter than some other candidate—one can uniquely reconstruct the linear ordering of the remaining candidates.

Once this order is recovered, the "Polar Comparison Rule" can strategically pick candidates from the extremes and the median to minimize the "distortion"—the gap between the chosen winner and the mathematically ideal winner.

The Power of Two Winners

The most striking evidence of the line's unique properties comes from the study of "bi-criteria" distortion. In general metric spaces, picking a single winner based only on rankings leads to a "distortion of 3," meaning the chosen winner might be three times worse than the ideal one.

However, Kiarash Banihashem, Diptarka Chakraborty, and their co-authors discovered a dramatic shortcut on the line. In Bi-Criteria Metric Distortion, they prove that while a single winner always carries some "price of ignorance," selecting a committee of just two candidates can achieve a distortion of 1. This means that with only ordinal rankings, you can pick two people who, together, perfectly match the performance of the best possible cardinal winner.

This "distortion of 1" is a unique feature of the line. As Banihashem and Chakraborty note in their 2024 work, achieving this same optimality in 2D or on tree-like networks would require selecting almost every available candidate.

Perfect Matching without Distances

This principle extends beyond voting to two-sided matching (e.g., matching workers to jobs). In Optimal Metric Distortion for Matching on the Line, Aris Filos-Ratsikas, Vasilis Gkatzelis, and their team show that if agents on both sides of a market are on a line, their ordinal preferences provide enough information to identify the exact optimal cardinal matching.

By using a greedy left-to-right pairing strategy after reconstructing the relative positions, they achieve a distortion factor of exactly one. This confirms that for 1D topologies, qualitative preferences are just as powerful as quantitative distance measurements. The line is "rigid" enough that if you know who everyone prefers, you effectively know where everyone stands.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_ordinal_reconstruction_and_optimal_match_8798aab8,
  title = {Ordinal Reconstruction and Optimal Matching on the Line},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/ordinal-reconstruction-and-optimal-matching-on-the-line/rdr_8798aab80d284827a523c92562b5da85},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_ordinal_reconstruction_and_optimal_match_8798aab8_v1,
  title = {Ordinal Reconstruction and Optimal Matching on the Line},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/ordinal-reconstruction-and-optimal-matching-on-the-line/rdr_8798aab80d284827a523c92562b5da85/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}