Multiwinner Elections under Minimax Chamberlin-Courant Rule in Euclidean Space

1 Introduction

Multiwinner elections are a classical problem in social science where the goal is to choose a fixed number of candidates, also called a winning committee, based on voters' preferences. The problem encapsulates a number of applications that range from choosing representatives in democracies to staff hiring and procurement decisions [Lu and Boutilier, 2011; Goel et al., 2019; Skowron et al., 2016]. Many facility location problems in operations research and public goods planning are equivalent to multiwinner elections: facilities are candidates and users are voters [Betzler et al., 2013].

One of the central computational problems in this area is to design algorithms for computing a winning committee with provable guarantees of representation quality. In particular, let V be a set of n voters, C a set of m candidates, and k the size of the winning committee, for a positive integer k. We focus on ordinal preferences where each voter v ranks all the candidates in C, from the most preferred (rank 1) to the least preferred (rank m). Elections under ordinal preferences are widely studied because in many settings, the rank ordering of candidates is both natural and easier to determine than a precise numerical value (cardinal preference) [Brandt et al., 2016; Endriss, 2017; Munagala et al., 2021]. We let σv(c) denote the rank of candidate c in v's list, and use Chamberlin-Courant voting rule [Chamberlin and Courant, 1983] for evaluating the score of a committee. In the simplest version, also called 1-Borda, a voter v's score for a committee T is the rank of its most preferred committee member: σv(T) = minc∈T σv(c). (In a generalized form called r-Borda, which we also consider, the score is the sum of the ranks of the r most preferred candidates in T.) This scoring function is often called the misrepresentation score to emphasize that we want to minimize it-more preferred candidates have smaller ranks.

The goal of a multiwinner election is to find a sizek committee T ⊆ C that optimizes some function g(σv1 (T), . . . , σvn (T)) of all the voter's scores. Two classical choices for g are the sum and the max. The former is the utilitarian objective and seeks to minimize the sum of the scores over all the voters. The latter is the egalitarian objective and minimizes the maximum (worst) of the scores over all the voters. Both versions of the multiwinner elections are NP-hard under general preferences [Lu and Boutilier, 2011; Betzler et al., 2013], and as a result, an important line of research has been to examine natural settings with structured preference spaces [Betzler et al., 2013; Yu et al., 2013; Skowron et al., 2015b; Elkind et al., 2017b].

Our paper studies one such setting-and arguably one of the most natural-namely, the Euclidean space of preferences. The geometry of Euclidean space gives an intuitive and interpretable positioning of voters and candidates in many natural settings such as spatial voting and facility locations, but it also has important computational advantages: when candidates and voters are embedded in d-space, only a tiny fraction of all (exponentially many) m! candidate orderings are realizable. In particular, the maximum number of realizable rankings is only (polynomially bounded) O(md+1 ). This important combinatorial property enables us derive much better bounds than what is possible in completely unstructured preferences spaces. Specifically, we explore algorithmic and hardness questions for minimax (egalitarian) multiwinner elections using the 1-Borda and r-Borda rules under ordinal Euclidean preferences. In this setting, voters and candidates are embedded in a d-dimensional Euclidean space, implicitly specifying each voter's ranking (closest to farthest) of the candidates. The goal is to choose a committee of k candidates minimizing the rank of the worst voter's most preferred candidate.

Remark: There are good reasons for using ordinal preferences even when cardinal distances are implied by an Euclidean embedding. The first is robustness: consider a voter v and two candidates c, c′ . If their distances satisfy d(v, c) < d(v, c′ ), then clearly v prefers c to c′ , but it seems harder to argue that v's preference varies linearly (or even smoothly) with distance-for instance, would doubling the distance really halve the value to a voter? Another reason is that k-center solutions based on cardinal preferences are highly susceptible to the outlier effect-a few outlying voters may control the minimax value (i.e., radius) of the optimal solution even though all other voters have significantly better solution quality. By contrast, under the ordinal measure the (rank-based) solution seems more equitable because outliers are matched with a highly ranked candidate (irrespective of the distances).

1.1 Our Results

Our work shows that a number of interesting and encouraging approximation results are possible for Euclidean preferences, thus, offering new directions for research. Indeed, quoting [Elkind et al., 2017b], "multidimensional domain restrictions offer many challenging research questions, but fast algorithms for these classes are very desirable." A brief summary of our main results is the following:

