Tight Approximation for Proportional Approval Voting

1 Introduction

We study multiwinner approval-based voting rules called Thiele rules [Brill et al., 2018] that were introduced by Thorvald Thiele [1895]. 1 Versions of Thiele rules have been used for distribution of seats within parties in Swedish parliamentary elections [Janson, 2016]. In recent years, Thiele rules regained interest in social choice community as a class of natural voting rules generalizing such well known multiwinner voting rules as Approval Chamberlin-Courant [Chamberlin and Courant, 1983; Procaccia et al., 2008; Skowron and Faliszewski, 2017] or Proportional Approval Voting [Thiele, 1895; Kilgour, 2010; Aziz et al., 2015; Byrka et al., 2018].

Thiele rules. w-THIELE rule is parameterized by a nonincreasing non-negative sequence w = (w1,w2, . . . ). Utility of a voter from a committee is increasing with the number of approved winners and it obeys the law of diminishing marginal utility known in economics (also called Gossen's First Law). The increase is defined by the weights in w.

1 The original paper was written in Danish, but there is a detailed survey in English [Janson, 2016].

Specifically, utility of a voter from a committee in which he or she approves j candidates is equal to ∑ji=1 wi. w-THIELE rule is purely utilitarian: the goal is to find a committee of k candidates that maximizes the total utility of the voters under the sequence of weights w.

When w is a constant sequence, the problem trivially admits a polynomial time algorithm. Such a voting rule is called Single Non-Transferable Vote (SNTV) [Faliszewski et al., 2018] and it is a generalization of a single-winner voting rule called Plurality Voting into multiwinner setting (every voter approves only the most favorite candidate, and the winners are k candidates with the highest support). All other Thiele rules are NP-hard [Skowron et al., 2016, Theorem 5]. Hence, they have been studied in terms of approximability [Skowron et al., 2016], parameterized complexity [Bredereck et al., 2020] and specific sequences of weights were considered [Kilgour, 2010; Aziz et al., 2015; Skowron and Faliszewski, 2017; Lackner and Skowron, 2019].

Related works. The simplest w-THIELE rule has w = (1, 0, 0, . . . ) which is known as the Max k-Coverage problem (or Approval Chamberlin-Courant in social choice theory [Procaccia et al., 2008; Skowron and Faliszewski, 2017]). Nemhauser et al. [1978] provided a greedy algorithm that finds (1 - 1/e)-approximate solution for Max k-Coverage. This has been shown to be tight unless P = NP [Feige, 1998]. Recently, Cohen-Addad et al. [2019] and Manurangsi [2020] showed this is tight even in FPT time with respect to k. In particular, the latter showed that, assuming the Gap Exponential Time Hypothesis (Gap-ETH) 2 , any (1 - 1/e + ϵ)- approximation algorithm for Max k-Coverage must run in time at least (n+m)Ωϵ(k) . This means that a brute-force algorithm checking all possible subsets of size k (runs in O⋆ (mk )) is essentially best possible, if one insists on achieving any approximation ratio better than (1 - 1/e).

Recently, Barman et al. [2020] gave an (1 - ℓℓ eℓ ℓ! )-approximation algorithm for the Multi l-Coverage problem which is tight assuming the Unique Games Conjecture. Multi ℓCoverage is equivalent to w-THIELE rule with wℓ(i) =

2 Gap-ETH states that, for some constant δ > 0, there is no 2o(n) - time algorithm that, given n-variable 3-SAT formula, can distinguish whether the formula is fully satisfiable or that it is not even (1 - δ)-satisfiable. Gap-ETH is a standard assumption in proving FPT hardness of approximation (see e.g. [Chalermsook et al., 2017]).

(1, 1, . . . , 1, 0, 0, . . . ) (i.e., ℓ ones followed by zeros). In fact, Barman et al.'s result holds also for general utilities (not only approval based). This means they provide a tight improved approximation for the ℓ-best OWA problem [Skowron et al., 2016] (improving previous best (1 - 1/e)-approximation).

Our contribution. Our main result (Theorem 1) is a tight αw-approximation algorithm for a natural class of "geometrically dominant" w-THIELE rules, where αw is a sequencedependent constant defined in (1). Resulting approximation ratios for selected w-THIELE rules are presented in Table 1.

Theorem 1. Let w be any geometrically dominant sequence such that limi→∞wi = 0. There exists a polynomial time αw-approximation algorithm for w-THIELE rule, and it is NP-hard to compute (αw + ϵ)-approximate solution for any constant ϵ > 0. Furthermore, assuming Gap-ETH, we cannot achieve (αw + ϵ)-approximation even in f(k) · no(k) -time.

The algorithm is a simple application of a well known linear programming rounding technique called pipage rounding due to Ageev and Sviridenko [2004]. Our contribution is an analysis of this algorithm for w-THIELE rules (Section 3). Pipage rounding gives a better ratio than (1 - 1/e) for a large class of w-THIELE rules with w being "geometrically dominant" (intuitively, this means that w "decreases slower than" a geometric sequence; for a formal definition, please refer to Section 2). Our algorithm can be extended by replacing cardinality constraint (choosing k winners) into matroid constraint due to Theorem 2. Our proof of the hardness of approximation (Section 4) largely follows the proof of (1 - 1/e + o(1))- inapproximability of Max k-Coverage of Feige [1998] by reducing from the Label Cover problem. We remark that our result is based on the P ̸= NP assumption in contrast to Barman et al.'s result [2020] which assumes the Unique Games Conjecture. As a consequence of our result, w-THIELE rule is APX-hard whenever marginal utility goes to 0 and, assuming Gap-ETH, no FPT-approximation scheme exists (wrt. parameter k). Additionally, we provide a family of hard instances for the standard greedy algorithm on which our LP-based algorithm works better (Theorem 18).

Applications. Multiwinner elections has practical implications not only in committee [Skowron et al., 2016] or parliamentary elections (apportionment seats in parliament) [Brill et al., 2018]. Thiele rules with a knapsack constraint (instead of cardinality constraint k) can be considered as participatory budgeting model [Fluschnik et al., 2019; Talmon and Faliszewski, 2019]. Multiwinner elections can model many realworld issues in which we need to choose some number of elements. In such scenarios, approximation algorithms seem to have clear motivation. For more discussion on using approximation and randomized algorithms in collective decision making, we refer the reader to, e.g., [Skowron et al., 2016; Byrka et al., 2018; Cygan et al., 2018].

Organisation of the paper. In Section 2 we define additional notations that will be used throughout. In Section 3 we describe the algorithm and provide the proof of its approximation guarantee. In Section 4 we prove our hardness of approximation result. All the proofs omitted due to space restrictions will be available in the full version of this paper.

2 Preliminaries

An approval-based election E = (V,C, {Av}v∈V ) consists of a set V of n voters, a set C of m candidates, and, for each voter v ∈ V , a set Av ⊆ C of candidates approved by v. The w-THIELE rule is parameterized by an infinite-dimensional non-increasing non-negative sequence w = (w1,w2, . . . ); the w-THIELE score (total utility) of a subset W ⊆ C is defined as scrEw(W) := ∑v∈V ∑|Av∩W| i=1 wi. The goal of an optimization problem called w-THIELE rule is to find a set W ⊆ C of k candidates that maximizes its w-THIELE score.

For notational convenience, we assume throughout that w1 = 1. 3 Furthermore, for brevity, the sequence w is henceforth assumed to be non-negative and non-increasing.

We say that a sequence w (and its corresponding wTHIELE rule) is geometrically dominant if for every i ∈ N, wi · wi+2 ⩾ w2 i+1 . It follows that if w is geometrically dominant then either w = (1, 0, 0, . . . ) or wi wi+1 ⩾ wi+1 wi+2 for all i ∈ N. All Thiele rules in Table 1 satisfy these properties.

We use Poi(·),Ber(·),Bin(·, ·) to denote the Poisson, Bernoulli and Binomial random variables respectively.

For a sequence w, we let αw denote

In words, αw is the expected utility of a voter if the number of elected candidates that he/she approves, is distributed as Poisson distribution with mean one.

3 Approximation Algorithm

In this section, we describe our algorithm and argue that it gives αw-approximate solution, thereby proving the algorithmic part of Theorem 1. Our algorithm is based on an LP rounding technique, which requires us to first define scrEw also on a fractional solution x ∈ [0, 1]C specifying for each candidate fractionally, how much the candidate is selected.

where xAv = ∑c∈Av xc. Intuitively, for each voter v this function adds the first xAv elements of the sequence w. The last element of the sequence may be counted in only fractionally. With this definition, we now compute the optimum fractional solution x∗ of the following linear program.

To round x∗ , we will employ a framework called pipage rounding [Ageev and Sviridenko, 2004]. Specifically, we resort to the following result of C˘alinescu et al. 4

3 This is w.l.o.g. since, as long as w1 ̸= 0, we may scale sequence w by any constant factor without effecting the approximation ratio.

4 Applying the theorem directly results in a randomized algorithm. A way to construct a deterministic algorithm is described in the full version of this paper.

Theorem 2 (C˘alinescu et al. [2011, Lemma 3.5]). Let f be a monotone, submodular function and a polytope B(M) be described by matroid constraints. Given vector y∗ = argmax{f(x) | x ∈ B(M)} the procedure PipageRounding(M, y∗ ) will return a solution S ∈ M of value E[f (S)] ⩾ Eˆ y∼y∗ [f (ˆ y)] where ˆ y ∼ y∗ means a random vector with each coordinate ˆ yi independently chosen to be 1 with probability y∗ i or 0 otherwise.

The function scrEw is submodular (because w is nonincreasing) and monotone (because w is non-negative). We can thus use Theorem 2 to round the optimum LP solution x∗ . The resulting approximation ratio is then equal to

The remainder of this section is dedicated to bounding ρ.

Let the approximation ratio of a voter v be ρv := Eˆx∼x∗ [scrEw (ˆx,v)] scrEw (x∗ ,v) where scrEw(x, v) is the score of v, i.e., ∑|Av | l=1 wk · min {1, max {0, xAv - l + 1}}. Henceforth, we will focus on a single voter v and show that ρv ⩾ αw. This straightforwardly implies that ρ ⩾ αw as desired.

We next characterize x∗ that minimizes the ratio ρv, which in the end will lead us to the claimed bound.

Step 1: Three-Valued x∗

Let τ = x∗Av = ∑c∈Av x∗c be a sum of x∗ values for candidates approved by v. The score of the fractional solution x∗ is now scrEw(x∗ , v) = w1 + · · · + w⌊τ⌋ + {τ} · w⌊τ⌋+1. 5

The numerator Eˆx∼x∗ [scr Ew(ˆx, v)] of ρv can be written as

We recall the following lemma due to Barman et al.

Lemma 3 (Barman et al. [2020] 6 ). Let x ∈ [0, 1]m be such that x1 +· · ·+xm = τ . Then, for any non-negative sequence (a1, a2, . . . ), there exist q ∈ (0, 1) and x′ ∈ {0, q, 1}m such that ∑i x′i = τ and ∑l (al Pˆx∼x [∑mi=1 ˆxi = l]) ⩾ ∑l (al Pˆx∼x′ [∑mi=1 ˆxi = l]).

5 {x} := x - ⌊x⌋ is a fractional part of a number x.

6 In [Barman et al., 2020, Lemma 2.5], τ is required to be an integer. It is however obvious from the proof that this is not necessary.

Now, notice that the denominator scrEw(x∗ , v) in our ratio ρv only depends on the sum τ = ∑c∈Av x∗c and not the way values are distributed among x∗c 's. Hence, from Lemma 3, ρv is minimised by x∗ that only takes three values-0, q and 1, although we do not yet know what the value of q is.

Step 2: Getting Rid of Ones

Let w(x) be a function w : R⩾0 → R⩾0 extending w, defined by w(x) := w⌊x⌋ · (1-{x})+w⌊x⌋+1 ·{x}. Clearly, when x is integral w(x) = wx. For fractional x, the function just takes the weighted average of w⌊x⌋,w⌊x⌋+1.The following observation is straightforward (as w is geometrically dominant).

Observation 4. The function w is convex.

Using this observation, we can prove the following lemma, which allows us to only consider x∗ that does not contain 1.

Lemma 5. Suppose x∗˜ c = 1 for a candidate ˜ c ∈ Av. Then the approximation ratio for the voter v decreases after removing ˜ c from the fractional solution x∗ . Formally, if x∗˜ c = 1, then

Hence, the fractional solution x∗ that minimizes the ratio ρv of a single voter only has values 0 and q where q ∈ (0, 1).

Step 3: Comparing Binomial and Poisson

The values {x∗c }c∈Av are now all either 0 or q and sum up to τ. It means that, when we sample ˆx ∼ x∗ , we now are performing τ/q coin tosses with an identical coin with bias q. The value of our integral solution which is equal to ∑l (wl · Pˆx∼x∗[∑c ˆxc ⩾ l]) can be now rewritten as ∑l (wl · P[Bin(τ/q, q) ⩾ l]) = E[w1+· · ·+wBin(τ/q,q)].

Let sw(n) = w1 + · · · +wn. The function sw is monotone (as w is non-negative) and concave (as w is non-increasing). We recall another lemma by Barman et al.

Lemma 6 (Barman et al. [2020, Lemma 2.3]). For any convex function f, any integer N ⩾ 1 and parameter p ∈ [0, 1] we have E[f(Bin(N, p))] ⩽ E[f(Poi(Np))].

By applying the above lemma with the function s-w(x) = -sw(x) which is convex, we get the following inequality E[w1 + · · · +wBin(τ/q,q)] ⩾ E[w1 + · · · +wPoi(τ)] and hence

Step 4: Changing the Mean of Poisson

A property of Poisson distributions is that sampling Xi ∼ Poi(λi) for i = 1, . . . ,m and adding them is equivalent to sampling Y ∼ Poi(∑i λi). Hence, E[w1 + · · · + wPoi(τ)]

We can bound each term in (3) as follows.

Lemma 7. For any l ∈ {1, . . . , ⌊τ⌋}, we have

Putting together (2), (3), Lemmas 7 and 8 allows us to conclude that the ratio ρv is at least

which is equal to E[w1 + · · · + wPoi(1)] = αw since w1 = 1. Hence, our algorithm yields an αw-approximate solution.

4 Hardness of Approximation

We next prove the hardness of approximation (second part of Theorem 1). Our proof largely follows the proof of (1-1/e+ o(1))-inapproximability of Max k-Coverage of Feige [1998]. Specifically, we reduce from the Label Cover problem:

Definition 9. A Label Cover instance L = (A,B,E, [L], [R], {π}e∈E ) consists of a bi-regular bipartite graph (A,B, E), alphabet sets [L], [R] and, for every edge e ∈ E, a constraint πe : [L] → [R].

A labelling of L is a function φ : A → [L]. We say that φ satisfies a right vertex v ∈ B if, for every two neighbours u, u′ of v, we have π(u,v)(φ(u)) = π(u′ ,v)(φ(u′ )). The value of φ, denoted by val(φ), is defined as the fraction of right vertices satisfied by φ. Moreover, we say that φ weakly satisfies a right vertex v ∈ B if there exist two distinct neighbours u, u′ of v such that π(u,v)(φ(u)) = π(u′ ,v)(φ(u′ )). Similarly, we define the weak value of φ, denoted by weak-val(φ), as the fraction of right vertices weakly satisfied by φ. We use val(L) (resp. weak-val(L)) to denote the maximum value (resp. weak value) among all assignments φ, i.e., val(L) := maxφ:A→[L] val(φ) (resp. weak-val(L) := maxφ:A→[L] weak-val(φ)).

For any δ > 0 and t ∈ N, let δ-Gap-Label-Cover(t,R) denote the following problem: given a Label Cover instance L with right degree t and right alphabet set [R], distinguish between val(L) = 1 and weak-val(L) < δ.

The hardness of δ-Gap-Label-Cover(t,R) is well-known and is often used as a starting point for reductions in hardness of approximation. Below we summarize the two hardness of approximation of Label Cover relevant to our work.

Theorem 10 (Feige [1998]). For every δ > 0, every t ∈ N, t ⩾ 2, and for any sufficiently large R ∈ N (depending on δ, t), δ-Gap-Label-Cover(t, R) is NP-hard.

Theorem 11 (Manurangsi [2020]). Assuming Gap-ETH, for every δ > 0, every t ∈ N, t ⩾ 2, and any sufficiently large R ∈ N (depending on δ, t), no f(k) · N o(k) -time algorithm can solve δ-Gap-Label-Cover(t, R), where k denote the number of left vertices in Label Cover and f can be any function.

We may now state the main properties of our reductions:

Theorem 12. Let w be such that limi→∞wi = 0. For any ϵ > 0, there exist δ > 0, t ∈ N and a reduction that takes in an instance L = (A,B,E, [L], [R], {πe}e∈E ) of δ-Gap-Label-Cover(t,R) and produces an election E = (V, C, {Av}v∈V ) in poly(|C|, |V |) time such that:

• (Completeness) If val(L) = 1, then there exists W ⊆ C such that scrEw(W) = |V |.
• (Soundness) If weak-val(L) < δ, then for all W ⊆ C, we have scrEw(W) = (αw + ϵ) · |V |.
• (Size bound) |C| = |A| · L and |V | = |B| · tR.
• (Parameter) k = |A|.

Plugging in Theorem 12 to Theorems 10, 11 immediately yields the desired hardness of approximation in Theorem 1.

The rest of this section is devoted to the proof of Theorem 12. Our reduction is in fact the same as Feige's [1998], which can be interpreted as the inapproximability for APPROVAL CHAMBERLIN-COURANT. Hence, on the hardness front, our main contribution is in extending the analysis to work with more general sequences of weights. To this end, we provide several helpful auxiliary lemmas in Section 4.1. Then, in Section 4.2, we describe Feige's reduction together with our generalized analysis, and prove Theorem 12.

4.1 Auxiliary Lemmas

Similar to the analysis of our algorithm, we will need to move from (generalizations of) Binomial random variables to Poisson random variables. The difference between here and the algorithmic counterpart (Section 3) is that the sign is flipped. Specifically, in Section 3, we need E[w1 + · · · +wBin(n,p)] ⩾ E[w1 + · · · +wPoi(np)]. Below, we show that in fact the lefthand side is not much more than the right-hand side. Our lemma is presented in its full generality below.

Lemma 13. Let w be such that limi→∞wi = 0, γ, λ > 0 be any positive real numbers. Then, there exists p0 = p0(w, γ, λ) > 0 such that, for any positive real number p < p0, any positive integer n < λ/p and any non-negative integers m1, . . . , mℓ with ∑ℓi=1 mi = n, we have

Another useful fact is stated below.

Lemma 14. The function f : R⩾0 → R⩾0 given by f(λ) = Ez∼Poi(λ)[w1 + · · · +wz] is concave.

4.2 The Reduction and Proof of Theorem 12

We can now describe the reduction and prove Theorem 12. As stated earlier, our reduction is the same as that in [Feige, 1998], which employs the following gadget:

Definition 15 (Hypercube Set System [Feige, 1998]). For any integer t ∈ N,R ∈ N, the (t,R)-hypercube set system is defined as H = (U, P1, . . . , PR) where the universe U is [t]R and each Pj = (Pj,1, . . . , Pj,t) is a partition of U into t parts where Pj,i = {u = (u1, . . . , uR) ∈ [t]R | uj = i}.

In our reduction, we first pick the parameters as follows.

• Let i∗ denote the smallest positive integer such that wi∗ < 0.1ϵ, and let ϑ = 10i∗ /ϵ.
• Let γ = 0.7ϵ, p0 = p0(w, γ, 10ϑ) be as in Lemma 13.
• We select t = ⌈2/p0⌉ and δ = 0.0001ϵ ϑ3 t2 .

Given a Label Cover instance L = (A,B,E, [L], [R], {πe}e∈E ) where the right degree is t, we create an election E = (V, C, {Av}v∈V ) as follows.

• Let (U, P1, . . . , PR) be a (t, R)-hypercube set system.
• Let the set of voters be V := B ×U.
• Let the set of candidates be C := A× [L].
• For each b ∈ B, order its neighbours arbitrarily and, for a neighbour a of b, let ι(a) ∈ [t] denote its index in this ordering. A voter (b, u) ∈ B × U approves a candidate (a, σ) ∈ A× [L] iff a is a neighbour of b and u ∈ Pπ(a,b)(σ),ι(a).
• Let k = |A|.

The reduction obviously runs in poly(|C|, |V |) time and the sizes of C, V are as stated in Theorem 12.

Completeness. Suppose that there is an assignment φ : A → [L] that satisfies every b ∈ B. Pick W = {(a, φ(a)) | a ∈ A}. We claim that scrEw(W) ⩾ |V |; specifically, we will argue that every voter approves a candidate in W. Consider any voter (b, u) ∈ B × U and let a1, . . . , at be b's (ordered) neighbours. Since φ satisfies b, we have π(a1,b)(φ(a1)) = · · · = π(at,b)(φ(at)). Since Pπa1,b(φ(a1)) is a partition of u, there exists i ∈ [t] such that u ∈ Pπa1,b(φ(a1)),i = Pπai,b(φ(ai)),i. This implies that (b, u) approves (ai, φ(ai)) as desired.

Soundness. Assume contrapositively that there exists a subset W ⊆ C of k candidates, such that scrEw(W) ⩾ (αw + ϵ) · |V |. We will show that weak-val(φ) ⩾ δ.

For every b ∈ B, let Vb = {b} × U, Eb = (Vb,C, {Av}v∈Vb ) denote the subelection on the voters Vb, and let degW(b) := |W ∩ (N(b) × [L])| where N(b) denote the set of neighbours of b. For every a ∈ A, let Wa ⊆ [L] denote {σ ∈ [L] | (a, σ) ∈ W}. Finally, let D = 10ϑt.

We divide the set B into three sets:

• Let B1 denote the set of b ∈ B s.t. degW(b) > D.
• Let B2 denote the set of b ∈ B such that degW(b) ⩽ D and, for all distinct neighbours a1, a2 of b and all σ1 ∈ Wa1 , σ2 ∈ Wa2 , we have π(a1,b)(σ1) ̸= π(a2,b)(σ2).
• Let B3 = B \ (B1 ∪ B2).

We will next argue that |B3| ⩾ Ωt,ϵ(|B|), which will then allow us to "decode" back the assignment to the Label Cover instance L. To do so, we start by bounding the contribution of B1 to scrEw(W). The main idea is that when degW (b) is large, the "average score per candidate" becomes small, which gives the following upper bound on the desired quantity:

Next, we bound the score contribution from B2, using the auxiliary lemmas shown in the previous subsection.

Proof. Let us fix b ∈ B2. Let a1, . . . , at be its (ordered) neighbours. For each κ ∈ [R], let τ κ = |{(a, σ) ∈ W | a ∈ N(b), π(a,b)(σ) = κ}|. Moreover, if τ κ ̸= 0, let iκ denote the index i ∈ [t] of the neighbour s.t. π(ai,b)(σi) = κ for some σi ∈ Wi. (Due to our definition of B2, there is a unique such i.) If τ κ = 0, let iκ =⊥.

Recall that a voter (b, u) approves a candidate (ai, σ) iff u ∈ Pπ(ai,b)(σ),i, or equivalently uπ(ai,b)(σ) = i. Hence, the number of candidates in W approved by (b, u) ∈ Vb is

where 1 is an indicator function. Hence, we may rearrange scrEb w (W) as

Observe that 1[u1 = i1 ], . . . , 1[uR = iR] are i.i.d. Ber(1/t) random variables. Moreover, ∑κ∈[L] τ κ = degW (b) ⩽ D = 10ϑt. By our choice of t, we may apply Lemma 13 to get

By summing this over b ∈ B2, ∑b∈B2 scrEb w (W) is at most

where the inequality comes from Lemma 14, and the equality from ∑b∈B degW(b) = |B| · t, |U| · |B| = |V | and from our choice of γ.

From the two propositions above and our assumption that scrEw(W) ⩾ (αw+ϵ)·|V |, we must have ∑b∈B3 scrEb w (W) ⩾ 0.1ϵ · |V |. It is obvious to see that scrEb w (W) ⩽ degW(b) · |Vb|/t, which is at most D · |V |/(t · |B|) for b ∈ B3. Thus,

Now, consider the following (random) assignment: for every a ∈ A such that Wa ̸= ∅, let φ(a) be a random element of Wa. By definition, each b ∈ B3 has distinct neighbours a1, a2 and σ1 ∈ Wa1 , σ2 ∈ Wa2 such that π(a1,b)(σ1) = π(a2,b)(σ2). Hence, the probability that φ weakly satisfies such b is at least 1 |Wa1 |·|Wa2 | ⩾ 1 D2 , where the inequality follows from degW (b) ⩽ D. Thus,

This completes our proof of Theorem 12.

5 Conclusion

In this work, we provide an approximation algorithm and hardness of approximation for w-THIELE rules, which are tight for the natural class of geometrically dominant rules. Many popular Thiele rules, such as PROPORTIONAL APPROVAL VOTING and p-GEOMETRIC, belong to this class. While our results resolve the approximability for these Thiele rules, many interesting questions still remain open.

Tight (in)approximability for other Thiele rules. An immediate open question from our work is whether there is a simple tight characterization of the approximability of wTHIELE rules for any (not necessarily geometrically dominant) w. Regarding this, recall that Barman et al. [2020] gives such a tight bound for w = (1, . . . , 1, 0, . . . ). Their ratio is not of the form (1). Furthermore, we note that the hardness results of Barman et al. [2020] need to rely on the Unique Games Conjecture (UGC), not just P ̸= NP as in our work. These highlight the challenges in generalizing our results to larger families of w.

Performance of the greedy algorithm. As touched upon earlier, a well-studied algorithm for w-THIELE (and its generalization) is the greedy algorithm, in which at each step the candidate whose inclusion maximizes the total utility increase is added to the committee. This is repeated until k candidates are selected. The greedy algorithm is very efficient and hence maybe preferred over LP-based algorithms in practice. Theoretically, the greedy algorithm is known to provide (1 - 1/e)- approximate solution for w-THIELE for any w [Nemhauser et al., 1978; Skowron et al., 2016]. An interesting direction is to determine the exact approximation guarantees of the greedy algorithm for specific w, such as PROPORTIONAL APPROVAL VOTING and p-GEOMETRIC. On this front, we manage to show the following:

Theorem 18. For any Thiele sequence w = (1, p,w3 . . . ), the approximation ratio of the greedy algorithm for wTHIELE is at most 1 1-p · (1- 1 e1-p ).

An important consequence of the above theorem is that, for any geometrically dominant w = (1, p, w3, . . . ) such that w is not p-GEOMETRIC, the approximation ratio guarantee by our LP-based algorithm is strictly better than that of the greedy algorithm. It remains open whether this also holds for p-GEOMETRIC and other non-geometrically dominant w.

Extensions to OWA-Winner and Participatory Budgeting. Skowron et al. [2016] studied the w-OWA-Winner problem, which is a generalization of w-THIELE rule that allows each voter to assign any utility to a candidate (in approval ballots the utility was 0 or 1). They, using a result of Nemhauser et al. [1978], gave an (1 - 1/e)-approximation algorithm for all non-increasing OWA vectors w. We note that the greedy algorithm of Khuller et al. [1999] also gives an (1 - 1/e)- approximation for the OWA-Winner problem with a knapsack constraint (instead of a cardinality constraint) due to analysis of Sviridenko [2004]. Knapsack constraint models an issue of Participatory Budgeting (PB) where candidates are projects with assigned costs. Only specific sequences of weights were considered, e.g., (1, 0, , . . . ), (1, 1, , . . . ) and (1, 1/2, 1/3, . . . ) [Talmon and Faliszewski, 2019; Fluschnik et al., 2019]. It is interesting whether we can get better than (1 - 1/e)-approximation algorithm for OWA-Winner using our results or if they can be extended by replacing cardinality constraint with a knapsack constraint (but keeping approval ballots as this is the most popular way of balloting-indeed, general non-increasing sequences of weights with approval ballots model projects substitution [Jain et al., 2020]). We note here that our hardness results in Theorems 1 and 18 also hold for OWA-Winner and PB.

Minimization variants. One can consider the minimization version of the problem, i.e., minimizing dissatisfaction instead of maximizing utility. Such a minimization variant, coming from computational social choice, has already been considered for several Thiele rules. Most of them assume that voters and candidates lie in a metric space, and dissatisfaction of a voter from a candidate is equal to the distance between them (not necessarily 0 or 1). The most popular objective function is minimizing the sum of distances of the voters to the closest chosen candidate, i.e., w = (1, 0, . . . ). This problem is called k-Median and can be approximated within 2.675-ratio [Byrka et al., 2017]. Hardness of approximation for k-Median is known to be 1 + 2/e [Guha and Khuller, 1999], even in FPT wrt. k time, in which the gap has been closed [Cohen-Addad et al., 2019]. The minimization version of w-THIELE rules is called OWA k-Median for which 93-approximation was shown [Byrka et al., 2018]. For some specific w, better approximation ratios have been achieved. For instance, when wℓ(i) = (1, , . . . , 1, , 0, . . . ) (i.e., ℓ ones followed by zeros), the problem is called ℓ-Fault Tolerant kMedian and a 4-approximation algorithm is known [Swamy and Shmoys, 2008]. When w(i) = 1/i, the problem is called Harmonic k-Median and a 2.36-approximation algorithm exists [Byrka et al., 2018]. Surprisingly, this last result does not assume that the function of dissatisfaction is a metric. There are still many approximation gaps for the minimization variants of w-THIELE rules that should be studied.

Acknowledgements

This research is partially supported by the National Science Centre, Poland (grant numbers 2015/18/E/ST6/00456, 2018/28/T/ST6/00366, 2018/29/B/ST6/02633) and the Israel Science Foundation (grant number 630/19). Part of this work was done while Pasin was visiting University of Wrocław. Krzysztof Sornat is partially supported by the Foundation for Polish Science (FNP) within the START programme.

We would like to thank Mateusz Lewandowski for initial discussion and the anonymous reviewers for their helpful comments.