The one-dimensional Euclidean domain: finitely many obstructions are not enough

Abstract

We show that one-dimensional Euclidean preference profiles can not be characterized in terms of finitely many forbidden substructures. This result is in strong contrast to the case of single-peaked and single-crossing preference profiles, for which such finite characterizations have been derived in the literature.

1 Introduction

Single-peakedness, single-crossingness, and one-dimensional Euclideanness are popular domain restrictions that show up in a variety of models in the social sciences and economics. In many situations, these domain restrictions guarantee the existence of a desirable entity that would not exist without the restriction, as for instance a strategy-proof collective choice rule, or a Condorcet winner, or an equilibrium point.

• Preferences are single-peaked, if there exists a linear ordering of the alternatives such that any voter’s preference relation along this ordering is either always increasing, always decreasing, or first increasing and then decreasing.

• Preferences are single-crossing, if there exists a linear ordering of the voters such that for any pair of alternatives along this ordering, there is a single spot where the voters switch from preferring one alternative above the other one.

• Preferences are one-dimensional Euclidean, if there exists a common embedding of voters and alternatives into the real numbers, such that every voter prefers alternatives that are embedded close to him to alternatives that are embedded farther away from him.

Single-peakedness goes back to the seminal work of Black (1948); among many other nice consequences, single-peakedness implies transitivity (Inada 1969) and non-manipulability of the majority rule (Moulin 1980).

Single-crossingness goes back to the work of Karlin (1968) in applied mathematics; Mirrlees (1971) and Roberts (1977) apply it in the theory of optimal income taxation, and Diamond and Stiglitz (1974) use it in the economics of uncertainty. Single-crossingness also plays a role in coalition formation (Demange 1994; Kung 2006), income redistribution (Meltzer and Richard 1981), local public goods and stratification (Westhoff 1977; Epple and Platt 1998), in the choice of constitutional voting rules (Barberà and Jackson 2004), and in the analysis of the majority rule (Grandmont 1978; Gans and Smart 1996).

One-dimensional Euclidean preference structures go back to Hotelling (1929). They have been discussed by Coombs (1964) under the name ‘unidimensional unfolding’ representations, and they unite all the good properties of single-peaked and single-crossing preference structures. Doignon and Falmagne (1994) discuss Euclidean preference structures in the context of behavioral sciences, and Brams et al. (2002) discuss them in the context of coalition formation.

Obstructions The scientific literature contains many characterizations of combinatorial objects in terms of forbidden substructures or obstructions. For instance, Kuratowski’s theorem Kuratowski (1930) characterizes planar graphs in terms of two obstructions: a graph is planar if and only if it does not contain a subdivided $K_5$ or $K_{3,3}$. In a similar spirit, Lekkerkerker and Boland (1962) characterize interval graphs through five (infinite) families of forbidden induced subgraphs, and Földes and Hammer (1977) characterize split graphs in terms of three forbidden induced subgraphs. Hoffman et al. (1985) characterize totally-balanced 0–1-matrices in terms of certain forbidden submatrices. The characterizations of split graphs and totally-balanced 0–1-matrices use a finite number of obstructions, while the characterizations of planar graphs and interval graphs both involve infinitely many obstructions.

In the area of social choice, Ballester and Haeringer (2011) characterize single-peaked preference profiles and group-separable preference profiles in terms of a small finite number of obstructions. Also single-crossing preference profiles allow a characterization by finitely many obstructions; see Bredereck et al. (2013). Let us stress that every monotone property of profiles (that is, every property that is preserved under the removal of voters and/or alternatives) can be characterized by a set of obstructions. For many monotone properties, however, the obstruction set will contain an infinite number of obstructions. Condorcet winners in tournaments form a typical (non-monotone) example of a property in social choice that can not be characterized at all through obstructions.

A characterization by finitely many obstructions has many positive consequences. Whenever a family ${\mathcal {F}}$ of combinatorial objects allows such a finite characterization, this directly implies the existence of a polynomial time algorithm for recognizing the members of ${\mathcal {F}}$: one may simply work through the obstructions one by one, and check whether the considered object contains the obstruction. By looking deeper into the combinatorial structure of such families ${\mathcal {F}}$, one usually manages to find recognition algorithms that are much faster than this simple approach. As an example, there exist sophisticated algorithms for recognizing single-peaked preference profiles that are due to Bartholdi and Trick (1986), Doignon and Falmagne (1994), and Escoffier et al. (2008). Also single-crossingness can be recognized very efficiently; see Doignon and Falmagne (1994), Elkind et al. (2012), and Bredereck et al. (2013).

As another positive consequence, a characterization by finitely many obstructions often helps us in understanding the algorithmic and combinatorial behavior of family ${\mathcal {F}}$. For example, Bredereck et al. (2016) investigate the problem of deciding whether a given preference profile is close to a nicely structured preference profile. The distance is measured by the number of voters or alternatives that have to be deleted from the given profile so as to reach a nicely structured profile. For the cases where ‘nicely structured’ means single-peaked or single-crossing, the proofs in Bredereck et al. (2016) are heavily based on characterizations (Ballester and Haeringer 2011; Bredereck et al. 2013) by finitely many obstructions. Elkind and Lackner (2014) study similar questions and derive approximation algorithms for the number of deleted voters or alternatives. All results in Elkind and Lackner (2014) are centered around preference profiles that can be characterized by a finite number of obstructions, and some of the theorems are parametrized by the obstruction set.

Scope and contribution of this paper As the one-dimensional Euclidean profiles form a special case of single-peaked and single-crossing profiles (see Sect. 2.3 for more information on this), every obstruction to single-peakedness and every obstruction to single-crossingness will automatically also form an obstruction to one-dimensional Euclideanness. Now the question arises: “Are there any further obstructions to one-dimensional Euclideanness?” To which Coombs (1964) answered back in 1964: “Yes, there are!” (again, see Sect. 2.3 for more information). This immediately takes us to another question: “Is there a characterization of one-dimensional Euclideanness in terms of finitely many obstructions?” The answer to this second question is negative, as we are going to show in this paper.

To this end, we construct an infinite sequence of preference profiles that satisfy two crucial properties. First, none of these profiles is one-dimensional Euclidean. Secondly, every profile just barely violates one-dimensional Euclideanness, as the deletion of an arbitrary voter immediately makes the profile one-dimensional Euclidean. The second property implies that each profile in the sequence is on the edge of being Euclidean, and that the reason for its non-Euclideanness must lie in its overall structure. In other words each of these infinitely many profiles yields a separate obstruction for one-dimensional Euclideanness, and this is exactly what we want to establish.

The definition of the infinite profile sequence and the resulting analysis are quite involved. Ironically, the complexity of our proof is a consequence of the very statement we are going to prove. As part of our proof, we have to argue that the deletion of an arbitrary voter from an arbitrary profile in the sequence yields a one-dimensional Euclidean profile. Now if there were a characterization of one-dimensional Euclideanness by finitely many obstructions, then this argument would be relatively easy to get through: we could simply analyze the preference structure and show that the deletion of any voter removes all obstructions. But unfortunately, such a characterization does not exist. The only viable (and fairly tedious) approach is to explicitly specify the corresponding Euclidean representations (one representation per deleted voter!) and to prove by case distinctions that each such representation correctly encodes the preferences of all the remaining voters.

Organization of the paper In Sect. 2 we summarize the central definitions, state useful observations, and provide some examples. In Sect. 3 we formulate our main results in Theorems 3.1 and 3.2, and we show how Theorem 3.2 follows from Theorem 3.1. The five Sects. 4 through 8 present the long and technical proof of Theorem 3.1. Section 9 completes the paper with a short discussion.

2 Definitions, notations, and examples

Let $1,\ldots ,m$ be m alternatives and let $v_1,\ldots ,v_n$ be n voters. A preference profile specifies the preference orderings of the voters, where voter $v_i$ ranks the alternatives according to a strict linear order $\succ _i$. For alternatives a and b, the relation $a\succ _i b$ means that voter $v_i$ strictly prefers a to b. If the meaning is clear from the context, we will sometimes simply write $\succ$ instead of $\succ _i$ and suppress the dependence on i. A profile with n voters and m alternatives will be called an $n\times m$ profile.