1. We show that the Euclidean minimax committee problem is NP-hard in every dimension d ≥ 2; in one dimension, the problem is easy to solve optimally with dynamic programming. The complexity of this problem, also called the ordinal Euclidean k-center problem, was not known and had been an important folklore problem. Our proof shows that the problem also hard to approximate in the worst-case (see Theorem 2), which stands in sharp contrast with the 2-approximability of the cardinal k-center problem [Kleinberg and Tardos, 2006].
2. We then show a number of efficient approximation results for the problem, starting with a polynomial time algorithm to compute a size-k committee with a minimax score of O(m/k) for any instance in dimension d = 2, and score of O((m/k) log k) for any instance in dimension d ≥ 3. These scores are also shown to be essentially the best possible in worst-case.
3. Our next approximation uses the bicriterion framework to design a polynomial time algorithm that achieves the optimal minimax score σ⋆ possible for a size-k committee by constructing slightly larger committee, namely, of size (1 + ϵ)k for d = 2 and size O(k logm) for d ≥ 3. (We also show that increasing the committee size by an additive constant is not sufficient.)
4. Our final approximation combines ordinal and cardinal features of the problem in a novel way, as follows. Suppose the optimal score of the k committee is σ⋆ , and d⋆v is the distance of v to its rank σ⋆ candidate. We define a committee T to be δ-optimal if each voter has a representative in T within distance δd⋆v . (That is, for each voter the committee contains a candidate whose distance to the voter is almost as good as distance to its σ∗ rank candidate.) We show that a δ-optimal committee can be

computed in polynomial time for δ = 3, but unless P = NP, there is no polynomial-time algorithm to compute δ-optimal committees for any δ < 2.

Due to limited space, we defer some of the proofs to the full version of this work [Sonar et al., 2022].

2 RelatedWork

The literature on multi-winner elections is too large to summarize in this limited space; hence, we mostly survey the computational results closely related to our work. For a general introduction to multi-winner elections, we refer the reader to the works of [Elkind et al., 2017a; Faliszewski et al., 2017; Faliszewski et al., 2019]. The work of [Aziz et al., 2018] studies the computational complexity and axiomatic properties of various egalitarian committee scoring rules under the general preferences. For computing a winning committee under the Chamberlin-Courant rule, polynomial-time algorithms are known only for restricted preferences such as single-peaked, single-crossing, 1D Euclidean, etc. [Betzler et al., 2013; Skowron et al., 2015b; Elkind et al., 2017b]. Very little is known about the more general d-dimensional Euclidean setting considered in our paper with the exception of a work of [Godziszewski et al., 2021], which shows NPhardness for the approval set voting rule for the utilitarian objective in 2-dimensional Euclidean elections.

Constant factor approximations are often easier to achieve under the utilitarian objective. For instance, [Munagala et al., 2021] present several nearly-optimal approximation bounds; [Skowron et al., 2015a] presents a constant factor approximation for minimizing the weighted sum of ranks of the winning candidates; and [Byrka et al., 2018] presents a constant factor approximation for minimizing the sum when σv(c) is an arbitrary cardinal value. In contrast, for the minimax objective, mostly inapproximability results are known, and only under general preferences [Skowron et al., 2015a].

3 Preliminaries

Throughout the paper, an election is a pair E = (C, V ), where C = {c1, . . . , cm} is the candidate set and V = {v1, . . . , vn} is the voter set. The preference list of each voter is a total ordering (ranking) of C, in which the most preferred candidate has rank 1 and the least preferred candidate has rank m.

We call an election E = (C, V ) a d-Euclidean election if there exists a function f : C ∪ V → Rd , called a Euclidean realization of E, such that for any pair ci, cj ∈ C, a voter v prefers ci to cj if and only if dist(f(v), f(ci)) < dist(f(v), f(cj)) where dist(·, ·) denotes the Euclidean distance (in case the candidates are equidistant, we break the ties arbitrarily). We assume that a Euclidean realization is part of the input; the decision problem of whether an election admits an Euclidean realization is computationally hard [Peters, 2017].

We use σv(c) to denote the rank of candidate c in v's preference list, and use the Chamberlin-Courant voting rule [Chamberlin and Courant, 1983] for evaluating the score of a committee. In particular, a voter v's score for a committee T is the rank of its most preferred committee member

σv(T) = minc∈T σv(c), and the Euclidean minimax committee problem is to choose a committee of size k that minimizes the maximum score (misrepresentation) of any voter. That is, minimize the following:

