Robust and Verifiable Proportionality Axioms for Multiwinner Voting

Introduction

The proportional representation of preferences is an important goal in many scenarios in which a subset of candidates needs to be selected based on the preferences of voters over those candidates. Such scenarios occur in a wide variety of applications, including parliamentary elections (Pukelsheim, 2014), participatory budgeting (Peters et al., 2021a), digital democracy platforms (Behrens et al., 2014), and blockchain consensus protocols (Cevallos and Stewart, 2021). In the (computational) social choice literature, this type of problem is often referred to as committee selection or multiwinner voting (Faliszewski et al., 2017; Lackner and Skowron, 2022). Some classic applications assume that candidates or voters (or both) come in predefined categories (political parties or voting districts), which greatly simplifies the task of finding representative outcomes. In the general case, when neither candidates nor voters come in predefined groups, it is surprisingly challenging to capture proportional representation formally. Perhaps as a consequence of this, the (computational) social choice literature has produced numerous competing criteria for when a selected committee qualifies as “proportional.”

What many of the existing definitions have in common is that they define proportionality over groups of voters whose preferences are similar to each other. This approach goes back to the seminal work of Dummett (1984), who defined proportionality for solid coalitions (PSC) in the setting where voters cast ranked ballots. PSC guarantees an appropriate level of representation to any group of voters that is “solidly committed” to a set of candidates in the sense that all voters of the group rank those candidates (in some order) over all other candidates. The most prominent example of a voting rule ensuring PSC is the widely used single transferable vote (STV).In his article on STV, Tideman remarked that “it is the fact that STV satisfies PSC that justifies describing STV as a system of proportional representation” (Tideman, 1995, page 27). Similar notions were subsequently introduced in the setting of approval-based multiwinner voting (Lackner and Skowron, 2022). In particular, extended justified representation (EJR) (Aziz et al., 2017a) and proportional justified representation (PJR) (Sánchez-Fernández et al., 2017) formulate proportional representation guarantees for “cohesive” groups; a group of voters qualifies as cohesive if the intersection of their approval sets is sufficiently large.

When voters with similar preferences fall short of the high standard of uniformity defined by “solid coalitions” or “cohesive groups,” the axioms stay mostly mute.PSC does not impose any lower bounds on the representation of an almost solid group. EJR, on the other hand, does at least impose weakened representation guarantees for less cohesive groups (Sánchez-Fernández et al., 2017). Indeed, this reliance on highly uniform voter groups has attracted criticism in the literature. For instance, Tideman remarked (in the context of discussing a rule satisfying PSC) that there may be “voters who would be members of a solid coalition except that they included an ‘extraneous’ candidate, which is quickly eliminated among their top choices. These voters’ nearly solid support for the coalition counts for nothing, which seems to me inappropriate” (Tideman, 2006, page 279). Aziz and Lee gave a concrete example for this behavior and stated — with regard to their own Expanding Approvals Rule (EAR) — that “understanding formally whether EAR, or other rules, satisfy Tideman’s notion of ‘robust’ PSC is an interesting avenue for future work” (Aziz and Lee, 2020, page 33). Relatedly, Hoffman et al. (2021) criticize that PSC is not compatible with ballot truncation. For instance, in an election where two candidates are to be elected and one quarter of the voters only rank $a$ whereas another quarter of the voters only rank $b$ before $a$, PSC would not require either $b$ or $a$ to be elected. This is further corroborated by the work of Marsh and Plescia (2016), who find frequent cases of vote splitting in Irish STV elections, which has the potential to make large solid coalitions quite rare.

Similar empirical criticism was also voiced for the justified-representation axioms in approval-based multiwinner voting. For instance, Bredereck et al. (2019) find that large cohesive groups do not seem to be very common in their experiments and that, for the preference models they studied, even a randomly chosen committee satisfies EJR and PJR with non-negligible probability. A similar effect was noticed by Szufa et al. (2022), who noted that the more “realistic” of their statistical models seem to have a low “cohesiveness level.”

An unrelated criticism of proportionality notions such as EJR and PJR is that they cannot be verified in polynomial time: It is coNP-complete to check whether a given committee satisfies EJR (Aziz et al., 2017a) or PJR (Aziz et al., 2018a). This is a crucial downside in applications in which the proportionality of the outcome needs to be verifiable (e.g., CeSt21a; MSW22a). The same criticism applies to AzLe20a’s generalization of PSC to weak preferences (i.e., rankings containing ties): it is coNP-complete to check whether a given committee satisfies the axiom (AzLe20a, Proposition 13). PSC itself, which is only defined for the special case of strict preferences (i.e., rankings without ties), is verifiable in polynomial time.

In this paper, we propose novel proportionality axioms that address the criticisms described above. Our axioms are (1) robust in the sense that they guarantee proportional representation also to voter groups that do not qualify as “solid” or “cohesive” and (2) verifiable in the sense that it can be checked in polynomial time whether a given committee satisfies the axiom or not. Our axioms are more demanding than existing ones, as they impose strictly more constraints on committees. Importantly, however, we show that these stronger proportionality requirements can be satisfied in all instances. Indeed, we identify voting rules from the literature that always produce committees satisfying our strong requirements. Our results can, therefore, be interpreted as evidence that those rules satisfy proportionality to a high extent. For an overview of the proportionality axioms considered in this paper, we refer to Figure 7 on page 7.

In the setting with approval preferences, we propose EJR+ as a robust and verifiable strengthening of EJR, together with a simply greedy procedure to compute committees satisfying EJR+. Using randomly generated preference profiles, we demonstrate that EJR+ is a considerably more demanding axiom compared to EJR and other existing axioms. We also observe that established rules such as Proportional Approval Voting (PAV) and the Method of Equal Shares (MES) satisfy EJR+ and that EJR+ can be — in contrast to EJR and PJR — efficiently verified.

In the setting with ranked preferences, we propose rank-PJR+ as a robust strengthening of Dummett’s PSC. In contrast to earlier strengthenings of PSC, rank-PJR+ can be efficiently verified even for general weak preferences. We observe that STV violates rank-PJR+. To the best of our knowledge, this establishes rank-PJR+ as the first satisfiable proportionality axiom that separates STV from more sophisticated methods such as the expanding approvals rule (EAR).Earlier strengthenings of PSC that are violated by STV are either sometimes unsatisfiable (AEFLS17) or equivalent to PSC in the case of strict preferences (for which STV is defined) (AzLe20a; AzLe21a). In order to prove that rank-EJR+ can always be satisfied, we extend the notion of priceability (PeSk20a) to the ranked preferences setting and show that EAR satisfies it. Moreover, we use randomly generated preference profiles to show that rank-PJR+ is much more demanding than PSC.

Finally, we extend our robustness approach to the proportionality degree (Skow21a) and to two applications that are closely related to multiwinner voting: participatory budgeting (PPS21a) and querying procedures for civic participation platforms (HKP+23a).

Our paper treats approval preferences and ranked preferences within a unified framework and establishes novel relationships between approval-based and ranking-based axioms. Hence, our work helps to consolidate the literature from the approval-based and ranking-based model, a task explicitly encouraged by LaSk22a.

2. Related Work

The study of proportional representation in multiwinner voting has a long tradition and voting rules aiming to produce proportional committees have been proposed long before the first proportionality notions have been formalized (see, e.g., the historical notes in the surveys by Tide95a, MMM96a, and Jans16a). For ranked preferences, the first and most well-known formal proportionality axiom is the aforementioned proportionality for solid coalitions (PSC), which was introduced by eminent philosopher Sir Michael Dummett (Dumm84a). Extensions of PSC to weak rankings were only recently introduced by AzLe20a; AzLe21a, who also provided a characterization of committees satisfying PSC (AzLe22a). AEFLS17 discussed several extensions or variants of Condorcet consistency to multiwinner voting. One of their notions, local stability, was independently studied by JMW20a.

