# Representative Proxy Voting

Elliot Anshelevich  Rensselaer Polytechnic Institute
<EMAIL_ADDRESS>Zack Fitzsimmons  College of the Holy Cross
<EMAIL_ADDRESS>Rohit Vaish  Tata Institute of Fundamental Research
<EMAIL_ADDRESS>Lirong Xia  Rensselaer Polytechnic Institute
<EMAIL_ADDRESS>
###### Abstract

We study a model of proxy voting where the candidates, voters, and proxies are
all located on the real line, and instead of voting directly, each voter
delegates its vote to the closest proxy. The goal is to find a set of proxies
that is _$\theta$ -representative_, which entails that for any voter located
anywhere on the line, its favorite candidate is within a distance $\theta$ of
the favorite candidate of its closest proxy. This property guarantees a strong
form of representation as the set of voters is not required to be fixed in
advance, or even be finite. We show that for candidates located on a line, an
optimal proxy arrangement can be computed in polynomial time. Moreover, we
provide upper and lower bounds on the number of proxies required to form a
$\theta$-representative set, thus showing that a relatively small number of
proxies is enough to capture the preferences of any set of voters. An
additional beneficial property of a $\theta$-representative proxy arrangement
is that for strict-Condorcet voting rules, the outcome of proxy voting is
similarly close to the outcome of direct voting.

##  1 Introduction

It is natural to consider settings where voters either may not be able to or
may not be willing to directly cast their vote, but instead decide to delegate
their votes to a proxy. In much of the related work on proxy voting, the
proxies are chosen from the set of eligible voters to then represent the
electorate (see, e.g., Cohensius et al., 2017). In this paper, we consider a
model for proxy voting that _introduces_ proxies to the election using only
the arrangement of the candidates and a given distance $\theta$ for any
collection of voters.

On first glance, the idea of “creating” proxies from scratch might seem
unnatural. However, note that in real-world applications where the
‘candidates’ correspond to different resource allocations or long-term policy
decisions (not actual political candidates), and the ‘proxies’ correspond to
human representatives/experts or policy positions, it is reasonable to assume
that human voters would find a proxy more relatable than the actual candidate.

We call our arrangement _$\theta$ -representative_ since each voter’s closest
proxy is guaranteed to have a top preference that is within $\theta$ of the
voter’s. This can be interpreted as providing a set of _allowed votes_
identified by a set of proxies placed in the metric space, and naturally the
voters cast the vote of the proxy closest to them with the guarantee that this
preference is close to the voter’s. Another way to think about our model is
that we form a set of _representatives_ (proxies) whose choice does not depend
on the locations of the voters (since these locations are difficult to
determine exactly, or perhaps they are not static and change over time). The
goal for this set of representatives is that it captures well the opinions of
the voters, even as the voters change over time, if the voters are able to
express their opinions by delegating their vote to their closest
representative (proxy).

We consider elections where the voters, the proxies, and the candidates are
all located in a metric space, and each voter and each proxy has spatial
preferences determined by its distance to each candidate (see, e.g.,
Schofield, 2008 for a survey on spatial voting). We focus our results on the
one-dimensional case where all candidates and voters lie in the interval
$[0,1]$ (as in Cohensius et al., 2017). While not as general as an arbitrary
metric space, it is an important step in understanding the behavior of the
problem in more general domains. The one-dimensional assumption encompasses
the well-studied domains of single-peaked (Black, 1948) and single-crossing
preferences (Mirrlees, 1971).

What sets our contributions apart from the related work on proxy voting is
that we determine a proxy arrangement _without_ knowing the locations of the
voters; that is, a $\theta$-representative proxy arrangement is representative
of all possible sets of voters simultaneously. In contrast, related work on
proxy voting generally selects proxies or representatives from among a given
set of voters (see, e.g., Cohensius et al., 2017; Meir et al., 2020 and the
references therein).

Restrictions on proxies $\downarrow$ | Bounds on the number of proxies |  Computational
---|---|---
|  Upper bound |  Lower bound |  Results
On top of candidates (Restricted) |  $2\lfloor\frac{1}{\theta}\rfloor$ |  $2\lfloor\frac{1}{\theta}\rfloor$ |  opt in poly time
|  (Theorem 2) |  (1) |  (Theorem 1)
Anywhere within $\mathbb{R}$ (Unrestricted) |  $\frac{3}{2}\lceil\frac{1}{\theta}\rceil$ |  $\lceil\frac{1}{\theta}\rceil$ |  opt in poly time
|  (Theorem 4) |  (2) |  (Theorem 3)
Table 1: Summary of results. For each assumption on the positioning of the
proxies (left column), the second and the third columns provide upper and
lower bounds, respectively, on the number of proxies as a function of $\theta$
for a $\theta$-representative proxy arrangement. The rightmost column contains
the computational results for optimal proxy arrangements.

#### Our Contributions

Our main contributions are as follows (see also Table 1):

  * •

We introduce a new model of proxy voting and measure for the representation of
voter preferences. We consider both the _unrestricted_ case where the proxies
can be placed anywhere, and the _restricted_ case where the proxies can only
be placed at the candidate locations.111Our results also hold if the possible
proxy locations are more general, as long as they include all candidate
locations as a subset.

  * •

We first provide algorithms for computing an optimal $\theta$-representative
proxy arrangement (i.e., one that uses a _minimum_ number of proxies) in
polynomial time (Theorems 1 and 3). However, these algorithms do not provide
much insight into _how many_ proxies are actually necessary in order to be
$\theta$-representative, for any possible set of candidates and voters.
Because of this, we also prove upper and lower bounds on the number of proxies
needed to have a $\theta$-representative proxy arrangement (see Table 1).
These bounds show that a relatively small number of proxies is enough to
capture the preferences of any set of voters, even in the worst case.

  * •

Our results also address the _dual_ problem of minimizing the distance
threshold $\theta$ for a given number of proxies. For example, we prove that
for the unrestricted case, one can use a given budget of $k$ proxies to
compute a $\theta$-representative arrangement with
$\theta\leq\frac{3}{2}\lceil\frac{1}{k}\rceil$ (Corollary 1).

  * •

We observe that the proxy arrangements determined by our algorithms are not
only $\theta$-representative with respect to the voters, but for elections
using strict-Condorcet voting rules, the direct election outcome (i.e.,
without proxies) is within $\theta$ of the proxy-voting outcome (3).

##  2 Related Work

Alger (2006) introduce a general proxy voting model where there is a fixed set
of proxies and the voters can choose a proxy to represent them. Cohensius et
al. (2017) consider a proxy voting setting closely related to ours where the
voters, the proxies, and the candidates are on an interval, and the voters
delegate their vote to their nearest proxy. However, in their work, the
proxies are selected at random and the focus is on how the outcome is
affected.

Green-Armytage (2015) consider proxy voting with spatial preferences where
proxies are elected from among the voters, but additionally explore settings
where proxies can further delegate their vote, which is often referred to as
delegative democracy (see, e.g., Kahng et al., 2018; Gölz et al., 2018). More
general models of delegative democracy have also been studied (see, e.g.,
Brill and Talmon, 2018; Abramowitz and Mattei, 2019). Another line of research
considers electing a set of representatives from the voters, and generally
comparing the outcome from the vote of the committee and the outcome from
direct voting (Skowron, 2015; Pivato and Soh, 2020; Meir et al., 2020; Magdon-
Ismail and Xia, 2018).

Besides having a $\theta$-representative proxy arrangement, we observe that
for Condorcet-consistent voting rules, our results guarantee that the proxy-
voting outcome is within $\theta$ of the direct-voting outcome. This notion of
a $\theta$-representative outcome is related to, but quite different than, the
notion of distortion Procaccia and Rosenschein (2006). A voting rule’s
distortion is the worst-case ratio of the distance from the voters to the
winner and the candidate that minimizes this distance. The study of distortion
is an active area of research in voting (see e.g., Anshelevich et al., 2018;
Goel et al., 2017; Abramowitz et al., 2019; Kempe, 2020).

Feldman et al. (2020) study a similar model to ours for a problem motivated by
fairness in academic hiring. They consider a setup where a set of applicants
(analogous to candidates in our model) are chosen by a set of experts
(analogous to proxies). Each applicant is associated with a known quality
score, and the applicants as well as the experts are arranged on a line. Each
expert votes for its closest candidate, where closeness is defined as
“distance minus quality.” As with the related work on distortion, the aim of
Feldman et al. (2020) is related to the outcome, while our paper is focused on
finding a representative set of proxies.

Finally, we note that our model bears some resemblance to the $p$-coverage
version of the facility location problem (Hassin and Tamir, 1991). Under this
problem, we are given a set $D=\\{v_{1},\dots,v_{n}\\}$ of $n$ demand points,
and the goal is to select a subset $S\subseteq D$ of at most $p$ points such
that each point in $D$ is at most a fixed distance away from some point in
$S$. If we think of the demand set $D$ as the set of candidates and the set
$S$ as the proxies, then the restricted variant of our problem is analogous to
the $p$-coverage facility location problem. However, note that the
unrestricted variant of our problem is significantly more general.

##  3 Preliminaries

For any natural number $s\in\mathbb{N}$, let $[s]\coloneqq\\{1,\dots,s\\}$.
Our model involves three types of entities— _candidates_ , _voters_ , and
_proxies_ —which are described below.

#### Candidates:

Let $\mathcal{C}=\\{c_{1},\dots,c_{m}\\}$ denote a set of $m\in\mathbb{N}$
candidates that are arranged on a line segment $[0,1]$. We will overload
notation to denote the position of the $i^{\text{th}}$ candidate also by
$c_{i}\in[0,1]$. We will assume throughout that the extreme candidates are
located at the endpoints of $[0,1]$ (i.e., $c_{1}=0$ and $c_{m}=1$), and that
all candidates have distinct locations (i.e., for any distinct $i,j\in[m]$,
$c_{i}\neq c_{j}$).

For any pair of adjacent candidates $c_{i}$ and $c_{i+1}$, their _candidate
bisector_ is the vertical line at $(c_{i}+c_{i+1})/2$. Notice that with $m$
candidates, there can, in general, be $\binom{m}{2}$ different bisectors.
However, unless stated otherwise, the term ‘candidate bisector’ will refer to
a bisector between _adjacent_ candidates.

#### Voters:

A voter can be located anywhere in $[0,1]$ and is identified by its location.
For any voter $v\in[0,1]$, its favorite candidate, denoted by
$\texttt{top}(v)$, is the candidate that is closest to it. That is,
$\texttt{top}(v)\coloneqq\arg\min_{c_{i}\in\mathcal{C}}|v-c_{i}|$, where ties
are broken according to any fixed _directionally consistent_ tie-breaking rule
(see Definition 1). Note that we do not assume the set of voters to be fixed
in advance. This is because our results apply to any arbitrary collection of
voters that could be located anywhere within $[0,1]$.

######  Definition 1 (Directionally consistent tie-breaking rule).

A tie-breaking rule is a function $\tau:[0,1]^{3}\rightarrow[0,1]$ that maps
any triple $v,x,y\in[0,1]$ as follows:

$\tau(v,x,y)=\begin{cases}x&\mbox{if }|v-x|<|v-y|\\\ y&\mbox{if
}|v-x|>|v-y|\\\ \text{either $x$ or $y$}&\mbox{otherwise}.\end{cases}$

That is, a tie-breaking rule always maps to the point that is closer to $v$,
and in case of a tie, picks exactly one of the two points. We say that a tie-
breaking rule $\tau$ is _directionally consistent_ if, for any fixed
$v\in[0,1]$, either $\tau$ always tie-breaks to the left of $v$ or always to
the right of $v$ (the choice of direction could depend on $v$). That is, for
any fixed $v\in[0,1]$, either $\tau(v,x,y)=x$ for all $x,y\in[0,1]$ such that
$x\leq v\leq y$ and $|v-x|=|v-y|$, or $\tau(v,x,y)=y$ for all $x,y\in[0,1]$
such that $x\leq v\leq y$ and $|v-x|=|v-y|$.

For any candidate $c_{i}\in\mathcal{C}$, its _Voronoi cell_ $V_{i}$ denotes
the set of all voter locations $v\in[0,1]$ whose favorite candidate is
$c_{i}$, i.e., $V_{i}\coloneqq\\{v\in[0,1]:\texttt{top}(v)=c_{i}\\}$. Notice
that the Voronoi cells $V_{1},\dots,V_{m}$ induce a partition of the line
segment $[0,1]$.

#### Proxies:

Our model also includes a finite set $\mathcal{P}$ of proxies whose role is to
vote on behalf of the voters. Specifically, each voter $v$ delegates its vote
to its _nearest proxy_ , denoted by
$p^{v}\coloneqq\arg\min_{p\in\mathcal{P}}|v-p|$. Each proxy $p\in\mathbb{R}$
then votes for its favorite candidate, denoted by $\texttt{top}(p)$, which is
defined as the candidate closest to it, i.e.,
$\texttt{top}(p)\coloneqq\arg\min_{c_{i}\in\mathcal{C}}|p-c_{i}|$. As before,
ties are broken according to a directionally consistent tie-breaking rule (see
Definition 1). We will often use the term _proxy arrangement_ to refer to a
set of proxies placed on the real line.

#### Representative proxy arrangements:

We will now formally define what it means for a proxy arrangement to be
_representative_. The definition is stated in terms of a parameter
$\theta\in[0,1]$ that corresponds to a distance threshold. We will find it
convenient to call two points $x,y\in[0,1]$ to be _$\theta$ -close_ if
$|x-y|\leq\theta$, and call them _$\theta$ -far_ otherwise.

Given any $\theta\in[0,1]$, we say that a proxy arrangement is _$\theta$
-representative_ if for _every_ voter location, the favorite candidate of the
voter is $\theta$-close to the favorite candidate of its closest proxy.222One
might ask whether, in place of an additive approximation in the definition of
$\theta$-representation, a multiplicative guarantee could be used instead. We
note that a multiplicative approximation would implicitly use different
“$\theta$” values for different voters, i.e., if a voter’s favorite candidate
is at position $z$, then its closest proxy’s favorite should be within
$[(1-\varepsilon)\cdot z,(1+\varepsilon)\cdot z]$. Thus, the voters whose
favorite candidate is far away from $x=0$ have a greater “slack” in their
representation (and are therefore loosely represented), whereas the voters
whose favorite candidates are closer to $x=0$ enjoy a stronger representation.
While this notion is mathematically well-defined, it does not seem as natural
as our additive notion since the representation guarantee is no longer uniform
for all voters.

######  Definition 2 ($\theta$-representative proxy arrangement).

An arrangement of proxies is _$\theta$ -representative_ if for any voter
$v\in[0,1]$, its favorite candidate is $\theta$-close to the favorite
candidate of its nearest proxy. That is, for every $v\in[0,1]$,
$|\texttt{top}(v)-\texttt{top}(p^{v})|\leq\theta$.