So the optimal committee score is always between 1 and m. (We mainly focus on this simpler 1-Borda scoring function, but some of our results also hold for the generalized r-Borda, as mentioned later.)

4 Hardness Results

We first show that the Euclidean minimax committee problem is NP-hard in any dimension d ≥ 2. After that, we extend our proof to show that the problem is even hard to approximate within any sublinear factor of m, where m is the number of candidates in the election.

Our hardness reduction uses the NP-complete problem PLANAR MONOTONE 3-SAT (PM-3SAT) [de Berg and Khosravi, 2010]. An instance of PM-3SAT consists of a monotone 3-CNF formula ϕ where each clause contains either three positive literals or three negative literals, and a special "planar embedding" of the variable-clause incidence graph of ϕ described below. In the embedding, each variable/clause is drawn as a (axis-parallel) rectangle in the plane. The rectangles for the variables are drawn along the x-axis, while the rectangles for positive (resp., negative) clauses lie above (resp., below) the x-axis. All the rectangles are pairwise disjoint. If a clause contains a variable, then there is a vertical segment connecting the clause rectangle and the variable rectangle. Each such vertical segment is disjoint from all the rectangles except the two it connects. We call such an embedding a rectangular embedding of ϕ. See Figure 1 for an illustration. Given ϕ with a rectangular embedding, the goal of PM-3SAT is to decide if there exists a satisfying assignment for ϕ.

Suppose we are given a PM-3SAT instance consisting of the monotone 3-CNF formula ϕ with a rectangular embedding. Let X = {x1, . . . , xn} be the set of variables and Z = {z1, . . . , zm} be the set of clauses of ϕ (each of which consists of three literals). We construct (in polynomial time) a Euclidean minimax committee instance (E, k) in R2 such that ϕ has a satisfying assignment if and only if for the election E there exists a committee of size k with score at most 4. We begin by modifying the rectangular embedding of ϕ

to another form that we call an orthogonal embedding. The details of the modifications are explained in the full version, but the resulting embedding satisfies the following three conditions: (i) no vertical segment crosses a horizontal segment; (ii) each horizontal segment s intersects exactly three vertical segments which correspond to the three variables contained in the clause corresponding to s; and (iii) the endpoints of all segments are connection points.

By properties (ii) and (iii), there are three connection points on each clause segment, two of which are the left and right endpoints of the segment, and we call the middle one the reference point of the clause. We denote by ˆx1, . . . , ˆxn the reference points of the variables x1, . . . , xn and denote by ˆ z1, . . . , ˆ zm the reference points of the clauses z1, . . . , zm. By shifting/scaling the segments properly without changing the topological structure of the orthogonal embedding, we can further guarantee that the x-coordinates (resp., y-coordinates) of the vertical (resp., horizontal) segments are distinct even integers in the range {1, . . . , 2n} (resp., {-2m, . . . , 2m}). Therefore, all the connection points now have integral coordinates (which are even numbers) and the entire embedding is contained in the rectangle [1, 2n]×[-2m, 2m]. Points on the segments of the orthogonal embedding that have integral coordinates partition each segment s into ℓ(s) unit-length segments, where ℓ(s) is the length of s. We call these unit-length segments the pieces of the orthogonal embedding. Let N be the total number of pieces. Clearly, N = O(nm).

Our Euclidean minimax committee instance (E, k) consists of the following set of voters and candidates in the twodimensional plane. (In fact, in our construction, each point is both a candidate and a voter, namely, C = V . It is easy to modify the construction so that the set of voters is much larger by simply making multiple copies of each voter.)

Variable gadgets. For each variable xi, we choose four points near the reference point ˆxi as follows. There are two (vertical) pieces incident to ˆxi in the orthogonal embedding, one above ˆxi, the other below ˆxi. On each of the two pieces, we choose two points with distances 0.01 and 0.02 from ˆxi, respectively. We put a candidate and a voter at each of the four chosen points, and call these candidates/voters the xigadget. We construct gadgets for all x1, . . . , xn. The total number of candidates/voters in the variable gadgets is 4n.

Clause gadgets. The second set of candidates/voters are constructed for the clauses z1, . . . , zm. For each clause zi, we put a candidate and a voter at the reference point ˆ zi, and call this candidate/voter the zi-gadget. The total number of candidates/voters in the clause gadgets is m.

