The Proportional Veto Principle for Approval Ballots

1 Introduction

Voting is one of the most prominent approaches to collective decision-making and has been studied extensively in several disciplines, not least in social choice theory [Brams and Fishburn, 2002; Zwicker, 2016]. Some applications of voting require selecting a single winner, e.g., the president of a country or the venue for an event. Other applications involve choosing multiple winners, such as members of a council, places to visit on a trip, or recipients of a research grant.

In several voting scenarios, a natural consideration is that groups of voters should have the right to veto candidates that they dislike, be it a politician whose views they disagree with or a venue they find unsuitable. This intuition is formalized by the concept of the proportional veto core, which was proposed by Moulin [1981] and further studied by a number of authors [Moulin, 1982; Ianovski and Kondratev, 2021; Kizilkaya and Kempe, 2023; Peters, 2023; Kondratev and Ianovski, 2024]. The proportional veto core is defined for single-winner voting when each voter expresses her preference over candidates in the form of a strict ranking. According to this principle, a candidate a can be vetoed by a group of voters T if there exists a sufficiently large set of candidates B such that every voter in T prefers all candidates in B to athe required size of B depends on the size of T . A significant result by Moulin [1981] states that the proportional veto core is always non-empty, i.e., there always exists a candidate that is not vetoed by any group of voters.

While ranked ballots have been examined since the dawn of social choice theory, an alternative method for eliciting voter preferences, which has also received substantial attention in the literature, is via approval ballots [Brams and Fishburn, 2007; Laslier and Sanver, 2010]. In an approval ballot, a voter may either approve or disapprove each candidate. In addition to their simplicity, approval ballots are quite expressive, as voters are allowed to approve as many or as few candidates as they wish. As Brandl and Peters [2022] discussed, approval ballots arise naturally when preferences are dichotomous-for example, when they correspond to whether workers are available during various time slots, or whether hiring committee members consider candidates to be capable of performing a clearly defined task. Approval ballots have been used in political contexts-including in the St. Louis, Missouri mayoral and Fargo, North Dakota municipal elections-as well as by professional groups such as the American Mathematical Society.

A tempting approach for applying the proportional veto principle to approval ballots is to convert the approval ballots into ranked ballots by breaking ties arbitrarily, and apply the result of Moulin [1981] to obtain a candidate in the proportional veto core of the ranked ballots. However, this approach may lead to patently undesirable outcomes. For instance, consider four candidates a, b, c, d and three voters who approve {b, c}, {b, d}, {c, d}, respectively. One can convert these approval ballots into the ranked ballots where voter 1 ranks b ≻ c ≻ a ≻ d, voter 2 ranks b ≻ d ≻ a ≻ c, and voter 3 ranks c ≻ d ≻ a ≻ b. For these approval ballots, voter 1 vetoes d for being last, and similarly voters 2 and 3 veto c and b, respectively, leaving a as the only candidate in the proportional veto core. However, the choice of a is clearly suboptimal with respect to the original approval ballots, as it is approved by none of the voters.

To formalize the proportional veto principle for approval ballots, we introduce a concept of voter flexibility, which corresponds to the fraction of candidates that a voter approves. Intuitively, in single-winner voting, if a group of voters is sufficiently large and each voter in the group is sufficiently flexible, we would like to ensure that at least one voter in the group approves the chosen candidate. Put differently, a sufficiently large and sufficiently flexible group has the power to veto a candidate that the entire group disapproves. While considering flexibility is natural in any setting where approval voting is employed, it may be especially useful in applications such as participatory budgeting, where voters sometimes participate to support a single project that aligns with a particular cause. Indeed, rules that reward flexibility could encourage voters to approve more projects, lead to chosen projects with broader consensus, and provide greater legitimacy to the process. 1 As another example, consider a group of countries deciding the location(s) for hosting an international event. In this scenario, flexibility could help motivate the representatives of each country to vote beyond merely their own country or close allies. We refer to our principle as flexible-voter representation (FVR).

We highlight that FVR is more robust than proportional veto for ranked ballots. In particular, for a candidate a to be vetoed by a group T , FVR does not require every voter in T to approve all candidates in some set B and disapprove ainstead, it only requires all voters in T to approve sufficiently many (but not necessarily the same) candidates and disapprove a. We discuss this distinction further in Section 1.2, but note here that FVR is particularly suited to approval ballots, where voter flexibility can be defined naturally.