This property essentially says that for every voter, no matter where they may
be located, it must be that their preference is not too different from the
preference of their closest proxy. Therefore, the voter should feel reasonably
satisfied with the proxy arrangement, as their closest proxy (to whom they
yield the power of their vote) will be somewhat representative of their
interests. On the other hand, if an arrangement is not $\theta$-representative
for some large $\theta$, this means that there are collections of voters which
would be unhappy with this proxy arrangement, as the votes of the proxies
would heavily disagree with the preferences of the voters.

We will now define the central problem studied in this paper.

######  Definition 3 (Proxy Voting).

An instance of the Proxy Voting problem
$\mathcal{I}=\langle\mathcal{C},\theta\rangle$ is specified by a set of
candidates $\mathcal{C}$ in $[0,1]$ and a parameter $\theta\in(0,1)$. The goal
is to compute an arrangement of proxies that is _$\theta$ -representative_ for
every location $v\in[0,1]$.333We exclude the degenerate corner cases of
$\theta=0$ and $\theta=1$ from the definition. Indeed, if $\theta=0$, then it
is easy to see that an optimal proxy arrangement requires as many proxies as
candidates (realized by placing a proxy on each candidate). On the other hand,
$\theta=1$ involves placing a single proxy anywhere in $[0,1]$.

We once again stress that a $\theta$-representative proxy arrangement should
be representative of all possible sets of voters: When choosing appropriate
proxies to represent the populace, we do not have information about the voter
locations; we only know the candidate locations. No matter where the voters
are located, or how they change in the future, the proxies will still be
representative of their views.

It is worth pointing out that the assumption about the candidates and voters
lying inside $[0,1]$ is without loss of generality. Indeed, by assuming the
extreme candidates to be at $x=0$ and $x=1$, we are able to specify the
parameter $\theta$ in absolute terms. Otherwise, we would need to define the
distance threshold as “$\theta$ times the distance between the extreme
candidates”. The voters too, in principle, can be anywhere on the real line.
However, note that for any voter located (weakly) to the left of $x=0$, its
favorite candidate is at $x=0$. Furthermore, it can be shown that under an
optimal proxy arrangement, the favorite proxy of any voter to the left of
$x=0$ is, without loss of generality, also the favorite proxy of the voter
_at_ $x=0$ (in other words, the leftmost proxy bisector is weakly to the right
of $x=0$). Thus, $\theta$-representation for _any_ voter to the left of $x=0$
is subsumed by the same condition for the voter at $x=0$, and therefore, it
suffices to assume that there are no voters in $x<0$. A similar argument can
be made for voters to the right of $x=1$.

We will study two variants of Proxy Voting which we call the _restricted_ and
_unrestricted_ versions. Under the _restricted_ version of the problem, we
require that the set of proxies must be a subset of candidate locations, that
is, the proxies must lie on top of the candidates. In the _unrestricted_
version, the proxies can lie anywhere on the real line.

Note that the computational problem pertaining to Footnote 3 can be formalized
as a decision as well as an optimization problem. The decision version asks
whether, given an instance $\mathcal{I}$ and a natural number
$k\in\mathbb{N}$, there exists a $\theta$-representative proxy arrangement for
$\mathcal{I}$ consisting of at most $k$ proxies. The optimization version asks
whether, given an instance $\mathcal{I}$, the _optimal_
$\theta$-representative proxy arrangement for $\mathcal{I}$ can be computed in
polynomial time. An arrangement of $k$ proxies is _optimal_ for instance
$\mathcal{I}$ if there is no other arrangement of $k-1$ or fewer proxies that
is $\theta$-representative. We will write $\texttt{opt}(\mathcal{I})$ to
denote the number of proxies in any optimal $\theta$-representative
arrangement for the instance $\mathcal{I}$. To make the computational problem
meaningful, we will assume throughout that all candidate locations in
$\mathcal{C}$ and the parameter $\theta$ are rational.

### Basic Properties and Examples

Let us start by discussing some of the issues that arise when constructing
$\theta$-representative sets of proxies, and attempt to build intuition about
our techniques. First, consider the following lemma, which points out a
precise relationship between candidate bisectors and proxy bisectors.

######  Lemma 1.

Let $\mathcal{I}=\langle C,\theta\rangle$ denote an instance with a pair of
adjacent candidates $c_{i}$ and $c_{i+1}$ that are $\theta$-far. Let
$\mathcal{P}$ be any proxy arrangement such that none of the bisectors between
adjacent proxies in $\mathcal{P}$ coincides with the bisector between $c_{i}$
and $c_{i+1}$. Then, $\mathcal{P}$ is not $\theta$-representative for
$\mathcal{I}$.

###### Proof.

Let $p_{1},\dots,p_{k}$ denote the proxies in $\mathcal{P}$. Among all proxy
bisectors between adjacent proxies, let the one between $p_{j}$ and $p_{j+1}$
be closest to the candidate bisector between $c_{i}$ and $c_{i+1}$ (see Figure
1). Without loss of generality, we can assume that this proxy bisector is to
the right of the candidate bisector, i.e.,
$\frac{c_{i}+c_{i+1}}{2}<\frac{p_{j}+p_{j+1}}{2}$. Let
$d\coloneqq\min\\{\frac{p_{j}+p_{j+1}}{2},c_{i+1}\\}-\frac{c_{i}+c_{i+1}}{2}$
and observe that $d>0$.

$c_{i}$$c_{i+1}$$v^{R}$$v^{L}$$>\theta$ Figure 1: Failure of
$\theta$-representation when none of the proxy bisectors between adjacent
proxies coincides with the candidate bisector between $\theta$-far candidates.
The candidate bisector is shown as solid vertical line, and its closest proxy
bisector is shown as a dashed vertical line in red.

Consider a pair of voters
$v^{L}\in(\frac{c_{i}+c_{i+1}}{2}-d,\frac{c_{i}+c_{i+1}}{2})$ and
$v^{R}\in(\frac{c_{i}+c_{i+1}}{2},\frac{c_{i}+c_{i+1}}{2}+d)$. Notice that the
favorite candidates of $v^{L}$ and $v^{R}$ are $c_{i}$ and $c_{i+1}$,
respectively. Furthermore, since the closest proxy bisector is at least a
distance $d$ away from the candidate bisector, the two voters must have the
same closest proxy, i.e., $p^{v^{L}}=p^{v^{R}}=p_{j}$. Then, regardless of the
favorite candidate of $p_{j}$, $\theta$-representation must be violated for at
least one of $v^{L}$ or $v^{R}$. ❑

It is relevant to note that the implication in Lemma 1 holds under both
restricted and unrestricted positioning assumptions. Because of Lemma 1, it is
easy to see that attempting something trivial like placing proxies at equal
distances will not result in a $\theta$-representative arrangement, as shown
by 1 below. Essentially, the example uses the observation that the proxy
bisectors under an equidistant proxy arrangement can only occur in certain
fixed locations. Thus, by adversarially placing a pair of $\theta$-far
candidates in a way that their candidate bisector does not coincide with any
of the proxy bisectors, we can use Lemma 1 to demonstrate a violation of
$\theta$-representation. This further motivates the need for sophisticated
algorithms for computing proxy arrangements, such as those discussed in
upcoming sections.

######  Example 1 (Evenly spaced proxies may not be $\theta$-representative).

Suppose we are given some $\theta\in(0,1)$ and a budget of $k\in\mathbb{N}$
proxies. We will construct an instance where evenly spacing these $k$ proxies,
i.e., placing the proxies at $\frac{\ell}{k-1}$ for every
$\ell\in\\{0,1,\dots,k-1\\}$, fails to be $\theta$-representative (we will
assume, without loss of generality, that $k\geq 2$). Notice that the bisectors
between adjacent proxies are located at $\frac{2\ell-1}{2(k-1)}$ for every
$\ell\in[k-1]$.

Consider a sufficiently small $\varepsilon>0$ such that
$[\theta,\theta+\varepsilon]\subseteq[\frac{\ell-1}{k-1},\frac{\ell}{k-1}]$
for some $\ell\in[k-1]$. Note that such a choice of $\varepsilon$ must exist
since $\theta\in(0,1)$. Pick a rational point
$x\in(\theta,\theta+\varepsilon)\setminus\cup_{i\in[\ell]}\\{\frac{2i-1}{k-1}\\}$.

Consider an instance with three candidates $c_{1}$, $c_{2}$, and $c_{3}$ that
are placed at $0$, $x$, and $1$, respectively. Notice that $c_{1}$ and $c_{2}$
are $\theta$-far, and that the bisector between $c_{1}$ and $c_{2}$, which is
located at $x/2$, does not coincide with any proxy bisector between adjacent
proxies. Therefore, by Lemma 1, the evenly spaced proxy arrangement fails to
be $\theta$-representative. ❑

We will now describe our results for restricted (Section 4) and unrestricted
positioning of proxies (Section 5).

##  4 Restricted Positioning of Proxies

This section provides an algorithm for computing an optimal proxy arrangement,
followed by upper and lower bounds on the number of proxies needed to be
$\theta$-representative.

###  4.1 Algorithm for Computing Optimal Number of Restricted Proxies

Our first result for restricted positioning (Theorem 1) shows that a
$\theta$-representative arrangement with the smallest number of proxies can be
computed in polynomial time. While the details are somewhat complex, the proof
is via an essentially straightforward dynamic programming algorithm, and is
presented in Section 8 in the appendix.

######  Theorem 1 (Optimal proxy arrangement under restricted positioning).

There is a polynomial-time algorithm that, given any instance
$\langle\mathcal{C},\theta\rangle$ of Proxy Voting as input, terminates in
polynomial time and returns an optimal $\theta$-representative proxy
arrangement satisfying restricted positioning.

###  4.2 Upper and Lower Bounds for Restricted Positioning of Proxies

Although the optimum number of proxies can be computed efficiently, these
algorithms do not provide any insight into _how many_ proxies are actually
necessary in order to be $\theta$-representative for any given set of
candidates and any set of voters. Because of this, we now prove upper and
lower bounds on the number of proxies needed to achieve
$\theta$-representation.

######  Theorem 2 (Upper bound under restricted positioning).

Given any instance $\langle\mathcal{C},\theta\rangle$ of Proxy Voting, there
exists a $\theta$-representative proxy arrangement satisfying restricted
positioning that consists of at most $2(\frac{1}{\theta}-1)$ proxies if
$\frac{1}{\theta}\in\mathbb{N}$, and at most $2\lfloor\frac{1}{\theta}\rfloor$
proxies otherwise. Furthermore, such an arrangement can be computed in
polynomial time.

_Proof Sketch._ The detailed proof of Theorem 2 is presented in Section 9 in
the appendix. Here, we will describe the main steps in our algorithm by means
of the example shown in Figure 2(a).

$c_{1}$$c_{2}$$c_{3}$$c_{4}$$c_{5}$$\theta$$\varepsilon$$2\theta$$\theta+\varepsilon$
(a) An instance of Proxy Voting.

$c_{1}$$c_{2}$$c_{3}$$c_{4}$$c_{5}$ (b) The proxy bisectors computed by the
algorithm are shown as dashed red lines, and the reference candidates are
highlighted in blue. The locations of proxies are shown as solid red circles.

Figure 2: Illustrating the execution of the algorithm in Theorem 2 on a toy
example.

To compute the desired proxy arrangement, our algorithm (see Algorithm 1 in
the appendix) computes a set of _proxy bisectors_ between adjacent proxies,
according to the following strategy. Starting from the leftmost candidate as
the _reference_ , the bisector between the furthest $\theta$-close and the
closest $\theta$-far candidates from the reference on the right is chosen as
the first proxy bisector. (In Figure 2(b), this is the bisector between
$c_{2}$ and $c_{3}$.) In the next iteration, the candidate immediately to the
right of the previous proxy bisector is chosen as the new reference in order
to compute the next proxy bisector. (Thus, when $c_{3}$ is the reference in
the next iteration, the furthest $\theta$-close candidate from $c_{3}$ on the
right is $c_{3}$ itself, and $c_{4}$ is the closest $\theta$-far candidate.
Therefore, the proxy bisector is chosen as the candidate bisector between
$c_{3}$ and $c_{4}$.) This process repeats until the rightmost candidate
$c_{m}$ either becomes a reference or is $\theta$-close to one.

Since, by construction, all proxy bisectors coincide with candidate bisectors,
the desired proxy arrangement is realized by placing proxies on the
equidistant candidates next to each proxy bisector. It is easy to show that
the number of proxy bisectors is at most $\lfloor\frac{1}{\theta}\rfloor$, and
therefore the number of proxies is at most $2\lfloor\frac{1}{\theta}\rfloor$.
The $\theta$-representation of this proxy arrangement follows from the fact
that all candidates between consecutive proxy bisectors are $\theta$-close. ❑

1 shows that the upper bound derived in Theorem 2 is tight.

######  Proposition 1 (Lower bound under restricted positioning).

Given any $\theta\in(0,1)$, there exists an instance for which any
$\theta$-representative proxy arrangement under restricted positioning
requires at least $2(\frac{1}{\theta}-1)$ proxies if
$\frac{1}{\theta}\in\mathbb{N}$, and $2\lfloor\frac{1}{\theta}\rfloor$ proxies
otherwise.

###### Proof.

Let $p\in\mathbb{N}$ denote the unique positive integer such that
$\frac{1}{p}\leq\theta<\frac{1}{p-1}$. Observe that $p-1$ equals
$\frac{1}{\theta}-1$ when $\frac{1}{\theta}\in\mathbb{N}$, and equals
$\lfloor\frac{1}{\theta}\rfloor$ otherwise. Therefore, it suffices to show
that any $\theta$-representative arrangement requires $2p-2$ proxies.

Our construction of the lower bound instance will depend on whether $p$ is
even or odd. Specifically, let
$\varepsilon\coloneqq\frac{1-(p-1)\theta}{5(p-1)/2}$ (if $p$ is odd) or
$\varepsilon\coloneqq\frac{1-(p-1)\theta}{(5p/2-3)}$ (if $p$ is even), and
observe that $\varepsilon>0$ in both cases. The distinction between even and
odd cases is made in order to ensure that the distance between the extreme
candidates is equal to $1$.

$c_{1}$$c_{2}$$c_{3}$$c_{4}$$c_{5}$$c_{6}$$c_{7}$$\theta+\varepsilon$$\varepsilon$$\theta+\varepsilon$$2\varepsilon$$\theta+\varepsilon$$\varepsilon$

$c_{1}$$c_{2}$$c_{3}$$c_{4}$$c_{5}$$c_{6}$$c_{7}$$c_{8}$$c_{9}$$\theta+\varepsilon$$\varepsilon$$\theta+\varepsilon$$2\varepsilon$$\theta+\varepsilon$$\varepsilon$$\theta+\varepsilon$$2\varepsilon$

