Multidimensional Manhattan Preferences

A preference profile (i.e., a collection of linear preference orders of the voters over a set of alternatives) with $m$ alternatives and $n$ voters is $d$-Manhattan (resp. $d$-Euclidean) if both the alternatives and the voters can be placed into a $d$-dimensional space such that between each pair of alternatives, every voter prefers the one which has a shorter Manhattan (resp. Euclidean) distance to the voter. We study how $d$-Manhattan preference profiles depend on the values $m$ and $n$. First, we provide explicit constructions to show that each preference profile with $m$ alternatives and $n$ voters is $d$-Manhattan whenever $d \ge \min(n, m - 1)$. We further extend this positive result for other $p$-norms with $p \in R_{\ge 1} \cup \{\infty\}$. Second, for $d = 2$, we develop forbidden substructures-preference patterns among small sets of voters that constrain any 2-Manhattan embedding -- and use them to show that the smallest non-2-Manhattan preference profile has either 3 voters and 6 alternatives, or 4 voters and 5 alternatives, or 5 voters and 4 alternatives. This is more complex than the case with $d$-Euclidean preferences (see (Bogomolnaia and Laslier, 2007) and (Bulteau and Chen, 2022)). We also show that $d$-Manhattan preferences imply $(2d-1)$-dimensional single-peakedness, while 2-Manhattanness is incomparable with single-peakedness and single-crossingness.