# recognising_multidimensional_euclidean_preferences__84798d42.pdf

Recognising Multidimensional Euclidean Preferences

Dominik Peters Department of Computer Science University of Oxford, UK dominik.peters@cs.ox.ac.uk

Euclidean preferences are a widely studied preference model, in which decision makers and alternatives are embedded in d-dimensional Euclidean space. Decision makers prefer those alternatives closer to them. This model, also known as multidimensional unfolding, has applications in economics, psychometrics, marketing, and many other ﬁelds. We study the problem of deciding whether a given preference proﬁle is d-Euclidean. For the one-dimensional case, polynomial-time algorithms are known. We show that, in contrast, for every other ﬁxed dimension d > 1, the recognition problem is equivalent to the existential theory of the reals (ETR), and so in particular NP-hard. We further show that some Euclidean preference proﬁles require exponentially many bits in order to specify any Euclidean embedding, and prove that the domain of d-Euclidean preferences does not admit a ﬁnite forbidden minor characterisation for any d > 1. We also study dichotomous preferences and the behaviour of other metrics, and survey a variety of related work.

1 Introduction The study of preferences spans a multitude of ﬁelds: economics (and particularly game theory and social choice), political science, psychology, multi-agent systems, marketing, and others. An important element of working with preferences is understanding them by constructing models for them and identifying underlying structure. For example, in a psychological model of preferences, we aim to discover which underlying psychological process has generated the preferences we now observe (Coombs 1964). In political science, one might wonder about the underlying structure of political space by analysing voter preferences (Merrill and Grofman 1999). In economics, working with wellstructured preferences often allows a model to become analytically tractable. This paper will use the lens and language of computational social choice. In recent years, much work in computational social choice has focussed on identifying structure in a given preference proﬁle (Elkind, Lackner, and Peters 2016). The reason for this is simple: many of the problems social

Copyright c 2017, Association for the Advancement of Artiﬁcial Intelligence (www.aaai.org). All rights reserved.

choice aims to solve (such as preference aggregation, committee selection, or fair and efﬁcient allocation) are computationally hard. However, if we manage to identify underlying, hopefully low-dimensional structure in the input proﬁle, we can exploit this structure to guide algorithms. This approach has been successful, particularly for the domain of single-peaked preferences: once we have identiﬁed an axis on which an input proﬁle is single-peaked, we can efﬁciently ﬁnd Kemeny, Young, and Dodgson winners (Brandt et al. 2015), identify an optimal committee according to the Chamberlin Courant rule (Betzler, Slinko, and Uhlmann 2013), control elections (Faliszewski et al. 2011), and solve the stable roommates problem (Bartholdi and Trick 1986). This leaves the question of whether we can, in fact, efﬁciently ﬁnd a certiﬁcate for single-peakedness (or another desired domain restriction) that such algorithms can use. The answer is often positive: there are efﬁcient and certiﬁcate-producing recognition algorithms for preferences that are single-peaked (Escofﬁer, Lang, and Ozt urk 2008), single-crossing (Elkind, Faliszewski, and Slinko 2012), onedimensional Euclidean (Doignon and Falmagne 1994), or single-peaked on a tree (Trick 1989). Indeed, each of these preference domains is quite well-understood, for example in terms of forbidden-substructure characterisations (Ballester and Haeringer 2011), concise representations of all certiﬁcates (Peters and Elkind 2016; Bartholdi and Trick 1986), containment relations between the different domains (Elkind, Faliszewski, and Skowron 2014), and the probability with which a random preference proﬁle falls within a given domain (Bruner and Lackner 2015). Intriguingly, there is another preference domain for which we do not have a comparable amount of understanding, yet it is an extremely popular modelling choice across disciplines. Known as spatial preferences, or as the d-Euclidean domain, or as multidimensional unfolding, this preference domain contains proﬁles that can be embedded into ddimensional Euclidean space. Precisely, a preference proﬁle is d-Euclidean if we can assign every voter and every alternative a point in Rd such that voters prefer those alternatives that are closer to them (according to the usual Euclidean metric) to those that are further away. This characterisation of preferences has intuitive appeal: considering Rd as a continuous policy space , within which alternatives can vary along multiple dimensions, each voter is identiﬁed

Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17)