1.1 Overview of Results

In Section 2, we focus on single-winner voting. For s ∈ (0, 1), we say that a voter is s-flexible if she approves at least an s-fraction of the candidates. For each voting rule R and each s, we denote by FVR(R, s) the smallest value of r such that whenever a group of voters constitutes more than an rfraction of the voters and each voter in the group is s-flexible, at least one voter in the group approves the candidate chosen by R. The lower FVR(R, s) is, the stronger the guarantee that the rule R provides for the threshold s.

We first derive a general lower bound: for any rule R and any s, it holds that FVR(R, s) ≥ 1 - s. Moreover, this bound is tight in the sense that for each s, the rule Rs-threshold, which chooses a candidate with the most approvals among sflexible voters, achieves FVR(Rs-threshold, s) = 1 - s. However, as each rule Rs-threshold is tailored to a specific value of s, a rule with strong guarantees for all values of s simultaneously would be more desirable. We show that the classic approval voting rule, which chooses a candidate with the most approvals overall, yields FVR(R, s) = 1 1+s for all s; this essentially matches the lower bound for s close to 0, but becomes further away as s increases. To achieve better guarantees for larger s, we consider placing more weight on voters with higher flexibility. Specifically, we let the contribution of a voter to the score of each of her approved candidates be the voter's flexibility raised to the p-th power, where p > 0 is a given parameter. For each p, we determine the exact FVR of the p-power scoring rule-we find that it matches the lower bound at s = p 1+p , but not at other values of s.

From the aforementioned results, one may be tempted to believe that there is an inevitable trade-off between optimizing for different thresholds s. Strikingly, we show that this is not the case: there is in fact a rule ROPT that is FVRoptimal, meaning that FVR(R, s) = 1 - s for all s simultaneously. One may interpret this result as demonstrating that an approval-ballot analog of the proportional veto core is always non-empty. Like p-power scoring rules, ROPT can be described as a scoring rule, with the scores chosen carefully. We also establish a general theorem that can be used to determine FVR guarantees of arbitrary scoring rules-this theorem allows us to characterize ROPT as the unique scoring rule (up to scaling) that satisfies FVR-optimality.

1 We also remark that proportionality is a central guarantee behind the method of equal shares, which has been used for participatory budgeting in Poland and Switzerland [Boehmer et al., 2024].

In Section 3, we turn our attention to the more general setting of multi-winner voting, where the goal is to choose a set of k candidates (called a committee) from the m given candidates; single-winner voting corresponds to k = 1. For 1 ≤ t ≤ k, we say that a voter t-approves a committee if she approves at least t candidates in the committee. Unlike in the single-winner setting, it will be more convenient to state our bounds including their dependency on m (rather than in the worst case over all m). Specifically, we let FVR(R, s, t,m) be the smallest value of r such that whenever a group of voters constitutes more than an r-fraction of the voters, each voter is s-flexible, and there are m candidates, then at least one voter in the group t-approves the committee chosen by R.

Similarly to single-winner voting, we provide a lower bound on FVR(R, s, t,m), which can be written in terms of a hypergeometric random variable; for any s, t,m, k, we present a rule for which this bound is tight. Moreover, if k and t are fixed, we show that there exists a rule that yields the optimal guarantee for all m and s. This rule operates by iteratively choosing a candidate using a scoring rule; however, the weight assigned to each voter in this procedure depends nontrivially on the voter's preference and the candidates added thus far. On the other hand, we prove that if we fix s (and k,m), it may not be possible to achieve FVR-optimality for different values of t at the same time. We also demonstrate the incompatibility between FVR-optimality and other notions of representation in the multi-winner literature.

1.2 Additional Discussion

As mentioned earlier, in single-winner voting, FVR can be viewed as an approval-ballot analog of the proportional veto core for ranked ballots [Moulin, 1981]. However, in order for a group of voters to veto a candidate a, FVR does not require the voters in the group to commonly approve a set of candidates and disapprove a-instead, it is enough that these voters approve sufficiently many candidates and disapprove a. To highlight the difference that this distinction makes, note that strengthening the proportional veto core along the lines of our FVR definition may lead to an empty core. Indeed, if there are two voters with rankings a ≻ b ≻ c and c ≻ b ≻ a over three candidates, then this more demanding notion would rule out c (as the first voter ranks it last), a (as the second voter ranks it last), and b (as both voters rank it second-last), leaving no viable candidate. 2 In the approval setting, FVR takes advantage of the dichotomous nature of the preferences to achieve a stronger guarantee.