2.1 Single-peaked profiles

A linear ordering of the alternatives is single-peaked with respect to a fixed voter $v_i$, if the preferences of $v_i$ taken along this ordering have a single local maximum. A preference profile is single-peaked, if it allows an ordering of the alternatives that is single-peaked with respect to every voter.

Note that for every single-peaked permutation $\pi (1),\pi (2),\ldots ,\pi (m)$ of the alternatives, also the reverse permutation $\pi (m),\ldots ,\pi (2),\pi (1)$ is single-peaked. The following proposition states a characterization of single-peakedness in terms of finitely many obstructions.

Proposition 2.1

(Ballester and Haeringer 2011) A preference profile is single-peaked, if and only if it avoids the following two obstructions. The first obstruction is a $3\times 3$ profile with alternatives a, b, c:

Voter  $v_1$:  $\{b,c\}\succ _1 a$

Voter  $v_2$:  $\{a,c\}\succ _2 b$

Voter  $v_3$:  $\{a,b\}\succ _3 c$

The second obstruction is a $2\times 4$ profile with alternatives a, b, c, d:

Voter  $v_1$:  $a\succ _1 b\succ _1 c$  and  $d\succ _1 b$

Voter  $v_2$:  $c\succ _2 b\succ _2 a$  and  $d\succ _2 b$

2.2 Single-crossing profiles

A linear ordering of the voters is single-crossing with respect to two alternatives a and b, if the ordered list of voters can be partitioned into an initial piece and a final piece such that all voters in the initial piece have the same relative ranking of a and b, while all voters in the final piece rank them in the opposite way. A preference profile is single-crossing, if it allows an ordering of the voters that is single-crossing with respect to every possible pair of alternatives.

The following proposition states a characterization of single-crossingness in terms of finitely many obstructions.

Proposition 2.2

(Bredereck et al. 2013) A preference profile is single-crossing, if and only if it avoids the following two obstructions. The first obstruction is a $3\times 6$ profile with (not necessarily distinct) alternatives a, b, c, d, e, f:

Voter  $v_1$:  $b\succ _1 a$  and  $c\succ _1 d$  and  $e\succ _1 f$

Voter  $v_2$:  $a\succ _2 b$  and  $d\succ _2 c$  and  $e\succ _2 f$

Voter  $v_3$:  $a\succ _3 b$  and  $c\succ _3 d$  and  $f\succ _3 e$

The second obstruction is a $4\times 4$ profile with (not necessarily distinct) alternatives a, b, c, d:

Voter  $v_1$:  $a\succ _1 b$  and  $c\succ _1 d$

Voter  $v_2$:  $a\succ _2 b$  and  $d\succ _2 c$

Voter  $v_3$:  $b\succ _3 a$  and  $c\succ _3 d$

Voter  $v_4$:  $b\succ _4 a$  and  $d\succ _4 c$

2.3 One-dimensional Euclidean profiles

Consider a common embedding of the voters and alternatives into the real number line, that assigns to every alternative j a real number $E[j]$ and that assigns to every voter $v_i$ a real number $F[i]$. A preference profile is one-dimensional Euclidean, if there exists such a common Euclidean representation of the voters and alternatives, such that for every voter $v_i$ and for every pair a and b of alternatives, $a\succ _i b$ holds if and only if the distance from $F[i]$ to $E[a]$ is strictly smaller than the distance from $F[i]$ to $E[b]$. In other words, small spatial distances from the point $F[i]$ indicate strong preferences of voter $v_i$.

It is well-known (and easy to see) that every one-dimensional Euclidean profile is simultaneously single-peaked and single-crossing: the left-to-right ordering of the alternatives along the Euclidean representation is single-peaked, and the left-to-right ordering of the voters along the Euclidean representation is single-crossing. Coombs (1964, page 91) discusses a $16\times 6$ preference profile that is both single-peaked and single-crossing, but fails to be one-dimensional Euclidean. The following example contains the smallest profile known to us that has these intriguing properties.

Example 2.3

Consider the following $3\times 6$ profile ${\mathcal {P}}$ (for the sake of readability, the preference orders are simply listed left to right from most preferred to least preferred alternative):

Voter  $v_1$:   3  2  1  4  5  6

Voter  $v_2$:   3  4  2  5  6  1

Voter  $v_3$:   5  4  3  6  2  1

This profile ${\mathcal {P}}$ is single-peaked with respect to the ordering 1, 2, 3, 4, 5, 6 of alternatives, and it is single-crossing with respect to the ordering $v_1,v_2,v_3$ of voters. Furthermore it can be shown by case distinctions that ${\mathcal {P}}$ is not one-dimensional Euclidean.

As the profile in Example 2.3 is single-peaked and single-crossing, it does not contain any of the obstructions listed in Propositions 2.1 and 2.2. Hence there must be some other obstruction contained in it, that is responsible for its non-Euclideanness. Example 2.3 and the $16\times 6$ profile of Coombs provide first indications that the obstructions for one-dimensional Euclideanness might be complex and intricate to analyze.

The following two propositions state simple observations that will be used repeatedly in our arguments.

Proposition 2.4

Let a and b be two alternatives in a Euclidean embedding (E, F) of some profile with $E[a]<E[b]$. Then voter $v_i$ prefers a to b if and only if $F[i]<\frac{1}{2}(E[a]+E[b])$, and he prefers b to a if and only if $F[i]>\frac{1}{2}(E[a]+E[b])$.

Proposition 2.5

Let a, b, c be three alternatives in a Euclidean embedding (E, F) of some preference profile with $E[a]<E[b]<E[c]$.

• If voter $v_i$ prefers $a\succ _i b$, then he also prefers $b\succ _i c$.

• If voter $v_i$ prefers $c\succ _i b$, then he also prefers $b\succ _i a$.

Finally, we mention that the (mathematical) literature on one-dimensional Euclidean preference profiles is scarce. Doignon and Falmagne (1994) and Knoblauch (2010) design polynomial time algorithms for deciding whether a given preference profile has a one-dimensional Euclidean representation. The approaches in Doignon and Falmagne (1994), Knoblauch (2010) are not purely combinatorial, as they are partially based on linear programming formulations.

3 Statement of the main results

In this section we formulate the two (closely related) main results of this paper. The first result is technical and states the existence of infinitely many non-Euclidean profiles that are minimal with respect to voter deletion.

Theorem 3.1

For any integer $k\ge 2$, there exists a preference profile ${\mathcal {P}}^*_k$ with $n=2k$ voters and $m=4k$ alternatives, such that the following holds.

• (a) Profile ${\mathcal {P}}^*_k$ is not one-dimensional Euclidean.

• (b) Profile ${\mathcal {P}}^*_k$ is minimal in the following sense: the deletion of an arbitrary voter from ${\mathcal {P}}^*_k$ yields a one-dimensional Euclidean profile.

The proof of Theorem 3.1 is long and will fill most of the rest of this paper. Here is a quick overview of this proof: Sect. 4 describes the profiles ${\mathcal {P}}^*_k$. Section 5 shows that every profile ${\mathcal {P}}^*_k$ satisfies property (a) in Theorem 3.1, while the three Sects. 6 through 8 establish property (b). Section 6 defines the underlying Euclidean representations, Sect. 7 lists a number of technical auxiliary statements, and Sect. 8 establishes the correctness of the Euclidean representations.

As an immediate consequence of Theorem 3.1, we derive our second main result (which essentially repeats the title of the paper) in the following theorem.

Theorem 3.2

One-dimensional Euclidean preference profiles can not be characterized in terms of finitely many obstructions.

Proof

Suppose for the sake of contradiction that such a characterization with finitely many obstructions would exist. Let t denote the largest number of voters in any obstruction, and consider a profile ${\mathcal {P}}^*_k$ from Theorem 3.1 with $k\ge t$. As ${\mathcal {P}}^*_k$ is not one-dimensional Euclidean by property (a), it must contain one of these finitely many obstructions with at most t voters. Pick such an obstruction. As profile ${\mathcal {P}}^*_k$ contains $2k>t+1$ voters, one of its voters is not involved in the obstruction. If we delete this voter, the resulting profile will still contain the obstruction; hence it is not one-dimensional Euclidean, which contradicts property (b). $\square$

