# Completing Priceable Committees:
Utilitarian and Representation Guarantees for Proportional Multiwinner Voting

Markus Brill111University of Warwick, UK; email<EMAIL_ADDRESS>Jannik Peters222TU Berlin, Germany; email<EMAIL_ADDRESS>
# Completing Priceable Committees:
Utilitarian and Representation Guarantees for Proportional Multiwinner Voting

Markus Brill111University of Warwick, UK; email<EMAIL_ADDRESS>Jannik Peters222TU Berlin, Germany; email<EMAIL_ADDRESS>
###### Abstract

When selecting committees based on preferences of voters, a variety of
different criteria can be considered. Two natural objectives are maximizing
the utilitarian welfare (the sum of voters’ utilities) and coverage (the
number of represented voters) of the selected committee. Previous work has
studied the impact on utilitarian welfare and coverage when requiring the
committee to satisfy minimal requirements such as justified representation or
weak proportionality. In this paper, we consider the impact of imposing much
more demanding proportionality axioms. We identify a class of voting rules
that achieve strong guarantees on utilitarian welfare and coverage when
combined with appropriate completions. This class is defined via a weakening
of priceability and contains prominent rules such as the Method of Equal
Shares. We show that committees selected by these rules (i) can be completed
to achieve optimal coverage and (ii) can be completed to achieve an
asymptotically optimal approximation to the utilitarian welfare if they
additionally satisfy EJR+. Answering an open question of Elkind et al. (2022),
we use the Greedy Justified Candidate Rule to obtain the best possible
utilitarian guarantee subject to proportionality. We also consider completion
methods suggested in the participatory budgeting literature and other
objectives besides welfare and coverage.

##  1 Introduction

In multiwinner voting, a subset of candidates (often called a committee) needs
to be chosen in a way that reflects the preferences of a set of voters over
these candidates. The (computational) social choice literature has identified
many different, often competing, criteria for committees (Felsenthal and Maoz,
1992; Elkind et al., 2017; Lackner and Skowron, 2022). In particular,
Faliszewski et al. (2017) distinguish between three important desiderata
referred to as individual excellence, diversity, and proportional
representation.

This paper focuses on approval-based multiwinner voting, where voters cast
approval ballots over individual candidates (Lackner and Skowron, 2022). In
this setting, it is commonly assumed that each voter evaluates a committee by
counting the number of approved committee members. This number is often
referred to as the utility that the voter derives from the committee, and a
voter is said to be represented by a committee if their utility is nonzero.
Using these conventions, the first two desiderata of Faliszewski et al. (2017)
have straightforward interpretations: Individual excellence is measured by the
utilitarian welfare of a committee, i.e., the sum over the voters’ utilities.
Utilitarian welfare is maximized when choosing the candidates with the highest
number of approvers, and the voting rule that selects this committee is known
as Approval Voting (AV). The diversity of a committee is captured by its
coverage, i.e., the number of voters that are represented by it. The
(computationally intractable) voting rule that selects committees maximizing
coverage is known as Chamberlin–Courant (CC). The third desideratum,
proportional representation, is much harder to formalize, and the literature
has identified a host of different (axiomatic and quantitative) measures to
assess the proportionality of a committee (Aziz et al., 2017; Sánchez-
Fernández et al., 2017; Skowron, 2021; Peters et al., 2021b; Brill and Peters,
2023); a prominent example is the extended justified representation (EJR)
axiom.

The study of trade-offs between the three desiderata has been initiated by
Lackner and Skowron (2020), who analyzed how closely classic multiwinner rules
such as PAV and Phragmén’s rules approximate the optimal utilitarian welfare
and coverage. The resulting bounds are referred to as utilitarian and
representation guarantees, respectively. Besides guarantees for specific
rules, they also proved upper bounds on the utilitarian and representation
guarantees of rules satisfying minimal proportionality requirements. In their
follow-up work, Elkind et al. (2022) studied which guarantees can be achieved
if the committee is required to satisfy the justified representation (JR)
axiom. While Lackner and Skowron (2020) gave an upper bound of
${2}/{\lfloor\sqrt{k}\rfloor}-{1}/{k}$ for the utilitarian guarantee of any
committee satisfying JR — with a higher guarantee being better — Elkind et al.
(2022) were almost able to close this gap by showing that a utilitarian
guarantee of $\frac{2-\varepsilon}{1+\sqrt{k}}$ is possible for any
$\varepsilon>0$ and sufficiently large $k$.333 Here, $k$ denotes the size of
the committee. Lackner and Skowron (2020) proved the upper bound for an axiom
they call weak proportionality, but — as Elkind et al. (2022) observe — the
bound also holds for JR. Moreover, we note that Elkind et al. (2022) phrase
their bounds in terms of the “price of JR,” with lower prices being better: a
price of $P$ corresponds to a guarantee of $1/P$. Further, they showed that a
representation guarantee of $\frac{3}{4}$ is possible in conjunction with EJR
and that both guarantees can be simultaneously approximated close to optimal
while requiring JR. They achieve the bounds for JR by using a variant of the
sequential Chamberlin–Courant rule, and the bound for EJR is achieved by the
somewhat unnatural GreedyEJR rule. Both of these rules construct committees by
matching committee members to voters approving them (see Section 3 for
details), in a way that is reminiscent of priceability and rules such as the
Method of Equal Shares (MES) (Peters and Skowron, 2020). These rules suffer
from a common drawback: They often select strictly fewer than the desired
number of candidates, and thus require a completion method to output a full
committee.

#### Our Contribution

In this paper, we study which representation and utilitarian guarantees are
possible when requiring much more demanding proportionality axioms than those
considered by Lackner and Skowron (2020) and Elkind et al. (2022). We identify
a class of voting rules that achieve strong guarantees on utilitarian welfare
and coverage when combined with appropriate completion methods. This class,
defined via a weakening of priceability (Peters and Skowron, 2020) we call
affordability, contains prominent voting rules such as MES.

We show that any affordable committee, when completed with the CC rule,
achieves an optimal representation guarantee of $\frac{3}{4}$. This general
result has several advantages over earlier results on representation
guarantees: First, our result implies that any proportionality axiom which is
compatible with affordability, such as EJR+ (Brill and Peters, 2023) or FJR
(Peters et al., 2021b), is also compatible with a representation guarantee of
$\frac{3}{4}$. Second, our result uses much simpler rules: Instead of the
unnatural and computationally intractable GreedyEJR rule, we can use
attractive rules such as MES to achieve this bound.

For utilitarian guarantees, we show that any affordable committee that
additionally satisfies EJR+ (which is more demanding than EJR but still
satisfied by MES), completed with AV, achieves a utilitarian guarantee of
$\Omega(\frac{1}{\sqrt{k}})$. We further show that the recently introduced
Greedy Justified Candidate Rule (GJCR) (Brill and Peters, 2023), completed
with AV, achieves a utilitarian guarantee of exactly
$\frac{2}{\sqrt{k}}-\frac{1}{k}$, which is the best possible guarantee for
proportional rules. This answers an open question by Elkind et al. (2022), who
were only able to obtain this bound asymptotically. Moreover, we establish an
interesting distinction between EJR and EJR+, by showing that GreedyEJR (which
satisfies EJR but not EJR+) does not achieve a utilitarian guarantee of
$\Omega(\frac{1}{k^{c}})$ for any $c<1$, even on instances where it is
exhaustive, i.e., where it selects exactly $k$ candidates. Thus, EJR is not
sufficient for strong utilitarian guarantees.

We also study trade-offs between utilitarian and representation guarantees and
show that one can simultaneously achieve a representation guarantee of
$\frac{3}{4}-o(1)$ and a utilitarian guarantee of
$\frac{2}{\sqrt{k}}-\frac{1}{k}$ together with EJR+, improving and simplifying
a similar result by Elkind et al. (2022) for JR.

Finally, we consider completion methods that are relevant for specific
applications of multiwinner voting: completion by the maximin support method
(Sánchez-Fernández et al., 2021), which is relevant for the security of
blockchain systems (Cevallos and Stewart, 2021), and completion by
perturbation or by varying the budget, which have been discussed in the
participatory budgeting (PB) literature (Rey and Maly, 2023).

#### Related Work

