# Distance rationalization of anonymous and homogeneous voting rules

Benjamin Hadjibeyli  ENS Lyon<EMAIL_ADDRESS>and  Mark C.
Wilson  University of Auckland<EMAIL_ADDRESS>
###### Abstract.

The concept of distance rationalizability of voting rules has been explored in
recent years by several authors. Roughly speaking, we first choose a
_consensus set_ of _elections_ (defined via preferences of voters over
candidates) for which the result is specified _a priori_ (intuitively, these
are elections on which all voters can easily agree on the result). We also
choose a measure of _distance_ between elections. The result of an election
outside the consensus set is defined to be the result of the closest
consensual election under the distance measure.

Most previous work has dealt with a definition in terms of preference
profiles. However, most voting rules in common use are anonymous and
homogeneous. In this case there is a much more succinct representation (using
the voting simplex) of the inputs to the rule. This representation has been
widely used in the voting literature, but rarely in the context of distance
rationalizability.

We show exactly how to connect distance rationalizability on profiles for
anonymous and homogeneous rules to geometry in the simplex. We develop the
connection for the important special case of votewise distances, recently
introduced and studied by Elkind, Faliszewski and Slinko in several papers.
This yields a direct interpretation in terms of well-developed mathematical
concepts not seen before in the voting literature, namely Kantorovich (also
called Wasserstein) distances and the geometry of Minkowski spaces.

As an application of this approach, we prove some positive and some negative
results about the decisiveness of distance rationalizable anonymous and
homogeneous rules. The positive results connect with the recent theory of
hyperplane rules, while the negative ones deal with distances that are not
metrics, controversial notions of consensus, and the fact that the
$\ell^{1}$-norm is not strictly convex.

We expect that the above novel geometric interpretation will aid the analysis
of rules defined by votewise distances, and the discovery of new rules with
desirable properties.

###### Key words and phrases:

social choice theory, collective decision-making, rankings, homogeneity,
anonymity, simplex, Wasserstein metric, Kantorovich distance, Earth Mover
distance

MW thanks Elchanan Mossel and Miklos Racz for research hospitality and useful
conversations.

##  1\. Introduction

We are interested in the relation between two ways of describing voting rules
(interpreted broadly), each of which has a geometric flavour.

The class of anonymous and homogeneous voting rules includes all rules used in
practice, and most rules appearing in the research literature (Dodgson’s rule
is a notable exception). For such rules there is an obvious concise way to
describe an input profile of preferences, using the _vote simplex_. This
approach goes back at least as far as Young [23] and was extensively developed
and popularized by Saari [17]. By allowing us to use geometric intuition, it
aids in the analysis of many properties of anonymous and homogeneous voting
rules.

The framework of _distance rationalizability_ is a useful way to organize the
huge number of voting rules that have been introduced. By decomposing a rule
into a _consensus_ and a notion of _distance_ to that consensus, the framework
allows systematic derivation of axiomatic properties of the rule from those of
its components. This kind of analysis has been carried out recently by Elkind,
Faliszewski and Slinko [5, 6] and the present authors [8], following early
work by Campbell, Lerer and Nitzan [16, 11, 1] and Meskanen and Nurmi [14].

Until now, the two approaches described above have not been explicitly
connected. Specific distance-based rules have indeed been studied in the
simplex or permutahedron, notably by Zwicker [26, 25, 3]. However, a more
general approach is lacking. As shown in [8], the theory can be developed
simultaneously for social choice rules and social welfare rules, and for very
general distances and consensus notions, in a way that clarifies the
relationship between the profile-based and simplex-based representations.

###  1.1. Outline of paper and our contribution

In Section 2 we cover the basic notation and terminology. A rule defined
directly on the simplex is automatically anonymous and homogeneous.
Conversely, every anonymous and homogeneous rule can instead be defined on the
simplex. In Section 3 we show how the usual distance rationalizability
approach on profiles connects with the geometric approach on the vote simplex.

The methods of Zwicker and Saari, starting with the simplex or related
geometric representations of the space of preference profiles and using usual
Euclidean geometry, have led both to the discovery of some new anonymous and
homogeneous rules and to improved analysis of some old ones. We give an
example in Proposition 3.11 of some new rules defined in an intuitive way.
However, as it seems that in order to find more interesting rules we must dig
deeper and use less well-known consensuses or distances, we focus instead on
the analysis of rules defined on profile space, using our geometric machinery.

Starting with an anonymous and homogeneous rule defined via distance
rationalization on profile space, we consider the corresponding rule on the
simplex and interpret it geometrically. Abstractly, this is straightforward if
we use a _quotient distance_ , a general construction which is nontrivial to
compute in general. However, in the situation of the present paper, we can
give simple explicit formulae (Proposition 3.15). We focus in Section 3.3 on
the special case of $\ell^{p}$-votewise distances, which have been shown by
Elkind, Faliszweski and Slinko (and the present authors) to have many
desirable properties. We sharpen further the description above to show that in
this case, the quotient distance on the simplex is a _Wasserstein_ (also
called _Kantorovich_) distance, a concept widely used in probability theory
and its applications in computer science. In particular when $p=1$ (the most
natural case for voting) each such distance is induced by a norm, and we can
interpret everything in terms of the geometry of finite-dimensional normed
spaces (also called _Minkowski spaces_). This provides a new perspective to
the voting literature and suggests not only new voting rules defined using
geometric intuition, but also a new geometric tool for the analysis of
existing rules.

In particular, in Section 4 we use the simplex representation to explore the
decisiveness (how often it gives a unique winner) of a distance rationalizable
rule. On the positive side, we give a sufficient condition in Corollary 6.9
for a rule to be a _hyperplane rule_ and thus admit a vanishingly small
fraction of profiles where ties occur. For example, any rule defined using an
$\ell^{p}$-votewise distance and the strong or weak unanimity consensus
satisfies this condition. On the negative side, we show in Proposition 5.1
that ties can occur in a large fraction of profile space if we use
$\ell^{1}$-votewise metrics, unless the notion of consensus is very well
chosen. This sheds light on some common consensus notions and casts some doubt
on that of Condorcet. In Section 7 we make some recommendations for desirable
properties of consensus sets and distances.

The approach adopted here and in [8], following [6], allows for systematic
exploration of the space of aggregation rules and the construction of rules
with guaranteed axiomatic properties. We expect that more insight into
distance-based voting rules will be obtained by exploiting the deeper
geometric connections developed here.

##  2\. Basic definitions

We use standard concepts of social choice theory. Not all of these concepts
have completely standardized names.

######  Definition 2.1.

We fix a finite set $C=\\{c_{1},c_{2},\dots,c_{m}\\}$ of candidates and an
infinite set $V^{*}=\\{v_{1},v_{2},\dots,\\}$ of potential voters. For each
$s$ with $1\leq s\leq m$, an $s$-ranking is a strict linear order of $s$
elements chosen from $C$. The set of all $s$-rankings is denoted $L_{s}(C)$.
When $s=m$ we write simply $L(C)$. When $s=1$ we identify $L_{1}(C)$ with $C$
in the natural way.

######  Definition 2.2.

A profile is a function $\pi:V\to L(C)$ where $V\subset V^{*}$ is finite. We
denote the set of all profiles with fixed $C$ and $V$ by $\mathcal{P}(C,V)$
and the set of all profiles by $\mathcal{P}(C)$. An election is a triple
$(C,V,\pi)$ with $\pi\in\mathcal{P}(C,V)$. We denote the set of all elections
with fixed $C$ and $V$ by $\mathcal{E}(C,V)$, and the class of all elections
by $\mathcal{E}$.

######  Definition 2.3.

A social rule of size $s$ is a function $R$ that takes each election
$E=(C,V,\pi)$ to a nonempty subset of $L_{s}(C)$. When there is a unique
$s$-ranking chosen, the word “rule” becomes “function”. When $s=1$, we have
the usual social choice function, and when $s=|C|$ the usual social welfare
function.

For each subset $D$ of $\mathcal{E}$ we can consider a partial social rule
with domain $D$ to be defined as above, but with domain restricted to $D$.

###  2.1. Consensus

Intuitively, a consensus is simply a socially agreed unique outcome on some
set of elections. We now define it formally.

######  Definition 2.4.

An $s$-consensus is a partial social function $\mathcal{K}$ of size $s$. The
domain $D(\mathcal{K})$ of $\mathcal{K}$ is called an $s$-consensus set and is
partitioned into the inverse images
$\mathcal{K}_{r}:=\mathcal{K}^{-1}(\\{r\\})$.

Several specific consensuses have been described in the literature. We list a
few important ones. Some have been discussed by previous authors only in the
case $s=1$ but the definitions extend naturally.

######  Definition 2.5.

We use the following consensuses in this article.

  * •

We denote by $\operatorname{\mathbf{S}}^{s}$ the consensus $\mathcal{K}$ for
which $\mathcal{K}_{r}$ is the election in which all voters agree that $r$ is
the ranking of the top $s$ candidates. When $s=|C|$, we simply write
$\operatorname{\mathbf{S}}$ (called the strong unanimity consensus), whereas
when $s=1$, for consistency with previous authors we denote it
$\operatorname{\mathbf{W}}$, the weak unanimity consensus.

  * •

The $1$-Condorcet consensus $\operatorname{\mathbf{C}}$ has domain consisting
of all elections for which a Condorcet winner exists. That is, there is a
candidate $c$ (the Condorcet winner) such that for every other candidate $b$ a
fraction strictly greater than $1/2$ of voters rank $c$ above $b$.

###  2.2. Distances

We require a notion of distance on elections. We aim to be as general as
possible.

######  Definition 2.6.

(distance) A distance (or hemimetric) on $\mathcal{E}$ is a function
$d:\mathcal{E}\times\mathcal{E}\to\mathbb{R}_{+}\cup\\{\infty\\}$ that
satisfies for all $x,y,z\in\mathcal{E}$

  * •

$d(x,x)=0$,

  * •

$d(x,z)\leq d(x,y)+d(y,z)$.

A pseudometric is a distance that also satisfies $d(x,y)=d(y,x)$. A
quasimetric is a distance that also satisfies $d(x,y)=0\Rightarrow x=y$. A
metric is a distance that is both a quasimetric and a pseudometric. We call a
distance standard if $d(E,E^{\prime})=\infty$ whenever $E$ and $E^{\prime}$
have different sets of voters or candidates.

One commonly used class of distances consists of the votewise distances [6]
(Definition 2.11 below). First we require some preliminary definitions.

######  Example 2.7.

(commonly used distances on $L(C)$) We discuss the following distances on
$L(C)$ in this article.

  * •

The discrete metric $d_{H}$, defined by

$d_{H}(\rho,\rho^{\prime})=\begin{cases}1\quad\text{if
$\rho=\rho^{\prime}$}\\\ 0\quad\text{otherwise}.\end{cases}$

  * •

The inversion metric $d_{K}$ (also called the swap, bubblesort or
Kendall-$\tau$ metric), where $d_{K}(\rho,\sigma)$ is the minimum number of
swaps of adjacent elements needed to change $\rho$ into $\sigma$.

  * •