with an ideal point (Bennett and Hays 1960). In practice, the embedding of voters and alternatives into Rd is hidden, and we only have access to the ordinal ranking data in form of a preference proﬁle (Anshelevich, Bhardwaj, and Postl 2015). Given this data, can we recover an appropriate embedding into Rd that explains the preferences? This problem is known as multidimensional unfolding (Bennett and Hays 1960), and a large variety of methods that attempt to estimate embeddings have been proposed in the statistics and psychometrics literature (for a modern exposition see, e.g., Borg and Groenen 2005). None of these methods is guaranteed to return a suitable embedding whenever it exists and terminate in polynomial time. We analyse this problem from a formal computational perspective. In particular, we prove that the decision problem of identifying d-Euclidean preference proﬁles is NPhard for each ﬁxed d 2. More precisely, we prove that the problem is equivalent to the existential theory of the reals (ETR), and thus is in fact R-complete. The recognition problem is thus unlikely to be contained in NP (though it is decidable in PSPACE). Using recent results about hyperplane arrangements, we deduce that, for each ﬁxed d 2, there exist d-Euclidean preference proﬁles such that the coordinates of any d-Euclidean embedding require exponentially many bits to specify. Thus, there is provably no polynomial-time algorithm that, on input a preference proﬁle, outputs a d-Euclidean embedding if one exists. Some restricted preference domains admit characterisations by a ﬁnite list of forbidden subproﬁles, such as preferences that are single-peaked (Ballester and Haeringer 2011), single-crossing (Bredereck, Chen, and Woeginger 2013), or single-peaked on a circle (Peters and Lackner 2017). In contrast, Chen, Pruhs, and Woeginger (2015) show that the 1Euclidean domain does not admit such a characterisation. They conjectured that the same is true for the domain of d Euclidean preferences, for each ﬁxed d 2. We use a connection with the theory of oriented matroids to prove their conjecture. The results in this paper cast some doubt on the fruitfulness of exploiting structure in d-Euclidean preferences in computational social choice, and they also limit the extent to which the spatial preference model can be used to reliably explain observed preference data. Future work could explore ways of mitigating this situation. At the end of this paper, we brieﬂy sketch one way that this could be done, namely by replacing the Euclidean ℓ2-metric by the ℓ1or ℓ -metric. We show that the recognition problems corresponding to these metrics are contained in NP.

2 Preliminaries Euclidean preferences Let A be a ﬁnite set of alternatives or candidates. A preference relation over A (usually referred to as a vote) is a complete and transitive binary relation over A. We denote by the strict part of , that is, a b if and only if a b but b a; and we denote by the indifference part of , with a b if and only if a b and b a. A proﬁle V over A is a set of votes over A. For notational convenience, we give voters names like v or i, and refer to their preference relation by v and i.

Let V be a proﬁle over A. We say that V is d-Euclidean (where d 1) if there exists a map x : V A Rd with

a v b = x(v) x(a) < x(v) x(b) (1)

for all v V and a, b A. Thus, voter v prefers those alternatives which are closer to v according to the embedding x. Here, refers to the usual Euclidean ℓ2-norm on Rd,

(x1, . . . , xd) = (x1, . . . , xd) 2 =

x2 1 + + x2 d.

The (open) ball of radius r centred at c is B(c, r) = {x Rd : x c < r}. Typically, we will consider proﬁles of strict orders in which every vote v is antisymmetric (that is, we do not allow ties). Notice that in any d-Euclidean embedding of a proﬁle of strict orders, no two alternatives can reside at the same point of Rd. In some applications, it makes sense to consider preferences that include indifferences (ties). An extreme case, which nevertheless ﬁnds many applications, is that of dichotomous preferences. A vote is dichotomous if there are no three alternatives a, b, c A with a b c. Equivalently, is dichotomous if A splits into approved and nonapproved alternatives. That is, we can write A = A1 A2 with A1 A2 = satisfying a b iff a A1 and b A2. We then say that the voter approves of the alternatives in A1, while the voter does not approve the alternatives in A2. A dichotomous vote can (and will) be speciﬁed by just giving the set A1 of approved alternatives. Our deﬁnition of Euclidean preferences applies to dichotomous preferences as well. Following the terminology of Elkind and Lackner (2015), we call a proﬁle of dichotomous preferences d-DE (Dichotomous Euclidean) if it is d Euclidean. In this context, the deﬁnition requires that there is an embedding x : V A Rd so that for each voter v V , the set of approved alternatives of v coincides with the set of alternatives contained in some ball B(x(v), rv) centred at x(v). Some authors deﬁne Euclidean preferences in a subtly different way from us. One popular deﬁnition involves reversing the direction of the implication arrow in (1). Notice that under this deﬁnition, whenever a voter is equidistant between two alternatives, the voter is free to break the tie in either way. In particular, when d 2, then every preference proﬁle is d-Euclidean under this deﬁnition place all voters at the origin, and position alternatives on the unit sphere around the origin. In the area of multidimensional unfolding, embeddings of this type are said to include degeneracies (see, e.g., Busing, Groenen, and Heiser 2005). Our deﬁnition circumvents this issue by just outright disallowing degeneracies. Bogomolnaia and Laslier (2007) use another different deﬁnition: they replace the implication in (1) by an if-andonly-if. This deﬁnition is equivalent to ours for strict preferences, but is much more restrictive for preferences including ties: Bogomolnaia and Laslier s deﬁnition requires that whenever a voter v is indifferent between a and b, then a and b are equidistant to v. Our deﬁnition does not impose any relation on the relative distances in cases of ties, which makes it more applicable to the case of dichotomous orders.