Besides the papers by Lackner and Skowron (2022) and Elkind et al. (2022),
utilitarian and representation guarantees have been studied in the context of
PB by Fairstein et al. (2022), who proved some guarantees, but mostly
impossibility results. The topic of completing non-exhaustive voting rules is
especially relevant in PB, where various ways to complete the Method of Equal
Shares have been discussed and analyzed on real-world data (Peters et al.,
2021b; Faliszewski et al., 2023; Boehmer et al., 2023). One of the completion
methods we study in this paper, “completion by varying the budget,” was
recently used in a real-world PB election in the Polish city of Wielizka (see
https://equalshares.net for details).

In a similar spirit as the paper by Elkind et al. (2022), Michorzewski et al.
(2020) and Tang et al. (2020) studied the “price of fairness” in the setting
of budget division (or probabilistic social choice).

##  2 Preliminaries

We are given a finite set $C=\\{c_{1},\dots,c_{m}\\}$ of $m>0$ _candidates_
and a finite set $N=\\{1,\dots,n\\}$ of $n>0$ _voters_. Voters cast _approval
ballots_ over candidates: for each voter $i\in N$, the set $A_{i}\subseteq C$
consists of the candidates that are approved by voter $i$. Together
$A=(A_{i})_{i\in N}$ forms an _approval profile_. For a candidate $c\in C$, we
call the members of the set $N_{c}=\\{i\in N\colon c\in A_{i}\\}$ the
_approvers_ of $c$. Further, we are given a committee size $k\leq m$. We call
any set $W\subseteq C$ of size $\lvert W\rvert\leq k$ a _committee_. If
$\lvert W\rvert=k$, we say that $W$ is _exhaustive_. Finally, we call
$\mathcal{I}=(A,C,k)$ an _instance_.

A _(multiwinner voting) rule_ $r$ is a function mapping instances
$\mathcal{I}=(A,C,k)$ to non-empty sets of committees $r(\mathcal{I})$. We
often say that a rule “satisfies” a property if, for each instance
$\mathcal{I}$, all committees in $r(\mathcal{I})$ satisfy the property.

#### Proportionality Axioms

First, we consider the classical justified representation axioms of Aziz et
al. (2017). For an integer $\ell\in\mathbb{N}$, a group $N^{\prime}\subseteq
N$ of voters is said to be _$\ell$ -large_ if $\lvert
N^{\prime}\rvert\geq\ell\frac{n}{k}$ and _$\ell$ -cohesive_ if
$\left\lvert\bigcap_{i\in N^{\prime}}A_{i}\right\rvert\geq\ell$. The
_justified representation (JR)_ axiom requires that for any $1$-large and
$1$-cohesive group $N^{\prime}$, there exists some $i\in N^{\prime}$ with
$\lvert A_{i}\cap W\rvert\geq 1$. _Extended Justified Representation (EJR)_
requires that for all $\ell\in[k]$ and for any $\ell$-large and
$\ell$-cohesive group $N^{\prime}$ there exists some $i\in N^{\prime}$ with
$\lvert A_{i}\cap W\rvert\geq\ell$. Finally, the recently introduced _EJR+_
axiom requires that for any $\ell$-large and $1$-cohesive group $N^{\prime}$,
there either exists some $i\in N^{\prime}$ with $\lvert A_{i}\cap
W\rvert\geq\ell$ or it holds that $\bigcap_{i\in N^{\prime}}A_{i}\subseteq W$,
for all $\ell\in[k]$. It is easy to see that EJR+ implies EJR which in turn
implies JR. We also use the following quantitative notion (Brill and Peters,
2023).

$1$$2$$3$$4$$5$$6$$7$$8$$9$$10$$11$$12$$13$$14$$15$$16$$17$$18$$19$$20$$21$$22$$23$$24$$c_{1}$$c_{2}$$c_{3}$$c_{4}$$c_{5},c_{6}$$c_{7},c_{8}$$c_{9}$$c_{10}$$c_{11}-c_{22}$

Figure 1: Instance with $n=24$ voters and $m=22$ candidates considered in
Example 1. Voters correspond to integers and approve candidates placed above
them, e.g., voter $1$ approves candidate $c_{1}$ and voter $9$ approves
candidates $c_{5},c_{6},c_{7},c_{8},c_{9}$.

######  Definition 1.

Given a committee $W$, a candidate $c\in C\setminus W$ is _$(t,\ell)$
-represented_ if there is no $\ell$-large group $N^{\prime}\subseteq N_{c}$
with $\frac{1}{\lvert N^{\prime}\rvert}\sum_{i\in N^{\prime}}\lvert A_{i}\cap
W\rvert<t$. For a given function $f\colon\\!\mathbb{N}\\!\to\\!\mathbb{R}$, a
committee is _$f$ -representative_ if every unchosen candidate $c\in
C\setminus W$ is $(f(\ell),\ell)$-represented for any $\ell\in[k]$.

This is a stronger notion than the proportionality degree (Skowron, 2021), in
the sense that an $f$-representative committee (or rule) also has a
proportionality degree of $f$, as the definition just removes the cohesiveness
requirement inherent to the proportionality degree. The representativeness of
a committee is polynomial-time computable, and as we show later, contrary to
the proportionality degree, it allows us to obtain bounds on the utilitarian
guarantee of a voting rule.

#### Rules

Given an instance $\mathcal{I}=(A,C,k)$ and a committee $W\subseteq C$, we let
$\operatorname{\textsf{uw}}(W)=\sum_{i\in N}\lvert A_{i}\cap W\rvert$ denote
the _utilitarian welfare_ of $W$ and
$\operatorname{\textsf{cov}}(W)=\lvert\\{i\in N\colon A_{i}\cap
W\neq\emptyset\\}\rvert$ the _coverage_ of $W$. The _Approval Voting (AV)_
rule selects a committee of size $k$ maximizing the utilitarian welfare. The
_Chamberlin–Courant (CC)_ rule selects a committee of size $k$ maximizing the
coverage. The _sequential Chamberlin–Courant (seq-CC)_ rule starts with an
empty committee $W=\emptyset$ and greedily adds candidates $c\notin W$
maximizing $\operatorname{\textsf{cov}}(W\cup\\{c\\})$ until $W$ has size $k$.

Next, we define three rules we study throughout the paper. The _Method of
Equal Shares_ (MES) (Peters and Skowron, 2020) starts with an empty committee
$W=\emptyset$ and with a budget $b_{i}=\frac{k}{n}$ for each voter $i\in N$.
Then, for each unselected candidate $c\notin W$, it calculates the value
$\rho$ such that $\sum_{i\in N_{c}}\min(b_{i},\rho)=1$. If such a $\rho$ does
not exist for any unselected candidate, MES terminates. Otherwise, it selects
the candidate $c$ with the minimum $\rho$, adds it to $W$, and sets
$b_{i}=b_{i}-\min(b_{i},\rho)$ for each $i\in N_{c}$.

The _Greedy Justified Candidate Rule_ (GJCR) (Brill and Peters, 2023) also
starts with an empty committee $W=\emptyset$. GJCR then repeatedly checks if
there is a candidate $c$, set $N^{\prime}\subseteq N_{c}$, and $\ell\in[k]$
with $\lvert N^{\prime}\rvert\geq\frac{\ell n}{k}$ and $\lvert A_{i}\cap
W\rvert<\ell$ for all $i\in N^{\prime}$. If there is such a candidate, it
picks the candidate maximizing $\lvert N^{\prime}\rvert$ and adds it to $W$,
otherwise it terminates.

The _GreedyEJR_ rule (Bredereck et al., 2019; Peters et al., 2021b) works
similarly to GJCR, but iterates over voter groups rather than candidates
(which makes the rule computationally intractable). Starting with an empty
committee $W$, GreedyEJR finds the largest $\ell$ such that there is an
$\ell$-cohesive and $\ell$-large group $N^{\prime}$, adds $\ell$ candidates
from $\bigcap_{i\in N^{\prime}}A_{i}$ to $W$, and deletes all voters in
$N^{\prime}$; this is repeated until no further group can be found.

MES and GJCR satisfy EJR+ (Brill and Peters, 2023), whereas GreedyEJR
satisfies EJR but not EJR+. All three rules may return non-exhaustive
committees (Example 1).

#### Utilitarian and Representation Guarantees

For a given instance $\mathcal{I}$, we define the utilitarian ratio of a
committee $W$ as the fraction of the highest achievable utilitarian welfare in
this instance, i.e.,
$\frac{\operatorname{\textsf{uw}}(W)}{\operatorname{\textsf{uw}}(AV(\mathcal{I}))}$.
Analogously,
$\frac{\operatorname{\textsf{cov}}(W)}{\operatorname{\textsf{cov}}(CC(\mathcal{I}))}$
is called the representation ratio of $W$.

A utilitarian or representation _guarantee_ is a lower bound on the
utilitarian or representation ratio of a committee or a set of committees
(such as those output by a rule).

#### Completion Methods

For a non-exhaustive committee $W$, we let $\overline{AV}(W)$ denote the
completion of $W$ with the highest approval score. Formally,
$\overline{AV}(W)=W\cup AV(\mathcal{I^{\prime}})$, where
$\mathcal{I^{\prime}}=(A,C\setminus W,k-|W|)$. Further, $\overline{CC}(W)$ is
the completion of $W$ with the highest coverage. Formally,
$\overline{CC}(W)=W\cup CC(\mathcal{I^{\prime\prime}})$, where
$\mathcal{I^{\prime\prime}}=(A^{\prime},C\setminus W,k-|W|)$ and $A^{\prime}$
results from $A$ by deleting all voters represented by $W$. Completion via
seq-CC is defined analogously.

######  Example 1.

Consider the instance depicted in Figure 1 with $n=24,k=12$, and $22$
candidates. In this instance, AV selects the candidates
$\\{c_{11},\dots,c_{22}\\}$ to achieve a utilitarian welfare of $12\cdot
8=96$. This committee, however, does not satisfy EJR (or even JR), as for
instance voters $5$ to $10$ together with candidate $c_{9}$ witness a
violation of JR (these voters deserve $6\frac{k}{n}=3$ seats on the
committee). The optimal coverage is $n=24$ and can be achieved, e.g., by
$\\{c_{1},\dots,c_{12}\\}$.

MES begins by assigning everyone a budget of $\frac{1}{2}$. Four candidates
out of $c_{11}$ to $c_{22}$ would be bought first, with a $\rho$ of
$\frac{1}{8}$ each. Then, $c_{5},c_{6},c_{7}$ can be bought with
$\rho=\frac{1}{7}$ each. The approvers of $c_{8}$ would then have a budget of
$4(\frac{1}{2}-\frac{3}{7})+3(\frac{1}{2}-\frac{2}{7})=\frac{13}{14}<1$, which
is not enough to buy $c_{8}$. Both the approvers of $c_{9}$ and of $c_{10}$,
on the other hand, have enough budget left to buy their candidate. The
approvers of any of $c_{1}$ to $c_{4}$ have a budget of $\frac{1}{2}$ each and
therefore, can not buy the candidate they approve. Hence, MES would (up to
tie-breaking) return the committee
$W=\\{c_{5},c_{6},c_{7},c_{9},\dots,c_{14}\\}$ with a utilitarian welfare of
$2\cdot 1+3\cdot 2+3\cdot 3+12\cdot 4=65$ and a utilitarian ratio of
$\frac{65}{96}$. Since it covers all but $4$ voters, its representation ratio
is $\frac{20}{24}=\frac{5}{6}$. The completion $\overline{CC}(W)$ additionally
contains three of $c_{1},c_{2},c_{3}$, leading to a representation ratio of
$\frac{23}{24}$ and a utilitarian ratio of $\frac{68}{96}$, while the
completion $\overline{AV}(W)$ would contain three of $c_{14}$ to $c_{22}$,
leading to a utilitarian ratio of $\frac{86}{96}$ and an (unchanged)
representation ratio of $\frac{5}{6}$.

GJCR could select $\\{c_{5},c_{6},c_{7},c_{10},c_{11},c_{12},c_{13},c_{14}\\}$
(notably leaving out $c_{9}$, but still selecting $c_{10}$ since the voters
$13$ to $16$ deserve two seats in the committee). Thus, GJCR completed with CC
selects $c_{1},\dots,c_{4}$, leading to a perfect representation ratio of $1$,
while GJCR completed with AV selects four out of $c_{15}$ to $c_{22}$,
reaching a utilitarian ratio of $\frac{91}{96}$.

GreedyEJR could select $\\{c_{5},c_{6},c_{10},c_{11},c_{12},c_{13},c_{14}\\}$
by first considering the $4$-cohesive group $17$ to $24$, then the
$2$-cohesive group $6$ to $12$ with candidates $c_{5}$ and $c_{6}$, and
finally the $1$-cohesive group $13$ to $16$ with candidate $c_{10}$. Notably,
this committee violates EJR+ since the approvers of $c_{9}$ would deserve $3$
seats, but get at most $2$. Since they do not form a cohesive group, they
could not get selected by GreedyEJR and therefore GreedyEJR does not satisfy
EJR+.

##  3 Affordable Committees

The three rules that play an important role in this paper are the Method of
Equal Shares, the Greedy Justified Candidate Rule, and GreedyEJR. A common
feature of these three rules is that they — explicitly or implicitly —
construct (fractional) matchings between committee members and their
approvers: each voter starts off with a “voting weight” of $k/n$ (so that the
total voting weight per committee member is $1$), and each time a candidate is
added to the committee under one of these rules, there is $1$ unit of
(previously unused) voting weight supporting this candidate, which then gets
used up by the candidate.

This is reminiscent of the notion of priceability (Peters and Skowron, 2020),
which assumes that each voter owns an equal amount of “money” that can be
spent on candidates they approve. A committee is called priceable if it is
possible to allocate the money in such a way that each committee member is
paid for and there is not enough leftover money to pay for the inclusion of
further candidates.444Priceability has been studied in various forms (Peters
et al., 2021a; Munagala et al., 2022; Brill et al., 2023; Lackner and Maly,
2023; Brill and Peters, 2023; Kraiczy and Elkind, 2023).

To formalize this, consider an instance $\mathcal{I}=(A,C,k)$. A payment
system is a collection $(p_{i})_{i\in N}$ containing a function $p_{i}\colon
C\to\mathbb{R}_{\geq 0}$ for each voter $i\in N$. A committee $W\subseteq C$
is said to be _priceable_ if there exists a payment system $(p_{i})_{i\in N}$
satisfying the following constraints:

  * C1

$p_{i}(c)=0$ if $c\notin A_{i}$ for all $c\in C$ and $i\in N$

  * C2

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

  * C3

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

  * C4

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

  * C5

$\sum_{i\in N_{c}}\left(\frac{k}{n}-\sum_{c\in C}p_{i}(c)\right)\leq 1$ for
all $c\notin W$.

Note that the left-hand side of constraint C5 exactly corresponds to the money
leftover with approvers of candidate $c$.

MES is probably the most prominent example of a priceable rule (i.e., a rule
that always outputs priceable committees). GJCR and GreedyEJR, on the other
hand, do not necessarily output priceable committees as they might violate C5
(while still satisfying C1–C4). As it turns out, constraints C1–C4 are
sufficient to prove strong guarantees. We call such committees affordable.

######  Definition 2.

A committee $W\subseteq C$ is _affordable_ if there is a payment system for
$W$ satisfying constraints C1–C4.

Clearly, every priceable committee is affordable. Affordability is a rather
weak requirement: it simply requires that each committee member can be
associated with a sufficient amount of voter support. Every subcommittee of an
affordable committee is affordable, and so is the empty committee.

Affordability (and thus priceability) is not generally compatible with
exhaustiveness. For example, consider an instance with two voters and two
candidates such that each candidate is approved by exactly one voter, and let
$k=1$.

GJCR and GreedyEJR output affordable committees. Another example of a rule
ensuring affordability is the variant of sequential CC employed by Elkind et
al. (2022). In light of the positive results on affordable committees in
Section 4, it is perhaps not surprising that both rules used by Elkind et al.
(2022) satisfy this notion. However, as we will show, affordable rules beyond
those considered by Elkind et al. (2022) can be used to obtain strictly
stronger guarantees.

Rules returning priceable or affordable committees are among the most popular
rules studied in the approval-based committee voting literature, as they are
able to achieve strong proportionality guarantees with often quite simple
(greedy) approaches. However, since priceable rules cannot be exhaustive, they
require a completion step. The effects of this completion step are largely
unexplored. By providing utilitarian and representation guarantees for the
completions of affordable committees, our work contributes to the ongoing
discussion on how to make priceable rules exhaustive.555There is variant of
priceability that replaces $k$ in C2 and C5 with an arbitrary budget $B>0$.
This weakening of priceability is compatible with exhaustiveness. Examples of
exhaustive rules satisfying this property include Phragmén’s sequential rule
(Phragmén, 1895), leximax-Phragmén (Brill et al., 2017), the Maximin Support
Method (Sánchez-Fernández et al., 2021), and Phragmms (Cevallos and Stewart,
2021). Since these rules do not necessarily output affordable committees, our
results in Section 4 do not apply to them. This explains why, e.g., the
representation guarantee of Phragmén’s sequential rule is only $\frac{1}{2}$
(Lackner and Skowron, 2020), whereas $\frac{3}{4}$ is possible by completing
affordable committees. In Appendix A, we prove that every exhaustive rule
satisfying this variant of priceability has a representation guarantee of
exactly $\frac{1}{2}$.

We begin our analysis of affordable committees with the following simple
observation, which was already implicit in the work of Elkind et al. (2022,
Theorem 3.6) and Peters et al. (2021b, Lemma 1).

######  Observation 1.

Let $W\subseteq C$ be an affordable committee. Then the coverage of $W$ is at
least $\frac{\lvert W\rvert}{k}n$.

###### Proof.

If the coverage of $W$ was less than $\frac{\lvert W\rvert}{k}n$, then there
must exist a represented voter who pays more than $\frac{\lvert
W\rvert}{\frac{\lvert W\rvert}{k}n}=\frac{k}{n}$, and thus $W$ could not have
been affordable. ∎

In particular, this implies that an exhaustive affordable committee covers all
voters and thus has a coverage of $n$. We can also show that any exhaustive
affordable committee has a utilitarian guarantee of $\Omega(\frac{1}{k})$.

######  Observation 2.

Let $W$ be an exhaustive affordable committee. Then $W$ has a representation
guarantee of $1$ and a utilitarian guarantee of at least $\frac{1}{k}$.

###### Proof.

The representation guarantee immediately follows from 1. For the utilitarian
guarantee, we observe that each candidate in $W$ must have at least
$\frac{n}{k}$ approvals, while each candidate outside $W$ can have at most
$n$, hence the utilitarian ratio is at least $\frac{n}{nk}=\frac{1}{k}$. ∎

While the representation guarantee is optimal, the utilitarian guarantee is
far from: Lackner and Skowron (2020) have shown that proportional rules can
achieve a utilitarian guarantee of $\Theta(\frac{1}{\sqrt{k}})$. In Section
4.1, we extend 2 and show that any $f$-representative — with
$f\in\Omega(\ell)$— affordable committee containing at least a constant
fraction of candidates has a utilitarian guarantee of
$\Omega(\frac{1}{\sqrt{k}})$. In particular, this will imply that both MES and
GJCR have a utilitarian guarantee of $\Omega(\frac{1}{\sqrt{k}})$ when
completed with AV.666Since MES and GJCR have been proposed relatively recently
(and they are not exhaustive), these rules have not been considered in the
paper by Lackner and Skowron (2020).

##  4 Utilitarian and Representation Guarantees

We show that optimal utilitarian and representation guarantees can be achieved
via completing affordable committees.

###  4.1 Utilitarian Guarantees

We begin with a general statement, lower bounding the utilitarian ratio of a
committee based on the highest number of approvals of any unselected
candidate.

For a given committee $W$, let $\operatorname{\overline{s}}(W)=\max_{c\notin
W}\lvert N_{c}\rvert$ denote the largest approval score of an unselected
candidate.

######  Lemma 3.

Let $f\colon\mathbb{N}\to\mathbb{R}$ and let $W$ be an $f$-representative
committee with $\operatorname{\overline{s}}(W)\geq t\frac{n}{k}$ for some
$t\in\mathbb{N}$. Then, $W$ has a utilitarian guarantee of
$\min\left(\frac{1}{2},\frac{f(t)}{2k}\right)$.

###### Proof.

Let $W^{*}$ be the committee chosen by AV and let $c\notin W$ such that
$\lvert N_{c}\rvert\geq t\frac{n}{k}$. Since $W$ is $f$-representative, we
know that $\sum_{i\in N_{c}}\lvert A_{i}\cap W\rvert\geq f(t)\lvert
N_{c}\rvert$. This gives us a lower bound on the utilitarian welfare of $W$:

$\displaystyle\operatorname{\textsf{uw}}(W)\geq\max(\operatorname{\textsf{uw}}(W\cap
W^{*}),\sum_{i\in N_{c}}\lvert A_{i}\cap
W\rvert)\geq\frac{\operatorname{\textsf{uw}}(W\cap W^{*})+f(t)\lvert
N_{c}\rvert}{2}.$

Further, since
$\operatorname{\textsf{uw}}(AV)\leq\operatorname{\textsf{uw}}(W\cap
W^{*})+k\lvert N_{c}\rvert$, we get

$\displaystyle\frac{\operatorname{\textsf{uw}}(W)}{\operatorname{\textsf{uw}}(AV)}\geq\frac{\operatorname{\textsf{uw}}(W\cap
W^{*})+f(t)\lvert N_{c}\rvert}{2(\operatorname{\textsf{uw}}(W\cap
W^{*})+k\lvert N_{c}\rvert)}\geq\min\left(\frac{1}{2},\frac{f(t)}{2k}\right).$

∎

Hence, if there is an unselected candidate with $\omega(\frac{n}{\sqrt{k}})$
approvals left and our committee is $\Theta(\ell)$-representative, we have a
utilitarian guarantee of $\omega(\frac{1}{\sqrt{k}})$.

For affordable committees, we can also show that a similar bound can be
obtained for the case $\operatorname{\overline{s}}(W)\in
o(\frac{n}{\sqrt{k}})$ (independently of $W$ being $f$-representative).

######  Lemma 4.

Let $W$ be an affordable committee with $\operatorname{\overline{s}}(W)\leq
t\frac{n}{k}$. Then, $W$ has a utilitarian guarantee of
$\min\left(\frac{1}{2},\frac{\lvert W\rvert}{2tk}\right)$.

###### Proof.

We again let $W^{*}$ denote the committee chosen by AV. We know that the
utilitarian welfare of $W^{*}$ is at most $\operatorname{\textsf{uw}}(W\cap
W^{*})+k\operatorname{\overline{s}}(W)$. On the other hand, the utilitarian
welfare of $W$ is at least $\max(\operatorname{\textsf{uw}}(W\cap
W^{*}),\lvert W\rvert\frac{n}{k})$, since every candidate in $W$ has at least
$\frac{n}{k}$ approvals. Therefore, the utilitarian guarantee of $W$ is at
least

$\displaystyle\frac{\max(\operatorname{\textsf{uw}}(W\cap W^{*}),\lvert
W\rvert\frac{n}{k})}{\operatorname{\textsf{uw}}(W\cap
W^{*})+nt}\geq\frac{\operatorname{\textsf{uw}}(W\cap W^{*})+\lvert
W\rvert\frac{n}{k}}{2(\operatorname{\textsf{uw}}(W\cap
W^{*})+nt)}\geq\min\left(\frac{1}{2},\frac{\lvert W\rvert}{2tk}\right)$

∎

Thus, in this case, we also obtain a bound better than
$\Omega(\frac{1}{\sqrt{k}})$ in case $\operatorname{\overline{s}}(W)\in
o(\frac{n}{\sqrt{k}})$ and $\frac{\lvert W\rvert}{k}\in\Omega(1)$. Piecing
these two lemmas together, we obtain a bound for both cases.

######  Theorem 5.

Any affordable and $f$-representative committee $W$ has a utilitarian
guarantee of $\frac{\min\left({\lvert
W\rvert}/{\sqrt{k}},f(\sqrt{k})\right)}{2k}$.

###### Proof.

The utilitarian guarantee follows from Lemmas 3 and 4, depending on whether
$\operatorname{\overline{s}}(W)$ is at least or at most
$\sqrt{k}\;\frac{n}{k}$. ∎

As a consequence, since any committee satisfying EJR+ is
$\frac{\ell-1}{2}$-representative (Brill and Peters, 2023), MES and GJCR both
have a utilitarian guarantee of $\Omega(\frac{1}{\sqrt{k}})$ in case they
select at least a constant fraction of candidates. The same proof idea applies
to completions of non-exhaustive committees.

######  Corollary 6.

Let $f\in\Omega(\ell)$ and $W$ be an affordable and $f$-representative
committee. Then $\overline{AV}(W)$ has a utilitarian guarantee of
$\Omega(\frac{1}{\sqrt{k}})$.

###### Proof.

If $\lvert W\rvert\geq k-\sqrt{k}$, we get the bound of
$\Omega(\frac{1}{\sqrt{k}})$ from Theorem 5. Otherwise, $\overline{AV}(W)$
would select at least the top $\sqrt{k}$ candidates with the highest approval
score and therefore achieve a utilitarian guarantee of $\frac{1}{\sqrt{k}}$. ∎

For committees satisfying EJR+, we give a precise bound.

######  Corollary 7.

Let $W$ be an affordable committee that satisfies EJR+. Then,
$\overline{AV}(W)$ has a utilitarian guarantee of
$\frac{1}{4\sqrt{k}}-\frac{1}{2k}$.

###### Proof.

If $\lvert W\rvert\geq\frac{3}{4}k$ we can apply Lemma 4 and Lemma 3 and get a
guarantee of $\frac{\sqrt{k}-2}{4k}=\frac{1}{4\sqrt{k}}-\frac{1}{2k}$, since
every EJR+ committee is $\frac{\ell-1}{2}$-representative. If, on the other
hand, $\lvert W\rvert\leq\frac{3}{4}k$ we would select at least the
$\frac{1}{4}k-1$ candidates with the highest approval score and thus achieve a
utilitarian guarantee of $\frac{1}{4}-\frac{1}{k}$. ∎

Interestingly, these strong guarantees for affordable EJR+ committees do not
hold for EJR.

######  Theorem 8.

For any $0<c<1$, there are exhaustive affordable committees satisfying EJR
with a utilitarian ratio of $\mathcal{O}(\frac{1}{k^{1-c}})$.

###### Proof.

For simplicity, we assume that $k$ is even, that $k^{c}$ and $k^{1-c}$ are
integers, and that $k$ is sufficiently large.

We create an instance with $2k$ candidates $C=C_{1}\cup C_{2}$, with both
$C_{1}$ and $C_{2}$ being of size $k$. For each subset $C^{\prime}\subseteq
C_{1}$ of size exactly $|C^{\prime}|=\frac{k}{2}$, we add a voter approving
all candidates in $C^{\prime}$. Thus, the number of voters is

$n={k\choose\frac{k}{2}}=\frac{k!}{(\frac{k}{2})!(k-\frac{k}{2})!}.$

Further, we arbitrarily partition the voters, and the candidates in $C_{2}$,
into $k^{1-c}$ equal-size groups, with the $\frac{n}{k^{1-c}}$ voters in one
group approving exactly the $k^{c}$ candidates approved by no other group.

We show that this instance does not contain an $\ell$-large and
$\ell$-cohesive group for any $\ell$ larger than $k^{c}$. Let
$C^{\prime}\subseteq C$ be a subset of candidates of size larger than $k^{c}$.
If $C^{\prime}\cap C_{2}\neq\emptyset$, we know that there are at most
$\frac{n}{k^{1-c}}$ voters approving $C^{\prime}\cap C_{2}$ and thus the group
is not large enough to be more than $k^{c}$-large. Thus, we know that
$C^{\prime}\subseteq C_{1}$. There are at most

$\displaystyle{(k-\lvert C^{\prime}\rvert)\choose(\frac{k}{2}-\lvert
C^{\prime}\rvert)}<{(k-k^{c})\choose(\frac{k}{2}-k^{c})}=\frac{(k-k^{c})!}{(\frac{k}{2}-k^{c})!(k-\frac{k}{2})!}$

voters approving all of $C^{\prime}$. By definition of the binomial
coefficient, we get that the fraction of voters approving all of $C^{\prime}$
is at most

$\displaystyle\frac{{(k-k^{c})\choose(\frac{k}{2}-k^{c})}}{{k\choose\frac{k}{2}}}=\frac{(k-k^{c})!\frac{k}{2}!}{(\frac{k}{2}-k^{c})!k!}=\frac{\prod_{i=\frac{k}{2}-k^{c}+1}^{k-k^{c}}i}{\prod_{i=\frac{k}{2}+1}^{k}i}=\frac{\prod_{i=\frac{k}{2}-k^{c}+1}^{\frac{k}{2}}i}{\prod_{i=k-k^{c}+1}^{k}i}\leq\left(\frac{(\frac{k}{2})}{k-k^{c}}\right)^{k^{c}}.$

Since $k$ is sufficiently large, we can assume that this is smaller than
$\frac{k^{c}}{k}$ and, thus, no $k^{c}$-cohesive group exists. Hence, we can
take the other $k$ candidates in $C_{2}$ and get a committee which is
affordable and satisfies EJR. However, their utilitarian welfare is only
$nk^{c}$ while the utilitarian welfare of the other $k$ candidates is
$n\frac{k}{2}$. Thus, no utilitarian ratio better than $O(\frac{1}{k^{1-c}})$
is possible for all affordable committees satisfying EJR. ∎

We point out that the committee witnessing the utilitarian ratio of
$\mathcal{O}(\frac{1}{k^{1-c}})$ can be selected by the GreedyEJR rule, since
no cohesive groups with an $\ell$ larger than $k^{c}$ exists. Thus, the
GreedyEJR rule, even when it is exhaustive (and thus cannot be completed any
further), can select committees with a very suboptimal utilitarian ratio.

We now show that a utilitarian guarantee of $\frac{2}{\sqrt{k}}-\frac{1}{k}$
can be achieved via completing the Greedy Justified Candidate Rule with AV,
thus meeting the lower bound proven by Lackner and Skowron (2020) and
answering an open question by Elkind et al. (2022). For our proof, we use that
GJCR behaves very similarly to AV at the beginning of its iterations, picking
the candidates with the highest approval score, until one of them would not be
“proportional” anymore.

######  Theorem 9.

The Greedy Justified Candidate Rule completed with AV has a utilitarian
guarantee of $\frac{2}{\sqrt{k}}-\frac{1}{k}$.

###### Proof.

Fix an instance and let $W$ be the committee output by GJCR. Let
$c_{1},\dots,c_{k}$ be the candidates selected by AV in order of their
approval scores. Further, let $c_{i+1}$ be the first among them which was not
selected by $\overline{AV}(W)$. Without loss of generality, we assume that all
other candidates selected by $\overline{AV}(W)$ with the same approval score
as $c_{i+1}$ come before it. Let $\alpha>0$ such that $\lvert
N_{c_{i+1}}\rvert=\alpha\frac{n}{k}$. We distinguish two cases. If $\alpha<1$,
we have $\lvert N_{c_{i+1}}\rvert<\frac{n}{k}$. Thus, $c_{i+1}$ could not have
been selected by GJCR, since all candidates selected by it have an approval
score of at least $\frac{n}{k}$. Hence, $\overline{AV}(W)$ and AV select
candidates with the same approval scores, and therefore the utilitarian
guarantee is $1$.

For the case of $\alpha\geq 1$, we first want to show that
$i\geq\lceil\alpha\rceil$. Since the candidate $c_{i+1}$ was not selected, we
know that there is at least one voter $j\in N_{c_{i+1}}$ with $\lvert
A_{j}\cap W\rvert\geq\lfloor\alpha\rfloor$ such that the candidates selected
for $j$ (meaning that $j\in N^{\prime}$ when this candidate was chosen by
GJCR) must have at least as many approvals as $c_{i+1}$. Therefore,
$i\geq\lfloor\alpha\rfloor$ immediately holds (and thus also
$i\geq\lceil\alpha\rceil$ if $\alpha\in\mathbb{N}$ or if there are at least
$\lceil\alpha\rceil$ candidates selected for $j$). If $\alpha\notin\mathbb{N}$
and if there are less than $\lceil\alpha\rceil$ selected for $j$, we know that
in the payment system constructed by GJCR, the budget of $j$ and thus also the
entire budget cannot be fully spent, since the voter pays at most
$\frac{\lfloor\alpha\rfloor k}{\alpha n}<\frac{k}{n}$. Therefore, the approval
voting step selects at least one candidate, which must have at least an
approval score of $\alpha\frac{n}{k}$. Hence, in this case,
$i\geq\lfloor\alpha\rfloor+1=\lceil\alpha\rceil$. Finally, we know that the
other $k-i$ candidates selected by GJCR must have at least $\frac{n}{k}$
approvals since they were selected by GJCR, while we know that the candidates
selected by AV afterwards must have an approval score of at most
$\alpha\frac{n}{k}$.

We can therefore lower-bound the utilitarian guarantee as

$\displaystyle\frac{\operatorname{\textsf{uw}}(\overline{AV}(W)))}{\operatorname{\textsf{uw}}(AV)}\geq\frac{\operatorname{\textsf{uw}}(\\{c_{1},\dots,c_{i})\\}+(k-i)\frac{n}{k}}{\operatorname{\textsf{uw}}(\\{c_{1},\dots,c_{i}\\})+(k-i)\alpha\frac{n}{k}}\geq\frac{i\alpha\frac{n}{k}+(k-i)\frac{n}{k}}{i\alpha\frac{n}{k}+(k-i)\alpha\frac{n}{k}}$
$\displaystyle=\frac{\alpha i+(k-i)}{\alpha i+(k-i)\alpha}=\frac{\alpha
i+(k-i)}{k\alpha}=\frac{(\alpha-1)i+k}{k\alpha}\geq\frac{(\alpha-1)\alpha+k}{k\alpha}=\frac{\alpha^{2}+k}{k\alpha}-\frac{1}{k}.$