Piece gadgets. The last set of candidates/voters are constructed for connecting the variable gadgets and the clause gadgets. Consider a piece s of the orthogonal embedding, which is a unit-length segment. We distinguish the two endpoints of s as s- and s+ as follows. If s is a vertical piece above (resp., below) the x-axis, let s- be the bottom (resp., top) endpoint of s and s+ be the top (resp., bottom) endpoint of s. If s is a horizontal piece, then it must belong to the horizontal segment of some clause zi. If s is to the left (resp., right) of the reference point ˆ zi, let s- be the left (resp., right) endpoint of s and s+ be the right (resp., left) endpoint of s.

For every piece s that is not adjacent to any clause reference point, we choose four points on s with distances 0.49, 0.8, 0.9, 1 from s- (i.e., with distances 0.51, 0.2, 0.1, 0 from s+), respectively. We put a candidate and a voter at each of the four chosen points, and call these the candidates/voters of the s-gadget. Note that we do not construct gadgets for the pieces that are adjacent to some clause reference point. Thus, the total number of candidates/voters in the piece gadgets is 4(N-3m), as each clause reference point is adjacent to three pieces.

By combining these three constructed gadgets, we obtain our election E = (C, V ) instance with 4N + 4n - 11m candidates and voters. The size of the committee is k = N + n - 3m. We now prove that E has a committee of size k with score ≤ 4 iff ϕ is satisfiable.

The "if" part. Suppose ϕ is satisfiable and let π : X → {true, false} be an assignment which makes ϕ true. We construct a committee T ⊆ C of size k as follows. Our committee T contains one candidate in each variable gadget and each piece gadget (this guarantees |T| = k as the total number of variable and piece gadgets is k). Consider a variable xi. By our construction, the xi-gadget contains four candidates which have the same x-coordinates as ˆxi. If π(xi) = true (resp., π(xi) = false), we include in T the topmost (resp., bottommost) candidate in the xi-gadget. Now consider a piece s that is not adjacent to any clause reference point. We first determine a variable as the associated variable of s as follows. If s is vertical, then the associated variable of s is just defined as the variable whose vertical segment contains s. If s is horizontal, then s must belong to the horizontal segment of some clause zj . In this case, we define the associated variable of s as the variable whose vertical segment intersects the left (resp., right) endpoint of the horizontal segment of zj if s is to the left (resp., right) of the reference point ˆ zj. Let xi be the associated variable of s. If π(xi) = true, then we include in T the candidate in the s-gadget that has distance 1 (resp., 0.9) from s- if s is above (resp., below) the x-axis. Symmetrically, if π(xi) = false, then we include in T the candidate in the s-gadget that has distance 1 (resp., 0.9) from s- if s is below (resp., above) the x-axis. This finishes the construction of T. The following lemma completes the "if" part of our proof.

Lemma 1. The score of T in the election E is at most 4.

The "only if" part. Suppose there exists a size-k committee T ⊆ C with score at most 4. We use that committee to construct a satisfying assignment π : X → {true, false}. We first note the following property of the committee T .

Lemma 2. T contains exactly one candidate in each variable gadget and exactly one candidate in each piece gadget.

We note that the total number of variable and piece gadgets is k. Since |T | = k, using Lemma 2, we conclude that T has no budget to contain any candidate in the clause gadgets.

Corollary 1. T contains no candidate in the clause gadgets.

Recall that each variable gadget contains four candidates, two of which are above the x-axis while the other two are below the x-axis. Consider a variable xi. By Lemma 2, T

contains exactly one candidate in the xi-gadget. If that candidate is above (resp., below) the x-axis, we set π(xi) = true (resp., π(xi) = false). We show that π is a satisfying assignment of ϕ. It suffices to show that every positive (resp., negative) clause of ϕ contains at least one variable which is mapped to true (resp., false) by π. We only consider positive clauses, as the proof for negative clauses is similar. We need the following property of T .

Lemma 3. Let s be a piece above the x-axis that is not adjacent to any clause reference point, and suppose xi is the associated variable of s. If T contains the candidate in the s-gadget with distance 1 from s-, then π(xi) = true.

The rest of the argument to complete the "only if" part of our proof includes showing that for any positive clause zi, π maps at least one variable of zi to true. Due to limited space, we skip the details in the full version of the paper.

Finally, the reduction can clearly be done in polynomial time, and so we have established the following result.

Theorem 1. Euclidean minimax committee is NP-hard in all dimensions d ≥ 2. This claim holds even if the voter and candidate sets are identical.