4 Definition of the profiles

In this section we start the proof of Theorem 3.1 by defining the underlying profiles ${\mathcal {P}}^*_k$. The properties (a) and (b) stated in Theorem 3.1 will be established in the following sections.

We consider $n=2k$ voters called $v_1,v_2,\ldots ,v_{2k}$ together with $m=4k$ alternatives called $1,2,3,\ldots ,4k$. The preference orderings of the voters will be pasted together from the following preference pieces $X_i$, $Y_i$, $Z_i$ with $1\le i\le k$.

$$\begin{aligned} X_i&:= {2k+2i-2} ~\succ ~ {2k+2i-3} ~\succ ~ {2k+2i-4} ~\succ ~ \cdots ~\succ ~ {2i+2} \\ Y_i&:= {2i-2} ~\succ ~ {2i-3} ~\succ ~ {2i-4} ~\succ ~ \cdots ~\succ ~ {1} \\ Z_i&:= {2k+2i+1} ~\succ ~ {2k+2i+2} ~\succ ~ {2k+2i+3} ~\succ ~ \cdots ~\succ ~ {4k} \end{aligned}$$

Note that for every $i=1,\ldots ,k$, the corresponding three pieces $X_i$, $Y_i$, $Z_i$ cover contiguous intervals of respectively $2k-3$, $2i-2$, $2k-2i$ alternatives. Hence these three pieces jointly cover $4k-5$ of the alternatives, and only the five alternatives in the set

$$\begin{aligned} U_i = \{2i-1,~ 2i,~ 2i+1\} ~\cup ~ \{2k+2i-1,~ 2k+2i\} \end{aligned}$$

remain uncovered. Note furthermore that the pieces $Y_1$ and $Z_k$ are empty. Now let us define the preference orderings of the voters. The two voters $v_{2i-1}$ and $v_{2i}$ always form a couple with fairly similar preferences. For $1\le i\le k-1$, these voters $v_{2i-1}$ and $v_{2i}$ have the following preferences:

$$\begin{aligned} v_{2i-1}&: X_i\succ {2i+1} \succ {2k+2i-1}\succ {2i} \succ {2i-1}\succ {2k+2i}\succ Y_i\succ Z_i \end{aligned}$$

(1a)

$$\begin{aligned} v_{2i}&: X_i\succ {2k+2i-1}\succ {2k+2i} \succ {2i+1}\succ {2i} \succ {2i-1} \succ Y_i\succ Z_i. \end{aligned}$$

(1b)

Note that the voters $v_{2i-1}$ and $v_{2i}$ both rank the three alternatives $2i+1$, 2i, $2i-1$ in $U_i$ in the same decreasing order, with the two other alternatives $2k+2i-1$ and $2k+2i$ shuffled into that order. The last two voters $v_{2k-1}$ and $v_{2k}$ are defined separately:

$$\begin{aligned} v_{2k-1}&: X_k\succ {2k+1}\succ {4k-1}\succ {2k}\succ {2k-1} \succ {4k} \succ Y_k \end{aligned}$$

(2a)

$$\begin{aligned} v_{2k}&: X_k\succ {2k+1}\succ {2k}\succ \cdots \cdots \succ {3} \succ {2} \succ {4k-1} \succ {4k} \succ {1} \end{aligned}$$

(2b)

Since piece $Z_k$ is empty, the preferences of voter $v_{2k-1}$ in (2a) actually run in parallel with the preferences of the other odd-index voters $v_{2i-1}$ with $1\le i\le k-1$ in (1a). The last voter $v_{2k}$, however, behaves very differently from the other even-index voters: on top of his preference list are the alternatives in piece $X_k$, followed by an intermingling of the alternatives in piece $Y_k$ and set $U_k$ (first the alternatives $2k+1,\ldots ,2$ in decreasing order, and then the three alternatives $4k-1$, 4k, and 1).

Example 4.1

For $k=4$, the preference profile ${\mathcal {P}}^*_4$ has $n=8$ voters and $m=16$ alternatives and looks as follows (all preference orders are listed left to right from most preferred to least preferred alternative):

The alternatives in the five leftmost columns form the pieces $X_i$. In the first seven rows, the five middle columns correspond to the sets $U_i$, while the remaining six columns belong to pieces $Y_i$ and $Z_i$. The last row illustrates the extraordinary behavior of the last voter $v_8$. $\square$

5 The profiles are not Euclidean

In this section, we will discuss single-crossing, single-peaked and one-dimensional Euclidean properties of the profiles ${\mathcal {P}}^*_k$. First, it can readily be seen that every profile ${\mathcal {P}}^*_k$ with $k\ge 2$ is single-crossing with respect to the ordering $v_1,v_2,\ldots ,v_{2k-2},v_{2k},v_{2k-1}$ of the voters (that is, the natural ordering of voters by increasing index, but with the last two voters $v_{2k-1}$ and $v_{2k}$ swapped). As this single-crossing property is of no relevance for our further considerations, the simple proof is omitted. Next, let us turn to single-peakedness.

Lemma 5.1

For $k\ge 2$, the profile ${\mathcal {P}}^*_k$ is single-peaked. Furthermore, the only two single-peaked orderings of the alternatives are the increasing ordering $1,2,3,\ldots ,4k$ and the decreasing ordering $4k,\ldots ,3,2,1$.

Proof

Every voter $v_{2i-1}$ and $v_{2i}$ with $1\le i\le k$ has alternative $2k+2i-2$ as his top preference. Furthermore, he ranks the small alternatives $1,2,\ldots ,2k+2i-2$ decreasingly and he ranks the large alternatives $2k+2i-2,2k+2i-1,\ldots ,4k$ increasingly. Hence ${\mathcal {P}}^*_k$ indeed is single-peaked with respect to $1,2,3,\ldots ,4k$ and $4k,\ldots ,3,2,1$.

Next consider an arbitrary single-peaked permutation $\pi (1),\pi (2),\ldots ,\pi (4k)$ of the alternatives. Since 4k and 1 are the least preferred choices of voters $v_1$ and $v_{2k}$, these two alternatives must be extremal in the single-peaked ordering; by symmetry we will assume $\pi (1)=1$ and $\pi (4k)=4k$.

• Voter $v_1$ ranks $1\succ 2k+2\succ 2k+3\succ \cdots \succ 4k$, without other alternatives ranked in between. This implies $\pi (x)=x$ for $2k+2\le x\le 4k$.

• Voter $v_{2k-1}$ ranks $2k+2\succ 2k+1\succ 2k\succ \cdots \succ 3\succ 2\succ 1$. This now implies $\pi (x)=x$ also for the alternatives x with $1\le x\le 2k+1$.

Summarizing, we have $\pi (x)=x$ for all x, and this completes the proof. $\square$

The following lemma shows that every profile ${\mathcal {P}}^*_k$ satisfies property (a) of Theorem 3.1.

Lemma 5.2

For $k\ge 2$, the profile ${\mathcal {P}}^*_k$ is not one-dimensional Euclidean.

Proof

We suppose for the sake of contradiction that profile ${\mathcal {P}}^*_k$ is one-dimensional Euclidean. Let $F[j]$ for $j=1,\ldots ,2k$ and $E[i]$ for $i=1,\ldots ,4k$ denote a corresponding Euclidean representation of the voters and alternatives. As the Euclidean representation induces a single-peaked ordering of the alternatives, we will assume by Lemma 5.1 that the alternatives are embedded in increasing order with

$$\begin{aligned} E[1]< E[2]< E[3]< \cdots< E[4k-1] < E[4k]. \end{aligned}$$

(3)

Next, we claim that in any Euclidean representation under (3), the embedded alternatives satisfy the following system of inequalities:

$$\begin{aligned} E[2k+2i-1]+E[2i]&<E[2k+2i]+E[2i-1] \quad \text{ for }\; 1\le i\le k \end{aligned}$$

(4a)

$$\begin{aligned} E[2k+2i]+E[2i+1]&< E[2k+2i-1]+E[2i+2] \qquad \text{ for }\;1\le i\le k-1 \end{aligned}$$