Spearman’s footrule $d_{S}$, defined by

$d_{S}(\rho,\rho^{\prime}):=\sum_{c\in
C}|\operatorname{rk}(\rho,c)-\operatorname{rk}(\rho^{\prime},c)|.$

Here $\operatorname{rk}(\rho,c)$ denotes the rank of $c$ in the preference
order $\rho$.

######  Definition 2.8.

A seminorm on a real vector space $X$ is a real-valued function $N$ satisfying
the identities

  * •

$N(x+y)\leq N(x)+N(y)$

  * •

$N(\lambda x)=|\lambda|N(x)$

for all $x,y\in X$ and all $\lambda\in\mathbb{R}$. Note that this implies that
$N(0)=0$ and $N(x)\geq 0$ for all $x\in X$.

A norm is a seminorm that also satisfies

  * •

$N(x)=0\Rightarrow x=0$.

######  Remark 2.9.

Every seminorm induces a pseudometric via $d(x,y)=||x-y||$. This is a metric
if and only if the seminorm is a norm.

######  Example 2.10.

Consider an $n$-dimensional space $X$ with fixed basis $e_{1},\dots,e_{n}$ and
corresponding coefficients $x_{i}$ for each element $x\in X$. Fix $p$ with
$1\leq p<\infty$ and define the $\ell^{p}$-norm on $X$ by

$||x||_{p}=\left(\sum_{i=1}^{n}|x_{i}|^{p}\right)^{1/p}.$

When $p=\infty$ we define the $\ell^{\infty}$ norm by

$||x||_{\infty}=\max_{1\leq i\leq n}|x_{i}|.$

######  Definition 2.11.

(votewise distances)

Fix a candidate set $C$ and voter set $V$, and a distance $d$ on $L(C)$.
Choose a family $\\{N_{n}\\}_{n\geq 1}$ of seminorms, where $N_{n}$ is defined
on $\mathbb{R}^{n}$. Extend $d$ to a function on $\mathcal{P}(C,V)$ by taking
$n=|V|$ and defining for $\sigma,\pi\in\mathcal{P}(C,V)$

$d^{N_{n}}(\pi,\sigma):=N_{n}(d(\pi_{1},\sigma_{1}),\dots,d(\pi_{n},\sigma_{n})).$

This yields a distance on elections having the same set of voters and
candidates. We complete the definition of the extended distance (which we
denote by $d^{N}$) on $\mathcal{E}$ by declaring it to be standard.

We use the abbreviation $d^{p}$ for $d^{\ell^{p}}$, and sometimes we even use
just $d$ for $d^{N}$ if the meaning is clear.

######  Remark 2.12.

Note that if $d$ is a metric and $N$ is a norm, then $d^{N}$ is a metric.

######  Example 2.13.

(famous votewise distances) The distances $d^{1}_{H}$ and $d^{1}_{K}$ are
called respectively the Hamming metric and Kemeny metric. The Hamming metric
measures the minimum number of voters whose preferences must be changed in
order to convert one profile to another, and as such has an interpretation in
terms of _unit cost bribery_ [7]. The Kemeny metric measures the minimum
number of swaps of adjacent candidates required to convert one profile to
another, and is related to models of voter error [24].

######  Example 2.14.

(tournament distances) Given an election $E=(C,V,\pi)$, we form the pairwise
tournament digraph $\Gamma(E)$ with nodes indexed by the candidates, where the
arc from $a$ to $b$ has weight equal to the _net support_ for $a$ over $b$ in
a pairwise contest. Formally, there is an arc from $a$ to $b$ whose weight
equals $n_{ab}-n_{ba}$, where $n_{ab}$ denotes the number of rankings in $\pi$
in which $a$ is above $b$.

Let $M(E)$ be the weighted adjacency matrix of $\Gamma(E)$ (with respect to an
arbitrarily chosen fixed ordering of $C$). Given a seminorm $N$ on the space
of all $|C|\times|C|$ real matrices, we define the $N$-tournament distance by

$d^{N}(E,E^{\prime})=N(M(E)-M(E^{\prime})).$

A closely related distance is defined in a similar way, but where each element
of the adjacency matrix is replaced by its sign ($1$, $0$, or $-1$). We call
this the $N$-reduced tournament distance. We denote the special cases where
$N$ is the $\ell^{1}$ norm on matrices by $d^{T}$ and $d^{RT}$ respectively.
Every (reduced) tournament distance is a pseudometric.

###  2.3. Combining consensus and distance

In order for a rule to be definable via the DR construction, it is necessary
that the following property holds, and we shall assume this from now on.

######  Definition 2.15.

Let $d$ be a distance and $\mathcal{K}$ a consensus. We say that
$(\mathcal{K},d)$ distinguishes consensus choices if whenever
$x\in\mathcal{K}_{r},y\in\mathcal{K}_{r^{\prime}}$ and $r\neq r^{\prime}$,
then $d(x,y)>0$.

We use a distance to extend a consensus to a social rule in the natural way.
The choice at a given election $E$ consists of all $s$-rankings $r$ whose
consensus set $\mathcal{K}_{r}$ minimizes the distance to $E$. We introduce
the idea of a score in order to use our intuition about positional scoring
rules.

######  Definition 2.16.

(DR scores and rules)

Suppose that $\mathcal{K}$ is an $s$-consensus and $d$ a distance on
$\mathcal{E}$. Fix an election $E\in\mathcal{E}$. For each $r\in L_{s}(C)$,
the $(\mathcal{K},d,E)$-score of $r$ is defined by

$|r|:=d(E,\mathcal{K}_{r}):=\inf_{E^{\prime}\in\mathcal{K}_{r}}d(E,E^{\prime}).$

The rule $R:=\operatorname{\mathcal{R}}(\mathcal{K},d)$ is defined by

(1) $R(E)=\arg\min_{r\in L_{s}(C)}|r|.$

We say that $R$ is distance rationalizable (DR) with respect to
$(\mathcal{K},d)$.

######  Example 2.17.

(scoring rules) The positional scoring rule defined by a vector $w$ of weights
with $w_{1}\geq\dots\geq w_{m}$ and $w_{1}>w_{m}$ elects all candidates with
maximum score, where the score of $a$ in the profile $\pi$ is defined as
$\sum_{v\in V}w_{\operatorname{rk}(\pi(v),a)}$.

The plurality ($w=(1,0,0,\dots,0)$) and Borda ($w=(m-1,m-2,\dots,0)$) rules
are well-known special cases.

The positional scoring rule defined by $w$ has the form
$\operatorname{\mathcal{R}}(\operatorname{\mathbf{W}},d_{S(w)}^{1})$ where
$d_{S(w)}$ is the generalization of $d_{S}$ given by

$d_{S(w)}(\rho,\rho^{\prime})=\sum_{c\in
C}|w_{\operatorname{rk}(\rho,c)}-w_{\operatorname{rk}(\rho^{\prime},c)}|.$

[6, Prop. 8]. Thus the Borda rule can be expressed as
$\operatorname{\mathcal{R}}(\operatorname{\mathbf{W}},d_{S}^{1})$.

Also, the positional scoring rule defined by $w$ has the form
$\operatorname{\mathcal{R}}(\operatorname{\mathbf{W}},d_{K(w)}^{1})$ where
$d_{K(w)}$ is a generalized swap distance on rankings [11]. Borda’s rule has
the form $\operatorname{\mathcal{R}}(\operatorname{\mathbf{W}},d_{K}^{1})$.

######  Remark 2.18.

Note that $d_{w}$ is a metric on $L_{s}(C)$ if and only if $w_{1},\dots,w_{s}$
are all distinct. The score of $r$ under the rule defined by $w$ is the
difference $nw_{1}-|r|$. For example, for Borda with $m$ candidates the
maximum possible score of a candidate $c$ is $(m-1)n$, achieved only for those
elections in $\operatorname{\mathbf{W}}_{c}$. Note that as far as the distance
to $\operatorname{\mathbf{W}}$ or $\operatorname{\mathbf{C}}$ is concerned,
$d_{S}^{1}$ and $d_{K}^{1}$ are proportional, but they are not proportional in
general [14, p. 298–299]. The score of $c$ under Borda is exactly $n(m-1)-K$
where $K$ is the total number of swaps of adjacent candidates needed to move
$c$ to the top of all preference orders in $\pi(E)$.

######  Example 2.19.

(Copeland’s rule) Copeland’s rule can be represented as
$\operatorname{\mathcal{R}}(\operatorname{\mathbf{C}},d_{RT})$. Indeed, in an
election $E$, the Copeland score of a candidate $c$ (the number of points it
scores in pairwise contests with other candidates) equals $n-1-s$, where $s$
is the minimum number of pairwise results that must be changed for $E$ to
change to an election that belongs to $\operatorname{\mathbf{C}}_{c}$.

##  3\. Simplex rules

Although it is far from the general case, most rules used in practice are in
fact anonymous and homogeneous. In this case there is an appealing geometric
interpretation. The frequency distribution of votes is sufficient information
to determine the output of the rule, and so profile space can be substantially
compressed.

We have previously explored in detail the connection with distance
rationalization [8]. We first recall the construction for anonymous rules.
Recall that a multiset of weight $n$ on an underlying set $S$ of size $M$ is
“a set of $n$ elements of $S$ with repetitions”. Formally, there is a function
$f:S\to\mathbb{N}$ where $f(s)$ gives the multiplicity of $s$ in the multiset.

######  Definition 3.1.

Let $E=(C,V,\pi)\in\mathcal{E}$. The vote number map
$\operatorname{\mathcal{N}}$ is the map that associates $E$ with the multiset
$\operatorname{\mathcal{N}}(E)$ on $L(C)$ of weight $|V|$, in which the
multiplicity of $\rho\in L(C)$ is the number of voters in $V$ having that
preference order.

A rule $R$ is anonymous if $R(E)=R(E^{\prime})$ whenever
$\operatorname{\mathcal{N}}(E)=\operatorname{\mathcal{N}}(E^{\prime})$. We
denote the quotient space by $\mathcal{V}$ and call it the set of anonymous
profiles.

######  Remark 3.2.

$\operatorname{\mathcal{N}}(E)$ simply keeps track of the numbers of votes of
each type in $\pi$, ignoring the identities of voters. A rule is anonymous if
this information is enough to determine the output. The more usual (and
equivalent) definition of anonymity is given in Remark 3.5 below.

######  Definition 3.3.

The vote distribution associated to $E$ is the relative frequency distribution
on $L(C)$ corresponding to the multiset $\operatorname{\mathcal{N}}(E)$, which
we denote $\operatorname{\mathcal{D}}(E)$. Explicitly,
$\operatorname{\mathcal{D}}$ is a function from $\mathcal{E}$ to
$[0,1]^{L(C)}$, which gives for each ranking the proportion of voters having
this ranking as preference. The vote distribution map defines an equivalence
relation $\sim$ on $\mathcal{E}$ in the usual way: $E\sim E^{\prime}$ if and
only if
$\operatorname{\mathcal{D}}(E)=\operatorname{\mathcal{D}}(E^{\prime})$.

