# understanding_distance_measures_among_elections__942faa5b.pdf

Understanding Distance Measures Among Elections

Niclas Boehmer1 , Piotr Faliszewski2 , Rolf Niedermeier1 , Stanisław Szufa2 and Tomasz W as2,3

1Technische Universität Berlin, Algorithmics and Computational Complexity 2AGH University 3University of Warsaw niclas.boehmer@tu-berlin.de, faliszew@agh.edu.pl, szufa@agh.edu.pl, t.was@mimuw.edu.pl

Motivated by putting empirical work based on (synthetic) election data on a more solid mathematical basis, we analyze six distances among elections, including, e.g., the challenging-to-compute but very precise swap distance and the distance used to form the so-called map of elections. Among the six, the latter seems to strike the best balance between its computational complexity and expressiveness.

1 Introduction

We study the properties of several distances (metrics) among elections.1 We focus on the ordinal model, where each voter ranks the candidates from the most to the least appealing one, and on metrics that are independent of renaming the candidates and voters. Such metrics were introduced by Faliszewski et al. [2019], who argued about their usefulness to compare two elections generated from some statistical models, or to evaluate which statistical model is most likely to generate elections similar to given real-life ones. Indeed, in such applications the names of the candidates and voters do not carry any information and should be disregarded. Unfortunately, while the metrics studied by Faliszewski et al. [2019] are naturally motivated for example, one of them extends the widely accepted swap distance many of them are not only NP-hard to compute (even approximately), but also difficult to compute in practice. Yet, many of the motivating ideas of Faliszewski et al. [2019] were soon implemented in the maps of elections, introduced by Szufa et al. [2020] and extended by Boehmer et al. [2021b]. Briefly put, such a map is a collection of election instances, typically generated from some statistical models (but Boehmer et al. [2021b] also used real-life ones from Pref Lib [Mattei and Walsh, 2013]), together with their distances. The elections are represented graphically as points in the plane, whose Euclidean distances are as similar to the distances between the respective elections as possible. Since maps of elections typically contain hundreds of elections, instead of using the appealing-but-hard-to-compute extension

1Generally, we use the word distance when we refer to a value of a metric, but occasionally, reflecting the literature, we break this rule (e.g., to speak of the earth mover s distance or the swap distance).

of the swap distance, Szufa et al. [2020] introduced and used a much simpler metric. Yet, the maps proved to be quite useful. For example, Szufa et al. [2020] used their map to find hard instances for some multiwinner voting rule, Boehmer et al. [2021b] and Boehmer and Schaar [2022] obtained insights about different types of real-life elections, and Boehmer et al. [2021a] used the maps to study the robustness of elections. In this work, we take a step back and analyze the properties of several metrics, including those of Faliszewski et al. [2019] and Szufa et al. [2020]. Our goal is to help putting empirical work with election data on a more solid mathematical basis and, in particular, to understand if basing the election maps on the simpler metric was a good decision, what was its price, and if one should have used other metrics. We view the swap distance as a yardstick against which we measure the other ones. In particular, we consider the following issues: 1. As a basic test, we compare the metrics ability to distinguish nonisomorphic elections. Since some metrics act on aggregate representations of elections, they may sometimes fail at this task. We also study the complexity of computing an election with a given representation. 2. We analyze distances between four compass elections, which capture four types of (dis)agreement among the voters [Boehmer et al., 2021b]. We find that two of them are the most distant elections under each of our metrics. 3. We compute the correlation between the values provided by the swap distance and the other metrics; we also compare the maps that they produce. 4. We note that the swap distance can be understood in terms of the shortest paths on a certain graph and we analyze to what extent this applies to the other metrics. Some proofs and arguments are deferred to our full version [Boehmer et al., 2022].

2 Preliminaries For an integer n, let [n] := {1, . . . , n}. Let C be set of candidates. By L(C) we denote the set of all total orders over C, referred to either as preference orders or votes, depending on the context. Elections. An election E = (C, V ) consists of a candidate set C = {c1, . . . , cm} and a preference profile V = (v1, . . . , vn), where each vi is a preference order from L(C).

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)

For example, a preference order vi : a b c indicates that the i-th voter ranks candidate a highest, followed by candidates b and c. Given a vote v and a candidate c, we write posv(c) to denote the position of c in v (the top-ranked candidate has position 1, the next one has position 2, and so on). Example 1. Consider elections E = (C, V ) and E = (C , V ), where C = {a, b, c}, C = {x, y, z}, V = (v1, v2, v3), V = (v 1, v 2, v 3), and the votes are: v1 : a b c, v2 : b c a, v3 : b a c,