Existential Theory of the Reals (ETR) The language of the ﬁrst-order theory of the reals consists of formulas using as symbols (i) a countable collection of variable symbols xi, (ii) constant symbols 0 and 1, (iii) addition, subtraction, multiplication symbols, (iv) the equality (=) and inequality (<) symbols, (v) Boolean connectives ( , , ), (vi) universal and existential quantiﬁers ( , ). The theory of the reals consists of all true sentences in this language, interpreted using the obvious semantics (where quantiﬁers quantify over the real numbers R). The existential theory of the reals (ETR) consists of the true sentences of the form

x1 R x2 R . . . xn R F(x1, x2, . . . , xn)

with F(x1, x2, . . . , xn) a quantiﬁer-free formula in the language just deﬁned. In other words, F is a Boolean combination of equalities and inequalities of real polynomials. The decision problem of ETR is the problem of deciding whether a given sentence of the above form is true, that is whether it is a member of ETR. Schaefer (2010) introduced the complexity class R as the class of decision problems that admit a polynomial-time many-one reduction to the decision problem of ETR. Thus, R captures the computational complexity of the existential theory of the reals. We say that a problem A is R-hard if all problems in R reduce to A in polynomial time. We say that A is R-complete if it is contained in R and is R-hard. From the deﬁnition of ETR it is not even clear that the decision problem of ETR is decidable. By introducing a quantiﬁer-elimination procedure, Tarski (1948) showed that ETR is in fact decidable. Since then, a variety of algorithmic improvement have been made over Tarski s procedure, and there exist algorithms with a singly-exponential time dependence in the number of variables (Grigor ev 1988; Renegar 1992). In addition, Canny (1988) obtained the astonishing result that ETR can be solved in polynomial space. Thus R PSPACE. ETR can be used to solve the propositional satisﬁability problem (3SAT); thus, we have the containments NP R PSPACE. Several R-complete problems are known, and many of them are questions of the form can a given combinatorial object be geometrically represented? . Particular examples include recognising intersection graphs of line segments in the plane (Schaefer 2010), of unit disk graphs (Kang and M uller 2012), or of unit distance graphs (Schaefer 2013).

Arrangements of hyperplanes Our exposition and terminology follows Kang and M uller (2012). An (afﬁne) d-hyperplane is a set of form h = {x Rd : c T x = b} Rd for some c Rd and b R. A particular example of a hyperplane, for given p, q Rd, is the set {x Rd : x p = x q } of points that are equidistant to p and q; in two dimensions, this is the perpendicular bisector. Any hyperplane h divides Rd \ h into two connected components, namely the half-planes c T x > b and c T x < b. We can give h an orientation by (arbitrarily) designating one of these components as h s positive side h+, and the other as h s negative side h . We call a hyperplane with a chosen orientation an oriented hyperplane. An oriented hyperplane

arrangement (h1, . . . , hn) is a ﬁnite ordered collection of oriented hyperplanes in Rd. Given a ﬁxed oriented hyperplane arrangement H = (h1, . . . , hn), we can assign to each point x Rd its sign vector σ(x) { , 0, +}n by setting σ(x)i = + if x h+ i , σ(x)i = 0 if x hi, and σ(x)i = if x h i . Thus, the sign vector of x records, for each oriented hyperplane in the arrangement, on which side of the hyperplane x lies. The combinatorial description D(H) = {σ(x) : x Rd} of H is the set of all sign vectors induced by the arrangement H. If D(H) = D(H ), we say that H and H are isomorphic. A connected component of Rd \H = Rd \(h1 hn) is called a cell. All points in the same cell have the same sign vector.

3 The Recognition Problem Here is the formal deﬁnition of the recognition problem whose complexity we will investigate in this section.

d-EUCLIDEAN

Instance: a proﬁle V of strict orders over A Question: is V d-Euclidean?

Proposition 1. d-EUCLIDEAN is contained in R for every d 1. In particular it is contained in PSPACE.