In fact, our construction also rules out the possibility of a PTAS as it is hard to decide in polynomial time whether the minimum score is ≤ 4 or ≥ 5. By slightly modifying the proof, we can also show that even computing an approximation for Euclidean minimax committee within any sublinear factor of |C| is hard.

Theorem 2. For any constant ϵ > 0, it is NP-hard to achieve a |C|1-ϵ -approximation for Euclidean minimax committee in Rd for any d ≥ 2.

5 Approximately-Optimal Committees

We now complement the hardness results of the previous sections with nearly-optimal approximation algorithms.

5.1 Approximation Using ϵ-nets

Our first algorithm computes in polynomial-time a sizek committee of minimax score O(m/k) for d = 2 and O((m/k) log k) for d ≥ 3. Our algorithm uses the notion of ϵ-nets, which are commonly used in computational geometry [Toth et al., 2017] for solving set cover and hitting set problems. Let us first briefly describe this notion.

Let X be a finite set of points in Rd and let R be a set of ranges (subsets of X) in Rd . A subset A ⊆ X is called an ϵ-net of (X,R) if A intersects all those ranges in R that are ϵ-heavy, i.e., they contain at least an ϵ-fraction of the points in X. In other words, A is an ϵ-net for (X,R) if A∩R ̸= ∅ for any R ∈ R with |R ∩ X| ≥ ϵ|X|. There exists an ϵ-net of size O( 1ϵ ) for ranges defined by disks in R2 , and of size O( 1ϵ log 1ϵ ) for ranges defined by balls in Rd , for any constant dimension d ≥ 3 [Toth et al., 2017]. In both cases, ϵ-nets can be computed in polynomial time.

Building on this result, we now present our algorithm.

Theorem 3. Given a d-Euclidean election E = (C, V ), we can compute in polynomial time a size k committee with minimax score O(m/k) for d = 2 and score O((m/k) log k) for d ≥ 3, where m = |C|.

Proof. In order to convey the intuition more clearly, let us first show how to find an O(k)-size committee with score at most ⌈(m/k) log k⌉. Given a d-Euclidean election, let C be the set of the m candidates with their embedding in Rd . For each voter v, we consider a d-dimensional ball Rv centered at v containing the ⌈(m/k) log k⌉ closest points of C to v. Let R be the set of all these balls. Each ball of R is ϵ-heavy for ϵ = log k/k because it contains an ϵ-fraction of the m candidates. Therefore, in polynomial time we can find an ϵnet T ⊆ C for (C,R) of size O( 1ϵ log 1ϵ ) = O(k). By the definition of ϵ-net, T contains at least one point from each Rv, and thus points of T form a committee of size O(k) with minimax score ⌈(m/k) log k⌉.

To reduce the committee size to k while increasing the score by only a constant factor, we enlarge each ball Rv to include the α(m/k) log k closest candidates of v, for an appropriate constant α. Each ball is now ϵ′ -heavy, for ϵ′ = α log k/k, which guarantees an ϵ′ -net T ⊆ C for (C,R) of size O( 1 ϵ′ log 1 ϵ′ ) = O(k/α). With an appropriate choice of α, we can ensure |T| ≤ k and achieve the score of α(m/k) log k = O((m/k) log k).

When d ≤ 2, the ϵ-nets of this set system have size O( 1ϵ ), and therefore we can construct a committee of size k with score O(m/k).

The O((m/k) log k) and O(m/k) bounds of Theorem 3 are essentially the best possible. In particular, we can construct instances of Euclidean elections in which no sizek committee can achieve the minimax score better than Ω(m/k).

Theorem 4. For any d ≥ 1, there exist Euclidean elections in Rd such that any committee T ⊆ C of size k has score Ω(m/k), where m = |C|.

On all the instances where C ⊆ V (note that most representative elections do satisfy this condition because each candidate is also a voter), we can show that any committee has score Ω(m/k). In this case, the algorithm in Theorem 3 gives a constant factor approximation.

5.2 Approximation by Relaxing the Committee Size

The hardness result of Theorem 2 rules out any efficient algorithm for Euclidean election with a good approximation guarantee but only under the rigid constraint that the committee size is at most k. In this section, we study the problem in the setting where we are allowed to relax the committee size. Specifically, we ask the following natural question: Can we efficiently compute a committee of size slightly larger than k whose score is close to the optimal score of a size-k committee?