By the AM-GM inequality we know that $(\alpha^{2}+k)/2\geq\alpha\sqrt{k}$ and
thus we obtain a utilitarian guarantee of $\frac{2}{\sqrt{k}}-\frac{1}{k}$. ∎

In the same vein, we can obtain a very similar bound for MES completed by AV.

######  Theorem 10.

The Method of Equal Shares completed by AV has a utilitarian guarantee of
$\frac{2}{\sqrt{k}}-\frac{2}{k}$.

###### Proof.

The proof is very similar to the one for GJCR. However, for MES we can only
claim that $i\geq\lfloor\alpha\rfloor$. Any candidate who has less approvals
than $\alpha\frac{n}{k}$ could only be bought with a $\rho$ of larger than
$\frac{k}{n\alpha}$ while any candidate in $c_{1},\dots,c_{i}$ could be bought
with a $\rho$ of at most $\frac{k}{n\alpha}$. Since $c_{i+1}$ was not selected
for a $\rho$ of $\frac{k}{n\alpha}$, we know that there must be an approver of
$c_{i+1}$ with a budget of less than $\frac{k}{n\alpha}$. Since this approver
paid at most $\frac{k}{n\alpha}$ for each previous candidate, we get that this
voter must approve at least $\lfloor\alpha\rfloor$ candidates with an approval
score of at least $\frac{\alpha n}{k}$.

