Phragmén Rules for Degressive and Regressive Proportionality

1 Introduction

Consider a scenario where a group of voters needs to select a committee, that is a given-size subset of available candidates. Assume the voters have approval-based preferences: each voter submits a ballot in which she indicates which of the available candidates she finds acceptable. This scenario received a considerable attention in the literature in recent years-see the book chapter by Kilgour [2010] and the recent survey by Lackner and Skowron [2020].

In many scenarios that fit in the model of approval-based committee elections, for example when the goal is to select a representative body for a population of voters, it is required that the elected committee should represent the voters proportionally. Typically, the term proportionality is used to indicate that each group of voters with similar opinions should approve the number of elected candidates that is proportional to the size of the group. For example, consider a society that is divided into two coherent groups: there are two disjoint sets of candidates, A and B; 60% voters approve A and 40% approve B. Then, proportionality-in its most commonly used sense-means that we shall select roughly 60% of committee members from A and 40% of committee members from B.

Is this outcome fair to the voters? That depends on how we define and interpret voters' satisfaction. If we define the satisfaction of a voter as the number of elected candidates she approves, then indeed the outcome seems fair. However, if the elected committee is to take a number of majoritarian decisions, then it is likely that such decisions will almost solely satisfy the voters from the first group, which can be considered highly unfair by those from the second group. Similar arguments led to the idea of degressive proportionality [Laslier, 2012; Mac´e and Treibich, 2012; Koriyama et al., 2013], where it is advised that smaller groups of voters shall obtain the number of representatives that is greater than the linear proportionality would require. In fact, degressive proportional committees can be observed in real world-European Parliament is perhaps the most commonly known example of such a committee [Rose, 2013]. 1

On the other hand, in certain applications one would prefer to use a voting rule that follows the opposite principle of regressive proportionality. As an example, consider a group of experts selecting grant proposals. Here, we want to use a rule that provides some degree of proportionality in order to ensure that different scientific disciplines are fairly represented among the selected project proposals. On the other hand, one would prefer to select projects that obtain a large support from the experts, following the idea of regressive proportionality.

1.1 Our Contribution

In this paper we introduce a new family of rules that follow the principles of degressive and regressive proportionality, and analyse these rules taking three different viewpoints:

1. The worst-case approach: for a given election rule we ask what is the guaranteed number of representatives that a coherent group of voters who form a γ-fraction of the society gets in the elected committee.
2. The average-case approach: assuming that the voters and the candidates are represented as points in a onedimensional issue space, we ask how different forms of proportionality map distributions of voters in the issue space to distributions of their satisfactions, measured as numbers of representatives in elected committees.
3. The analysis of the voting committee model [Skowron, 2015; Jaworski and Skowron, 2020]: we ask how different forms of proportionality map distributions of voters in the issue space to distributions of their satisfactions from decisions made by elected committees.

1 Degressive proportional rules have been also considered for selecting the United Nations Parliamentary Assembly [International Network for a UN Second Assembly, 1987] and for allocating weights in the Council of the European Union [BBC News, 2004].

Our rules extend Sequential Phragm´en's Rule, which is known to behave very well in terms of proportionality [Brill et al., 2018; Brill et al., 2017; Skowron, 2021; Peters and Skowron, 2020]. These rules are practical, and can be computed in polynomial time. In [Jaworski and Skowron, 2022] we compare them with other voting methods, such as (sequential) Thiele rules.

2 Preliminaries

For each n ∈ N we set [n] = {1, . . . , n}. For a set X we use Sk(X) to denote the set of all k-element subsets of X; by S(X) we denote the set of nonempty subsets of X.

An approval-based election is a quadruple (C, V,A, k), where C = {c1, . . . , cm} is a set of candidates, V = {v1, . . . , vn} is a set of voters, A: V → S(C) is a function that maps each voter to a subset of candidates that she approves-we call A an approval-based profile, and k is a desired size of the committee to be elected. We use n and m to denote the number of voters and candidates, respectively, i.e., |V | = n and |C| = m.