Proof. This is almost immediate from the deﬁnition of d Euclidean preferences. Namely, a proﬁle is d-Euclidean if and only if there exist reals xr,i R for each r A V and i = 1, . . . , d such that whenever a v b, we have

xv xa < xv xb

d i=1 (xv,i xa,i)2 < d i=1 (xv,i xb,i)2 .

Thus, the problem is equivalent to asking whether a system of polynomial inequalities has a solution. This system can be constructed in polynomial time, given the proﬁle.

Our hardness proofs will use the following problem about combinatorial descriptions of hyperplane arrangements.

d-REALISABILITY

Instance: a set S { , +}n of sign vectors with ( , . . . , ), (+, . . . , +) S Question: is there an oriented d-hyperplane arrangement H with S D(H)?

For example, the set S = {(+, +, +, +), ( , +, +, ), ( , +, , +), ( , +, , ), ( , , , +), ( , , , )} is 2-realised by the four red lines in Figure 1, where the red label of the line is placed on the positive side of the line.

Theorem 2 (Kang and M uller 2012). d-REALISABILITY is R-complete for d 2.

Kang and M uller establish this by a reduction from SIMPLE STRETCHABILITY, the problem of deciding whether an arrangement of pseudolines can be stretched into an isomorphic arrangement of lines. That problem is R-complete

Figure 1: 2-Euclidean embedding of a proﬁle obtained from a 2-realisable sign vector set S through the reduction of Theorem 3. Black dots represent voters vσ, positioned within the unit ball and within the cell with sign vector σ induced by the red hyperplanes (lines). The red labels are on the positive side of each line. Blue circles denote the points pi. Blue dots correspond to alternatives; note that ai and bi are at radius R i 2 from the origin.

by Mn ev s (1985) universality theorem, a deep topological result about representing semialgebraic varieties. Shor (1991) gives a direct proof of NP-hardness by a reduction from SAT. We are now ready to prove our main result.

Theorem 3. d-EUCLIDEAN is R-complete for each d 2.

Proof. We have already seen that d-EUCLIDEAN is contained in R (Proposition 1). We now show R-hardness by a reduction from d-REALISABILITY. Let S { , +}n be a given set of sign vectors with ( , . . . , ), (+, . . . , +) S. We construct a proﬁle of |S| votes over a total of 2n alternatives. Precisely, we take as alternatives the set A = {a1, b1, . . . , an, bn}. For each σ S, we introduce a voter vσ with strict order σ such that

{a1, b1} σ {a2, b2} σ σ {an, bn}

and speciﬁed by ai σ bi σi = +, bi σ ai σi = .

This completes the description of the reduction. We now show its correctness. Suppose the proﬁle constructed is d-Euclidean, and let x : V A Rd be a Euclidean embedding. Take the oriented

hyperplane arrangement H = (h1, . . . , hn) deﬁned by

hi = {x Rd : x x(ai) = x x(bi) },

h+ i = {x Rd : x x(ai) < x x(bi) },

h i = {x Rd : x x(ai) > x x(bi) }. Then, clearly, S D(H): Let σ S and let i {1, . . . , d}. If σi = +, we have ai σ bi, and thus by deﬁnition of Euclidean preferences, we must have x(vσ) x(ai) < x(vσ) x(bi) and hence x(vσ) h+ i so that σ(x(vσ))i = + = σi. Similarly if σi = . It follows that σ D(H). Hence S D(H). Conversely, suppose that S D(H) for some oriented d-hyperplane arrangement H. By applying an appropriate scaling map x λx if needed, we may assume that every cell of H intersects the unit ball B(0, 1) Rd. Write H = (h1, . . . , hn) with hi = {x Rd : u T i x = bi}, where without loss of generality ui = 1, so that ui is a unit vector. Further, we will say that h+ i = {x : u T i x > bi} and h i = {x : u T i x < bi}. We now construct a Euclidean embedding x : A V Rd. We start by placing the voter vσ corresponding to σ S at an arbitrary point x(vσ) B(0, 1) of the cell of H with sign vector σ. This exists by our assumption that S D(H). Next, for each i = 1, . . . , d, pick some point pi hi B(0, 1) (this is possible because B(0, 1) meets both h i and h+ i since ( , . . . , ), (+, . . . , +) S). Following an argument by Kang and M uller (2012), we set for r > 0 w+ i,r := pi + rui and w i,r := pi rui,

B+ i,r := B(w+ i,r, r) and B i,r := B(w i,r, r).

Note that B+ i,r h+ i and B i,r h i . In fact (see picture), r>0 B+ i,r = h+ i and r>0 B i,r = h i . Hence, for all r sufﬁciently large, we have

x(vσ) B+ i,r for σ with σi = +, and