In approval-based multiwinner voting (LaSk22a), proportionality axioms have received a lot of attention in recent years. Starting with the work of ABC+16a, who introduced not only EJR but also core stability, several papers either generalized these proportionality notions, found new rules satisfying them, or identified new settings to apply them. For instance, PJR was introduced by SFF+17a and subsequently studied by BFJL16a and AEH+18a, the proportionality degree was introduced by Skow21a and further studied by JaFa22a, individual representation was introduced by BIMP22a, and fully justified representation was introduced by PeSk20a, who also proposed the Method of Equal Shares and the concept of priceability.

Commonly studied formalisms that are closely related to approval-based multiwinner voting include participatory budgeting (PPS21a; LCG22a; BFL+23a; ALT18a), proportional rankings (SLB+17a; isbr21b; RST22a), and public decision-making (SkGo22a; FKP21a). In many cases, axioms like EJR and PJR and voting rules like PAV and MES have been adapted to these related settings. Interestingly, SkGo22a motivate their axioms with the goal to “[…] guarantee fair treatment for all groups of voters, not only the cohesive ones.” Since they work in a setting with multiple binary issues, their concepts and results do not translate to the multiwinner setting we study.

Finally, a recent line of work studying approximations of core stability in approval-based multiwinner voting and beyond (CJMW19a; PeSk20a; JMW20a; MSWW22a). Determining whether the core of an approval-based multiwinner election is always nonempty is considered an important open question (LaSk22a).

Preliminaries

In this section, we formally introduce the setting and review proportionality axioms and voting rules from the literature. For a natural number $n$, let $[n]$ denote the set $\{1,\dots,n\}$.

We consider a social choice setting with a finite set $C=\{c_{1},\dots,c_{m}\}$ of $m$ candidates and a finite set $N=[n]$ of voters who have ordinal preferences over the candidates. Throughout this paper, we assume that preferences have the following form: For each voter $i\in N$, there is a set $A_{i}\subseteq C$ of acceptable candidates and a complete and transitive preference relation $\succeq_{i}\,\subseteq A_{i}\times A_{i}$ over the acceptable candidates. In other words, $\succeq_{i}$ is a weak order over $A_{i}$. We let $\succ_{i}$ denote the strict part of $\succeq_{i}$. We assume that voters strictly prefer acceptable candidates to unacceptable ones, and that they are indifferent among unacceptable candidates.

For $A,B\subseteq C$, we write $A\succeq_{i}B$ (respectively, $A\succ_{i}B$) if $a\succeq_{i}b$ (respectively, $a\succ_{i}b$) holds for all $a\in A$ and $b\in B$. Further, for any $c\in A_{i}$ we let $\operatorname{rank}(i,c)=\lvert\{c^{\prime}\in C\colon c^{\prime}\succ_{i}c\}\rvert+1$ denote the rank voter $i$ assigns to candidate $c$. We say that voter $i$ ranks candidate $c$ higher than candidate $c^{\prime}$ if $c\succ_{i}c^{\prime}$, or, equivalently, $\operatorname{rank}(i,c)<\operatorname{rank}(i,c^{\prime})$. All unacceptable candidates $c\in C\setminus A_{i}$ are assigned a rank of $\operatorname{rank}(i,c)=+\infty$.

Besides the general case of weak-order preferences, we consider two important special cases. If $\succeq_{i}$ is a linear order over $A_{i}$, we say that voter $i$ has strict preferences. In this case, there are no ties between acceptable candidates. If, on the other hand, a voter is indifferent among all candidates in $A_{i}$, we say that the voter has dichotomous preferences. Dichotomous preferences naturally occur when using approval ballots, which is why we also refer to them as approval preferences. We use the term weak preferences to refer to the general case, i.e., when preferences are not assumed to be strict or dichotomous.

A preference profile $P=(\succeq_{1},\dots,\succeq_{n})$ contains the preferences of all voters. Note that, for each voter $i$, the set $A_{i}$ can be deduced from $\succeq_{i}$. We call a preference profile strict if all voters have strict preferences. If all voters have dichotomous preferences, we refer to $P$ as an approval profile and denote it as $P=(A_{1},\dots,A_{n})$. For a given approval profile and a candidate $c\in C$, we let $N_{c}=\{i\in N\colon c\in A_{i}\}$ denote the set of approvers of $c$.

We often write the preferences of voters as a strict ranking over indifference classes, omitting unacceptable candidates. The following example illustrates this.

Consider the following preference profile with $m=6$ candidates and $n=3$ voters.

Here, we have $A_{1}=\{c_{1},c_{2},c_{3},c_{4}\}$, $A_{2}=\{c_{2},c_{3}\}$, and $A_{3}=\{c_{3},c_{4},c_{5}\}$. The ranks that voter 1 assigns to the candidates are given by $\operatorname{rank}(1,c_{1})=1$, $\operatorname{rank}(1,c_{2})=\operatorname{rank}(1,c_{3})=\operatorname{rank}(1,c_{4})=2$, and $\operatorname{rank}(1,c_{5})=+\infty$. Voter 2 has dichotomous preferences and voter 3 has strict preferences.

A (multiwinner voting) instance consists of a set $N$ of voters, a set $C$ of candidates, a preference profile $P$, and target committee size $k\leq m$. A feasible committee is any subset $W\subseteq C$ with $\lvert W\rvert\leq k$. A (multiwinner voting) rule maps every instance $(N,C,P,k)$ to a non-empty set of feasible committees. We allow a rule to output more than one committee to account for ties and in order to be able to speak about rules such as EAR and STV (see Section 2.5) that come in several different variants. We say that a rule “satisfies” a proportionality notion if and only if, for each instance, every committee in the output of the rule satisfies the respective notion.

2. Proportionality Notions for Strict Preferences

We now turn to the proportionality notions defined in the literature, starting with the oldest and most prominent setting: multiwinner elections with strict preferences. In his classical work, Dumm84a introduced the notion of Proportionality for Solid Coalitions (PSC). To define this property, we first need to define the eponymous solid coalitions.

Given a strict preference profile, a subset $N^{\prime}\subseteq N$ of voters forms a solid coalition over a set of candidates $C^{\prime}\subseteq C$ if $C^{\prime}\succ_{i}C\setminus C^{\prime}$ for all $i\in N^{\prime}$.

Hence, voters in a solid coalition rank all candidates in $C^{\prime}$ higher than candidates outside of $C^{\prime}$, but the order among candidates in $C^{\prime}$ may differ among voters in the coalition. Since the group $N^{\prime}$ contains an $(|N^{\prime}|/n)$-fraction of all voters, PSC requires that at least $\lfloor(|N^{\prime}|/{n})k\rfloor$ candidates from this prefix are selected.In accordance with the literature on approval-based committee voting, our definition of PSC is based on the so-called Hare quota $\frac{n}{k}$. Different choices of quota are often discussed; e.g., the Droop quota is given by $\frac{n}{k+1}$ (AzLe20a).

3. Proportionality Notions for Approval Preferences

Inspired by Dumm84a, in the setting with approvalpreferences, ABC+16a and SFF+17a introduced their justified-representation axioms. Just as solid coalitions are the foundation for PSC, the justified-representation axioms build on cohesive groups.

This now serves as the main ingredient for the two most prominent justified-representation notions: extended justified representation (ABC+16a) and proportional justified representation (SFF+17a).