An anonymous rule $R$ is homogeneous if $R(E)=R(E^{\prime})$ whenever
$\operatorname{\mathcal{D}}(E)=\operatorname{\mathcal{D}}(E^{\prime})$. We
denote the quotient space by $\mathcal{F}$, and call it the set of anonymous
and homogeneous profiles.

######  Remark 3.4.

Note that if
$E=(C,V,\pi),E^{\prime}=(C,V^{\prime},\pi^{\prime})\in\mathcal{E}$ and
$\operatorname{\mathcal{N}}(E)=\operatorname{\mathcal{N}}(E^{\prime})$, then
$|V|=|V^{\prime}|$. Thus there is a well-defined map
$f:\mathcal{V}\to\mathcal{F}$ (“divide by the number of voters”), and
$\operatorname{\mathcal{D}}(E)$ simply lists each preference order according
to its relative frequency in $\pi$.

######  Remark 3.5.

Anonymous and homogeneous rules were already defined in the literature, but in
different ways.

Let $g$ be a permutation of $V^{*}$. For each $E=(C,V,\pi)$, define
$g(E)=(C,g(V),g(\pi))$ where $g(\pi)(v)=\pi(g(v))$. A rule $R$ is anonymous if
and only if $R(g(E))=R(E)$ for all $E\in\mathcal{E}$ and all $g$.

For $k\geq 1$, define $kE$ to be an election $(C,kV,k\pi)$ where $kV$ consists
of $k$ copies of each voter in $V$ and $k\pi$ the corresponding copies of
their preference orders (the exact order of the voters is irrelevant since we
deal only with anonymous rules). An anonymous rule $R$ is homogeneous if and
only if $R(kE)=R(E)$ for all $E\in\mathcal{E}$ and all $k$.

We call anonymous and homogeneous rules simplex rules for short, and now
explain why. So far the discussion has been coordinate-free, but it is often
useful to introduce coordinates. Given any linear ordering
$\rho_{1},\rho_{2},\dots,\rho_{M}$ on $L(C)$, where $|C|=m$ and $M=m!$, we can
introduce coordinates $x_{i}$ such that $x_{i}$ denotes the relative frequency
associated to $\rho_{i}$. The set of frequency distributions
$\operatorname{\Delta}^{\mathbb{Q}}(L(C))$ is then coordinatized by the
rational points of the standard simplex.

######  Definition 3.6.

The standard simplex in $\mathbb{R}^{M}$ is the set

$\operatorname{\Delta}_{M}:=\left\\{x\in\mathbb{R}^{M}\mid\sum_{i}x_{i}=1,x_{i}\geq
0\text{ for $1\leq i\leq M$}\right\\}.$

We let
$\operatorname{\Delta}^{\mathbb{Q}}_{M}:=\mathbb{Q}^{M}\cap\operatorname{\Delta}_{M}$
denote the rational points of $\operatorname{\Delta}_{M}$.

######  Remark 3.7.

For simplicity we sometimes write $x_{t}$ for the component of
$x\in\operatorname{\Delta}_{M}$ corresponding to $t\in L(C)$ (instead of
$x_{i}$ where $i$ is the number of $t$ in some linear ordering on $L(C)$).

######  Example 3.8.

An election on candidates $C=\\{a,b,c\\}$ having $7$ voters of whom $3$ have
preference $a\succ b\succ c$, $2$ have preference $b\succ a\succ c$ and $2$
have preference $c\succ b\succ a$ corresponds (under the lexicographic order
on $L(C)$) to the anonymous profile $(3,0,2,0,0,2)$ and hence to the point
$(3/7,0,2/7,0,0,2/7)\in\operatorname{\Delta}_{6}$.

######  Remark 3.9.

We always consider $\operatorname{\Delta}_{M}$ as embedded in
$\mathbb{R}_{M}$. It is contained in a unique hyperplane $H_{M}$, which is
given by the single linear equation $\sum_{i=1}^{M}x_{i}=1$.

We can interpret each anonymous and homogeneous rule as being defined on
$\operatorname{\Delta}^{\mathbb{Q}}_{M}$. If the rule is also _continuous_
then we can in fact define it on $\operatorname{\Delta}_{M}$, which allows us
to use our usual geometric intuition. For example, the domain of
$\operatorname{\mathbf{S}}$ consists of the corners of the simplex, while the
domain of $\operatorname{\mathbf{W}}$ also lies on the boundary of the simplex
(for example, $\operatorname{\mathbf{W}}_{a}$ contains all points of the
simplex for whom all coordinates corresponding to rankings with $a$ not at the
top are zero).

The general approach of the last paragraph has been adopted by many previous
authors. For example, Saari [18] simply uses the terminology “profiles” to
refer to vote distributions, and all rules he considers are continuous simplex
rules by definition.

###  3.1. Distance rationalization in the simplex

We shall see in Section 3.2 how anonymous and homogeneous distance
rationalizable rules defined using profiles can be interpreted using the
simplex. The converse idea is to define distance rationalizable rules directly
on the simplex rather than on profile space. We make the obvious definitions
by analogy with those for profiles.

######  Definition 3.10.

Given a fixed candidate set $C$ of size $m$ and a distance on
$\operatorname{\Delta}^{\mathbb{Q}}_{M}$ where $M=m!$, a partial social rule
on $\operatorname{\Delta}^{\mathbb{Q}}_{M}$ of size $s$ with domain
$D\subseteq\operatorname{\Delta}^{\mathbb{Q}}_{M}$ is a mapping taking each
element of $D$ to a nonempty subset of $L_{s}(C)$. A consensus on
$\operatorname{\Delta}^{\mathbb{Q}}_{M}$ is a partial social rule that is
single-valued at every point (a partial social function). Given a consensus
$K$ and distance $\delta$ on $\operatorname{\Delta}^{\mathbb{Q}}_{M}$, the
rule $\operatorname{\mathcal{R}}(K,\delta)$ is defined by

(2) $R(x)=\arg\min_{r\in L_{s}(C)}\delta(x,K_{r}).$

The most obvious distances mathematically are surely the $\ell^{p}$ metrics.
The interpretation in terms of social choice is less compelling for $p>1$,
since we are measuring the amount of effort needed to change one election into
another by transferring vote mass under a nonlinear penalty. The case $p=1$ is
by far the most commonly studied, and also arises directly from votewise
distances, unlike the case $p>1$.

To our knowledge, several fairly obvious rules of this type have not yet been
studied in detail. Here is an example using the unanimity consensus.

######  Proposition 3.11.

Fix $p$ with $1\leq p\leq\infty$ and consider the social choice rule
$\operatorname{\mathcal{R}}(\operatorname{\mathbf{S}}^{s},\ell^{p})$ defined
on $\operatorname{\Delta}^{\mathbb{Q}}_{M}$. This rule chooses precisely the
initial $s$-ranking from each of the most frequent ranking(s) from the input
profile.

###### Proof.

Let $\delta$ be the $\ell^{p}$ distance on $\mathbb{R}^{M}$ and let $e_{t}$
denote the basis vector in $\mathbb{R}^{M}$ corresponding to $t\in L(C)$, a
corner of the simplex. Then for $x\in\Delta_{M}$ and $t,t^{\prime}\in L(C)$,

$\displaystyle\delta^{p}(x,e_{t})-\delta^{p}(x,e_{t^{\prime}})$
$\displaystyle=(1-x_{t})^{p}+\sum_{k\neq
t}x_{t}^{p}-(1-x_{t^{\prime}})^{p}-\sum_{k\neq t^{\prime}}x_{t^{\prime}}^{p}$
$\displaystyle=(1-x_{t})^{p}-(1-x_{t^{\prime}})^{p}+x_{t^{\prime}}^{p}-x_{t}^{p}.$

Choosing $x_{t^{*}}$ to be the maximum value among the entries of $x$ and
setting $t=t^{*}$ shows the right side of the above expression to be
nonpositive for all $t^{\prime}\neq t^{*}$. Hence $t^{*}$ is a minimizer (the
same argument works for $p=\infty$ with a different computation).

Thus if $\rho^{*}$ denotes the initial $s$-ranking corresponding to $t^{*}$
(written $t^{*}_{s}=\rho^{*}$), then for each $s$-ranking $\rho$, we have

$\delta(x,\operatorname{\mathbf{S}}^{s}_{\rho})=\min_{\\{t:t_{s}=\rho\\}}\delta(x,e_{t})\geq\delta(x,e_{t^{*}})=\delta(x,\operatorname{\mathbf{S}}^{s}_{\rho_{*}}).$

∎

######  Remark 3.12.

For $s=m$ this rule is the modal ranking rule [2] (the term plurality ranking
rule may seem more logical, but it is important not to be confused with the
ranking induced by plurality scores of candidates in the case where these
scores all differ). For $s=1$ it is the social choice variant of the modal
ranking rule, choosing the highest ranked candidate from each modal ranking.
Note that the latter rule differs from plurality rule, which is what we would
get if we used the simplex in dimension $m$, as for example done by Saari
[18].

In order to find more interesting rules defined naturally on
$\operatorname{\Delta}^{\mathbb{Q}}_{M}$, we may need to use less common
distances. For example, so-called _statistical distances_ such as the
(asymmetric) _Kullback–Leibler divergence_ (or _relative entropy_) and the
_Hellinger metric_ are heavily used in many application areas (the simpler
_total variation distance_ arises in Example 3.22 below). We do not present a
detailed study here, deferring it to future work. Instead, we now move on to
explore distances on $\operatorname{\Delta}^{\mathbb{Q}}_{M}$ induced by
distances on $\mathcal{E}$.

###  3.2. Quotient distances

We can define a simplex rule by first starting with profiles and passing to
the quotient space, provided the rule in question is anonymous and homogeneous
(the case of Dodgson’s rule
$\operatorname{\mathcal{R}}(\operatorname{\mathbf{C}},d_{K}^{1})$ which is
anonymous but not homogeneous shows that care must be taken).

Since votewise distances are very natural and the $\ell^{1}$ norm is the most
obvious choice for a votewise distance (because it just adds the distance from
each voter), we obtain several rules with an $\ell^{1}$ flavour in this way.
For example, the Hamming metric yields a constant multiple of $\ell^{1}$ via
the Wasserstein construction as described in Example 3.22 below, while the
Kemeny metric and $\ell^{1}$ lead to rules such as Borda and Kemeny’s rule. We
discuss $\ell^{1}$-votewise rules in more detail in Section 5.

######  Definition 3.13.

A distance is anonymous if $d(g(E),g(E^{\prime}))=d(E,E^{\prime})$ for all
$E,E^{\prime}\in\mathcal{E}$ and all permutations $g$. An anonymous distance
is homogeneous if $d(kE,kE^{\prime})=d(E,E^{\prime})$ for all
$E,E^{\prime}\in\mathcal{E}$ and all $k\geq 1$.

