# representative_proxy_voting__dbffa333.pdf

Representative Proxy Voting

Elliot Anshelevich,1 Zack Fitzsimmons,2 Rohit Vaish,3 Lirong Xia1

1 Rensselaer Polytechnic Institute, Troy, New York, USA 12180 2 College of the Holy Cross, Worcester, Massachusetts, USA 01610 3 Tata Institute of Fundamental Research, Mumbai, India 400005 {eanshel,xial}@cs.rpi.edu, zﬁtzsim@holycross.edu, rohit.vaish@tifr.res.in

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 ﬁnd a set of proxies that is θrepresentative, which entails that for any voter located anywhere on the line, its favorite candidate is within a distance θ 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 ﬁxed in advance, or even be ﬁnite. 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 θ-representative set, thus showing that a relatively small number of proxies is enough to capture the preferences of any set of voters. An additional beneﬁcial property of a θ-representative proxy arrangement is that for strict-Condorcet voting rules, the outcome of proxy voting is similarly close to the outcome of direct voting.

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 θ for any collection of voters. We call our arrangement θ-representative since each voter s closest proxy is guaranteed to have a top preference that is within θ of the voter s. This can be interpreted as providing a set of allowed votes identiﬁed 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 difﬁcult to determine exactly, or perhaps they are not static and change over time). The goal

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

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., Schoﬁeld 2008 for a survey on spatial voting). We focus our results on the onedimensional 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 θ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, Sandomirskiy, and Tennenholtz 2020 and the references therein).

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.1

We ﬁrst provide algorithms for computing an optimal θ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 θ-representative, for any possible set of candidates and voters. Because of this, we also prove upper and lower bounds on the number of proxies

1Our results also hold if the possible proxy locations are more general, as long as they include all candidate locations as a subset.

The Thirty-Fifth AAAI Conference on Artificial Intelligence (AAAI-21)

Restrictions on proxies Bounds on the number of proxies Computational

Upper bound Lower bound Results

On top of candidates (Restricted) 2 1

θ opt in poly time

(Theorem 2) (Proposition 1) (Theorem 1)

Anywhere within R (Unrestricted)

θ opt in poly time

(Theorem 4) (Proposition 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 θ for a θ-representative proxy arrangement. The rightmost column contains the computational results for optimal proxy arrangements.

needed to have a θ-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 θ 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 θrepresentative arrangement with θ 3

k (Corollary 1).

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

Related Work Alger (2006) introduce a general proxy voting model where there is a ﬁxed 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, Mackenzie, and Procaccia 2018; G olz 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, Sandomirskiy, and Tennenholtz 2020; Magdon-Ismail and Xia 2018). Besides having a θ-representative proxy arrangement, we observe that for Condorcet-consistent voting rules, our results guarantee that the proxy-voting outcome is within θ of the direct-voting outcome. This notion of a θ-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, Krishnaswamy, and Munagala 2017; Abramowitz, Anshelevich, and Zhu 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 deﬁned 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 ﬁnding a representative set of proxies.

Preliminaries

For any natural number s N, let [s] := {1, . . . , s}. Our model involves three types of entities candidates, voters, and proxies which are described below.

Candidates: Let C = {c1, . . . , cm} denote a set of m N candidates that are arranged on a line segment [0, 1]. We will overload notation to denote the position of the ith candidate also by ci [0, 1]. We will assume throughout that the extreme candidates are located at the endpoints of [0, 1] (i.e., c1 = 0 and cm = 1), and that all candidates have distinct locations (i.e., for any distinct i, j [m], ci = cj). For any pair of adjacent candidates ci and ci+1, their candidate bisector is the vertical line at (ci + ci+1)/2. Notice that with m candidates, there can, in general, be 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 identiﬁed by its location. For any voter v [0, 1], its favorite candidate, denoted by top(v), is the candidate that is closest to it. That is, top(v) := arg minci C |v ci|, where ties are broken according to any ﬁxed directionally consistent tiebreaking rule (see Deﬁnition 1). Note that we do not assume the set of voters to be ﬁxed in advance. This is because our

results apply to any arbitrary collection of voters that could be located anywhere within [0, 1]. Deﬁnition 1 (Directionally consistent tie-breaking rule). A tie-breaking rule is a function τ : [0, 1]3 [0, 1] that maps any triple v, x, y [0, 1] as follows:

τ(v, x, y) =