Given an instance with approval preferences, a feasible committee $W$ satisfies

By definition, EJR is a stronger requirement than PJR. Finally, we introduce the concept of priceability (PeSk20a; PPS21a).

Given an instance with approval preferences, a committee $W$ is priceable if there exist a $B>0$ and functions $p_{i}\colon C\rightarrow[0,\frac{B}{n}]$ such that the following conditions hold:

$\sum_{c\in C}p_{i}(c)\leq\frac{B}{n}$ for all $i\in N$

$\sum_{i\in N}p_{i}(c)=1$ for all $c\in W$

$\sum_{i\in N}p_{i}(c)=0$ for all $c\notin W$

${\sum_{i\in N\colon c\in A_{i}}\left(\frac{B}{n}-\sum_{c^{\prime}\in C}p_{i}(c^{\prime})\right)}\leq 1$ for all $c\in C\setminus W$

In this case, the pair $\{B,\{p_{i}\}_{i\in N}\}$ is called a price system for $W$.

PeSk20a have shown that every priceable committee of size $k$ satisfies PJR.

4. Proportionality Notions for Weak Preferences

For committee elections with general weak preferences, AzLe20a generalized the notion of solid coalitions (Definition 2) and PSC (Definition 3) in the following way.

Given a preference profile, a group $N^{\prime}\subseteq N$ of voters forms a generalized solid coalition over a set $C^{\prime}\subseteq C$ of candidates if $C^{\prime}\succeq_{i}C\setminus C^{\prime}$ for all $i\in N^{\prime}$.

In order to qualify as a generalized solid coalition, no candidate outside of $C^{\prime}$ can be ranked higher than any candidate inside $C^{\prime}$. Ties, however, are allowed.

To facilitate the definition of generalized PSC, we define the upper contour set of a set $C^{\prime}$ of candidates w.r.t. a set $N^{\prime}$ of voters as the set consisting of those candidates $c$ for which there is at least one voter in $N^{\prime}$ that does not rank all candidates in $C^{\prime}$ strictly higher than $c$. Formally, the upper contour set $\overline{C^{\prime}}(N^{\prime})$ of $C^{\prime}\subseteq C$ w.r.t. $N^{\prime}\subseteq N$ is defined as

Generalized PSC is equivalent to PJR when restricted to instances with approval preferences and — by definition — equivalent to PSC when restricted to instances with strict preferences. The former equivalence was proven by AzLe20a, who also introduced a rule that satisfies generalized PSC for general weak preferences (see Section 2.5).

In a follow-up work on participatory budgeting, AzLe21a introduced a slight strengthening of generalized PSC called Inclusion PSC (IPSC), which we reformulate here for our setting.

The following example illustrates the difference between generalized PSC and IPSC.

Consider the following instance with $n=3$ voters, $m=9$ candidates, and $k=6$.

Each voter $i\in\{1,2,3\}$ by herself forms a generalized coalition over the candidates with $\operatorname{rank}(i,c)\leq 3$ and deserves to be represented by $\frac{1}{3}k=2$ candidates. Moreover, voters 1 and 2 together form a generalized solid coalition over $\{c_{1},c_{2}\}$ of size $4\frac{n}{k}$. Generalized PSC prescribes that $c_{1},c_{7},c_{8}$, at least one of $\{c_{2},c_{3},c_{4}\}$, and at least one of $\{c_{2},c_{5},c_{6}\}$ needs to be selected. Therefore, the committee $W=\{c_{1},c_{3},c_{5},c_{7},c_{8},c_{9}\}$ satisfies generalized PSC. On the other hand, $W$ does not satisfy IPSC since the group $N^{\prime}=\{1,2\}$ solidly supports $C^{\prime}=\{c_{1},c_{2}\}$ with $c_{2}\notin W$ and $\lvert\overline{C^{\prime}}(N^{\prime})\cap W\rvert=\lvert\{c_{1},c_{3},c_{5}\}\rvert<4$.

We note that for strict preferences, IPSC and generalized PSC coincide with Dummett’s PSC.

For strict preferences, both IPSC and generalized PSC are equivalent to PSC.

AzLe20a have shown that it is coNP-complete to verify whether a given committee satisfies generalized PSC. We show that the same is true for IPSC.

Given an instance with weak preferences and a feasible committee $W$, it is coNP-complete to check whether $W$ satisfies IPSC.

First, we note that membership in coNP follows from the fact that if there is a violation to IPSC, one can use the candidates $C^{\prime}$ and group $N^{\prime}$ of voters as a witness to this violation, since it can be verified in polynomial time whether $N^{\prime}$ indeed form a generalized solid coalition and whether there are sufficiently many candidates selected from their upper contour set.

For the hardness, we reduce from the Clique problem. Given a graph $G=(V,E)$ and an integer $k^{\prime}$, the task is to determine whether there are $k^{\prime}$ vertices in $V$ forming a clique, i.e., a complete subgraph. Without loss of generality, we assume $\lvert V\rvert$ to be divisible by $k^{\prime}$; this can easily be achieved by adding isolated vertices. Since Clique is NP-complete, its complement is coNP-complete.

For a given Clique instance $(G,k)$, we construct a multiwinner voting instances as follows. Let $v_{1},\dots,v_{n}$ be the vertices of $G$. For each vertex $v_{i}$, there is one voter $i$ and one candidate $c_{i}$. Further, let $N(i)$ denote the set of candidates corresponding to the neighbors of $v_{i}$ in $G$. The preferences of voter $i\in[n]$ are given by

with all candidates in $N(i)$ being in a tie. We set the target committee size to $k=\frac{n}{k^{\prime}}$ and add $k$ dummy candidates $d_{1},\dots,d_{k}$. We claim that the committee $W=\{d_{1},\dots,d_{k}\}$ consisting of all dummy candidates satisfies IPSC if and only if there is no clique of size $k^{\prime}$ in $G$.

First, assume that $W$ does not satisfy IPSC. Then there must be a subset $N^{\prime}$ of voters solidly supporting a set of candidates $C^{\prime}$ such that $\lvert N^{\prime}\rvert\geq\frac{n}{k}=k^{\prime}$. Since, the unique first choice of each voter is the candidate corresponding to themselves, all candidates corresponding to voters in $N^{\prime}$ must be in $C^{\prime}$. Otherwise, they would not form a solid coalition, since there would be a voter missing their first choice candidate. Then, however, every vertex corresponding to a voter in $N^{\prime}$ must be connected to every other vertex, since they rank them at least at second place. Therefore, the vertices form a clique of size $k^{\prime}$.

On the other hand, if we have a clique of size $k^{\prime}$, the voters corresponding to the clique form a solid coalition of size $\frac{n}{k}$ over the candidates corresponding to the clique, thus witnessing a violation of IPSC. ∎

5. Multiwinner Voting Rules

Finally, we introduce four rules that we consider throughout the paper: EAR, MES, PAV, and STV. While the first two are defined for general weak preferences, PAV assumes approval preferences and STV assumes strict preferences. To emphasize the similarity between EAR, MES, and STV, we formulate these rules in a slightly non-standard way.

The expanding approvals rule (EAR) is a family of rules introduced by AzLe20a; AzLe21a for the general setting with weak preferences. Intuitively, the family consists of rules which give each voter a budget of $\frac{k}{n}$ with the goal to buy candidates for a price of $1$. The rules go rank-by-rank and check, for every rank $r$, if there is a candidate who can be afforded by the voters who assign a rank of at most $r$ to this candidate. If there is, one of these candidates is selected and the budget of the supporting voters is decreased by $1$ (the price of the candidate). See Algorithm 1 for an algorithmic template of these rules. Different instantiations of this family differ in (i) how they select the candidate to add (line 1) and (ii) how they decrease the budgets of the voters approving this candidate (line 1).