First, we show that if we are allowed to increase the committee size by a (small) multiplicative factor, then one can achieve (or improve) the optimal score of a size-k committee.

Theorem 5. Given a d-Euclidean election, we can compute in polynomial time a committee of size (1 + ϵ)k, given any fixed ϵ > 0, when d = 2 and of size O(k logm), where m is the number of candidates, when d ≥ 3, whose score is smaller than or equal to the score of any size-k committee.

Proof. We prove the result for a Euclidean election E = (C, V ) in d = 2; the proof for higher dimensions is similar. Suppose we know that the optimal size-k committee of E has score σ⋆ . We show how to compute a committee of size (1 + ϵ)k whose score is at most σ⋆ . For each voter v ∈ V , we consider the smallest disk Rv centered at v containing its closest σ⋆ candidates in C. Let R = {Rv : v ∈ V }. A hitting set of the set system (C,R) is a subset H ⊆ C such that H ∩ R ̸= ∅ for all R ∈ R. If a committee has score at most σ⋆ , then it must be a hitting set of (C,R), and since there is a size-k committee with score σ⋆ , the minimum hitting set of (C, R) has size at most k. By using the PTAS for disk hitting set [Mustafa and Ray, 2010], we can compute a hitting set for (C, R) of size (1+ϵ)k, which is the desired committee. Since we do not know the value of σ⋆ , we simply try all values from 1 to m, and pick the smallest one for which we have a hitting set of size (1 + ϵ)k.

In higher dimensions, we can apply the same approach. The only difference is that we do not have a PTAS for ball hitting set in Rd for d ≥ 3. But we can apply the greedy hitting set algorithm to compute a hitting set of size O(k logm) if a size-k hitting set exists. Therefore, the above algorithm computes a committee of size O(k logm) whose score is at most the score of any size-k committee.

On the other hand, we prove that if we can only increase the committee size by an additive constant, we are not able to achieve any good approximation for the minimax score. (The proof of this theorem is a minor modification of Theorem 2 and is presented in the full version of the paper.)

Theorem 6. Let α, ϵ > 0 be constants. Given a Euclidean election E = (C, V ) in Rd for d ≥ 2 and a number k ≥ 1, it is NP-hard to compute a committee of size k +α whose score is at most |C|1-ϵ · σ⋆ , where σ⋆ is the minimum score of a size-k committee.

5.3 Minimax Committees for the r-Borda Rule

A natural generalization of the Chamberlin Courant rule is the so-called r-Borda rule where the score of each voter is determined by its nearest r candidates in the committee for a given r ≤ k. More specifically, the score of a voter v with respect to a committee is the sum of the ranks of its nearest r candidates in the committee in the preference list of v. The minimax score of a committee T is the maximum over all voter scores. Our goal is to find a committee T of size k that minimizes σ(T ), where

We show that for any election E = (C, V ) in Rd , we can compute a size-k committee with an r-Borda score of O((r2m/k) log k) using a modification of the algorithm in Theorem 3. In R2 , the score of the committee can be further improved to O(r2m/k) using the same approach with ϵ-nets of size O(1/ϵ) for disks. Thus, we have the following result.

Theorem 7. Given an election in any fixed dimension d, we can find in polynomial time a size-k committee with minimax r-Borda score O((r2m/k) log k). Furthermore, if d ≤ 2, the score can be further improved to O(r2m/k).

We observe that the bound O(r2m/k) in the above theorem is tight. In particular, there are instances for which an optimal committee's r-Borda score is Ω(r2m/k)-this can be verified using the instance described in the proof of Theorem 4-and so this serves as the benchmark score for rBorda.

5.4 δ-Optimal Committees

In the previous section, we showed that for any instance we can find a minimax committee of optimal score if we increase the committee size by a small (multiplicative) factor. In this section, we suggest an alternative way to assess the approximation quality while keeping the committee size k.

To introduce this criterion, let us consider an election E = (C, V ) and suppose the optimal score of a size-k committee is σ⋆ . In our approximation, we are looking for a size-k committee in which the candidate closest to each voter v ∈ V has rank not much larger than σ⋆ in the preference list of v. Our hardness proof shows that in general this is not possible because there may be many candidates at roughly the same distance from v, but with a large difference in ranks, and any polynomial time algorithm is bound to end up with a bad minimax score for some v. A natural way to get rid of this pathological situation is to treat two candidates with roughly the same distance from v as if they have similar ranks.