(4b)

$$\begin{aligned} E[4k]+E[1]&< E[4k-1]+E[2] \end{aligned}$$

(4c)

The correctness of this system can be seen as follows. For each $i=1,\ldots ,k$, voter $v_{2i-1}$ ranks ${2k+2i-1}\succ {2i}$ and ${2i-1}\succ {2k+2i}$, which by Proposition 2.4 yields

$$\begin{aligned} \frac{1}{2}\left( E[2k+2i-1]+E[2i]\right) ~<~ F[2i-1] ~<~ \frac{1}{2}\left( E[2k+2i]+E[2i-1]\right) , \end{aligned}$$

which in turn implies (4a). Similarly, for $i=1,\ldots ,k-1$ voter $v_{2i}$ ranks ${2i+2}\succ {2k+2i-1}$ and ${2k+2i}\succ {2i+1}$ which leads to (4b). Finally, voter $v_{2k}$ ranks ${2}\succ {4k-1}$ and ${4k}\succ {1}$, which implies (4c). This establishes correctness of the system (4a)–(4c). By adding up all the inequalities in (4a)–(4c), we derive the contradiction $\sum _{x=1}^{4k}E[x]<\sum _{x=1}^{4k}E[x]$. $\square$

6 Definition of the Euclidean representations

In this section, we fix an integer s with $1\le s\le 2k$ and construct corresponding Euclidean embeddings $F_s$ and $E_s$ of the voters and alternatives in profile ${\mathcal {P}}^*_k$. We start by defining the Euclidean embedding $E_s$ of the alternatives. We anchor the embedding by placing the first alternative at the position

$$\begin{aligned} E_s[1] ~=~ 0. \end{aligned}$$

(5)

The remaining values $E_s[2],\ldots ,E_s[4k]$ are described recursively in equations (6)–(11) below. For $1\le i\le k-1$ we set

$$\begin{aligned} E_s[2i+1]-E_s[2i] ~=~2 \end{aligned}$$

(6)

and for $1\le i\le k$ we set

$$\begin{aligned} E_s[2i]-E_s[2i-1] ~=~ (4i-2s-3 \bmod 4k). \end{aligned}$$

(7)

Note that the relations (5)–(7) determine $E_s[x]$ for all $x\le 2k$. For $1\le i\le k-1$ we set