Figure 3: Lower bound instance in 1 when $\frac{1}{4}\leq\theta<\frac{1}{3}$
(top) and $\frac{1}{5}\leq\theta<\frac{1}{4}$ (bottom).

The instance consists of the candidate $c_{1}$ on the left, followed by a
sequence of pairs of candidates $\\{c_{2i},c_{2i+1}\\}$ for $i\in\mathbb{N}$
such that each pair is at a distance of $\theta+\varepsilon$ from the
preceding pair, and the gap between the candidates in each pair alternates
between $\varepsilon$ and $2\varepsilon$ (see Figure 3 for an example). In
other words, the sequence of distances between adjacent pair of candidates
from left to right is given by
$\theta+\varepsilon,\varepsilon,\theta+\varepsilon,2\varepsilon,\theta+\varepsilon,\varepsilon$
and so on. The rightmost candidate is $c_{2p-1}$. It is easy to see that all
candidate locations are rational, and that the distance between the extreme
candidates is equal to $1$.

The fact that the candidate pairs $\\{c_{1},c_{2}\\}$, $\\{c_{3},c_{4}\\}$,
$\\{c_{5},c_{6}\\}$, and so on are each $\theta$-far necessitates that for
every candidate bisector between these pairs, there must exist a proxy
bisector between adjacent proxies that coincides with it (contrapositive of
Lemma 1). Furthermore, due to the alternating gaps property, any
$\theta$-representative proxy arrangement is required to place proxies on
every candidate except for the last candidate $c_{2p-1}$ (see Section 10 in
the appendix for a detailed argument). This implies that any
$\theta$-representative proxy arrangement for the above instance requires at
least $2p-2$ proxies. ❑

##  5 Unrestricted Positioning of Proxies

Let us now turn our attention to the _unrestricted_ setting wherein the
proxies can be placed anywhere on the real line. Clearly, any feasible proxy
arrangement in the restricted model is also feasible under the unrestricted
model. Therefore, the optimal number of proxies under the latter setting is at
most that under the former; in fact, Figure 4 shows that the separation
between the two models can be strict.

######  Example 2 (Unrestricted positioning uses fewer proxies than
restricted).

Fix $\theta=\frac{1}{3}$ and let $\varepsilon>0$ be sufficiently small.
Consider the instance shown in Figure 4 consisting of four candidates
$c_{1}=0$, $c_{2}=\frac{1}{3}+\varepsilon$, $c_{3}=\frac{2}{3}-\varepsilon$,
and $c_{4}=1$. Notice that the adjacent candidate pairs $\\{c_{1},c_{2}\\}$
and $\\{c_{3},c_{4}\\}$ are $\theta$-far. Thus, by the contrapositive of Lemma
1, any $\theta$-representative proxy arrangement must have bisectors between
adjacent proxies that coincide with the candidate bisectors between these
pairs.

$c_{1}$$c_{2}$$c_{3}$$c_{4}$$\theta+\varepsilon$$\theta-2\varepsilon$$\theta+\varepsilon$

$c_{1}$$c_{2}$$c_{3}$$c_{4}$$\theta+\varepsilon$$\theta-2\varepsilon$$\theta+\varepsilon$

Figure 4: Unrestricted positioning (bottom) requires strictly fewer proxies
than restricted positioning (top). The proxies in each case are shown as solid
red circles.

Under restricted positioning, a $\theta$-representative proxy arrangement must
place proxies on all candidates, using four proxies in total (see top figure
in Figure 4). By contrast, under unrestricted positioning, there exists a
feasible proxy arrangement that only uses three proxies, namely
$p_{1}=-\frac{1}{6}+\varepsilon$, $p_{2}=0.5$, and
$p_{3}=\frac{7}{6}+\varepsilon$ (see bottom figure in Figure 4).

Notice that the saving in the number of proxies in the unrestricted case was
achieved by “merging” the second and the third proxies. This, in turn, forces
the first and the fourth proxies to fall outside of $[0,1]$, thus highlighting
the importance of allowing the proxies to be anywhere on the real line. ❑

###  5.1 Algorithm for Computing Optimal Number of Unrestricted Proxies

Let us now state our main result for unrestricted proxies.

######  Theorem 3 (Optimal proxy arrangement under unrestricted positioning).

There is a polynomial-time algorithm that, given any instance
$\langle\mathcal{C},\theta\rangle$ of Proxy Voting as input, terminates in
polynomial time and returns an optimal $\theta$-representative proxy
arrangement.

The proof of Theorem 3 is technically the most involved part of the paper and
is presented in Section 11 in the appendix. Here we will outline a brief
sketch of the proof.

_Proof Sketch._ For any fixed $k\in[m]$, our algorithm decides whether there
exists a feasible (i.e., $\theta$-representative) arrangement of $k$ proxies
for the given instance. The smallest $k$ with a positive answer is returned as
the output.

Given a proxy arrangement $\mathcal{P}=\\{p_{1},\dots,p_{k}\\}$ (where
$p_{1}<p_{2}<\dots<p_{k}$), let us define the Voronoi cell $W_{j}$ of proxy
$p_{j}$ as the set of all locations of voters whose closest proxy is $p_{j}$,
i.e., $W_{j}\coloneqq\\{v\in[0,1]:|v-p_{j}|\leq|v-p_{\ell}|\text{ for any
}\ell\neq j\\}$, where ties are broken according to a directionally-consistent
tie-breaking rule (Definition 1). Notice that $v\in W_{j}$ if and only if
$p_{j}=p^{v}$.

At a high level, the algorithm uses dynamic programming to compute the set of
feasible locations (or the _feasibility set_) of the proxy $p_{j+1}$ using the
feasibility set of the preceding proxy $p_{j}$. It maintains the property that
for each point $s$ in the feasibility set of proxy $p_{j+1}$, there exists
some point $s^{\prime}<s$ in the feasibility set of proxy $p_{j}$ such that
$\theta$-representation is satisfied for all voters in $W_{j}$ (see Lemma 2 in
the appendix for a formal characterization result). Such a pair of locations
$\\{s^{\prime},s\\}$ is said to be _mutually feasible_.

To begin with, the feasibility set $F^{1}$ of the leftmost proxy $p_{1}$ is
initialized as the union of the Voronoi cells of all candidates that are
$\theta$-close to the leftmost candidate $c_{1}$, along with the region
$(-\infty,0)$.444Recall from Figure 4 that proxies can lie outside $[0,1]$ in
an optimal arrangement under unrestricted positioning. This corresponds to the
set of all positions of the leftmost proxy such that $\theta$-representation
is satisfied for the leftmost voter.

The feasibility set $F^{j+1}$ of the proxy $p_{j+1}$ is computed using $F^{j}$
as follows: Consider the restriction of $F^{j}$ to the Voronoi cell of
candidate $c_{h}$ (denoted by $F^{j,h}$), as illustrated by the interval
$[x,y]$ in Figure 5 (thus, $\texttt{top}(p_{j})=c_{h}$). We will use $F^{j,h}$
to compute $F^{j+1,i}$, which is the restriction of $F^{j+1}$ to the Voronoi
cell of candidate $c_{i}$.

Let $\makebox[0.0pt]{$\phantom{b}\overline{\phantom{b}}$}b_{h}$ denote the
candidate bisector between the furthest $\theta$-close and closest
$\theta$-far candidates to the right of $c_{h}$. Similarly, let
$\makebox[0.0pt]{$\phantom{b}\underline{\phantom{b}}$}b_{i}$ denote the
candidate bisector between the furthest $\theta$-close and closest
$\theta$-far candidates to the left of $c_{i}$.

By our characterization result, it follows that any point $z\in F^{j+1,i}$
that is mutually feasible with some point in $F^{j,h}$ must be (weakly) to the
left of the mirror image of the point $x$ about the bisector
$\makebox[0.0pt]{$\phantom{b}\overline{\phantom{b}}$}b_{h}$ (namely,
$x^{\prime}$). This is because the proxy bisector between $p_{j}$ and
$p_{j+1}$ has to be (weakly) to the left of
$\makebox[0.0pt]{$\phantom{b}\overline{\phantom{b}}$}b_{h}$. Similarly, $z$
must be (weakly) to the right of the mirror image of point $y$ about the
bisector $\makebox[0.0pt]{$\phantom{b}\underline{\phantom{b}}$}b_{i}$ (namely,
$y^{\prime}$). The contribution of the set $[x,y]$ to $F^{j+1,i}$ is given by
$V_{i}\cap[y^{\prime},x^{\prime}]$. In general, the restriction $F^{j,h}$
could comprise of several disjoint intervals. In Section 11 in the appendix,
we describe how the feasibility set $F^{j+1}$ can nevertheless be efficiently
computed.

$c_{h}$$c_{i}$$\makebox[0.0pt]{$\phantom{b}\underline{\phantom{b}}$}b_{i}$$\makebox[0.0pt]{$\phantom{b}\overline{\phantom{b}}$}b_{h}$$x$$y$$y^{\prime}$$x^{\prime}$$\theta$$\theta$
Figure 5:

Having computed the feasibility set $F^{k}$ of the rightmost proxy, the
algorithm now checks whether it overlaps with the union of the Voronoi cells
of candidates that are $\theta$-close to the rightmost candidate $c_{m}$ along
with the region $(1,\infty)$. If yes, then there exists a feasible location of
the proxy $p_{k}$ that is $\theta$-representative for the rightmost voter. By
the aforementioned property, there must exist a feasible location $p_{k-1}$ of
the previous proxy such that $p_{k-1}$ and $p_{k}$ are mutually feasible, thus
implying $\theta$-representation for the voters in $W_{k-1}$. Similarly, there
must exist a feasible location of the proxy $p_{k-2}$ that is mutually
feasible with $p_{k-1}$, and so on. Continuing backwards in this manner, we
obtain a set of proxy locations $p_{1},\dots,p_{k}$ wherein the adjacent pairs
are mutually feasible, which immediately implies $\theta$-representation. On
the other hand, the absence of an overlap certifies that with $k$ proxies,
there is no $\theta$-representative proxy arrangement in the given instance. ❑

###  5.2 Upper and Lower Bounds for Unrestricted Positioning of Proxies

To compute an upper bound on the number of proxies, we will show that an
algorithm similar to that for the restricted setting turns out to be useful.
We will defer the detailed description of our algorithm and its formal
analysis to Section 12 in the appendix, and instead revisit the example from
Figure 2 considered previously in the restricted case.

Our algorithm proceeds in two phases. The first phase is identical to that of
the algorithm for the restricted case (Theorem 2), and returns a set of proxy
bisectors. In the second phase, the algorithm starts with a proxy arrangement
that is consistent with the proxy bisectors computed in Phase 1 by placing a
pair of equidistant proxies on either side of each bisector. This results in
twice as many proxies as there are bisectors. To shrink this number down to
$3/2$ times the number of bisectors, the algorithm utilizes the additional
flexibility of the unrestricted setting via an “expand and merge” step.
Specifically, the algorithm pulls all the proxies away from their bisectors at
equal speeds until there is a “collision” event in some interval (recall that
an interval is the area between adjacent proxy bisectors). At this point, the
two proxies in that interval can be merged into a single proxy, and the
locations of their ‘partner’ proxies are frozen (see Figure 6). This process
is repeated until all proxies are frozen.

$c_{1}$$c_{2}$$c_{3}$$c_{4}$$c_{5}$CollisionCollision Figure 6: Illustrating
the execution of the algorithm in Theorem 4 on a toy example. The initial and
the final proxy locations are shown as empty and solid red circles,
respectively.

By construction, all candidates within each interval are $\theta$-close.
Furthermore, since each voter is in the same interval as its closest proxy,
$\theta$-representation is satisfied for all voters. By an analysis similar to
that in Theorem 2, it follows that the number of proxy bisectors is at most
$\lceil\frac{1}{\theta}\rceil$. The expand-and-merge step ensures that no two
consecutive intervals can have two proxies each. This readily implies the
desired bound of $\frac{3}{2}\lceil\frac{1}{\theta}\rceil$ for the number of
proxies.

######  Theorem 4 (Upper bound under unrestricted positioning).

Given any instance $\langle\mathcal{C},\theta\rangle$ of Proxy Voting as
input, there exists a $\theta$-representative arrangement consisting of at
most $\frac{3}{2}\lceil\frac{1}{\theta}\rceil$ proxies. Furthermore, such an
arrangement can be computed in polynomial time.

Notice that Theorem 4 can be used to obtain upper bounds for the dual problem
to Proxy Voting wherein the input consists of a proxy budget $k$ and the goal
is to provide an upper bound on $\theta$. Indeed, given as input a budget of
$k>1$ proxies, we can invoke our algorithm with
$\theta=1/\lfloor\frac{2k}{3}\rfloor$. Then, by Theorem 4, we know that the
proxy arrangement returned by the algorithm is
$\left(1/\lfloor\frac{2k}{3}\rfloor\right)$-representative and uses at most
$\frac{3}{2}\lceil\frac{1}{\theta}\rceil\leq k$ proxies, which is within the
given budget. Corollary 1 formalizes this observation.

######  Corollary 1 (Upper bound on $\theta$).

There is a polynomial-time algorithm that, given any positive integer
$k\in\mathbb{N}$ as input, returns an arrangement of at most $k$ proxies that
is $\left(1/\lfloor\frac{2k}{3}\rfloor\right)$-representative.

Next, we will show that the dependence on $\theta$ in the upper bound cannot
be improved.

######  Proposition 2 (Lower bound under unrestricted positioning).

Given any $\theta\in(0,1)$, there exists an instance such that any
$\theta$-representative proxy arrangement requires at least
$\lceil\frac{1}{\theta}\rceil$ proxies.

###### Proof.

Define $\theta^{\prime}\in(0,1)$ as follows:

$\theta^{\prime}\coloneqq\begin{cases}\frac{1}{p-1},&\text{if
}\theta=\frac{1}{p}\text{ for some positive integer }p\\\
\frac{1}{p},&\text{if }\frac{1}{p+1}<\theta<\frac{1}{p}\text{ for some
positive integer }p.\end{cases}$

Observe that $\theta^{\prime}>\theta$. Consider an instance where the
candidates are evenly spaced at a distance of $\theta^{\prime}$, as shown in
Figure 7. Notice that the total number of candidates is
$m=\frac{1}{\theta^{\prime}}+1=\lceil\frac{1}{\theta}\rceil$.

$c_{1}$$c_{2}$$c_{3}$$c_{m-1}$$c_{m}$…$\theta^{\prime}$$\theta^{\prime}$$\theta^{\prime}$
Figure 7: Lower bound on the number of proxies under unrestricted positioning
(2)