We call the elements of Sk(C) size-k committees, or simply committees, if k is clear from the context. An approvalbased committee election rule, in short a rule, is a function R that for each election instance E = (C, V,A, k) returns one or multiple size-k committees, i.e., R(E) ∈ S(Sk(C)). We call elements of R(E) winning committees.

3 The Class of α/β-Phragm´en's Rules

We introduce two classes of election rules that generalize the Phragm´en's sequential rule (for a broader discussion we refer to the recent survey by Lackner and Skowron [2020]). The definitions of those classes are based on the following idea. The voters earn virtual money-credits-over time (the time is continuous), and they use the credits they earned to pay for committee members that they approve; buying each candidate costs a certain amount of money. The rules are sequential-they start with an empty committee W = ∅ and iteratively add candidates to W. The voters are greedy: in the first time moment, when there is a group of voters and a not-yet-selected candidate c /∈ W, such that the voters who approve c have altogether certain amount of unspent money, the rule stops, adds c to the committee, asks the voters to pay for c (resetting their credits to zeros), and resumes. We finish when k candidates are selected.

In the original Phragm´en's sequential rule the voters earn credits with a constant speed (e.g., one credit per time unit) and each candidate costs 1 credit. Here, we consider the following two variants of the rule:

1. We allow the speed of earning to change, dependently on the number of candidates that the voters like in the already assembled committee. Formally, let us fix a positive, non-increasing, discrete function α : N+ → (0, 1] such that α(1) = 1. In the α-Phragm´en's rule, α(i) is the voter's speed of earning credits per time unit in case (i-1) committee members are already approved by the voter. In other words, each time voter v pays for the i-th candidate, her speed of earning credits changes to α(i + 1) and remains the same until the next v's purchase of a candidate.

In particular, the original Phragm´en's sequential rule corresponds to the α-Phragm´en's rule, for the constant sequence α. In this paper we will consider α-Phragm´en's rules for non-increasing functions α.

1. We allow the costs of the candidates to differ dependently on the number of voters who approve the specific candidate. Formally, let us fix a positive function β : [0, 1] → (0, 1] such that β(0) = 1. In the β-Phragm´en's rule, β(|V ′ |/|V |) is the cost of the candidate that is approved exactly by the voters from V ′ . In other words, the voters from V ′ can buy candidate c′ , if they have β(|V ′ |/|V |) credits in total. In particular, the original Phragm´en's sequential rule corresponds to the β-Phragm´en's rule, for the constant function β. In this paper we will consider β-Phragm´en's rules for non-increasing functions β.

Example 1. Consider an instance E = (C, V, A, k) depicted in Figure 1 for k = 3, and let us fix two functions: α(i) = (1/10)i-1 and β(x) = (1/4)7x . The procedures of selecting candidates to the committee according to α-Phragm´en's and β-Phragm´en's rules are as follows.

Let us first consider the α-Phragm´en's rule, which starts with the empty set W = ∅. Each voter earns credits with the speed of α(1) = 1 per time unit. At time 1/4 voters {v1, v2, v3, v4} buy candidate c1-these voters spend all sofar earned money on c1 and their speed of earning changes to α(2) = 1/10. Next, after 1/4 time units voters {v5, v6} buy candidate c2-let us check that voters {v5, v6} can afford to buy c2. Voters v5 and v6 have 1/4 + 1/4 = 1/2 credits each. Hence, in total they have one credit. At this moment:

1. W = {c1, c2};
2. Each voter from {v1, v2, v3, v4} has 1/40 credits and their speed of earning is α(2) = 1/10;
3. Voters from{v5, v6} have 0 credits. They approve one candidate in W, thus their speed of earning is α(2) = 1/10;
4. voter v7 earns credits with the speed of α(1) = 1, and she already has 1/2 credits.

In the last step the rule selects c3. Indeed, after 1/2 time units voter v7 who approves candidate c3 has one credit. What is more, within the considered time frame:

1. Each voter from {v1, . . . , v4} has 1 40 + 1 20 = 3 40 credits;
2. Each voter from {v5, v6} has 1/20 credits.

Based on the above observation, it is easy to see that no other candidate can be bought. Hence, W = {c1, c2, c3}.