Note that votewise distances need to be normalized before becoming
homogeneous, as we explain in Remark 3.20.

Every anonymous and homogeneous rule $R$ corresponds to a simplex rule
$\overline{R}$. When $R=\operatorname{\mathcal{R}}(\mathcal{K},d)$ where both
$\mathcal{K}$ and $d$ are anonymous and homogeneous, we can express
$\overline{R}$ as $\operatorname{\mathcal{R}}(K,\delta)$ where $K,\delta$
depend nicely on $\mathcal{K},d$. The mapping from profiles to the simplex
yields the obvious consensus $K=\overline{\mathcal{K}}$. The distance $\delta$
is a little more involved. The obvious idea is to use a quotient distance [4].
This concept is standard but relatively little-known.

######  Definition 3.14.

We define
$\overline{d}:\operatorname{\Delta}_{M}\times\operatorname{\Delta}_{M}\to\mathbb{R}_{+}$
to be the quotient distance induced by $\sim$. That is,

(3) $\overline{d}(x,y)=\inf\sum_{i=1}^{k}d(E_{i},E^{\prime}_{i})$

where the infimum is taken over all _admissible paths_ , namely paths such
that $E^{\prime}_{i}\sim E_{i+1}$ for $1\leq i\leq k-1$,
$E=E_{1},E^{\prime}=E^{\prime}_{k}$, $E$ projects to $x$ and $E^{\prime}$ to
$y$.

In general, quotient distances are tricky to work with, owing to the
complicated definition. In our setup, it turns out that they are reasonably
tractable.

######  Proposition 3.15.

Let $d$ be an anonymous and homogeneous standard distance on $\mathcal{E}$.
Then $\overline{d}$ is given by

$\overline{d}(x,y)=\inf_{E^{\prime}}d(E,E^{\prime})$

where $E,E^{\prime}$ range over all elections having an equal number of
voters, such that
$\operatorname{\mathcal{D}}(E)=x,\operatorname{\mathcal{D}}(E^{\prime})=y$.

###### Proof.

Let $x,y\in\mathcal{F}$ and consider an admissible path and its corresponding
sum

$\sum_{i=1}^{k}d(E_{i},E^{\prime}_{i})$

where $k>1$. We show that we can reduce the value of $k$. By homogeneity of
$d$, we can change the size of the voter sets so that $E_{k}$ and
$E^{\prime}_{k-1}$ have the same sized voter set. Then we can choose a
permutation $g$ of $V^{*}$ taking $E_{k}$ to $E^{\prime}_{k-1}$. Since $d$ is
anonymous, using the triangle inequality we obtain

$\displaystyle d(E_{k-1},E^{\prime}_{k-1})+d(E_{k},E^{\prime}_{k})$
$\displaystyle=d(E_{k-1},E^{\prime}_{k-1})+d(g(E_{k}),g(E^{\prime}_{k}))$
$\displaystyle=d(E_{k-1},E^{\prime}_{k-1})+d(E^{\prime}_{k-1},g(E^{\prime}_{k}))$
$\displaystyle\geq d(E_{k-1},g(E^{\prime}_{k})).$

This gives an admissible path with $k$ replaced by $k-1$.

Thus without loss of generality, in computing $\overline{d}$ we need only deal
with the case $k=1$. Finally, if the minimum is reached for some $E=E_{*}$,
then for each $E$ we can write $g(E_{*})=E$ for some $g$. Thus by anonymity
$d(E,E^{\prime})=d(E_{*},g^{-1}(E^{\prime}))$. Thus the minimum can be taken
only over $E^{\prime}$, since $g^{-1}(E^{\prime})$ ranges over all elections
as $g$ ranges over all permutations. ∎

######  Remark 3.16.

Proposition 3.15 shows that we can replace $\inf$ by $\min$, since by
anonymity, once we fix the number of voters there are only a finite number of
possible distances $d(E,E^{\prime})$ to consider.

######  Proposition 3.17.

Let $d$ be an anonymous and homogeneous standard distance on $\mathcal{E}$,
and $K$ be an anonymous and homogeneous consensus. If
$R=\operatorname{\mathcal{R}}(K,\delta)$ is anonymous and homogeneous, then
$\overline{R}=\operatorname{\mathcal{R}}(\overline{K},\overline{d})$.

###### Proof.

By Definition 2.16, $R(E)=\arg\min_{r\in L_{s}(C)}d(E,K_{r})$. By Proposition
3.15, $\overline{d}(x,y)=\inf_{E^{\prime}}d(E,E^{\prime})$, such that
$\operatorname{\mathcal{D}}(E)=x,\operatorname{\mathcal{D}}(E^{\prime})=y$. In
particular,
$\overline{d}(\operatorname{\mathcal{D}}(E),\overline{K}_{r})=\inf_{E^{\prime}}d(E,E^{\prime})$
with $E^{\prime}\in K_{r}$, so
$\overline{d}(\operatorname{\mathcal{D}}(E),\overline{K}_{r})=d(E,K_{r})$.
Thus, $\overline{R}(\operatorname{\mathcal{D}}(E))=R(E)=\arg\min_{r\in
L_{s}(C)}\overline{d}(\operatorname{\mathcal{D}}(E),\overline{K}_{r})$ and
$\overline{R}=\operatorname{\mathcal{R}}(\overline{K},\overline{d})$.

∎

###  3.3. The $\ell^{p}$-votewise case — Wasserstein distance

In the special case of $\ell^{p}$-votewise distances, we can describe
$\overline{d}$ in more detail using a well-known construction from probability
theory, the Wasserstein distance, which we now recall.

Let $S$ be a finite set of size $M$, and let $\operatorname{\Delta}(S)$ denote
the set of probability distributions on $S$. For a distance $d$ defined on
$S$, the function
$d^{p}_{W}:\operatorname{\Delta}(S)\times\operatorname{\Delta}(S)\to\mathbb{R}$
is defined by

$d^{p}_{W}(x,y)^{p}=\inf_{A}\sum_{r,r^{\prime}\in
S}A_{r,r^{\prime}}d(r,r^{\prime})^{p},$

where the infimum is taken over all _couplings_ of $x$ and $y$, defined as
nonnegative square matrices of size $M$ whose marginals are $x$ and $y$
respectively (i.e. $\forall r,\sum_{r^{\prime}}A_{rr^{\prime}}=x_{r}$ and
$\forall r^{\prime},\sum_{r}A_{rr^{\prime}}=y_{r^{\prime}}$). Basically, it
represents the minimum cost to move from one configuration to another, where
the underlying distance $d$ defines the cost of each movement. Indeed, this
construction leads to a new distance.

######  Proposition 3.18.

If $d$ is a distance on $S$, then $d_{W}^{p}$ is a distance on
$\operatorname{\Delta}(S)$. If $d$ is a metric, then so is $d_{W}^{p}$.

###### Proof.

See [20, Ch. 6]. ∎

######  Remark 3.19.

The function $d_{W}^{p}$ goes by several names, some common ones being the
$l^{p}$-transportation distance, the Kantorovich $p$-distance, the
$p$-Wasserstein distance. When $p=1$, it is also called the Earth Mover’s
distance or first Mallows metric, and is used heavily in several areas of
computer science, particularly image retrieval and pattern recognition.

Now we are able to make the link with the votewise metrics, by applying the
construction of $d^{p}_{W}$ in the case $S=L(C)$. Scaling a votewise distance
based on the $\ell^{p}$ norm gives a homogeneous distance with a special
formula, and this turns out to be exactly the $p$-Wasserstein distance.

######  Remark 3.20.

A votewise distance based on $\ell^{p}$ is not homogeneous, as its value
depends on the number of voters. However, we may make an equivalent
homogeneous version by scaling. For each real number $p$ with $1\leq
p\leq\infty$, and each positive integer $n$, we define a new norm on
$\mathbb{R}^{n}$ by defining for each $x\in\mathbb{R}^{n}$

$||x||^{*}_{p}=\frac{1}{n}||x||_{p}.$

Denote the votewise distance corresponding to this norm by $d_{*}^{p}$; then
$\operatorname{\mathcal{R}}(\mathcal{K},d^{p})=\operatorname{\mathcal{R}}(\mathcal{K},d_{*}^{p})$.

######  Proposition 3.21.

Let $d$ be a finite distance on $L(C)$. Then $\overline{d_{*}^{p}}=d^{p}_{W}$.

###### Proof.

Write $S=L(C)$. Since $d_{*}^{p}$ is anonymous and homogeneous, Proposition
3.15 implies that
$\overline{d_{*}^{p}}(x,y)=\min_{E,E^{\prime}}d_{*}^{p}(E,E^{\prime})$, where
$\overline{E}=x$, $\overline{E^{\prime}}=y$ and $|V(E)|=|V(E^{\prime})|$. Fix
$n\geq 1$ and let $E=(C,V,\pi)$ and $E^{\prime}=(C,V,\pi^{\prime})$ denote
elections with $n$ voters such that $\overline{E}=x$,
$\overline{E^{\prime}}=y$. Then

$\overline{d_{*}^{p}}(x,y)^{p}=\min_{\pi^{\prime}}\frac{1}{n}\sum_{i}d(\pi_{i},\pi^{\prime}_{i})^{p}\geq\frac{1}{n}\sum_{r,r^{\prime}\in
S}\sum_{\\{i:\pi_{i}=r,\pi^{\prime}_{i}=r^{\prime}\\}}d(r,r^{\prime})^{p}=\sum_{r,r^{\prime}\in
S}\frac{a_{r,r^{\prime}}}{n}d(r,r^{\prime})^{p},$

where the $a_{r,r^{\prime}}$’s are nonnegative integers such that for all
$r\in S,\sum_{r}\frac{a_{r,r^{\prime}}}{n}=x_{r}$ and for all $r^{\prime}\in
S,\sum_{r^{\prime}}\frac{a_{r,r^{\prime}}}{n}=y_{r^{\prime}}$, which
corresponds to the Wasserstein distance restricted to matrices $A$ respecting
the conditions and with coefficients of the form $\frac{k}{n}$ with $0\leq
k\leq n$ (in other words, a rational coupling with restricted denominators).
So clearly, $d^{p}_{W}(x,y)\leq\overline{d_{*}^{p}}(x,y)$.

Let assume that this inequality is strict. Then there is a coupling
$A^{\prime}$ (not all of whose entries are rational) with
$\sum_{r,r^{\prime}\in
S}a^{\prime}_{r,r^{\prime}}d(r,r^{\prime})^{p}+\epsilon/2<\sum_{r,r^{\prime}\in
S}a_{r,r^{\prime}}d(r,r^{\prime})^{p}$ for all rational couplings $A$. However
since $\max_{r,r^{\prime}}d(r,r^{\prime})<\infty$ and we can choose $n$ as
large as we want, $d^{p}_{W}(x,y)$ can be approximated arbitrarily closely,
since we can approach all entries of $A^{\prime}$ simultaneously arbitrarily
closely by a rational matrix satisfying the coupling constraints. This
contradiction yields the final result. ∎