Since any pair of adjacent candidates are $\theta$-far, it must be that each
candidate is the favorite candidate of some proxy. Indeed, in any arrangement
with fewer than $m$ proxies, there must exist a candidate, say $c$, that is
not the favorite candidate of any proxy. Consider a voter $v$ that is located
at $c$. The distance between the favorite candidate of $v$ and that of $v$’s
nearest proxy must then be strictly greater than $\theta$, which violates
$\theta$-representation. Thus, $m$ proxies are necessary, which gives the
desired bound. ❑

##  6 Representative Election Outcomes

So far, we have focused on achieving $\theta$-representation for each
individual voter (i.e., in the “input” space). A natural question is whether a
similar guarantee can be achieved in the “outcome” space as well.
Specifically, when is it that the outcome under direct voting (where the
preference profile consists of voter’s preferences over the candidates) is
close to the outcome under proxy voting (where each voter’s preference is
substituted by that of its closest proxy). This is formally defined as
follows.

######  Definition 4.

Let $P\in[0,1]^{n}$ denote a preference profile consisting of the votes of the
$n$ voters, and let $Q\coloneqq\\{p^{v}:v\in P\\}$ be the preference profile
derived from $P$ by replacing the vote of each voter $v$ by that of its
closest proxy $p^{v}$ (note that $Q$ can be a multiset). Then, an arrangement
of proxies is said to be _$\theta$ -representative under a voting rule
$r:\mathbb{R}^{n}\rightarrow\mathcal{C}$_ if, for any preference profile
$P\in[0,1]^{n}$, the candidate $r(P)$ is $\theta$-close to the candidate
$r(Q)$. Here, $r(P)$ and $r(Q)$ are the outcomes under direct and proxy
voting, respectively.

It turns out that $\theta$-representation of a proxy arrangement implies
$\theta$-representation under any strict-Condorcet rule with consistent tie-
breaking (i.e., any strict-Condorcet rule which must choose a weak Condorcet
winner as the winner, and in case there is more than one weak Condorcet
winner, the leftmost (or, the rightmost) one must be chosen).

######  Proposition 3.

Let $r$ be a strict-Condorcet rule with consistent tie-breaking. If an
arrangement of proxies is $\theta$-representative, then it is
$\theta$-representative under the rule $r$.

In light of Proposition 3, all $\theta$-representation results proved in this
paper (see Table 1) naturally extend to $\theta$-representation under strict-
Condorcet rules. The proof of 3 is presented in Section 13 in the appendix.

##  7 Concluding Remarks

In this paper, we gave efficient algorithms for computing optimal sets of
$\theta$-representative proxies, as well as proved upper and lower bounds on
the number of proxies needed to achieve this property. Unlike in most related
work, our proxy arrangements do not depend on the voter locations, and will
remain representative for any set of voters. In fact, all our results hold
(although some of the proofs become far more complex) even with additional
requirements on the proxy arrangement, such as requiring that for every voter
$v\in[0,1]$, its closest proxy is within a distance $\theta$, in addition to
them being $\theta$-representative.

Many interesting open problems remain, however, beginning with closing the gap
between the upper and lower bounds for the number of proxies under
unrestricted positioning, and analysing the ability to form
$\theta$-representative proxies in more general metric spaces. More generally,
it would be interesting to expand the scope of $\theta$-representation from
“representing the top candidate well” to “representing the top-$k$ candidates
well”, or to more general fairness properties.

## Acknowledgments

EA acknowledges support from NSF awards CCF-1527497 and CCF-2006286. RV
acknowledges support from ONR#N00014-171-2621 while he was affiliated with
Rensselaer Polytechnic Institute, and is currently supported by project no.
RTI4001 of the Department of Atomic Energy, Government of India. Part of this
work was done while RV was supported by the Prof. R Narasimhan postdoctoral
award. Research done in part while ZF was on research leave at Rensselaer
Polytechnic Institute. We thank the anonymous reviewers for their very helpful
comments and suggestions.

## References

  * Abramowitz and Mattei (2019) Ben Abramowitz and Nicholas Mattei.  Flexible Representative Democracy: An Introduction with Binary Issues.  In Proceedings of the 28th International Joint Conference on Artificial Intelligence, pages 3–10, August 2019.
  * Abramowitz et al. (2019) Ben Abramowitz, Elliot Anshelevich, and Wennan Zhu.  Awareness of Voter Passion Greatly Improves the Distortion of Metric Social Choice.  In Proceedings of the 15th International Conference on Web and Internet Economics, pages 3–16, December 2019.
  * Alger (2006) Dan Alger.  Voting by Proxy.  Public Choice, 126(1-2):1–26, 2006.
  * Anshelevich et al. (2018) Elliot Anshelevich, Onkar Bhardwaj, Edith Elkind, John Postl, and Piotr Skowron.  Approximating Optimal Social Choice under Metric Preferences.  Artificial Intelligence, 264:27–51, 2018.
  * Black (1948) Duncan Black.  On the Rationale of Group Decision-Making.  Journal of Political Economy, 56(1):23–34, 1948.
  * Brill and Talmon (2018) Markus Brill and Nimrod Talmon.  Pairwise Liquid Democracy.  In Proceedings of the 27th International Joint Conference on Artificial Intelligence, pages 137–143, July 2018.
  * Cohensius et al. (2017) Gal Cohensius, Shie Mannor, Reshef Meir, Eli Meirom, and Ariel Orda.  Proxy Voting for Better Outcomes.  In Proceedings of the 16th Conference on Autonomous Agents and Multiagent Systems, pages 858–866, May 2017.
  * Congleton (2002) Roger Congleton.  The Median Voter Model.  In Charles Rowley and Friedrich Schneider, editors, The Encyclopedia of Public Choice. Kluwer Academic Press, 2002.
  * Feldman et al. (2020) Michal Feldman, Yishay Mansour, Noam Nisan, Sigal Oren, and Moshe Tennenholtz.  Designing Committees for Mitigating Biases.  In Proceedings of the Thirty-Fourth AAAI Conference on Artificial Intelligence, pages 1942–1949, 2020.
  * Goel et al. (2017) Ashish Goel, Anilesh Kollagunta Krishnaswamy, and Kamesh Munagala.  Metric Distortion of Social Choice Rules: Lower Bounds and Fairness Properties.  In Proceedings of the 2017 ACM Conference on Economics and Computation, pages 287–304, June 2017.
  * Gölz et al. (2018) Paul Gölz, Anson Kahng, Simon Mackenzie, and Ariel D. Procaccia.  The Fluid Mechanics of Liquid Democracy.  In Proceedings of the 14th International Conference on Web and Internet Economics, pages 188–202, December 2018.
  * Green-Armytage (2015) James Green-Armytage.  Direct Voting and Proxy Voting.  Constitutional Political Economy, 26(2):190–220, 2015.
  * Hassin and Tamir (1991) Refael Hassin and Arie Tamir.  Improved Complexity Bounds for Location Problems on the Real Line.  Operations Research Letters, 10(7):395–402, 1991.
  * Kahng et al. (2018) Anson Kahng, Simon Mackenzie, and Ariel Procaccia.  Liquid Democracy: An Algorithmic Perspective.  In Proceedings of the 32nd AAAI Conference on Artificial Intelligence, pages 1095–1102, February 2018.
  * Kempe (2020) David Kempe.  Communication, Distortion, and Randomness in Metric Voting.  In Proceedings of the 34th AAAI Conference on Artificial Intelligence, pages 2087–2094, February 2020.
  * Magdon-Ismail and Xia (2018) Malik Magdon-Ismail and Lirong Xia.  A Mathematical Model For Optimal Decisions In A Representative Democracy.  In Advances in Neural Information Processing Systems, pages 4702–4711, 2018.
  * Meir et al. (2020) Reshef Meir, Fedor Sandomirskiy, and Moshe Tennenholtz.  Representatitve Committees of Peers.  Technical Report arXiv:2006.07837 [cs.GT], arXiv.org, June 2020.
  * Mirrlees (1971) James Mirrlees.  An Exploration in the Theory of Optimum Income Taxation.  The Review of Economic Studies, 38(2):175–208, 1971.
  * Pivato and Soh (2020) Marcus Pivato and Arnold Soh.  Weighted Representative Democracy.  Journal of Mathematical Economics, 88:52–63, 2020.
  * Procaccia and Rosenschein (2006) Ariel Procaccia and Jeffrey Rosenschein.  The Distortion of Cardinal Preferences in Voting.  In Proceedings of the 10th International Workshop on Cooperative Information Agents, pages 317–331, September 2006.
  * Schofield (2008) Norman Schofield.  The Spatial Model of Politics.  Number 95 in Routledge Frontiers of Political Economy. Routledge, New York, 2008.
  * Skowron (2015) Piotr Skowron.  What Do We Elect Committees For? A Voting Committee Model for Multi-Winner Rules.  Proceedings of the 24th International Joint Conference on Artificial Intelligence, page 1141—1147, July 2015.

Appendix

##  8 Proof of Theorem 1

See 1

###### Proof.

In order to compute the optimal proxy arrangement, it suffices to efficiently
determine whether, for any fixed $k\in[m]$, there exists an arrangement of $k$
proxies satisfying the desired properties (and if the answer is YES, then
return such an arrangement).

Our algorithm relies on the following structural observation: Consider a proxy
arrangement $\mathcal{P}$ consisting of $k$ proxies $p_{1},\dots,p_{k}$ such
that the rightmost proxy $p_{k}$ is placed at the candidate location $c_{j}$.
Then, $\mathcal{P}$ satisfies the desired properties (i.e.,
$\theta$-representation and restricted positioning) if and only if the
following conditions hold:

  1. 1.

$\mathcal{P}$ satisfies the desired properties (i.e., $\theta$-representation
and restricted positioning) with respect to the subinstance
$\langle\\{c_{1},c_{2},\dots,c_{j}\\},\theta\rangle$, and

  2. 2.

$c_{j}\in\mathcal{C}_{\theta}$, where
$\mathcal{C}_{\theta}\coloneqq\\{c_{i}\in\mathcal{C}:|c_{i}-c_{m}|\leq\theta\\}$
is the set of candidates that are $\theta$-close to the rightmost candidate
$c_{m}$.

Condition 1 specifies the feasibility requirement for $\mathcal{P}$ with
respect to the subinstance on the left side of the proxy $p_{k}$, while
Condition 2 encodes a similar restriction for the right side. Indeed, for an
extreme voter located at $v=c_{m}$, its favorite candidate is
$\texttt{top}(v)=c_{m}$, and the favorite candidate of its closest proxy is
$\texttt{top}(p^{v})=c_{j}$. Therefore, $\theta$-representation for voter $v$
is equivalent to Condition 2. Furthermore, since there are no proxies between
$c_{j}$ and $c_{m}$, the aforementioned conditions also imply
$\theta$-representation for all intermediate voters $v\in[c_{j},c_{m}]$.

It is easy to see that Condition 2 can be efficiently checked (recall that all
candidate locations and the parameter $\theta$ are rational). Therefore, it
suffices to establish that Condition 1 can also be decided in polynomial time.
To this end, we will provide an algorithm for determining, for every $j\in[m]$
and every $k\in[m]$, whether there exists a feasible proxy arrangement that
uses _exactly_ $k$ proxies and under which the rightmost proxy coincides with
the candidate $c_{j}$.

We will present a dynamic programming algorithm to solve this problem. The
algorithm computes a binary table $T$ with $m$ rows and $m$ columns, where the
entry $T(j,k)$ equals $1$ if there exists a $\theta$-representative proxy
arrangement for the subinstance
$\langle\\{c_{1},c_{2},\dots,c_{j}\\},\theta\rangle$ that uses exactly $k$
proxies, say $p_{1},\dots,p_{k}$, such that (a) the proxy locations are a
subset of the candidate locations (i.e.,
$\\{p_{1},\dots,p_{k}\\}\subseteq\\{c_{1},c_{2},\dots,c_{j}\\}$), and (b) the
rightmost proxy $p_{k}$ is placed on the rightmost candidate $c_{j}$ for the
subinstance.

To compute the table $T$, the algorithm starts by setting the diagonal entries
$T(j,j)=1$ for all $j\in[m]$ since $j$ proxies suffice for a subinstance with
$j$ candidates. In addition, the upper-triangular entries are set to $0$ (i.e,
$T(j,k)=0$ whenever $k>j$) due to insufficient candidate locations for placing
$k$ distinct proxies. When $k<j$, we set $T(j,k)=1$ if the following two
conditions hold:

  1. (a)

there exists $i<j$ such that $T(i,k-1)=1$, and

  2. (b)

for all $v\in[c_{i},c_{j}]$,
$|\texttt{top}(v)-\texttt{top}(p^{v})|\leq\theta$;

otherwise we set $T(j,k)=0$.

Condition (a) ensures that there is a subinstance $\langle
c_{1},\dots,c_{i}\rangle$ that admits a feasible proxy arrangement with $k-1$
proxies such that the proxy $p_{k-1}$ is placed at $c_{i}$, while condition
(b) ensures $\theta$-representation for the voters that lie between $c_{i}$
and $c_{j}$.

It is easy to see that condition (a) can be efficiently checked. To decide
condition (b), the algorithm checks whether the proxy bisector between
$p_{k-1}$ and $p_{k}$ coincides with a bisector between some pair of adjacent
candidates.

  1. (i)

If yes, then let $c_{\ell}$ and $c_{\ell+1}$ denote the adjacent candidates
such that $\frac{c_{\ell}+c_{\ell+1}}{2}=\frac{p_{k}+p_{k-1}}{2}$. Then, the
algorithm returns YES if $|c_{\ell}-c_{i}|\leq\theta$ and
$|c_{\ell+1}-c_{j}|\leq\theta$, otherwise it returns NO.

  2. (ii)

Otherwise, the algorithm checks whether the favorite candidate of the voters
located on either side of the proxy bisector is $\theta$-close to both $c_{i}$
and $c_{j}$. Specifically, let $\delta$ denote the smallest positive gap
between any two candidate bisectors between not-necessarily-adjacent
candidates (notice that such a $\delta>0$ must exist), and let
$\varepsilon=\delta/3$. Then, the algorithm considers the voters
$v^{L}\coloneqq\frac{p_{k-1}+p_{k}}{2}-\varepsilon$ and
$v^{R}\coloneqq\frac{p_{k-1}+p_{k}}{2}+\varepsilon$, and checks whether
$|\texttt{top}(v^{L})-\texttt{top}(p^{v^{L}})|\leq\theta$ and
$|\texttt{top}(v^{R})-\texttt{top}(p^{v^{R}})|\leq\theta$, where $p^{v^{L}}$
and $p^{v^{R}}$ denote the proxies closest to $v^{L}$ and $v^{R}$,
respectively. If both of these conditions are true, then the algorithm decides
YES for condition (b), otherwise it decides NO.