v 1 : x y z, v 2 : x y z, v 3 : y x z. Aggregate Representations. Let E = (C, V ) be an election. We use the following aggregate representations of E: 1. For each two candidates c, d C, ME(c, d) is the number of voters that prefer c to d in election E. We call it the weighted majority relation and represent it as an m m matrix where rows and columns correspond to the candidates (the diagonal is undefined). A relative weighted majority relation is a weighted majority relation from whose entries we subtract n/2 (let n be even here). 2. For a candidate c C and a position i [m], PE(c, i) is the number of voters from E that rank c on position i; PE(c) = (PE(c, 1), . . . , PE(c, m)) is a (column) position vector of c. We view PE as a matrix with columns PE(c1), . . . , PE(cm) and call it a position matrix.

3. For a candidate c C, BE(c) := Pn i=1 m posvi(c)

is the Borda score of c in E. Then, BE is the Borda score vector, whose entries correspond to the candidates. Example 2. Below we provide ME, PE, and BE, respectively, for election E from Example 1:

, a b c 3 5 1 .

(Pseudo)Metrics. Given a set X, a function d: X X R is a pseudometric over X if for each three elements a, b, c X it holds that (i) d(a, b) = d(b, a) 0, (ii) d(a, a) = 0, and (iii) d(a, c) d(a, b) + d(b, c). For brevity, we will refer to our pseudometrics as metrics (formally, a metric should assume value 0 only if both its arguments are identical). Metrics Among Vectors. Let x = (x1, . . . , xn) and y = (y1, . . . , yn) be two real-valued vectors. Then, ℓ1(x, y) := |x1 y1| + + |xn yn| is the ℓ1-metric between x and y. Given a real-valued vector z = (z1, . . . , zn), we write ˆz to denote its prefix-sum variant, i.e., an n-dimensional vector such that for each i [n], its i-th entry is ˆzi = z1 + z2 + + zi. If the entries of x and y sum up to the same value and contain only nonnegative entries, then their earth mover s distance is defined as [Rubner et al., 2000]: emd(x, y) := ℓ1(ˆx, ˆy). Alternatively, emd(x, y) is defined as the minimum total cost of a sequence of operations that transform vector x into vector y, where each operation is of the form subtract value α from some xi (where, at the time of performing the operation, we have xi α) and add α to xj and has cost α |j i|. Both definitions are equivalent [Rubner et al., 2000].

Bijections. Given two equal-sized sets X and Y , let Π(X, Y ) denote the set of all one-to-one mappings from X to Y . For a positive integer n, let Sn be the set of all permutations of [n] (i.e., Sn = Π([n], [n])). Given two equalsized candidate sets C and D, a preference order v L(C), and a function σ Π(C, D), we write σ(v) to denote the preference order obtained from v by replacing each candidate c C with the candidate σ(c) D. Given a preference profile V = (v1, . . . , vn) (L(C))n, by σ(V ) we mean (σ(v1), . . . , σ(vn)). We use analogous notation for other objects defined over candidate sets. For example, for an election E = (C, V ), we write σ(ME) to denote the weighted majority relation of the election (σ(C), σ(V )) = (D, σ(V )).

3 Metrics Among Elections

In this section, we define the six metrics among elections that we study. All but the last one already appeared in the literature. We only consider distances between elections with the same numbers of candidates and the same numbers of voters.

Swap and Discrete Isomorphic Metrics Let C be a candidate set and let u, v L(C) be two votes. Their discrete distance, ddisc(u, v), is 0 if they are identical and it is 1 otherwise. Their swap distance, dswap(u, v), is the number of inversions between u and v, i.e., the number of pairs of candidates c, d C such that u and v rank these candidates in opposite order. Let d be either ddisc or dswap. For two elections, E = (C, V ) and E = (C , V ), where |C| = |C |, V = (v1, . . . , vn), and V = (v 1, . . . , v n), Faliszewski et al. [2019] extended d to elections as follows:

d(E, E ) := minσ Π(C,C ) minρ Sn Pn i=1 d σ(vi), v ρ(i) .

In other words, under the extended distance we match the candidates and the votes of the two input elections so that the sum of the distances between the matched votes is minimal.

Example 3. The discrete distance between elections E and E from Example 1 is one, as witnessed by the candidate matching σ(a) = x, σ(b) = y, and σ(c) = z. For the same matching, the swap distance between E and E is two.