The Method of Equal Shares (MES) can be described as a special case of EAR. It was first introduced for instances with approval preferences by PeSk20a (who referred to it as “Rule X”) and subsequently generalized to participatory budgeting with additive utilities as well as strict rankings by PPS21a. In their variant of MES, PPS21a define it using their framework of additive utilities by assuming that the utilities are lexicographic. In our paper, we use a simplified version of the rule. To define MES, for a given $\rho>0$ and budgets $(b_{i})_{i\in N}$, we say that a candidate is $\rho$-affordable if $\sum_{i\in N_{c}^{r}}\min(\rho,b_{i})=1$. Here, $N_{c}^{r}$ denotes the set of voters who assign to $c$ a rank of at most $r$. MES is the variant of EAR which always selects the candidate which is $\rho$-affordable for the lowest $\rho$ and then reduces the budget $b_{i}$ for each $i\in N_{c}^{r}$ by $\delta_{i}=\min(\rho,b_{i})$.

A well-known rule for instances with approval preferences is proportional approval voting (PAV) (Thie95a). PAV selects all committees $W$ of size $|W|=k$ maximizing $\sum_{i\in N}\sum_{j=1}^{\lvert A_{i}\cap W\rvert}\frac{1}{j}$.

Finally, we consider the widely-used Single Transferable Vote (STV) family of voting rules (Tide95a), which assumes that preferences are strict. We again work with the Hare quota $\frac{k}{n}$. STV can be described similarly to EAR: Each voter is assigned a budget of $\frac{k}{n}$ in the beginning, with the price of a candidate being $1$. The crucial difference to EAR is that instead of going rank-by-rank, STV checks if there is a candidate who can be afforded by the voters ranking it first. If there is no such candidate, a candidate with the lowest amount of budget among voters ranking it first is eliminated. Different versions of STV differ in deciding (i) which candidate to eliminate, (ii) which affordable candidate to select, and (iii) how to transfer the surplus budget. For an algorithmic description, we refer to algorithm 2.

Approval Ballots

We first consider the case of approval preferences. Our notions for ranked preferences in Section 4 will build on the notions we develop here. We consider a robust strengthening of PJR in Section 3.1, a robust strengthening of EJR in Section 3.2, and a simple greedy algorithm satisfying the robust EJR notion in Section 3.3. In Section 3.4, we show that the robust EJR notion is considerably more discriminating than existing proportionality axioms for randomly generated instances.

Our point of departure is the following observation: Existing proofs establishing that certain voting rules satisfy justified-representation axioms like PJR and EJR do not actually use the fact that the voter group under consideration forms a cohesive group. (For example, this is true for the proof by ABC+16a that PAV satisfies EJR and for the proof by PeSk20a that MES satisfies EJR.) Instead, these proofs only argue about the existence of certain candidates that are not included in the committee but approved by the voter group. Based on this observation, we can reformulate justified-representation axioms in a robust way, moving away from arguing about cohesive groups and rather focusing on candidates outside the committee who have a valid “proportional” reason to be included. Adapting proportionality requirements in this way means that voter groups are no longer required to be highly cohesive in order to be properly represented in the committee. Rather, it is sufficient to identify an unselected candidate that is approved by all voters in the group and whose addition would bring the group closer to their justified representation.

Before defining our main new axiom in Section 3.2, we prepare the ground by reformulating (and renaming) an existing notion: Inclusion PSC. IPSC was originally defined for instances with general weak preferences (see Definition 9). When restricted to instances with approval preferences, AzLe21a observed that IPSC can be formulated as follows.

Given an instance with approval preferences, a feasible committee $W$ satisfies IPSC if and only if there is no group $N^{\prime}\subseteq N$ of voters so that

$\lvert N^{\prime}\rvert\geq(\left\lvert\bigcup_{i\in N^{\prime}}A_{i}\cap W\right\rvert+1)\frac{n}{k}$, and

there exists some $c^{*}\in\bigcap_{i\in N^{\prime}}A_{i}\setminus(\bigcup_{i\in N^{\prime}}A_{i}\cap W)$.

AzLe21a have also shown that, for approval preferences, IPSC is strictly stronger than PJR (and incomparable to EJR). We note that IPSC can be reformulated in a way that better aligns this with the definitions of axioms in Section 2.

Before defining our main new axiom in Section 3.2, we prepare the ground by reformulating (and renaming) an existing notion: Inclusion PSC. IPSC was originally defined for instances with general weak preferences (see Definition 9). When restricted to instances with approval preferences, AzLe21a have shown that IPSC is strictly stronger than PJR (and incomparable to EJR). Based on an earlier reformulation (AzLe21a, Proposition 9), we note that IPSC can be reformulated in a way that aligns with the definitions in Section 2.

In light of this observation, the name “Inclusion-PSC” is a misnomer when considering approval preferences. From now on, motivated by the fact that the property can be considered a robust strengthening of proportional justified representation (PJR), we will refer to this property as PJR+.

Given an instance with approval preferences, a committee satisfies PJR+ if and only if it satisfies IPSC.

This new name will also make it easier to recognize that we are applying the IPSC axiom to the special case of approval preferences.

We show that PJR+ can be verified in polynomial time by reducing the problem to submodular optimization (using the same reduction that BGP+19a used in the approval-based apportionment setting). This is in contrast to PJR, which is coNP-complete to verify (AEH+18a).

Given an instance with approval preferences and a feasible committee $W$, it can be verified in polynomial time whether $W$ satisfies PJR+.

To show that this function is submodular, we need to show that for any $N^{\prime\prime}\subset N^{\prime}\subset N_{c}$ and $i\in N_{c}\setminus N^{\prime}$ it holds that $f(N^{\prime\prime}\cup\{i\})-f(N^{\prime\prime})\geq f(N^{\prime}\cup\{i\})-f(N^{\prime})$. To see that this holds, we observe

Further, observe that a subset $N^{\prime}\subseteq N_{c}$ witnesses a violation of PJR+ if and only if $f(N^{\prime})\leq-1$. ∎

Finally, we note the following relationship between priceability and PJR+.We note that any priceable committee of size exactly $k$ can always be made priceable with a budget $B>k$. Hence, Proposition 3 generalizes Proposition 1 by PeSk20a.

For instances with approval preferences, any priceable committee with a price system $\{B,p\}$ such that $B>k$ satisfies PJR+.

Proposition 3 is a corollary of Proposition 6, which we prove in Section 4. Proposition 3 implies that MES and EAR, as well as the following approval-based voting rules, satisfy PJR+: Phragmén’s sequential rule (BFJL16a), the maximin support method (SFFB22a), and Phragmms (CeSt21a). Further, PAV also satisfies PJR+ (AzLe21a).

Like priceability, PJR+ is incomparable to EJR: Phragmén’s sequential rule satisfies PJR+, but not EJR, and there exist committees which satisfy EJR, but not PJR+ (AzLe21a).

2. Extended Justified Representation (EJR) Without Cohesiveness

PJR is a rather weak axiom, and strengthening it to PJR+ does not make much of a difference, as we will see in Section 3.4. Nevertheless, we can take the relationship between PJR and PJR+ as a blueprint for defining a robust strengthening of EJR. We call the resulting axiom EJR+.

To see how EJR+ is different from EJR, consider the two approval profiles illustrated in Figure 1. Both profiles have $n=8$ voters. We consider $k=4$, so that $\frac{n}{k}=2$.