x(vσ) B i,r for σ with σi = .

Fix a value R > 4 of r for which this holds. We now pick the positions of the alternatives in the Euclidean embedding: Set

x(ai) = w+ i,R i and x(bi) = w i,R i.

We are left to verify that the map x : A V Rd thus constructed actually corresponds to voters preferences. First let us show that, according to the embedding x, every voter s preference has the form {a1, b1} σ {a2, b2} σ σ {an, bn}. So let vσ be a voter, let 1 i < j n, and let ci {ai, bi} and cj {aj, bj}. Then x(vσ) x(ci) x(vσ) pi + pi x(ci) (triangle inequality) 2 + R i (ui is a unit vector) < R j 2 (j > i and R > 4) x(cj) pj pj x(vσ) (as before) x(vσ) x(cj) . (reverse triangle inequality)

Hence ci σ cj, as desired. Finally, we need to conﬁrm that

x(vσ) x(ai) < x(vσ) x(bi) σi = +.

So suppose σi = +. By choice of R, we have x(vσ) B+ i,R i, so that x(vσ) x(ai) < R i. On the other hand, we have x(vσ) x(bi) R i: for suppose not. Then x(vσ) B i,R i, and thus x(vσ) B+ i,R i B i,R i = , a contradiction.

Certainly, this hardness result implies that it is also hard to recognise d-Euclidean proﬁles of weak orders (since strict orders form a special case). For dichotomous orders, hardness does not follow immediately, but a similar reduction can be used. The argument employed is almost identical to the hardness result for recognising unit disk graphs (Kang and M uller 2012); see the full version (Peters 2016). Theorem 4. For each d 2, it is R-complete to decide whether a proﬁle of dichotomous votes is d-Euclidean.

4 Precision In this section, we consider the question of how many bits are needed to specify a Euclidean embedding x : A V Rd. We only consider the natural encoding where the coordinates of each point are given as rational numbers. Note that if every d-Euclidean proﬁle were to admit an embedding that can be speciﬁed in polynomially many bits, then this would put the problem d-EUCLIDEAN in NP. Yet in this section we show that there is a family of proﬁles which need exponentially many bits in order to specify any Euclidean embedding. This result, by itself, does not rule out that the decision problem d-EUCLIDEAN is in NP: there could be a clever way to certify that an embedding exists, without explicitly giving the embedding. On the other hand, our result shows that the function problem associated with the problem d-EUCLIDEAN is provably not in P. Let us now make precise the notion of the size of an embedding x : A V Rd. Here, we follow the deﬁnitions of Mc Diarmid and M uller (2013). The number of bits needed to store an integer n Z is the number of digits in its binary representation plus its sign: size(n) := 1 + log2(n + 1) . We represent a rational number q Q as a pair of integers representing a fraction: if q = m/n in lowest terms, we set size(q) := size(m) + size(n). The size of a rational vector x Qd is size(x) := d i=1 size(xi). Finally, the size of a rational Euclidean embedding x : A V Qd is

r A V size(x(r)).

Before we establish the promised lower bound, let us ﬁrst give a corresponding upper bound. Namely, while some d Euclidean proﬁles require exponentially many bits to specify, (single-)exponentially many bits are always enough. To see this, we will ﬁrst need a guarantee that every d-Euclidean proﬁle admits a rational embedding, because we have only assigned sizes to rational embeddings. Theorem 5. Every d-Euclidean proﬁle admits a rational embedding. Further, for each d 2, there is a constant

c = c(d) such that any d-Euclidean proﬁle with n voters and m alternatives admits a rational embedding x : A V Qd with size(x) 2c(n+m).

This theorem is an essentially immediate corollary of a general result due to Basu, Pollack, and Roy (1996) about the bit sizes of solutions to polynomial inequalities. For the lower bound, we use techniques developed by Mc Diarmid and M uller (2013) and Kang and M uller (2012) and apply them to the reduction of Theorem 3. The proof appears in the full version of this paper (Peters 2016). For a proﬁle V over alternative set A, we deﬁne V := |V |+|A|.

Theorem 6. Fix d 2. For a d-Euclidean preference proﬁle V , let e(V ) denote the minimum size of a rational Euclidean embedding of V . For each m 1, let e(n + m) be the maximum e(V ) among d-Euclidean preference proﬁles V with V = n + m. Then e(n + m) 2Ω(n+m).