The rest follows analogously, and we can give the utilitarian guarantee as

$\displaystyle\frac{\operatorname{\textsf{uw}}(\overline{AV}(W)))}{\operatorname{\textsf{uw}}(AV)}\geq\frac{\operatorname{\textsf{uw}}(\\{c_{1},\dots,c_{i}\\})+(k-i)\frac{n}{k}}{\operatorname{\textsf{uw}}(\\{c_{1},\dots,c_{i}\\})+(k-i)\alpha\frac{n}{k}}\geq\frac{i\alpha\frac{n}{k}+(k-i)\frac{n}{k}}{i\alpha\frac{n}{k}+(k-i)\alpha\frac{n}{k}}$
$\displaystyle=\frac{(\alpha-1)i+k}{k\alpha}\geq\frac{(\alpha-1)\lfloor\alpha\rfloor+k}{k\alpha}\geq\frac{(\alpha-1)^{2}+k}{k\alpha}\geq\frac{\alpha^{2}+k}{k\alpha}-\frac{2}{k}.$

Hence, we can again apply the AM-GM inequality and obtain a utilitarian
guarantee of $\frac{2}{\sqrt{k}}-\frac{2}{k}$. ∎

###  4.2 Representation Guarantees

We begin the analysis of representation guarantees with a simple lemma:
Generalizing the proof of Theorem 3.6 by Elkind et al. (2022) gives us a
general bound on the representation guarantee of $\overline{CC}(W)$.