For the instance on the left, consider the committee $W=\{c_{1},c_{3},c_{5},c_{7}\}$. This committee satisfies EJR, since all voters are covered, and every $2$-cohesive group contains at least one voter approving $2$ candidates in $W$. However, $W$ does not satisfy EJR+. For this, consider the candidate $c_{4}$ and the group $\{2,3,5,6,7,8\}\subseteq N_{c_{4}}$. This group has $6=3\frac{n}{k}$ members and thus deserves to be represented by $3$ seats; however, no group member approves $3$ candidates in $W$. Hence, $c_{4}$ has a justified claim to be included.

For the instance on the right, consider the committee $W^{\prime}=\{c_{1},c_{2},c_{3},c_{7}\}$. This committee satisfies EJR, since the only $2$-cohesive group $\{3,4,5,6\}$ is covered (voter $3$ even approves $3$ candidates in $W^{\prime}$) and since the group $N^{\prime}=\{4,5,6,7\}$ narrowly misses out on qualifying as a $2$-cohesive group. The group $N^{\prime}$ together with candidate $c_{5}$, however, witness a violation of EJR+, since they together deserve two candidates, but each group member approves at most one candidate in $W^{\prime}$.

By definition, EJR+ is a stronger requirement than EJR and PJR+.

A committee $W$ satisfying EJR+ satisfies EJR and PJR+ as well.

Moreover, we can utilize existing proofs to show that both MES and PAV satisfy EJR+.

Given an instance with approval preferences, PAV and MES satisfy EJR+.

An important advantage of EJR+ over EJR is that the former can be verified in polynomial time, whereas the latter is coNP-complete to verify (ABC+16a).

Given an instance with approval preferences and a committee $W$, it can be verified in polynomial time whether $W$ satisfies EJR+.

The requirements on a EJR+ committee can easily be encoded as constraints of an Integer Linear Program (ILP), enabling computational experiments that optimize a linear function (e.g., the total approval score) over the space of all EJR+ committees. Similar experiments are not feasible for EJR and have previously only been possible for very weak axioms (BFNK19a).

EJR+ is incomparable to alternative strengthenings of EJR known as fully justified representation (FJR) (PPS21a) and core stability (ABC+16a). To see that EJR+ does not imply FJR or core stability, we note that MES satisfies EJR+, but not FJR (PPS21a). To see that core stability does not imply EJR+, consider an instance with $2$ voters and $3$ candidates $c_{1},c_{2},c_{3}$ such that the first voter approves $c_{1}$ and $c_{2}$ and the second voter approves $c_{1}$ and $c_{3}$. The committee $\{c_{2},c_{3}\}$ is core-stable, but does not satisfy EJR+.

3. A Simple Greedy Procedure for Finding EJR+ Committees

Yet another advantage of EJR+ is that its definition gives rise to a very simple greedy procedure that produces committees satisfying EJR+ (and thus EJR) in polynomial time. The Greedy Justified Candidate Rule (GJCR), formalized as Algorithm 3, greedily selects candidates witnessing a violation of EJR+ constraints, ordered by decreasing size of the corresponding voter group.

The Greedy Justified Candidate Rule selects a committee of size at most $k$ and satisfies EJR+.

Our greedy rule allows us to have a simple and fast baseline algorithm for EJR+ (and EJR). This algorithm is arguably easier to understand (and to implement) than any other known algorithm satisfying EJR. Such a simple rule is also useful in the analysis of EJR+ and its properties, and in the design of new algorithms: As we show in Section 5.3, the greedy rule can be used to find faster query procedures in the setting of HKP+23a.

Furthermore, the simplicity of the Greedy Justified Candidate Rule allows us to show that EJR+ (and thus EJR) satisfy the following property, which can be considered a weak form of committee monotonicity.A rule satisfies committee monotonicity (a.k.a. house monotonicity or committee enlargement monotonicity) if selected candidates for a given committee size $k$ are also selected for committee size $k+1$. It is an open question whether EJR is compatible with committee monotonicity (LaSk22a, page 105). It was previously unknown that this property holds for EJR.

Consider an approval profile over a set $C$ of candidates. For all $k<m$, there exist a committee $W$ of size $|W|=k$ and candidate $c\in C\setminus W$ such that $W$ satisfies EJR+ w.r.t. committee size $k$ and $W\cup\{c\}$ satisfies EJR+ w.r.t. committee size $k+1$.

4. Experiments with Approval Ballots

In order to assess how demanding the notions studied in Sections 3.1 and 3.2 are, we ran experiments with randomly generated instances. As a measure for the discriminative power of an axiom, we consider the likelihood that a randomly drawn committee satisfies the axiom; stronger axioms yield lower values.

Following the recent work of SFJ+22a, we sample profiles from two different statistical cultures: the resampling model and the truncated urn model. We provide a brief description of these models below, and refer to the paper by SFJ+22a for details.

In the resampling model with parameters $p$ and $\phi$, an approval ballot $A$ approving $\lfloor pm\rfloor$ candidates is generated uniformly at random. Following this, for each voter $i$ and candidate $c$, the approval of $i$ to $c$ is kept as in $A$ with probability $1-\phi$ and resampled with probability $\phi$, with the probability of approval being $p$. This model generalizes the impartial culture.

The disjoint model has three parameters, $p,\phi$, and $g$. The model partitions the candidates into $g$ groups $C_{1},\dots,C_{g}$. Then, for each voter it samples $j\in[g]$ uniformly at random and runs the same procedure as in the resampling model with parameters $(p,\phi)$ and the approval ballot $C_{j}$ as the start vote.

In the noise model with parameters $\phi$ and $p$, we sample one vote approving $\lfloor pm\rfloor$ uniformly at random. For each voter, a new vote is then generated proportional to $\phi^{d}$, where $d$ is the distance of the new vote to the original vote.

In the truncated urn model with parameters $\alpha$ and $p$, we sample according to the Pólya-Eggenberger Urn Model with parameter $\alpha$, and truncate the corresponding ranking to approve the top $\lfloor pm\rfloor$ candidates.

For each model, we consider four different values for $p$: $0.2$, $0.4$, $0.6$, and $0.8$. For the resampling, noise, and disjoint models, we let $\phi$ vary between $0.01$ and $1$ (in steps of $0.01$) and for the truncated urn model, we let $\alpha$ vary between $0.01$ and $1$ (in steps of $0.01$). For each combination of parameter values, we sample $400$ instances with $100$ voters and $50$ candidates. For each instance, we sample one committee of size $k=10$ uniformly at random and check whether it satisfies PJR, EJR, PJR+, and EJR+.

Results

The results of our experiments are presented in Figures 3, 5, 4 and 2. We observe that the established axioms PJR and EJR are quite easy to satisfy for a lot of parameters. This is similar to the findings of BFNK19a and SFJ+22a. Moreover, the difference between PJR+ and PJR is often very small. EJR+, on the other hand, is almost always much more discriminating than all the other axioms. This is particularly true when the instances are “far away” from impartial culture (which corresponds to parameter value $\phi=1$ in the resampling model). Interestingly, the incomparability of PJR+ and EJR (see Remark 1) is also visible in some of the graphs.

Ranked Ballots

In this section, we consider multiwinner voting based on ranked preferences. Our results hold for general weak preferences, and we often mention the important special case of strict preferences. To motivate the need for more robust proportionality axioms, consider the following example with strict preferences.A similar (slightly more complex) example was given by AzLe20a. We discuss their example in Appendix A.