5 Forbidden Subproﬁle Characterisations We say that the proﬁle V contains the proﬁle W if we can obtain W by ﬁrst deleting some alternatives and voters from V , and then relabelling the remaining alternatives and reordering the remaining voters. A preference domain R (that is, a set of proﬁles) may then be characterised by forbidden subproﬁles by giving a set S of proﬁles such that R = {proﬁle V : V does not contain any W S}. We call a preference domain R hereditary if it is closed under containment. That is, if V R and V contains W, then W R. The d-Euclidean domain is hereditary for any d 1. Any hereditary domain R is characterised by its complement R (its set of counterexamples) in this way. Consider a possible characterisation of the d-Euclidean domain by a set S of forbidden subproﬁles. We will call this characterisation good if the set S is polynomial-time recognisable: that is, given a proﬁle, there should be a polynomial-time algorithm deciding whether the given proﬁle is contained in S. Certainly, if S were ﬁnite, then S provides a good characterisation. However, there exist inﬁnite characterisations that are still good in this sense, for example for interval graphs (Lekkerkerker and Boland 1962) and matrices with the consecutive ones property (Tucker 1972). However, given the complexity result of Section 3, it is a straightforward observation that for each d 2, no good characterisation by forbidden substructures will exist for the d-Euclidean domain, subject to a reasonable complexitytheoretic assumption.

Proposition 7. For each d 2, the set of d-Euclidean preference proﬁles does not admit a good characterisation by forbidden substructures unless R co NP.

Proof. Suppose a good characterisation by S exists. We give a co NP-algorithm that recognises d-Euclidean preferences: Given an input proﬁle, guess some subproﬁle, guess a relabeling of voters and alternatives in this subproﬁle, and check whether the result is contained in S.

By a similar argument, no ﬁnite characterisation can exist unless P = R = NP. In the remainder of this section, we prove this weaker result without appealing to any

complexity-theoretic assumptions. To do this, we use a connection between the theory of arrangements of hyperplanes and the theory of ordered matroids. Theorem 8 (Bokowski and Sturmfels 1989). There exist inﬁnitely many nonrealisable uniform oriented matroids of rank 3 such that every proper minor of them is realisable. To prove our result about d-Euclidean preferences, we will use the examples from Theorem 8 and apply to them the chain of many-one reductions that yielded the hardness result of Theorem 3. We present this argument in several lemmas, whose proofs appear in the full version (Peters 2016). Lemma 9. Fix d 2. For every n0 N, there exists n > n0 and a set S { , +}n with (+, . . . , +), ( , . . . , ) S such that S is not d-realisable, but for each i = 1, . . . , n, the set S i = {s i : s S} obtained by deleting coordinate i is d-realisable. Lemma 10. Fix d 2. For every m0 N, there is m > m0 such that there exists a preference proﬁle over m alternatives which is not d-Euclidean, yet removing any alternative yields a d-Euclidean proﬁle. It is worth noting that all these inﬁnitely many minimal counterexamples have the shape {a1, b1} {a2, b2} {an, bn}, and in particular they are single-peaked. Theorem 11. The domain of d-Euclidean preferences does not admit a ﬁnite characterisation by forbidden conﬁgurations, for any ﬁxed d 2.

Proof. Suppose for a contradiction that such a characterisation exists, and let M be the maximum number of alternatives in any of the forbidden conﬁgurations. By Lemma 10, there exists a proﬁle V over at least M +1 alternatives which is not d-Euclidean. Since the forbidden conﬁgurations characterise the d-Euclidean domain, one of the conﬁgurations must be contained in V . Considering the size of the conﬁguration, it must be contained in V even with one alternative deleted. However this proﬁle is d-Euclidean, contradicting the fact that the d-Euclidean domain is hereditary.

6 Other metrics We have deﬁned Euclidean preferences using the usual Euclidean ℓ2-metric, measuring distances by shortest paths in the plane. Other choices of metric may be preferred in certain contexts. We now look at the ℓ1-metric and the ℓ - metric. The ℓ1-metric is also known as the cityblock or Manhattan distance, because it measures distances by shortest paths on a grid like the street network of Manhattan. Formally, the ℓ1-norm is deﬁned by

(x1, . . . , xd) 1 := |x1| + + |xd|.

Thus, the ℓ1-distance x y 1 of two points x and y is the sum of the absolute distances along each coordinate axis. The ℓ -metric, on the other hand, measures the maximum distance along a coordinate axis:

(x1, . . . , xd) := max{|x1|, . . . , |xd|}.

For each of these metrics (or indeed, any metric space), we can obtain a notion of d-Euclidean preferences. For certain