The reasoning behind the step (i) is the following: When $p_{k-1}=c_{i}$ and
$p_{k}=c_{j}$, the proxy bisector between $p_{k-1}$ and $p_{k}$ coincides with
the candidate bisector between $c_{i}$ and $c_{j}$ (note that $c_{i}$ and
$c_{j}$ may not be adjacent). Then, for any voter $v\in[c_{i},c_{j}]$, its
closest proxy is either $p_{k-1}$ or $p_{k}$ (i.e.,
$p^{v}\in\\{p_{k-1},p_{k}\\}$), and therefore
$\texttt{top}(p^{v})\in\\{c_{i},c_{j}\\}$. Furthermore, under a directionally-
consistent tie-breaking rule, voter $v$’s favorite candidate $\texttt{top}(v)$
must be on the same side of the proxy bisector as $\texttt{top}(p^{v})$. Thus,
in order to check for $\theta$-representation, we only need to check whether
the candidates closest to the bisector (equivalently, the candidates that are
furthest away from $c_{i}$ and $c_{j}$) are $\theta$-close to either $c_{i}$
or $c_{j}$.

The reasoning behind step (ii) is as follows: Since the proxy bisector between
$p_{k-1}$ and $p_{k}$ does not coincide with any candidate bisector between
adjacent candidates, there must exist a candidate, say
$c_{\ell}\in\mathcal{C}$, whose Voronoi cell $V_{\ell}$ includes the proxy
bisector in its relative interior. Then, for any sufficiently small
$\varepsilon>0$ (for example, as chosen above), there must exist voters that
are $\varepsilon$-far from the proxy bisector on either side of it whose
favorite candidate is $c_{\ell}$, but the favorite candidates of their
respective closest proxies are $c_{i}$ and $c_{j}$. Thus, it suffices to check
the $\theta$-representation condition for these voters only. For any other
voter $v\in[c_{i},c_{j}]\setminus V_{\ell}$, its favorite candidate and the
favorite candidate of its closest proxy are on the same side of the bisector
between $c_{i}$ and $c_{j}$, and are therefore $\theta$-close.

Overall, we have that condition (b) can also be efficiently verified. This
implies that each lower-triangular entry $T(j,k)$ for $k<j$ can be efficiently
computed, implying that the algorithm runs in polynomial time.

Once the table $T$ has been computed, the optimal number of proxies for the
given instance $\mathcal{I}$ is the smallest $k$ for which $T(j,k)$ equals $1$
for some candidate $c_{j}\in\mathcal{C}_{\theta}$, i.e.,
$\texttt{opt}(\mathcal{I})=\min\\{k\in[m]:T(j,k)=1\text{ for some
}c_{j}\in\mathcal{C}_{\theta}\\}$. To construct the optimal proxy arrangement
$p_{1},\dots,p_{k}$, the algorithm computes the positions of the proxies in
the reverse order, i.e., first $p_{k}$, then $p_{k-1}$, and so on. The
strategy is as follows: Pick any $j\in[m]$ such that
$T(j,\texttt{opt}(\mathcal{I}))=1$, and place the proxy $p_{k}$ at $c_{j}$.
Next, pick any $i<j$ such that $T(i,\texttt{opt}(\mathcal{I})-1)=1$; we know
that such $i$ exists from condition (a) above. The proxy $p_{k-1}$ is then
placed at $c_{i}$, and so on. Note that the proxy arrangement thus constructed
satisfies restricted positioning. ❑

##  9 Proof of Theorem 2

See 2

###### Proof.

We will show that Algorithm 1 computes the desired proxy arrangement.

Input: A Proxy Voting instance $\mathcal{I}=\langle\mathcal{C},\theta\rangle$.

Output: A $\theta$-representative arrangement of proxies.

Initialize $c\leftarrow c_{1}$

$\triangleright$ Start with $c_{1}$ as the reference

Initialize $j\leftarrow 1$

$\triangleright$ $j$ is the index of proxy bisector

1 while  _$c+\theta <1$_ do

// $c^{L}$ and $c^{R}$ are the candidates closest to $(c+\theta)$ on left and
right, respectively

2 $c^{L}\leftarrow\arg\min_{c_{i}\in\mathcal{C}\,:\,c_{i}\leq
c+\theta}|c_{i}-(c+\theta)|$

3
$c^{R}\leftarrow\arg\min_{c_{i}\in\mathcal{C}\,:\,c_{i}>c+\theta}|c_{i}-(c+\theta)|$

// Place proxies on $c^{L}$ and $c^{R}$ to create the $j^{\text{th}}$ proxy
bisector at $b_{j}\coloneqq(c^{L}+c^{R})/2$

4 $p_{j}^{L}\leftarrow c^{L}$ and $p_{i}^{R}\leftarrow c^{R}$

$c\leftarrow c^{R}$

$\triangleright$ Repeat with $c^{R}$ as the new reference

5 $j\leftarrow j+1$

return _$\mathcal{P}=\\{p_{j}^{L},p_{j}^{R}\\}_{j\in[t]}$_

$\triangleright$ $t$ is the number of proxy bisectors computed by the
algorithm

ALGORITHM 1 Algorithm for computing upper bound on no. of proxies under
restricted positioning

The algorithm works by fixing a _reference_ candidate $c$ in each iteration
(in the first iteration, the leftmost candidate $c_{1}$ is the reference). Let
$c^{L}\coloneqq\arg\min_{c_{i}\in\mathcal{C}\,:\,c_{i}\leq
c+\theta}|c_{i}-(c+\theta)|$ denote the candidate that is weakly to the left
of and closest to the point $c+\theta$. Similarly, let
$c^{R}\coloneqq\arg\min_{c_{i}\in\mathcal{C}\,:\,c_{i}>c+\theta}|c_{i}-(c+\theta)|$
denote the candidate that is strictly to the right of and closest to
$c+\theta$. The algorithm places proxies at $c^{L}$ and $c^{R}$, thus creating
a _proxy bisector_ that coincides with the candidate bisector at
$(c^{L}+c^{R})/2$. It then proceeds to the next iteration with $c^{R}$ as the
new reference, and this process continues as long as $c+\theta$ remains within
$[0,1]$.

It is easy to see that the algorithm runs in polynomial time. Indeed, each
candidate can take the role of the reference at most once, and therefore the
algorithm performs at most $m$ iterations of the while-loop. Furthermore, each
such iteration takes polynomial time since the candidate locations
$c_{1},\dots,c_{m}$ and the parameter $\theta$ are assumed to be rational
numbers.

Let $\mathcal{P}$ denote the proxy arrangement returned by the algorithm. To
see why $\mathcal{P}$ is $\theta$-representative, we will find it convenient
to define a partitioning of the line segment $[0,1]$ into _intervals_.
Specifically, let $p_{j}^{L}$ and $p_{j}^{R}$ denote the proxies added by the
algorithm in the $j^{\text{th}}$ iteration, and let $b_{j}$ denote the
corresponding proxy bisector, i.e., $b_{j}\coloneqq(p_{j}^{L}+p_{j}^{R})/2$.
Thus, if there are $t$ iterations overall, then
$\mathcal{P}=\\{p_{j}^{L},p_{j}^{R}\\}_{j\in[t]}$ and the set of corresponding
proxy bisectors is $\\{b_{1},\dots,b_{t}\\}$.555Notice that the output
$\mathcal{P}$ of Algorithm 1 can contain up to $2t$ proxies, and thus there
can be up to $2t-1$ proxy bisectors between pairs of adjacent proxies. Among
these, $b_{j}$ denotes the proxy bisector between the pair of proxies
$\\{p_{j}^{L},p_{j}^{R}\\}$ created in the $j^{\text{th}}$ iteration.

By construction, each proxy bisector $b_{j}$ coincides with a candidate
bisector between adjacent candidates. Therefore, we can associate each
candidate $c_{i}$ with a unique $j\in\\{0,1,\dots,t\\}$ such that
$b_{j}<c_{i}<b_{j+1}$, where $b_{0}\coloneqq-\infty$ and
$b_{t+1}\coloneqq+\infty$. In other words, we obtain a partitioning of the set
of candidates
$\mathcal{C}=\mathcal{C}_{1}\cup\mathcal{C}_{2}\cup\dots\cup\mathcal{C}_{t+1}$,
where, for every $j\in[t+1]$,
$\mathcal{C}_{j}\coloneqq\\{c_{i}\in\mathcal{C}:b_{j-1}<c_{i}<b_{j}\\}$
denotes the set of candidates between the proxy bisectors $b_{j-1}$ and
$b_{j}$.

Recall that the Voronoi cell of candidate $c_{i}$ is defined as
$V_{i}\coloneqq\\{v\in[0,1]:\texttt{top}(v)=c_{i}\\}$. For every $j\in[t+1]$,
we define the _interval_
$I_{j}\coloneqq\cup_{i\in[m]:c_{i}\in\mathcal{C}_{j}}V_{i}$ as the set of
locations of all voters whose favorite candidate is in $\mathcal{C}_{j}$
(recall that ties are broken according to a directionally consistent tie-
breaking rule). As before, we will identify all candidates, voters, and
proxies with their locations, and will say that ‘a candidate $c$ (or a proxy
$p$) belongs to interval $I_{j}$’ if the voter located at $v=c$ (or $v=p$) is
in $I_{j}$. Notice that $I_{1}\cup I_{2}\cup\dots\cup I_{t+1}=[0,1]$.

A useful observation is that all candidates in an interval are $\theta$-close.
Indeed, the leftmost candidate in each interval plays the role of a reference
candidate during some iteration (let us call such a candidate the reference
candidate for the interval). By the candidate selection rule in Line 1, the
rightmost candidate in an interval is $\theta$-close to the reference (i.e.,
the leftmost) candidate in that interval. Thus, we have that for every
$j\in[t+1]$, all candidates in $I_{j}$ (equivalently, all candidates in
$\mathcal{C}_{j}$) are $\theta$-close.

Fix any $j\in[t+1]$ and consider any voter location $v\in I_{j}$. In order to
prove that the proxy arrangement $\mathcal{P}$ is $\theta$-representative, we
need to show that $|\texttt{top}(v)-\texttt{top}(p^{v})|\leq\theta$. Since
$I_{j}$ is a union of Voronoi cells, it is easy to see that the favorite
candidate of voter $v$ must be in $\mathcal{C}_{j}$, i.e.,
$\texttt{top}(v)\in\mathcal{C}_{j}$. Furthermore, since all candidates in
$\mathcal{C}_{j}$ are $\theta$-close, it suffices to show that voter $v$’s
closest proxy also lies in $I_{j}$ (i.e., $p^{v}\in I_{j}$), as that would
imply $\texttt{top}(p^{v})\in\mathcal{C}_{j}$.

In order to prove that $p^{v}\in I_{j}$, observe that any voter $v\in I_{j}$
prefers the leftmost candidate in $\mathcal{C}_{j}$ over any candidate in
$\mathcal{C}_{1}\cup\dots\cup\mathcal{C}_{j-1}$. Similarly, it prefers the
rightmost candidate in $\mathcal{C}_{j}$ over any candidate in
$\mathcal{C}_{j+1}\cup\dots\cup\mathcal{C}_{t+1}$. Since the proxy bisectors
$b_{j-1}$ and $b_{j}$ coincide with the candidate bisectors, a similar
observation holds for the proxies. That is, voter $v$ is closer to the proxy
$p^{R}_{j-1}$ than to any other proxy to its left, and is closer to the proxy
$p^{L}_{j}$ than to any other proxy to its right. Thus, voter $v$’s closest
proxy must be either $p^{R}_{j-1}$ or $p^{L}_{j}$ (i.e.,
$p^{v}\in\\{p^{R}_{j-1},p^{L}_{j}\\}$), both of which lie in $I_{j}$, as
desired.

Finally, we will show that the total number of proxies in $\mathcal{P}$
satisfies the desired bound. Observe that the total number of bisectors
computed by the algorithm is $t<\frac{1}{\theta}$. This is because for any
$j\in[t]$, the reference candidates for the intervals $I_{j}$ and $I_{j+1}$
are separated by a distance strictly greater than $\theta$ (Line 1), and the
distance between the extreme candidates is equal to $1$. If
$\theta=\frac{1}{q}$ for some $q\in\mathbb{N}$, we have $t<q$, and since $t$
and $q$ are both integers, we have $t\leq q-1=\frac{1}{\theta}-1$. Otherwise,
we have $t\leq\lfloor\frac{1}{\theta}\rfloor$. The desired bound now follows
by observing that there are at most two distinct proxies per bisector. ❑

##  10 Proof of Proposition 1

See 1

###### Proof.

Let $p\in\mathbb{N}$ denote the unique positive integer such that
$\frac{1}{p}\leq\theta<\frac{1}{p-1}$. Observe that $p-1$ equals
$\frac{1}{\theta}-1$ when $\frac{1}{\theta}\in\mathbb{N}$, and equals
$\lfloor\frac{1}{\theta}\rfloor$ otherwise. Therefore, it suffices to show
that any $\theta$-representative arrangement requires $2p-2$ proxies.

Our construction of the lower bound instance will depend on whether $p$ is
even or odd. Specifically, let
$\varepsilon\coloneqq\frac{1-(p-1)\theta}{5(p-1)/2}$ (if $p$ is odd) or
$\varepsilon\coloneqq\frac{1-(p-1)\theta}{(5p/2-3)}$ (if $p$ is even), and
observe that $\varepsilon>0$ in both cases. The distinction between even and
odd cases is made in order to ensure that the distance between the extreme
candidates is equal to $1$.

The instance consists of the candidate $c_{1}$ on the left, followed by a
sequence of pairs of candidates $\\{c_{2i},c_{2i+1}\\}$ for $i\in\mathbb{N}$
such that each pair is at a distance of $\theta+\varepsilon$ from the
preceding pair, and the gap between the candidates in each pair alternates
between $\varepsilon$ and $2\varepsilon$ (see Figure 3 for an example). In
other words, the sequence of distances between adjacent pair of candidates
from left to right is given by
$\theta+\varepsilon,\varepsilon,\theta+\varepsilon,2\varepsilon,\theta+\varepsilon,\varepsilon$
and so on. The rightmost candidate is $c_{2p-1}$. It is easy to see that all
candidate locations are rational, and that the distance between the extreme
candidates is equal to $1$.

We will now show that any $\theta$-representative proxy arrangement for the
aforementioned instance requires at least $2p-2$ proxies, which, by the above
observation, will imply the desired bound. Notice that $c_{1}$ and $c_{2}$ are
$\theta$-far since $\varepsilon>0$. Therefore, under any
$\theta$-representative proxy arrangement, there must exist a proxy bisector
(between adjacent proxies) that coincides with the candidate bisector between
$c_{1}$ and $c_{2}$ (contrapositive of Lemma 1). The only way this could
happen under restricted positioning is if there are proxies on both $c_{1}$
and $c_{2}$.

