Proof. Let \({\cal P}=({\cal A}, {\cal V}, (\succ_i)_{i\in [n]})\) be a profile with \(m\) alternatives \({\cal A}=[m]\) and \(n\) voters \({\cal V}\).

Conceptually, the proof is similar to that of [7]. By embedding the voters correctly, we can find \(m\) spheres of increasing sizes around each alternative so that all of these spheres intersect with all the spheres of the other voters. These intersection points correspond to different combinations of voter ranks for alternatives. See 1 and 5 for an example: The smallest blue solid circle corresponds to alternatives for which \(v_1\) has rank \(0\), the second smallest blue circle to alternatives for which \(v_1\) has rank \(1\) and so on. Similarly, the smallest red dashed circle corresponds to alternatives for which \(v_2\) has rank \(0\), the second smallest red circle to alternatives for which \(v_1\) has rank \(1\) and so on. Consider for example the alternative 1, which in this example satisfies \(\mathsf{rk}_{1}(1) = 0\) and \(\mathsf{rk}_{2}(1) = 2\). Hence it is placed in the intersection of the blue circle closest to \(v_1\) and the red circle third closest to \(v_2\).

Now let us describe our formal construction. First we embed the \(n\) voters in \(n - 1\) dimensions so that for every voter \(v_i \in {\cal V}\), the first \(i - 1\) coordinates are \(m\), the coordinates from \(i\) to \(n - 1\) are \(-m\) and the last coordinate is \(0\). More formally, for every \(v_i \in {\cal V}\): \[E(v_i)[z] \mathrel{\vcenter{:}}= \begin{cases} m, &\text{ if } z \leq i - 1,\\ -m, &\text{ if } i \leq z \leq n -1, \\ 0, &\text{ if }z = n. \end{cases}\]

We embed the alternatives in the following points: \[E(j)[z] \mathrel{\vcenter{:}}= \begin{cases} \mathsf{rk}_z(j) - \mathsf{rk}_{z+1}(j), &\text{ if } z \neq n,\\ \mathsf{rk}_1(j) + \mathsf{rk}_n(j), &\text{ if } z = n. \end{cases}\] These are the intersections of the spheres of radius \(m(n - 1) + 2 \mathsf{rk}_i(j)\) around \(E(v_i)\), \(v_i \in {\cal V}\). We can show this by computing the distance \(\|E(v_i) - E(j) \|_1\) for every \(v_i \in {\cal V}, j \in {\cal A}\): \[\begin{align} \|E(v_i) - E(j) \|_1 &= \sum_{z =1}^n|E(v_i)[z] - E(j)[z]| \tag{2}\\ & = \sum_{z = 1}^{i - 1}|m - (\mathsf{rk}_z(j) - \mathsf{rk}_{z+1}(j))| + \sum_{z = i}^{n - 1}|- m - (\mathsf{rk}_z(j) - \mathsf{rk}_{z+1}(j))| + |0 - (\mathsf{rk}_1(j) + \mathsf{rk}_n(j))| \tag{3}\\ & = \left( \sum_{z = 1}^{i - 1}m - \mathsf{rk}_z(j) + \mathsf{rk}_{z+1}(j) \right) + \left(\sum_{z = i}^{n - 1} m + \mathsf{rk}_z(j) - \mathsf{rk}_{z+1}(j)\right) + \mathsf{rk}_1(j) + \mathsf{rk}_n(j) \tag{4}\\ & = (n - 1) m + \left( \sum_{z = 1}^{i - 1}-\mathsf{rk}_z(j) + \mathsf{rk}_{z+1}(j)\right) + \left(\sum_{z = i}^{n - 1} \mathsf{rk}_z(j) - \mathsf{rk}_{z+1}(j)\right) + \mathsf{rk}_1(j) + \mathsf{rk}_n(j) \tag{5}\\ &= (n - 1)m + 2 \mathsf{rk}_i(j).\tag{6} \end{align}\]

For Step 6 , observe that if \(2 \leq i \leq n - 1\), then the terms in the first sum cancel each other so that in the end we have \(-\mathsf{rk}_1(j) + \mathsf{rk}_i(j)\). Similarly, the second sum simplifies to the form \(\mathsf{rk}_i(j) - \mathsf{rk}_n(j)\). Since \(m(n - 1) + 2 \mathsf{rk}_i(j)\) is linear in the ranks, this proves the statement. This clearly holds even if preferences may contain indifferences. ◻

Proof. We may assume that \(m \geq 2\), because otherwise we have one alternative and the profile can trivially be embedded in a point.

Let \({\cal P}=({\cal A}, {\cal V}, (\succ_i)_{i\in [n]})\) be a profile with \(m \geq 2\) alternatives \({\cal A}=[m]\) and \(n\) voters \({\cal V}\). The idea is to place every alternative except \(m\) on its own axis. Then it is straightforward to choose the placement of a voter so that any possible preference order of the first \(m - 1\) is embedded: As the alternatives are on their own axes, we can move closer to one alternative without changing how close we are to a different alternative. Finally, we embed \(m\) to the origin. By choosing how far an alternative is from the origin, we can respect the voter’s preferences regarding \(m\).

More precisely, define an embedding \(E\colon {\cal A}\cup {\cal V}\to \mathbb{N}_0\) such that alternative \(m\) is embedded in the origin coordinate, i.e., \(E(m)[z]=0\) for all \(z\in [m - 1]\). For each alternative \(j\in [m - 1]\) and each coordinate \(z\in [m - 1]\), we have \(E(j)[z]\mathrel{\vcenter{:}}= 2m\) if \(z=j\), and \(E(j)[z]\mathrel{\vcenter{:}}= 0\) otherwise.

Then, the embedding of each voter \(v_i\in {\cal V}\) is defined as follows: \(\forall~z\in [m - 1]\colon\) \[\begin{align} E(v_i)[z] & \mathrel{\vcenter{:}}= \begin{cases} 2m - \mathsf{rk}_i(z), & \text{ if } \mathsf{rk}_i(z) < \mathsf{rk}_i(m),\\ m -\mathsf{rk}_i(z), & \text{ if } \mathsf{rk}_i(z) > \mathsf{rk}_i(m). \end{cases} \end{align}\] Observe that \(0\le E(v_i)[j] \le 2m\). Before we show that \(E\) is -Manhattan for \({\cal P}\), let us establish a simple formula for the distance between a voter and an alternative.

Now, we proceed with the proof. Consider an arbitrary voter \(v_i\in {\cal V}\) and let \(j,k\in [m]\) be two consecutive alternatives in the preference order \(\succ_i\) such that \(\mathsf{rk}_i(j) = \mathsf{rk}_i(k)-1\).

It is clear from [clm:m-Manhattan] and the voter embedding that if \(j \succ_i k \succ_i m\) or \(m \succ_i j \succ_i k\), then \(\|E(v_i) - E(j) \|_1 < \|E(v_i) - E(k) \|_1\). It remains to consider the cases when \(m \in \{j,k\}\).

Case 1:

\(k=m\) and thus \(E(v_i)[j]=2m-\mathsf{rk}_i(j)\). Then, by [clm:m-Manhattan] and by definition, it follows that \[\begin{align} \|E(v_i)-E(j) \|_1 &- \|E(v_i)-E(k) \|_1 = 2(m - E(v_i)[j]) =2\mathsf{rk}_i(j) - 2m < 0. \end{align}\] Note that the last inequality holds since \(\mathsf{rk}_i(j)=\mathsf{rk}_i(k)-1 < m\).

Case 2:

\(j=m\) and thus \(E(v_i)[k]=m-\mathsf{rk}_i(k)\). Then, by [clm:m-Manhattan] and by definition, it follows that \[\begin{align} \|E(v_i)-E(j) \|_1 &- \|E(v_i)-E(k) \|_1 = -2(m - E(v_i)[k]) = - 2\mathsf{rk}_i(k) < 0. \end{align}\]

Since in all cases, we show that \(\|E(v_i)-E(j) \|_1 - \|E(v_i)-E(k) \|_1 < 0\), embedding \(E\) is indeed -Manhattan for \({\cal P}\). ◻

Proof. Let \({\cal P}\), \(E\), \(r,s\), and \(x,y\) be as defined. Both statements follow from using simple calculations and the triangle inequality of Manhattan distances. The idea is also illustrated in 8.

For Statement [lem:not-inside], suppose, towards a contradiction, that \(r,s\colon y \succ x\) and \(\boldsymbol{x}\in \mathsf{BB}(\boldsymbol{r}, \boldsymbol{s})\). By the definition of Manhattan distances, this implies that \[\begin{align} \|\boldsymbol{r}-\boldsymbol{x} \|_1+\|\boldsymbol{x}-\boldsymbol{s} \|_1 = \|\boldsymbol{r}-\boldsymbol{s} \|_1.\label{eq-lemma1-1} \end{align}\tag{7}\] By the preferences of voters \(r\) and \(s\) we infer that \(\|\boldsymbol{r}-\boldsymbol{y} \|_1+\|\boldsymbol{s}-\boldsymbol{y} \|_1 < \|\boldsymbol{r}-\boldsymbol{x} \|_1+\|\boldsymbol{s}-\boldsymbol{x} \|_1 \stackrel{\eqref{eq-lemma1-1}}{=} \|\boldsymbol{r}-\boldsymbol{s} \|_1,\) a contradiction to the triangle inequality of \(\|\cdot \|_1\).

For Statement [lem:not-outside-corner], suppose, towards a contradiction, that \(r\colon x \succ y\) and \(s\colon y\succ x\) and \(\boldsymbol{s}\in \mathsf{BB}(\boldsymbol{r}, \boldsymbol{x})\). By the definition of Manhattan distances, this implies that \[\begin{align} \|\boldsymbol{r}-\boldsymbol{x} \|_1=\|\boldsymbol{r}-\boldsymbol{s} \|_1 + \|\boldsymbol{s}-\boldsymbol{x} \|_1.\label{eq-lemma1-2} \end{align}\tag{8}\] By the preferences of voters \(r\) and \(s\) we infer that \[\begin{align} \|\boldsymbol{r}-\boldsymbol{s} \|_1+\|\boldsymbol{s}-\boldsymbol{y} \|_1 < \|\boldsymbol{r}-\boldsymbol{s} \|_1+\|\boldsymbol{s}-\boldsymbol{x} \|_1 \stackrel{\eqref{eq-lemma1-2}}{=} \|\boldsymbol{r}-\boldsymbol{x} \|_1 < \|\boldsymbol{r}-\boldsymbol{y} \|_1, \end{align}\] a contradiction to the triangle inequality of \(\|\cdot \|_1\).  ◻

Proof. All proofs are straightforward by evoking the definition of Manhattan embedding. Hence, we only showcase how to prove the first statement. Let \({\cal P},E,s,x,y\) be as defined. Assume that \(\boldsymbol{y}\in \mathsf{NE}(\boldsymbol{s})\). Then, by the Manhattan property and the fact that \(s\colon x\succy\), it follows that \[\begin{align} (\boldsymbol{y}[1]-\boldsymbol{s}[1])+(\boldsymbol{y}[2]-\boldsymbol{s}[2]) & = \|\boldsymbol{y}-\boldsymbol{s} \|_1 > \|\boldsymbol{x}-\boldsymbol{s} \|_1 = | \boldsymbol{x}[1]-\boldsymbol{s}[1]| + | \boldsymbol{x}[2]-\boldsymbol{s}[2]| \\ &\ge (\boldsymbol{x}[1]-\boldsymbol{s}[1]) + (\boldsymbol{x}[2]-\boldsymbol{s}[2])\\ \Rightarrow \boldsymbol{y}[1] + \boldsymbol{y}[2] & > \boldsymbol{x}[1]+\boldsymbol{x}[2], \end{align}\] as desired.  ◻

Proof. Let \({\cal P},E,r,s,t,x,y\) be as defined. The first statement follows directly from applying 1. Hence, we only prove the case with \(\Pi=\mathsf{NW}\). For a contradiction, suppose that \(\boldsymbol{x}\in \mathsf{NW}(\boldsymbol{s})\) and \(\boldsymbol{y}\in \mathsf{NW}(\boldsymbol{r})\). Since \(r\colon x\succy\) and \(\boldsymbol{y}\in \mathsf{NW}(\boldsymbol{r})\), by 1[obs:pref-NW] we have that \(\boldsymbol{y}[2]-\boldsymbol{y}[1] > \boldsymbol{x}[2]-\boldsymbol{x}[1]\). Since \(s \colon y \succx\) and \(\boldsymbol{x}\in \mathsf{NW}(\boldsymbol{s})\), by 1[obs:pref-NW] we have that \(\boldsymbol{x}[2]-\boldsymbol{x}[1] > \boldsymbol{y}[2]-\boldsymbol{y}[1]\). However, these two statements contradict each other.

Statement [lem:Ntogether2]: We only show the case with \(\Pi=\mathsf{NW}\) as the other case is symmetric. For a contradiction, suppose that \(\boldsymbol{x}, \boldsymbol{y}\in \mathsf{NW}(\boldsymbol{s})\). Since \(r,t\colon x \succ y\), \(s\colon y \succ x\), \(\boldsymbol{x}\in \mathsf{NW}(\boldsymbol{s})\), by the first statement, we have \(\boldsymbol{y}\notin \mathsf{NW}(\boldsymbol{r})\cup \mathsf{NW}(\boldsymbol{t})\). However, since \(\boldsymbol{y}\in \mathsf{NW}(\boldsymbol{s})\), it follows that \(\boldsymbol{y}\in \mathsf{BB}(\boldsymbol{r},\boldsymbol{t})\), a contradiction to 1[lem:not-inside].  ◻