######  Lemma 11.

Let $W$ be a committee with a representation ratio of $\rho$. Then,
$\overline{CC}(W)$ has a representation guarantee of
$\rho+(1-\rho)(\frac{k-\lvert W\rvert}{k})$.

###### Proof.

Let $n^{\prime}$ be the number of voters covered by the optimal CC committee.
Since $W$ has a representation ratio of $\rho$ there are at least
$(1-\rho)n^{\prime}$ of these voters uncovered. Since at least
$(1-\rho)n^{\prime}$ uncovered voters can be covered using $k$ candidates,
using $k-\lvert W\rvert$ candidates we can cover at least
$\left(\frac{k-\lvert W\rvert}{k}\right)(1-\rho)n^{\prime}$. The
representation guarantee thus follows. ∎

This allows us to derive the same representation guarantee as Elkind et al.
(2022), but for any affordable committee completed with CC.

######  Corollary 12.

Let $W$ be an affordable committee. Then $\overline{CC}(W)$ has a
representation guarantee of $\frac{3}{4}$.

###### Proof.

Let $\rho$ be the representation ratio of $W$. By 1, we know that
$\rho\geq\frac{\lvert W\rvert}{k}$. Using Lemma 11, we get that the
representation guarantee is at least

$\displaystyle\rho+(1-\rho)\left(\frac{k-\lvert
W\rvert}{k}\right)=\left(1-\frac{\lvert W\rvert}{k}\right)+\rho\frac{\lvert
W\rvert}{k}\geq\left(1-\frac{\lvert W\rvert}{k}\right)+\left(\frac{\lvert
W\rvert}{k}\right)^{2}.$

To bound this, we notice that $(1-x)+x^{2}$ for $x\in[0,1]$ is minimized for
$x=\frac{1}{2}$ with $\frac{1}{2}+\frac{1}{2^{2}}=\frac{3}{4}$. ∎

As a consequence, the proportionality notions EJR+ and FJR (Peters et al.,
2021b) 777FJR or fully justified representation is a strengthening of EJR,
which relaxes the cohesiveness requirement and thereby strengthens the axiom.
It is still satisfiable via a generalization of the GreedyEJR rule. are
compatible with a representation guarantee of $\frac{3}{4}$.

######  Corollary 13.

For every instance, there exist committees $W$ and $W^{\prime}$, each with
representation ratio of at least $\frac{3}{4}$, such that $W$ satisfies EJR+
and $W^{\prime}$ satisfies FJR.

###### Proof.

This follows from the fact that there are affordable committees satisfying
EJR+ (for instance, the output of MES or GJCR) or satisfying FJR (for
instance, the output of the greedy cohesive rule of Peters et al., 2021b). ∎

Next, we turn to completing committees via the sequential Chamberlin–Courant
(seq-CC) rule. It is well known that seq-CC achieves a representation
guarantee of $1-\frac{1}{e}\approx 0.632$ and that this is the best possible
for any polynomial-time rule (assuming P $\neq$ NP) (Feige, 1998). Perhaps
surprisingly, we show that the analysis of seq-CC does not depend on the first
steps being taken optimally, but that any affordable committee, completed with
seq-CC, has a representation guarantee of $1-\frac{1}{e}$. Thus, additionally
imposing strong proportionality notions (e.g., EJR+) does not lower the best
possible representation guarantee of a polynomial-time computable rule.

######  Theorem 14.

Let $W$ be an affordable committee. Then, $\overline{\text{seq-CC}}(W)$ has a
representation guarantee of $1-\frac{1}{e}$.

###### Proof.

First, by 1, the committee $W$ has a representation ratio of at least
$\frac{\lvert W\rvert}{k}$. Let
$\alpha=\operatorname{\textsf{cov}}\left(CC(\mathcal{I})\right)$ be the
optimal coverage. Now, seq-CC iteratively adds a candidate $c\notin W$ to $W$
such that $\operatorname{\textsf{cov}}(W\cup\\{c\\})$ is maximized. Let $r$ be
the representation ratio in a step of seq-CC. Then there are at least
$(1-r)\alpha$ of the voters covered by $CC(\mathcal{I})$ uncovered. Since they
can be covered using $k$ candidates, there is at least one candidate covering
$\frac{(1-r)\alpha}{k}$ of these voters. Thus, after adding the candidate to
$W$, the total number of uncovered voters is at most

$(1-r)\alpha-(1-r)\alpha\frac{1}{k}=(1-r)\left(1-\frac{1}{k}\right)\alpha$

. By induction, we get that after $k-\lvert W\rvert$ steps, there are at most

$\left(1-\frac{\lvert W\rvert}{k}\right)\left(1-\frac{1}{k}\right)^{k-\lvert
W\rvert}\alpha\leq\left(1-\frac{1}{k}\right)^{k}\alpha\leq\frac{\alpha}{e}$

uncovered voters. Since $\alpha$ is the optimal representation ratio, we get
that the representation guarantee of our approximation is at least
$1-\frac{1}{e}$. ∎

###  4.3 Combining Utilitarian and Representation Guarantees

Finally, we turn to combining both types of guarantees. For both ratios, we
show that they can be approximated optimally, while still maintaining a close-
to-optimal approximation to the other ratio. We first show that a
representation guarantee of exactly $\frac{3}{4}$ is compatible with an
asymptotically optimal utilitarian guarantee and EJR+.

######  Theorem 15.

For any $c>2$, there exists a committee satisfying EJR+ with a representation
guarantee of $\frac{3}{4}$ and a utilitarian guarantee of
$\min\left(\frac{2}{\sqrt{ck}}-\frac{2}{k},\frac{(c-2)^{2}}{4c^{2}}-\frac{1}{k}\right)\in\Omega(\frac{1}{\sqrt{k}})$.

###### Proof.

Let $W$ be the committee selected by GJCR. We distinguish two cases.

Case 1: $\lvert W\rvert\geq\frac{k}{c}$. In this case, we complete $W$
entirely with CC. As shown in Theorem 9, this gives us a representation
guarantee of $\frac{3}{4}$.

For the utilitarian guarantee, we follow the proof of Theorem 9. We again sort
the candidates $c_{1},\dots,c_{m}$ by their approval scores and let $c_{i+1}$
be the candidate with the largest approval score $\alpha\frac{n}{k}$ not
selected by GJCR. Based on the way GJCR is run, we know that
$i\geq\lfloor\alpha\rfloor$ since $c_{i+1}$ is not included in the committee.
For the utilitarian guarantee, we ignore the candidates added by CC and lower
bound the guarantee by

$\displaystyle\frac{\operatorname{\textsf{uw}}\left(\\{c_{1},\dots,c_{i}\\}\right)+\left(\frac{k}{c}-i\right)\frac{n}{k}}{\operatorname{\textsf{uw}}(\\{c_{1},\dots,c_{i}\\})+(k-i)\alpha\frac{n}{k}}\geq\frac{i\alpha\frac{n}{k}+\left(\frac{k}{c}-i\right)\frac{n}{k}}{i\alpha\frac{n}{k}+(k-i)\alpha\frac{n}{k}}=\frac{i\alpha+(\frac{k}{c}-i)}{i\alpha+(k-i)\alpha}$
$\displaystyle=\frac{(\alpha-1)i+\frac{k}{c}}{k\alpha}\geq\frac{(\alpha-1)^{2}+\frac{k}{c}}{k\alpha}\geq\frac{\alpha^{2}+\frac{k}{c}}{k\alpha}-\frac{2}{k}\geq\frac{2\alpha\frac{\sqrt{k}}{\sqrt{c}}}{k\alpha}-\frac{2}{k}=\frac{2}{\sqrt{ck}}-\frac{2}{k}\;\text{,}$