We refer to the extensions of ddisc and dswap as the discrete and swap isomorphic metrics. This stems from the fact that two elections are isomorphic (i.e., can be made identical by renaming candidates and reordering the votes) if and only if their discrete distance (equivalently, swap distance) is zero. Faliszewski et al. [2019] have shown that while computing the discrete isomorphic distance can be done in polynomial time, the same task for the swap distance is NP-hard (in essence, this follows from the hardness proofs for the Kemeny voting rule [Bartholdi et al., 1989; Dwork et al., 2001]).

Positionwise and Pairwise Metrics To circumvent the hardness of computing the isomorphic swap distance, Szufa et al. [2020] introduced two other metrics, based on analyzing aggregate representations of elections. Let E = (C, V ) and E = (C , V ) be two elections such that |C| = |C | and |V | = |V |. The EMD-positionwise

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)

distance between E and E is:

demd pos (E, E ):= min σ Π(C,C )

c C emd PE(c), PE (σ(c) .

Note that we view each candidate as her or his position vector and we seek a candidate matching that minimizes the earth mover s distances between the vectors of matched candidates.

Example 4. Consider the same elections and the same matching σ as in Example 3. We have that PE(a) = (1, 1, 1), whereas PE (σ(a)) = (2, 1, 0) and their earth mover s distance is 2. Altogether, demd pos (E, E ) = 2 + 1 + 1 = 4.

Szufa et al. [2020] based their metric on EMD because they felt it was intuitively appropriate. We aim to verify this intuition and, thus, we also consider the ℓ1-positionwise metric, which uses the ℓ1 distance instead of EMD. Szufa et al. [2020] also introduced the pairwise metric, which works on top of the weighted majority relation:

dpair(E, E ) := min σ Π(C,C )

|ME(a, b) ME (σ(a), σ(b))|.

Example 5. Take the elections from Example 1 and matching σ (a) = y, σ (b) = x, and σ (c) = z; ME and σ (ME ) are:

σ (a) σ (b) σ (c)

and we see that the pairwise distance of our elections (for this matching) is 0 + 1 + 0 + 0 + 1 + 0 = 2. The positionwise distances can be computed in polynomial time [Szufa et al., 2020], whereas the pairwise distance is NP-hard to compute [Grohe et al., 2018; Szufa et al., 2020]).

Bordawise Metric We introduce one new metric, similar in spirit to the positionwise and pairwise ones, but defined on top of the election s Borda score vectors. Given two equal-sized elections E and E , their Bordawise distance is defined as:

d Borda(E, E ) := emd(sort(BE), sort(BE )),

where for a vector x, sort(x) means a vector obtained from x by sorting it in nonincreasing order. The Bordawise metric is defined to be as simple as possible, while trying to still be meaningful. For example, sorting the score vectors ensures that two isomorphic elections are at distance zero and removes the use of an explicit matching between the candidates. Example 6. The distance between the elections from Example 1 is emd (5, 3, 1), (5, 4, 0) = 1.

4 Aggregate Representations First, we discuss how the aggregate representations that underlie our metrics affect their ability to distinguish nonisomorphic elections. Then, we study the complexity of deciding if a given representation indeed corresponds to some election.

|C| |V | ANECs Positionwise Pairwise Bordawise

3 3 10 10 8 8 3 4 24 23 17 13 3 5 42 40 25 18

4 3 111 93 50 37 4 4 762 465 200 76 4 5 4095 1746 513 131

Table 1: Number of equivalence classes under our metrics.