x if |v x| < |v y| y if |v x| > |v y| either x or y otherwise.

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 τ is directionally consistent if, for any ﬁxed v [0, 1], either τ always tiebreaks to the left of v or always to the right of v (the choice of direction could depend on v). That is, for any ﬁxed v [0, 1], either τ(v, x, y) = x for all x, y [0, 1] such that x v y and |v x| = |v y|, or τ(v, x, y) = y for all x, y [0, 1] such that x v y and |v x| = |v y|. For any candidate ci C, its Voronoi cell Vi denotes the set of all voter locations v [0, 1] whose favorite candidate is ci, i.e., Vi := {v [0, 1] : top(v) = ci}. Notice that the Voronoi cells V1, . . . , Vm induce a partition of the line segment [0, 1].

Proxies: Our model also includes a ﬁnite set P of proxies whose role is to vote on behalf of the voters. Speciﬁcally, each voter v delegates its vote to its nearest proxy, denoted by pv := arg minp P |v p|. Each proxy p R then votes for its favorite candidate, denoted by top(p), which is deﬁned as the candidate closest to it, i.e., top(p) := arg minci C |p ci|. As before, ties are broken according to a directionally consistent tie-breaking rule (see Deﬁnition 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 deﬁne what it means for a proxy arrangement to be representative. The deﬁnition is stated in terms of a parameter θ [0, 1] that corresponds to a distance threshold. We will ﬁnd it convenient to call two points x, y [0, 1] to be θ-close if |x y| θ, and call them θ-far otherwise. Given any θ [0, 1], we say that a proxy arrangement is θ-representative if for every voter location, the favorite candidate of the voter is θ-close to the favorite candidate of its closest proxy. Deﬁnition 2 (θ-representative proxy arrangement). An arrangement of proxies is θ-representative if for any voter v [0, 1], its favorite candidate is θ-close to the favorite candidate of its nearest proxy. That is, for every v [0, 1], |top(v) top(pv)| θ. 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 satisﬁed 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 θ-representative for some large θ, 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 deﬁne the central problem studied in this paper. Deﬁnition 3 (PROXY VOTING). An instance of the PROXY VOTING problem I = C, θ is speciﬁed by a set of candidates C in [0, 1] and a parameter θ (0, 1). The goal is to compute an arrangement of proxies that is θ-representative for every location v [0, 1].2

We once again stress that a θ-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. 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 Deﬁnition 3 can be formalized as a decision as well as an optimization problem. The decision version asks whether, given an instance I and a natural number k N, there exists a θrepresentative proxy arrangement for I consisting of at most k proxies. The optimization version asks whether, given an instance I, the optimal θ-representative proxy arrangement for I can be computed in polynomial time. An arrangement of k proxies is optimal for instance I if there is no other arrangement of k 1 or fewer proxies that is θ-representative. We will write opt(I) to denote the number of proxies in any optimal θ-representative arrangement for the instance I. To make the computational problem meaningful, we will assume throughout that all candidate locations in C and the parameter θ are rational.

Basic Properties and Examples Let us start by discussing some of the issues that arise when constructing θ-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 I = C, θ denote an instance with a pair of adjacent candidates ci and ci+1 that are θ-far. Let P be any proxy arrangement such that none of the bisectors between adjacent proxies in P coincides with the bisector between ci and ci+1. Then, P is not θ-representative for I.

Proof. Let p1, . . . , pk denote the proxies in P. Among all proxy bisectors between adjacent proxies, let the one be-

2We exclude the degenerate corner cases of θ = 0 and θ = 1 from the deﬁnition. Indeed, if θ = 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, θ = 1 involves placing a single proxy anywhere in [0, 1].

tween pj and pj+1 be closest to the candidate bisector between ci and ci+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., ci+ci+1

2 < pj+pj+1

2 . Let d := min{ pj+pj+1

2 , ci+1} ci+ci+1

2 and observe that d > 0.

ci ci+1 v R v L

Figure 1: Failure of θ-representation when none of the proxy bisectors between adjacent proxies coincides with the candidate bisector between θ-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 ( ci+ci+1

2 d, ci+ci+1

2 ) and v R ( ci+ci+1

2 , ci+ci+1

2 + d). Notice that the favorite candidates of v L and v R are ci and ci+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., pv L = pv R = pj. Then, regardless of the favorite candidate of pj, θ-representation must be violated for at least one of v L or v R. K

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 θ-representative arrangement, as shown by Example 1 below. 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 θ-representative). Suppose we are given some θ (0, 1) and a budget of k N proxies. We will construct an instance where evenly spacing these k proxies, i.e., placing the proxies at ℓ k 1 for every ℓ {0, 1, . . . , k 1}, fails to be θ-representative (we will assume, without loss of generality, that k 2). Notice that the bisectors between adjacent proxies are located at 2ℓ 1 2(k 1) for every ℓ [k 1].