Now, let us consider the β-Phragm´en's rule. Again, we start with W = ∅. Each voter earns money with the speed of one credit per time unit. At time 1/1024 voters {v1, v2, v3, v4} buy candidate c1 (since candidate c1 is approved by 4 voters, she costs β(4/7) = 1/256)-these voters spend all sofar earned money on c1. Next, after 1/192 time units voters from {v1, v2, v3} can buy candidate c4 and voters from {v1, v2, v4} can buy candidate c6. On the other hand, let us check that voters {v5, v6} cannot afford to buy c2 in that time frame. Indeed, voters from {v5, v6} have 2 · 1/1024 + 2 · 1/192 = 3+24/3·29 < 1/16. Let us assume that candidate c6 is bought by {v1, v2, v4} and finally after 1/288 time units voters from {v1, v2, v3} can buy candidate c4-indeed, they have 1/192 + 3 · 1/288 = 1/192 + 1/96 = 3/192 = 1/64. One can also easily compute that other candidate cannot be bought in that time frame. Hence, W = {c1, c4, c6} is winning. ⊣

4 Proportionality of α/β-Phragm´en's Rules

In this section we assess how well committees returned by αPhragm´en's and β-Phragm´en's rules represent minorities of voters, depending on the sizes of these minorities.

In Definition 1 we formulate the axiom of proportional justified representation degree (PJR degree), which is a quantitative variant of PJR [S´anchez-Fern´andez et al., 2017]. Similarly to PJR and other related properties, such as extended justified representation (EJR) [Aziz et al., 2017] or lower quota [Brill et al., 2018; Lackner and Skowron, 2018], our axiom requires that groups of voters of sufficient sizes and with cohesive preferences should have right to decide about certain fractions of elected committees. However, since our goal is to analyze rules which are not proportional in the classic sense, our axiom does not have an encoded threshold specifying how many candidates cohesive groups of voters are allowed to elect. Instead, this threshold is provided as an adjustable function which allows to quantify the level to which the rule respects opinions of voters with cohesive preferences. This way, the axiom is more similar to proportionality degree [Skowron, 2021], a quantitative version of EJR [Aziz et al., 2017]. Considering a quantitative variant of PJR rather than of EJR is motivated by the fact that the original Phragm´en's rule which we generalise in this paper, satisfies PJR and violates EJR. Thus, when analyzing the PJR degree of α/β-Phragm´en's rules for other than constant α/β-functions, we will have a reference point of a perfectly linearly-proportional rule in the class.

Definition 1 (Proportional justified representation (PJR) degree). Let f : [0, 1] × N → Q. We say that a rule R has the PJR degree of f if for each election instance E = (C, V, A, k), each winning committee W ∈ R(E), and each group of voters S ⊂ V it holds that:

For example, if a group of voters S form 20% of the whole society and if it agrees on sufficiently many candidates (∣∣⋂v∈S A(v)∣∣ is sufficiently high), then the PJR degree of f means this group is allowed to decide at least about f(0.2, k) members of the committee. If those voters agree on less than f(0.2, k) candidates, the number of candidate they are allowed to decide about is truncated accordingly.

Below, we present the main theoretical results for the αPhragm´en's rule.

Theorem 1. Fix a non-increasing, positive function α : N+ → (0, 1]. The α-Phragm´en's rule has the PJR degree of fα, where fα(γ, k) is the largest natural number ℓ that:

Proof strategy. The proof follows by estimating two bounds: one on the number of credits that a cohesive group of voters S must collect until time t, and the other one on the number of credits the remaining voters can earn until t. The first bound implies that at least a certain number of candidates paid by the voters from S must be selected until t, and the second implies that the process cannot end too soon (that is, it lower bounds the time t). Together, they imply the desired PJR guarantee.

The tricky part is to accurately estimate the first bound. For that we analyze a broader class of mechanisms which follow certain constraints with respect to how the voters earn and spend money. This extension of the domain allows us to apply local-search changes to the initial election instance, and characterize those elections which are worst-case in terms of the analysis of PJR degree. It happens that these elections are also worst-case for the specific rule at hand. The formal proof is given in [Jaworski and Skowron, 2022].