$$\begin{aligned}&E_s[2k+2i-1]-E_s[2k+2i-2] \nonumber \\&\quad = \left\{ \begin{array}{ll} E_s[2k+2i-3]-E_s[2i+1]+2~~&{}\text{ if } s\ne 2i-1\\ E_s[2k+2i-3]-E_s[2i+2]+2 &{}\text{ if } s=2i-1. \end{array} \right. \end{aligned}$$

(8)

For $1\le i\le k-1$ we define

$$\begin{aligned} E_s[2k+2i]-E_s[2k+2i-1] ~=~ (4i-2s-1 \bmod 4k). \end{aligned}$$

(9)

Note that the relations (8) and (9) determine $E_s[x]$ for all x with $2k+1\le x\le 4k-2$. Finally, we determine the Euclidean embedding of the last two alternatives by defining

$$\begin{aligned} E_s[4k-1]-E_s[4k-2] ~=~ \left\{ \begin{array}{ll} E_s[4k-3]-E_s[2]+2 &{} \quad \text{ if }\,\, s\ne 2k\\ E_s[4k-3]-E_s[2k+1]+2 &{}\quad \text{ if }\,\, s=2k \end{array} \right. \end{aligned}$$

(10)

and

$$\begin{aligned} E_s[4k]-E_s[4k-1] ~=~ \left\{ \begin{array}{ll} E_s[2] -E_s[1]-2 &{}\quad \text{ if } \,\,s\ne 2k\\ E_s[2k+1]-E_s[2k-1] &{}\quad \text{ if } \,\,s=2k. \end{array} \right. \end{aligned}$$

(11)

This completes the description of the Euclidean embedding $E_s$ of the alternatives. Note that $E_s[x]$ is integer for all alternatives x.

Lemma 6.1

The embedding $E_s$ satisfies $E_s[x]<E_s[y]$ for all alternatives x and y with $1\le x<y\le 4k$. In other words, $E_s$ satisfies the chain of inequalities in (3).

Proof

The statement follows from (5)–(11) by an easy inductive argument. The right hand sides in (6), (7) and (9) are all positive. The right hand sides in (8) and (10) can be seen to be positive by induction. Finally for $i=1$ and $s\ne 2k$, the right hand side of (7) is a positive odd integer strictly greater than 1; this yields $E_s[2]\ge 3$ so that also the right hand side $E_s[2]-E_s[1]-2$ in (11) is positive. $\square$

Example 6.2

We continue our discussion of the profile ${\mathcal {P}}^*_4$ from Example 4.1. For every embedding $E_s$ with $1\le s\le 8$, the corresponding row in Table 1 lists the distances $d_i=E_s[i]-E_s[i-1]$ between pairs of consecutive alternatives according to formulas (6)–(11). For instance the crossing of the row $E_{5}$ and the column labeled $d_4$ contains an entry with value 11; this means that in the Euclidean representation $E_{5}$, the distance $E_{5}[4]-E_{5}[3]$ between the embedded alternatives 3 and 4 equals 11. As $E_s[1]=0$, we see that for $2\le i\le 4k$ the value $E_s[i]$ then equals $d_2+d_3+\cdots +d_i$. For instance in $E_{5}$, alternative 4 will be embedded in the point $E_{5}[4]=7+2+11=20$.

The reader will notice that part of the data in Table 1 carries a periodic structure. For instance every even-indexed column (except the last one) contains a circular shift of the eight numbers 1, 3, 5, 7, 9, 11, 13, 15 presented in boldface, which results from formulas (7) and (9). Furthermore, all the entries in the three columns $d_3$, $d_5$, $d_7$ have the same value 2 according to (6). The numbers in other parts of the table look somewhat irregular and chaotic, which is caused by formula (8). For us, the most convenient way of working with this data is via the recursive definitions (5)–(11). $\square$

Table 1 This table is discussed in Example 6.2 and illustrates the Euclidean embedding of the alternatives in profile ${\mathcal {P}}^*_4$

Now let us turn to the Euclidean embedding of the voters. The Euclidean position $F_s[j]$ of every voter $v_j$ will be the average of exactly four embedded alternatives. For $1\le i\le k-1$ we define

$$\begin{aligned} F_s[2i-1] ~=~ \frac{1}{4}\left( E_s[2i-1]+E_s[2i]+E_s[2k+2i-1]+E_s[2k+2i]\right) . \end{aligned}$$

(12)

Similarly, for $1\le i\le k-1$ we define

$$\begin{aligned} F_s[2i] ~=~ \frac{1}{4}\left( E_s[2i+1]+E_s[2i+2]+E_s[2k+2i-1]+E_s[2k+2i]\right) . \end{aligned}$$

(13)

If $s\ne 2k$ then voter $v_{2k-1}$ is embedded according to (12), while for $s=2k$ it is embedded in a slightly different way. More precisely, we set

$$\begin{aligned} F_s[2k-1] ~= \left\{ \begin{array}{ll} \frac{1}{4}\left( E_s[2k-1]+E_s[2k] +E_s[4k-1]+E_s[4k]\right) &{}\text{ if } s\ne 2k\\ \frac{1}{4}\left( E_s[2k-2]+E_s[2k+1]+E_s[4k-1]+E_s[4k]\right) &{}\text{ if } s=2k. \end{array} \right. \end{aligned}$$

(14)

Finally, the very last voter $v_{2k}$ is embedded in

$$\begin{aligned} F_s[2k] ~=~ \frac{1}{4}\left( E_s[1]+E_s[2]+E_s[4k-1]+E_s[4k]\right) . \end{aligned}$$

(15)

Equations (12)–(15) define $F_s[j]$ for all voters $v_j$ with $1\le j\le 2k$. This completes the description of the Euclidean representation $F_s$ of the voters.

We note that the location $F_s[s]$ of voter $v_s$ has been specified, but will be irrelevant for our further arguments. We will show that $F_s$ and $E_s$ constitute a correct Euclidean representation for the $2k-1$ voters in $\{v_1,\ldots ,v_{2k}\}\backslash \{v_s\}$ together with all 4k alternatives $1,2,\ldots ,4k$. In other words, the deletion of voter $v_s$ from profile ${\mathcal {P}}^*_k$ yields a one-dimensional Euclidean profile, which completes the proof of property (b) in Theorem 3.1. To this end, the following lemma will be established in Sect. 8.

Lemma 6.3

For all r and s with $1\le r\ne s\le 2k$, the Euclidean representation $E_s$ and $F_s$ correctly represents the preferences of voter $v_r$.

The correctness of Lemma 6.3 for the small profiles ${\mathcal {P}}^*_k$ with $k\in \{2,3,4\}$ can easily be verified by a computer program (or by a human prover through tedious case distinctions). Hence we will from now on assume that

$$\begin{aligned} k\ge 5. \end{aligned}$$

(16)

This assumption will considerably shorten and simplify our arguments. Note furthermore that the proof of our main result in Theorem 3.2 is not touched by this assumption, as it builds on the profiles ${\mathcal {P}}^*_k$ for which k is large and tends to infinity.

7 A collection of technical results

In this section we state five technical lemmas. Lemmas 7.1 and 7.2 summarize a number of useful identities, and will serve as reference tables in our later analysis. Lemmas 7.3 through 7.5 state important inequalities that will be central to our proofs. Throughout we assume that $k\ge 5$ according to (16).

Lemma 7.1

For $1\le s\le 2k$, the Euclidean embedding $E_s$ satisfies the following.

$$\begin{aligned} E_s[2]&= 4k-2s+1 \end{aligned}$$

(17a)

$$\begin{aligned} E_s[3]&= 4k-2s+3 \end{aligned}$$

(17b)

$$\begin{aligned} E_s[4]&= \left\{ \begin{array}{ll} 4k-4s+8 &{}\quad \text{ if }\;s\in \{1,2\}\\ 8k-4s+8 &{}\quad \text{ if }\;s\ge 3. \end{array} \right. \end{aligned}$$

(17c)

Furthermore for $s\in \{1,2\}$, the embedding $E_s$ satisfies the following.

$$\begin{aligned} E_s[2k-2]-E_s[2k-3]&= 4k-2s-7 \end{aligned}$$

(18a)

$$\begin{aligned} E_s[2k-4]-E_s[2k-5]&= 4k-2s-11 \end{aligned}$$

(18b)

Proof

These statements follow by straightforward calculations from (5)–(9).

Lemma 7.2

If (a) $1\le i\le k-1$ and $s\ne 2i-1$, or if (b) $i=k$ and $s\notin \{2k-1,2k\}$, the following holds:

$$\begin{aligned}&E_s[2k+2i]-E_s[2k+2i-1] ~=~ E_s[2i]-E_s[2i-1]+2 \end{aligned}$$

(19a)

If (c) $1\le i\le k-1$ and $s\ne 2i$, the following holds:

$$\begin{aligned}&E_s[2k+2i]-E_s[2k+2i-1] ~=~ E_s[2i+2]-E_s[2i+1]-2 \end{aligned}$$

(19b)

Proof

We distinguish five cases. The first case assumes $s=2i-1$. In the setting of the lemma, this case can only occur under (c) with $1\le i\le k-1$. Then (9) yields $E_s[2k+2i]-E_s[2k+2i-1]=1$, while (7) yields $E_s[2i+2]-E_s[2i+1]=3$. This implies the desired equality (19b) for this first case.

The second case assumes $s=2i$. In the setting of the lemma, this case can only occur under (a) with $1\le i\le k-1$. Then (9) yields $E_s[2k+2i]-E_s[2k+2i-1]=4k-1$, while (7) yields $E_s[2i]-E_s[2i-1]=4k-3$. This implies the desired equality (19a).

The third case assumes $i=k$. In the setting of the lemma, this case can only occur under (b) with $1\le s\le 2k-2$. Then (11) and (17a) yield $E_s[4k]-E_s[4k-1]=4k-2s-1$, while (7) yields $E_s[2k]-E_s[2k-1]=4k-2s-3$. This implies the desired equality (19a).

In the remaining cases we always have $s\notin \{2i-1,2i\}$. The fourth case assumes that $1\le i\le k-1$ and that $s=2\ell -1$ is odd, where $1\le \ell \le k$ and $\ell \ne i$. In the setting of the lemma, this case can only occur under (a) and (c). Then (9) yields

$$\begin{aligned} E_s[2k+2i]-E_s[2k+2i-1]= & {} 4(i-\ell )+1 \bmod 4k, \end{aligned}$$

(20)

while (7) yields $E_s[2i]-E_s[2i-1]=4(i-\ell )-1 \bmod 4k$. Since $i-\ell \ne 0$, these two equations together yield (19a). Furthermore, (7) yields $E_s[2i+2]-E_s[2i+1]= 4(i-\ell )+3 \bmod 4k$, which together with (20) gives (19b).

The fifth case assumes that $1\le i\le k-1$ and that $s=2\ell$ is even, where $1\le \ell \le k$ and $\ell \ne i$. In the setting of the lemma, this case can only occur under (a) and (c). Then (9) yields

$$\begin{aligned} E_s[2k+2i]-E_s[2k+2i-1]= & {} 4(i-\ell )-1 \bmod 4k, \end{aligned}$$

(21)

while (7) yields $E_s[2i]-E_s[2i-1]=4(i-\ell )-3 \bmod 4k$. Since $i-\ell \ne 0$, these two statements together imply (19a). Finally, (7) yields $E_s[2i+2]-E_s[2i+1]= 4(i-\ell )+1 \bmod 4k$. As $i-\ell \ne 0$, this equation together with (21) yields (19b). This completes the proof. $\square$

Lemma 7.3

For all alternatives x and y with $1\le y\le x\le 4k$, the embedding $E_s$ satisfies the inequality $E_s[x]-E_s[y]\ge x-y$.

Proof

This follows from Lemma 6.1 and the integrality of $E_s$. $\square$

Lemma 7.4

All i and s with $1\le i\le 2k-1$ and $1\le s\le 2k$ satisfy the following inequality.

$$\begin{aligned} E_s[2i+1]-E_s[2i] ~\ge ~2. \end{aligned}$$

(22)

Proof

For $1\le i\le k-1$, this follows directly from (6). For $k\le i\le 2k-1$, this follows from (8) and (10) in combination with Lemma 7.3. $\square$

Lemma 7.5

All i and s with $1\le i\le k-1$ and $1\le s\le 2k$ satisfy the following inequality.

$$\begin{aligned} E_s[2k+2i-1] ~\ge ~ E_s[2k]+E_s[2i]+2. \end{aligned}$$

(23)

Proof

The proof is done by induction on $i=1,\ldots ,k-1$. For the inductive base case $i=1$ we distinguish two subcases on the value of s. The first subcase assumes $s\in \{1,2\}$. Then (8) and $k\ge 5$, together with (6), (17a), (18a), and (18b) yield

$$\begin{aligned}&E_s[2k+2i-1]-E_s[2k] \ge E_s[2k-1]-E_s[4]+2 \\&\quad \ge (E_s[2k-1]-E_s[2k-2]) +(E_s[2k-2]-E_s[2k-3]) \\&\qquad + \, (E_s[2k-3]-E_s[2k-4]) +(E_s[2k-4]-E_s[2k-5])+2 \\&\quad = 2 +(4k-2s-7) +2 +(4k-2s-11) +2 \\&\quad = 8k-4s-12 ~>~ (4k-2s+1)+2 ~=~ E_s[2]+2. \end{aligned}$$

The second subcase assumes $s\ge 3$. Then the first line of (8) together with $k\ge 5$ (17a), (17b) and (17c) yields

$$\begin{aligned} E_s[2k+2i-1]-E_s[2k]= & {} E_s[2k-1]-E_s[3]+2\\\ge & {} E_s[4]-E_s[3]+2 ~=~ (8k-4s+8)-(4k-2s+3) +2 \\= & {} 4k-2s+7 ~>~ E_s[2]+2. \end{aligned}$$

Summarizing, in both subcases we have established the desired (23). This completes the analysis of the inductive base case $i=1$. Next, let us state the inductive assumption as

$$\begin{aligned} E_s[2k+2i-3]\ge & {} E_s[2k]+E_s[2i-2]+2. \end{aligned}$$

(24)

In the inductive step, we will use the following consequence of (8):

$$\begin{aligned} E_s[2k+2i-1]-E_s[2k+2i-2]\ge & {} E_s[2k+2i-3]-E_s[2i+2]+2. \end{aligned}$$

(25)

Furthermore, by (9) the left hand side of the following inequality equals $(4i-2s-5\bmod 4k)$, while by (7) its right hand side equals $(4i-2s-3\bmod 4k)-2$. This implies

$$\begin{aligned} E_s[2k+2i-2]-E_s[2k+2i-3]\ge & {} E_s[2i]-E_s[2i-1]-2. \end{aligned}$$

(26)

Adding up (24), (25) and (26), and rearranging and simplifying the resulting inequality yields

$$\begin{aligned}&E_s[2k+2i-1]-E_s[2k]-E_s[2i]-2 \\&\quad \ge E_s[2k+2i-3]-E_s[2i+2] +E_s[2i-2]-E_s[2i-1] \\&\quad \ge (2k+2i-3)-(2i+2)-2 ~=~ 2k-7 ~>~ 0. \end{aligned}$$

Here we used Lemma 7.3 to bound $E_s[2k+2i-3]-E_s[2i+2]$, and we used (6) to get rid of $E_s[2i-2]-E_s[2i-1]$. As this implies (23), the inductive argument is complete. $\square$

8 Correctness of the Euclidean representations

In this section we prove Lemma 6.3. Hence, let us fix two arbitrary voters $v_r$ and $v_s$ with $r\ne s$. We recall that by Lemma 6.1 the Euclidean representation $E_s$ embeds the alternatives $1,\ldots ,4k$ in increasing order from left to right. Our goal is to show that any two alternatives x and y with $x\succ _r y$ that are consecutive in the preference order of voter $v_r$ satisfy

$$\begin{aligned}&2F_s[r]< E_s[x]+E_s[y] \qquad \text{ whenever }\; x<y \end{aligned}$$

(27a)

$$\begin{aligned}&2F_s[r]> E_s[x]+E_s[y] \qquad \text{ whenever }\; x>y. \end{aligned}$$

(27b)

By our construction, all preference orders in profile ${\mathcal {P}}^*_k$ contain long monotone (increasing or decreasing) runs of alternatives. By Proposition 2.5 it will therefore be sufficient to establish (27a) and (27b) at the few turning points where the preference order of voter $v_r$ changes its monotonicity behavior. We stress that the first pair of alternatives in every preference order forms a turning point by default.

The remaining argument is split into four cases that will be handled in the following four sections. Sections 8.1 and 8.2 treat the cases with odd r, while Sects. 8.3 and 8.4 treat the cases with even r.

8.1 The cases with odd r (with a single exception)

In this section we consider the cases with odd $r=2i-1$ for $1\le i\le k$, and with $s\ne 2i-1$. If $i=k$ (and hence $r=2k-1$) then we additionally assume $s\ne 2k$; the remaining case with $i=k$ and $s=2k$ will be settled in the next section. Note that in the cases under current consideration, the value $F_s[2i-1]$ is given by (12). Furthermore (19a) in Lemma 7.2 yields

$$\begin{aligned} E_s[2k+2i]+E_s[2i-1] ~=~ E_s[2i] +E_s[2k+2i-1]+2. \end{aligned}$$

(28)

In order to prove (27a) and (27b) for the preference orders in (1a) and (2a), it is sufficient to establish the following six inequalities for the turning points.

$$\begin{aligned}&2F_s[2i-1] ~>~ E_s[2k+2i-2]+E_s[2k+2i-3] \end{aligned}$$

(29a)

$$\begin{aligned}&2F_s[2i-1] ~<~ E_s[2i+1] +E_s[2k+2i-1] \end{aligned}$$

(29b)

$$\begin{aligned}&2F_s[2i-1] ~>~ E_s[2k+2i-1]+E_s[2i] \end{aligned}$$

(29c)

$$\begin{aligned}&2F_s[2i-1] ~<~ E_s[2i-1] +E_s[2k+2i] \end{aligned}$$

(29d)

$$\begin{aligned}&2F_s[2i-1] ~>~ E_s[2k+2i] +E_s[2i-2] \end{aligned}$$

(29e)

$$\begin{aligned}&2F_s[2i-1] ~<~ E_s[1] +E_s[2k+2i+1] \end{aligned}$$

(29f)

Note that for $i=1$ the inequality in (29e) vanishes as piece $Y_1$ is empty, and that for $i=k$ inequality (29f) vanishes as piece $Z_k$ is empty. We use (12) or the first line of (14) together with (28), and rewrite the common left hand side of all inequalities (29a)–(29f) as

$$\begin{aligned} 2F_s[2i-1]&= \frac{1}{2}\left( E_s[2i-1]+E_s[2i]+E_s[2k+2i-1]+E_s[2k+2i]\right) \nonumber \\&= E_s[2i]+E_s[2k+2i-1]+1 ~=~ E_s[2i-1]+E_s[2k+2i]-1. \end{aligned}$$

(30)

For (29a), we distinguish two subcases. The first subcase assumes $i\le k-1$. We compute by using (8), (30) with $s\ne 2i-1$, and (6) that

$$\begin{aligned}&2F_s[2i-1]-E_s[2k+2i-2]-E_s[2k+2i-3] \\&\quad = (E_s[2i]+E_s[2k+2i-1]+1) -E_s[2k+2i-2]-E_s[2k+2i-3] \\&\quad = E_s[2i]+1-E_s[2i+1]+2 ~=~ 1 ~>~ 0. \end{aligned}$$

The second subcase deals with the remaining case $i=k$. We use (30), the first line in (10), and Lemma 6.1 to compute

$$\begin{aligned}&2F_s[2i-1]-E_s[2k+2i-2]-E_s[2k+2i-3] \\&\quad = (E_s[2k]+E_s[4k-1]+1) -E_s[4k-2]-E_s[4k-3] \\&\quad = (E_s[2k]+1)+(-E_s[2]+2) ~=~ (E_s[2k]-E_s[2])+3 ~>~ 0. \end{aligned}$$

For (29b), we compute by using (22) and (30) that

$$\begin{aligned}&2F_s[2i-1]-E_s[2i+1] -E_s[2k+2i-1] \\&\qquad = (E_s[2i]+E_s[2k+2i-1]+1) -E_s[2i+1] -E_s[2k+2i-1] ~<~ 0. \end{aligned}$$

For (29c), we compute by using (30) that

$$\begin{aligned}&2F_s[2i-1]-E_s[2k+2i-1]-E_s[2i] \\&\quad = (E_s[2i]+E_s[2k+2i-1]+1) -E_s[2k+2i-1]-E_s[2i] ~=~ 1 ~>~ 0. \end{aligned}$$

For (29d), we compute by using (30) that

$$\begin{aligned}&2F_s[2i-1]-E_s[2i-1] -E_s[2k+2i] \\&\quad = (E_s[2i-1]+E_s[2k+2i]-1) -E_s[2i-1] -E_s[2k+2i] ~=~ -1 ~<~ 0. \end{aligned}$$

For (29e) with $i\ge 2$, we compute by using (6) and (30) that

$$\begin{aligned}&2F_s[2i-1]-E_s[2k+2i] -E_s[2i-2] \\&\quad = (E_s[2i-1]+E_s[2k+2i]-1) -E_s[2k+2i] -E_s[2i-2] ~=~ 1 ~>~ 0. \end{aligned}$$

It remains to prove inequality (29f) which takes more effort. Since (29f) vanishes for $i=k$, we may assume $i\le k-1$. We first use (5) and (30) to derive

$$\begin{aligned}&2F_s[2i-1] -E_s[1] -E_s[2k+2i+1] \nonumber \\&\quad = E_s[2i-1]-1 - (E_s[2k+2i+1]-E_s[2k+2i]). \end{aligned}$$

(31)

Our goal is to show that the value in (31) is strictly negative, and for this we branch into three subcases. The first subcase assumes $i\le k-2$. We use (8), (23), and Lemma 6.1 to compute

$$\begin{aligned}&E_s[2i-1]-1 - (E_s[2k+2i+1]-E_s[2k+2i]) \\&\quad \le E_s[2i-1]-1 - (E_s[2k+2i-1]-E_s[2i+4]+2) \\&\quad \le E_s[2i-1]-3+E_s[2i+4] - (E_s[2k]+E_s[2i]+2) \\&\quad = (E_s[2i+4]-E_s[2k]) +(E_s[2i-1]-E_s[2i]) -5 ~<~ 0. \end{aligned}$$

The second subcase assumes $i=k-1$ and $s\ne 2k$. We use (10), (23), and Lemma 6.1 to compute

$$\begin{aligned}&E_s[2i-1]-1 - (E_s[2k+2i+1]-E_s[2k+2i]) \\&\quad = E_s[2k-3]-1 - (E_s[4k-1]-E_s[4k-2]) \\&\quad = E_s[2k-3]-1 - (E_s[4k-3]-E_s[2]+2) \\&\quad \le E_s[2k-3]-3+E_s[2] - (E_s[2k]+E_s[2k-2]+2) \\&\quad = (E_s[2k-3]-E_s[2k])+(E_s[2]-E_s[2k-2])-5 ~<~ 0. \end{aligned}$$

The third and last subcase assumes $i=k-1$ and $s=2k$. We use the second line of (10), the first line of (8), inequality (23), Eq. (6), and Lemma 6.1 to compute

$$\begin{aligned}&E_s[2i-1]-1 - (E_s[2k+2i+1]-E_s[2k+2i]) \\&\quad = E_s[2k-3]-1 - (E_s[4k-1]-E_s[4k-2]) \\&\quad = E_s[2k-3]-1 - (E_s[4k-3]-E_s[2k+1]+2) \\&\quad =E_s[2k-3]-3+E_s[2k+1] - (E_s[4k-4]+E_s[4k-5]-E_s[2k-1]+2) \\&\quad \le E_s[2k-3]-5+E_s[2k+1]-E_s[4k-4]\\&\qquad + \, E_s[2k-1]-(E_s[2k]+E_s[2k-4]+2) \\&\quad = (E_s[2k+1]-E_s[4k-4]) + (E_s[2k-1]-E_s[2k]) -5 ~<~ 0. \end{aligned}$$

As (31) is strictly negative in each of the three subcases, the proof of (29f) is complete. The Euclidean representation $E_s$ and $F_s$ correctly represents the preferences of voter $v_r$.

8.2 The exceptional case with odd r

In this section we consider the exceptional case $i=k$ (and hence $r=2k-1$) under $s=2k$, which has been left open in the preceding section. In this exceptional case, the embedding $F_s[2k-1]$ is given by the second option in formula (14). Furthermore, (6) and (11) yield

$$\begin{aligned} E_s[4k]-E_s[4k-1]= & {} E_s[2k+1] -E_s[2k-2]-2. \end{aligned}$$

Altogether this leads to

$$\begin{aligned} 2F_s[2k-1]&= \frac{1}{2}\left( E_s[2k-2]+E_s[2k+1]+E_s[4k-1]+E_s[4k]\right) \nonumber \\&= E_s[2k-2]+E_s[4k]+1 ~=~ E_s[2k+1]+E_s[4k-1]-1. \end{aligned}$$

(32)

As inequality (29f) vanishes for $i=k$, our goal in this section is to establish the five inequalities (29a)–(29e) for $i=k$ and $s=2k$. For (29a), we compute by using (10) and (32) that

$$\begin{aligned}&2F_s[2k-1]-E_s[4k-2]-E_s[4k-3] \\&\quad = (E_s[2k+1]+E_s[4k-1]-1) -E_s[4k-2]-E_s[4k-3] \\&\quad = E_s[2k+1]-E_s[4k-3]-1+(E_s[4k-3]-E_s[2k+1]+2) ~=~ 1 ~>~ 0. \end{aligned}$$

For (29b), we compute by using (32) that

$$\begin{aligned}&2F_s[2k-1]-E_s[2k+1] -E_s[4k-1] \\&\quad = (E_s[2k+1]+E_s[4k-1]-1) -E_s[2k+1] -E_s[4k-1] ~=~ -1 ~<~ 0. \end{aligned}$$

For (29c), we compute by using (22) and (32) that

$$\begin{aligned}&2F_s[2k-1]-E_s[4k-1]-E_s[2k] \\&\quad = (E_s[2k+1]+E_s[4k-1]-1) -E_s[4k-1]-E_s[2k] ~>~ 0. \end{aligned}$$

For (29d), we compute by using (6) and (32) that

$$\begin{aligned}&2F_s[2k-1]-E_s[2k-1] -E_s[4k] \\&\quad = (E_s[2k-2]+E_s[4k]+1) -E_s[2k-1] -E_s[4k] ~=~ -1 ~<~ 0. \end{aligned}$$

For (29e), we compute by using (32) that

$$\begin{aligned}&2F_s[2k-1]-E_s[4k] -E_s[2k-2] \\&\quad = (E_s[2k-2]+E_s[4k]+1) -E_s[4k] -E_s[2k-2] ~=~ 1 ~>~ 0. \end{aligned}$$

This completes the analysis of the exceptional case with odd r. Also in this case, the representation $E_s$ and $F_s$ correctly represents the preferences of the considered voter.

8.3 The cases with even r (with a single exception)

In this section we consider the cases with even $r=2i$ for $1\le i\le k-1$, and with $s\ne 2i$. The remaining case $r=2k$ will be settled in the next section. Note that in the cases under consideration, the value $F_s[2i]$ is given by (13). Furthermore (19b) in Lemma 7.2 yields

$$\begin{aligned}&E_s[2i+1]+E_s[2k+2i] ~=~ E_s[2i+2]+E_s[2k+2i-1]-2. \end{aligned}$$

(33)

In order to prove (27a) and (27b) for the preference orders in (1b), it is sufficient to establish the following four inequalities for the turning points.

$$\begin{aligned}&2F_s[2i] ~>~ E_s[2k+2i-2]+E_s[2k+2i-3] \end{aligned}$$

(34a)

$$\begin{aligned}&2F_s[2i] ~<~ E_s[2i+2] +E_s[2k+2i-1] \end{aligned}$$

(34b)

$$\begin{aligned}&2F_s[2i] ~>~ E_s[2k+2i] +E_s[2i+1] \end{aligned}$$

(34c)

$$\begin{aligned}&2F_s[2i] ~<~ E_s[1] +E_s[2k+2i+1] \end{aligned}$$

(34d)

We use the definition of $F_s[2i]$ in (13) together with (33) to rewrite the common left hand side of all inequalities (34a)–(34d) as

$$\begin{aligned} 2F_s[2i] =~&\frac{1}{2}\left( E_s[2i+1]+E_s[2i+2]+E_s[2k+2i-1]+E_s[2k+2i]\right) \nonumber \\ =~&E_s[2i+1]+E_s[2k+2i]+1 ~=~ E_s[2i+2]+E_s[2k+2i-1]-1. \end{aligned}$$

(35)

For (34a), we compute by using (8) and (35) that

$$\begin{aligned}&2F_s[2i]-E_s[2k+2i-2]-E_s[2k+2i-3] \\&\quad = (E_s[2i+2]+E_s[2k+2i-1]-1) -E_s[2k+2i-2]-E_s[2k+2i-3] \\&\quad \ge E_s[2i+2]-E_s[2k+2i-3]-1+(E_s[2k+2i-3]-E_s[2i+2]+2) =1 >0. \end{aligned}$$

For (34b), we compute by using (35) that

$$\begin{aligned}&2F_s[2i]-E_s[2i+2]-E_s[2k+2i-1] \\&\quad = (E_s[2i+2]+E_s[2k+2i-1]-1) -E_s[2i+2]-E_s[2k+2i-1] = -1 < 0. \end{aligned}$$

For (34c), we compute by using (35) that

$$\begin{aligned}&2F_s[2i]-E_s[2k+2i]-E_s[2i+1] \\&\quad = (E_s[2i+1]+E_s[2k+2i]+1) -E_s[2k+2i]-E_s[2i+1] = 1 > 0. \end{aligned}$$

It remains to prove inequality (34d) which takes a considerable amount of work. We branch into three subcases. The first subcase assumes $1\le i\le k-2$. Then Lemma 6.1 implies $E_s[2i+4]\le E_s[2k]$. We use (5), (6), (8), (23) and (35) to derive

$$\begin{aligned}&2F_s[2i] -E_s[1] -E_s[2k+2i+1] \\&\quad = (E_s[2i+1]+E_s[2k+2i]+1) -E_s[2k+2i+1] \\&\quad \le E_s[2i+1]+1 - (E_s[2k+2i-1]-E_s[2i+4]+2) \\&\quad \le E_s[2i+1]+E_s[2i+4]-1 -(E_s[2k]+E_s[2i]+2) \\&\quad = E_s[2i+4]-E_s[2k]-1 ~<~ 0. \end{aligned}$$

The second subcase assumes $i=k-1$ and $s\ne 2k$. For proving (34d), we compute by using (5), (6), (10), (23) and (35) that

$$\begin{aligned}&2F_s[2k-2] -E_s[1] -E_s[4k-1] \\&\quad = (E_s[2k-1]+E_s[4k-2]+1) -E_s[4k-1] \\&\quad = E_s[2k-1]+1 -(E_s[4k-3]-E_s[2]+2) \\&\quad \le E_s[2k-1]+E_s[2]-1 -(E_s[2k]+E_s[2k-2]+2) \\&\quad = E_s[2]-E_s[2k]-1 ~<~ 0. \end{aligned}$$

The third and last subcase finally assumes $i=k-1$ and $s=2k$. We start the analysis by deriving a number of auxiliary equations and inequalities. First we determine $E_s[3]=3$ from (17b), and compute by using (8) and (6) that

$$\begin{aligned}&E_s[2k+1] -E_s[2k-2] \nonumber \\&\quad = (E_s[2k+1]-E_s[2k]) +(E_s[2k]-E_s[2k-1]) +(E_s[2k-1]-E_s[2k-2])\nonumber \\&\quad = (E_s[2k-1]-E_s[3]+2) +(E_s[2k]-E_s[2k-1]) +2 ~~=~~ E_s[2k]+1.\nonumber \\ \end{aligned}$$

(36)

Next, we use (19b) to derive

$$\begin{aligned} E_s[2k-2]-E_s[2k-3]-2= & {} E_s[4k-4]-E_s[4k-5]. \end{aligned}$$

(37)

We express $E_s[4k-3]$ once by the first line of (8) and once by the second line of (10), which by equating yields

$$\begin{aligned}&E_s[4k-4]+E_s[4k-5]-E_s[2k-1]+2 \nonumber \\&\quad = E_s[2k+1]-2 +E_s[4k-1]-E_s[4k-2]. \end{aligned}$$

(38)

Next, we add up (36)–(38) and rearrange the result to derive

$$\begin{aligned}&E_s[2k-1]+E_s[4k-2]-E_s[4k-1]+1 \nonumber \\&\quad = 2E_s[2k-1] +E_s[2k]+E_s[2k-3]-2E_s[4k-5]. \end{aligned}$$

(39)

We compute $E_s[2k]-E_s[2k-1]=4k-3$ and $E_s[2k-2]-E_s[2k-3]=4k-7$ from (7), and use these together with (6) to get

$$\begin{aligned}&E_s[2k-1]-E_s[2k-4]+E_s[2k-1]-E_s[2k] \nonumber \\&\quad = (E_s[2k-2]+2)-(E_s[2k-3]-2)-(E_s[2k]-E_s[2k-1]) \nonumber \\&\quad = 2+(4k-7)+2-(4k-3) ~=~ 0. \end{aligned}$$

(40)

Now for finally proving (34d) in this third and last subcase, we compute by using (6), (5), (23), (35), (39) and (40) that

$$\begin{aligned}&2F_s[2k-2] -E_s[1] -E_s[4k-1] \\&\quad = (E_s[2k-1]+E_s[4k-2]+1) -E_s[4k-1] \\&\quad = 2E_s[2k-1] +E_s[2k]+E_s[2k-3]-2E_s[4k-5] \\&\quad \le 2E_s[2k-1] +E_s[2k]+E_s[2k-3]-2(E_s[2k]+E_s[2k-4]+2) \\&\quad = E_s[2k-3]-E_s[2k-4]-4 ~=~ -2 ~<~ 0. \end{aligned}$$

This completes the proof of inequality (34d). Summarizing, the representation $E_s$ and $F_s$ correctly represents the preferences of the considered voter $v_r$.

8.4 The exceptional case with even r

In this section we consider the last remaining case with even r, where $r=2k$ and $s\ne 2k$ holds. In order to prove (27a) and (27b) for the preference orders in (2b), it is sufficient to establish the following three inequalities for the turning points.

$$\begin{aligned}&2F_s[2k] ~>~ E_s[4k-2]+E_s[4k-3] \end{aligned}$$

(41a)

$$\begin{aligned}&2F_s[2k] ~<~ E_s[2] +E_s[4k-1] \end{aligned}$$

(41b)

$$\begin{aligned}&2F_s[2k] ~>~ E_s[4k] +E_s[1] \end{aligned}$$

(41c)

The definition of $F_s[2k]$ in (11) and (15) with $s\ne 2k$ yield for the common left hand side of (41a)–(41c) that

$$\begin{aligned} 2F_s[2k]&= \frac{1}{2}\left( E_s[1]+E_s[2]+E_s[4k-1]+E_s[4k]\right) \nonumber \\&=E_s[4k]+E_s[1]+1 ~=~ E_s[4k-1]+E_s[2]-1. \end{aligned}$$

(42)

For (41a), we compute by using (10) and (42) with $s\ne 2k$ that

$$\begin{aligned}&2F_s[2k]-E_s[4k-2]-E_s[4k-3] \\&\quad = (E_s[4k-1]+E_s[2]-1) -E_s[4k-2]-E_s[4k-3] \\&\quad = E_s[2]-E_s[4k-3]-1 +(E_s[4k-3]-E_s[2]+2) = 1 ~>~ 0. \end{aligned}$$

For (41b), we compute by using (42) that

$$\begin{aligned}&2F_s[2k]-E_s[2] -E_s[4k-1] \\&\quad = (E_s[4k-1]+E_s[2]-1) -E_s[2] -E_s[4k-1] = -1 ~<~ 0. \end{aligned}$$

For (41c), we compute by using (42) that

$$\begin{aligned}&2F_s[2k]-E_s[4k] +E_s[1] \\&\quad = (E_s[4k]+E_s[1]+1) -E_s[4k] -E_s[1] = 1 > 0. \end{aligned}$$

This settles the last case. The proof of Lemma 6.3 and with it the proof of Theorem 3.1 are finally complete.

9 Conclusions

We have shown that one-dimensional Euclidean preference profiles can not be characterized in terms of finitely many obstructions. This is similar to the situation of interval graphs, which also can not be characterized by finitely many obstructions. For interval graphs, however, we have a full understanding of all the obstructions that are minimal with respect to vertex deletion; see Lekkerkerker and Boland (1962). In a similar vein, it would be interesting to determine all the (infinitely many) obstructions for one-dimensional Euclidean preferences that are minimal with respect to deletion of voters or alternatives. At the current moment, we have no idea of what these minimal obstructions would look like.

With respect to general d-dimensional Euclidean preference profiles, we feel that the situation should be analogous to the one-dimensional situation: we conjecture that for any fixed value of $d\ge 2$, there will be no characterization of d-dimensional Euclidean profiles through finitely many obstructions. However, we see no realistic way of generalizing our current approach to the higher-dimensional situations, and we leave this as an open problem. (We remind the reader that in a d-dimensional Euclidean preference profile the voters and alternatives are embedded in d-dimensional Euclidean space, so that small distance corresponds to strong preference; see for instance Bogomolnaia and Laslier 2007.)