Given a metric, two elections are in the same equivalence class if their distance is zero. An anonymous, neutral equivalence class (ANEC) consists of all isomorphic elections with a given number of candidates and voters [E gecio glu and Giritligil, 2013]. While ANECs are the equivalence classes of the swap and discrete metrics, the other metrics are less precise and their equivalence classes are unions of some ANECs. To get a feeling as to how much precision is lost due to various aggregate representations, in Table 1 we compare the number of ANECs and the numbers of equivalence classes of the positionwise, pairwise, and Bordawise metrics, for small elections; we computed the table using exhaustive search2 (note that EMDand ℓ1-positionwise metrics have the same equivalence classes). Among these metrics, positionwise ones perform best and Bordawise performs worst. Next, we provide a partial theoretical explanation for this observation. We say that a metric d is at least as fine as a metric d if for each two elections A and B, d(A, B) = 0 implies that d (A, B) = 0 (i.e., each equivalence class of d is a subset of some equivalence class of d ). Metric d is finer than d if it is at least as fine as d but d is not at least as fine as d. Proposition 1. Swap and discrete isomorphic metrics are finer than EMD/ℓ1-positionwise and pairwise, which both are finer than Bordawise. Neither EMD/ℓ1-positionwise is finer than pairwise nor the other way round. Nonetheless, having many equivalence classes does not automatically make a metric desirable. For example, the discrete isomorphic metric is as fine as the swap one, but has many unappealing properties. Let us now move to the problem of deciding if a given matrix/vector indeed represents some election. For position matrices, Boehmer et al. [2021b] have shown this to be easy: If a matrix M has nonnegative entries and its rows and columns sum up to the same value, then there is a polynomial-time computable election E with M = PE. Hence, one can work directly on the matrices and recover elections when needed. Unfortunately, for Borda score vectors and weighted majority relations analogous problems are NP-complete. Thus, by operating on them directly, we may leave the space of elections. Theorem 1. Given a vector x of nonnegative integers, it is NP-complete to decide if there is an election E with BE = x. The hardness of deciding whether there is an election with a given Borda score vector is not too surprising because it is closely related to strategic voting under the Borda rule, which is also NP-complete [Betzler et al., 2011]. The case of weighted majority relation is more intriguing because

2There are exact formulas for some columns in Table 1, but not for all. See, e.g., the work of E gecio glu and Giritligil [2013].

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)

the classic Mc Garvey s theorem [Mc Garvey, 1953] gives a polynomial-time algorithm for recovering an election with a given relative weighted majority relation (but see also the work of Bachmeier et al. [2019]). Theorem 2. Given an m m matrix M, it is NP-complete to decide if there is an election E with ME = M.

Proof (First Part). We reduce from the NP-complete RESTRICTED X3C problem (RX3C) [Gonzalez, 1985]. Its instances consist of a universe X = {x1, . . . , x3t} and a family S = {S1, . . . , S3t} of size-3 subsets of X, where each xi appears in exactly three sets from S. We ask if there is a family S S of t sets such that S Si S Si = X (i.e., we ask if there is an exact cover of X). Let (X, S) be an instance of RX3C. We form a candidate set:

C = {d} X {s1. . . . , s3t} {b1, b2, b3} A F,

where A = {a1, . . . , a3t} and F = {f1, . . . , f3t} are sets of location candidates. The candidates s1, . . . , s3t correspond to the sets from S, b1, b2, b3 will delineate blocks in the votes, and d will be used to encode the exact cover (if one exists). For each i [3t], by A(i) and F(i) we mean the orderings:

A(i): a1 ai si ai+1 a3t, F(i): f1 s1 f2 s2 fi 1 si 1 fi fi+1 si+1 . . . f3t s3t.

For a subset C C of candidates, [C ] denotes an arbitrary, fixed ordering of the candidates from C . For every Si = {xj, xk, xℓ} S, let vi denote the following vote:

b1 xj xk xℓ b2 A(i) [X \ Si] b3 F(i).

Let E = (C \ {d}, (v1, . . . , v3t)) be an election. We form a weighted majority relation M by taking ME and extending it to include d as follows: We require that d is placed behind b1 in exactly t votes, d is placed behind each candidate from X in exactly one vote, and d is never placed behind any other candidate. We claim that there is an election E such that M = ME if and only if S contains an exact cover of X. First, let S S be an exact cover of X. To construct E, for each Si S , we include vote vi with d inserted right in front of b2, and for each Si S \ S , we include vi with d inserted before b1. As S is an exact cover, M = ME. The other direction is available in our full version.

5 Diameter and Compass Elections In this section, we analyze the distances between four compass elections of Boehmer et al. [2021b]. These elections capture four different types of (dis)agreement among the voters and, thus, we expect good metrics to put them far apart. Since the smallest nonzero distances under all our metrics are either 1, 2, or 4, the larger are the distances between the compass elections, the more space there is between them for other elections. For technical reasons, we fix the number m of candidates to be even, and the number of voters to be n = t m!, where t is some positive integer (we will see ways to relax this assumption). The compass elections are defined as follows:

1. In the identity elections, denoted ID, all voters have the same, fixed preference order.

2. In the antagonism elections, denoted AN, half of the voters rank the candidates in one way and half of the voters rank them in the opposite way.

3. In the uniformity elections, denoted UN, each possible vote appears the same number of times.

4. In the stratification elections, denoted ST, the candidates are partitioned into two equal-sized sets A and B. Each possible preference order where all members of A are ranked ahead of B appears the same number of times.

The next proposition gives asymptotic distances between the compass elections.