######  Example 3.22.

Let $d_{1}$ be the $\ell^{1}$ distance between probability measures on $L(C)$
and let $d=d_{H}$. Then $\overline{d_{*}^{1}}=\frac{1}{2}d_{1}$ (also called
the total variation distance). This was observed (without the current
notation) in [15, Lemma 3.2]: if $E,E^{\prime}$ are elections on $(C,V)$ with
$|V|=n$, then

$d_{1}(\overline{E},\overline{E^{\prime}})\leq\frac{2}{n}d_{H}(E,E^{\prime})$

and given
$\overline{E},\overline{E^{\prime}}\in\operatorname{\Delta}^{\mathbb{Q}}_{M}$,
we can choose $n$ and the preimages $E,E^{\prime}$ so that equality holds.

######  Example 3.23.

If $x\in\mathcal{V}$ has $2$ “$abc$ voters” ( voters with preferences $a\succ
b\succ c$) and $3$ $bac$ voters, while $y$ has $2$ $bac$ voters and $3$ $cba$
voters, the quotient distance corresponding to the normalized version of
$d_{H}^{1}$ is $3/5$. This is because we must change at least $3$ of the $5$
voters to convert $x$ to $y$ (switch both $abc$ voters to $cba$, and one of
the $bac$ voters to $cba$). For the Kemeny metric $d_{K}^{1}$, the analogous
quantity is $8/5$, because we must make at least $8$ swaps of adjacent
candidates to convert $x$ to $y$ (switching $abc$ to $cba$ requires $3$ swaps,
and switching $bac$ to $cba$ requires $2$ swaps; similarly, switching both
$abc$ votes to $bac$ and all three $bac$ to $cba$ requires $8$ swaps).

##  4\. Tied sets and decisiveness

All social rules used in practice encounter the problem of breaking ties.
However, many commonly used social rules have the property that the subset of
profiles where a unique output is not determined is “small” (for example
asymptotically negligible as $n\to\infty$, for fixed $m$). This is important,
because if the region where ties occur is small, then ties can be ignored for
many purposes, whereas if that region is asymptotically large, our rule may
suffer extreme lack of decisiveness.

In the worst case, the rule may do nothing, and simply return all possible
$s$-rankings at every profile, making it useless. In the DR framework, this
extreme indecision cannot occur, because some consensus set must be nonempty.
However, it is certainly possible to have “large” subsets of profile space on
which a DR rule is not single-valued. We investigate this question for simplex
rules, giving both positive (few ties) and negative (many ties) results.

###  4.1. Boundaries

We formalize the concept of “tied region” in our geometric context.

######  Definition 4.1.

The boundary of the social rule $R$ is the set of all elections $E$ at which
$R(E)$ is of size at least $2$.

######  Example 4.2.

Suppose that $m=2$, with alternatives $a$ and $b$,
$\mathcal{K}=\operatorname{\mathbf{C}}$, and $d$ is an anonymous neutral
standard distance. The concepts of majority winner and Condorcet winner
coincide when $m=2$. When $n$ is odd, the boundary
$\operatorname{\mathcal{R}}(\mathcal{K},d)$ is empty, whereas when $n$ is
even, the elections having an equal number of $ab$ and $ba$ voters are in the
boundary.

On the other hand, for the simplex rule
$\operatorname{\mathcal{R}}(\overline{\operatorname{\mathbf{C}}},\overline{d})$,
the boundary is the point $(1/2,1/2)$.

Our intuition is that the boundary of a well-behaved simplex rule should be
“small” in $\operatorname{\Delta}_{M}$, and be geometrically “nice”. The
relevant geometric theory is that of _Voronoi diagrams_. We now digress to
review some known results, which will help develop a more refined intuition.

###  4.2. Geometric background

Voronoi theory is usually defined for a metric space, and most commonly for a
Minkowski space (a finite-dimensional real normed vector space). All
definitions below work for an arbitrary metric space. The theory can no doubt
be generalized to distances, but we do not deal with maximum generality here.
Our main interest is in explaining that there are several interesting reasons
why DR rules defined by $\ell^{p}$-votewise distances may fail to be decisive.

For a fixed set of of sites (subsets of the entire space), the open Voronoi
cell of each site $X$ is defined as the set of points closer to $X$ than to
any other site. The boundaries of these cells are contained in the union of
bisectors, where a bisector of the sites $X$ and $Y$, denoted
$\operatorname{\beta}(X,Y)$, is defined to be the set of points equidistant
from those two sites.

Interpreting the sites as the consensus sets $\mathcal{K}_{r}$, we see that
the open Voronoi cell corresponding to $\mathcal{K}_{r}$ is precisely the set
on which $\operatorname{\mathcal{R}}(\mathcal{K},d)$ is single-valued with
value $r$. Also, the boundary as defined above is just the union of boundaries
of all Voronoi cells.

We first discuss bisectors, because if these are well-behaved, so will the
boundary of the rule be. We first restrict to the nicest situation (where our
intuition is strongest), namely where the space is $\mathbb{R}^{n}$ under the
Euclidean $\ell^{2}$ norm. Suppose first that the sites are all distinct
points. In this case for each pair of distinct sites $X$ and $Y$, the bisector
$\operatorname{\beta}(X,Y)$ is a hyperplane normal to the line joining the
points. The Voronoi cells are therefore convex polyhedra that tile the entire
space.

However, this situation is rather special. In fact $\operatorname{\beta}(X,Y)$
is a hyperplane for all $X$ and $Y$ if and only if the space is indeed
Euclidean (in other words the norm is $\ell^{2}$) [13]. Thus we should expect
to see bisectors that are not hyperplanes. Of course, such bisectors may still
be well-behaved, for example smooth hypersurfaces. Note that
$\operatorname{\beta}(X,Y)$ is known to be homeomorphic to a hyperplane
provided the norm is strictly convex (recall that a norm is strictly convex if
its unit sphere contains no line segment) and even sometimes when it is not
[9]. This does not preclude nasty behaviour such as two bisectors intersecting
in arbitrarily complicated ways, but for norms defined algebraically, such as
$\ell^{p}$, that does not happen.

When the sites are not single points (in particular when they are not
separated), bisectors may be poorly behaved even in $\ell^{2}$ (see Example
4.4). We conclude that well-behaved bisectors should not be expected in
general, and we explore this in the next section.

###  4.3. Large boundary

The most obvious way for a rule to be rather indecisive is if the underlying
distance does not distinguish points well. We say that a subset of a Minkowski
space (possibly defined with a seminorm) is large if it contains an open ball,
and small otherwise.

######  Example 4.3.

(pseudometric) Consider the Copeland rule whose boundary contains all points
with no unique Copeland winner. This contains in particular the set where all
candidates have the same Copeland score, for example because the majority
tournament contains a cycle that includes all candidates. This is a large
subset of $\operatorname{\Delta}_{M}$. To see this, note that in terms of
coordinates, the majority cycle is described by $\binom{m}{2}$ equations of
the form $\sum_{i\in S_{ab}}x_{i}>\sum_{i\in S_{ba}}x_{i}$, where $S_{ab}$
denotes the set of rankings for which $a$ is above $b$. The tied set contains
a sufficiently small neighborhood of every point for which all inequalities
are strict, because small changes to the proportions of voter types will not
change the majority tournament.

In view of this example, we should require our distances to be quasimetrics.
However, there are other more subtle problems that can occur. Note that in the
next example, the distance is $\ell^{2}$ and is hence as nice as could be
expected: a metric induced by a norm that is strictly convex, symmetric, and
algebraically defined. The problem is that the consensus notion is wrong —
intuitively, consensus sets should be separated, because otherwise how could
the consensus choice be uncontroversial?

######  Example 4.4.

(non-separated consensus) Let $m=3$ and consider $\operatorname{\Delta}_{6}$
with the usual $\ell^{2}$ metric (induced from $\mathbb{R}^{5}$ which
coordinatizes $H_{6}$ in the usual way).

Consider the half-open line segments $L_{1},L_{2}$ that join the center $P$ of
$\operatorname{\Delta}_{6}$ to the points $x_{abc}=1$ and $x_{bca}=1$
respectively (Figure 4.1 gives some intuition in lower dimension). Each
contains the endpoint on the boundary, but neither contains the center of the
simplex.

Define a $1$-consensus by letting
$\mathcal{K}_{a}=L_{1},\mathcal{K}_{b}=L_{2}$ and $\mathcal{K}_{c}$ be the
single point $x_{cab}=1$. Let $H_{1},H_{2}$ be the hyperplanes (in
$\operatorname{\Delta}_{6}$, i.e. having dimension $4$) normal to
$L_{1},L_{2}$ at $P$. Let $S$ be the set of points in
$\operatorname{\Delta}_{6}$ that lie on the other side of $H_{1}$ from $L_{1}$
and on the other side of $H_{2}$ from $L_{2}$. Then each point of $S$ lies on
the bisector of $L_{1}$, $L_{2}$ with respect to the usual $\ell^{2}$ metric
$d$, because the closest point of $L_{1}$ is $P$ and this is the closest point
of $L_{2}$. Every point of $S$ that is closer to the centre of
$\operatorname{\Delta}_{6}$ than to $\mathcal{K}_{c}$ (this includes the point
$L_{1}\cap L_{2}$) is in the boundary of the social choice rule
$\operatorname{\mathcal{R}}(\mathcal{K},d)$, which is therefore large. Note
that $\mathcal{K}$ satisfies anonymity and homogeneity, but not neutrality.
Furthermore, every $\mathcal{K}_{r}$ is a convex polyhedral subset of the
simplex.

If instead we define $\mathcal{K}$ symmetrically by letting $\mathcal{K}_{c}$
be the line segment $L_{3}$ joining the point $x_{cab}=1$ to the centre of the
simplex, then although the bisectors are large on $\operatorname{\Delta}_{6}$,
the boundary of the rule is small. This is because points in $S$ are now
closer to $L_{3}$ than either $L_{1}$ or $L_{2}$.

Also note that if the line segments $L_{1}$ and $L_{2}$ did not approach
arbitrarily closely, the bisectors would all be small.

Figure 4.1. Illustration for Example 4.4.$a$$b$$c$

Thus we should require that consensus sets be separated. However, there is
another common way in which bisectors can fail to behave well, which is when
the underlying norm in a Minkowski space is not strictly convex. We now
analyse a special case of this in some detail.

##  5\. Analysis of $\ell^{1}$-votewise metrics

Votewise distances based on the $\ell^{1}$ norm are very commonly used. They
are typically computationally easy and have a clear interpretation in terms of
adding distances corresponding to each voter. In fact we are not aware of a
named $\ell^{p}$-votewise rule that has been defined for any $p\neq 1$.
However, when we consider decisiveness, there are some potential negative
consequences to using the $\ell^{1}$ norm.

We first show in Proposition 5.1 and Proposition 5.3 that each
$\ell^{1}$-votewise metric corresponds to a (Wasserstein) distance on the
simplex that is induced by a norm that is not strictly convex.