settings, the ℓ metric has a nice interpretation as corresponding to pessimistic voters who judge candidate according to their (subjectively) worst feature. The ℓ1 metric also has intuitive appeal see Eguia (2011) and the references therein for arguments in favour of using Euclidean preferences with respect to this metric. Comparing the ℓ1and ℓ -metrics to the ℓ2-metric we have used so far, one gets the sense that ℓ1 and ℓ are more discrete or combinatorial than the more geometric ℓ2. Supporting this intuition, we ﬁnd that the complexity of the recognition problem changes (unless NP = R):

Theorem 12. The problems of recognising preference proﬁles that are d-Euclidean with respect to the ℓ1-metric or the ℓ -metric are contained in NP for every d 1.

Proof. We start with the ℓ1-metric and show containment in NP by giving a nondeterministic reduction to linear programming. For each of the d coordinate axes of Rd, nondeterministically guess in which order the points corresponding to voters and alternatives appear along that axis. Once we have decided these orderings, we can rewrite the deﬁnition of ℓ1-Euclidean preferences without using absolute values. Then, we can replace strict inequalities with weak inequalities by introducing additive slack constants (Elkind and Faliszewski 2014, Prop. 3). The result is a linear program producing an ℓ1-Euclidean embedding if one exists.

dv,c,i = (xv,i xc,i) (distance from v to c along i)

dv,c = d i=1 dv,c,i (distance from v to c) dv,a dv,b 1 when a v b

xy,i xy ,i 1 when y occurs left of y on axis i

In constraints of the ﬁrst form, the can be replaced by plus or minus at compile -time so that the quantity reﬂects |xv,i xc,i|. The argument for the ℓ -metric is similar: here we additionally guess for each pair (v, c) in which direction the maximum distance is achieved.

7 Conclusions The results of this paper are bad news for the d-Euclidean domain: because producing a Euclidean embedding will in general be infeasible, we are stuck with heuristic algorithms that may or may not produce a correct output in their allotted time. In some sense, our hardness results show that the estimation algorithms developed for the multidimensional unfolding problem over the past several decades are best possible, in the sense that we cannot hope for exact efﬁcient algorithms. Still, future developments in ETR-solver technology might allow solving practical instances in reasonable time, and perhaps some of the ideas in the area of multidimensional unfolding can be formalised and yield exact algorithms. We have run some preliminary experiments on the Pref Lib dataset (Mattei and Walsh 2013) using the nlsat solver (Jovanovi c and De Moura 2012) which appears to be the strongest ETR-solver available. However, nlsat was unable to decide whether any of the non-trivial Pref Lib proﬁles that we tried was 2or 3-Euclidean within a time bound of one hour.

Acknowledgements I thank Edith Elkind and Martin Lackner for helpful discussions, several anonymous reviewers for their feedback, and J urgen Bokowski for correspondence about the theory of oriented matroids. This work was supported by EPSRC and by ERC under grant number 639945 (ACCORD).

References Anshelevich, E.; Bhardwaj, O.; and Postl, J. 2015. Approximating optimal social choice under metric preferences. In AAAI 15, 777 783. Ballester, M. A., and Haeringer, G. 2011. A characterization of the single-peaked domain. Social Choice and Welfare 36(2):305 322. Bartholdi, J., and Trick, M. A. 1986. Stable matching with preferences derived from a psychological model. Operations Research Letters 5(4):165 169. Basu, S.; Pollack, R.; and Roy, M.-F. 1996. On the combinatorial and algebraic complexity of quantiﬁer elimination. Journal of the ACM 43(6):1002 1045. Bennett, J. F., and Hays, W. L. 1960. Multidimensional unfolding: Determining the dimensionality of ranked preference data. Psychometrika 25(1):27 43. Betzler, N.; Slinko, A.; and Uhlmann, J. 2013. On the computation of fully proportional representation. Journal of Artiﬁcial Intelligence Research 47(1):475 519. Bogomolnaia, A., and Laslier, J.-F. 2007. Euclidean preferences. Journal of Mathematical Economics 43(2):87 98. Bokowski, J., and Sturmfels, B. 1989. An inﬁnite family of minorminimal nonrealizable 3-chirotopes. Mathematische Zeitschrift 200(4):583 589. Borg, I., and Groenen, P. J. 2005. Modern multidimensional scaling: Theory and applications. Springer Science & Business Media. Brandt, F.; Brill, M.; Hemaspaandra, E.; and Hemaspaandra, L. A. 2015. Bypassing combinatorial protections: Polynomial-time algorithms for single-peaked electorates. Journal of Artiﬁcial Intelligence Research 53:439 496. Bredereck, R.; Chen, J.; and Woeginger, G. J. 2013. A characterization of the single-crossing domain. Social Choice and Welfare 41(4):989 998. Bruner, M.-L., and Lackner, M. 2015. On the likelihood of singlepeaked preferences. Technical Report ar Xiv:1505.05852 [cs.GT]. Busing, F. M.; Groenen, P. J.; and Heiser, W. J. 2005. Avoiding degeneracy in multidimensional unfolding by penalizing on the coefﬁcient of variation. Psychometrika 70(1):71 98. Canny, J. 1988. Some algebraic and geometric computations in PSPACE. In STOC 88, 460 467. Chen, J.; Pruhs, K.; and Woeginger, G. J. 2015. The onedimensional Euclidean domain: Finitely many obstructions are not enough. Technical Report ar Xiv:1506.03838 [cs.GT]. Coombs, C. H. 1964. A Theory of Data. John Wiley & Sons. Doignon, J.-P., and Falmagne, J.-C. 1994. A polynomial time algorithm for unidimensional unfolding representations. Journal of Algorithms 16(2):218 233. Eguia, J. X. 2011. Foundations of spatial preferences. Journal of Mathematical Economics 47(2):200 205. Elkind, E., and Faliszewski, P. 2014. Recognizing 1-Euclidean preferences: An alternative approach. In Algorithmic Game Theory. Springer. 146 157. Elkind, E., and Lackner, M. 2015. Structure in dichotomous preferences. In IJCAI 15, 2019 2025.