where in the last row we applied the AM-GM inequality.

Case 2: $\lvert W\rvert\leq\frac{k}{c}$. In this case, we can select the
$x\coloneqq\left\lfloor\frac{(c-2)^{2}}{4c^{2}}k\right\rfloor$ candidates with
the highest approval scores, thus guaranteeing a utilitarian guarantee of at
least $\frac{(c-2)^{2}}{4c^{2}}-\frac{1}{k}$. We note that

$\displaystyle\frac{k}{c}+\frac{(c-2)^{2}}{4c^{2}}k=k\frac{c^{2}+4}{4c^{2}}\leq
k\frac{4c^{2}-4c}{4c^{2}}=k-\frac{k}{c}\;\text{,}$

where for the inequality we used that $c\geq 2$. Thus, we can indeed select
$x$ candidates without using more than $k$ candidates in total.

For the representation guarantee, we observe that the function $x+(1-x)^{2}$
is monotonically decreasing between $0$ and $\frac{1}{2}$. Thus, using Lemma
11, we get a representation guarantee of at least

$\displaystyle\frac{\lvert W\rvert}{k}+\left(1-\frac{\lvert
W\rvert}{k}\right)\left(1-\frac{\lvert W\rvert+x}{k}\right)=\frac{\lvert
W\rvert}{k}+\left(1-\frac{\lvert W\rvert}{k}\right)^{2}-\left(1-\frac{\lvert
W\rvert}{k}\right)\frac{x}{k}$
$\displaystyle\geq\frac{1}{c}+\left(1-\frac{1}{c}\right)^{2}-\left(1-\frac{\lvert
W\rvert}{k}\right)\frac{x}{k}\geq
1+\frac{1}{c^{2}}-\frac{1}{c}-\frac{x}{k}=\frac{3}{4}+\frac{(c-2)^{2}}{4c^{2}}-\frac{x}{k}\geq\frac{3}{4}.$

∎

Moreover, we show that one can achieve a representation guarantee of
$\frac{3}{4}-\mathcal{O}(\frac{1}{\sqrt{k}})$ and a utilitarian guarantee of
$\frac{2}{\sqrt{k}}-\frac{1}{k}$ simultaneously with EJR+, thereby
strengthening the result of Elkind et al. (2022, Theorem 3.3) with a simpler
proof.

######  Theorem 16.

There exists a committee satisfying EJR+ with a representation guarantee of
$\frac{3}{4}-\frac{2}{\sqrt{k}}$ and a utilitarian guarantee of
$\frac{2}{\sqrt{k}}-\frac{1}{k}$.

###### Proof.

Again, let $W$ be the output of GJCR. If $\lvert W\rvert\geq\frac{3}{4}k$,
then by 1 we know that $W$ must have a representation guarantee of at least
$\frac{3}{4}$. Thus, by Theorem 9, the committee $\overline{AV}(W)$ achieves
both bounds.

If $\lvert W\rvert\leq\frac{3}{4}k$, we first complete it with the $\lfloor
2\sqrt{k}\rfloor$ candidates with the highest approval score and then with CC.
This, by definition, achieves a utilitarian guarantee of
$\frac{2}{\sqrt{k}}-\frac{1}{k}$. Let $W^{\prime}$ be the committee $W$
together with the $\lfloor 2\sqrt{k}\rfloor$ candidates and let $\rho$ be the
representation guarantee of $W^{\prime}$. By Lemma 11, we get that the
representation guarantee of $\overline{CC}(W^{\prime})$ is at least

$\displaystyle\rho$ $\displaystyle+(1-\rho)\frac{k-\lvert W\rvert-\lfloor
2\sqrt{k}\rfloor}{k}\geq\frac{\lvert W\rvert}{k}+\left(\frac{k-\lvert
W\rvert}{k}\frac{k-\lvert W\rvert-2\sqrt{k}}{k}\right)$
$\displaystyle=\frac{\lvert W\rvert}{k}+\left(\frac{k-\lvert
W\rvert}{k}\right)^{2}-\left(\frac{k-\lvert
W\rvert}{k}\right)\frac{2}{\sqrt{k}}\geq\frac{3}{4}-\frac{2}{\sqrt{k}}.$

∎

##  5 Other Completion Methods

There are other ways to complete committees besides AV and (seq-)CC. In this
section, we discuss three of them.

###  5.1 Maximin Support

The maximin support of a committee is a quantitative notion measuring the
overrepresentation of voters. Cevallos and Stewart (2021) argued that this
measure is relevant for the security of a blockchain consensus mechanism known
as Nominated Proof-of-Stake. They also showed that the maximin support method,
a voting rule introduced by Sánchez-Fernández et al. (2021), approximates this
measure.

To formally define these concepts, we adopt the formulation of Cevallos and
Stewart (2021). The maximin support $\operatorname{mms}(W)$ of a committee $W$
is given by $\min_{S\subseteq W,S\neq\emptyset}\frac{1}{\lvert
S\rvert}\lvert\\{i\in N\colon A_{i}\cap S\neq\emptyset\\}\rvert$, and the goal
is to maximize this value. The maximin support method (MMS) starts with an
empty committee $W$ and iteratively adds a candidate $c\notin W$ maximizing
$\operatorname{mms}(W\cup\\{c\\})$. This rule achieves a
$\frac{1}{2}$-approximation to the maximin support objective (Cevallos and
Stewart, 2021), but does not satisfy EJR (Sánchez-Fernández et al., 2021).

First, we give an example of an instance in which every committee satisfying
EJR approximates the optimal maximin support value by a factor of at most
$\frac{2}{3}$.

######  Example 2.

Consider an instance with $2k$ voters and $2k$ candidates
$c_{1},\dots,c_{2k}$. Voters $i=1,\dots,k$ each only approve candidate
$c_{i}$, while voters $i=k+1,\dots,2k$ approve all of $c_{k+1},\dots,c_{2k}$
and $c_{i-k}$. Now, the optimal committee with regard to the maximin support
would include the candidates $c_{1},\dots,c_{k}$ with an optimal maximin
support of $\frac{n}{k}=2$. On the other hand, to satisfy EJR we need to
include at least $\frac{k}{2}-1$ of the candidates $c_{k+1},\dots,c_{2k}$.
Hence, there must be at least $\frac{k}{2}-1$ voters from $1$ to $k$ without a
candidate they approve in the committee. The maximin support is thus at least
$\frac{1}{k}(k+\frac{k}{2}+1)=1.5+\frac{1}{k}$ and therefore a maximin support
approximation of $\frac{2}{3}+\varepsilon$ is not possible.

Second, we show that a simple application of a lemma from Cevallos and Stewart
(2021) shows that any affordable committee, completed with the maximin support
rule, achieves an approximation to the maximin support of $\frac{1}{2}$.

######  Theorem 17.

Let $W$ be an affordable committee. Then the committee obtained by completing
$W$ by running the maximin support rule approximates the maximin support
objective by a factor of $\frac{1}{2}$.

###### Proof.

Let $x$ be the optimal obtainable maximin support value. As shown by Cevallos
and Stewart (2021, Lemma 10), for any committee $W$ there always exists a
candidate $c\notin W$ with
$\operatorname{mms}(W\cup\\{c\\})\geq\min\left(\operatorname{mms}(W),\frac{1}{2}x\right)$.

First, since the optimal committee $W^{\prime}$ has size $|W^{\prime}|=k$, we
observe that

$\frac{1}{\lvert W^{\prime}\rvert}\left\lvert\\{i\in N\colon A_{i}\cap
W^{\prime}\neq\emptyset\\}\right\rvert\leq\frac{n}{k}$

and thus $x\leq\frac{n}{k}$. Further, since the committee is affordable, we
know that for any subset $S\subseteq W$ it has to hold that $\lvert\\{i\in
N\colon A_{i}\cap S\neq\emptyset\\}\rvert\geq\frac{\lvert S\rvert n}{k}$ and
thus $\operatorname{mms}(W)\geq\frac{n}{k}\geq x$. Hence, inductively by
adding candidates via the maximin support rule, it holds that in each step the
maximin support is at least $\frac{1}{2}x$ and, therefore, we have a
$\frac{1}{2}$-approximation. ∎

This approximation factor is currently the best known polynomial-time
approximation to the maximin support. Interesting question for future work
include (i) whether there is a polynomial-time rule with a better
approximation factor than $\frac{1}{2}$, and (ii) whether there always exists
a committee satisfying EJR and providing an approximation to the maximin
support value of better than $\frac{1}{2}$.

###  5.2 Other Completions

Next, we consider two completion methods that have been suggested in the PB
literature (Rey and Maly, 2023) for the Method of Equal Shares: “completion by
varying the budget” and “completion by perturbation.”

#### Completion by Varying the Budget

This completion method finds the first committee size $k^{\prime}\geq k$ for
which MES would select at least $k$ candidates. If, for committee size
$k^{\prime}$, MES selects a committee of size exactly $k$, then this committee
is output. Otherwise, the completion method outputs the committee selected for
committee size $k^{\prime}-1$. This, however, does not need not be exhaustive
(or even select any candidates) as the following simple example shows.888We
note that, due to the non-monotonicity of MES, this method does not
necessarily select a superset of the committee selected by MES (Rey and Maly,
2023), and is thus not a completion method in the technical sense.

######  Example 3.

Consider an instance with $n=6,k=2$ and three candidates $c_{1},c_{2},c_{3}$
such that each candidate is approved by exactly two voters. For $k=2$, MES
would output nothing, while for $k=3$ it would choose all candidates.

This shows that a second completion step is necessary. Boehmer et al. (2023)
and Faliszewski et al. (2023) suggest to use (a PB analog of) AV for this
second step. We show that this has the same guarantees as MES completed with
AV.

######  Theorem 18.

MES completed by varying the budget and AV achieves a representation guarantee
of $\frac{1}{k}$ and a utilitarian guarantee of
$\frac{2}{\sqrt{k}}-\frac{2}{k}$. Both bounds are asymptotically tight.

###### Proof.

Let $B\geq k$ the budget for which MES is finally run and let $W$ be the
selected committee.