Next, observe that the candidates $c_{3}$ and $c_{4}$ are also $\theta$-far.
Therefore, under any $\theta$-representative proxy arrangement, there must
exist a proxy bisector between adjacent proxies that coincides with the
candidate bisector between $c_{3}$ and $c_{4}$. Notice that the proxy at
$c_{2}$ cannot be one of these proxies, since that would require placing
another proxy at the location $c_{4}+\varepsilon$ which does not have any
candidate and would violate restricted positioning assumption. Therefore,
there must exist another pair of proxies on $c_{3}$ and $c_{4}$.

By a similar argument, the proxy bisector that coincides with the candidate
bisector between $c_{5}$ and $c_{6}$ cannot correspond to the proxy at
$c_{4}$, since that would involve placing another proxy at
$c_{6}+2\varepsilon$, which does not have any candidate. Therefore, it is
necessary to place proxies at $c_{5}$ and $c_{6}$.

Continuing in this manner, we observe that the desired arrangement must place
proxies on all candidates except for the last one. Thus, the number of proxies
required is $2p-2$, as desired. ❑

##  11 Proof of Theorem 3

This section provides an algorithm for constructing an optimal
$\theta$-representative proxy arrangement. Unlike the restricted case, the set
of possible proxy locations is no longer finite, which prohibits the use of
simple dynamic programming techniques (as in Theorem 1) that iterate over the
discrete set of feasible locations. Instead, we must perform a careful
analysis of the feasible _regions_ of $\theta$-representative proxies, and
then prove that such regions can be computed efficiently.

Before discussing the algorithm, let us set up some helpful notation. Recall
that for any $i\in[m]$, the Voronoi cell of candidate $c_{i}\in\mathcal{C}$ is
the set of locations of all voters whose favorite candidate is $c_{i}$, i.e.,
$V_{i}=\\{v\in[0,1]:\texttt{top}(v)=c_{i}\\}$. We will find it convenient to
define, for every $i\in[m]$, the _extended Voronoi cell_
$\makebox[0.0pt]{$\phantom{V}\overline{\phantom{V}}$}V_{i}\coloneqq\\{v\in(-\infty,\infty):\texttt{top}(v)=c_{i}\\}$
as the analog of Voronoi cell where the voters are hypothesized to lie
anywhere on the real line. Thus,
$\makebox[0.0pt]{$\phantom{V}\overline{\phantom{V}}$}V_{1}=(-\infty,0)\cup
V_{1}$,
$\makebox[0.0pt]{$\phantom{V}\overline{\phantom{V}}$}V_{m}=V_{m}\cup(1,\infty)$,
and $\makebox[0.0pt]{$\phantom{V}\overline{\phantom{V}}$}V_{i}=V_{i}$ for all
$i\in\\{2,3,\dots,m-1\\}$. Additionally, given any $\theta\in(0,1)$, we will
define
$\makebox[0.0pt]{$\phantom{V}\overline{\phantom{V}}$}V_{i}^{+}\coloneqq\cup_{c_{\ell}\in\mathcal{C}\,:\,c_{\ell}>c_{i}+\theta}\makebox[0.0pt]{$\phantom{V}\overline{\phantom{V}}$}V_{\ell}$
as the set of all locations of voters (lying anywhere on the real line) whose
favorite candidate is $\theta$-far from $c_{i}$ on the right, and
$\makebox[0.0pt]{$\phantom{V}\overline{\phantom{V}}$}V_{i}^{-}\coloneqq\cup_{c_{\ell}\in\mathcal{C}\,:\,c_{\ell}<c_{i}-\theta}\makebox[0.0pt]{$\phantom{V}\overline{\phantom{V}}$}V_{\ell}$
as the analogous set on the left side. We will call
$\makebox[0.0pt]{$\phantom{V}\overline{\phantom{V}}$}V^{+}_{i}$ and
$\makebox[0.0pt]{$\phantom{V}\overline{\phantom{V}}$}V^{-}_{i}$ the _right
infeasible_ and _left infeasible_ regions, respectively, as they denote the
regions where the proxy $p^{v}$ is not allowed to lie if voter $v$’s favorite
candidate is $c_{i}$. Note that the idea of allowing the voters to lie
anywhere on the real line is only used for defining the quantities
$\makebox[0.0pt]{$\phantom{V}\overline{\phantom{V}}$}V_{i}$,
$\makebox[0.0pt]{$\phantom{V}\overline{\phantom{V}}$}V^{+}_{i}$, and
$\makebox[0.0pt]{$\phantom{V}\overline{\phantom{V}}$}V^{-}_{i}$.

We will also define the Voronoi cells of the proxies. Given a proxy
arrangement $\mathcal{P}=\\{p_{1},\dots,p_{k}\\}$, the Voronoi cell $W_{j}$ of
proxy $p_{j}$ is the set of all locations of voters whose closest proxy is
$p_{j}$, i.e., $W_{j}\coloneqq\\{v\in[0,1]:|v-p_{j}|\leq|v-p_{\ell}|\text{ for
any }\ell\neq j\\}$, where ties are broken according to a directionally-
consistent tie-breaking rule (Definition 1). Notice that $v\in W_{j}$ if and
only if $p_{j}=p^{v}$.

Let us start with a characterization of $\theta$-representative proxy
arrangements in terms of Voronoi cells of proxies and the left/right
infeasible regions that will be useful in our algorithm (Lemma 2).

######  Lemma 2.

A proxy arrangement $\mathcal{P}=\\{p_{1},\dots,p_{k}\\}$ is
$\theta$-representative if and only if for every proxy $p_{j}\in\mathcal{P}$,

$W_{j}\cap\\{\makebox[0.0pt]{$\phantom{V}\overline{\phantom{V}}$}V_{i}^{+}\cup\makebox[0.0pt]{$\phantom{V}\overline{\phantom{V}}$}V_{i}^{-}\\}=\emptyset,$

where $c_{i}\in\mathcal{C}$ is the unique candidate such that
$\texttt{top}(p_{j})=c_{i}$.

###### Proof.

To prove the forward direction, suppose, for contradiction, that for some
proxy $p_{j}\in\mathcal{P}$, there exists a voter $v\in
W_{j}\cap\\{\makebox[0.0pt]{$\phantom{V}\overline{\phantom{V}}$}V_{i}^{+}\cup\makebox[0.0pt]{$\phantom{V}\overline{\phantom{V}}$}V_{i}^{-}\\}$.
Then, $\texttt{top}(v)\in\\{c_{\ell}\in\mathcal{C}:|c_{\ell}-c_{i}|>\theta\\}$
and $\texttt{top}(p^{v})=\texttt{top}(p_{j})=c_{i}$, which violates
$\theta$-representation.

In the reverse direction, suppose, for contradiction, that $\mathcal{P}$ is
not $\theta$-representative. Then, there must exist a voter $v\in[0,1]$ such
that $|\texttt{top}(v)-\texttt{top}(p^{v})|>\theta$. Let
$c_{\ell}\coloneqq\texttt{top}(v)$ denote the favorite candidate of voter $v$,
$p_{j}\coloneqq p^{v}$ denote its closest proxy, and
$c_{i}\coloneqq\texttt{top}(p_{j})$ denote the favorite candidate of $p_{j}$.
Thus, $|c_{\ell}-c_{i}|>\theta$, which means that
$v\in\makebox[0.0pt]{$\phantom{V}\overline{\phantom{V}}$}V_{i}^{+}\cup\makebox[0.0pt]{$\phantom{V}\overline{\phantom{V}}$}V_{i}^{-}$.
Furthermore, $v\in W(p_{j})$. Therefore,
$W_{j}\cap\\{\makebox[0.0pt]{$\phantom{V}\overline{\phantom{V}}$}V_{i}^{+}\cup\makebox[0.0pt]{$\phantom{V}\overline{\phantom{V}}$}V_{i}^{-}\\}\neq\emptyset$,
which is a contradiction. ❑

Input: A Proxy Voting instance $\mathcal{I}=\langle\mathcal{C},\theta\rangle$
and a positive integer $k\in\mathbb{N}$.

Output: YES (if $k$ proxies can form a $\theta$-representative arrangement) or
NO (otherwise).

// Initialize the feasibility set $F^{1}$ for the leftmost proxy

1
$F^{1,1}\leftarrow\makebox[0.0pt]{$\phantom{V_{1}}\overline{\phantom{V_{1}}}$}V_{1}$
for  _$i\in\\{2,3,\dots,m\\}$_ do

2 if  _$|c_{i}-c_{1}|\leq\theta$_ then

$F^{1,i}=\makebox[0.0pt]{$\phantom{V}\overline{\phantom{V}}$}V_{i}$

$\triangleright$ Include
$\makebox[0.0pt]{$\phantom{V}\overline{\phantom{V}}$}V_{i}$ in the feasibility
set if $c_{i}$ is $\theta$-close to $c_{1}$

3

4 else

$F^{1,i}=\emptyset$

$\triangleright$ Discard if $c_{i}$ is $\theta$-far from $c_{1}$

5

6

7$F^{1}\leftarrow\cup_{i\in[m]}F^{1,i}$

// Compute the feasibility set $F^{j}$ for the $j^{\text{th}}$ proxy $p_{j}$
for $j\in\\{2,\dots,k\\}$

8 Initialize $F^{j,i}\leftarrow\emptyset$ for all $j\in\\{2,\dots,k\\}$ and
$i\in[m]$.

9 for  _$j\in\\{2,\dots,k\\}$_ do

10 for  _$h\in[m]$_ do

11 for  _$i\geq h$_ do

12 if  _$h=i$_ then

13 $\alpha\leftarrow\inf F^{j-1,h}$

$F^{j,i}\leftarrow
F^{j,i}\cup\\{\makebox[0.0pt]{$\phantom{V}\overline{\phantom{V}}$}V_{i}\cap(\alpha,\infty)\\}$

$\triangleright$ Include all
$p_{j}\in\makebox[0.0pt]{$\phantom{V}\overline{\phantom{V}}$}V_{i}$ for which
$p_{j}>p_{j-1}$ for some $p_{j-1}\in F^{j-1,i}$

14

15 else if
_$\makebox[0.0pt]{$\phantom{b}\overline{\phantom{b}}$}b_{h}\geq\makebox[0.0pt]{$\phantom{b}\underline{\phantom{b}}$}b_{i}$_
then

// Iterate over all maximal convex subsets $S\in F^{j-1,h}$

16 for  _$S\in F^{j-1,h}$_ do

17 $x\leftarrow\inf S$ and $y\leftarrow\sup S$

$x^{\prime}\leftarrow\mu(x,\makebox[0.0pt]{$\phantom{b}\overline{\phantom{b}}$}b_{h})$
and
$y^{\prime}\leftarrow\mu(y,\makebox[0.0pt]{$\phantom{b}\underline{\phantom{b}}$}b_{i})$

$\triangleright$ Reflect the endpoints of $S$ about
$\makebox[0.0pt]{$\phantom{b}\overline{\phantom{b}}$}b_{h}$ and
$\makebox[0.0pt]{$\phantom{b}\underline{\phantom{b}}$}b_{i}$

$F^{j,i}\leftarrow
F^{j,i}\cup\\{[y^{\prime},x^{\prime}]\cap\makebox[0.0pt]{$\phantom{V}\overline{\phantom{V}}$}V_{i}\\}$

$\triangleright$ Compute the intersection of the reflection with
$\makebox[0.0pt]{$\phantom{V}\overline{\phantom{V}}$}V_{i}$

18

19

20

21

22 $F^{j}\leftarrow\cup_{i\in[m]}F^{j,i}$

23

24 if
_$F^{k}\cap\\{\cup_{c_{i}\in\mathcal{C}:|c_{i}-c_{m}|\leq\theta}\makebox[0.0pt]{$\phantom{V}\overline{\phantom{V}}$}V_{i}\\}\neq\emptyset$_
then

25 return _YES_

26 else

27 return _NO_

ALGORITHM 2 Algorithm for determining the optimal number of proxies under
unrestricted positioning

#### Description of the algorithm

Consider a pair of adjacent proxies located at $p_{j-1}$ and $p_{j}$ such that
$\texttt{top}(p_{j-1})=c_{\ell}$ and $\texttt{top}(p_{j})=c_{i}$. We say that
the proxy locations $p_{j-1}$ and $p_{j}$ are _mutually feasible_ if the
Voronoi cell $W_{j-1}$ of the proxy $p_{j-1}$ does not overlap with the right
infeasible region
$\makebox[0.0pt]{$\phantom{V}\overline{\phantom{V}}$}V^{+}_{\ell}$ of the
candidate $c_{\ell}$, and the Voronoi cell $W_{j}$ of the proxy $p_{j}$ does
not overlap with the left infeasible region
$\makebox[0.0pt]{$\phantom{V}\overline{\phantom{V}}$}V^{-}_{i}$ of the
candidate $c_{i}$. From Lemma 2, it follows that a proxy arrangement is
$\theta$-representative if and only if all adjacent pairs of proxies are
mutually feasible (in addition to the leftmost and rightmost proxies being
feasible for the leftmost and rightmost voters, respectively).

At a high level, our algorithm (Algorithm 2) uses dynamic programming to
determine the “feasibility set” of each proxy using the feasibility set of its
preceding proxy. More concretely, the feasibility set of the leftmost proxy
$p_{1}$ is given by $F^{1}\coloneqq\cup_{c_{i}\in\mathcal{C}\,:\,c_{i}\leq
c_{1}+\theta}\makebox[0.0pt]{$\phantom{V}\overline{\phantom{V}}$}V_{i}$, which
is the set of all locations of $p_{1}$ for which $\theta$-representation is
satisfied for all voters in $[0,p_{1}]$. For any $j\in\\{2,3,\dots,k\\}$, the
feasibility set $F^{j}$ of the proxy $p_{j}$ is the set of all locations of
$p_{j}$ (on the real line) for which there exists some feasible location
$p_{j-1}\in F^{j-1}$ of the previous proxy such that $p_{j}$ and $p_{j-1}$ are
mutually feasible. Thus, if all adjacent pairs of proxies in
$\\{p_{1},p_{2},\dots,p_{j}\\}$ are mutually feasible, then
$\theta$-representation is satisfied for all voters in $W_{1}\cup
W_{2}\cup\dots\cup W_{j-1}$.

Once the feasibility set $F^{k}$ of the rightmost proxy $p_{k}$ has been
determined, the algorithm checks whether it overlaps with the set
$\cup_{c_{i}\in\mathcal{C}:|c_{i}-c_{m}|\leq\theta}\makebox[0.0pt]{$\phantom{V}\overline{\phantom{V}}$}V_{i}$.
The latter is the set of all locations of the rightmost proxy for which
$\theta$-representation is satisfied for the rightmost voter in $[0,1]$. If
the overlap is non-empty, then there exists a feasible location of the proxy
$p_{k}$ that is $\theta$-representative for the voters in $W_{k}$. By
definition of the feasibility set, there must exist a feasible location
$p_{k-1}$ of the previous proxy such that $p_{k-1}$ and $p_{k}$ are mutually
feasible, thus implying $\theta$-representation for voters in $W_{k-1}$.
Similarly, there must exist a feasible location of the proxy $p_{k-2}$ that is
mutually feasible with $p_{k-1}$, and so on. Continuing backwards in this
manner, we obtain a set of proxy locations $p_{1},\dots,p_{k}$ wherein the
adjacent pairs are mutually feasible, which immediately implies
$\theta$-representation. On the other hand, the absence of an overlap
certifies that with $k$ proxies, there is no $\theta$-representative proxy
arrangement in the given instance.