Consider an instance with four voters, $m=6$, $k=2$, and the following strict preferences:

Since there are no non-trivial (generalized) solid coalitions, even the strongest axiom IPSC (which coincides with PSC for strict preferences; see 1) enforces nothing. Thus, every committee satisfies IPSC, even $\{c_{4},c_{6}\}$. This committee could also be selected by STV (by first eliminating $c_{2}$ and $c_{3}$, then eliminating $c_{5}$, selecting $c_{4}$, eliminating $c_{1}$, and selecting $c_{6}$). However, this committee seems gravely unfair to the first two voters, who can make the claim that they should be represented by half of the committee. Even though they do not form a solid coalition, there exists a candidate, $c_{2}$, that represents those voters much better than any committee member. Hence, requiring voters to form (generalized) solid coalitions is too demanding a requirement in this instance.

A first attempt to define a notion of proportionality without reference to solid coalitions was made by AEFLS17 in the setting with strict preferences. According to their definition, a committee $W$ is locally stable if, for every group $N^{\prime}$ of voters with $\lvert N^{\prime}\rvert\geq\frac{n}{k}$, there is no single unchosen candidate $c\notin W$ with $\{c\}\succ_{i}W$ for all $i\in N^{\prime}$. However, this notion is not always satisfiable, and it is computationally intractable to decide whether an instance admits a locally stable committee (AEFLS17).

Recall from Section 2.4 that generalized PSC and IPSC can be defined using the upper contour set $\overline{C^{\prime}}(N^{\prime})$ of a set $C^{\prime}$ of candidates w.r.t. a set $N^{\prime}$ of voters. An intuitive idea to generalize these axioms could consist in requiring that

holds for any $N^{\prime}\subseteq N$ and unchosen candidate $c\in\bigcap_{i\in N^{\prime}}A_{i}$. This is, however, more demanding than local stability, and committees satisfying this notion may fail to exist.

In order to slightly relax the requirement above, we return to the concept of ranks. (Recall that only acceptable candidates are assigned finite ranks.) Using the concept of ranks, we can translate any instance with weak preferences into a collection of instances with approval preferences in a straightforward way: For each possible rank $r$, the approval set of a voter $i$ with preference relation $\succeq_{i}$ can be defined as the set of all candidates that have been assigned a rank of at most $r$ by voter $i$. To make this precise, consider an instance $(N,C,P,k)$ with weak preferences. For each $r\in[m]$, define the approval profile $P^{r}=(A_{1}^{r},\dots,A_{n}^{r})$ via $A^{r}_{i}=\{c\in C\colon\operatorname{rank}(i,c)\leq r\}$. This translation results in $m$ instancesThe approval profiles $P^{1}$, …, $P^{m}$ have a nested structure and are not necessarily distinct. In particular, if the profile $P$ has dichotomous preferences to begin with, then $P^{r}$ is identical to $P$ for all $r\in[m]$. with approval preferences, given by $(N,C,P^{1},k),\dots,(N,C,P^{m},k)$. Intuitively, an outcome which is proportional for the instance with weak preferences should also be proportional for all the approval instances derived from it. The following definition formalizes this idea.

Given an instance $(N,C,P,k)$ with weak preferences, a feasible committee $W$ satisfies rank-PJR+ if, for every $r\in[m]$, $W$ satisfies PJR+ in the instance $(N,C,P^{r},k)$.

This property can also be formulated without reference to PJR+.

Consider again the instance given in Example 1. The committee $\{c_{4},c_{6}\}$ does not satisfy rank-PJR+, since candidate $b$ is justified to be included in the committee via voter group $\{1,2\}$ in the approval instance $(N,C,P^{2},k)$, where each voter approves their two top-ranked candidates. An analogous violation of rank-PJR+ can be found for candidate $c_{3}$. A committee satisfying rank-PJR+ has to include at least one of $c_{2}$ or $c_{3}$. More precisely, rank-PJR+ requires that either (i) $c_{2}$ and one of $\{c_{3},c_{4},c_{6}\}$ or (ii) $c_{3}$ and one of $\{c_{1},c_{2},c_{5}\}$ is selected.

For instances with approval preferences, rank-PJR+ is equivalent to PJR+. To show that rank-PJR+ is always satisfiable, we turn to the concept of priceability (PeSk20a) and define a generalization to weak preferences.

The goal of this section is to generalize the notion of priceability (see Section 2.3) from approval instances to instances with general weak preferences. First, we note that the definition of a price system (i.e., the constraints C1 to C5 in Definition 4) generalize immediately from the approval setting to the ranked setting. Axiom C5 however, which is required to relate price systems to proportionality axioms, does not give us any proportionality guarantees in the ranked setting: Consider an instance with two voters, both of whom rank $c_{1}$ higher than $c_{2}$, and let $k=1$. Selecting $c_{2}$, a clearly suboptimal choice, results in a priceable committee, even with budget $B>1$. Unsurprisingly, the committee $\{c_{2}\}$ violates all our previously defined proportionality axioms for ranked preferences.

In order to relate priceability to proportionality, we thus need to strengthen C5. A first idea to do that would be to require that no candidate can be bought using unspent money and money spent on candidates ranked worse than them. Formally, this corresponds to requiring

While seemingly reasonable, this axiom is not always satisfiable, as a committee satisfying it would also be locally stable. Therefore, we relax the above inequality by considering ranks. Let $N_{c}^{r}=\{i\in N\colon\operatorname{rank}(i,c)\leq r\}$ be the set of voters ranking candidate $c$ at rank $r$ or higher. The following constraint, to which we refer as $\textbf{C5}_{\textbf{rank}}$, requires that the unspent money of $N_{c}^{r}$ plus the money this group spent on candidates ranked worse than $r$ is not enough to buy $c$.

We call a committee $W$ rank-priceable if there is a price system for $W$ satisfying $\textbf{C5}_{\textbf{rank}}$.Since $\textbf{C5}_{\textbf{rank}}$ implies C5, there is no need to require C5 explicitly.

Given an instance with weak preferences, a committee $W$ is rank-priceable if there exist a $B>0$ and functions $p_{i}\colon C\rightarrow[0,\frac{B}{n}]$ satisfying C1–C4 and $\textbf{C5}_{\textbf{rank}}$.

It is easy to see that these constraints can be verified using a linear program.

Given an instance with weak preferences and a committee $W$, it can be verified in polynomial time whether $W$ is rank-priceable.

Next, we show that rank-priceability implies PJR+.

Any rank-priceable feasible committee with a price system $\{B,p\}$ such that $B>k$ satisfies rank-PJR+.

Assume that $W$ does not satisfy rank-PJR+. Then there is a rank $r\in[m]$ such that $W$ does not satisfy PJR+ in the approval instance $(N,C,P^{r},k)$. Thus, there is a group of voters $N^{\prime}$ and a candidate $c\in\bigcap_{i\in N^{\prime}}A_{i}^{r}\setminus W$ with

which is a contradiction to $\textbf{C5}_{\textbf{rank}}$. ∎

In order to prove that rank-PJR+ is always satisfiable, it is therefore sufficient to identify rules that produce rank-priceable committees. We show that EAR is such a rule.

Any committee in the output of EAR is rank-priceable for some $B>k$.

First, we observe that during the execution of EAR (Algorithm 1) we indeed construct a pricesystem satisfying C1–C4 for budget $B=k$. Further, if there was an unpicked candidate at rank $r$ with a budget of $1$ or more left among the voters ranking it at least as good as $r$, this candidate would be selected. Hence, the inequality in $\textbf{C5}_{\textbf{rank}}$ is strict. It follows that there exists $\varepsilon>0$ such that the inequality also holds for $B=k+\varepsilon$. Thus, each EAR committee is indeed rank-priceable. ∎