For the representation guarantee, it is easy to see that the candidate with
the most approvals. which is guaranteed to be selected, covers at least
$\frac{1}{k}$ of the voters.

For the utilitarian guarantee, this follows from a similar case distinction as
in Theorem 9 and Theorem 10. For the unselected candidate with the largest
approval score $c_{i+1}$ (with $\lvert N_{c_{i+1}}\rvert=\alpha\frac{n}{k})$,
MES must buy at least $\left\lfloor\alpha\frac{B}{k}\right\rfloor$ candidates
approved by at least $\alpha\frac{n}{k}$ voters. Further, each candidate
selected afterwards has at least an approval score of $\frac{n}{B}$. Thus, we
get a utilitarian guarantee of

$\displaystyle\frac{\operatorname{\textsf{uw}}(\overline{AV}(W)))}{\operatorname{\textsf{uw}}(AV)}\geq\frac{\operatorname{\textsf{uw}}(\\{c_{1},\dots,c_{i}\\})+(k-i)\frac{n}{B}}{\operatorname{\textsf{uw}}(\\{c_{1},\dots,c_{i}\\})+(k-i)\alpha\frac{n}{k}}\geq\frac{i\alpha\frac{n}{k}+(k-i)\frac{n}{B}}{i\alpha\frac{n}{k}+(k-i)\alpha\frac{n}{k}}=\frac{\alpha
i+(k-i)\frac{k}{B}}{k\alpha}$
$\displaystyle=\frac{(\alpha-\frac{k}{B})i+\frac{k^{2}}{B}}{k\alpha}\geq\frac{(\alpha-\frac{k}{B})\lfloor\alpha\frac{B}{k}\rfloor+\frac{k^{2}}{B}}{k\alpha}\geq\frac{(\alpha-\frac{k}{B})(\alpha\frac{B}{k}-1)+\frac{k^{2}}{B}}{k\alpha}$
$\displaystyle\geq\frac{\alpha^{2}\frac{B}{k}-2\alpha+\frac{k^{2}}{B}}{k\alpha}=\frac{\alpha^{2}\frac{B}{k}+\frac{k^{2}}{B}}{k\alpha}-\frac{2}{k}\geq\frac{2\sqrt{\frac{\alpha^{2}B}{k}}\sqrt{\frac{k^{2}}{B}}}{k\alpha}-\frac{2}{k}=\frac{2}{\sqrt{k}}-\frac{2}{k}.$

The asymptotic tightness of the utilitarian guarantee follows from the general
upper bound on rules satisfying JR (Lackner and Skowron, 2020; Elkind et al.,
2022). For the representation guarantee, consider the instance in Example 3
with one of the candidates cloned $k$ times. This candidate and its clones
could be selected, leading to a coverage of $\frac{n}{k+1}$, while a coverage
of $\frac{kn}{k+1}$ is possible. ∎

#### Completion by Perturbation

This variant, suggested by Peters et al. (2021b), is also known as the
“epsilon method.” We give it here in the formulation of Faliszewski et al.
(2023). When MES terminates, the approvers of each unselected candidate
$c\notin W$ do not have enough budget left to fund $c$. The completion method
calculates, for each $c\notin W$, the $\rho$ such that $\sum_{i\in
N_{c}}b_{i}+\sum_{i\notin N_{c}}\min(b_{i},\rho)=1$. It selects the candidate
minimizing $\rho$ and updates the budgets accordingly. Thus, voters not
approving the candidate help fund it, but should spend as little as possible.
It is easy to see that this completion method makes MES exhaustive. We show
that it achieves a representation guarantee of $\frac{1}{2}$, but a
utilitarian guarantee of only $\frac{1}{k}$.

######  Theorem 19.

MES completed by perturbation has a utilitarian guarantee of
$\Theta(\frac{1}{k})$ and a representation guarantee of $\frac{1}{2}$. Both
bounds are asymptotically tight.

###### Proof.

For the representation guarantee, let $W$ be the selected committee. Further,
assume that there is another committee $W^{\prime}$ of size $k$ covering more
than twice as many voters as $W$. Let $N^{\prime}$ be the voters covered by
$W$ and $N^{\prime\prime}$ the voters covered by $W^{\prime}$ but not by $W$.
Since $W^{\prime}$ covers more than twice as many voters as $W$ we get that
$\lvert N^{\prime\prime}\rvert\geq\lvert N^{\prime}\rvert$.

First, we notice that if an originally unaffordable candidate is bought, the
voters approving this candidate must spend their whole budget. Let
$N_{1},\dots,N_{k}$ be a partition of $N^{\prime}$ such that the last
candidate (during the execution of MES) on which the voters in $N_{i}$ spend
their spent their budget is candidate $c_{i}$. By the pigeon-hole principle,
there must a $N_{i}$ with $\lvert N_{i}\rvert<\lvert W^{\prime}\setminus
W\rvert/k$. However, when this candidate was bought, instead the candidate
from $W^{\prime}\setminus W$ covering the largest set of approvers no one in
$W$ could have been selected, achieving a lower $\rho$ since the voters
approving have not spent any budget on candidates they approve. (We note that
this proof is very similar to the proof of Theorem 20. However, MES completed
by perturbation does not need to be priceable.)

The utilitarian guarantee of $\frac{1}{k}$, on the other hand, is the trivial
guarantee which follows from the fact that MES completed by perturbation
selects the approval winner in the first step.

The asymptotic tightness of the representation guarantee follows immediately,
since it is a constant-factor approximation. For the utilitarian guarantee,
consider an instance consisting of $\frac{n}{2k}$ voters approving $k$
candidates together and $n-\frac{n}{2k}$ voters, each approving a single
candidate only approved by them. MES completed by perturbation would first
select one candidate approved by the $\frac{n}{2k}$ voters, deplete their
budget and then select $k-1$ candidates arbitrarily, This has a utilitarian
welfare of $\frac{n}{2k}+k-1$ while the optimal utilitarian welfare is
$\frac{n}{2}$ thus showing a utilitarian guarantee of
$\mathcal{O}(\frac{1}{k})$. ∎

##  6 Conclusion and Future Work

We studied trade-offs between proportionality, coverage (aka diversity), and
utilitarian welfare (aka individual excellence) in the setting of approval-
based multiwinner voting. We showed that very good compromises, even under
strong proportionality notions, can be achieved by completing so-called
affordable committees. Rules that always output affordable committees include
the Method of Equal Shares (Peters and Skowron, 2020) and the Greedy Justified
Candidate Rule (Brill and Peters, 2023). For the latter, we showed that it can
be completed to achieve an optimal utilitarian guarantee of
$\frac{2}{\sqrt{k}}-\frac{1}{k}$, thereby answering an open question of Elkind
et al. (2022). For diversity, we showed that any affordable committee can be
completed to satisfy a representation guarantee of $\frac{3}{4}$. We also
studied trade-offs between both guarantees and showed that they can be
approximated close to optimal simultaneously, while still satisfying EJR+.

We highlight two directions for future work that go beyond approval-based
multiwinner voting. For elections based on ordinal (rank-order) preferences,
trade-offs between (the ordinal analogue of) the Chamberlin–Courant rule and
the Borda rule, as well as the Monroe rule, have been studied (Kocot et al.,
2019; Faliszewski and Talmon, 2018). It would be interesting to extend this
line of research by analyzing the “price of fairness” for axioms such as
proportionality for solid coalitions (Dummett, 1984) or the recently
introduced notions of Brill and Peters (2023). Furthermore, ordinal rules such
as STV (Tideman, 1995) or the Expanding Approvals Rule (Aziz and Lee, 2020)
may require completion methods as well, in the case of truncated, i.e.,
incomplete, ballots.

Moreover, it would be interesting to revisit the participatory budgeting
setting. Although the results by Fairstein et al. (2022) were mostly negative,
there remain several possibilities for more positive results. As a first
example, we note that Fairstein et al. (2022) exclusively look at the utility
function that counts the approved projects in the outcome. This, however, is
not the only way to measure utility. For instance, in real-world applications
of MES, the utility of a voter is often measured by the cost of approved
projects in the outcome (rather than their number); and several other utility
functions have been discussed in the PB literature (Brill et al., 2023; Maly
et al., 2023). It is, therefore, natural to ask whether the impossibility
results of Fairstein et al. (2022) extend to these functions, or whether
positive results are possible.

As a second example, a lot of axiomatic work has focused on “relaxed” notions
of fairness, such as EJR up to one project (Peters et al., 2021b). An
intriguing question is whether meaningful utilitarian and representation
guarantees _up to one project_ can be achieved.

### Acknowledgments

This research is supported by the Deutsche Forschungsgemeinschaft (DFG) under
the grant BR 4744/2-1 and the Graduiertenkolleg “Facets of Complexity” (GRK
2434). We thank Piotr Faliszewski for helpful feedback.