We fix a candidate set $C$ with $|C|=m$ and let $M=m!$ as in previous
sections. Let $c=(1,1,\dots,1)/M\in\mathbb{R}^{M}$ be the center of the
simplex $\Delta_{M}$. Now, we translate the center $c$ to the origin, and we
denote by $\Delta^{\prime}$ the image of the simplex under this translation.
We denote by $\mathcal{H}$ the hyperplane containing $\Delta^{\prime}$. Our
study of the geometry under the Wasserstein distance will be facilitated by
the following observations.

######  Proposition 5.1.

Let $d$ be an $\ell^{1}$-votewise distance. Then $d$ induces a norm $N$ on
$\mathcal{H}$.

###### Proof.

It is a well known property of the Wasserstein $1$-distance (the norm is
called the Kantorovich-Rubinstein norm [20, Ch 6]). Explicitly, one first
shows that any Wasserstein distance is translation-invariant. Then one shows
that the function $f:x\mapsto d^{1}_{W}(x+c,c)$ is homogeneous on
$\Delta^{\prime}$. Since every translation-invariant and homogeneous metric is
induced by a norm, $d$ induces a norm $N$ on $\mathcal{H}$ by setting
$N(x)=f(x)$ on $\Delta^{\prime}$ and then extending it to $\mathcal{H}$ by
requiring it to be homogeneous. ∎

######  Remark 5.2.

This result is not true for the other Wasserstein metrics, because they do not
satisfy the homogeneity property of norms. For example, let us choose
$z\in\Delta^{\prime}$ such that $z_{1}\leq 0$ and $\forall i\not=1,z_{i}\geq
0$. It is easy to show that the matrix $A$ reaching the minimum in the
definition of $d_{W}^{p}(x,y)$ is such that $A_{rr}=min(x_{r},y_{r})$ for all
$r$ and then $d_{W}^{p}(x,y)=d_{W}^{p}((x-y)^{+},(y-x)^{+})$ where
$x^{+}=(\max(x_{1},0),...\max(x_{n},0))$. Then
$d_{W}^{p}(z+c,c)^{p}=d_{W}^{p}((z_{1},0,...0),(0,z_{2},...z_{n}))=\sum_{r^{\prime}}z_{r^{\prime}}d(r,r^{\prime})^{p}$,
and $d_{W}^{p}(\lambda
z+c,c)=|\lambda|^{\frac{1}{p}}\sum_{r^{\prime}}z_{r^{\prime}}d(r,r^{\prime})^{p}=|\lambda|^{\frac{1}{p}}d_{W}^{p}(z+c,c)$.

######  Proposition 5.3.

The norm $N$ of Proposition 5.1 is not strictly convex.

###### Proof.

We need to show that the unit sphere is not strictly convex. Fix a ranking
$r\in L(C)$ and consider the subset $S_{r}$ of all points $x\in\mathcal{H}$
where only the component corresponding to $r$ is negative. In $S_{r}$, we have

$N(x)=\sum_{r^{\prime}}x_{r^{\prime}}d(r,r^{\prime}).$

Thus the equation $N(x)=1$ of the unit sphere defines a hyperplane in $S_{r}$.
Since $S_{r}$ is large, the unit ball is not strictly convex. ∎

We can now show that for any distance $d$, there are two distinct points whose
bisector under the Wasserstein distance $d^{1}_{W}$ is large.

######  Proposition 5.4.

Consider a norm $N$ induced over $\mathcal{H}$ by an $\ell^{1}$-votewise
metric. Let $r,r_{1},r_{2}$ be rankings. We denote by $d_{1}$ and $d_{2}$ the
distances $d(r,r_{1})$ and $d(r,r_{2})$. Let $\epsilon>0$. We define $x$ and
$y$ as the two points of $\mathcal{H}$ such that
$x_{r}=-x_{r_{1}}=\frac{\epsilon}{d_{1}}$,
$y_{r}=-y_{r_{2}}=\frac{\epsilon}{d_{2}}$ and all other components are equal
to zero. Then, any point $z\in\mathcal{H}$ such that $z_{r}\leq 0$ and
$z_{r^{\prime}}\geq 0$ for all $r^{\prime}\not=r$ is equidistant from $x$ and
$y$ according to $N$.

###### Proof.

Let $z$ be such a point. Then, $x-z$ and $y-z$ have only one positive
component: the one corresponding to the ranking $r$. So
$N(x-z)=\sum_{r^{\prime}\not=r}(x_{r^{\prime}}-z_{r^{\prime}})d(r,r^{\prime})$
and
$N(y-z)=\sum_{r^{\prime}\not=r}(y_{r^{\prime}}-z_{r^{\prime}})d(r,r^{\prime})$.
Since the only components (different from $r$) where $x$ and $y$ differ are
$r_{1}$ and $r_{2}$, they are equidistant from $z$ if and only if
$(x_{r_{1}}-z_{r_{1}})d_{1}+(x_{r_{2}}-z_{r_{2}})d_{2}=(y_{r_{1}}-z_{r_{1}})d_{1}+(y_{r_{2}}-z_{r_{2}})d_{2}$,
which is equivalent to
$x_{r_{1}}d_{1}+x_{r_{2}}d_{2}=y_{r_{1}}d_{1}+y_{r_{2}}d_{2}$, which is in
turn equivalent to $x_{r_{1}}d_{1}=y_{r_{2}}d_{2}$, which is true by
definition. ∎

It follows that the behaviour of $\ell^{1}$-votewise distances is rather
counterintuitive.

######  Corollary 5.5.

Let $d$ be an $\ell^{1}$-votewise metric. Then there is a consensus
$\mathcal{K}$ consisting of isolated points, such that the boundary of
$\operatorname{\mathcal{R}}(\mathcal{K},d)$ is large.

###### Proof.

Write $x_{\epsilon}$ and $y_{\epsilon}$ for points $x$ and $y$ of the form
defined in Proposition 5.4. That proposition implies that, if we set
$\mathcal{K}_{a}=\\{x_{\epsilon}\\}$ and $\mathcal{K}_{b}=\\{y_{\epsilon}\\}$
and choose a sufficiently small $\epsilon$, then
$\operatorname{\beta}(\mathcal{K}_{a},\mathcal{K}_{b})$ will be large. Also,
for any other candidate $c$, if we set
$\mathcal{K}_{c}=\\{x_{\epsilon_{c}}\\}$ with $\epsilon<\epsilon_{c}$, then
for any $z$ such that $z_{r}$ is the only negative component,
$N(z,\mathcal{K}_{a})=N(z,\mathcal{K}_{b})<N(z,\mathcal{K}_{c})$. ∎

######  Remark 5.6.

Note that the consensus in the proof of Corollary 5.5 is somewhat unnatural.
For example, it is not neutral and does not intersect the boundary of
$\operatorname{\Delta}_{M}$.

The next question is how often this kind of situation happens. For simplicity
we focus on the case $d=d_{H}$, when the induced norm is exactly $\ell^{1}$.
We can give an exact characterization of when two points have a large
bisector. This is directly connected with the well-known integer partition
problem.

######  Proposition 5.7.

Let $M\geq 1$ and let $x,y\in\mathbb{R}^{M}$. We denote by $S$ the set of
values $(x_{i}-y_{i})$. Then $x$ and $y$ have a large bisector under
$\ell^{1}$ if and only if there exists a subset $S^{\prime}\subset S$ such
that $\sum_{e\in S^{\prime}}e=\sum_{e\not\in S^{\prime}}e$.

###### Proof.

By definition
$\operatorname{\beta}(x,y)=\\{z|\sum_{i}|x_{i}-z_{i}|=\sum_{i}|y_{i}-z_{i}|\\}$.
We divide $\mathbb{R}^{M}$ into $4^{M}$ subspaces corresponding to the
possible signs of the values $(x_{i}-z_{i})$ and $(y_{i}-z_{i})$. Let $V$ be
one of these subspaces: in $V$, the equality
$\sum_{i}|x_{i}-z_{i}|=\sum_{i}|y_{i}-z_{i}|$ is equivalent to
$\sum_{i}\epsilon_{i}(x_{i}-z_{i})=\sum_{i}\epsilon_{i}^{\prime}(y_{i}-z_{i})$,
where $\forall i,\epsilon_{i},\epsilon^{\prime}_{i}=\pm 1$. This is equivalent
to
$\sum_{i}(\epsilon_{i}-\epsilon^{\prime}_{i})z_{i}=\sum_{i}(\epsilon_{i}x_{i}-\epsilon^{\prime}_{i}y_{i})$.

There are two cases. First, if for some $i$,
$\epsilon_{i}\not=\epsilon_{i}^{\prime}$, then the linear equation in $z$ is
nontrivial and $z$ lies in a hyperplane, so that
$V\cap\operatorname{\beta}(x,y)$ is small. The other case is when
$\epsilon_{i}=\epsilon_{i}^{\prime}$ for all $i$, in which case the left side
of the equation is $0$. If the right side is nonzero there is no solution, and
$V\cap\operatorname{\beta}(x,y)=\emptyset$. If the right side is zero, then
$V\cap\operatorname{\beta}(x,y)$ is large (for each $i$, it contains all
points for which $z_{i}$ is sufficiently large, for example). The right side
is zero if and only if $\sum_{i}\epsilon_{i}(x_{i}-y_{i})=0$, which is
equivalent to the fact that there exists $S^{\prime}\subset S,\sum_{e\in
S^{\prime}}e=\sum_{e\not\in S^{\prime}}e$. ∎

The argument in the proof gives insight into the shape of any large bisector
of two points: any ball included in the bisector is contained in cells where
$(x_{i}-z_{i})$ and $(y_{i}-z_{i})$ are of the same sign, and thus in a subset
defined by a set of equations $z_{i}\leq\min(x_{i},y_{i})$ or
$z_{i}\geq\max(x_{i},y_{i})$ for all $i$. It implies, for example, that if the
points are corners of the simplex, the large bisector in $\mathbb{R}^{M}$
intersects $\operatorname{\Delta}_{M}$ in a small set. Thus, for example,
large boundaries cannot occur with $\operatorname{\mathbf{S}}$ (which also
follows from Corollary 6.9 below).

######  Definition 5.8.

The standard decision problem PARTITION is defined as follows. Input is a
vector $(z_{1},\dots,z_{M})$ of natural numbers. We must decide whether there
is a subset $S\subseteq\\{1,\dots,M\\}$ for which $\sum_{i\in
S}z_{i}=\sum_{i\not\in S}z_{i}$.

Define the decision problem LARGE-BISECTOR as follows. Input is a pair $(x,y)$
of points of $\mathbb{Q}^{M}_{+}$ and we must decide whether
$\operatorname{\beta}(x,y)$ contains an open ball under the $d^{1}_{H}$
metric.

######  Remark 5.9.