Another related concept is justified representation (JR) [Aziz et al., 2017], which has received significant attention recently in the context of multi-winner (approval) voting. JR captures the idea that if a group of voters is sufficiently large and all voters in the group approve a common candidate, then at least one candidate approved by some voter in the group should be selected. While FVR bears some similarity to JR, a major difference is that FVR does not require voters in the group to approve any candidate in common, but only that these voters be sufficiently flexible. Note that in single-winner voting, JR does not provide any meaningful guarantee, and neither do its various strengthenings [Aziz et al., 2017; S´anchez-Fern´andez et al., 2017; Peters et al., 2021; Brill and Peters, 2023].

2 We formalize this in the full version of our paper [Halpern et al., 2025]. Note that the proportional veto core does not rule out b, since the two voters do not agree on a candidate that is preferred to b.

2 Single-Winner Voting

2.1 Preliminaries

For each positive integer t, let [t] := {1, 2, . . . , t}. There is a set N of n voters and a set M of m candidates. Each voter i has an approval set Ai ⊆ M. An instance consists of N, M, and (Ai)i∈N. For a candidate a ∈ M, let Na := {i ∈ N | a ∈ Ai} be the set of voters who approve it. For a voter i ∈ N, let fi := |Ai|/m be the fraction of candidates that i approves. In single-winner voting, a rule chooses a single candidate from each instance.

For s ∈ (0, 1), we say that a voter i is s-flexible if fi ≥ s. Given a rule R, we are interested in, for each s ∈ (0, 1), the smallest r ∈ [0, 1] (as a function of s) such that whenever a group of strictly more than rn voters (i.e., more than an r-fraction of the voters) are all s-flexible, at least one voter in the group approves the candidate chosen by the rule. 3 We refer to this condition as the FVR condition, and denote this value of r by FVR(R, s). Note that FVR(R, s) is always well-defined. Indeed, r = 1 satisfies the FVR condition vacuously; if some r satisfies the condition then every r′ ≥ r does as well; and if for some r it holds that every r′ > r satisfies the condition, then r also satisfies the condition (because the condition is phrased as "strictly more than rn voters"). The smaller the value FVR(R, s), the stronger the FVR guarantee provided by the rule R for the threshold s.

Example 2.1. Consider a rule R that always returns the first candidate, regardless of the voters' approvals. We claim that FVR(R, s) = 1 for all s ∈ (0, 1), i.e., this rule offers the worst possible FVR guarantees. Indeed, for any s ∈ (0, 1), consider an instance where each of the n voters approves all m candidates except the first candidate, where m> 1 1-s . All voters are s-flexible but none of them approves the candidate chosen by R, so the FVR condition holds only for r = 1.

2.2 Lower Bound

We first derive a lower bound on the FVR guarantee achievable by any rule.

Theorem 2.2. For any rule R and any s ∈ (0, 1), we have FVR(R, s) ≥ 1 - s. Moreover, for each s ∈ (0, 1), there exists a rule R such that FVR(R, s) = 1 - s.

3 If s = 1, the answer is clearly r = 0 regardless of the rule, so we do not consider this trivial case.

Proof. For the first statement, consider any rule R and any s ∈ (0, 1), and take any r < 1 - s. It suffices to show that there exists an instance where a group of at least rn voters are all s-flexible but do not approve the candidate chosen by R. Consider an instance with sufficiently large n and m (to be made more precise later). Assume that each of the n voters approves exactly ⌈sm⌉ candidates (so all voters are s-flexible), and the voters distribute their approvals as equally as possible. 4 Hence, each candidate receives at most

As mgrows, sm+1 m converges to s, so n· sm+1 m +1 converges to sn + 1. Since s < 1 - r, we have sn + 1 < (1 - r)n for sufficiently large n. This means that for sufficiently large n and m, each candidate is approved by at most (1-r)n voters. Consequently, no matter which candidate R chooses, at least rn voters disapprove it.