Proof. Suppose, towards a contradiction, that \({\cal P}\) is a profile which contains a \((v,u,w)\)-BE-configuration and admits a -Manhattan embedding \(E\), such that \(E\) satisfies the \((v,u,w)\)-BE-property, for \(3\) voters \(u,v,w\). Let \(a,b,x\) be the \(3\) alternatives defined in the \((v,u,w)\)-BE-configuration (see 3). By symmetry and by the preferences of \(u\) and \(w\), the embedding \(E\) corresponds to one of the four possible types of illustrations labeled with (BE) in 7. Since they are equivalent up to mirroring, let us assume that \(E\) corresponds to the top left illustration of 7. Since there are \(3\) voters, we can divide the two-dimensional space into \(16\) subspaces by drawing a vertical and horizontal line through each voter’s embedded point. We enumerate these regions and use \(R_i\) to refer to region \(i\), \(i\in [16]\).

First, using 1[lem:not-inside] (setting \((r,s,y)\mathrel{\vcenter{:}}= (u,w,b)\)), we infer that alternative \(x\) cannot be embedded in \(R_6\), \(R_7\), \(R_{10}\), or \(R_{11}\). Moreover, using 1[lem:not-outside-corner] (setting \((r,s,y)\mathrel{\vcenter{:}}= (u,v,a)\)), we infer that alternative \(x\) cannot be embedded in \(R_3\), \(R_4\), \(R_7\), or \(R_8\). Similarly, using 1[lem:not-outside-corner] (setting \((r,s,y)\mathrel{\vcenter{:}}= (w,v,b)\)), we infer that alternative \(x\) cannot be embedded in \(R_9\), \(R_{10}\), \(R_{13}\), or \(R_{14}\). This implies that \(x\) is in one of the regions \(R_1\), \(R_2\), \(R_5\), \(R_{12}\), \(R_{15}\) or \(R_{16}\). By exchanging the two coordinates and the roles of \(u\) and \(w\) and the roles of \(a\) and \(b\), respectively, we know that if \(E\) embeds alternative \(x\) in \(R_5\) (resp.\(R_1\) or \(R_2\)), then there exists another Manhattan embedding which embeds \(x\) in \(R_{15}\) (resp.\(R_{16}\) or \(R_{12}\)), and vice versa. Hence, without loss of generality, assume that \(E\) embeds \(x\) in \(R_1\), \(R_2\), or \(R_5\). Note that this implies that \(\boldsymbol{x}\in \mathsf{NW}({\color{red!50!black}\boldsymbol{v}})\).

Similarly, using 1[lem:not-outside-corner] (setting \((r,s,x,y)=(u,v,b,a)\) and \((r,s,x,y)=(w,v,b,a)\)), we infer that \({\color{red!50!black}\boldsymbol{v}}\notin \mathsf{BB}(\boldsymbol{u}, \boldsymbol{b})\cup \mathsf{BB}(\boldsymbol{w}, \boldsymbol{b})\). This implies that \(\boldsymbol{b}\notin \mathsf{NE}({\color{red!50!black}\boldsymbol{v}})\cup \mathsf{SW}({\color{red!50!black}\boldsymbol{v}})\). Since \(\boldsymbol{x}\in \mathsf{NW}({\color{red!50!black}\boldsymbol{v}})\), by 2[lem:Ntogether2] (wrt.alternatives \(x\) and \(b\)), it follows that \(\boldsymbol{b}\notin \mathsf{NW}({\color{red!50!black}\boldsymbol{v}})\). This implies that \(\boldsymbol{b}\in \mathsf{SE}({\color{red!50!black}\boldsymbol{v}})\).

Let us consider alternative \(a\). On the one hand, since \(u,w\colon x\succ a\) and \(v\colon a \succ x\), by 1, it follows that \(\boldsymbol{a}\notin \mathsf{BB}(\boldsymbol{u},\boldsymbol{w})\cup \mathsf{NE}(\boldsymbol{w})\cup \mathsf{SW}(\boldsymbol{u})\). Altogether, it follows that \(\boldsymbol{a}\in \mathsf{SE}(\boldsymbol{w})\cup\mathsf{NW}(\boldsymbol{w})\cup \mathsf{SE}(\boldsymbol{u})\cup \mathsf{NW}(\boldsymbol{u})\).

On the other hand, since \(v\colon a \succ b\), \(u, w\colon b \succ a\), and \(\boldsymbol{b}\in \mathsf{SE}(v)\), by 2[lem:Ntogether1], it follows that \(\boldsymbol{a}\notin \mathsf{SE}(u)\cup \mathsf{SE}(w)\). Analogously, since \(v\colon a \succ x\), \(u, w\colon x \succ a\), and \(\boldsymbol{x}\in \mathsf{NW}(v)\), by 2[lem:Ntogether1], it follows that \(\boldsymbol{a}\notin \mathsf{NW}(u)\cup \mathsf{NW}(w)\).

This results in having no place to embed alternative \(a\), a contradiction.  ◻

Proof. Suppose, for the sake of contradiction, that there exists a profile \({\cal P}\) which contains a \((v,u,w)\)-EX-configuration and admits a -Manhattan embedding \(E\) such that \(E\) satisfies the \((v,u,w)\)-EX-property, for \(3\) voters \(v,u,w\). Let \(x,a,b,c,d,e\) be the \(6\) alternatives defined in the \((v,u,w)\)-EX-configuration (see 4). Observe that the preferences of \(u\) and \(w\) are symmetric in the sense that if we exchange the roles of \(a\) and \(b\), and also the roles of \(d\) and \(e\), then we arrive at a new \((v,u,w)\)-EX-configuration for \({\cal P}\). Hence, up to rotation and mirroring, we can assume that embedding \(E\) corresponds to the first embedding of the second row of 7. Since there are \(3\) voters, we can divide the two-dimensional space into \(16\) subspaces by drawing a vertical and horizontal line through each voter’s embedded point. We enumerate these regions as in the first embedding of the second row of 7 and use \(R_i\) to refer to region \(i\), \(i\in [16]\). We aim to show by contradiction that \(x\) cannot be embedded in any region.

First, using 1[lem:not-inside] (setting \((r,s,y)\mathrel{\vcenter{:}}= (u,w,c)\)), we infer that alternative \(x\) cannot be embedded in \(R_6\). Analogously, repeatedly using 1[lem:not-inside] (setting \((r,s,y)\mathrel{\vcenter{:}}= (u,v,a)\) and \((r,s,y)\mathrel{\vcenter{:}}= (v,w,b)\), respectively), we infer that \(x\) cannot be embedded in regions \(R_7\), \(R_{10}\) or \(R_{11}\). Further, using 1[lem:not-outside-corner] (setting \((r,s,y)\mathrel{\vcenter{:}}= (v,u,d)\)), we infer that alternative \(x\) cannot be embedded in regions \(R_1\) and \(R_5\). Again, using 1[lem:not-outside-corner] repeatedly (setting \((r,s,y)\mathrel{\vcenter{:}}= (v,w,e)\), \((r,s,y)\mathrel{\vcenter{:}}= (u,w,b)\), and \((r,s,y)\mathrel{\vcenter{:}}= (w,u,a)\), and \((r,s,y)\mathrel{\vcenter{:}}= (u,v,b)\), respectively), we further infer that alternative \(x\) cannot be embedded in regions \(R_1\)–\(R_4\), \(R_9\), \(R_{13}\), and \(R_{16}\).

This implies that \(x\) can only be embedded in \(R_8\), \(R_{12}\), \(R_{14}\), or \(R_{15}\). To this end, since \({\color{red!50!black}\boldsymbol{v}}\in \mathsf{SE}(\boldsymbol{u})\cap \mathsf{SE}(\boldsymbol{w})\), by 1[lem:not-outside-corner] (setting \((r,s,x,y)=(v,w,a,x)\) and \((r,s,x,y)=(v,u,b,x)\), respectively), we observe that \[\begin{align} \label{eq:ext-property-ab} \boldsymbol{a}[2]\le \boldsymbol{w}[2] \text{ and } \boldsymbol{b}[1]\ge \boldsymbol{u}[1]. \end{align}\tag{9}\]

If \(E\) embeds \(x\) in regions \(R_{14}\)–\(R_{15}\), then \[\begin{align} \boldsymbol{x}\in \mathsf{SW}({\color{red!50!black}\boldsymbol{v}})\cap \mathsf{SE}(\boldsymbol{u}).\label{eq:ext-property-xvu} \end{align}\tag{10}\] Since \(v\colon a\succ x\), \(w\colon x \succ a\), by 2[lem:Ntogether1], it follows that \(\boldsymbol{a}\notin \mathsf{SW}(\boldsymbol{w})\). By 9 , it follows that \(\boldsymbol{a}\in \mathsf{SE}(\boldsymbol{w})\). Since \(w\colon x \succ a\) and \(u\colon a \succ x\), by 2[lem:Ntogether1], it follows that \(\boldsymbol{x}\notin \mathsf{SE}(\boldsymbol{u})\), a contradiction to 10 .

Analogously, we also obtain a contradiction if \(x\) is embedded in region \(R_8\) or \(R_{12}\) by focusing on voter \(u\) and alternative \(b\). Assume that \[\begin{align} \boldsymbol{x}\in \mathsf{NE}({\color{red!50!black}\boldsymbol{v}})\cap \mathsf{SE}(\boldsymbol{w}).\label{eq:ext-property-xvw} \end{align}\tag{11}\] Since \(v\colon b\succ x\) and \(u\colon x \succ b\), by 2[lem:Ntogether1], it follows that \(\boldsymbol{b}\notin \mathsf{NE}(\boldsymbol{u})\). By 9 , it follows that \(\boldsymbol{b}\in \mathsf{SE}(\boldsymbol{u})\). Since \(u\colon x \succ b\) and \(w\colon b \succ x\), by 2[lem:Ntogether1], it follows that \(\boldsymbol{x}\notin \mathsf{SE}(\boldsymbol{w})\), a contradiction to 11 .  ◻

Proof. Consider profile \({\cal P}_{\thevthreecounter}\) given in 4. Suppose, towards a contradiction, that \(E\) is a -Manhattan embedding for \({\cal P}_{\thevthreecounter}\). Since each embedding for \(3\) voters must satisfy one of the two properties in 2, we distinguish between two cases: there exists a voter who is embedded inside the bounding box of the other two, or there is no such voter.

Case 1:

There exists a voter \(v_i\), \(i\in [3]\), such that \(E\) satisfies the \(v_i\)-BE-property. Since \({\cal P}_{\thevthreecounter}\) contains a \((v_1,v_2,v_3)\)-BE-configuration wrt.\((a,b,x)=(2,6,5)\), by 3 it follows that \(E\) violates the \(v_1\)-BE-property. Analogously, since \({\cal P}\) contains a \((v_2,v_1,v_3)\)-BE-configuration regarding \(a=4,b=2,x=3\), and \((v_3,v_1,v_2)\)-BE-configuration with \(a=5,b=1,x=3\), neither does \(E\) satisfy the \(v_2\)-BE-property or the \(v_3\)-BE-property.

Case 2:

There exists a voter \(v_i\), \(i\in [3]\), such that \(E\) satisfies the \(v_i\)-EX-property. Consider the subprofile \({\cal P}'\) restricted to the alternatives \(1,2,\) \(3,6\). We claim that this subprofile contains an EX-configuration, which by 4 precludes the existence of such a voter \(v_i\) with the \(v_i\)-EX-property:

First, since \({\cal P}'\) contains a \((v_3,v_1,v_2)\)-EX-configuration (setting \((u,v,w)\) \(\mathrel{\vcenter{:}}= (v_1,v_3,v_2)\) and \((x,a,b,c,d,e)=(3,2,6,1,1,1)\)), by 4, it follows that \(E\) violates the \(v_3\)-EX-property. In fact, \({\cal P}'\) also contains a \(v_2\)-EX-configuration (setting \((u,v,w)\mathrel{\vcenter{:}}= (v_1,v_2,v_3)\) and \((x,a,b,c,d,e)=(3,1,6,2,2,2)\)) and a \(v_1\)-EX-configuration (setting \((u,v,w)\mathrel{\vcenter{:}}= (v_2,v_1,v_3)\) and \((x,a,b,c,d,e)=(3,1,2,6,6,6)\)). By 4, it follows that \(E\) violates the \(v_2\)-EX-property and the \(v_1\)-EX-property.

Summarizing, we obtain a contradiction for \(E\).   ◻

Proof. Assume that we have three alternatives \(x, y\) and \(z\), and a -Max embedding \(E\) such that \(\boldsymbol{z}\in \mathsf{BB}(\boldsymbol{x}, \boldsymbol{y})\). Let \(v\) be an arbitrary voter.

Consider an arbitrary dimension \(i \in [d]\). Since \(\boldsymbol{z}\in \mathsf{BB}(\boldsymbol{x}, \boldsymbol{y})\), we have \(\min\{\boldsymbol{x}[i], \boldsymbol{y}[i]\} \leq \boldsymbol{z}[i] \leq \max\{\boldsymbol{x}[i], \boldsymbol{y}[i]\}\). Let \(\boldsymbol{r}\mathrel{\vcenter{:}}= \mathop{\mathrm{arg\,min}}_{\{x, y\}} \{\boldsymbol{x}[i], \boldsymbol{y}[i]\}\) and \(\boldsymbol{s}\mathrel{\vcenter{:}}= \mathop{\mathrm{arg\,max}}_{\{x, y\}} \{\boldsymbol{x}[i], \boldsymbol{y}[i]\}\); if \(\boldsymbol{x}[i] = \boldsymbol{y}[i]\), then we set \((\boldsymbol{r}, \boldsymbol{s}) \mathrel{\vcenter{:}}= (\boldsymbol{x}, \boldsymbol{y})\). Therefore, we have \[\boldsymbol{r}[i] \leq \boldsymbol{z}[i] \leq \boldsymbol{s}[i].\label{eq:maxbetweennes}\tag{12}\] We have the following two cases regarding the relative order of \({\color{red!50!black}\boldsymbol{v}}[i]\) and \(\boldsymbol{z}[i]\):

Case 1:

\({\color{red!50!black}\boldsymbol{v}}[i] \leq \boldsymbol{z}[i]\). Then, \({\color{red!50!black}\boldsymbol{v}}[i] \leq \boldsymbol{s}[i]\) and \(| \boldsymbol{z}[i] - {\color{red!50!black}\boldsymbol{v}}[i]| = \boldsymbol{z}[i] - {\color{red!50!black}\boldsymbol{v}}[i] \stackrel{\eqref{eq:maxbetweennes}}{\leq} \boldsymbol{s}[i] - {\color{red!50!black}\boldsymbol{v}}[i] = | \boldsymbol{s}[i] - {\color{red!50!black}\boldsymbol{v}}[i]| \leq \max\{| \boldsymbol{x}[i] - {\color{red!50!black}\boldsymbol{v}}[i]| , | \boldsymbol{y}[i] - {\color{red!50!black}\boldsymbol{v}}[i]| \}\).

Case 2:

\({\color{red!50!black}\boldsymbol{v}}[i] > \boldsymbol{z}[i]\). Then, \({\color{red!50!black}\boldsymbol{v}}[i] > \boldsymbol{r}[i]\) and \(| \boldsymbol{z}[i] - {\color{red!50!black}\boldsymbol{v}}[i]| = {\color{red!50!black}\boldsymbol{v}}[i] - \boldsymbol{z}[i] \stackrel{\eqref{eq:maxbetweennes}}{\leq} {\color{red!50!black}\boldsymbol{v}}[i] - \boldsymbol{r}[i] = | \boldsymbol{r}[i] - {\color{red!50!black}\boldsymbol{v}}[i]| \leq \max\{| \boldsymbol{x}[i] - {\color{red!50!black}\boldsymbol{v}}[i]| , | \boldsymbol{y}[i] - {\color{red!50!black}\boldsymbol{v}}[i]| \}\).

In both cases, it holds that \(| \boldsymbol{z}[i] - {\color{red!50!black}\boldsymbol{v}}[i]| \leq \max\{| \boldsymbol{x}[i] - {\color{red!50!black}\boldsymbol{v}}[i]| , | \boldsymbol{y}[i] - {\color{red!50!black}\boldsymbol{v}}[i]| \}\). As this holds for an arbitrary \(i \in [d]\), it holds for every \(i \in [d]\). Therefore, \[\begin{align} \|{\color{red!50!black}\boldsymbol{v}}- \boldsymbol{z} \|_{\infty} = \max_{i \in [d]}| \boldsymbol{z}[i] - {\color{red!50!black}\boldsymbol{v}}[i]| & \leq \max_{i \in [d]} \biggl( \max\{| \boldsymbol{x}[i] - {\color{red!50!black}\boldsymbol{v}}[i]| , | \boldsymbol{y}[i] - {\color{red!50!black}\boldsymbol{v}}[i]| \} \biggr) = \max\{ \|{\color{red!50!black}\boldsymbol{v}}- \boldsymbol{x} \|_{\infty}, \|{\color{red!50!black}\boldsymbol{v}}- \boldsymbol{y} \|_{\infty}\}. \end{align}\]

This implies that \(\|{\color{red!50!black}\boldsymbol{v}}- \boldsymbol{z} \|_{\infty} < \|{\color{red!50!black}\boldsymbol{v}}- \boldsymbol{x} \|_{\infty}\) or \(\|{\color{red!50!black}\boldsymbol{v}}- \boldsymbol{z} \|_{\infty} < \|{\color{red!50!black}\boldsymbol{v}}- \boldsymbol{y} \|_{\infty}\) and thus by the definition of -Max, \(z \succ_v x\) or \(z \succ_v y\), as desired. ◻

Proof. Assume, towards a contradiction, that \({\cal S}\subset \mathbb{R}^{2}\) is a point set with five points \(\boldsymbol{r},\boldsymbol{s},\boldsymbol{t},\boldsymbol{u},\boldsymbol{w}\), but it contains no distinct points \(\boldsymbol{x}, \boldsymbol{y}, \boldsymbol{z}\in {\cal S}\) such that \(\boldsymbol{z}\in \mathsf{BB}(\boldsymbol{x}, \boldsymbol{y})\). By renaming we assume that \[\boldsymbol{r}[1] \leq \boldsymbol{s}[1] \leq \boldsymbol{t}[1] \leq \boldsymbol{u}[1] \leq \boldsymbol{w}[1].\] Without loss of generality, assume that \[\boldsymbol{r}[2] \leq \boldsymbol{w}[2];\] note that if \(\boldsymbol{r}[2] > \boldsymbol{w}[2]\) we can mirror the embedding by \(x\)-axis.

For each point \(\boldsymbol{a}\in \{\boldsymbol{s}, \boldsymbol{t}, \boldsymbol{u}\}\), we have two options for their relative positions regarding \(\boldsymbol{r}\) and \(\boldsymbol{w}\) on axis \(2\): \(\boldsymbol{a}[2] < \boldsymbol{r}[2]\) or \(\boldsymbol{a}[2] > \boldsymbol{w}[2]\). Note that we cannot have \(\boldsymbol{r}[2] \leq \boldsymbol{a}[2] \leq \boldsymbol{w}[2]\), because then we would have \(\boldsymbol{r}[i] \leq \boldsymbol{a}[i] \leq \boldsymbol{w}[i]\) for every axis \(i \in [2]\), which would imply \(\boldsymbol{a}\in \mathsf{BB}(\boldsymbol{r}, \boldsymbol{w})\), a contradiction to our assumption.

As we have three remaining alternatives \(\boldsymbol{s}\), \(\boldsymbol{t}\), and \(\boldsymbol{u}\), but two options, at least two of them must satisfy the same option. Let \(\{\boldsymbol{a}, \boldsymbol{b}\} \subset \{\boldsymbol{s}, \boldsymbol{t}, \boldsymbol{u}\}\) such that \(\boldsymbol{a}[1] \leq \boldsymbol{b}[1]\) and \(\max\{\boldsymbol{a}[2], \boldsymbol{b}[2]\} < \boldsymbol{r}[2]\) or \(\min\{\boldsymbol{a}[2], \boldsymbol{b}[2]\} > \boldsymbol{w}[2]\). We have four cases for the possible relative orders of \(\boldsymbol{a}, \boldsymbol{b}, \boldsymbol{r}\) and \(\boldsymbol{w}\) on axis \(2\), which are also illustrated in 10:

Case 1:

\(\boldsymbol{a}[2] \leq \boldsymbol{b}[2] < \boldsymbol{r}[2]\). Then, it follows that \(\boldsymbol{a}[i] \leq \boldsymbol{b}[i] \leq \boldsymbol{w}[i]\) for every axis \(i \in [2]\), which implies that \(\boldsymbol{b}\in \mathsf{BB}(\boldsymbol{a}, \boldsymbol{w})\), a contradiction.

Case 2:

\(\boldsymbol{b}[2] \leq \boldsymbol{a}[2] < \boldsymbol{r}[2]\). Then, it follows that \(\boldsymbol{r}[1] \leq \boldsymbol{a}[1] \leq \boldsymbol{b}[1]\) and \(\boldsymbol{b}[2] \leq \boldsymbol{a}[2] < \boldsymbol{r}[2]\), which implies that \(\boldsymbol{a}\in \mathsf{BB}(\boldsymbol{r}, \boldsymbol{b})\) a contradiction.

Case 3:

\(\boldsymbol{w}[2] < \boldsymbol{a}[2] \leq \boldsymbol{b}[2]\). Then, \(\boldsymbol{r}[i] \leq \boldsymbol{a}[i] \leq \boldsymbol{b}[i]\) for every axis \(i \in [2]\), which implies that \(\boldsymbol{a}\in \mathsf{BB}(\boldsymbol{r}, \boldsymbol{b})\), a contradiction.

Case 4:

\(\boldsymbol{w}[2] < \boldsymbol{b}[2] \leq \boldsymbol{a}[2]\). Then, \(\boldsymbol{a}[1] \leq \boldsymbol{b}[1] \leq \boldsymbol{w}[1]\) and \(\boldsymbol{w}[2] < \boldsymbol{b}[2] \leq \boldsymbol{a}[2]\), which implies that \(\boldsymbol{b}\in \mathsf{BB}(\boldsymbol{a}, \boldsymbol{w})\), a contradiction.

= [fill=red!20,draw=red, inner sep=-1pt]

As all cases lead to a contradiction, our original assumption must have been false. This concludes the proof. ◻

Proof. Suppose, towards a contradiction, that we have a profile \({\cal P}\) with at least \(5\) alternatives \(\{a, b, c, d, e\}\) which contains an all-triples worst-diverse configuration and is -Max with a -Max embedding \(E\).

As we have \(5\) alternatives, by 6 there must be a triple \(\{ x, y, z\} \subset \{a, b, c, d, e\}\) such that \(\boldsymbol{z}\in \mathsf{BB}(\boldsymbol{x}, \boldsymbol{y})\). This together with 5 implies that no voter \(v\) can satisfy \(\{x, y\} \succ_v z\). However, this is a contradiction to our assumption that \({\cal P}\) contains an all-triples worst-diverse configuration. Therefore we cannot have a profile \({\cal P}\) with at least \(5\) alternatives which contains an all-triples worst-diverse configuration and has a -Max embedding \(E\).

One can verify that profile \({\cal P}_{\thevfourcounter}\) given in 5 with \(5\) alternatives and \(4\) voters contains an all-triples worst-diverse configuration, and is not -Max: The alternatives \(1, 2, 4\), and \(5\) are ranked last by voters \(v_4, v_3, v_2\), and \(v_1\), respectively. Therefore we can pick the corresponding voters for every triple involving only the alternatives \(1, 2, 4\) and \(5\). It is straightforward to verify that there is a worst-diverse configuration for every triple of alternatives involving \(3\) as well. Thus we have shown that there is a profile with \(4\) voters and \(5\) alternatives that is not -Max. By 1 it is also not -Manhattan. ◻

Proof. Let \({\cal P},u,v,w,r,a,b,c,d,E\) be as defined such that \({\color{red!50!black}\boldsymbol{v}}\in \mathsf{BB}(\boldsymbol{u}, \boldsymbol{w})\). Without loss of generality assume that \(\boldsymbol{u}[1]\le {\color{red!50!black}\boldsymbol{v}}[1] \le \boldsymbol{w}[1]\) and \(\boldsymbol{u}[2]\le {\color{red!50!black}\boldsymbol{v}}[2] \le \boldsymbol{w}[2]\). We divide the two-dimensional space into 16 subspaces, enumerate these regions as in the top left configuration of 7, also shown again in 11 and use \(R_i\) to refer to region \(i\), \(i\in [16]\). To prove the statement, we will show that if \(\boldsymbol{r}\in \mathsf{NW}({\color{red!50!black}\boldsymbol{v}})\cup \mathsf{SE}({\color{red!50!black}\boldsymbol{v}})\cup \mathsf{NE}({\color{red!50!black}\boldsymbol{v}})\), then \(E\) is not -Manhattan.

Before we proceed, we establish where the individual alternatives can be embedded. First, by the preferences of \(u\) and \(w\) regarding \(c\) and \(a\), and by 1[lem:not-inside], we obtain that \({\color{blue}\boldsymbol{c}}\notin \mathsf{BB}(\boldsymbol{u},\boldsymbol{w})\). Further, by the preferences of \(u\) and \(v\) regarding \(c\) and \(d\) and by 1[lem:not-outside-corner], we infer that since \({\color{red!50!black}\boldsymbol{v}}\in \mathsf{NE}(\boldsymbol{u})\), it holds that \({\color{blue}\boldsymbol{c}}\notin \mathsf{NE}({\color{red!50!black}\boldsymbol{v}})\). Analogously, due to the preference of \(v\) and \(w\) regarding \(b\) and \(c\), we have that since \(\boldsymbol{w}\in \mathsf{SW}({\color{red!50!black}\boldsymbol{v}})\), it holds that \({\color{blue}\boldsymbol{c}}\notin \mathsf{SW}({\color{red!50!black}\boldsymbol{v}})\). Together, we infer that \({\color{blue}\boldsymbol{c}}\in R_1\cup R_2\cup R_5\cup R_{12}\cup R_{15}\cup R_{16}\). By symmetry, assume that \({\color{blue}\boldsymbol{c}}\in R_1\cup R_2 \cup R_5\), implying that \({\color{blue}\boldsymbol{c}}\in \mathsf{NW}({\color{red!50!black}\boldsymbol{v}})\).

Similarly, we obtain that \(\boldsymbol{a}\in \mathsf{NW}({\color{red!50!black}\boldsymbol{v}})\cup \mathsf{SE}({\color{red!50!black}\boldsymbol{v}})\). By the preferences of \(u,v,w\) regarding \(c\) and \(a\) and by 2[lem:Ntogether2], we infer that \(\boldsymbol{a}\in \mathsf{SE}({\color{red!50!black}\boldsymbol{v}})\) since \({\color{blue}\boldsymbol{c}}\in \mathsf{NW}({\color{red!50!black}\boldsymbol{v}})\).

Now, we distinguish between three cases regarding the relative position of voter \(r\).

Case 1:

\(\boldsymbol{r}\in \mathsf{NW}({\color{red!50!black}\boldsymbol{v}})\). Since \(r\colon a \succ d\) and \(v\colon d \succ a\), by 1[lem:not-outside-corner], it follows that \({\color{red!50!black}\boldsymbol{v}}\notin \mathsf{BB}(\boldsymbol{r}, \boldsymbol{a})\), a contradiction to \(\boldsymbol{r}\in \mathsf{NW}({\color{red!50!black}\boldsymbol{v}})\) and \(\boldsymbol{a}\in \mathsf{SE}({\color{red!50!black}\boldsymbol{v}})\).

Case 2:

\(\boldsymbol{r}\in \mathsf{SE}({\color{red!50!black}\boldsymbol{v}})\). This case is analogous to the first case. We consider \(c\) and \(d\) instead. Since \(r\colon c \succ d\) and \(v\colon d \succ c\), by 1[lem:not-outside-corner], it follows that \({\color{red!50!black}\boldsymbol{v}}\notin \mathsf{BB}(\boldsymbol{r},{\color{blue}\boldsymbol{c}})\), a contradiction to our assumption as well.

Case 3:

\(\boldsymbol{r}\in \mathsf{NE}({\color{red!50!black}\boldsymbol{v}})\). Let us consider alternative \(d\). By the preferences of \(u\) and \(r\), and by 1[lem:not-inside], we obtain that \(\boldsymbol{d}\notin \mathsf{BB}(\boldsymbol{u},\boldsymbol{r})\). By 1[lem:not-outside-corner] (considering the preferences of \(u\) and \(v\) regarding \(c\) and \(d\)) we infer that since \(\boldsymbol{u}\in \mathsf{SW}({\color{red!50!black}\boldsymbol{v}})\), it holds that \(\boldsymbol{d}\notin \mathsf{SW}(\boldsymbol{u})\). Analogously by considering the preferences of \(r\) and \(v\) regarding \(c\) and \(d\) we infer that \(\boldsymbol{d}\notin \mathsf{NE}(\boldsymbol{r})\). Moreover, by 2[lem:Ntogether1] (considering the preferences of \(u,v,r\) regarding \(c\) and \(d\)) and since \({\color{blue}\boldsymbol{c}}\in \mathsf{NW}({\color{red!50!black}\boldsymbol{v}})\), we infer that \(\boldsymbol{d}\notin \mathsf{NW}(\boldsymbol{u})\cup \mathsf{NW}(\boldsymbol{r})\). By 2[lem:Ntogether2] (considering the preferences of \(u,v,r\) regarding \(c\) and \(d\)) and since \({\color{blue}\boldsymbol{c}}\in \mathsf{NW}({\color{red!50!black}\boldsymbol{v}})\), we further infer that \(\boldsymbol{d}\notin \mathsf{NW}({\color{red!50!black}\boldsymbol{v}})\). Hence \(\boldsymbol{d}\in \mathsf{SE}(\boldsymbol{u}) \cup \mathsf{SE}(\boldsymbol{r})\).

However, this is a contradiction: Since \(v\colon d \succ a\) and \(u,r\colon a \succ d\), and \(\boldsymbol{a}\in \mathsf{SE}({\color{red!50!black}\boldsymbol{v}})\), by 2[lem:Ntogether1], it follows that \(\boldsymbol{d}\notin \mathsf{SE}(\boldsymbol{u})\cup \mathsf{SE}(\boldsymbol{r})\).

Summarizing, this implies that \(\boldsymbol{r}\in \mathsf{SW}({\color{red!50!black}\boldsymbol{v}})\), and hence \({\color{red!50!black}\boldsymbol{v}}\in \mathsf{BB}(\boldsymbol{r},\boldsymbol{w})\). ◻

Proof. We show that profile \({\cal P}_{\thevfivecounter}\) given in 6 is not -Manhattan. Suppose, towards a contradiction, that \({\cal P}_{\thevfivecounter}\) admits a -Manhattan embedding \(E\). For the sake of brevity, we use \({\color{blue}\boldsymbol{c}}_1, \dots, {\color{blue}\boldsymbol{c}}_5\) to refer to \(E(1), \dots, E(5)\).

First, we observe that one of voters \(v_1\), \(v_2\), and \(v_3\) is embedded within the bounding box defined by the other two since the subprofile of \({\cal P}_{\thevfivecounter}\) restricted to voters \(v_1\), \(v_2\), and \(v_3\) is equivalent to profile \({\cal P}_{\theextcounter}\) which, by 4, violates the EX-property (for each of \(v_1\), \(v_2\), and \(v_3\), respectively). We distinguish between two cases.

Case 1:

\({\color{red!50!black}\boldsymbol{v}}_2\in \mathsf{BB}({\color{red!50!black}\boldsymbol{v}}_1,{\color{red!50!black}\boldsymbol{v}}_3)\) or \({\color{red!50!black}\boldsymbol{v}}_1\in \mathsf{BB}({\color{red!50!black}\boldsymbol{v}}_2,{\color{red!50!black}\boldsymbol{v}}_3)\). Note that these two subcases are equivalent in the sense that if we exchange the roles of alternatives \(2\) and \(4\), i.e., \(1\mapsto 1\), \(3 \mapsto 3\), \(2\mapsto 4\), and \(4 \mapsto 2\), we obtain an equivalent (in terms of the Manhattan property) profile where the roles of voters \(v_1\) and \(v_2\) (resp.\(v_4\) and \(v_5\)) are exchanged. Hence, it suffices to consider the case of \({\color{red!50!black}\boldsymbol{v}}_2\in \mathsf{BB}({\color{red!50!black}\boldsymbol{v}}_1,{\color{red!50!black}\boldsymbol{v}}_3)\). Without loss of generality, assume that \({\color{red!50!black}\boldsymbol{v}}_1[1]\le {\color{red!50!black}\boldsymbol{v}}_2[1]\le {\color{red!50!black}\boldsymbol{v}}_3[1]\) and \({\color{red!50!black}\boldsymbol{v}}_1[2]\le {\color{red!50!black}\boldsymbol{v}}_2[2]\le {\color{red!50!black}\boldsymbol{v}}_3[2]\); see 12.

Then, by 7 (setting \((u,v,w,r)\mathrel{\vcenter{:}}= (v_1,v_2,v_3,v_4)\)), we obtain that \({\color{red!50!black}\boldsymbol{v}}_2\in \mathsf{BB}({\color{red!50!black}\boldsymbol{v}}_4,{\color{red!50!black}\boldsymbol{v}}_3)\). This implies that \({\color{red!50!black}\boldsymbol{v}}_4[1]\le {\color{red!50!black}\boldsymbol{v}}_2[1]\) and \({\color{red!50!black}\boldsymbol{v}}_4[2]\le {\color{red!50!black}\boldsymbol{v}}_2[2]\); see 12.

By the preferences of \(v_4\), \(v_2\), and \(v_3\) regarding alternatives \(2\) and \(1\), and by 1[lem:Ntogether2], it follows that \({\color{red!50!black}\boldsymbol{v}}\notin \mathsf{BB}({\color{red!50!black}\boldsymbol{v}}_3, 2) \cup \mathsf{BB}({\color{red!50!black}\boldsymbol{v}}_4,2)\) and hence \({\color{blue}\boldsymbol{c}}_2\in \mathsf{NW}({\color{red!50!black}\boldsymbol{v}}_2)\cup \mathsf{SE}({\color{red!50!black}\boldsymbol{v}}_2)\). With the same voters and alternatives and 1[lem:Ntogether1] we obtain that by the preferences of \(v_4\), \(v_2\), and \(v_3\) regarding alternatives \(2\) and \(1\), we obtain that \({\color{blue}\boldsymbol{c}}_1\notin \mathsf{BB}({\color{red!50!black}\boldsymbol{v}}_3,{\color{red!50!black}\boldsymbol{v}}_4)\). Combining this and applying 1[lem:Ntogether2] again, we obtain that \({\color{red!50!black}\boldsymbol{v}}_3, {\color{red!50!black}\boldsymbol{v}}_4 \notin \mathsf{BB}({\color{red!50!black}\boldsymbol{v}}_2, {\color{blue}\boldsymbol{c}}_1)\) and hence \[\begin{align} {\color{blue}\boldsymbol{c}}_1\notin \mathsf{BB}({\color{red!50!black}\boldsymbol{v}}_3,{\color{red!50!black}\boldsymbol{v}}_4)\cup \mathsf{NE}({\color{red!50!black}\boldsymbol{v}}_3)\cup \mathsf{SW}({\color{red!50!black}\boldsymbol{v}}_4).\label{eq:n5-m4:case1-c1} \end{align}\tag{13}\] Similarly, regarding the preferences over \(3\) and \(1\), it follows that \({\color{red!50!black}\boldsymbol{v}}_2 \notin \mathsf{BB}({\color{red!50!black}\boldsymbol{v}}_3, 3) \cup \mathsf{BB}({\color{red!50!black}\boldsymbol{v}}_4,3)\) and hence \({\color{blue}\boldsymbol{c}}_3\in \mathsf{NW}({\color{red!50!black}\boldsymbol{v}}_2)\cup \mathsf{SE}({\color{red!50!black}\boldsymbol{v}}_2)\). By 2[lem:Ntogether2] (considering the preferences of \(v_1,v_2\) and \(v_3\) regarding alternatives \(2\) and \(3\)), we further infer that either \({\color{blue}\boldsymbol{c}}_2\in \mathsf{NW}({\color{red!50!black}\boldsymbol{v}}_2)\) and \({\color{blue}\boldsymbol{c}}_3\in \mathsf{SE}({\color{red!50!black}\boldsymbol{v}}_2)\) or \({\color{blue}\boldsymbol{c}}_2\in \mathsf{SE}({\color{red!50!black}\boldsymbol{v}}_2)\) and \({\color{blue}\boldsymbol{c}}_3\in \mathsf{NW}({\color{red!50!black}\boldsymbol{v}}_2)\). By symmetry, we only consider the case of \({\color{blue}\boldsymbol{c}}_2\in \mathsf{NW}({\color{red!50!black}\boldsymbol{v}}_2)\) and \({\color{blue}\boldsymbol{c}}_3\in \mathsf{SE}({\color{red!50!black}\boldsymbol{v}}_2)\).

On the one hand, by the preferences of \(v_3\) and \(v_2\) (resp.\(v_4\) and \(v_2\)) regarding \(1\) and \(3\) and by 2[lem:Ntogether1] and the fact that \({\color{blue}\boldsymbol{c}}_3\in \mathsf{SE}({\color{red!50!black}\boldsymbol{v}}_2)\), it follows that \({\color{blue}\boldsymbol{c}}_1\notin \mathsf{SE}({\color{red!50!black}\boldsymbol{v}}_3)\) (resp.\({\color{blue}\boldsymbol{c}}_1\notin \mathsf{SE}({\color{red!50!black}\boldsymbol{v}}_4)\)). On the other hand, by the preferences of \(v_4\) and \(v_2\) (resp.\(v_3\) and \(v_2\)) regarding \(1\) and \(2\) and by 2[lem:Ntogether1] and \({\color{blue}\boldsymbol{c}}_2\in \mathsf{NW}({\color{red!50!black}\boldsymbol{v}}_2)\), it follows that \({\color{blue}\boldsymbol{c}}_1\notin \mathsf{NW}({\color{red!50!black}\boldsymbol{v}}_3)\) (resp.\({\color{blue}\boldsymbol{c}}_1\notin \mathsf{NW}({\color{red!50!black}\boldsymbol{v}}_4)\)). Together, this leads to a contradiction to 13 .

Case 2:

\({\color{red!50!black}\boldsymbol{v}}_3\in \mathsf{BB}({\color{red!50!black}\boldsymbol{v}}_1,{\color{red!50!black}\boldsymbol{v}}_2)\). Without loss of generality, assume that \({\color{red!50!black}\boldsymbol{v}}_1[1]\le {\color{red!50!black}\boldsymbol{v}}_3[1]\le {\color{red!50!black}\boldsymbol{v}}_2[1]\) and \({\color{red!50!black}\boldsymbol{v}}_1[2]\le {\color{red!50!black}\boldsymbol{v}}_3[2]\le {\color{red!50!black}\boldsymbol{v}}_2[2]\); see [fig:no-n5-m4-case2] for an illustration. Then, by 7 (setting \((u,v,w,r)\mathrel{\vcenter{:}}=(v_1,v_3,v_2,v_4)\) and \((u,v,w,r)\mathrel{\vcenter{:}}= (v_2,v_3,v_1,v_5)\), respectively), we obtain that \({\color{red!50!black}\boldsymbol{v}}_3\in \mathsf{BB}({\color{red!50!black}\boldsymbol{v}}_4,{\color{red!50!black}\boldsymbol{v}}_2)\) and \({\color{red!50!black}\boldsymbol{v}}_3\in \mathsf{BB}({\color{red!50!black}\boldsymbol{v}}_5,{\color{red!50!black}\boldsymbol{v}}_1)\). This implies that \[\begin{align} {\color{red!50!black}\boldsymbol{v}}_4[1]\le {\color{red!50!black}\boldsymbol{v}}_3[1] \text{ and }{\color{red!50!black}\boldsymbol{v}}_4[2]\le {\color{red!50!black}\boldsymbol{v}}_3[2], \text{ and } {\color{red!50!black}\boldsymbol{v}}_5[1]\ge {\color{red!50!black}\boldsymbol{v}}_3[1] \text{ and }{\color{red!50!black}\boldsymbol{v}}_5[2]\ge {\color{red!50!black}\boldsymbol{v}}_3[2].\label{eq:n5-m4-v5-v3} \end{align}\tag{14}\] See [fig:no-n5-m4-case2-v-refined] for an illustration.

In the remainder of the proof, we will show that we can assume the following relative orientation from each of the four alternatives towards voter \(v_3\); see 14: \[\begin{align} {\color{blue}\boldsymbol{c}}_1 \in \mathsf{NW}({\color{red!50!black}\boldsymbol{v}}_3), {\color{blue}\boldsymbol{c}}_2 \in \mathsf{SW}({\color{red!50!black}\boldsymbol{v}}_3), {\color{blue}\boldsymbol{c}}_3 \in \mathsf{SE}({\color{red!50!black}\boldsymbol{v}}_3), \text{ and } {\color{blue}\boldsymbol{c}}_4 \in \mathsf{NE}({\color{red!50!black}\boldsymbol{v}}_3). \end{align}\] Moreover, among all four alternatives, alternative \(1\) shall be embedded to the westmost and northmost, while alternative \(3\) to the southmost and \(4\) the eastmost. Such conditions are, however, not possible to yield a -Manhattan embedding for voters \(v_2\) and \(v_4\) respect to the two pairs \(\{1,2\}\) and \(\{3,4\}\).

Before we formally prove this, we give an intuitive idea. Since voters \(v_1\) and \(v_5\) are embedded to the southwest and northeast of \(v_3\), respectively, and since both prefer \(1\succ 2\) and \(3 \succ 4\), but \(v_3\) prefers \(2\succ 1\) and \(4 \succ 3\), the bisector between alternatives \(1\) and \(2\) and that between alternatives \(3\) and \(4\) must “cross” twice; see 14. This enforces the relative positions of the four alternatives as described above. Analogously, due voters \(v_2\) and \(v_4\), and \(v_3\)’s preferences over \(\{1,4\}\) and \(\{3,2\}\), the bisector between alternatives \(1\) and \(4\) and the one between alternatives \(3\) and \(2\) must also cross twice. This is, however, impossible; see [fig:no-n5-m4-case2:crossingtwiche-b].

Now, we proceed with the proof of the relative positions of the alternatives.

Claim 1. We can assume that \({\color{blue}\boldsymbol{c}}_1 \in \mathsf{NW}({\color{red!50!black}\boldsymbol{v}}_3)\), \({\color{blue}\boldsymbol{c}}_2 \in \mathsf{SW}({\color{red!50!black}\boldsymbol{v}}_3)\cap \mathsf{SE}({\color{red!50!black}\boldsymbol{v}}_1)\cap \mathsf{NW}({\color{red!50!black}\boldsymbol{v}}_4)\), \({\color{blue}\boldsymbol{c}}_3 \in \mathsf{SE}({\color{red!50!black}\boldsymbol{v}}_3)\), and \({\color{blue}\boldsymbol{c}}_4 \in \mathsf{NE}({\color{red!50!black}\boldsymbol{v}}_3)\cap \mathsf{SE}({\color{red!50!black}\boldsymbol{v}}_2) \cap \mathsf{NW}({\color{red!50!black}\boldsymbol{v}}_5)\).

Proof of 1. By 1[lem:not-inside] (setting \((r,s,x,y)=(v_2,v_3,1,4)\) and \((r,s,x,y)=(v_4,v_3,1,4)\), respectively), we infer that \({\color{red!50!black}\boldsymbol{v}}_3\notin \mathsf{BB}({\color{red!50!black}\boldsymbol{v}}_2,{\color{blue}\boldsymbol{c}}_1)\cup \mathsf{BB}({\color{red!50!black}\boldsymbol{v}}_4,{\color{blue}\boldsymbol{c}}_1)\). This implies that \({\color{blue}\boldsymbol{c}}_1\in \mathsf{NW}({\color{red!50!black}\boldsymbol{v}}_3) \cup \mathsf{SE}({\color{red!50!black}\boldsymbol{v}}_3)\). By symmetry, we can assume that \[\begin{align} {\color{blue}\boldsymbol{c}}_1\in \mathsf{NW}({\color{red!50!black}\boldsymbol{v}}_3).\label{eq:n5-m4-c1} \end{align}\tag{15}\] Again, by 1[lem:not-inside] (setting \((r,s,x,y)=(v_2,v_3,3,2)\) and \((r,s,x,y)=(v_4,v_3,3,2)\), respectively), we infer that \({\color{red!50!black}\boldsymbol{v}}_3\notin \mathsf{BB}({\color{red!50!black}\boldsymbol{v}}_2,{\color{blue}\boldsymbol{c}}_3)\cup \mathsf{BB}({\color{red!50!black}\boldsymbol{v}}_4,{\color{blue}\boldsymbol{c}}_3)\). This implies that \({\color{blue}\boldsymbol{c}}_1\in \mathsf{NW}({\color{red!50!black}\boldsymbol{v}}_3) \cup \mathsf{SE}({\color{red!50!black}\boldsymbol{v}}_3)\). Then, by 2[lem:Ntogether2] (setting \((r,s,t,x\), \(y) = (v_1,v_3,v_2,1,3)\)) and by 15 , we infer that \[\begin{align} {\color{blue}\boldsymbol{c}}_3\in\mathsf{SE}({\color{red!50!black}\boldsymbol{v}}_3).\label{eq:n5-m4-c3} \end{align}\tag{16}\] It remains to show the relative positions for alternatives \(2\) and \(4\). By 2[lem:Ntogether2] (setting \((r,s,t,x,y)=(v_1,v_3,v_5,1,2)\) and \((r,s,t,x,y)=(v_2,v_3,v_4,3,2)\), respectively), we infer that \({\color{blue}\boldsymbol{c}}_2 \notin \mathsf{NW}({\color{red!50!black}\boldsymbol{v}}_3)\cup \mathsf{SE}({\color{red!50!black}\boldsymbol{v}}_3)\) since \({\color{blue}\boldsymbol{c}}_1\in \mathsf{NW}({\color{red!50!black}\boldsymbol{v}}_3)\) and \({\color{blue}\boldsymbol{c}}_3 \in \mathsf{SE}({\color{red!50!black}\boldsymbol{v}}_3)\). In other words, \({\color{blue}\boldsymbol{c}}_2 \in \mathsf{NE}({\color{red!50!black}\boldsymbol{v}}_3)\cup \mathsf{SW}({\color{red!50!black}\boldsymbol{v}}_3)\).

By 1[lem:not-inside] (setting \((r,s,x,y)=(v_4,v_5,2,3)\), \((r,s,x,y)=(v_1,v_2,2,1)\), \((r,s,x,y) = (v_1,v_5, 2,1)\), \((r,s,x,y) = (v_2,v_5, 2,1)\), respectively), we infer that \({\color{blue}\boldsymbol{c}}_2 \notin \mathsf{BB}({\color{red!50!black}\boldsymbol{v}}_4,{\color{red!50!black}\boldsymbol{v}}_5)\cup \mathsf{BB}({\color{red!50!black}\boldsymbol{v}}_1,{\color{red!50!black}\boldsymbol{v}}_2)\cup \mathsf{BB}({\color{red!50!black}\boldsymbol{v}}_1,{\color{red!50!black}\boldsymbol{v}}_5) \cup \mathsf{BB}({\color{red!50!black}\boldsymbol{v}}_2,{\color{red!50!black}\boldsymbol{v}}_5)\). By 1[lem:not-outside-corner] (setting \((r,s,x,y)=(v_3,v_2,2,3)\) and \((r,s,x,y)=(v_3,v_4,2,3)\)), we infer that \({\color{red!50!black}\boldsymbol{v}}_2,{\color{red!50!black}\boldsymbol{v}}_4\notin \mathsf{BB}({\color{red!50!black}\boldsymbol{v}}_3,{\color{blue}\boldsymbol{c}}_2)\), i.e., \({\color{blue}\boldsymbol{c}}_2 \notin \mathsf{NE}({\color{red!50!black}\boldsymbol{v}}_2)\cup \mathsf{SW}({\color{red!50!black}\boldsymbol{v}}_4)\). Again, by 1[lem:not-outside-corner] (setting \((r,s,x,y)=(v_3,v_1,2,1)\) and \((r,s,x,y)=(v_3,v_5,2,1)\)), we infer that \({\color{red!50!black}\boldsymbol{v}}_1,{\color{red!50!black}\boldsymbol{v}}_5 \notin \mathsf{BB}({\color{red!50!black}\boldsymbol{v}}_3,{\color{blue}\boldsymbol{c}}_2)\), i.e., \({\color{blue}\boldsymbol{c}}_2 \notin \mathsf{SW}({\color{red!50!black}\boldsymbol{v}}_1)\cup \mathsf{NE}({\color{red!50!black}\boldsymbol{v}}_5)\). Analogously, since \(v_5\colon 2\succ 3\) and \(v_3\colon 2 \succ 3\), By 2[lem:Ntogether1] (setting \((r,s,x,y)=(v_5,v_3,3,2)\)), we infer that \({\color{blue}\boldsymbol{c}}_2 \notin \mathsf{SE}({\color{red!50!black}\boldsymbol{v}}_5)\) since \({\color{blue}\boldsymbol{c}}_3 \in \mathsf{SE}({\color{red!50!black}\boldsymbol{v}}_3)\). Analogously, since \(v_1,v_2,v_5\colon 1\succ 2\), and \(v_3\colon 2 \succ 1\), by 2[lem:Ntogether1], \({\color{blue}\boldsymbol{c}}_2 \notin \mathsf{NW}({\color{red!50!black}\boldsymbol{v}}_1)\cup \mathsf{NW}({\color{red!50!black}\boldsymbol{v}}_2)\cup \mathsf{NW}({\color{red!50!black}\boldsymbol{v}}_5)\) since \({\color{blue}\boldsymbol{c}}_1 \in \mathsf{NW}({\color{red!50!black}\boldsymbol{v}}_3)\). Summarizing, the only region possible for \({\color{blue}\boldsymbol{c}}_2\) is \(\mathsf{SE}({\color{red!50!black}\boldsymbol{v}}_1)\cap \mathsf{NW}({\color{red!50!black}\boldsymbol{v}}_4)\). This gives \[\begin{align} \label{eq:n5-m4-c2} {\color{blue}\boldsymbol{c}}_2 \in\mathsf{SE}({\color{red!50!black}\boldsymbol{v}}_1)\cap \mathsf{NW}({\color{red!50!black}\boldsymbol{v}}_4)\cap \mathsf{SW}({\color{red!50!black}\boldsymbol{v}}_3). \end{align}\tag{17}\] By exchanging the roles of \(2\) and \(4\), those of \(v_1\) and \(v_2\), and those of \(v_4\) and \(v_5\), we can analogously obtain \[\begin{align} \label{eq:n5-m4-c4} {\color{blue}\boldsymbol{c}}_4 \in\mathsf{SE}({\color{red!50!black}\boldsymbol{v}}_2)\cap \mathsf{NW}({\color{red!50!black}\boldsymbol{v}}_5)\cap \mathsf{NE}({\color{red!50!black}\boldsymbol{v}}_3). \end{align}\tag{18}\] See [fig:no-n5-m4-case2-refined] for an illustration. ◻

To formally prove that the relative positions as described in 1 are not -Manhattan, we will use the following claim. Briefly put, it states that given the premises, the alternative that is less preferred by \(v\) should be embedded further away in which both alternatives lie on the same side of \(v\). Moreover, the shorter side of the bounding box formed by the two alternatives must be along the coordinate where both alternatives lie on the same side of \(v\); see 15 for an illustration of the first case.

Claim 2. Let \({\cal P}\) admit a -Manhattan embedding \(E\). For every three voters \(u,v,w\) and two alternatives \(x,y\) such that \(u,w\colon y\succ x\), \(v\colon y\succ x\), \(\boldsymbol{w}\in \mathsf{NE}({\color{red!50!black}\boldsymbol{v}})\), and \(\boldsymbol{u}\in \mathsf{SW}({\color{red!50!black}\boldsymbol{v}})\), the following holds:

Proof of 2. Let \({\cal P},E,u,v,w,x,y\) be as defined. We only consider the first statement in details as the other one can be shown by transforming the embedding accordingly. We first show that \(\boldsymbol{y}\in \mathsf{SE}(\boldsymbol{u})\). First, since \(u,w\colon x\succ y\), by 1[lem:not-inside], we infer that \(\boldsymbol{y}\notin \mathsf{BB}(\boldsymbol{u},\boldsymbol{w})\). This implies that \(\boldsymbol{y}\notin \mathsf{NE}(\boldsymbol{u})\) since \(\boldsymbol{y},\boldsymbol{u}\in \mathsf{SW}({\color{red!50!black}\boldsymbol{v}})\). Secondly, by 1[lem:not-outside-corner] (setting \((r,s,x,y)=(v,u,y,x)\)), we infer that \(\boldsymbol{u}\notin \mathsf{BB}({\color{red!50!black}\boldsymbol{v}}, \boldsymbol{y})\). This implies that \(\boldsymbol{y}\notin \mathsf{SW}(\boldsymbol{u})\). Finally, since \(\boldsymbol{x}\in\mathsf{NW}({\color{red!50!black}\boldsymbol{v}})\), by 2[lem:Ntogether1] (setting \((r,s,x,y)=(u,v,x,y)\)), we infer that \(\boldsymbol{y}\notin \mathsf{NW}(\boldsymbol{u})\). Summarizing, we obtain that \[\begin{align} \label{eq:y-SE-w} \boldsymbol{y}\in \mathsf{SE}(\boldsymbol{u}). \end{align}\tag{19}\]

Now, we proceed to show that \(\boldsymbol{x}[1] < \boldsymbol{y}[1]\). Since \(v\colon y\succ x\), implying that \(\|\boldsymbol{y}-{\color{red!50!black}\boldsymbol{v}} \|_1 < \|\boldsymbol{x}-{\color{red!50!black}\boldsymbol{v}} \|_1\), we infer by \(\boldsymbol{x}\in \mathsf{NW}({\color{red!50!black}\boldsymbol{v}})\) that \(({\color{red!50!black}\boldsymbol{v}}[1]-\boldsymbol{y}[1])+({\color{red!50!black}\boldsymbol{v}}[2]-\boldsymbol{y}[2]) < ({\color{red!50!black}\boldsymbol{v}}[1]-\boldsymbol{x}[1])+(\boldsymbol{x}[2]-{\color{red!50!black}\boldsymbol{v}}[2])\), i.e., \[\begin{align} \label{eq:v-x-y} 2{\color{red!50!black}\boldsymbol{v}}[2] < -\boldsymbol{x}[1]+\boldsymbol{x}[2]+\boldsymbol{y}[1]+\boldsymbol{y}[2]. \end{align}\tag{20}\] Similarly, since \(u\colon x \succ y\), implying that \(\|\boldsymbol{x}-\boldsymbol{u} \|_1 < \|\boldsymbol{y}-\boldsymbol{u} \|_1\), we infer that \(|\boldsymbol{x}[1]-\boldsymbol{u}[1]|+|\boldsymbol{x}[2]-\boldsymbol{u}[2]| \stackrel{\eqref{eq:y-SE-w}}{<} (\boldsymbol{y}[1]-\boldsymbol{u}[1])+(\boldsymbol{u}[2]-\boldsymbol{y}[2])\). This further implies that \((\boldsymbol{x}[1]-\boldsymbol{u}[1])+(\boldsymbol{x}[2]-\boldsymbol{u}[2]) < (\boldsymbol{y}[1]-\boldsymbol{u}[1])+(\boldsymbol{u}[2]-\boldsymbol{y}[2])\), i.e., \[\begin{align} \label{eq:w-x-y} \boldsymbol{x}[1]+\boldsymbol{x}[2]-\boldsymbol{y}[1]+\boldsymbol{y}[2] < 2\boldsymbol{u}[2]. \end{align}\tag{21}\] Since \(\boldsymbol{u}[2] < {\color{red!50!black}\boldsymbol{v}}[2]\), combining 20 and 21 , we immediately obtain that \(\boldsymbol{x}[1] < \boldsymbol{y}[1]\).

It remains to show the last part of the statement. Intuitively this means that the distance of \(\boldsymbol{x}\) and \(\boldsymbol{y}\) in the first coordinate must be smaller than that in the second coordinate. This is due to voter \(w\)’s preferences. Since \(w\) prefers \(x\succ y\), implying that \(\|\boldsymbol{x}-\boldsymbol{w} \|_1 < \|\boldsymbol{y}-\boldsymbol{w} \|_1\), we infer by \(\boldsymbol{w}\in \mathsf{NE}({\color{red!50!black}\boldsymbol{v}})\) that \((\boldsymbol{w}[1]-\boldsymbol{x}[1])+|\boldsymbol{w}[2]-\boldsymbol{x}[2]| < (\boldsymbol{w}[1]-\boldsymbol{y}[1])+(\boldsymbol{w}[2]-\boldsymbol{y}[2])\). This further implies that \((\boldsymbol{w}[1]-\boldsymbol{x}[1])+(\boldsymbol{w}[2]-\boldsymbol{x}[2]) < (\boldsymbol{w}[1]-\boldsymbol{y}[1])+(\boldsymbol{w}[2]-\boldsymbol{y}[2])\), i.e., \(\boldsymbol{y}[1]-\boldsymbol{x}[1] < \boldsymbol{x}[2]-\boldsymbol{y}[2]\), as desired.

Since rotating and flipping an embedding do not change the -Manhattan property, we can apply the following transformation to show the other statement. We first rotate the embedding by 180 degree and then exchange the roles of \(u\) and \(w\). ◻

In fact, the two cases in 2 one-to-one correspond to the two pairs of alternatives  \((1,2)\) and \((3,4)\). Specifically, by 2[case:W] (setting \((u,v,w,x,y)=(v_1,v_3,v_5,c_1,c_2)\)), we immediately obtain that \[\begin{align} \label{eq:c1c2} {\color{blue}\boldsymbol{c}}_1[1]<{\ensuremath{\color{blue}\boldsymbol{c}}}_2[1]. \end{align}\tag{22}\] By 2[case:E] (setting \((u,v,w,x,y)=(v_1,v_3,v_5,c_3,c_4)\)), we immediately obtain that \[\begin{align} \label{eq:c3c4} {\color{blue}\boldsymbol{c}}_3[1]>{\ensuremath{\color{blue}\boldsymbol{c}}}_4[1]. \end{align}\tag{23}\] We show that these two inequalities 22 –23 are not possible to embed both voters \(v_2\) and \(v_4\). On the one hand, since \(v_2\) and \(v_4\) prefer \(1\succ 4\), implying that \(\|{\color{blue}\boldsymbol{c}}_1-{\color{red!50!black}\boldsymbol{v}}_2 \|_1 < \|{\color{blue}\boldsymbol{c}}_4-{\color{red!50!black}\boldsymbol{v}}_2 \|_1\) and \(\|{\color{blue}\boldsymbol{c}}_1-{\color{red!50!black}\boldsymbol{v}}_4 \|_1 < \|{\color{blue}\boldsymbol{c}}_4-{\color{red!50!black}\boldsymbol{v}}_4 \|_1\), by 1, we infer that \[\begin{align} {2} & &\|{\color{blue}\boldsymbol{c}}_1-{\color{red!50!black}\boldsymbol{v}}_2 \|_1 = ({\color{red!50!black}\boldsymbol{v}}_2[1]-{\color{blue}\boldsymbol{c}}_1[1])+|{\color{red!50!black}\boldsymbol{v}}_2[2]-{\color{blue}\boldsymbol{c}}_1[2]| <~ & ({\color{blue}\boldsymbol{c}}_4[1]-{\color{red!50!black}\boldsymbol{v}}_2[1])+({\color{red!50!black}\boldsymbol{v}}_2[2]-{\color{blue}\boldsymbol{c}}_4[2]) = \|{\color{blue}\boldsymbol{c}}_4-{\color{red!50!black}\boldsymbol{v}}_2 \|_1 \nonumber\\ &\Rightarrow & ({\color{red!50!black}\boldsymbol{v}}_2[1]-{\color{blue}\boldsymbol{c}}_1[1])+({\color{red!50!black}\boldsymbol{v}}_2[2]-{\color{blue}\boldsymbol{c}}_1[2]) <~ &({\color{blue}\boldsymbol{c}}_4[1]-{\color{red!50!black}\boldsymbol{v}}_2[1])+({\color{red!50!black}\boldsymbol{v}}_2[2]-{\color{blue}\boldsymbol{c}}_4[2])\nonumber \\ & \Leftrightarrow & 2{\color{red!50!black}\boldsymbol{v}}_2[1] <~ & {\color{blue}\boldsymbol{c}}_1[1] + {\color{blue}\boldsymbol{c}}_1[2] + {\color{blue}\boldsymbol{c}}_4[1] - {\color{blue}\boldsymbol{c}}_4[2].\tag{24} \\[1ex] &&\|{\color{blue}\boldsymbol{c}}_1-{\color{red!50!black}\boldsymbol{v}}_4 \|_1=|{\color{red!50!black}\boldsymbol{v}}_4[1]-{\color{blue}\boldsymbol{c}}_1[1]|+({\color{blue}\boldsymbol{c}}_1[2]-{\color{red!50!black}\boldsymbol{v}}_4[2]) <~& ({\color{blue}\boldsymbol{c}}_4[1]-{\color{red!50!black}\boldsymbol{v}}_4[1])+({\color{blue}\boldsymbol{c}}_4[2]-{\color{red!50!black}\boldsymbol{v}}_4[2]) =\|{\color{blue}\boldsymbol{c}}_4-{\color{red!50!black}\boldsymbol{v}}_4 \|_1\nonumber \\ & \Rightarrow & ({\color{red!50!black}\boldsymbol{v}}_4[1]-{\color{blue}\boldsymbol{c}}_1[1])+({\color{blue}\boldsymbol{c}}_1[2]-{\color{red!50!black}\boldsymbol{v}}_4[2]) <~& ({\color{blue}\boldsymbol{c}}_4[1]-{\color{red!50!black}\boldsymbol{v}}_4[1])+({\color{blue}\boldsymbol{c}}_4[2]-{\color{red!50!black}\boldsymbol{v}}_4[2])\nonumber\\ &\Leftrightarrow & 2{\color{red!50!black}\boldsymbol{v}}_4[1] <~& {\color{blue}\boldsymbol{c}}_1[1] - {\color{blue}\boldsymbol{c}}_1[2] + {\color{blue}\boldsymbol{c}}_4[1]+{\color{blue}\boldsymbol{c}}_4[2]. \tag{25} \end{align}\] On the other hand, since \(v_2\) and \(v_4\) prefer \(3\succ 2\), implying that \(\|{\color{blue}\boldsymbol{c}}_3-{\color{red!50!black}\boldsymbol{v}}_2 \|_1 < \|{\color{blue}\boldsymbol{c}}_2-{\color{red!50!black}\boldsymbol{v}}_2 \|_1\) and \(\|{\color{blue}\boldsymbol{c}}_3-{\color{red!50!black}\boldsymbol{v}}_4 \|_1 < \|{\color{blue}\boldsymbol{c}}_2-{\color{red!50!black}\boldsymbol{v}}_4 \|_1\), by 1, we infer that \[\begin{align} {2} & & \|{\color{blue}\boldsymbol{c}}_3-{\color{red!50!black}\boldsymbol{v}}_2 \|_1 = |{\color{blue}\boldsymbol{c}}_3[1]-{\color{red!50!black}\boldsymbol{v}}_2[1]| + ({\color{red!50!black}\boldsymbol{v}}_2[2]-{\color{blue}\boldsymbol{c}}_3[2]) <~& ({\color{red!50!black}\boldsymbol{v}}_2[1]-{\color{blue}\boldsymbol{c}}_2[1]) + ({\color{red!50!black}\boldsymbol{v}}_2[2]-{\color{blue}\boldsymbol{c}}_2[2])=\|{\color{blue}\boldsymbol{c}}_2-{\color{red!50!black}\boldsymbol{v}}_2 \|_1\nonumber\\ & \Rightarrow & ({\color{blue}\boldsymbol{c}}_3[1]-{\color{red!50!black}\boldsymbol{v}}_2[1]) + ({\color{red!50!black}\boldsymbol{v}}_2[2]-{\color{blue}\boldsymbol{c}}_3[2]) <~& ({\color{red!50!black}\boldsymbol{v}}_2[1]-{\color{blue}\boldsymbol{c}}_2[1]) + ({\color{red!50!black}\boldsymbol{v}}_2[2]-{\color{blue}\boldsymbol{c}}_2[2])\nonumber\\ & \Leftrightarrow & {\color{blue}\boldsymbol{c}}_2[1]+{\color{blue}\boldsymbol{c}}_2[2]+{\color{blue}\boldsymbol{c}}_3[1]-{\color{blue}\boldsymbol{c}}_3[2] <~& 2{\color{red!50!black}\boldsymbol{v}}_2[1].\tag{26}\\[1ex] && \|{\color{blue}\boldsymbol{c}}_3-{\color{red!50!black}\boldsymbol{v}}_4 \|_1 = ({\color{blue}\boldsymbol{c}}_3[1]-{\color{red!50!black}\boldsymbol{v}}_4[1]) + |{\color{blue}\boldsymbol{c}}_3[2]-{\color{red!50!black}\boldsymbol{v}}_4[2]| <~& ({\color{red!50!black}\boldsymbol{v}}_4[1]-{\color{blue}\boldsymbol{c}}_2[1]) + ({\color{blue}\boldsymbol{c}}_2[2]-{\color{red!50!black}\boldsymbol{v}}_4[2]) = \|{\color{blue}\boldsymbol{c}}_2-{\color{red!50!black}\boldsymbol{v}}_4 \|_1\nonumber\\ &\Rightarrow & ({\color{blue}\boldsymbol{c}}_3[1]-{\color{red!50!black}\boldsymbol{v}}_4[1]) + ({\color{blue}\boldsymbol{c}}_3[2]-{\color{red!50!black}\boldsymbol{v}}_4[2]) <~& ({\color{red!50!black}\boldsymbol{v}}_4[1]-{\color{blue}\boldsymbol{c}}_2[1]) + ({\color{blue}\boldsymbol{c}}_2[2]-{\color{red!50!black}\boldsymbol{v}}_4[2])\nonumber\\ & \Leftrightarrow & {\color{blue}\boldsymbol{c}}_2[1]-{\color{blue}\boldsymbol{c}}_2[2]+{\color{blue}\boldsymbol{c}}_3[1]+{\color{blue}\boldsymbol{c}}_3[2] <~& 2{\color{red!50!black}\boldsymbol{v}}_4[1].\tag{27} \end{align}\] Adding up 24 –27 , we obtain that \({\color{blue}\boldsymbol{c}}_2[1]+{\color{blue}\boldsymbol{c}}_3[1]< {\color{blue}\boldsymbol{c}}_1[1]+{\color{blue}\boldsymbol{c}}_4[1]\), a contradiction to 23 –22 .

In summary, we show that it is not possible to find a -Manhattan embedding for profile \({\cal P}_{\thevfivecounter}\). ◻

Proof. Since the Manhattan property is monotone, to show the statement, we only need to look at profiles which have either \(3\) voters and \(5\) alternatives, or \(4\) voters and \(4\) alternatives. We achieve this by using a computer program employing the CPLEX solver that exhaustively searches for all possible profiles with either \(3\) voters and \(5\) alternatives, or \(4\) voters and \(4\) alternatives, and provide a -Manhattan embedding for each of them. Since the CPLEX solver accepts constraints on the absolute value of the difference between any two variables, our computer program is a simple one-to-one translation of the -Manhattan constraints given in 1, without any integer variables. Peters [25] has noted a similar formulation for -Manhattan embeddings. The same program can also be used to show that the preference profiles from the examples 4, 5 and 6 do not admit a -Manhattan embedding.

Following a similar line as in the work of [16], we did some optimization to significantly shrink the search space on all profiles: We only consider profiles with distinct preference orders and we assume that one of the preference orders is \(1 \succ \dots \succ m\). Hence, the number of relevant profiles with \(n\) voters and \(m\) alternatives is \(\binom{m!-1}{n-1}\). For \((n,m) = (3,5)\) and \((n,m)=(4,4)\), we need to iterate through \(7021\) and \(1771\) profiles, respectively. We implemented a program which, for each of these produced profiles, uses the IBM ILOG CPLEX optimization software package to check and find a -Manhattan embedding. The verification is done by going through each voter’s preference order and checking the condition given in 1. All generated profiles, together with their -Manhattan embeddings and the distances used for the verification, are available at https://owncloud.tuwien.ac.at/index.php/s/s6t1vymDOx4EfU9.  ◻

Proof. By the characterization of the single-peakedness from [28], we know that every minimally non-single-peakedprofile consists of either \(3\) voters and \(3\) alternatives, or \(2\) voters and \(4\) alternatives. By 1 2 every profile with \(3\) voters and \(3\) alternatives, or \(2\) voters and \(4\) alternatives is -Manhattan. This proves Statement [lem:minspsc1].

By the characterization of the single-crossingness from [33], we know that every smallest non-single-crossing profiles has \(3\) voters and \(3\) alternatives. Moreover, the following profile is neither single-peaked nor single-crossing [28], [33], but it is -Manhattan by 2: \[\begin{align} {\cal P}_{\thevsixcounter} \colon & v_1 \colon 1 \succ 2 \succ 3, \\ & v_2 \colon 2 \succ 3 \succ 1, \\ & v_3 \colon 3 \succ 1 \succ 2. \end{align}\]This proves Statements [lem:minspsc2] and [lem:minspsc3]. ◻

Proof. Assume that a profile \({\cal P}= ({\cal V}, {\cal A}, {\cal R})\) has a -Max embedding \(E\).

For every dimension \(i \in [d]\), create the linear order \(\triangleright_i\) by ordering the alternatives along their \(i\)-coordinate. In the case of a tie, order the alternatives arbitrarily. In the resulting linear order \(\triangleright_i\), for every \(a_j, a_{k} \in {\cal A}\), if \(a_j \triangleright_i a_{k}\) then \(E(a_j)[i] \leq E(a_{k})[i]\). Let \(\overrightarrow{\triangleright}= (\triangleright_1, \dots, \triangleright_d)\).

Now we show \({\cal P}\) is -dimensional single-peaked wrt.linear orders \(\overrightarrow{\triangleright}\). Let \(a, b, c \in {\cal A}\) be an arbitrary triple of alternatives such that \(b \in \mathsf{BB}(a, c,\) \(\overrightarrow{\triangleright})\). By definition for every dimension \(i \in [d]\), we have that \(E(a)[i] \le E(b)[i] \le E(c)[i]\) or \(E(c)[i] \le E(b)[i] \le E(a)[i]\) and thus \(E(b) \in \mathsf{BB}(E(a), E(c))\). By 5 there cannot be a voter \(v_i \in {\cal V}\) such that \(\{a, c\} \succ_i b\). As this holds for an arbitrary triple with \(a \overrightarrow{\triangleright}b \overrightarrow{\triangleright}c\), \({\cal P}\) is -dimensional single-peaked wrt.\(\overrightarrow{\triangleright}\). ◻

Proof. Assume that a profile \(\mathcal{P} = ({\cal V}, {\cal A}, {\cal R})\) has a -Manhattan embedding \(E\).

The idea of the proof relies on the fact that on \(\mathbb{R}^{d}\)under \(1\)-norm the distance of a point \(\boldsymbol{x}\) from a point \(\boldsymbol{p}\) is given by \(\sum_{i = 1}^d |\boldsymbol{x}[i] - \boldsymbol{p}[i]|\). There are \(2^d\) ways to break the absolute values in the formula, giving us \(2^d\) possible formulas for the distance, and consequently \(2^d\) values that are contributed by \(\boldsymbol{x}\) to the equation. For example, in 2-dimensions, the possible values contributed by \(\boldsymbol{x}\) are given by the following four formulae: \[\boldsymbol{x}[1] + \boldsymbol{x}[2], \quad \boldsymbol{x}[1] - \boldsymbol{x}[2], \quad -\boldsymbol{x}[1] + \boldsymbol{x}[2],\quad \text{ and } \quad-\boldsymbol{x}[1] - \boldsymbol{x}[2].\] We will show that if the value contributed by one point is between the values contributed by two other points according to each of these formulas, then this point cannot be further from \(\boldsymbol{p}\) than both of the two other points. This way we obtain \(2^d\) axes. Moreover, we can observe that each of these formulae has another formula that is its negation and vice versa: for example \(\boldsymbol{x}[1] + \boldsymbol{x}[2]\) and \(-\boldsymbol{x}[1] - \boldsymbol{x}[2]\). We only need to keep one formula for each of these pairs, because negating a formula does not change whether one value is between two others according to it. This way we obtain \(2^{d-1}\) axes.

We proceed to the formal proof. Let \(\Pi = \{-1, 1\}^{d - 1}\) be the set of all (\(d-1\))-dimensional \((-1, 1)\)-vectors. We create an axis for each of these vectors. Observe that \(|\Pi| = 2^{d-1}\).

For every \(\sigma \in \Pi\), let \(S_{\sigma} \colon {\cal V}\cup {\cal A}\to \mathbb{R}\) with \(S_{\sigma}(x) = \left( \sum_{z \in 1}^{d - 1} \sigma[z] \cdot E(x)[z]\right) + E(x)[d]\). Create axis \(\triangleright_{\sigma}\) by ordering every alternative \(i \in {\cal A}\) non-decreasingly by \(S_{\sigma}(i)\). Break the ties arbitrarily. That is, for every \(a_j, a_{k} \in {\cal A}\), if \(a_j \triangleright_{\sigma} a_{k}\) then \(S_{\sigma}(j) \leq S_{\sigma}(k)\). Let \(\overrightarrow{\triangleright}= (\triangleright_{\sigma})_{\sigma \in \Pi}\).

Now we show \({\cal P}\) is -dimensional single-peaked wrt.\(\overrightarrow{\triangleright}\). Let \(a, b, c \in {\cal A}\) be an arbitrary triple of alternatives such that \(b \in \mathsf{BB}(a, c,\) \(\overrightarrow{\triangleright})\). Assume, towards a contradiction, that there is a voter \(v_i \in {\cal V}\) such that \(\{a, c\} \succ_i b\).

We proceed in two cases.

Case 1:

\(E(v)[d] \leq E(b)[d]\). Consider the following linear order \(\sigma' \in \Pi\): For every \(z \in [d - 1]\), if \(E(b)[z] \geq E(v)[z]\), then \(\sigma'[z] \mathrel{\vcenter{:}}= 1\), otherwise \(\sigma'[z] \mathrel{\vcenter{:}}= - 1\).

We obtain that \[\begin{align} \|E(v) - E(b) \|_1 &= \sum_{z = 1}^{d}|E(v)[z] - E(b)[z]| = \left(\sum_{z = 1}^{d - 1}|E(b)[z] - E(v)[z]|\right) + E(b)[d] - E(v)[d]\\ & = \left(\sum_{z = 1}^{d - 1}\sigma'[z]\cdot (E(b)[z] - E(v)[z]) \right) + E(b)[d] - E(v)[d] = S_{\sigma'}(b) - S_{\sigma'}(v). \end{align}\] By assumption that \(b \in \mathsf{BB}(a, c, \overrightarrow{\triangleright})\), there must be an \(x \in \{a, c\}\) such that \(S_{\sigma'}(b) \leq S_{\sigma'}(x)\). We obtain that \[\begin{align} S_{\sigma'}(b) - S_{\sigma'}(v) &\leq S_{\sigma'}(x) - S_{\sigma'}(v) =\left(\sum_{z = 1}^{d - 1}\sigma'[z]\cdot(E(x)[z] - E(v)[z])\right) + E(x)[d] - E(v)[d]\\ &\leq \left(\sum_{z = 1}^{d - 1}|(E(x)[z] - E(v)[z]|\right) + |E(x)[d] - E(v)[d]|\\ & = \|E(v) - E(x) \|_1. \end{align}\] Thus \(\|E(v) - E(b) \|_1 \leq \|E(v) - E(x) \|_1\). Since \(E\) is -Manhattan embedding, this contradicts \(\{a, c\}\succ_i b\).

Case 2:

\(E(v)[d] > E(b)[d]\). Consider the following linear order \(\sigma' \in \Pi\): For every \(z \in [d - 1]\), if \(E(b)[z] \geq E(v)[z]\), then \(\sigma'[z] \mathrel{\vcenter{:}}= -1\), otherwise \(\sigma'[z] \mathrel{\vcenter{:}}= 1\). Observe this is the opposite of Case 1.\[\begin{align} \|E(v) - E(b) \|_1 &= \sum_{z = 1}^{d}|E(v)[z] - E(b)[z]| = \left(\sum_{z = 1}^{d - 1}|E(b)[z] - E(v)[z]|\right) + E(v)[d] - E(b)[d]\\ & = \left(\sum_{z = 1}^{d - 1}\sigma'[z] \cdot (E(v)[z] - E(b)[z])\right) + E(v)[d] - E(b)[d] = S_{\sigma'}(v) - S_{\sigma'}(b). \end{align}\]

By construction, there must be an \(x \in \{a, c\}\) such that \(S_{\sigma'}(b) \geq S_{\sigma'}(x)\). We obtain that \[\begin{align} S_{\sigma'}(v) - S_{\sigma'}(b) \leq S_{\sigma'}(v) - S_{\sigma'}(x) & = \left(\sum_{z = 1}^{d - 1}\sigma'[z] \cdot (E(v)[z] - E(x)[z])\right) + E(v)[d] - E(x)[d]\\ &\leq \left(\sum_{z = 1}^{d - 1}|(E(x)[z] - E(v)[z]|\right) + |E(x)[d] - E(v)[d]|\\ & = \|E(v) - E(x) \|_1. \end{align}\]

Thus \(\|E(v) - E(b) \|_1 \leq \|E(v) - E(x) \|_1\). Since \(E\) is -Manhattan embedding, this contradicts \(\{a, c\}\succ_i b\).

As both cases lead to a contradiction, this concludes the proof. ◻

Proof. By [33], the number of voters a single-crossing profile on \(4\) alternatives may have is at most \(\frac{(4-1)4}{2} + 1 = 7\). We verify computationally that all single-crossing profiles with \(4\) alternatives and \(7\) voters, \(5\) alternatives and \(4\) voters, and \(6\) alternatives and \(3\) voters, are -Manhattan. All generated profiles, together with their -Manhattan embeddings and the distances used for the verification, are available at https://owncloud.tuwien.ac.at/index.php/s/s6t1vymDOx4EfU9.

We proceed to show the numbers of voters given in Statements [thm:smallest95SC95non2man:6alt] and [thm:smallest95SC95non2man:5alt] are indeed minimal:

The remaining part of Statement [thm:smallest95SC95non2man:6alt]. The profile \({\cal P}_{\thevsevencounter}\) from 7 is single-crossing along the linear order \(v_1 \triangleright v_2 \triangleright v_3 \triangleright v_4\). However, we will show that it is not -dimensional single-peaked. By the contrapositive of 5, this implies it is not -Manhattan.

To show that \({\cal P}_{\thevsevencounter}\) is not -dimensional single-peaked, assume, towards a contradiction, that \({\cal P}_2\) is -dimensional single-peaked wrt.a pair of linear orders \((\triangleright_1, \triangleright_2)\).

We first observe that the reasoning of 6 can be used to show analogous statement on -dimensional single-peaked profiles:

We can deduce from the definition of -dimensional single-peakedness (7) that for every triple \((a, b, c)\) of alternatives, if there is a voter satisfying \(\{b, c\} \succ a\), then \(a \notin \mathsf{BB}(b, c, (\triangleright_1, \triangleright_2))\). We observe that for every triple in \(\{1,2,4,5,6\}\), the only triples \((a,b,c)\) that do not have a voter such that \(\{b,c\} \succ a\) are \((2, 1,4)\) and by symmetry \((2,4,1)\). Also observe that the alternatives \(1,4,5\), and \(6\) all have a voter who places them last, so it is sufficient to consider triples where \(a = 2\).

Moreover, by 3, there must be three alternatives \(a,b,c \in \{1,2,4,5,6\}\) such that \(a \in \mathsf{BB}(b,c, (\triangleright_1, \triangleright_2))\). Thus it must be that \(2 \in \mathsf{BB}(1,4,(\triangleright_1, \triangleright_2))\). Through identical reasoning on the set \(\{1,3,4,5,6\}\) we must have \(3 \in \mathsf{BB}(1,4,(\triangleright_1, \triangleright_2))\).

Without loss of generality, assume that \(1 \triangleright_i \{2,3\} \triangleright_i 4\) for \(i \in [2]\).

Now let us consider the order of \(2\) and \(3\) on \(\triangleright_1\) and \(\triangleright_2\). If \(1 \triangleright_i 2 \triangleright_i 3 \triangleright_i 4\) for every \(i \in [2]\), then \(2 \in \mathsf{BB}(1,3,(\triangleright_1, \triangleright_2))\) and the preferences of the voter \(v_3 \colon \{1, 3\} \succ 2\) lead to a contradiction. If \(1 \triangleright_i 3 \triangleright_i 2 \triangleright_i 4\) for every \(i \in [2]\), then \(3 \in \mathsf{BB}(1,2, (\triangleright_1, \triangleright_2))\) and the preferences of the voter \(v_2 \colon \{1, 2\} \succ 3\) lead to a contradiction. Thus one linear order must have \(2\) before \(3\) and the other \(3\) before \(2\). Without loss of generality, assume \(1 \triangleright_1 2 \triangleright_1 3 \triangleright_1 4\) and \(1 \triangleright_2 3 \triangleright_2 2 \triangleright_2 4\). We depict this in 16.

Next, we wish to place alternative \(6\) on the linear orders. Let us proceed with case distinction.

Case 1: \(6 \triangleright_1 2\).

If \(6 \triangleright_2 2\) as well, then \(2 \in \mathsf{BB}(4,6,(\triangleright_1, \triangleright_2))\), a contradiction to voter \(v_4\) satisfying \(\{4, 6\} \succ 2\). If \(2 \triangleright_2 6\), then \(2 \in \mathsf{BB}(3,6,(\triangleright_1, \triangleright_2))\), a contradiction to \(v_4\) satisfying \(\{3, 6\} \succ 2\).

Case 2: \(2 \triangleright_1 6 \triangleright_1 3\).

If \(6 \triangleright_2 3\), then \(3 \in \mathsf{BB}(4,6,(\triangleright_1, \triangleright_2))\), a contradiction to \(v_4\) satisfying \(\{4, 6\} \succ 3\). If \(3 \triangleright_2 6 \triangleright_2 2\), we have \(6 \in \mathsf{BB}(2,3,(\triangleright_1, \triangleright_2))\), a contradiction to \(v_1\) satisfying \(\{2, 3\} \succ 6\). If \(2 \triangleright_2 6\), we have \(2 \in \mathsf{BB}(1,6,(\triangleright_1, \triangleright_2))\), a contradiction to \(v_3\) satisfying \(\{1, 6\} \succ 2\).

Case 3: \(3 \triangleright_1 6\).

If \(6 \triangleright_2 3\), then \(3 \in \mathsf{BB}(2,6,(\triangleright_1, \triangleright_2))\), a contradiction to \(v_2\) satisfying \(\{2, 6\} \succ 3\). If \(3 \triangleright_2 6\), then \(3 \in \mathsf{BB}(1,6,(\triangleright_1, \triangleright_2))\), a contradiction to \(v_2\) satisfying \(\{1, 6\} \succ 3\).

As all cases lead to a contradiction, \({\cal P}_{\thevsevencounter}\) cannot be -dimensional single-peaked.

The remaining part of Statement [thm:smallest95SC95non2man:5alt]. The profile \({\cal P}_{\theveightcounter}\) from 7 is not -Manhattan by Theorem 3 from Escoffier et al. [20] as it has more than \(4\) distinct last choices; intuitively, since circles in -Manhattan space are squares parallel to the coordinate axes rotated by 45 degrees, every alternative who is least preferred by one of the voters must be extremal along one the rotated coordinate axes, and there only four possible extrema. However, the profile is single-crossing wrt.the linear order \(v_1 \triangleright v_2 \triangleright v_3 \triangleright v_4 \triangleright v_5\). ◻

Proof. Consider a single-peaked profile with \(19\) alternatives. Given a single-peaked order, there are \(2^{19-1}=262144\) possible voters with pairwise disjoint preference orders [34]. However, the proof of Theorem 4 from Escoffier et al. [20] implies that a -Manhattan profile with \(19\) alternatives has at most \(6 \cdot (19 \cdot(19-1)/2)^2 = 175446\) pairwise disjoint preference orders. Thus the single-peaked profile with \(19\) alternatives and all the possible disjoint voters is single-peaked but not -Manhattan. ◻

Proof. We prove this by induction.

Base case: \(d = 2\).

Chen et al. [16] show that any single-peaked profile with two voters is -Euclidean and thus -Max. This proves the base case.

Inductive step.

Assume that every profile with \(n - 1\) voters, two of which are single-peaked, is -Max. We show that any profile with \(n\) voters is -Max.

Intuitively, we reuse the embedding from the inductive assumption and embed the remaining \(n^{th}\) voter in the \((n-1)^{th}\) dimension in such a way that each alternative is equally far from her. Then we slightly tweak the positions of the alternatives in such a way that the previous voters’ preferences are unchanged, but we embed the preferences of the \(n^{th}\) voter.

Let \({\cal P}= ({\cal V}= \{v_1, \dots, v_n\}, {\cal A}= [m], {\cal R})\) be a profile with \(n\) voters. Without loss of generality, assume \(v_1\) and \(v_2\) are single-peaked wrt.some linear order.

By inductive assumption \({\cal P}\) restricted to the first \(n-1\) voters is -Max. Let \(F\) be the embedding of \(({\cal V}\setminus \{v_n\}, [m], \{\succ_1, \dots, \succ_{n-1}\})\) to \(\mathbb{R}^{n-2}\). Without loss of generality, assume that \(F(x)[k] \geq 0\) for every \(x \in {\cal A}\cup {\cal V}\setminus \{v_n\}, k \in [n - 2]\). If not, we can shift the embedding so that this holds.

We choose a constant \(\epsilon > 0\) to be smaller than the smallest difference in distances between a voter and two alternatives in \(F\), divided by the number of alternatives. Formally, let \(\epsilon < \min_{\substack{i,j \in {\cal A}\\ v_k \in {\cal V}\setminus \{v_n\}}}\frac{\displaystyle|\|F(i) - F(v_k) \|_{\infty} - \|F(j) - F(v_k) \|_{\infty}|}{\displaystyle m}\). Because the preferences are strict, it holds that \(|\|F(i) - F(v_k) \|_{\infty} - \|F(j) - F(v_k) \|_{\infty}| > 0\) for every \(i,j \in {\cal A}, v_k \in {\cal V}\setminus \{v_n\}\).

Now let us define -Max embedding \(E\) as follows: For every \(i \in {\cal A}\) let \[E(i) = (F(i)[1], \dots, F(i)[n - 2], \epsilon \cdot \mathsf{rk}_n( i)).\]

For every \(k \in [n - 1]\), let \[E(v_k) = (F(i)[1], \dots, F(i)[n - 2], 0).\] Let \(M = \max_{\substack{i \in {\cal A}\\ z \in [n - 2]}}\{F(i)[z]\}\). Let \(E(v_n) = (0, \dots, 0, -M)\).

It remains to show that \(E\) is an -Max-embedding. Let \(i, j \in {\cal A}\) be two arbitrary alternatives, and \(v_k \in {\cal V}\) a voter such that \(v_k \colon i \succ j\).
Case 1: \(v_k \in \{v_1, \dots, v_{n-1}\}\).

Note that for every \(i' \in {\cal A}\) we have that \[\begin{align} \|E(i') - E(v_k) \|_{\infty} &= \max_{\ell \in [n - 1]}\{|E(i')[\ell] - E(v_k)[\ell]|\} = \max\left \{\max_{\ell \in [n - 2]}\{|F(i')[\ell] - F(v_k)[\ell]|\}, | \epsilon \cdot \mathsf{rk}(v_n, i)|\right\}\\ &= \max\{\|F(i') - F(v_k) \|_{\infty}, \epsilon \cdot \mathsf{rk}_n( i')\}. \end{align}\]

We know by our choice of \(\epsilon\) that \(\|F(j) - F(v_k) \|_{\infty} -\|F(i) - F(v_k) \|_{\infty}> \epsilon m\).

We proceed in three cases:

Case 1.a: \(\|F(i) - F(v_k) \|_{\infty} < \epsilon \cdot \mathsf{rk}(v_n, i)\).

We must have that \(\|F(j) - F(v_k) \|_{\infty} > \epsilon m\) and therefore \[\|E(j)- E(v_k) \|_{\infty} - \|E(i), E(v_k) \|_{\infty} = \|F(j) - F(v_k) \|_{\infty} - \epsilon m > 0,\] as required.

Case 1.b: \(\|F(j) - F(v_k) \|_{\infty} < \epsilon \cdot \mathsf{rk}(v_n, i)\).

This case is impossible, because \(\|F(j) - F(v_k) \|_{\infty} - \epsilon m> \|F(i) - F(v_k) \|_{\infty} \geq 0\).

Case 1.c: Otherwise.

We have \[\begin{align} \|E(j) - &E(v_k) \|_{\infty} - \|E(i) - E(v_k) \|_{\infty} = \|F(j) - F(v_k) \|_{\infty} - \|F(i) - F(v_k) \|_{\infty} > 0, \end{align}\] as required, because \(F\) is a -Max embedding.

Case 2: \(v_k = v_n\).

Note that for each \(i' \in {\cal A}\), we have that \[\begin{align} \|E(i') - E(v_n) \|_{\infty} &= \max_{z \in [n - 1]}[|E(i')[z] - E(v_n)[z]|] = \max\left\{\max_{z \in [n - 1]}\{|F(i')[z]]\}, M + \epsilon \cdot \mathsf{rk}_n( i')\right\}\\ &= M + \epsilon \cdot \mathsf{rk}_n( i'), \end{align}\]