#### Computing the feasibility sets

For every $j\in[k]$ and every $i\in[m]$, let $F^{j,i}\coloneqq
F^{j}\cap\makebox[0.0pt]{$\phantom{V}\overline{\phantom{V}}$}V_{i}$ denote the
restriction of the feasibility set of the proxy $p_{j}$ to the extended
Voronoi cell of the candidate $c_{i}$. Notice that
$F^{j}=\cup_{c_{i}\in\mathcal{C}}F^{j,i}$. To compute $F^{j,i}$, the algorithm
considers $F^{j-1,h}$ for a fixed candidate $c_{h}\leq c_{i}$, and computes
all locations in $F^{j,i}$ that are mutually feasible with some location in
$F^{j-1,h}$. To help with the forthcoming discussion on the computation of
$F^{j,i}$, let us set up the relevant notation below.

For every candidate $c_{h}\in\mathcal{C}$, let
$\makebox[0.0pt]{$\phantom{b}\overline{\phantom{b}}$}b_{h}$ denote the
candidate bisector between the furthest $\theta$-close and the closest
$\theta$-far candidates to $c_{h}$ on the right. That is,
$\makebox[0.0pt]{$\phantom{b}\overline{\phantom{b}}$}b_{h}\coloneqq\frac{c_{\ell}+c_{\ell+1}}{2}$
where $c_{\ell}\coloneqq\arg\min_{c_{i}\in\mathcal{C}\,:\,c_{i}\leq
c_{h}+\theta}|c_{i}-(c_{h}+\theta)|$. Similarly, let
$\makebox[0.0pt]{$\phantom{b}\underline{\phantom{b}}$}b_{h}$ denote the
analogous bisector on the left side, i.e.,
$\makebox[0.0pt]{$\phantom{b}\underline{\phantom{b}}$}b_{h}\coloneqq\frac{c_{\ell-1}+c_{\ell}}{2}$
where $c_{\ell}\coloneqq\arg\min_{c_{i}\in\mathcal{C}\,:\,c_{i}\geq
c_{h}-\theta}|c_{i}-(c_{h}-\theta)|$. In addition, we will define a _mirror_
function $\mu:\mathbb{R}\times[0,1]\rightarrow\mathbb{R}$ such that $\mu(x,b)$
denotes the _reflection_ of the point $x\in\mathbb{R}$ about the point
$b\in[0,1]$; thus, $b=(x+\mu(x,b))/2$.

Let us now discuss the computation of $F^{j,i}$ using $F^{j-1,h}$. Notice that
if $h=i$, then any location
$x\in\makebox[0.0pt]{$\phantom{V}\overline{\phantom{V}}$}V_{i}$ is feasible
for proxy $p_{j}$ as long as there exists some $y\in F^{j-1,h}$ such that
$y<x$ (since proxies are assumed to be non-overlapping). Thus, if
$\alpha\coloneqq\inf F^{j-1,h}$, then all locations in
$\makebox[0.0pt]{$\phantom{V}\overline{\phantom{V}}$}V_{i}$ strictly to the
right of $\alpha$ are feasible for $p_{j}$ (Lines 2 and 2 of Algorithm 2). If
$h>i$, then we obtain infeasibility due to $p_{j-1}>p_{j}$.

This leaves us with the case $h<i$. Here, we will leverage the
characterization in Lemma 2 to compute the desired feasibility set. Notice
that for a proxy $p_{j-1}$ with $\texttt{top}(p_{j-1})=c_{h}$, Lemma 2
immediately implies that the next proxy bisector must be (weakly) to the left
of $\makebox[0.0pt]{$\phantom{b}\overline{\phantom{b}}$}b_{h}$. Similarly, it
implies that for a proxy $p_{j}$ with $\texttt{top}(p_{j})=c_{i}$, the
previous proxy bisector must be (weakly) to the right of
$\makebox[0.0pt]{$\phantom{b}\underline{\phantom{b}}$}b_{i}$. Hence, it cannot
be that $\texttt{top}(p_{j-1})=c_{h}$ and $\texttt{top}(p_{j})=c_{i}$ when
$\makebox[0.0pt]{$\phantom{b}\overline{\phantom{b}}$}b_{h}<\makebox[0.0pt]{$\phantom{b}\underline{\phantom{b}}$}b_{i}$.

Thus, we only need to consider the case when
$\makebox[0.0pt]{$\phantom{b}\overline{\phantom{b}}$}b_{h}\geq\makebox[0.0pt]{$\phantom{b}\underline{\phantom{b}}$}b_{i}$.
Note that for any $j\in[k]$ and any $i\in[m]$, the set $F^{j,i}$ could, in
general, consist of multiple disjoint convex sets that are either open,
closed, or semi-open intervals, depending on the tie-breaking rule (we will
shortly prove that the number of such sets is polynomially bounded). Let
$n^{j,i}\coloneqq|F^{j,i}|$ denote the number of maximal convex subsets of
$F^{j,i}$, and let $n^{j}\coloneqq\sum_{i\in[m]}n^{j,i}$. Note that $n^{j}$ is
an upper bound on the number of maximal convex subsets in $F^{j}$, since the
sets from different $F^{j,i}$’s could be merged when we take their union.

$c_{h}$$c_{i}$$\makebox[0.0pt]{$\phantom{b}\underline{\phantom{b}}$}b_{i}$$\makebox[0.0pt]{$\phantom{b}\overline{\phantom{b}}$}b_{h}$$x$$y$$y^{\prime}$$x^{\prime}$$\theta$$\theta$
Figure 8: Computing the set $F^{j,i}$ using the set $S=[x,y]$ in $F^{j-1,h}$.
Here, $x^{\prime}\coloneqq\mu(x,\overline{b}_{h})$ and
$y^{\prime}\coloneqq\mu(y,\underline{b}_{i})$. The shaded regions denote the
extended Voronoi cells of the candidates. Note that the set
$[y^{\prime},x^{\prime}]$ falls completely inside the extended Voronoi cell
$\overline{V}_{i}$ of candidate $c_{i}$, and therefore the set $S$ is of Type
I.

Consider any maximal convex subset $S\in F^{j-1,h}$. For ease of discussion,
let us assume that $S$ is a closed interval of the form $[x,y]$ as shown in
Figure 8 (the case of open or semi-open intervals can be handled similarly).
By Lemma 2, any point $z\in F^{j,i}$ that is mutually feasible with some point
in $S$ must be (weakly) to the left of the reflection of $x$ about the
bisector $\makebox[0.0pt]{$\phantom{b}\overline{\phantom{b}}$}b_{h}$, i.e.,
$z\leq x^{\prime}$ where
$x^{\prime}\coloneqq\mu(x,\makebox[0.0pt]{$\phantom{b}\overline{\phantom{b}}$}b_{h})$.
This is because the proxy bisector between $p_{j-1}$ and $p_{j}$ has to be
(weakly) to the left of
$\makebox[0.0pt]{$\phantom{b}\overline{\phantom{b}}$}b_{h}$ by Lemma 2. Also,
again by Lemma 2, for any point $z\in F^{j,i}$, we must have that the
reflection of $z$ about the bisector
$\makebox[0.0pt]{$\phantom{b}\underline{\phantom{b}}$}b_{i}$ is (weakly) to
the left of $y$. This is equivalent to asking that $z\geq y^{\prime}$, where
$y^{\prime}\coloneqq\mu(y,\makebox[0.0pt]{$\phantom{b}\underline{\phantom{b}}$}b_{i})$.
Thus, the contribution of the set $S$ to $F^{j,i}$ is given by
$\makebox[0.0pt]{$\phantom{V}\overline{\phantom{V}}$}V_{i}\cap[y^{\prime},x^{\prime}]$.
The contributions of all maximal convex subsets in $F^{j-1,h}$ to $F^{j,i}$
are taken together as a union in Line 2 of Algorithm 2.

We will finish this segment by arguing that the number of maximal convex
subsets is polynomially bounded. Formally, we will show (via induction) that
for every $j\in[k]$, $n^{j}=\sum_{i\in[m]}n^{j,i}\leq j\cdot 2m$. The base
case of $j=1$ is easy to verify: Indeed, for every $i\in[m]$, the set
$F^{1,i}$ is either empty or consists of a single maximal convex subset,
namely the extended Voronoi cell of candidate $c_{i}$ (Lines 2 to 2 in
Algorithm 2). Thus, for every $i\in[m]$, $n^{1,i}\leq 1$, and therefore
$n^{1}\leq m$.

Now suppose $n^{j-1}\leq(j-1)\cdot 2m$. We want to show that $n^{j}\leq j\cdot
2m$. Fix some $h\in[m]$ and some $i\geq h$, and consider any fixed maximal
convex subset $S\in F^{j-1,h}$. Observe that $S$ is of one of the following
two types: If the interval $[y^{\prime},x^{\prime}]$ is completely contained
inside the extended Voronoi cell
$\makebox[0.0pt]{$\phantom{V}\overline{\phantom{V}}$}V_{i}$, we say that $S$
is of _Type I_ for $i$ (see Figure 8). Otherwise, if $[y^{\prime},x^{\prime}]$
overlaps partially with
$\makebox[0.0pt]{$\phantom{V}\overline{\phantom{V}}$}V_{i}$ or not at all,
then we say that it is _Type II_ for $i$ (see Figure 9).

$c_{h}$$c_{i}$$\makebox[0.0pt]{$\phantom{b}\underline{\phantom{b}}$}b_{i}$$\makebox[0.0pt]{$\phantom{b}\overline{\phantom{b}}$}b_{h}$$x$$y$$y^{\prime}$$x^{\prime}$$\theta$$\theta$
Figure 9: Illustrating a Type II set $[x,y]$. Observe that the intersection
$[y^{\prime},x^{\prime}]\cap\overline{V}_{i}$ is right extremal for
$\overline{V}_{i}$.

Note that the reflection
$x^{\prime}\coloneqq\mu(x,\makebox[0.0pt]{$\phantom{b}\overline{\phantom{b}}$}b_{h})$
is independent of $i$, and can lie in at most one
$\makebox[0.0pt]{$\phantom{V}\overline{\phantom{V}}$}V_{i}$. Therefore, each
set $S\in F^{j-1,h}$ can be Type I for at most one $i$, thereby contributing
at most one maximal convex subset to $F^{j}$. If $S=[x,y]$ is Type II for $i$,
then the intersection
$[y^{\prime},x^{\prime}]\cap\makebox[0.0pt]{$\phantom{V}\overline{\phantom{V}}$}V_{i}$
must be either _left extremal_ or _right extremal_ in
$\makebox[0.0pt]{$\phantom{V}\overline{\phantom{V}}$}V_{i}$. A priori, it may
seem that each such set $S$ contributes $\mathcal{O}(m)$ convex subsets to
$F^{j}$, which might make the cardinality $n^{j}$ grow exponentially in $j$.
However, the key observation is that when taking the union in Line 2, _all_
left/right extremal subsets within each candidate’s extended Voronoi cell are
_merged_ , and thus we never have more than two extremal sets per candidate.
Therefore, the combined contribution of all Type II sets $S\in F^{j-1,h}$ for
all $h\in[m]$ towards $F^{j,i}$ (where $i\in[m]$ is fixed) results in an
additive increase of at most $2$ in the cardinality of $F^{j,i}$, which, in
turn, results in an additive increase of at most $2m$ in the cardinality of
$F^{j}$. Thus, $n^{j}\leq n^{j-1}+2m\leq(j-1)\cdot 2m+2m=j\cdot 2m$, as
desired.

With the above setup in hand, let us now prove our main result.

See 3

###### Proof.

We will show that Algorithm 2 computes the desired proxy arrangement.

Let us start with the running time analysis. As shown previously, for every
$j\in[k]$, the number of maximal convex subsets in each feasibility set
$F^{j}$ is at most $j\cdot 2m$. Furthermore, each such set can be computed
efficiently, since each reflection or intersection operation takes polynomial
time (note that all maximal convex subsets, which are either closed, open, or
semi-open intervals, can be stored in terms of the end-points of their
closures, and all end-points are rational). Thus, the overall running time is
polynomial.

Notice that although the pseudocode of Algorithm 2 is shown to return only a
YES/NO outcome, one can actually compute a feasible proxy arrangement (if it
exists) as follows: Pick _any_ location in
$F^{k}\cap\\{\cup_{c_{i}\in\mathcal{C}:|c_{i}-c_{m}|\leq\theta}\makebox[0.0pt]{$\phantom{V}\overline{\phantom{V}}$}V_{i}\\}$
for the proxy $p_{k}$ (such a location must exist by the feasibility check in
Line 2). Then, compute a mutually feasible location of the proxy $p_{k-1}$.
This can be computed by a procedure similar to the one used in computing
$F^{j,i}$ using $F^{j-1,h}$. Next, the location of the proxy $p_{k-2}$ is
computed, and so on. Finally, the $\theta$-representation of the proxy
arrangement returned by the algorithm follows from the mutual feasibility
condition maintained by the algorithm in each iteration. ❑

##  12 Proof of Theorem 4

Input: A Proxy Voting instance $\mathcal{I}=\langle\mathcal{C},\theta\rangle$.

Output: A $\theta$-representative arrangement of proxies.

// Phase 1: Compute locations of proxy bisectors

Initialize $c\leftarrow c_{1}$

$\triangleright$ Start with $c_{1}$ as the reference candidate

Initialize $j\leftarrow 1$

$\triangleright$ $j$ is the index of the proxy bisector

1 while  _$c+\theta <1$_ do

// $c^{L}$ and $c^{R}$ are the candidates closest to $(c+\theta)$ on the left
and the right side, respectively

2 $c^{L}\leftarrow\arg\min_{c_{i}\in\mathcal{C}\,:\,c_{i}\leq
c+\theta}|c_{i}-(c+\theta)|$

3
$c^{R}\leftarrow\arg\min_{c_{i}\in\mathcal{C}\,:\,c_{i}>c+\theta}|c_{i}-(c+\theta)|$

$b_{i}=(c^{L}+c^{R})/2$

$\triangleright$ Bisector of $c^{L}$ and $c^{R}$

$c\leftarrow c^{R}$

$\triangleright$ Repeat with $c^{R}$ as the new reference

4 $j\leftarrow j+1$

// Phase 2: Compute proxy locations

5 $B\leftarrow\\{b_{1},b_{2},\dots,b_{t}\\}$