For the second statement, fix s ∈ (0, 1). Consider the rule Rs-threshold that chooses a candidate a with the highest number of approvals among s-flexible voters, breaking ties arbitrarily; in particular, the rule ignores voters who are not s-flexible. It suffices to show that whenever a group of more than (1-s)n voters are all s-flexible, at least one voter in the group approves a. Since each s-flexible voter approves at least an sfraction of the candidates, the candidates are approved by at least an s-fraction of the s-flexible voters on average. By definition of the rule Rs-threshold, the candidate a is approved by at least an s-fraction of the s-flexible voters, which means that at most a (1-s)-fraction of the s-flexible voters disapprove a. Since the number of s-flexible voters is at most n, this implies that at most (1 - s)n voters who are s-flexible disapprove a. It follows that in any group of more than (1-s)n voters who are s-flexible, at least one voter in the group approves a.

While the rule Rs-threshold in the proof of Theorem 2.2 achieves the optimal FVR guarantee for the corresponding flexibility threshold s, it is tailored to only one threshold s, which leads to unwanted effects-for instance, the rule completely ignores voters who are almost s-flexible. As such, it would be more desirable to have a rule that yields good guarantees for several thresholds s simultaneously.

2.3 Approval Voting Rule

We next analyze the classic approval voting rule, which selects a candidate with the highest number of approvals, breaking ties arbitrarily. For this rule, we determine the tight FVR guarantee for every s.

Theorem 2.3. Let Rapproval be the approval voting rule. For each s ∈ (0, 1), we have FVR(Rapproval, s) = 1 1+s .

Proof. Fix s ∈ (0, 1). We first show the upper bound FVR(Rapproval, s) ≤ 1 1+s . Take an arbitrary instance, and consider a group B of more than 1 1+s · n voters, all of whom are s-flexible. The total number of approvals made by the voters in B is greater than 1 1+s · n · sm. Since there are m candidates, there exists a candidate a approved by more than 1 1+s · n · s = s 1+s · n voters in B. On the other hand, a candidate that is not approved by any voter in B has an approval score of less than (1- 1 1+s )n = s 1+s · n. In particular, such a candidate is approved by fewer voters than a. Hence, the candidate chosen by the approval voting rule must be approved by some voter in B.

4 For example, we can let the voters distribute their approvals one voter after another. In each voter's turn, the voter approves ⌈sm⌉ candidates that have received the fewest approvals so far, breaking ties arbitrarily.

Next, we show that FVR(Rapproval, s) ≥ 1 1+s . Take any r < 1 1+s . It suffices to show that there exists an instance where a group of at least rn voters are all s-flexible but do not approve the candidate chosen by the approval voting rule. Consider an instance with sufficiently large n and m (to be made more precise later). Let C be a group of ⌈rn⌉ voters, and assume that all voters in N \ C approve a common candidate a (and no other candidate). Moreover, assume that each voter in C approves exactly ⌈sm⌉ candidates in M \ {a}, and these voters distribute their approvals among these candidates as equally as possible. Note that a receives n-⌈rn⌉ = ⌊(1-r)n⌋ approvals, while every other candidate receives at most ⌈ ⌈rn⌉·⌈sm⌉ m-1 ⌉ approvals. Since r < 1 1+s , we have 1-r > s 1+s , and so ⌊(1-r)n⌋ > s 1+s ·n when n is sufficiently large. Hence, a receives more than s 1+s ·n approvals for sufficiently large n. On the other hand, note that

As m grows, sm+1 m-1 converges to s, so (rn + 1) · sm+1 m-1 + 1 converges to (rn+1)s+1 = rns+s+1. Since r < 1 1+s , we have rns+s+1 < 1 1+s ·ns = s 1+s ·n for sufficiently large n. This means that for sufficiently large n and m, each candidate inM \{a} receives at most s 1+s · n approvals. Consequently, the approval voting rule chooses the candidate a, which is approved by none of the voters in C.

Comparing Theorems 2.2 and 2.3, we find that the FVR guarantee of the approval voting rule is essentially optimal for s close to 0, but gets further from optimal as s increases.

2.4 Power Scoring Rules

To achieve better guarantees for larger s, an enticing idea is to give more weight to voters with higher flexibility. However, unlike the rule Rs-threshold in the proof of Theorem 2.2 where this weight is binary (according to whether a voter is s-flexible), we shall use a smoother weighting scheme.