Elkind, E.; Faliszewski, P.; and Skowron, P. 2014. A characterization of the single-peaked single-crossing domain. In AAAI 14, 654 660. Elkind, E.; Faliszewski, P.; and Slinko, A. 2012. Clone structures in voters preferences. In EC 12, 496 513. Elkind, E.; Lackner, M.; and Peters, D. 2016. Preference restrictions in computational social choice: Recent progress. In IJCAI 16, 4062 4065. Escofﬁer, B.; Lang, J.; and Ozt urk, M. 2008. Single-peaked consistency and its complexity. In ECAI 08, 366 370. Faliszewski, P.; Hemaspaandra, E.; Hemaspaandra, L. A.; and Rothe, J. 2011. The shield that never was: Societies with singlepeaked preferences are more open to manipulation and control. Information and Computation 209(2):89 107. Grigor ev, D. Y. 1988. Complexity of deciding Tarski algebra. Journal of Symbolic Computation 5(1):65 108. Jovanovi c, D., and De Moura, L. 2012. Solving non-linear arithmetic. In Automated Reasoning. Springer. 339 354. Kang, R. J., and M uller, T. 2012. Sphere and dot product representations of graphs. Discrete & Computational Geometry 47(3):548 568. Lekkerkerker, C. G., and Boland, J. 1962. Representation of a ﬁnite graph by a set of intervals on the real line. Fundamenta Mathematicae 51(1):45 64. Mattei, N., and Walsh, T. 2013. Preﬂib: A library for preferences http://www.preﬂib.org. In Algorithmic Decision Theory. Springer. 259 270. Mc Diarmid, C., and M uller, T. 2013. Integer realizations of disk and segment graphs. Journal of Combinatorial Theory, Series B 103(1):114 143. Merrill, S., and Grofman, B. 1999. A uniﬁed theory of voting: Directional and proximity spatial models. Cambridge University Press. Mn ev, N. E. 1985. Realizability of combinatorial types of convex polyhedra over ﬁelds. Journal of Soviet Mathematics 28(4):606 609. Peters, D., and Elkind, E. 2016. Preferences single-peaked on nice trees. In AAAI 16, 594 600. Peters, D., and Lackner, M. 2017. Preferences single-peaked on a circle. In AAAI 17. Peters, D. 2016. Recognising multidimensional Euclidean preferences. ar Xiv:1602.08109 [cs.GT]. Renegar, J. 1992. On the computational complexity and geometry of the ﬁrst-order theory of the reals. Journal of Symbolic Computation 13(3):255 299. Schaefer, M. 2010. Complexity of some geometric and topological problems. In Graph Drawing: 17th International Symposium, volume 5849, 334 344. Springer. Schaefer, M. 2013. Realizability of graphs and linkages. In Thirty Essays on Geometric Graph Theory. Springer. 461 482. Shor, P. 1991. Stretchability of pseudolines is NP-hard. Applied Geometry and Discrete Mathematics, Amer. Math. Soc., Providence, RI 4:531 554. Tarski, A. 1948. A decision method for elementary algebra and geometry. Rand report. Rand Corporation. Trick, M. A. 1989. Recognizing single-peaked preferences on a tree. Mathematical Social Sciences 17(3):329 334. Tucker, A. 1972. A structure theorem for the consecutive 1 s property. Journal of Combinatorial Theory, Series B 12(2):153 162.