The results presented in the Theorem 1 are general, but hard to interpret. In order to simplify the expression presented in the Theorem 1 we observe that ∑ℓi=1 1/α(i) ≥ ℓ, and formulate the following corollary.

Corollary 1. Fix a non-increasing, function α : N+ → (0, 1]. The α-Phragm´en's rule has the PJR degree of fα, where fα(γ, k) is the largest natural number ℓ such that:

Corollary 1 provides bounds which are easier to interpret, but weaker than those given in Theorem 1. Nevertheless, even Corollary 1 itself implies that the classic Phragm´en's rule, which corresponds to the α-Phragm´en's with the constant function α(i) = 1, has the PJR degree of f(γ, k) = γ(k + 1) > γ · k, which implies satisfying PJR.

We will use the simplified expression from Corollary 1 to obtain PJR degree for geometric Phragm´en rules with q < 1.

Proposition 1. For a function α(i) = qi-1 , where q < 1, the α-Phragm´en's rule has the PJR degree of fα:

The comparison of the results implied by Theorem 1 and Proposition 1 for two concrete examples of geometric αPhragm´en's rules are depicted in Figure 2. This figure leads to an interesting interpretation of what is degressive proportionality. At first one could expect that the PJR degree of a degressive proportional rule should have a plot that for small values of γ lies above the plot for the linear function g(γ) = γ. Somehow surprisingly, this is not the case and the worst-case guarantee of each group is worse than in case of linear proportionality. The intuitive reason is that for each small cohesive group of voters there can always appear multiple groups which are even smaller and which should be even more privileged. Figure 2 quantifies this effect in the worst-case. On the other hand, degressive proportionality means that for small values of γ the ratio the PJR degree between a larger and a smaller group of voters is sublinear compared to the ratio of the sizes of the groups. This is visible by observing that for small values of γ (here γ ≤ 1/2) the derivative of the PJR degree is decreasing. We infer that one of the distinctive properties of the degressive proportionality is that the derivative of the proportionality guarantee is convex.

Let us now we move to the analysis of β-Phragm´ens' rules.

Theorem 2. Fix a non-increasing, positive function β : [0, 1] → (0, 1] with β(0) = 1. The β-Phragm´en's rule has the PJR degree of fβ, where

Using the assumptions that β is non-increasing, (for γ ≥ 1/2 we have β(γ) ≤ β(1-γ) and for γ ≤ 1/2 we have β(γ) ≥ β(1 - γ)) we obtained a simplified version of the bounds.

Corollary 2. The lower bound for PJR degree, fβ(γ, k), satisfies the following:

One could expect that the separated guarantee for regressive-proportional rules should be a function that is below f(x) = x for small arguments and above f(x) = x for large arguments. This is indeed the case, as illustrated in Figure 3; the exact shape of the function quantify this effect. Similarly, according to our intuition the derivative of the PJR degree for regressive proportional rules is concave.

One can naturally ask: what if the speeds of earning money in the definition of α-Phragm´en's rules are increasing? Will we obtain a regressive proportional rule? Interestingly, this is not the case, which is illustrated in the following example.

Example 2. Consider an α-Phragm´en's rule with α(i) = i100 , and the following election instance. There are 100 voters. Voters v1, . . . v55 approve candidate c1. Additionally, voters v1, . . . v30 approve c2, c3, . . . , c6. Further, voters v51, . . . v100 approve c7, c8, . . . , c13. The size of the committee to be elected is k = 6. Here, the α-Phragm´en's rule would select c1, . . . , c6. Thus, the candidates who are approved by 50 voters, c7, c8, . . . , c13, would not be selected even though the voters who approved such candidates got only one or zero representatives. Instead, the rule would pick candidates who are approved by only 30 voters. This is not consistent with our interpretation of regressive proportionality. In contrary, from Corollary 2 it follows that each β-Phragm´en's rule would guarantee at least 3 candidates in the committee from those that are approved by 50 voters. ⊣

Example 2 is very instructive. It illustrates that designing voting rules based solely on the intuitive premises can have undesirable effects. This illuminates the need of applying formal methods to the analysis of voting rules. Indeed, for an increasing function α the α-Phragm´en's rule does not have a good PJR degree. In fact, exactly this observation has lead us to the definition of the class of β-Phragm´en's rules.