To this end, for each real number p ≥ 0, we define the ppower approval score of candidate a as SCp(a) := ∑i∈Na f p i (recall that Na denotes the set of voters who approve a). We consider the p-power scoring rule, which chooses a candidate that maximizes the p-power approval score, breaking ties arbitrarily. Note that if p = 0, then ∑i∈Na f p i = |Na|, so the rule reduces to the approval voting rule which we already analyzed in Theorem 2.3. As p increases, the rule places more

s

Figure 1: FVR guarantees of p-power scoring rules for flexibility thresholds s ∈ (0, 1), compared to the optimal guarantees indicated by the thick line. For p = 1, 2, the guarantees match the optimal ones at s = 1/2, 2/3, respectively.

importance on voters with high flexibility. For each p, we derive tight FVR guarantees for the corresponding rule.

Theorem 2.4. For each p > 0, let Rp-power be the ppower scoring rule. For each s ∈ (0, 1), we have FVR(Rp-power, s) = 1 1+ (s(1+p))1+p pp .

The proof of Theorem 2.4, along with all other missing proofs, can be found in the full version of our paper [Halpern et al., 2025]. Comparing Theorem 2.4 with Theorem 2.2, we find that the FVR guarantee of the p-power scoring rule is optimal only at s = p/(1 + p). Indeed, one can verify that

Within the range x ∈ [0, 1], basic calculus shows that the function xp (1-x) ismaximized at x = p 1+p , and the resulting maximum is pp (1+p)1+p . Hence, the only s for which the FVR guarantee of the p-power scoring rule is optimal is s = p 1+p , and the corresponding guarantee is 1 1+p .

The FVR guarantees of p-power scoring rules for p = 0 (i.e., approval voting rule), 1, and 2, as well as the optimal guarantees, are illustrated in Figure 1.

2.5 Optimal Scoring Rule

Our discussion thus far raises an obvious question: is there an inherent trade-off between optimizing for different values of s, or does there exist a rule that achieves the optimal FVR guarantee for all s simultaneously (that is, a rule whose guarantees exactly match the thick line in Figure 1)? Perhaps surprisingly, we show that such a rule in fact exists, and moreover, comes from a simple class called scoring rules [Fishburn, 1979]. 5

5 In the original definition, these are called simple scoring rules, but for conciseness, we drop the word 'simple'.

To define scoring rules, let a weight function be a function w : Q ∩ (0, 1) → R≥0 mapping each flexibility to a weight. From this, we define the w-score of a candidate a to be SCw (a) = ∑i∈Na w(fi). We assume without loss of generality that w(1) = 0; if a voter i has fi = 1, then she approves all candidates, so modifying w(1) changes the scores of all candidates by a constant. We call a weight function w nontrivial if w(f) > 0 for some f ∈ (0, 1). 6 We say that a rule is parameterized by w if it always picks a candidate maximizing SCw , and we call it a scoring rule if it is parameterized by some nontrivial w. Note that all of the rules we have considered so far are scoring rules: Rs-threshold is parameterized by w(f) = I[f ≥ s], Rapproval is parameterized by w(f) = 1, and Rp-power is parameterized by w(f) = f p .

For our optimal rule, unlike the power rules we have seen, we will choose the weight function w(f) = 1 1-f . Specifically, let ROPT be the rule that assigns a score of ∑i∈Na 1 1-fi to each candidate a and selects a candidate with the highest score, breaking ties arbitrarily. 7 We say that a rule R is FVRoptimal if FVR(R, s) = 1 - s for all s ∈ (0, 1).

Theorem 2.5. The rule ROPT is FVR-optimal.

Proof. Observe that an equivalent formulation of ROPT is that each voter i distributes 1 1-fi points to each candidate that the voter disapproves, and ROPT chooses a candidate with the lowest total points. In this formulation, each voter i distributes a total of 1 1-fi ·(1-fi)m = m points, 8 so at most nm points are distributed overall. This means that the candidate a chosen by ROPT receives at most n points.

Next, fix any s ∈ (0, 1), and consider a group of s-flexible voters who all disapprove a. Since each voter in the group gives at least 1 1-s points to a, the size of the group is at most (1-s)n. It follows that whenever a group of more than (1s)n voters are all s-flexible, at least one voter in the group approves a.