Proposition 2. Let X and Y be two distinct compass elections. Then, d Borda(X, Y ) = Θ(nm3), dswap(X, Y ) = demd pos (X, Y ) = dpair(X, Y ) = Θ(nm2), dℓ1 pos(X, Y ) = Θ(nm), and ddisc(X, Y ) = Θ(n), except that dpair(AN, UN) = d Borda(AN, UN) = 0.

The distances between the compass elections are the largest under the swap and EMD-positionwise metrics, followed by those under ℓ1-positionwise and discrete isomorphic metrics. Pairwise and Bordawise metrics perform particularly badly because they cannot distinguish between UN and AN. Yet, except for this, the compass elections are asymptotically as distant under each of our metrics as possible. Indeed, ID and UN even form diameters of our election spaces (this also confirms a conjecture of Boehmer et al. [2021b]).

Theorem 3. Let d be one of our six metrics. For each two elections X and Y (with sizes as specified at the beginning of this section) it holds that d(X, Y ) d(ID, UN).

Proof (EMD-positionwise). The EMD-positionwise metric can be seen as working over matrices whose entries are nonnegative and whose rows and columns sum up to the same value. Let A and B be two such matrices, whose rows and columns sum up to some value n . Let A/n and B/n be the same matrices, but with their entries divided by n . Note that demd pos (A, B) = n demd pos (A/n , B/n ). From now on, we focus on matrices whose entries are nonnegative and whose rows and columns sum up to 1 (they are called bistochastic). Boehmer et al. [2021b] have shown that demd pos (ID, UN) =

n(m2 1)/3. We claim that for each two m m bistochastic matrices X and Y it holds that demd pos (X, Y ) (m2 1)/3. For the sake of contradiction, assume that the opposite holds. Let x1, . . . , xm be the columns of X and y1, . . . , ym be the columns of Y . Without loss of generality, we assume that demd pos (X, Y ) = P i [m] emd(xi, yi); otherwise we could reorder the columns of one of the matrices. By definition of the EMD metric, we have that P i [m] emd(xi, yi) = P i [m] ℓ1(ˆxi, ˆyi). For each i [m], we write ˆxi,1, . . . , ˆxi,m to denote the entries of the cumulative vector ˆxi; we use analogous notation for ˆyi. Note that in the matrices with columns ˆx1, . . . , ˆxm and ˆy1, . . . , ˆym, for each j [m], the j-th row sums up to j (we refer to this as the cumulative rows property). Using these observations, we note that: P i [m]emd(xi, yi) = P i [m] ℓ1(ˆxi, ˆyi)

= P i,j [m] |ˆxi,j ˆyi,j|

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)

= P i,j [m] max(ˆxi,j, ˆyi,j) min(ˆxi,j, ˆyi,j)

= P i,j [m](ˆxi,j + ˆyi,j) 2 P i,j [m] min(ˆxi,j, ˆyi,j)

= 2 P j [m] j 2 P i,j [m] min(ˆxi,j, ˆyi,j)

= m(m + 1) 2 P i,j [m] min(ˆxi,j, ˆyi,j).

Thus, if demd pos (X, Y ) > (m2 1)/3, then it must hold that:

P i,j [m] min(ˆxi,j, ˆyi,j) < 1

2 m(m + 1) m2 1

= (2m2 + 3m + 1)/6 = (2m + 1)(m + 1)/6.

In the following, for each i, k [m] with i + k > m, if i + k is used as a column index, then we take it to be i + k m (i.e., column indices cycle ). For each k [m], we have demd pos (X, Y ) P i [m] emd(xi, yi+k); if this were not the case, then our assumption that demd pos (X, Y ) = P i [m] emd(xi, yi) would have been false. Consequently, for every k [m], repeating the above reasoning, we get: P i,j [m] min(ˆxi,j, ˆyi+k,j) < (2m + 1)(m + 1)/6,

If a, b [0, 1] then a b min(a, b). As for each i, j [m] we have ˆxi,j, ˆyi,j [0, 1], for each k [m] we have: P i,j [m] ˆxi,j ˆyi+k,j < (2m + 1)(m + 1)/6.

By summing this inequality sidewise for all k [m], we get: P i,j [m] ˆxi,j P k [m] ˆyk,j < m(2m + 1)(m + 1)/6.

By applying the cumulative rows property, we obtain: Pm j=1 j2 < m(2m + 1)(m + 1)/6.