As a consequence, EAR (and thus also MES) satisfies rank-PJR+. We can further show that rank-priceability is a strictly stronger requirement than rank-PJR+, even for strict preferences.

There exist committees $W$ which satisfy rank-PJR+, but not rank-priceability.

Consider the following instance with $n=2$ voters, $m=6$ candidates, and $k=3$.

The committee $\{c_{1},c_{4},c_{5}\}$ satisfies rank-PJR+. Candidates $c_{2}$ and $c_{3}$ cannot witness a violation of rank-PJR+ in the second rank, since both voters only deserve $\frac{3}{2}$ candidates. However, independent of the price system, there is one voter spending at least $1$ on $c_{4}$ and $c_{5}$ and thus witnesses a rank-priceability violation for rank $2$. ∎

In our experiments (see Section 4.3), committees satisfying rank-PJR+, but not rank-priceability were extremely rare. In other words, rank-priceability is not a significant strengthening of rank-PJR+ and mainly serves the technical purpose of establishing the existence of rank-PJR+ committees.

Finally, we note that rank-PJR+ is indeed a stronger notion than IPSC, even for strict preferences.

Any committee satisfying rank-PJR+ also satisfies IPSC, but there are committees which satisfy IPSC, but not rank-PJR+. The latter holds even for strict preferences.

As stated earlier, the latter part follows from Examples 1 and 3. To see that rank-PJR+ implies IPSC, let $W$ be a committee satisfying rank-PJR+ and $N^{\prime}\subseteq N$ be a set of voters forming a generalized solid coalition over a set $C^{\prime}\subseteq C$ of candidates. Then, for $r=\lvert C^{\prime}\rvert$, we see that $\bigcup_{i\in N^{\prime}}A_{i}^{r}$ is precisely $\overline{C^{\prime}}(N^{\prime})$, since any candidate with at most $r-1$ candidates ranked better, must be ranked equal to a candidate from $C^{\prime}$. Further, by definition it holds that $C^{\prime}\subseteq A_{i}^{r}$ for all $i\in N^{\prime}$ and thus, there must be a candidate $c\in\bigcap_{i\in N^{\prime}}A_{i}^{r}\setminus W$. Hence, due to rank-PJR+, at least $\frac{\lvert N^{\prime}\rvert k}{n}$ candidates must be selected from $\bigcup_{i\in N^{\prime}}A_{i}^{r}$ and thus from $\overline{C^{\prime}}(N^{\prime})$. ∎

To the best of our knowledge, rank-PJR+ is the first proportionality axiom for strict preferences that is always satisfiable and violated by STV (see Examples 1 and 3). Therefore, our results can be interpreted as an axiomatic argument against STV (and in favor of rules such as EAR and MES).

2. Other Rank-Based Notions

Analogously to rank-PJR+, one can define rank-versions for other approval-based axioms. In light of the positive results from Section 3, it is particularly tempting to consider rank-EJR+.

Given an instance $(N,C,P,k)$ with weak preferences, a feasible committee $W$ satisfies rank-EJR+ if, for every $r\in[m]$, $W$ satisfies EJR+ in the instance $(N,C,P^{r},k)$.

However, there exist instances where rank-EJR+ (and even rank-EJR) is unsatisfiable.

Consider an instance with $n=2$, $m=4$, $k=2$, and preferences $c_{1}\succ_{1}c_{2}\succ_{1}c_{3}\succ_{1}c_{4}$ and $c_{4}\succ_{2}c_{2}\succ_{2}c_{3}\succ_{2}c_{1}$. For $r=1$, rank-EJR+ would require both $c_{1}$ and $c_{4}$ to be selected, while for $r=3$, either $c_{2}$ or $c_{3}$ needs to be selected.

One could also consider $\operatorname{rank}$-PJR, for which we note the following relationships.

For weak preferences, rank-PJR+ implies $\operatorname{rank}$-PJR. Furthermore, $\operatorname{rank}$-PJR is incomparable to IPSC and implies generalized PSC.

First, we notice that rank-PJR+ implies $\operatorname{rank}$-PJR by definition, since PJR+ implies PJR. To see that IPSC does not imply $\operatorname{rank}$-PJR, we refer to Example 1. Here, the committee $\{d,f\}$ satisfies IPSC but not $\operatorname{rank}$-PJR. Similarly, PJR is strictly weaker than IPSC for approval preferences and hence, also does not imply it for weak-rankings.

For strict preferences, $\operatorname{rank}$-PJR implies PSC and IPSC, but is not implied by them.

3. Experiments With Ranked Ballots

As in the setting with approval preferences (Section 3.4), we again ran experiments with randomly generated instances in order to compare the discriminative power of the proportionality axioms considered in this section.

We use a setting with $100$ voters and $50$ candidates and we generate strict rankings over all candidates using four different models: the classic Mallows model and urn model, as well as the Euclidean hypersphere and hypercube models, in which voters and candidates are uniformly distributed in a $d$-dimensional hypersphere or hypercube, with voters ranking candidates by distance. Detailed descriptions of these models can be found, e.g., in (BBF+21a).

For the Mallows model, we vary the $\phi$ parameter from to $1$; in the urn model, we vary the $\alpha$ parameter from to $0.2$; and in the Euclidean models, we vary the dimension from $1$ to $100$. For each parameter combination, we sample $300$ instances and one committee per instance, and we check whether this committee satisfies PSC, rank-PJR+, and rank-EJR+.

Results

The results are presented in Figure 6. We find that both rank-PJR+ and rank-EJR+ are significantly more discriminating than PSC. Moreover, rank-EJR+ is harder to satisfy than rank-PJR+ (but committees satisfying the former axiom are not guaranteed to exist).

Extensions

Finally, we demonstrate the value of our robustness approach by applying it to three related settings.

This is indeed a stronger notion than the proportionality degree.

Any $f$-representative voting rule also has a proportionality degree of $f$.

An important advantage of the new notion is that we can efficiently check whether a given committee is $f$-representative.

Given an instance with approval preferences and a committee $W$, we can check in polynomial time whether $W$ is $f$-representative.

By contrast, the proportionality degree is coNP-complete to verify (JaFa22a).

2. Participatory Budgeting

Participatory Budgeting (PB) is a democratic innovation that enables citizens to decide on budget allocations of cities or districts (Caba04a). PB elections can be treated as a generalization of multiwinner voting in which the candidates (which are now referred to as projects) have a cost and the total cost of selected projects cannot exceed a given budget limit.

Several papers have suggested generalizations of proportionality axioms from multiwinner voting to the PB setting. Here, we focus on PB instances with approval preferences and we assume that the utility of a voter is given by the cost of the approved projects in the final allocation (ALT18a; AzLe21a). Another common assumption is to measure the utility of a voter via the number of approved projects in the final allocation (PPS21a; LCG22a). Other utility functions have been considered by BFL+23a and MREL23a. Our robustness approach can be applied to notions like EJR/PJR up to one project (PPS21a) and EJR/PJR up to any project (BFL+23a).

To facilitate the comparison of axioms, we state the definition of EJR up to any project from the paper by BFL+23a.

Given an approval-based PB instance, a committee $W$ satisfies EJR up to any project (for cost utilities) if for every group $N^{\prime}\subseteq N$ of voters and group $T\subseteq\bigcap_{i\in N^{\prime}}A_{i}$ of projects such that $\sum_{p\in T}c(p)\leq\frac{\lvert N^{\prime}\rvert b}{n}$, there is a voter $i\in N^{\prime}$ with