2.6 General Weight Function Analysis

Theorems 2.3 to 2.5 provide analyses for specific scoring rules. What can we say about scoring rules more broadly? In the following theorem, we analyze the FVR guarantees of arbitrary scoring rules. Given a weight function w, let Rw denote a scoring rule parameterized by w.

Theorem 2.6. Let w be a nontrivial weight function. Then,

where ρ := supf(1 - f) · w(f) and φs := inff≥s f · w(f); if ρ = ∞, the ratio is defined to be 1. Further, if w is nondecreasing, then φs = s · w(s) and the bound simplifies to

6 If w(f) = 0 for all f, then the w-scores of all candidates will be equal.

7 If a voter approves all candidates, we simply ignore that voter.

8 Again, we ignore voters who approve all candidates. Note that voters who approve none of the candidates also distribute points.

Proof. Fix w, Rw , and s ∈ (0, 1). We first bound FVR(Rw , s) from above. If ρ = ∞ then the bound holds trivially, so assume that ρ < ∞. Fix an instance and let a∗ be the candidate chosen by Rw . Let B be a set of s-flexible voters who disapprove a∗ , and let ¯B = N \B be the set of remaining voters. Note that SCw (a∗ ) ≤ ∑i∈ ¯B w(fi), because no voter in B can contribute to the score of a∗ . Consider now the average score of all candidates, which is equal to

where the second equality holds because each voter i contributes w(fi) points to each of exactly |Ai| candidates. Since a∗ has the largest w-score, it must have w-score at least the average. This implies that

On the other hand,

where the inequality holds by the definitions of ρ and φs, as fi ≥ s for i ∈ B. Finally, observe that

Note that since w is nontrivial, we have ρ > 0, and so ρ + φs > 0 and the last transition is valid.

The remainder of the proof, which bounds FVR(Rw , s) from below, is left to the full paper [Halpern et al., 2025].

Theorem 2.6 is a powerful tool that allows us to analyze arbitrary scoring rules. Indeed, Theorems 2.3 to 2.5 could be proven as consequences (although we keep them separate for exposition). In addition, we can derive other nontrivial consequences, including the following fact that ROPT is essentially the unique scoring rule that ensures FVR-optimality.

Theorem 2.7. Suppose that Rw is FVR-optimal for some nontrivial weight function w. Then, there exists a positive real number c such that w(f) = c 1-f for all f.

3 Multi-Winner Voting

3.1 Preliminaries

In this section, we turn to the more general setting of multiwinner voting. Given an instance, our rules R now choose a subset of winning candidates of a given size k. We refer to a subset of k candidates as a k-committee (or just committee if k is clear from the context) and refer to a rule that selects a k-committee as a k-committee rule. Assume without loss of generality that k < m, since if k = m, there is a single k-committee which also makes all voters maximally happy.

To generalize the FVR condition to the multi-winner setting, we need to generalize the notion of a voter "approving the chosen candidate" to "approving the chosen committee." Two natural generalizations immediately come to mind. Fix a committee W. A quite lenient notion we could consider is to say that a voter i approves W if she approves at least one of the committee members (i.e., W ∩ Ai ̸= ∅), while a much more stringent requirement is that i approves W only if she approves all of the committee members (i.e., W ⊆ Ai). We will generalize both of these notions at once by introducing an additional (positive integer) parameter t ≤ k, and saying that a voter t-approves a committee W if she approves at least t of the committee members (i.e., |W ∩ Ai| ≥ t). If a voter does not t-approve a committee (i.e., |W ∩ Ai| < t), we will say that she t-disapproves it. The earlier notions correspond to the special cases of t = 1 and t = k, respectively.

With this generalization in hand, we can now extend the notion of FVR to the multi-winner setting. Unlike in the single-winner setting, it will be more convenient to state our guarantees including their dependency on m (rather than in the worst case over all m), although we will primarily be interested in the behavior of these bounds as m grows large. This is because in some cases, unlike in the singlewinner setting, as m grows, the worst case may occur for a fixed finite m rather than in the limit. With this in mind, for a k-committee rule R, we define FVR(R, s, t,m) as the largest possible fraction of voters that are all s-flexible, yet t-disapprove the chosen committee when choosing from m candidates using R.

3.2 Lower Bound

