Manhattan preferences need only min(n, m-1) dimensions

A new paper by Jiehua Chen, Martin Nöllenburg, Sofia Simola, Anaïs Villedieu, and Markus Wallinger, submitted to arXiv, tackles the geometry of collective decision-making. The authors study d-Manhattan preferences, where voters and alternatives can be placed in a d-dimensional space so that each voter prefers alternatives closer by Manhattan distance. They provide explicit constructions proving that any preference profile is d-Manhattan whenever d ≥ min(n, m-1), where n is voters and m is alternatives. This bound is tight and also holds for other p-norms, including Euclidean.

The team then dives into the 2D case, developing forbidden substructures that prevent a 2-Manhattan embedding. They discover the smallest counterexamples: either 3 voters and 6 alternatives, 4 voters and 5 alternatives, or 5 voters and 4 alternatives—more complex than the analogous 2-Euclidean case. They also show that d-Manhattan preferences imply (2d-1)-dimensional single-peakedness, but 2-Manhattan is incomparable with standard single-peakedness or single-crossingness. These results advance theoretical understanding of preference representation and have implications for multiagent systems, voting theory, and spatial models of opinion dynamics.