Note that $M$ is part of the input in each case. When $M$ is bounded,
PARTITION can be solved trivially by exhaustive enumeration of subsets. Note
that if we let $K:=\sum_{i}x_{i}$, then a standard dynamic programming
algorithm solves PARTITION in $O(KM)$ time.

######  Proposition 5.10.

LARGE-BISECTOR is NP-complete.

###### Proof.

Given an instance $(z_{1},\dots,z_{M})$ of PARTITION, let
$x_{i}=z_{i},y_{i}=0$. This gives an instance of LARGE-BISECTOR, which is a
yes instance if and only if the original instance is a yes instance of
PARTITION. Thus LARGE-BISECTOR is NP-hard. On the other hand, given a yes-
instance $(x,y,M)$ of LARGE-BISECTOR, the criterion in Proposition 5.7 gives a
polynomial-sized certificate checkable in polynomial time, so LARGE-BISECTOR
is in NP. Thus, LARGE-BISECTOR is NP-complete. ∎

######  Remark 5.11.

We suspect the analogue of LARGE-BISECTOR to be NP-hard for every
$\ell^{1}$-votewise metric. Presumably it is in NP for “nice” distances, but
of course there exist distances which cannot even be computed in polynomial
time, so that an analogue of Proposition 5.7 may not exist.

The question of large bisectors is quite subtle, because large bisectors do
not occur when the consensus sets are hyperplanes instead of points.

######  Proposition 5.12.

The bisector of two distinct hyperplanes under any norm on $\mathbb{R}^{M}$ is
contained in a union of at most two hyperplanes.

###### Proof.

The distance from a point $x$ to a hyperplane $H$ defined by $a^{T}x=b$ is
equal to $d(x,H)=\frac{|a^{T}x-b|}{||a||^{*}}$ where ∗ denotes the dual norm
(see for example [12]; the exact definition is not necessary here). Now, let
$H^{\prime}$ be another hyperplane defined by the equation $a^{\prime
T}x=b^{\prime}$. We assume that $||a||^{*}=||a^{\prime}||^{*}$ (without loss
of generality since multiplying by a scalar still defines the same
hyperplane). The bisector of $H$ and $H^{\prime}$ can be defined as the set of
points $x$ satisfying $|a^{T}x-b|=|a^{\prime T}x-b^{\prime}|$. So, we have two
cases, depending on the sign of these absolute values: either
$\sum_{i}(a_{i}-a^{\prime}_{i})x_{i}=b-b^{\prime}$ or
$\sum_{i}(a_{i}+a^{\prime}_{i})x_{i}=b+b^{\prime}$. Since $H\neq H^{\prime}$,
each of these is the equation of a hyperplane. ∎

##  6\. Small bisectors and hyperplane rules

All our results in this section show that the bisectors in question are
contained in a finite union of hyperplanes. Rules which have a well-defined
winner on each component of the complement in $\operatorname{\Delta}_{M}$ of a
finite set of hyperplanes have been studied recently. Mossel, Procaccia and
Racz [15] call such simplex rules hyperplane rules and show their equivalence
with the generalized scoring rules of Xia and Conitzer [21]. These rules can
be defined axiomatically using finite local consistency [22]. Although
originally introduced for social choice rules only, the definition extends to
social welfare rules [2] and it is clear that it also extends to general $s$.

Most rules that have ever been studied by social choice theorists are
hyperplane rules. A notable exception is Copeland’s rule. In order to
interpret Copeland’s rule as a hyperplane rule, Mossel, Procaccia and Racz
[15] require that the winner be (arbitrarily) specified on the tied region.
This seems to us to be stretching the definition too far – we could do the
same thing for any indecisive rule.

We now give a sufficient condition for a DR rule to be a hyperplane rule.

######  Definition 6.1.

Let $\mathcal{K}$ be a homogeneous consensus and $d$ a homogeneous distance.

Say that $(\mathcal{K},d)$ satisfies the votewise minimizer property (VMP) if
the following condition is satisfied.

> There is a mapping $\xi:L(C^{*})\times L_{s}(C^{*})\to L(C^{*})$ such that
> for each $r\in L_{s}(C^{*})$ with $\mathcal{K}_{r}\neq\emptyset$, and each
> election $E=(C,V,\pi)\in\mathcal{E}$, $m(E,r):=(C,V,\xi(\pi,r))$ minimizes
> the distance under $d$ from $E$ to $\mathcal{K}_{r}$, where
> $\xi(\pi,r):=(\xi(\pi_{1},r),\dots,\xi(\pi_{n},r))$.

######  Remark 6.2.

The VMP allows us to find a minimizer by dealing with each voter separately,
and if two voters have the same preference order in $E$ then the corresponding
votes in $m(E,r)$ are equal. Also if $d$ is votewise based on $N$, then