Since we know that Pm j=1 j2 = m(2m + 1)(m + 1)/6, this is a contradiction. Hence, for all m m bistochastic matrices X, Y we have demd pos (X, Y ) (m2 1)/3. Thus, for all elections with m candidates and n voters, their EMDpositionwise distance is at most n(m2 1)/3.

In the above proof we do not work directly with elections, but, rather, with normalized position matrices. Viewed this way, ID is a unit diagonal matrix and UN is a matrix whose entries are all equal. Indeed, this is how Boehmer et al. [2021b] defined them. In this way, the proof works for any number of voters (this also applies to ℓ1-positionwise and, using normalized weighted majority relations, to pairwise). For Bordawise, the proof of Theorem 3 shows that for each election the sum of its distances from ID and UN is the same. That is, under this metric every election lays on the diameter.

6 Maps and Correlations

While in the previous section we studied distances between hand-crafted elections, now we analyze automaticallygenerated ones. We test how our metrics correlate with the swap one, and we compare their maps of elections. We use two datasets. The first one consists of all small elections, as in Section 4. The second one resembles those used in the maps of Szufa et al. [2020] and Boehmer et

|C| |V | EMD-Pos. ℓ1-Pos. ℓ1-Pair. Bordawise Discrete

3 3 0.942 0.748 0.860 0.587 0.614 3 4 0.900 0.697 0.860 0.659 0.636 3 5 0.920 0.759 0.843 0.606 0.680

4 3 0.850 0.577 0.735 0.442 0.402 4 4 0.782 0.561 0.689 0.415 0.434 4 5 0.772 0.567 0.672 0.439 0.432

10 50 (340 elections) 0.745 0.563 0.708 0.430 0.342

Table 2: Pearson correlation coefficients between swap distances and the other ones computed for our datasets.

al. [2021b], but consists of elections with 10 candidates and 50 voters,3 generated according to the following statistical models (see the just-cited papers for more details): IC, Urn, and Mallows. We generated 20 elections using the impartial culture model (IC), where each vote is selected uniformly at random, and 60 elections for each of the classic urn and Mallows models (we used the same sampling protocol as Boehmer et al. [2021b]). SP, SC, and SPOC. We generated 20 single-peaked elections (SP elections) uniformly at random (this is known as the SP Walsh model [Walsh, 2015]), 20 such elections using the Conitzer model [Conitzer, 2009], and 20 single-peaked on a circle elections (SPOC elections), uniformly at random [Peters and Lackner, 2020]. We also generated 20 singlecrossing elections (SC elections) using the sampling protocol of Szufa et al. [2020]. Euclidean. In these elections, each candidate and voter is a point from some Euclidean space and the voters rank the candidates with respect to their increasing distances from them. We have generated the points uniformly at random from (i) a 1D interval, (ii) a 2D sphere, (iii) a 2D disc, and (iv) a 3D cube; in each case we generated 20 elections. Group-Separable. Group-separable elections were introduced by Inada [1964; 1969]. We use a definition based on trees (see, e.g., the works of Karpov [2019] and Faliszewski et al. [2022] for a discussion and motivation). Consider an ordered, rooted tree where each leaf is a unique candidate. To obtain a vote, for each of the nodes we can choose to reverse the order of its children and, then, rank the candidates by reading them off from left to right. Given such a tree, we sample a vote by reversing the order of each node s children with probability 1/2. We generated 20 elections using complete binary trees, and 20 elections using binary caterpillar trees (a binary caterpillar tree is defined recursively to either be a leaf, or a root whose one child is a leaf and whose other child is a root of a binary caterpillar tree.) For each dataset we have computed the Pearson Correlation Coefficient (PCC) between the swap distances and those provided by the other metrics. PCC is a classic measure of correlation that takes values between 1 and 1; its absolute value gives the strength of the correlation and the sign indicates its positive or negative nature. Szufa et al. [2020]

3This is the largest size for which we could compute swap distances within a few weeks. Szufa et al. [2020] used 100 100 elections, and Boehmer et al. [2021b] used 10 100 ones.

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)

(a) Isomorphic swap

(b) EMD-positionwise

(c) ℓ1-positionwise

(d) Pairwise

(e) Bordawise

Figure 1: Maps of elections prepared using each of our metrics.