We begin by deriving a lower bound analogous to Theorem 2.2 from the single-winner setting. Let h(P,K, ℓ; ·) and H(P,K, ℓ; ·) be the probability mass function and cumulative distribution function of a hypergeometric random variable with population size P, population success size K, and draw size ℓ, respectively. 9 In other words, this is the distribution over the number of "good" elements sampled when taking a random subset of size ℓ out of P elements where K of the elements are good.

Theorem 3.1. For any k-committee rule R, any s ∈ (0, 1), and any t ≤ k, we have

Additionally, there exists a k-committee rule R (tailored to this (s, t) combination) for which this is tight.

The proof of this theorem (along with other results about multi-winner voting) relies on the following correspondence

between the number of candidates approved and the number of k-committees which are t-approved.

Lemma 3.2. If a voter approves exactly ℓ candidates, then she t-approves a (1 - H(m, ℓ, k; t - 1))-fraction of all kcommittees.

Proof. This follows from the definition of the hypergeometric distribution. Define the population to be the m candidates and a "success" to be the ℓ candidates approved by the voter. Then, if we pick a k-committee uniformly at random, the probability that the voter approves at most t - 1 candidates on the committee is H(m, ℓ, k; t - 1). Therefore, the voter t-approves the committee with probability 1 - H(m, ℓ, k; t - 1).

While the bound in Theorem 3.1 may not be the most natural-looking, note that as m grows large, the hypergeometric distribution with parameters m, ⌈sm⌉, k approaches a binomial Bin(k, s) distribution. Hence, the FVR bound approaches

Although still unwieldy, the binomial limit gives us a pathway to gain more intuition on this bound. By standard concentration inequalities, if s ≪ t/k, then this bound is exponentially close to 1, whereas if s ≫ t/k, then it is exponentially close to 0. Further, we can see that it simplifies in some special cases. Indeed, when k = 1 (so t = 1), the hypergeometric bound simplifies to 1 - ⌈sm⌉ m . This is always at most 1 - s and approaches 1 - s as m grows; hence, it coincides with the single-winner bound (Theorem 2.2). When we fix t = 1 but let k be arbitrary, the limiting binomial bound simplifies to (1 - s)k . If we fix t = k, it simplifies to 1 - sk . For finite m, the hypergeometric distribution is slightly more concentrated than the binomial distribution-for t ≪ sk, the binomial bound is an overestimate, while for t ≫ sk, it is an underestimate. Specifically, for t = 1 the hypergeometric bound is always less than the binomial limit, and for t = k it is always more. This aligns with the fact that when sampling without replacement, getting 0 success is less likely than with replacement. Similarly, getting k (out of k) successes is less likely without replacement than with replacement.

3.3 Simultaneously-Optimal Rules

We will say that a k-committee rule R is FVR-optimal for (s, t) if for all m, FVR(R, s, t, m) = H(m, ⌈sm⌉, k; t - 1). As with the single-winner setting, Theorem 3.1 implies that for any fixed (s, t), we can find an FVR-optimal rule for this combination. However, what if we wish to attain optimality for multiple choices of (s, t) simultaneously? We first show that for a fixed t, we can achieve optimality over all s via a simple algorithm. Given k and t, we construct what we call a (k, t)-expanded instance as follows. The candidates in this expanded instance are all (mk ) possible committees of size k. Each voter approves a committee W exactly when she t-approves W in the original instance. We have the following.

Theorem 3.3. Fix k and t. Let Rk,t expanded be the rule that runs ROPT on the (k, t)-expanded instance and selects the winning committee. Then, for all s ∈ (0, 1), Rk,t expanded is FVR-optimal for (s, t).

This theorem shows that we can directly generalize our single-winner rule to be optimal (in a certain sense) in the multi-winner setting. However, a downside of Rk,t expanded is that, in its current implementation, it runs in time exponential in k, as we must construct an instance with (mk ) candidates. Hence, a natural question is whether we can obtain the same guarantees with a polynomial-time algorithm. We show next that this is indeed possible using a greedy algorithm, which effectively applies the method of conditional expectations, presented as Algorithm 1.

Algorithm 1 (k, t) Sequential Algorithm

At each step, the algorithm chooses a candidate that maximizes a certain score among the remaining candidates, and adds it to the committee. However, unlike in our previous scoring rules, the weight given to each voter i now depends not only on i's flexibility, but also on the size of the current committee and the number of candidates in that committee approved by i. The algorithm yields the following guarantee.