5 Degressive and Regressive Proportionality in the Euclidean Model

We will now analyze, through experiments, how voters' satisfaction depends on using committee election rules implementing different types of proportionality.

5.1 Distributions of Voters' Preferences

We consider the 1-D Euclidean model, where each individual (a voter or a candidate) is represented as a point in the interval [-1; 1]. Intuitively, this point represents the position of the individual in the left-right political spectrum. The Euclidean model is commonly used in political science [Davis and Hinich, 1966; Plott, 1967; Enelow and Hinich, 1984; Enelow and Hinich, 1990; McKelvey and Ordeshook, 1990; Schofield, 2007], and-more recently-in computational social choice [Elkind and Lackner, 2015; Elkind et al., 2017; Faliszewski et al., 2018; Faliszewski and Talmon, 2018].

We draw the individuals independently at random from beta distributions, scaled into [-1, 1]. We consider: Beta(1/2, 1/2), Beta(1/2, 2), Beta(2, 2), Beta(2, 4). The voters' preferences are constructed from their positions as follows. We fix the approval radius ξ ∈ {0.1, 0.2, 0.3, 0.4, 0.5}, and assume that a voter v approves a candidate c if and only if |v - c| ≤ ξ. We set a threshold of 0.5 for the approval radius-higher values would imply that there might exist voters that approve e.g. extreme right-wing candidates and leftwing candidates. The elections drawn this way belong to the candidate-interval domain [Elkind and Lackner, 2015]. Further, each election instance from the candidate-interval domain can be obtained from the 1-D Euclidean model.

5.2 Voting Rules Used in Simulations

In our simulations we select winning committees using one of the following rules:

1. Degressive: α-Phragm´en's with α(i) = (1/2)i ;
2. Regressive: β-Phragm´en's with β(x) = (9/10)100x ;
3. Linear: α-Phragm´en's with α(i) = 1 (which equivalent to Phragm´en's Sequential rule).

5.3 TwoMeasures of Voters' Satisfaction

We quantify the satisfaction of the voters from the elected committees using two measures:

Number of Representatives. In this case the satisfaction of a voter v from a committee W equals to the number of committee members that v approves, sat(v) = |W ∩ A(v)|.

Number of Satisfying Decisions. Our second measure is based on the analysis of the voting committee model [Skowron, 2015; Jaworski and Skowron, 2020]. The high level idea is the following. We assume that the voters and the candidates have preferences over a number of binary issues. The positions of the individuals are correlated with their preferences over the issues. Thus the voters and the candidates who are closer in the Euclidean space are more likely to have similar opinions regarding the issues. Next, we assume that the elected committee uses majoritarian voting to decide about the issues. We measure the satisfaction of a voter v as the fraction of the committee's decisions consistent with v's preferences. Formally, we use the following procedure.

1. We generate p issues according to the same beta distribution as the one from which we have sampled the voters and candidates-each issue is represented as a value from [-1; 1] which indicates the ideological characteristic of the issue. In our experiments we have used p = 100.
2. We assign to each individual a p dimensional binary vector, where in the i-th position of the vector we set 1 if the individual is for the issue, and 0 if she is against. We generate preferences over the issues using the Bernoulli distribution, where the probability of an individual η getting 1 in the i-th position in the vector depends on the position x of an issue in the space, and is given by the formula:

The function pη for different values of η (and τ = 30, δ = 120) is depicted in [Jaworski and Skowron, 2022]. Let us explain this function through an example. Consider a center-left individual η = -0.3. We assume that the issue in the center x = 0 represents the status quoaccepting it does not change the state of the world, hence no voter opposes to it. E.g., the position η = -0.3 might correspond to the preferred tax rate at the level of 35%, while the current tax rate-corresponding to position x = 0-is 31%. Further:

• (a) Every left-oriented issue x that is closer to the center than the individual (i.e., x ∈ [η, 0)) is always approved by η. Accepting it changes the status-quo towards the state that is preferred by the individual.
• (b) The more far-left the issue, the less likely it is that the individual accepts the issue. Our centre-left individual η has an aversion to radicalism, thus for x < η the probability function is increasing and convex.
• (c) For right-oriented issues the function is decreasing and convex; the slope is greater than in case of more left-oriented issues, as the individual η is centre-left.
• (d) The more radical the individual, the less probable it is that she accepts the issue with the opposite characteristics. For instance, for η1 > η2 > 0 and x < 0 we have that pη1 (x) < pη2 (x).

Such functions ensure that candidates that are closer to a voter v are more likely to have similar preferences as v regarding the issues (see [Jaworski and Skowron, 2022]).

Once we build an election with preferences over issues, we measure the satisfaction of each voter v as the fraction of issues for which v's preferences coincide with the committee's decision; recall that in the voting committee model the winning committee W makes majoritarian decisions.

5.4 Results of the Simulations

We present the results of the aggregated satisfaction of the voters in the form of box plots in Figure 4 and Figure 5. In order to simplify the visual presentation we divided the voters into three groups based on their position on the Euclidean line: [-1,-1/3), [-1/3, 1/3], (1/3, 1]. In the simulations we consider instances with n = 200 voters, m = 150 candidates and for the committee size k = 25. What is more, we set the acceptance radius τ = 0.2 and the parameters of the probability function pη to: τ = 30, δ = 120. We also checked several others sets of parameters (e.g. {τ = 5, δ = 20}, {τ = 10, δ = 60}), but we found that the key observations and regularities stay the same. We ran 1000 simulations for each scenario. Additional results can be found in [Jaworski and Skowron, 2022].

In Table 1 we give numerical values quantifying the voters' satisfaction. From the experiments we conclude:

1. Except for the case of polarized societies (i.e., scenarios (c) and (d) in Figures 4 and 5), we observe a positive cor-
2. relation between the voters' satisfactions quantified according to our two measures. This suggests that for such societies voters' satisfactions from the decisions made by the committee is related to the number of representatives these voters get in the elected committee. On the other hand, for the polarized societies there is no such a correlation. For example, in scenario (d) the groups of voters from less populous (and underrepresented) areas are more happy with the decisions made by the committees than the voters from the populous well represented poles. In such cases regressive proportional rules result in the distributions of the voters' satisfactions that more closely resemble densities of the voters' distributions.
3. We observe that for regressive proportional rules the shapes of the distributions of the voters' satisfactions (measured in either of the two ways) reflect the shapes of the densities of the voters' distributions. Interestingly, this relation is reflected to a slightly smaller extent for linear-proportional rules, and is not observed for the rules following the principle of degressive proportionality (see the plots (c) and (d) in Figure 5). In our opinion this weakens the arguments in favor of degressive proportionality that are sometimes raised in the literature.
4. In the voting committee model degressive-proportional rules favor less densely populated areas compared to the other rules, which is especially visible in case of asymmetric voters' distributions (cf. (b) and (c) in Figure 5).
5. The largest variance is observed for regressiveproportional rules-specifically for the case when the voters' satisfaction is measured as the number of representatives, for Beta(1/2, 2). What is more, in case of Beta(2, 4), around half of the voters from [-1,-1/3) have the satisfaction higher than 17 and around 25% have the satisfaction lower than 8.
6. In the voting committee model the highest average satisfaction of the voters from the committees' decisions is observed for the rules that follow linear proportionality. If we measure voters' satisfaction as the number of their representatives in the elected committees, then the highest total satisfaction is attained by rules that follow regressive proportionality (consult Table 1).

6 Conclusion

We have defined a family of committee election rules that extend Phragm´en's Sequential Rule. These rules span the spectrum of different types of proportionality. We have assessed the worst-case guarantees that these rules provide to groups of voters with similar preferences, and analyzed how these rules treat voters assuming the voters and the candidates are represented as points in the 1-D Euclidean space.

Acknowledgements

The authors were supported by the National Science Center in Poland within the OPUS programme (Project title: Multiwinner Election Rules: Beyond Scoring Protocols). We are very grateful to IJCAI reviewers for their thorough remarks.