## References

  * Aziz and Lee [2020] H. Aziz and B. E. Lee.  The expanding approvals rule: improving proportional representation and monotonicity.  _Social Choice and Welfare_ , 54:1–45, 2020.
  * Aziz et al. [2017] H. Aziz, M. Brill, V. Conitzer, E. Elkind, R. Freeman, and T. Walsh.  Justified representation in approval-based committee voting.  _Social Choice and Welfare_ , 48(2):461–485, 2017\.
  * Boehmer et al. [2023] N. Boehmer, P. Faliszewski, Ł. Janeczko, and A. Kaczmarczyk.  Robustness of participatory budgeting outcomes: Complexity and experiments.  In _Proceedings of the 16th International Symposium on Algorithmic Game Theory (SAGT)_ , 2023.  Forthcoming.
  * Bredereck et al. [2019] R. Bredereck, P. Faliszewski, R. Niedermeier, and A. Kaczmarczyk.  An experimental view on committees providing justified representation.  In _Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI)_ , pages 109–115, 2019.
  * Brill and Peters [2023] M. Brill and J. Peters.  Robust and verifiable proportionality axioms for multiwinner voting.  In _Proceedings of the 24th ACM Conference on Economics and Computation (ACM-EC)_ , page 301. ACM, 2023.  Full version arXiv:2302.01989 [cs.GT].
  * Brill et al. [2017] M. Brill, R. Freeman, S. Janson, and M. Lackner.  Phragmén’s voting methods and justified representation.  In _Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI)_ , pages 406–413. AAAI Press, 2017.
  * Brill et al. [2023] M. Brill, S. Forster, M. Lackner, J. Maly, and J. Peters.  Proportionality in approval-based participatory budgeting.  In _Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI)_ , pages 5524–5531, 2023.
  * Cevallos and Stewart [2021] A. Cevallos and A. Stewart.  A verifiably secure and proportional committee election rule.  In _Proceedings of the 3rd ACM Conference on Advances in Financial Technologies (AFT)_ , pages 29–42. ACM, 2021.
  * Dummett [1984] M. Dummett.  _Voting Procedures_.  Oxford University Press, 1984.
  * Elkind et al. [2017] E. Elkind, P. Faliszewski, P. Skowron, and A. Slinko.  Properties of multiwinner voting rules.  _Social Choice and Welfare_ , 48:599–632, 2017.
  * Elkind et al. [2022] E. Elkind, P. Faliszewski, A. Igarashi, P. Manurangsi, U. Schmidt-Kraepelin, and W. Suksompong.  The price of justified representation.  In _Proceedings of the 36th AAAI Conference on Artificial Intelligence (AAAI)_ , pages 4983–4990, 2022.
  * Fairstein et al. [2022] R. Fairstein, D. Vilenchik, R. Meir, and K. Gal.  Welfare vs. representation in participatory budgeting.  In _Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems (AAMAS)_ , pages 409–417, 2022.
  * Faliszewski and Talmon [2018] P. Faliszewski and N. Talmon.  Between proportionality and diversity: Balancing district sizes under the chamberlin–courant rule.  In _Proceedings of the 17th International Conference on Autonomous Agents and Multiagent Systems (AAMAS)_ , pages 14–22, 2018.
  * Faliszewski et al. [2017] P. Faliszewski, P. Skowron, A. Slinko, and N. Talmon.  Multiwinner voting: A new challenge for social choice theory.  In U. Endriss, editor, _Trends in Computational Social Choice_ , chapter 2. AI Access, 2017.
  * Faliszewski et al. [2023] P. Faliszewski, J. Fils, D. Peters, G. Pierczyński, P. Skowron, D. Stolicki, S. Szufa, and N. Talmon.  Participatory budgeting: Data, tools, and analysis participatory budgeting: Data, tools, and analysis.  In _Proceedings of the 32nd International Joint Conference on Artificial Intelligence (IJCAI)_ , pages 2667–2674, 2023.
  * Feige [1998] U. Feige.  A threshold of ln n for approximating set cover.  _Journal of the ACM_ , 45(4):634–652, 1998.
  * Felsenthal and Maoz [1992] D. S. Felsenthal and Z. Maoz.  Normative properties of four single-stage multi-winner electoral procedures.  _Behavioral Science_ , 37(2):109–127, 1992.
  * Kocot et al. [2019] M. Kocot, A. Kolonko, E. Elkind, P. Faliszewski, and N. Talmon.  Multigoal committee selection.  In _Proceedings of the 28th International Joint Conference on Artificial Intelligence (IJCAI)_ , pages 385 – 391, 2019.
  * Kraiczy and Elkind [2023] S. Kraiczy and E. Elkind.  An adaptive and verifiably proportional method for participatory budgeting.  In _Proceedings of the 19th International Workshop on Internet and Network Economics (WINE)_ , 2023.  Forthcoming.
  * Lackner and Maly [2023] M. Lackner and J. Maly.  Proportional decisions in perpetual voting.  In _Proceedings of the 37th AAAI Conference on Artificial Intelligence (AAAI)_ , pages 5722–5729. AAAI Press, 2023.
  * Lackner and Skowron [2020] M. Lackner and P. Skowron.  Utilitarian welfare and representation guarantees of approval-based multiwinner rules.  _Artificial Intelligence_ , 288:103366, 2020.
  * Lackner and Skowron [2022] M. Lackner and P. Skowron.  _Multi-Winner Voting with Approval Preferences_.  Springer, 2022.
  * Maly et al. [2023] J. Maly, S. Rey, U. Endriss, and M. Lackner.  Fairness in participatory budgeting via equality of resources.  In _Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS)_ , pages 2031–2039, 2023.  Forthcoming.
  * Michorzewski et al. [2020] M. Michorzewski, D. Peters, and P. Skowron.  Price of fairness in budget division and probabilistic social choice.  In _Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI)_ , pages 2184–2191, 2020.
  * Munagala et al. [2022] K. Munagala, Y. Shen, and K. Wang.  Auditing for core stability in participatory budgeting.  In _Proceedings of the 18th International Workshop on Internet and Network Economics (WINE)_ , pages 292 – 310, 2022.
  * Peters and Skowron [2020] D. Peters and P. Skowron.  Proportionality and the limits of welfarism.  In _Proceedings of the 21st ACM Conference on Economics and Computation (ACM-EC)_ , pages 793–794. ACM, 2020.  Full version arXiv:1911.11747 [cs.GT].
  * Peters et al. [2021a] D. Peters, G. Pierczyński, N. Shah, and P. Skowron.  Market-based explanations of collective decisions.  In _Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI)_ , pages 5656–5663, 2021a.
  * Peters et al. [2021b] D. Peters, G. Pierczyński, and P. Skowron.  Proportional participatory budgeting with additive utilities.  In _Advances in Neural Information Processing Systems_ , volume 34, pages 12726–12737, 2021b.
  * Phragmén [1895] E. Phragmén.  _Proportionella val. En valteknisk studie_.  Svenska spörsmål 25. Lars Hökersbergs förlag, Stockholm, 1895.
  * Rey and Maly [2023] S. Rey and J. Maly.  The (computational) social choice take on indivisible participatory budgeting.  Technical report, arXiv:2303.00621 [cs.GT], 2023.
  * Sánchez-Fernández et al. [2017] L. Sánchez-Fernández, E. Elkind, M. Lackner, N. Fernández, J. A. Fisteus, P. Basanta Val, and P. Skowron.  Proportional justified representation.  In _Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI)_ , pages 670–676. AAAI Press, 2017.
  * Sánchez-Fernández et al. [2021] L. Sánchez-Fernández, N. Fernández, J. A. Fisteus, and M. Brill.  The maximin support method: An extension of the D’Hondt method to approval-based multiwinner elections.  In _Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI)_ , pages 5690–5697. AAAI Press, 2021.
  * Skowron [2021] P. Skowron.  Proportionality degree of multiwinner rules.  In _Proceedings of the 22nd ACM Conference on Economics and Computation (ACM-EC)_ , pages 820–840. ACM, 2021.
  * Tang et al. [2020] Z. Tang, C. Wang, and M. Zhang.  Price of fairness in budget division for egalitarian social welfare.  In _Proceedings of the 14th Annual International Conference on Combinatorial Optimization and Applications (COCOA)_ , pages 594–607, 2020.
  * Tideman [1995] N. Tideman.  The single transferable vote.  _Journal of Economic Perspectives_ , 9(1):27–38, 1995.

##  Appendix A Priceability with Variable Budget

Consider an instance $\mathcal{I}=(A,C,k)$. A committee $W\subseteq C$ is said
to be _$B$ -priceable_ if there exists a budget $B>0$ and a payment system
$(p_{i})_{i\in N}$ satisfying the following constraints:

  * C1

$p_{i}(c)=0$ if $c\notin A_{i}$ for all $c\in C$ and $i\in N$

  * C2

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

  * C3

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

  * C4

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

  * C5

$\sum_{i\in N_{c}}\left(\frac{B}{n}-\sum_{c\in C}p_{i}(c)\right)\leq 1$ for
all $c\notin W$.

We prove a representation guarantee for $B$-priceable committees that are
exhaustive. Examples of rules producing such committees include Phragmén’s
sequential rule [Phragmén, 1895], leximax-Phragmén [Brill et al., 2017], the
Maximin Support Method [Sánchez-Fernández et al., 2021], and Phragmms
[Cevallos and Stewart, 2021].

######  Theorem 20.

Let $W$ be an exhaustive $B$-priceable committee with budget $B\geq k$. Then,
$W$ has a representation guarantee of $\frac{1}{2}$.

###### Proof.

Assume that $W$ has a representation guarantee of strictly less than
$\frac{1}{2}$. Then, there exists a set of candidates $W^{\prime}$ with
$\operatorname{\textsf{cov}}(W^{\prime})>2\operatorname{\textsf{cov}}(W)$. Let
$N^{\prime}$ be the set of voters covered by $W$ and $N^{\prime\prime}$ the
set of voters covered by $W^{\prime}$ but not by $W$. We get that $\lvert
N^{\prime\prime}\rvert>\lvert N^{\prime}\rvert$.

Since $W$ is $B$-priceable and of size $|W|=k$, we know that every voter needs
to have at least a budget of $\frac{k}{\lvert N^{\prime}\rvert}$. However,
since $\lvert N^{\prime\prime}\rvert>\lvert N^{\prime}\rvert$ and all voters
in $N^{\prime\prime}$ are covered by $W^{\prime}$ there must be a candidate in
$W^{\prime}$ which covers more than $\frac{\lvert N^{\prime}\rvert}{k}$
voters, all previously uncovered. The approvers of this candidate must
therefore have a leftover budget of more than $1$, which contradicts the
assumption that $W$ is $B$-priceable. ∎

######  Theorem 21.

For any $\varepsilon>0$, there exists an instance in which every exhaustive
$B$-priceable committee has a representation ratio of less than
$\frac{1}{2}+\varepsilon$.

###### Proof.

Consider an instance with $\frac{n}{2}+1$ voters approving $k$ candidates
$\\{c_{1},\dots,c_{k}\\}$ and $k$ groups of size $(\frac{n}{2}-1)/k$ each
approving a single candidate not approved by any other group. Now assume that
we have an exhaustive $B$-priceable committee $W$ in which less than $k$
candidates from $\\{c_{1},\dots,c_{k}\\}$ are chosen. Since $W$ is
$B$-priceable and contains at least one candidate only approved by
$(\frac{n}{2}-1)/k$ voters, we know that $B\geq\frac{k}{\frac{n}{2}-1}$. Thus,
the group of $\frac{n}{2}+1$ voters have a budget of at least

$\left(\frac{n}{2}+1\right)B\geq\left(\frac{n}{2}+1\right)\frac{k}{\frac{n}{2}-1}>k.$

Therefore, they have enough budget to buy all $k$ candidates from their
approval set. Hence, $W$ was not $B$-priceable.

In this instance, a $B$-priceable committee can cover at most $\frac{n}{2}+1$
voters, while the committee optimizing coverage covers
$\frac{n}{2}+1+(k-1)\frac{\frac{n}{2}-1}{k}$. As for fixed $k$, the
representation ratio of this committee approaches $\frac{k}{2k-1}$ as
$n\to\infty$, we get that no representation guarantee of
$\frac{1}{2}+\varepsilon$ is possible for $B$-priceable and exhaustive
committees. ∎