presented a similar experiment, but on a much smaller scale, and on a limited set of metrics. We present our results in Table 2. We see that EMD-positionwise is most strongly correlated with the swap metric, with a large advantage over all the metrics, except for pairwise (where the advantage is smaller). Next, we used the techniques of Szufa et al. [2020] to draw the maps of elections from the 10 50 dataset. We show these maps in Figure 1 (we omit the discrete metric as its visualization is nearly meaningless); each dot is an election, its color corresponds to the statistical model it comes from, and the points are placed so that their Euclidean distances resemble those according to a given metric as much as possible (following Szufa et al. [2020], we used the algorithm of Fruchterman and Reingold [1991] to place the points). We also included the compass elections on the maps (for the swap metric, their location is approximate). The maps provided by the isomorphic swap distance and both positionwise metrics are remarkably similar, but, nonetheless, there are some differences. For example, under the swap metric group-separable caterpillar elections are closer to the IC ones than the group-separable balanced elections (both on the map and in terms of actual distances), whereas according to the positionwise metrics this relation is reversed. Also, ℓ1-positionwise clearly distinguishes between 2D-Sphere and group-separable balanced elections (like the swap metric), but EMD-positionwise does not. Generally, the area between UN and AN is quite challenging for our metrics (fortunately, according to Boehmer et al. [2021b], only few real-life elections land there). The maps for the pairwise and Bordawise metrics illustrate their flaws identified in the previous sections (e.g., Bordawise and pairwise conflate UN and AN, and the former also puts all the elections on the diameter, which explains its elongated shape; the curvature is

an artifact of the drawing algorithm). All in all, the positionwise metrics seem to perform best in this section, with the PCC values pointing to the EMD one.

7 Metrics as Graphs We conclude by discussing the intrinsicness of our metrics (see, e.g., the textbook of Khamsi and Kirk [2001] for more details on this notion). Consider a graph whose vertices are equivalence classes of a given metric and where the edges connect those classes that are at minimum nonzero distance from each other. Under the swap distance, each edge corresponds to a swap of adjacent candidates and each shortest path corresponds to the distance between its endpoints. This means that the swap distance is intrinsic. Definition 1. Let α 1 be a number. A metric d is αintrinsic if for each pair of elections X and Y (with the same number of candidates and the same number of voters), there are elections X = E0, E1, E2, . . . , Ek 1, Ek = Y such that Pk i=1 d(Ei 1, Ei) α d(X, Y ), and for each i [k], d(Ei 1, Ei) is the smallest nonzero distance between elections under d. If α = 1, then d is intrinsic. An intrinsic metric can be viewed as performing a series of simple, unit operations. Among our metrics only swap and discrete are intrinsic, but the positionwise ones are 2-intrinsic (this is, perhaps, the most technically involved of our results). Theorem 4. The swap and discrete metrics are intrinsic, but neither of the EMD/ℓ1-positionwise, pairwise, and Bordawise metric is intrinsic, but the EMDand ℓ1-positionwise metrics are 2-intrinsic yet not α-intrinsic for any α < 2. We conjecture that pairwise is not α-intrinsic for any α 1.

8 Summary We found that the EMDand ℓ1-positionwise metrics are quite similar to the swap one (which, computational issues aside, we view as ideal), but the EMD variant seems better. This justifies the choice of the EMD-positionwise metric for the maps of Szufa et al. [2020] and Boehmer et al. [2021b]. Yet, we ask for a metric that would perform even better, especially on elections between the uniform and antagonism ones. With our study of intrinsicness, we have initiated an axiomatic analysis of our metrics; it would be interesting to extend this analysis to better understand their properties.

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)

Acknowledgements NB was supported by the DFG project Ma Mu (NI 369/19) and by the DFG project Com Soc-MPMS (NI 369/22). TW was supported by the Polish National Science Center grant 2018/31/B/ST6/03201. This project has received funding from the European Research Council (ERC) under the European Union s Horizon 2020 research and innovation programme (grant agreement No 101002854).