Consider a sufﬁciently small ε > 0 such that [θ, θ + ε] [ ℓ 1

k 1, ℓ k 1] for some ℓ [k 1]. Note that such a choice of ε must exist since θ (0, 1). Pick a rational point x (θ, θ + ε) \ i [ℓ]{ 2i 1

k 1 }. Consider an instance with three candidates c1, c2, and c3 that are placed at 0, x, and 1, respectively. Notice that c1 and c2 are θ-far, and that the bisector between c1 and c2, 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 θ-representative.

We will now describe our results for restricted and unrestricted positioning of proxies.

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 θ-representative.

Algorithm for Computing Optimal Number of Restricted Proxies Our ﬁrst result for restricted positioning (Theorem 1) shows that a θ-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 the full version of the paper (Anshelevich et al. 2020). Theorem 1 (Optimal proxy arrangement under restricted positioning). There is a polynomial-time algorithm that, given any instance C, θ of PROXY VOTING as input, terminates in polynomial time and returns an optimal θ-representative proxy arrangement satisfying restricted positioning.

Upper and Lower Bounds for Restricted Positioning of Proxies Although the optimum number of proxies can be computed efﬁciently, these algorithms do not provide any insight into how many proxies are actually necessary in order to be θ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 θrepresentation. Theorem 2 (Upper bound under restricted positioning). Given any instance C, θ of PROXY VOTING, there exists a θ-representative proxy arrangement satisfying restricted positioning that consists of at most 2( 1

θ 1) proxies if 1

θ N, and at most 2 1

θ proxies otherwise. Furthermore, such an arrangement can be computed in polynomial time.

Proof Sketch. The detailed proof of Theorem 2 is presented in the full version of the paper (Anshelevich et al. 2020). Here, we will describe the main steps in our algorithm by means of the example shown in Figure 2a.

c1 c2 c3 c4 c5

θ ε 2θ θ + ε

(a) An instance of PROXY VOTING. c1 c2 c3 c4 c5

(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 Anshelevich et al. 2020) computes a set of proxy bisec-

tors between adjacent proxies, according to the following strategy. Starting from the leftmost candidate as the reference, the bisector between the furthest θ-close and the closest θ-far candidates from the reference on the right is chosen as the ﬁrst proxy bisector. (In Figure 2b, this is the bisector between c2 and c3.) 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 c3 is the reference in the next iteration, the furthest θ-close candidate from c3 on the right is c3 itself, and c4 is the closest θ-far candidate. Therefore, the proxy bisector is chosen as the candidate bisector between c3 and c4.) This process repeats until the rightmost candidate cm either becomes a reference or is θ-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 1

θ , and therefore the number of proxies is at most 2 1

θ . The θ-representation of this proxy arrangement follows from the fact that all candidates between consecutive proxy bisectors are θ-close. K

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

Proposition 1 (Lower bound under restricted positioning). Given any θ (0, 1), there exists an instance for which any θ-representative proxy arrangement under restricted positioning requires at least 2( 1

θ 1) proxies if 1 θ N, and 2 1

θ proxies otherwise.

Proof. Let p N denote the unique positive integer such that 1

p θ < 1 p 1. Observe that p 1 equals 1

θ 1 when 1 θ N, and equals 1

θ otherwise. Therefore, it sufﬁces to show that any θ-representative arrangement requires 2p 2 proxies. Our construction of the lower bound instance will depend on whether p is even or odd. Speciﬁcally, let ε := 1 (p 1)θ

5(p 1)/2 (if p is odd) or ε := 1 (p 1)θ

(5p/2 3) (if p is even), and observe that ε > 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.

c1 c2 c3 c4 c5 c6 c7

θ + ε ε θ + ε 2ε θ + ε ε

c1 c2 c3 c4 c5 c6 c7 c8 c9

θ + ε ε θ + ε 2ε θ + ε ε θ + ε 2ε