$\triangleright$ Set of proxy bisectors computed in Phase 1

for  _$j\in[t-1]$_ do

$w_{j}\leftarrow b_{j+1}-b_{j}$

$\triangleright$ Compute widths of intervals between consecutive bisectors

6

$W\leftarrow\\{w_{1},w_{2},\dots,w_{t-1}\\}$

$\triangleright$ Set of interval widths

// Initialize a proxy arrangement with two proxies per bisector

7 Initialize
$\varepsilon\leftarrow\frac{1}{3}\cdot\min_{i\in[m-1]}|c_{i+1}-c_{i}|$

8 for  _$j\in[t]$_ do

9 $p_{j}^{L}=b_{j}-\varepsilon$

10 $p_{j}^{R}=b_{j}+\varepsilon$

// Move $p_{j}^{L}$ and $p_{j}^{R}$ away from the bisector $b_{j}$ in opposite
directions until a ‘‘collision’’ occurs

11 for  _$\ell\in[t-1]$_ do

12 $\Delta\leftarrow 0.5\cdot(\min^{(\ell)}W-\min^{(\ell-1)}W)$

$\triangleright$ The step size $\Delta$ is chosen as half of the difference
between the $\ell^{\text{th}}$ and $(\ell-1)^{\text{th}}$ smallest elements in
$W$ (i.e., difference in the widths of the $\ell^{\text{th}}$ and
$(\ell-1)^{\text{th}}$ smallest intervals); here, $\min^{(0)}W\coloneqq
2\varepsilon$.

// Move the left and right proxies in opposite directions by a distance
$\Delta$

13 for  _$j\in[t]$_ do

14 if  _$b_{j}$ is not “frozen”_ then

15 $p_{j}^{L}\leftarrow p_{j}^{L}-\Delta$

16 $p_{j}^{R}\leftarrow p_{j}^{R}+\Delta$

17

// Check for ‘‘collision’’ events

18 for  _$j\in[t-1]$_ do

19 if  _$p_{j}^{R}=p_{j+1}^{L}$_ then

20 Fix the locations of $p_{j}^{L}$, $p_{j}^{R}$, $p_{j+1}^{L}$, and
$p_{j+1}^{R}$

21 Mark the proxy bisectors $b_{j}$ and $b_{j+1}$ as “frozen”

22

23

return _$\mathcal{P}=\\{p_{j}^{L},p_{j}^{R}\\}_{j\in[t]}$_

ALGORITHM 3 Algorithm for computing upper bound on no. of proxies under
unrestricted positioning

See 4

###### Proof.

We will show that Algorithm 3 computes the desired proxy arrangement.

Let us start by showing that Algorithm 3 terminates in polynomial time.
Observe that in Phase 1, the algorithm performs at most $m$ iterations of the
while-loop (since a candidate can be a reference at most once) and each such
iteration takes polynomial time (since the candidate locations
$c_{1},\dots,c_{m}$ and the parameter $\theta$ are assumed to be rational
numbers). Furthermore, since each proxy bisector $b_{j}$ overlaps with a
candidate bisector between adjacent candidates (Line 3), we know that there
are at most $m-1$ proxy bisectors in total (i.e., $t\leq m-1$) and that each
$b_{j}$ is rational. The latter implies that all interval widths in the set
$W$ as well as the quantity $\Delta$ in each iteration are also rational.
Thus, each for-loop iteration in Phase 2 takes polynomial time, and since
there can be at most $\mathcal{O}(t^{2})$ such iterations, the desired running
time guarantee follows.

Let $\mathcal{P}=\\{p_{j}^{L},p_{j}^{R}\\}_{j\in[t]}$ denote the proxy
arrangement returned by Algorithm 3. We will now argue that $\mathcal{P}$ is
$\theta$-representative. To prove this, it would be helpful to recall the
notion of an “interval” from the proof of Theorem 2. Let $b_{1},\dots,b_{t}$
denote the proxy bisectors computed by the algorithm in Phase 1, where
$b_{j}\coloneqq(p_{j}^{L}+p_{j}^{R})/2$. As noted in the proof of Theorem 2,
the candidates can be partitioned into the sets
$\mathcal{C}_{1},\mathcal{C}_{2},\dots,\mathcal{C}_{t+1}$, where
$\mathcal{C}_{j}\coloneqq\\{c_{i}\in\mathcal{C}:b_{j-1}<c_{i}<b_{j}\\}$ for
$j\in[t+1]$, assuming $b_{0}\coloneqq-\infty$ and $b_{t+1}\coloneqq+\infty$.
For every $j\in[t+1]$, the _interval_
$I_{j}\coloneqq\cup_{i\in[m]:c_{i}\in\mathcal{C}_{j}}V_{i}$ is the set of
locations of all voters whose favorite candidate is in $\mathcal{C}_{j}$. It
is easy to verify that all candidates within an interval are $\theta$-close.

Consider any voter location $v\in[0,1]$ such that $v\in I_{j}$. Thus,
$\texttt{top}(v)\in\mathcal{C}_{j}$. In order to show that the proxy
arrangement $\mathcal{P}$ is $\theta$-representative, it suffices to establish
that voter $v$’s closest proxy $p^{v}$ is such that
$p^{v}\in\\{p_{j}^{R},p_{j+1}^{L}\\}$. Before proving this claim, let us argue
why it gives the desired result. Notice that the initialization in Lines 3 and
3 and the expansion operation in Lines 3 and 3 together ensure that
$p_{j}^{R}\geq b_{j}+\varepsilon$ and $p_{j+1}^{L}\leq b_{j+1}-\varepsilon$ at
every step. Furthermore, the collision check in Line 3 ensures that
$p_{j}^{R}\leq p_{j+1}^{L}$. (Note that the reason the proxies $p_{j}^{R}$ and
$p_{j+1}^{L}$ do not “cross over” is because the step size $\Delta$ is chosen
as the _difference_ in widths of the intervals.) Thus, overall, we have that
$p_{j}^{R},p_{j+1}^{L}\in[b_{j}+\varepsilon,b_{j+1}-\varepsilon]$, which means
that the proxies $p_{j}^{R}$ and $p_{j+1}^{L}$ are contained in the interval
$I_{j}$. This, in turn, implies that the favorite candidates of these proxies,
namely $\texttt{top}(p_{j}^{R})$ and $\texttt{top}(p_{j+1}^{L})$, are
contained in $\mathcal{C}_{j}$. Since all candidates within $\mathcal{C}_{j}$
are $\theta$-close, we get that
$|\texttt{top}(v)-\texttt{top}(p^{v})|\leq\theta$, as desired.

The reason why $p^{v}\in\\{p_{j}^{R},p_{j+1}^{L}\\}$ holds is also similar to
that in the proof of Theorem 2. Indeed, voter $v$ prefers the leftmost
candidate in $\mathcal{C}_{j}$ over any candidate in
$\mathcal{C}_{1}\cup\dots\cup\mathcal{C}_{j-1}$, and prefers the rightmost
candidate in $\mathcal{C}_{j}$ over any candidate in
$\mathcal{C}_{j+1}\cup\dots\cup\mathcal{C}_{t+1}$. Since the proxy bisectors
coincide with the candidate bisectors, it follows that voter $v$ is closer to
the proxy $p^{R}_{j-1}$ than to any other proxy to its left, and is closer to
the proxy $p^{L}_{j}$ than to any other proxy to its right. Thus, voter $v$’s
closest proxy must be either $p^{R}_{j-1}$ or $p^{L}_{j}$, i.e.,
$p^{v}\in\\{p^{R}_{j-1},p^{L}_{j}\\}$.

We will now show that the total number of proxies is
$|\mathcal{P}|\leq\frac{3}{2}\lceil\frac{1}{\theta}\rceil$. First, observe
that the total number of bisectors computed by the algorithm is
$t\leq\lfloor\frac{1}{\theta}\rfloor$. This is because for any $j\in[t]$, the
reference candidates for the intervals $I_{j}$ and $I_{j+1}$ are separated by
a distance strictly greater than $\theta$ (Line 3), and the distance between
the extreme candidates is equal to $1$. Next, observe that there is no pair of
consecutive intervals $I_{j}$ and $I_{j+1}$ with two proxies each, since at
least one of these four proxies will be absorbed during the expansion step in
Phase 2 (Lines 3 and 3). Therefore, any pair of adjacent intervals together
contain at most three proxies, resulting in the bound
$\frac{3}{2}\lfloor\frac{1}{\theta}\rfloor$ on the total number of proxies.
Finally, in the special case when there is only one bisector (i.e., when
$t=1$), we have exactly two proxies, and the bound
$\frac{3}{2}\lceil\frac{1}{\theta}\rceil$ is satisfied for any given
$\theta\in(0,1)$. ❑

Although Theorem 4 provides an absolute upper bound on the number of proxies,
this number could, in general, be much larger than the _optimal_ number of
proxies for the instance at hand. Indeed, in an instance with two candidates
located at the endpoints of $[0,1]$ and $\theta=0.01$, the bound in Theorem 4
evaluates to $150$, even though it is clear that two proxies suffice.
Corollary 2 shows that Algorithm 3 never uses more than three times the
optimal number of proxies for the given instance.

######  Corollary 2.

Algorithm 3 is a $3$-approximation algorithm for Proxy Voting.

For any fixed $\alpha\in[0,1]$, we say that an algorithm is an _$\alpha$
-approximation algorithm_ for Proxy Voting if, given any instance
$\mathcal{I}$ as input, it terminates in polynomial time and returns a
$\theta$-representative arrangement of at most
$\alpha\cdot\texttt{opt}(\mathcal{I})$ proxies.

###### Proof.

(of Corollary 2) Recall that the Voronoi cell $V_{i}$ of candidate
$c_{i}\in\mathcal{C}$ is the set of all voter locations $v\in[0,1]$ for which
$\texttt{top}(v)=c_{i}$. Let us define the _segment_ $S_{i}$ associated with
the candidate $c_{i}$ as the union of Voronoi cells of all candidates that are
$\theta$-close to $c_{i}$, i.e.,
$S_{i}\coloneqq\cup_{\ell\in[m]:|c_{\ell}-c_{i}|\leq\theta}V_{\ell}$. It is
easy to see that if a voter is located at $c_{i}$ (i.e., $v=c_{i}$), then
under a $\theta$-representative proxy arrangement, its closest proxy must be
located in $S_{i}$ (i.e., $p^{v}\in S_{i}$).

Let $\mathcal{I}=\langle\mathcal{C},\theta\rangle$ denote a given instance of
Proxy Voting, and let $\texttt{opt}(\mathcal{I})$ denote the optimal number of
proxies in any $\theta$-representative proxy arrangement in $\mathcal{I}$. Let
$c_{i_{1}},c_{i_{2}},\dots,c_{i_{t}}$ denote the set of candidates from left
to right that are chosen as reference candidates during Phase 1 of Algorithm
3. Additionally, let $S_{i_{1}},\dots,S_{i_{t}}$ denote the corresponding
segments.

We will argue that the alternate segments, namely
$S_{i_{1}},S_{i_{3}},\dots,S_{i_{t}}$ (if $t$ is odd) or
$S_{i_{1}},S_{i_{3}},\dots,S_{i_{t-1}}$ (if $t$ is even), are disjoint.
(Stated differently, the set of alternate segments constitutes an independent
set of the underlying interval graph.) Note that this would imply that
$\texttt{opt}(\mathcal{I})\geq\lceil\frac{t}{2}\rceil$ since, by the above
observation, any $\theta$-representative proxy arrangement must have a proxy
in each segment. We know from the proof of Theorem 4 that the total number of
proxies under Algorithm 3 is at most $\frac{3}{2}$ times the number of proxy
bisectors computed by the algorithm in Phase 1. Thus, with $t$ bisectors,
Algorithm 3 uses at most $\frac{3}{2}t$ proxies, which gives the stated
approximation guarantee.

To see why the alternate segments are disjoint, fix any $\ell\in[t]$ and
consider the segments $S_{i_{\ell}}$, $S_{i_{\ell+1}}$, and $S_{i_{\ell+2}}$.
Since the candidates $c_{i_{\ell}}$ and $c_{i_{\ell+1}}$ are chosen as
reference candidates in consecutive iterations, we have that
$c_{i_{\ell+1}}>c_{i_{\ell}}+\theta$, and therefore $c_{i_{\ell+1}}$ (and any
candidate to its right) is not included in the segment $S_{i_{\ell}}$. For a
similar reason, the candidate $c_{i_{\ell+1}}$ (and any candidate to its left)
is excluded from the segment $S_{i_{\ell+2}}$, implying that $S_{i_{\ell}}$
and $S_{i_{\ell+2}}$ are disjoint, as desired. ❑

##  13 Proof of Proposition 3

See 3

###### Proof.

We first prove the proposition when $r$ is a strict-Condorcet rule, where the
tie-breaking mechanism favors the leftmost alternative. The proof for the
other tie-breaking mechanism is similar.

For any preference profile $P$ with odd number of voters, let $\bar{v}$ denote
the location of $P$’s median voter(s). Let $p^{P}=\\{p^{v}:v\in P\\}$ denote
the proxy profile. It is well-known that the top choice of $\bar{v}$ is the
Condorcet winner (see, e.g., Congleton, 2002), which means that $r(P)$ is the
candidate that is closest to $\bar{v}$, i.e. $\texttt{top}(\bar{v})$.
Therefore, it suffices to prove that
$r(p^{P})=\texttt{top}(p^{\overline{v}})$, or in other words, $p^{\bar{v}}$ is
the median of $p^{P}$. This follows after the fact that for any voter
$v^{\prime}\in P$ such that $v^{\prime}\leq\bar{v}$ (respectively,
$v^{\prime}\geq\bar{v}$), we must have $p^{v^{\prime}}\leq p^{\bar{v}}$
(respectively, $p^{v^{\prime}}\geq p^{\bar{v}}$).

For any preference profile $P$ with even number of voters, it is possible to
have two median voters, whose locations are denoted by
$\bar{v}_{1}<\bar{v}_{2}$, respectively. It follows that the weak Condorcet
winners are $\\{\texttt{top}(\bar{v}_{1}),\texttt{top}(\bar{v}_{2})\\}$, and
in case the set contains more than one candidate, according to the tie-
breaking mechanism, the leftmost candidate $\texttt{top}(\bar{v}_{1})$ wins.
Therefore, it suffices to prove that $r(p^{P})=\texttt{top}(p^{\bar{v}_{1}})$.
Similar to the case with odd number of voters, it is not hard to verify that
the median locations of $p^{P}$ are $\\{p^{\bar{v}_{1}},p^{\bar{v}_{2}}\\}$.
In case the set contains two locations, according to the tie-breaking
mechanism, $\texttt{top}(p^{\bar{v}_{1}})$ will be chosen as the winner. This
completes the proof. ❑