Theorem 3.4. Fix k and t. Let Rk,t alg be the rule induced by Algorithm 1. Then, for all s ∈ (0, 1), Rk,t alg is FVR-optimal for (s, t).

To gain some intuition about the algorithm, note that for the (k, t)-expanded instance in Theorem 3.3 (and in the proof of Theorem 2.5), we need not choose a committee maximizing the w-score (for the optimal w(f) = 1 1-f ); instead, it is sufficient to choose one with above-average score. In other words, if we pick a committee W uniformly at random, E[SCw (W)] would be sufficient for optimal guarantees. However, a priori, it is possible that only a single committee W ∗ has SC(W ∗ ) ≥ E[SC(W)] while all others are strictly below, where we drop the superscript w for convenience. To get around this and "round" the random committee into a deterministic one, we greedily construct C = {a1, . . . , ak} such that at each step, E[SC(W) | {a1, . . . , aj} ⊆ W] ≥ E[SC(W)]. The weighting rule we use essentially tells us the marginal gain to the score of permanently adding each possible candidate a. On average, adding each does not change the expectation, so adding one with the largest marginal gain can only improve the conditional expectation, thereby giving the desired bound.

Next, we show that unlike the positive results we found for simultaneous optimality over s in Theorems 3.3 and 3.4, the same does not hold for t.

Theorem 3.5. For any k ≥ 2 and t ≤ ⌊k/2⌋, no rule is simultaneously FVR-optimal for (1/2, t) and (1/2, k).

3.4 Compatibility with Other Notions of Representation

Finally, we address the compatibility between FVR and other notions of representation. While several such notions have been proposed in the literature [Aziz et al., 2017; S´anchezFern´andez et al., 2017; Peters et al., 2021; Brill and Peters, 2023], one of the weakest is justified representation (JR). We show that FVR-optimality is incompatible even with JR; this implies a similar incompatibility with stronger representation notions (see the discussion in Section 1.2).

Recall that a committee W of size k is said to satisfy JR if there is no blocking coalition T of voters which fulfills the following properties:

1. Large: |T| ≥ n/k;
2. Cohesive: ⋂i∈T Ai ̸= ∅;
3. Unrepresented: W ∩ Ai = ∅ for all i ∈ T .

We establish the following incompatibility.

Theorem 3.6. For each k > 1, there exists s such that no k-committee rule is FVR-optimal for (s, 1) and satisfies JR at the same time.

4 Discussion

In this paper, we have introduced the notion of voter flexibility and a corresponding objective, flexible-voter representation (FVR), under approval voting. In the single-winner setting, we present a simple rule that is simultaneously optimal for all flexibility thresholds. In the multi-winner setting, while some impossibilities exist, we still find a polynomialtime rule which makes similar guarantees, once the definition of "approving a committee" (i.e., the parameter t) is fixed.

One may wonder what the practical implications of these objectives are. That is, should we care more about voters who are flexible? The answer certainly depends on the context. For example, consider an election in which Party A runs 20 candidates whereas Party B runs only 2. In this setting, Party A voters are not necessarily "more flexible" than Party B voters, and it may be preferable to simply take the approval winner. On the other hand, consider a setting where a community is deciding on one of several projects to fund. In this case, we may wish to reward voters who are more flexible. Indeed, the flexibility of such voters may indicate that they find their disapproved projects strongly unacceptable. Furthermore, encouraging flexibility can help achieve consensus, an inherently difficult task if few voters are flexible and no candidate has a reasonably-sized base.

More broadly, we believe that flexibility is an interesting foundational metric in its own right. Even when the chosen rules are not FVR-optimal, flexible-voter representation can be used to compare various candidates and weigh them according to their total support. Applied in a way suitable to the context, flexibility measures can help ensure a more desirable outcome in approval-based voting scenarios.

Acknowledgments

This work was partially supported by the National Science Foundation under grants IIS-2147187, IIS-2229881, and CCF-2007080, by the Office of Naval Research under grant N00014-20-1-2488, by the Singapore Ministry of Education under grant number MOE-T2EP20221-0001, and by an NUS Start-up Grant. We thank the anonymous reviewers for their valuable feedback.