Figure 3: Lower bound instance in Proposition 1 when 1

3 (top) and 1

4 (bottom).

The instance consists of the candidate c1 on the left, followed by a sequence of pairs of candidates {c2i, c2i+1} for i N such that each pair is at a distance of θ + ε from the preceding pair, and the gap between the candidates in each

pair alternates between ε and 2ε (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 θ + ε, ε, θ + ε, 2ε, θ + ε, ε and so on. The rightmost candidate is c2p 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 {c1, c2}, {c3, c4}, {c5, c6}, and so on are each θ-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 θ-representative proxy arrangement is required to place proxies on every candidate except for the last candidate c2p 1 (see Anshelevich et al. 2020 for a detailed argument). This implies that any θ-representative proxy arrangement for the above instance requires at least 2p 2 proxies. K

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, Example 2 shows that the separation between the two models can be strict.

Example 2 (Unrestricted positioning uses fewer proxies than restricted). Fix θ = 1

3 and let ε > 0 be sufﬁciently small. Consider the instance shown in Figure 4 consisting of four candidates c1 = 0, c2 = 1

3 + ε, c3 = 2

3 ε, and c4 = 1. Notice that the adjacent candidate pairs {c1, c2} and {c3, c4} are θ-far. Thus, by the contrapositive of Lemma 1, any θ-representative proxy arrangement must have bisectors between adjacent proxies that coincide with the candidate bisectors between these pairs.

c1 c2 c3 c4

θ + ε θ 2ε θ + ε c1 c2 c3 c4

θ + ε θ 2ε θ + ε

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 θ-representative proxy arrangement must place proxies on all candidates, using four proxies in total (see top ﬁgure in Figure 4). By contrast, under unrestricted positioning, there exists a feasible proxy arrangement that only uses three proxies, namely p1 = 1

6+ε, p2 = 0.5, and p3 = 7

6 + ε (see bottom ﬁgure 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 ﬁrst 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.

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 C, θ of PROXY VOTING as input, terminates in polynomial time and returns an optimal θ-representative proxy arrangement.

The proof of Theorem 3 is technically the most involved part of the paper and is presented in (Anshelevich et al. 2020). Here we will outline a brief sketch of the proof.

Proof Sketch. For any ﬁxed k [m], our algorithm decides whether there exists a feasible (i.e., θ-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 P = {p1, . . . , pk}, let us deﬁne the Voronoi cell Wj of proxy pj as the set of all locations of voters whose closest proxy is pj, i.e., Wj := {v [0, 1] : |v pj| |v pℓ| for any ℓ = j}, where ties are broken according to a directionally-consistent tie-breaking rule (Deﬁnition 1). Notice that v Wj if and only if pj = pv. At a high level, the algorithm uses dynamic programming to compute the set of feasible locations (or the feasibility set) of the proxy pj+1 using the feasibility set of the preceding proxy pj. It maintains the property that for each point s in the feasibility set of proxy pj+1, there exists some point s < s in the feasibility set of proxy pj such that θ-representation is satisﬁed for all voters in Wj (see Anshelevich et al. 2020 for a formal characterization result). Such a pair of locations {s , s} is said to be mutually feasible. To begin with, the feasibility set F 1 of the leftmost proxy p1 is initialized as the union of the Voronoi cells of all candidates that are θ-close to the leftmost candidate c1, along with the region ( , 0).3 This corresponds to the set of all positions of the leftmost proxy such that θ-representation is satisﬁed for the leftmost voter. The feasibility set F j+1 of the proxy pj+1 is computed using F j as follows: Consider the restriction of F j to the Voronoi cell of candidate ch (denoted by F j,h), as illustrated by the interval [x, y] in Figure 5 (thus, top(pj) = ch). 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 ci. Let bh denote the candidate bisector between the furthest θ-close and closest θ-far candidates to the right of ch. Similarly, let bi denote the candidate bisector between the furthest θ-close and closest θ-far candidates to the left of ci. By our characterization result, it follows that any point z 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 bh (namely, x ). This is because the proxy bisector between pj and pj+1 has to be (weakly) to

3Recall from Example 2 that proxies can lie outside [0, 1] in an optimal arrangement under unrestricted positioning.

the left of bh. Similarly, z must be (weakly) to the right of the mirror image of point y about the bisector bi (namely, y ). The contribution of the set [x, y] to F j+1,i is given by Vi [y , x ]. In general, the restriction F j,h could comprise of several disjoint intervals. In the full version of the paper (Anshelevich et al. 2020), we describe how the feasibility set F j+1 can nevertheless be efﬁciently computed.

ch ci bi bh

x y y x θ θ

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 θ-close to the rightmost candidate cm along with the region (1, ). If yes, then there exists a feasible location of the proxy pk that is θ-representative for the rightmost voter. By the aforementioned property, there must exist a feasible location pk 1 of the previous proxy such that pk 1 and pk are mutually feasible, thus implying θ-representation for the voters in Wk 1. Similarly, there must exist a feasible location of the proxy pk 2 that is mutually feasible with pk 1, and so on. Continuing backwards in this manner, we obtain a set of proxy locations p1, . . . , pk wherein the adjacent pairs are mutually feasible, which immediately implies θ-representation. On the other hand, the absence of an overlap certiﬁes that with k proxies, there is no θ-representative proxy arrangement in the given instance. K

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 the full version of the paper (Anshelevich et al. 2020), and instead revisit the example from Figure 2 considered previously in the restricted case. Our algorithm proceeds in two phases. The ﬁrst 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 ﬂexibility of the unrestricted setting via an expand and merge step. Speciﬁcally, 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.

c1 c2 c3 c4 c5

Collision Collision

Figure 6: Illustrating the execution of the algorithm in Theorem 4 on a toy example. The initial and the ﬁnal proxy locations are shown as empty and solid red circles, respectively.

By construction, all candidates within each interval are θ-close. Furthermore, since each voter is in the same interval as its closest proxy, θ-representation is satisﬁed for all voters. By an analysis similar to that in Theorem 2, it follows that the number of proxy bisectors is at most 1

θ . The expand-and-merge step ensures that no two consecutive intervals can have two proxies each. This readily implies the desired bound of 3

θ for the number of proxies.

Theorem 4 (Upper bound under unrestricted positioning). Given any instance C, θ of PROXY VOTING as input, there exists a θ-representative arrangement consisting of at most 3

θ 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 θ. Indeed, given as input a budget of k > 1 proxies, we can invoke our algorithm with θ = 1/ 2k

3 . Then, by Theorem 4, we know that the proxy arrangement returned by the algorithm is 1/ 2k

3 -representative and uses at most 3

θ k proxies, which is within the given budget. Corollary 1 formalizes this observation.

Corollary 1 (Upper bound on θ). There is a polynomialtime algorithm that, given any positive integer k N as input, returns an arrangement of at most k proxies that is 1/ 2k

3 -representative.

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

Proposition 2 (Lower bound under unrestricted positioning). Given any θ (0, 1), there exists an instance such that any θ-representative proxy arrangement requires at least 1

Proof. Deﬁne θ (0, 1) as follows:

( 1 p 1, if θ = 1

p for some positive integer p 1 p, if 1 p+1 < θ < 1

p for some positive integer p.

Observe that θ > θ. Consider an instance where the candidates are evenly spaced at a distance of θ , as shown in Figure 7. Notice that the total number of candidates is m = 1

θ . Since any pair of adjacent candidates are θ-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

c1 c2 c3 cm 1 cm ...

Figure 7: Lower bound on the number of proxies under unrestricted positioning (Proposition 2)

nearest proxy must then be strictly greater than θ, which violates θ-representation. Thus, m proxies are necessary, which gives the desired bound. K

Representative Election Outcomes So far, we have focused on achieving θ-representation for each individual voter. A natural question is whether the voting outcome by proxies is a good representation of the direct voting outcome. This is formally deﬁned as follows. Deﬁnition 4. An arrangement of proxies is said to be θrepresentative under a voting rule r, if for any preference proﬁle P [0, 1]n, r(P) is θ-close to r({pv : v P}). In Deﬁnition 4, r(P) is the outcome of direct voting and {pv : v P} is the multiset of proxy votes. It turns out that θ-representation of an arrangement implies θ-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 θrepresentative, then it is θ-representative under the rule r. In light of Proposition 3, all θ-representation results proved in this paper (see Table 1) naturally extend to θrepresentation under strict-Condorcet rules. The proof of Proposition 3 is presented in (Anshelevich et al. 2020).

Concluding Remarks In this paper, we gave efﬁcient algorithms for computing optimal sets of θ-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 [0, 1], its closest proxy is within a distance θ, in addition to them being θ-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 θ-representative proxies in more general metric spaces. More generally, it would be interesting to expand the scope of θ-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 CCF1527497 and CCF-2006286. RV acknowledges support from ONR#N00014-171-2621 while he was afﬁliated 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. LX acknowledges support from NSF #1453542 and #1716333, ONR #N00014-171-2621, and a gift fund from Google. 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, B.; Anshelevich, E.; and Zhu, W. 2019. Awareness of Voter Passion Greatly Improves the Distortion of Metric Social Choice. In Proceedings of the 15th International Conference on Web and Internet Economics, 3 16.

Abramowitz, B.; and Mattei, N. 2019. Flexible Representative Democracy: An Introduction with Binary Issues. In Proceedings of the 28th International Joint Conference on Artiﬁcial Intelligence, 3 10.

Alger, D. 2006. Voting by Proxy. Public Choice 126(1-2): 1 26.

Anshelevich, E.; Bhardwaj, O.; Elkind, E.; Postl, J.; and Skowron, P. 2018. Approximating Optimal Social Choice under Metric Preferences. Artiﬁcial Intelligence 264: 27 51.

Anshelevich, E.; Fitzsimmons, Z.; Vaish, R.; and Xia, L. 2020. Representative Proxy Voting. ar Xiv preprint ar Xiv:2012.06747 .

Black, D. 1948. On the Rationale of Group Decision Making. Journal of Political Economy 56(1): 23 34.

Brill, M.; and Talmon, N. 2018. Pairwise Liquid Democracy. In Proceedings of the 27th International Joint Conference on Artiﬁcial Intelligence, 137 143.

Cohensius, G.; Mannor, S.; Meir, R.; Meirom, E.; and Orda, A. 2017. Proxy Voting for Better Outcomes. In Proceedings of the 16th Conference on Autonomous Agents and Multiagent Systems, 858 866.

Feldman, M.; Mansour, Y.; Nisan, N.; Oren, S.; and Tennenholtz, M. 2020. Designing Committees for Mitigating Biases. In Proceedings of the Thirty-Fourth AAAI Conference on Artiﬁcial Intelligence, 1942 1949.

Goel, A.; Krishnaswamy, A. K.; and Munagala, K. 2017. Metric Distortion of Social Choice Rules: Lower Bounds and Fairness Properties. In Proceedings of the 2017 ACM Conference on Economics and Computation, 287 304.

G olz, P.; Kahng, A.; Mackenzie, S.; and Procaccia, A. D. 2018. The Fluid Mechanics of Liquid Democracy. In Proceedings of the 14th International Conference on Web and Internet Economics, 188 202.

Green-Armytage, J. 2015. Direct Voting and Proxy Voting. Constitutional Political Economy 26(2): 190 220. Kahng, A.; Mackenzie, S.; and Procaccia, A. 2018. Liquid Democracy: An Algorithmic Perspective. In Proceedings of the 32nd AAAI Conference on Artiﬁcial Intelligence, 1095 1102. Kempe, D. 2020. Communication, Distortion, and Randomness in Metric Voting. In Proceedings of the 34th AAAI Conference on Artiﬁcial Intelligence, 2087 2094. Magdon-Ismail, M.; and Xia, L. 2018. A Mathematical Model For Optimal Decisions In A Representative Democracy. In Advances in Neural Information Processing Systems, 4702 4711. Meir, R.; Sandomirskiy, F.; and Tennenholtz, M. 2020. Representatitve Committees of Peers. Technical Report ar Xiv:2006.07837 [cs.GT], ar Xiv.org. Mirrlees, J. 1971. An Exploration in the Theory of Optimum Income Taxation. The Review of Economic Studies 38(2): 175 208. Pivato, M.; and Soh, A. 2020. Weighted Representative Democracy. Journal of Mathematical Economics 88: 52 63. Procaccia, A.; and Rosenschein, J. 2006. The Distortion of Cardinal Preferences in Voting. In Proceedings of the 10th International Workshop on Cooperative Information Agents, 317 331. Schoﬁeld, N. 2008. The Spatial Model of Politics. Number 95 in Routledge Frontiers of Political Economy. New York: Routledge. Skowron, P. 2015. What Do We Elect Committees For? A Voting Committee Model for Multi-Winner Rules. Proceedings of the 24th International Joint Conference on Artiﬁcial Intelligence 1141 1147.