References [Bachmeier et al., 2019] Georg Bachmeier, Felix Brandt, Christian Geist, Paul Harrenstein, Keyvan Kardel, Dominik Peters, and Hans Georg Seedig. k-majority digraphs and the hardness of voting with a constant number of voters. Journal of Computer and System Sciences, 105:130 157, 2019. [Bartholdi et al., 1989] John Bartholdi, III, Craig Tovey, and Michael Trick. Voting schemes for which it can be difficult to tell who won the election. Social Choice and Welfare, 6(2):157 165, 1989. [Betzler et al., 2011] Nadja Betzler, Rolf Niedermeier, and Gerhard J. Woeginger. Unweighted coalitional manipulation under the Borda rule is NP-hard. In Proceedings of IJCAI-2011, pages 55 60, 2011. [Boehmer and Schaar, 2022] Niclas Boehmer and Nathan Schaar. Collecting, classifying, analyzing, and using real-world elections. Technical Report ar Xiv:2204.03589 [cs.GT], ar Xiv.org, 2022. [Boehmer et al., 2021a] Niclas Boehmer, Robert Bredereck, Piotr Faliszewski, and Rolf Niedermeier. Winner robustness via swapand shift-bribery: Parameterized counting complexity and experiments. In Proceedings of IJCAI2021, pages 52 58, 2021. [Boehmer et al., 2021b] Niclas Boehmer, Robert Bredereck, Piotr Faliszewski, Rolf Niedermeier, and Stanislaw Szufa. Putting a compass on the map of elections. In Proceedings of IJCAI-2021, pages 59 65, 2021. [Boehmer et al., 2022] Niclas Boehmer, Piotr Faliszewski, Rolf Niedermeier, Stanislaw Szufa, and Tomasz W as. Understanding distance measures among elections. Technical Report ar Xiv:2205.00492 [cs.GT], ar Xiv.org, 2022. [Conitzer, 2009] Vincent Conitzer. Eliciting single-peaked preferences using comparison queries. Journal of Artificial Intelligence Research, 35:161 191, 2009. [Dwork et al., 2001] Cynthia Dwork, Ravi Kumar, Moni Naor, and D. Sivakumar. Rank aggregation methods for the web. In Proceedings of WWW-2001, pages 613 622, March 2001. [E gecio glu and Giritligil, 2013] Ömer E gecio glu and Ayca Giritligil. The impartial, anonymous, and neutral culture model: A probability model for sampling public pref-

erence structures. Journal of Mathematical Sociology, 37(4):203 222, 2013. [Faliszewski et al., 2019] Piotr Faliszewski, Piotr Skowron, Arkadii Slinko, Stanislaw Szufa, and Nimrod Talmon. How similar are two elections? In Proceedings of AAAI2019, pages 1909 1916, 2019. [Faliszewski et al., 2022] Piotr Faliszewski, Alexander Karpov, and Svetlana Obraztsova. The complexity of election problems with group-separable preferences. Autonomous Agents and Multi-Agent Systems, 36(1):18, 2022. [Fruchterman and Reingold, 1991] Thomas Fruchterman and Edward Reingold. Graph drawing by forcedirected placement. Software: Practice and Experience, 21(11):1129 1164, 1991. [Gonzalez, 1985] Teofilo Gonzalez. Clustering to minimize the maximum intercluster distance. Theoretical Computer Science, 38:293 306, 1985. [Grohe et al., 2018] Martin Grohe, Gaurav Rattan, and Gerhard J. Woeginger. Graph similarity and approximate isomorphism. In Proceedings of MFCS-2018, pages 20:1 20:16, 2018. [Inada, 1964] Ken-ichi Inada. A note on the simple majority decision rule. Econometrica, 32(32):525 531, 1964. [Inada, 1969] Ken-ichi Inada. The simple majority decision rule. Econometrica, 37(3):490 506, 1969. [Karpov, 2019] Alexander Karpov. On the number of groupseparable preference profiles. Group Decision and Negotiation, 28(3):501 517, 2019. [Khamsi and Kirk, 2001] Mohamed Khamsi and William Kirk. An Introduction to Metric Spaces and Fixed Point Theory. Wiley, 2001. [Mattei and Walsh, 2013] Nicholas Mattei and Toby Walsh. Preflib: A library for preferences. In Proceedings of ADT2013, pages 259 270, 2013. [Mc Garvey, 1953] David Mc Garvey. A theorem on the construction of voting paradoxes. Econometrica, 21(4):608 610, 1953. [Peters and Lackner, 2020] Dominik Peters and Martin Lackner. Preferences single-peaked on a circle. Journal of Artificial Intelligence Research, 68:463 502, 2020. [Rubner et al., 2000] Yossi Rubner, Carlo Tomasi, and Leonidas J. Guibas. The earth mover s distance as a metric for image retrieval. International Journal of Computer Vision, 40(2):99 121, 2000. [Szufa et al., 2020] Stanislaw Szufa, Piotr Faliszewski, Piotr Skowron, Arkadii Slinko, and Nimrod Talmon. Drawing a map of elections in the space of statistical cultures. In Proceedings of AAMAS-2020, pages 1341 1349, 2020. [Walsh, 2015] Toby Walsh. Generating single peaked votes. Technical Report ar Xiv:1503.02766 [cs.GT], ar Xiv.org, March 2015.

Proceedings of the Thirty-First International Joint Conference on Artificial Intelligence (IJCAI-22)