With this motivation, we introduce the following δoptimality criterion. We say a committee T ⊆ C of size k is δ-optimal, for δ ≥ 1, if for each voter v ∈ V the distance from v to its closest candidate in T is at most δ times the distance from v to its rank-σ⋆ candidate.

We now show how to compute a 3-optimal committee in polynomial time for any d-Euclidean election. Let E = (C, V ) be a Euclidean election and k ≥ 1 be the desired committee size. For convenience, let us first assume that the optimal score σ⋆ of a size-k committee of E is known. For each voter v ∈ V , define d⋆v as the distance from v to the rank-σ⋆ candidate in the preference list of v. We say a voter v is satisfied with a subset T ⊆ C if there exists a candidate c ∈ T such that dist(c, v) ≤ 3d⋆v . We denote by S[T ] ⊆ V the subset of voters satisfied with T. Then a committee T ⊆ C (of size k) is 3-optimal if every v ∈ V is satisfied with T. Our algorithm begins with an empty committee T = ∅ and iteratively adds new candidates to T using the following three steps until S[T ] = V :

1. ˆ v ← arg minv∈V \S[T ] d⋆v .
2. ˆ c ← a candidate within distance d⋆ˆ v from ˆ v.
3. T ← T ∪ {ˆ c}.

In words, in each iteration, we find the unsatisfied voter ˆ v with the minimum d⋆ˆ v , and then add to T a (arbitrarily chosen) candidate ˆ c ∈ C within distance d⋆ˆ v from ˆ v. The algorithm terminates when S[T] = V , and so all voters are satisfied with T at the end.

We only need to show that |T| ≤ k; if |T| < k, we can always add extra candidates while keeping all voters satisfied. Consider an optimal size-k committee Topt = {c1, . . . , ck}, with score σ⋆ , and let Vi ⊆ V be the subset of voters whose closest candidate in Topt is ci. Thus, V1, . . . , Vk form a partition of V . We say two voters v, v′ ∈ V are separated if they belong to different Vi's.

Suppose our algorithm terminates in r iterations. We will show that r ≤ k. Let ˆ vj (resp., ˆ cj) be the voter ˆ v (resp., the candidate ˆ c) chosen in the j-th iteration, and let Tj be the committee T at the beginning of the j-th iteration. We claim the following property of our greedy algorithm.

Lemma 4. The voters ˆ v1, . . . , ˆ vr are pairwise separated.

Thus, the voters ˆ v1, . . . , ˆ vr belong to different Vi's, which implies that r ≤ k and |T | = r ≤ k, proving the correctness of our algorithm.

Finally, notice that in our algorithm we assumed σ⋆ is known, but this assumption is easy to get rid of. We can try each possible value from 1 to m = |C|, and choose the smallest number σ⋆ ∈ [m] for which the algorithm returns a committee of size at most k. Thus, we proved the following.

Theorem 8. Given a Euclidean election E = (C, V ) in any dimension and k ≥ 1, one can compute a 3-optimal committee of size k in polynomial time.

Complementary to the above algorithmic result, we can also show the following hardness result.

Theorem 9. For any δ < 2, unless P=NP, there is no polynomial time algorithm to compute a δ-optimal committee of size k for a given Euclidean election in Rd for d ≥ 2.

6 Closing Remarks

We studied the multiwinner elections in Euclidean space under minimax Chamberlin-Courant voting rules. First, we settle the complexity of the problem by showing it is NP-hard for dimensions d ≥ 2 (in contrast, the problem is known to be polynomial time solvable in 1d), but our main contribution is presenting several attractive (& nearly-optimal) approximation bounds which are elusive in the general setting. We believe that our algorithms are robust and will generalize to many other interesting questions, for instance, most of our algorithmic results (except for Thm. 5) extend to the recently studied egalitarian k-median rules [Gupta et al., 2021] when considered for the Euclidean elections.

Our work suggests many natural directions, including resolving the complexity and approximation bounds for other important voting rules, such as the utilitarian variant of the CC rule and the general class of OWA rules [Skowron et al., 2015a; Skowron et al., 2016] for the Euclidean elections. Investigating the parameterized complexity of the problems we considered is also an interesting question since natural parameters such as the committee size or the number of candidates are small in many real-world elections. Another interesting avenue is to explore Euclidean elections when the positions of voters and candidates are only approximately known, for instance, each placed at some unknown point in a disk. Such data uncertainty naturally exists in many real-world applications.