$d(E,\mathcal{K}_{r})=N(d(\pi_{1},\xi(\pi_{1},r)),\dots,d(\pi_{n},\xi(\pi_{n},r)).$

If $N$ is also symmetric then $d(E,\mathcal{K}_{r})$ depends only on the
multiset of all values $d(\pi_{i},\xi(\pi_{i},r))$.

######  Proposition 6.3.

Let $d$ be $\ell^{p}$-votewise for some $1\leq p<\infty$ and suppose that
$(\mathcal{K},d)$ satisfies the VMP. Then on $\operatorname{\Delta}_{M}$,
$\operatorname{\beta}(\mathcal{K}_{r},\mathcal{K}_{r^{\prime}})$ is defined by

$\sum_{t\in L(C)}x_{t}\delta(t,r)^{p}=\sum_{t\in
L(C)}x_{t}\delta(t,r^{\prime})^{p}.$

###### Proof.

The distance between $E=(C,V,\pi)$ and the minimizer $m(E,r)=(C,V,\pi^{*})$
equals $N(\Sigma)$ where $\Sigma$ is the multiset with entries $\delta(t,r)$
occurring according to their multiplicities $nx_{t}$, for all $t\in L(C)$. The
specific form of $N$ then shows that
$d(E,m(E,r))^{p}=n\left(\sum_{t}x_{t}\delta(t,r)^{p}\right)$. Applying the
same argument for $r^{\prime}$ yields the result. ∎

######  Definition 6.4.

Suppose that the $s$-consensus $\mathcal{K}$ satisfies the following: for each
$r\in L_{s}(C)$, there is a subset $S_{r}$ of $L(C)$ such that
$\mathcal{K}_{r}$ consists precisely of those elections for which every voter
has a ranking in $S_{r}$. Then we call $\mathcal{K}$ a generalized unanimity
consensus.

######  Proposition 6.5.

Let $d$ be an $\ell^{p}$-votewise distance on $\mathcal{E}$ and let
$\mathcal{K}$ be a generalized unanimity consensus. Then $(\mathcal{K},d)$
satisfies the VMP.

###### Proof.

If $\mathcal{K}_{r}\neq\emptyset$, define $\xi(\pi_{i})$ to be the closest
element of $S_{r}$ to $\pi_{i}$ under the underlying distance on $L(C)$ (if
there is more than one such element, make an arbitrary choice). For each
$E=(C,V,\pi)$, the element $E^{*}=(C,V,\xi(\pi))$ belongs to
$\mathcal{K}_{r}$. If $F=(C,V,\pi^{\prime})\in\mathcal{K}_{r}$ then
$d(E,F)\geq d(E,E^{*})$ because $d(\pi_{i},\xi(\pi_{i}))\leq
d(\pi_{i},\pi^{\prime}_{i})$ for each $i$, and the $\ell^{p}$-norm is
increasing in each argument in the positive orthant. Thus $E^{*}$ is the
desired minimizer. ∎

######  Corollary 6.6.

$(\operatorname{\mathbf{S}}^{s},d^{p})$ satisfies the VMP for every distance
$d$.

###### Proof.

We can take $S_{r}$ to be the set of rankings which agree with $r$ in their
initial $s$-ranking, showing that $\operatorname{\mathbf{S}}^{s}$ is a
generalized unanimity consensus. ∎

######  Example 6.7.

Let $\mathcal{K}=\operatorname{\mathbf{W}}$ and $d=d_{K}$, and $N=\ell^{2}$.
For each $E=(C,V,\pi)\in\mathcal{E}$ and $a\in C$, we can take $\xi(\pi,a)$ to
be the ranking derived from $\pi$ by swapping $a$ to the top as efficiently as
possible in each $\pi_{i}$. Thus
$d(E,\operatorname{\mathbf{W}}_{a})^{2}=\sum_{t\in L(C)}n(t)(\xi(t,a)-1)^{2}$,
where $n(t)$ is the number of times $t$ occurs in $\pi$.

######  Remark 6.8.

We do not know of any “natural” consensus and distance which satisfy the VMP,
apart from those already mentioned. We can easily create strange examples,
however, by creating generalized unanimity consensuses. If for each candidate
$a$ we choose a single ranking with $a$ at the top, this yields a generalized
unanimity consensus that is extended by $\operatorname{\mathbf{W}}$. Note that
this consensus is not neutral. Alternatively, we could choose all rankings
having $a$ in the first or second position (in which case $a$ is the consensus
winner), or $b$ in the first position as long as $a$ is not in the second
position (in which case $b$ is the consensus winner), or $c$ in the first or
second position (provided $a$ is not first or second and $b$ is not first), in
which case $c$ is the consensus winner. Again, this is not neutral.

######  Corollary 6.9.

Suppose that $d$ is $\ell^{p}$-votewise with $1\leq p<\infty$, $d$ is finite
and not identically zero, and $\mathcal{K}$ is a generalized unanimity
consensus. Then $\operatorname{\mathcal{R}}(\mathcal{K},d)$ is a hyperplane
rule.

###### Proof.

Since $d<\infty$ we may rearrange the formula in Proposition 6.3 to get
$\sum_{t}(\delta(t,r)-\delta(t,r^{\prime}))=0$. It suffices to show that the
linear function on the left side is not identically zero. That could only
happen if $\delta(t,r)=\delta(t,r^{\prime})$ for all $t$. However, note that
the distance from $x$ to $\mathcal{K}_{r}$ is attained at a point $m(x,r)$
where $m(x,r)_{t}=x_{t}$ for all $t\not\in S$, and
$d(x,\mathcal{K}_{r})=\sum_{t\in S}x_{t}\delta(t,r)^{p}$. If $r\neq
r^{\prime}$ then by definition $S_{r}\neq S_{r^{\prime}}$. Thus taking
$t\not\in S\cap S^{\prime}$, without loss of generality $\delta(t,r)=0$ and
$\delta(t,r^{\prime})\neq 0$. ∎

######  Corollary 6.10.

Every rule of the form
$\operatorname{\mathcal{R}}(\operatorname{\mathbf{S}}^{s},d^{p})$, where
$1\leq p<\infty$ and $d$ is a distance on $L(C)$ that is neither infinite nor
identically zero, is a hyperplane rule.

######  Remark 6.11.

This result does not extend to general distances. For example, Copeland’s rule
as we have defined it is not a hyperplane rule, yet it can be defined as
$\operatorname{\mathcal{R}}(\operatorname{\mathbf{W}},d_{RT})$. Also note that
when $p=\infty$, we do not obtain a hyperplane rule. For example, every point
$x\in\operatorname{\Delta}^{\mathbb{Q}}_{M}$ for which every coordinate is
nonzero is equidistant from all $\operatorname{\mathbf{S}}_{r}$, so
$\operatorname{\mathcal{R}}(\operatorname{\mathbf{S}},d^{\infty})$ is almost
maximally indecisive.

######  Remark 6.12.

Rules of the type described in Proposition 6.3 are rather special. Since the
distance to $\mathcal{K}_{r}$ is of the form $\sum_{t}x_{t}\delta(t,r)^{p}$,
each can be thought of as a differently weighted version of the rule with
$p=1$.

##  7\. Discussion and future work

We now summarize what we have learned about the boundary of a DR simplex rule.

  * •

Using a pseudometric that is not a metric can easily lead to a large boundary.

  * •

Large bisectors can occur even with $\ell^{2}$, if consensus sets are not
separated.

  * •

Large bisectors can occur with $\ell^{1}$-votewise rules, even for consensus
sets that are isolated points, and it can be difficult to determine whether
they do occur.

  * •

Even when bisectors are large in the ambient space, using consensus sets on
the boundary of the simplex often yields small bisectors on the simplex.

  * •

Even when bisectors are large on the simplex, neutrality often makes the
boundary of the rule small.

We have seen some desirable properties of consensus sets, such as homogeneity
and neutrality. We argue that convexity (defined in the usual way via
restriction from $\mathbb{R}^{M}$) of each $\mathcal{K}_{r}$ is another
essential condition. In the following example, it seems ridiculous that $a$
should win at the extra point.

######  Example 7.1.

Consider the case $m=3$, and the consensus formed by extending
$\operatorname{\mathbf{W}}$ so that $a$ is the winner whenever
$x_{bca}=x_{cba}=1/2$ (and similarly for $b,c$). This consensus is anonymous
and homogeneous, but $\mathcal{K}_{a},\mathcal{K}_{b},\mathcal{K}_{c}$ are not
convex.

######  Remark 7.2.

In the simplex model, convexity (over $\mathbb{Q}$) is equivalent to the
notion of consistency: if we split the voter set into two parts each of which
elects $r$, the original voter set should elect $r$. It rules out the above
example. Note that $\operatorname{\mathbf{C}}$ and
$\operatorname{\mathbf{S}}^{s}$ are convex. In fact we do not know of a
consensus that has been used in the literature that is not convex.

Based on the above results, we suggest that the following criteria be required
of consensus classes in the simplex (anonymity and homogeneity come for free)

  * •

neutrality

  * •

convexity

  * •

separation

  * •

intersecting the boundary of the simplex

while distances should be required to be metrics.

Note that the separation requirement rules out $\operatorname{\mathbf{C}}$ as
a consensus notion. This may of course be somewhat controversial. It may turn
out that neutral rules based on $\operatorname{\mathbf{C}}$ and using metrics
always have small boundary (we do not know of a counterexample, but have no
proof yet). However, it seems strange to consider a situation arbitrarily
close to a complete tie among all rankings (the centre of the simplex) to be
an election on which a “consensus” can be formed.

We saw above that $\ell^{1}$ votewise distances can lead to major problems
with decisiveness. However there are many natural examples of $\ell^{1}$
votewise distances, as we have seen. We do not know of any “natural” simplex
rule satisfying the above requirements for which the boundary is large.
However, not all obvious rules have been thoroughly explored.

Systematic exploration of rules $\operatorname{\mathcal{R}}(\mathcal{K},d)$,
where $\mathcal{K}$ and $d$ satisfy the recommendations above, may prove
fruitful in finding new rules with desirable properties. For example, by the
results in this paper and [8], the rules
$\operatorname{\mathcal{R}}(\operatorname{\mathbf{S}}^{s},d^{p})$ where $d$ is
a neutral metric on permutations, are anonymous, homogeneous, neutral,
continuous, hyperplane rules. There are many neutral (also called right-
invariant) metrics on permutations we have not discussed here, such as the
$\ell^{q}$-metrics (the cases $q=1,2,\infty$ being called Spearman’s footrule,
Spearman’s rank correlation and the maximum displacement distance), and the
Lee distance [4]. Even the rules
$\operatorname{\mathcal{R}}(\operatorname{\mathbf{W}},d^{p})$ and
$\operatorname{\mathcal{R}}(\operatorname{\mathbf{S}},d^{p})$ have not been
fully explored, to our knowledge.

Even less understood are rules of the form
$\operatorname{\mathcal{R}}(\operatorname{\mathbf{C}},\ell^{p})$. For example,
when $p=1$, we obtain a homogeneous version of the recently described _Voter
Replacement Rule_ [5]. Little is known about the Voter Replacement Rule other
than that it is not homogeneous [8].

Beyond the realm of votewise and $\ell^{p}$ distances, we have already
mentioned more general statistical distances. Finally, rules involving various
matrix norms on the tournament matrices have not been well studied.

Distance-based aggregation of preferences is a more general procedure than we
have studied here: it could be applied with many different input and output
spaces [Zwic2014]. If the input consists of the tournament matrix rather than
the profile, there is a natural hypercube representation of the input in
$\binom{m}{2}$ dimensions. Saari & Merlin [19] showed that the Kemeny rule can
be described in this way using distance rationalization with respect to the
$\ell^{1}$ norm and $\operatorname{\mathbf{S}}$. This is the same as using an
elementwise norm on the weighted tournament matrix, in our framework. When
using profiles as input, the simplex geometry is hard enough to visualize that
some authors have used a fixed projection to the _permutahedron_ and
essentially used $\operatorname{\mathbf{S}}$ as a consensus. The cases $p=2$
(_mean proximity rules_) [26, 10] and $p=1$ (_mediancenter rules_) [3] have
received attention. These can be interpreted in our framework by changing the
distance — detailed formulae might be interesting.

A question which partially motivated the present work remains unanswered. Does
(a homogenization of) Dodgson’s rule have a “small and nice” boundary? What
about other Condorcet rules
$\operatorname{\mathcal{R}}(\operatorname{\mathbf{C}},d)$ where $d$ is a
votewise metric, or even rules based on $d_{T}$, such as the maximin rule?

## References

  * [1] D.E. Campbell and S.I. Nitzan.  Social compromise and social metrics.  Social Choice and Welfare, 3(1):1–16, 1986.
  * [2] Ioannis Caragiannis, Ariel D Procaccia, and Nisarg Shah.  Modal ranking: A uniquely robust voting rule.  In Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI), pages 616–622, 2014.
  * [3] Davide P. Cervone, Ronghua Dai, Daniel Gnoutcheff, Grant Lanterman, Andrew Mackenzie, Ari Morse, Nikhil Srivastava, and William S. Zwicker.  Voting with rubber bands, weights, and strings.  Mathematical Social Sciences, 64(1):11–27, 2012.
  * [4] Michel Marie Deza and Elena Deza.  Encyclopedia of distances.  Springer, 2009.
  * [5] Edith Elkind, Piotr Faliszewski, and Arkadii Slinko.  Rationalizations of Condorcet-consistent rules via distances of hamming type.  Social Choice and Welfare, 39(4):891–905, 2012.
  * [6] Edith Elkind, Piotr Faliszewski, and Arkadii Slinko.  Distance rationalization of voting rules.  Social Choice and Welfare, 45(2):345–377, 2015.
  * [7] Piotr Faliszewski, Edith Hemaspaandra, and Lane A Hemaspaandra.  How hard is bribery in elections?  Journal of Artificial Intelligence Research, 35:485–532, 2009.
  * [8] Benjamin Hadjibeyli and Mark C Wilson.  Distance rationalization of social rules.  arXiv preprint arXiv:1610.01902, 2016.
  * [9] A.G. Horvath.  On bisectors in Minkowski normed spaces.  Acta Mathematica Hungarica, 89:233–246, 2000.
  * [10] Sébastien Lahaie and Nisarg Shah.  Neutrality and geometry of mean voting.  In Proceedings of the fifteenth ACM conference on Economics and computation, pages 333–350. ACM, 2014.
  * [11] Ehud Lerer and Shmuel Nitzan.  Some general results on the metric rationalization for social decision rules.  Journal of Economic Theory, 37(1):191–201, 1985.
  * [12] O. L. Mangasarian.  Arbitrary-norm separating plane.  Operations Research Letters, 24:15–23, 1997.
  * [13] Heinrich Mann.  Untersuchungen über wabenzellen bei allgemeiner minkowskischer metrik.  Monatshefte für Mathematik, 42(1):417–424, 1935.
  * [14] Tommi Meskanen and Hannu Nurmi.  Closeness counts in social choice.  In Matthew Braham and Frank Steffen, editors, Power, Freedom, and Voting, pages 289–306. Springer Berlin Heidelberg, 2008.
  * [15] Elchanan Mossel, Ariel D. Procaccia, and Miklós Z. Rácz.  A smooth transition from powerlessness to absolute power.  Journal of Artificial Intelligence Research, pages 923–951, 2013\.
  * [16] Shmuel Nitzan.  Some measures of closeness to unanimity and their implications.  Theory and Decision, 13(2):129–138, 1981.
  * [17] Donald G. Saari.  Geometry of voting, volume 3 of Studies in Economic Theory.  Springer-Verlag, Berlin, 1994.
  * [18] Donald G. Saari.  Basic geometry of voting.  Springer-Verlag, Berlin, 1995.
  * [19] Donald G. Saari and Vincent R. Merlin.  Changes that cause changes.  Soc. Choice Welf., 17(4):691–705, 2000.
  * [20] Cédric Villani.  Optimal transport: old and new, volume 338.  Springer Science & Business Media, 2008.
  * [21] Lirong Xia and Vincent Conitzer.  Generalized scoring rules and the frequency of coalitional manipulability.  In Lance Fortnow, John Riedl, and Tuomas Sandholm, editors, Proceedings 9th ACM Conference on Electronic Commerce (EC-2008), Chicago, IL, USA, June 8-12, 2008, pages 109–118. ACM, 2008.
  * [22] Lirong Xia and Vincent Conitzer.  Finite local consistency characterizes generalized scoring rules.  In Craig Boutilier, editor, IJCAI 2009, Proceedings of the 21st International Joint Conference on Artificial Intelligence, Pasadena, California, USA, July 11-17, 2009, pages 336–341, 2009.
  * [23] H. Young.  Social choice scoring functions.  SIAM Journal on Applied Mathematics, 28(4):824–838, 1975.
  * [24] Peyton Young.  Optimal voting rules.  Journal of Economic Perspectives, 9(1):51–64, 1995.
  * [25] William S Zwicker.  A characterization of the rational mean neat voting rules.  Mathematical and Computer Modelling, 48(9):1374–1384, 2008.
  * [26] William S. Zwicker.  Consistency without neutrality in voting rules: When is a vote an average?  Mathematical and Computer Modelling, 48(9):1357–1373, 2008.