where the last equality holds by our choice of \(M\). This is clearly linear in the ranks, thus proving the statement.
Because \(\|E(j) - E(v_k) \|_{\infty} > \|E(i) - E(v_n) \|_{\infty}\) holds for every \(v_k \in {\cal V}, i, j \in {\cal A}\) such that \(v_k \colon i \succ j\), \(E\) is a -Max embedding of \({\cal P}\). ◻

Proof. 1 8 directly imply that any profile on three voters, two of which are single-peaked, is -Manhattan.

To see that the reverse direction does not hold, consider the profile \[\begin{align} v_1 \colon 1 \succ 2 \succ 3 \succ 4 \succ 5,\; v_2 \colon 5 \succ 4 \succ 1 \succ 3 \succ 2,\; v_3 \colon 5 \succ 4 \succ 2 \succ 3 \succ 1. \end{align}\]

By the result of [28] any profile that contains four alternatives \(a, b, c, d\) and two voters \(u, w\) such that \[\begin{align} u \colon a \succ b \succ c, d \succ b \text{~ and ~} w \colon c \succ b \succ a, d \succ b \end{align}\] is not single-peaked.

To show \(v_1, v_2\) are not single-peaked, rename \((2, 3, 4, 1) \mathrel{\vcenter{:}}= (a, b, c, d)\) and \((v_1, v_2) \mathrel{\vcenter{:}}= (u,w)\). To show \(v_1, v_3\) are not single-peaked, rename \((1, 3, 4, 2) \mathrel{\vcenter{:}}= (a, b, c, d)\) and \((v_1, v_3) \mathrel{\vcenter{:}}= (u,w)\). To show \(v_2, v_3\) are not single-peaked, rename \((1, 3, 2, 5) \mathrel{\vcenter{:}}= (a, b, c, d)\) and \((v_2, v_3) \mathrel{\vcenter{:}}= (u,w)\).

As this profile has \(3\) voters and \(5\) alternatives, it is -Manhattan by 2. ◻