A robust strengthening of this axiom can be defined as follows. (Here, $c(p)$ denotes the cost of project $p$ and $B$ denotes the budget limit.)

Given an approval-based PB instance, a feasible committee $W$ satisfies EJR+ up to any project (for cost utilities) if for every group $N^{\prime}\subseteq N$ of voters and $p\in\bigcap_{i\in N^{\prime}}A_{i}\setminus W$, there is an $i\in N^{\prime}$ with

The axiom in Definition 7 is stronger than EJR up to any project, but can be satisfied by an appropriate generalization of MES to the PB setting, using the approach of (PPS21a)

Given a PB instance, MES starts with an empty committee $W=\emptyset$ and assigns a budget $b_{i}=\frac{b}{n}$ to each voter $i\in N$. A project $p\notin W$ is $\rho$-affordable if

It then selects the project $p_{j}$ which is $\rho$-affordable for the minimum $\rho$ and sets the budget $b_{i}$ is updated to $b_{i}-\min(b_{i},\rho c(p))$ for every approver $i$ of $p$. MES continues until no $\rho$-affordable projects are left.

This generalization now satisfies EJR+ up to any project.

MES generalized to PB with cost utilities satisfies EJR+ up to any project.

Assume that the output $W$ of MES does not satisfy EJR+ up to any project. Thus, there is a project $p$ and voters $N^{\prime}\subseteq N_{p}$ with $c(A_{i}\cap W)+c(p)\leq\frac{\lvert N^{\prime}\rvert b}{n}$. Since $p$ is no longer affordable, we know that $\sum_{i\in N^{\prime}}b_{i}<c(p)$. Thus, we get that

Hence, one voter must pay more than $\frac{1}{\lvert N^{\prime}\rvert}$ per utility they receive and there must have been a candidate selected with a $\rho$ larger than $\frac{1}{\lvert N^{\prime}\rvert}$. However, in the moment this candidate got selected, each voter in $N^{\prime}$ still had less than $\frac{c(A_{i}\cap W)}{\lvert N^{\prime}\rvert}\leq\frac{b}{n}-\frac{c(p)}{\lvert N^{\prime}\rvert}$ budget left. Thus, $p$ was still $\frac{1}{\lvert N^{\prime}\rvert}$-affordable, a contradiction. ∎

We can also define a robust version of PJR up to any project.

Given an approval-based PB instance, a feasible committee $W$ satisfies PJR+ up to any project (for cost utilities) if for any $N^{\prime}\subseteq N$ and $p\in\bigcap_{i\in N^{\prime}}A_{i}\setminus W$, it holds that

PJR+ up to any project would then in turn be implied by priceability (this statement can be proven analogously to Proposition 6). This generalizes Theorem 4.4 by BFL+23a and implies that the PB generalizations of MES and other rules such as Phragmén’s sequential rule satisfy PJR+ up to any project.

3. Querying Procedures

Motivated by the application of civic participation platforms, HKP+23a have recently introduced the problem of querying procedures for proportional committees. They study two models: (i) An exact query model, in which one can query a subset of candidates $C^{\prime}\subseteq C$ and, for each subset of $C^{\prime}$, get the number of voters approving exactly this subset; and (ii) a noisy model, where for a given queried subset $C^{\prime}\subseteq C$, a single voter $i$ is selected uniformly at random and the set $A_{i}\cap C^{\prime}$ is returned. Using these models, they showed how to simulate the Local Search-PAV procedure by AEH+18a to find a committee satisfying EJR using $\mathcal{O}(mk^{2}\log(k))$ queries in the exact case and $\mathcal{O}(mk^{6}\log(k)\log(m))$ queries with high probability in the randomized case.

We show how the Greedy Justified Candidate Rule (Algorithm 3) can be employed to improve these bounds. The simplicity of the rule allows us to show that a committee satisfying EJR+ can be found using $\mathcal{O}(m\log(k))$ queries (of size at most $k$) in the exact model and with high probability using $\mathcal{O}(mk^{4}\log(k)\log(m))$ in the noisy model.

We start with the exact setting and show that the Greedy Justified Candidate Rule (Algorithm 3) can be simulated using $\mathcal{O}(m\log(k))$ queries.

The Greedy Justified Candidate Rule can be implemented using $\mathcal{O}(m\log(k))$ queries of size at most $k$.

We show that it can be implemented in $\mathcal{O}(m\log(k))$ queries. Let $\{c_{1},\dots,c_{i}\}$ be the already selected candidates. Then we can partition the unselected $m-i$ candidates into $\lceil\frac{m-i}{k-i}\rceil$ sets $S_{1},\dots,S_{\lceil\frac{m-i}{k-i}\rceil}$ of size at most $k-i$. By querying every $S_{j}\cup\{c_{1},\dots,c_{i}\}$, we can determine the next candidate who would be chosen by GJCR. Thus, we only need to query

Next, we show how GJCR can be adapted to the noisy model as Algorithm 4.

For any $\delta>0$, Algorithm 4 with probability $1-\delta$ and $\mathcal{O}(mk^{4}\log(m)\log(k))$ queries returns a committee of size at most $k$ satisfying EJR+.

Hence, the probability that a small candidate is selected is at most $\frac{\delta}{4}$.

Similarly, we can bound the probability of a large candidate not being selectable by

Thus, since at most $k$ candidates get selected, we use $h\mathcal{O}(m\log(k))=\mathcal{O}(mk^{4}\log(m)\log(k))$ queries in total. ∎

Conclusion

We have proposed novel proportionality axioms for multiwinner voting, both in the approval-based and in the ranking-based setting. Figure 7 summarizes the relations between the proportionality axioms considered in this paper. Our axioms are more robust and easier to verify than existing ones. Moreover, committees satisfying these axioms are guaranteed to exist and can be found by applying polynomial-time computable voting rules that have other attractive properties (AzLe20a; PeSk20a; PPS21a).

We have demonstrated that our approach can also be used to “robustify” the proportionality degree and proportionality axioms for participatory budgeting. The computational benefits of our approach go beyond verifiability: The simple structure of EJR+ enables the optimization over all EJR+ committees and gives rise to a simple and very useful greedy procedure.

Our work gives rise to multiple follow-up questions. First, it would be interesting to see whether a robust version of fully proportional representation (FJR) (PPS21a) can be defined. Finding such a generalization might prove useful in answering the open question whether committees satisfying FJR can be found in polynomial time. Second, our extensions to participatory budgeting (Section 5.2) only apply to cost utilities. Are there similar notions which also apply to other utility notions (BFL+23a), or maybe even to general additive utilities? Third, it would be interesting to see if there is a generalization of EJR+ to the ranked setting that is always satisfiable.

References

Appendix A Example of Aziz and Lee

AzLe20a considered the following example to demonstrate a weakness of PSC.

There are $n=9$ voters and $k=3$, so that $\frac{n}{k}=3$. In this instance, STV could select the committee $\{e_{1},e_{2},e_{3}\}$ by first selecting $e_{1},e_{2}$, then eliminating $c_{1},c_{2},c_{3},d_{1}$ and finally selecting $e_{3}$. This committee does not satisfy rank-PJR+, since either $c_{1},c_{2}$ or $c_{3}$ witness a violation with the first three voters. Indeed, the only committees satisfying rank-PJR+ in this instance are $\{e_{1},e_{2}\}$ together with one of $\{c_{1},c_{2},c_{3},d_{1}\}$. EAR here selects either $\{e_{1},e_{2},c_{1}\}$ or $\{e_{1},e_{2},c_{3}\}$.