Mathematical Programming
https://doi.org/10.1007/s10107-022-01852-1
FULL LENGTH PAPER
Series B
Approval-based apportionment
Markus Brill1·Paul Gölz2·Dominik Peters3·
Ulrike Schmidt-Kraepelin1·Kai Wilker1
Received: 31 January 2021 / Accepted: 30 May 2022
© The Author(s) 2022
Abstract
In the apportionment problem, a fixed number of seats must be distributed among
parties in proportion to the number of voters supporting each party. We study a gen-
eralization of this setting, in which voters can support multiple parties by casting
approval ballots. This approval-based apportionment setting generalizes traditional
apportionment and is a natural restriction of approval-based multiwinner elections,
where approval ballots range over individual candidates instead of parties. Using
techniques from both apportionment and multiwinner elections, we identify rules that
generalize the D’Hondt apportionment method and that satisfy strong axioms which
are generalizations of properties commonly studied in the apportionment literature. In
fact, the rules we discuss provide representation guarantees that are currently out of
reach in the general setting of multiwinner elections: First, we show that core-stable
committees are guaranteed to exist and can be found in polynomial time. Second,
we demonstrate that extended justified representation is compatible with committee
monotonicity (also known as house monotonicity).
A preliminary version of this paper has appeared in the Proceedings of the 34th AAAI Conference on
Artificial Intelligence [19].
BMarkus Brill
Paul Gölz
Dominik Peters
Ulrike Schmidt-Kraepelin
Kai Wilker
1Technische Universität Berlin, Research Group Efficient Algorithms, Berlin, Germany
2Carnegie Mellon University, Pittsburgh, PA, USA
3CNRS, LAMSADE, Université Paris Dauphine–PSL, Paris, France
123
M. Brill et al.
Mathematics Subject Classification 91B14 ·91B12 ·91B32
1 Introduction
The fundamental fairness principle of proportional representation is relevant in a vari-
ety of applications ranging from recommender systems to digital democracy [16]. It
features most explicitly in the context of political elections, which is the language
we adopt for this paper. In this context, proportional representation prescribes that
the number of representatives championing an opinion in a legislature should be
proportional to the number of voters who favor that opinion.
In most democratic institutions, proportional representation is implemented via
what we call party-choice elections: Candidates are members of political parties and
voters are asked to choose their favorite party; each party is then allocated a number
of seats that is (approximately) proportional to the number of votes it received. The
problem of transforming a voting outcome into a distribution of seats is known as
apportionment. Analyzing the advantages and disadvantages of different apportion-
ment methods has a long and illustrious political history and has given rise to an
elegant mathematical theory [7,48].
Forcing voters to choose a single party prevents them from communicating any
preferences beyond their most preferred alternative. For example, if a voter feels
equally well represented by several political parties, there is no way to express this
preferencewithinthevotingsystem.Inthecontextofsingle-winnerelections,approval
voting has been put forward as a solution to this problem as it strikes an attractive
compromise between simplicity and expressivity [10,40]. Under approval voting,
each voter is asked to specify a set of candidates she “approves of,” i.e., voters can
arbitrarily partition the set of candidates into approved candidates and disapproved
ones. Proponents of approval voting argue that its introduction could increase voter
turnout, “help elect the strongest candidate,” and “add legitimacy to the outcome” of
an election [10, pp. 4–8].
The practical and theoretical appeal of approval voting in single-winner elections
has led a number of scholars to suggest to also use approval voting for multiwinner
elections, in which a fixed number of candidates need to be elected [37]. Whereas,
in the single-winner setting, the straightforward voting rule “choose the candidate
approved by the highest number of voters” enjoys a strong axiomatic foundation [1,
14,27,28], several ways of aggregating approval ballots have been proposed for the
multiwinner setting [37,39].
Most studies of approval-based multiwinner elections assume that voters directly
express their preference over individual candidates; we refer to this setting as
candidate-approval elections. This assumption runs counter to widespread democratic
practice, in which candidates belong to political parties and voters indicate preferences
over these parties (which induce implicit preferences over candidates). In this paper,
we therefore study party-approval elections, in which voters express approval votes
over parties and a given number of seats must be distributed among the parties. We
refer to the process of allocating these seats as approval-based apportionment.
123
Approval-Based apportionment
Throughout this paper, we interpret a ballot that approves a set Sof parties as a
preference for legislatures with a larger total number of members from parties in S.
This interpretation generalizes the natural interpretation of party-choice ballots as
preferences for legislatures with a larger number of members of the chosen party. Our
interpretation implicitly imputes perfect indifference between approved parties. This
means that we assume voters to be indifferent to the distribution of seats between
approved parties. For example, consider only legislatures with a fixed total number of
seats given to approved parties. Then a voter would be indifferent between a legislature
where the approved parties all get an equal number of seats, and a legislature where just
one of the approved parties obtains all those seats. While this assumption is restrictive,
it does allow for a simple voting process, and the additional expressivity of approval
ballots compared to party-choice ballots seems attractive.
Indeed, we believe that party-approval elections are a promising framework for
legislative elections in the real world, especially since allowing voters to approve mul-
tiple parties enables the aggregation mechanism to coordinate like-minded voters. For
example, under party-choice elections, two groups of voters might vote for parties that
they mutually disapprove of. Approval ballots could reveal that both groups approve
a third party of more general appeal. Given this information, a voting rule could then
allocate more seats to this third party, leading to mutual gain. This cooperation is par-
ticularly necessary for small minority opinions that are not centrally coordinated. In
such cases, finding a commonly approved party can make the difference between being
represented or votes being wasted because the individual parties receive insufficient
support.
One aspect that makes it easier to transition from party-choice elections to party-
approval elections (rather than to candidate-approval elections) is that party-approval
elections can be implemented as closed-list systems. That is, parties can retain the
power to choose the ordering in which their candidates are allocated seats, as they
do in many current democratic systems. By contrast, candidate-approval elections
necessarily confer this power to the voters (leading to an open-list system), which
might give parties an incentive to oppose a change of the voting system. Of course,
party-approval elections are compatible with an open-list approach, since we can run
a secondary mechanism alongside the party-approval election to determine the order
of party candidates.
1.1 Related work
To the best of our knowledge, this paper is the first to formally develop and sys-
tematically study approval-based apportionment. That said, several scholars have
previously explored possible generalizations of existing aggregation procedures to
allow for approval votes over parties.
For instance, Brams et al. [13] study multiwinner approval rules that are inspired
by classical apportionment methods. Besides the setting of candidate approval, they
explicitly consider the case where voters cast party-approval votes. They conclude
that these rules could “encourage coalitions across party or factional lines, thereby
diminishing gridlock and promoting consensus.”
123
M. Brill et al.
Candidate-approval elections
(approval-based committee voting)
Party-approval elections
(approval-based apportionment)
Party-choice elections
(apportionment)
(i)
(ii)
(iii)
Fig. 1 Relations between the different settings of multiwinner elections. An arrow from Xto Ysignifies
that Xis a generalization of Y. The relationship corresponding to arrow (iii) has been explored by Brill et
al. [18]. We establish and explore the relationship (i) in Sect. 3and the relationship (ii) in Sect. 4
Such desire for compromise is only one motivation for considering party-approval
elections, as exemplified by recent work by Speroni di Fenizio and Gewurz [55]. To
allow for more efficient governing, they aim to concentrate the power of a legislature in
the hands of few big parties, while nonetheless preserving the principle of proportional
representation. To this end, they let voters cast party-approval votes and transform
these votes into a party-choice election by assigning each voter to one of her approved
parties. Specifically, they propose to assign voters to parties so that the strongest party
has as many votes as possible. We later call this method majoritarian portioning.
Several other papers consider extensions of approval-based voting rules to accom-
modate party-approval elections. In their paper introducing the satisfaction approval
voting rule, Brams and Kilgour [11] discuss a variant of this rule adapted for party-
approval votes. Mora and Oliver [41] and Camps et al. [20] study two approval-based
multiwinner rules due to Phragmén and Eneström, and note that they also work for
party-approval elections (which is true for any multiwinner rule using the embed-
ding that we discuss in Sect. 3). Both papers consider a monotonicity axiom for
party-approval elections (“if a party receives additional approvals, it should receive
additional seats”) but find that their two methods fail it. For the case of two parties,
they analyze the behavior of these rules as the house size approaches infinity. They find
that both rules fail to converge to the most natural seat distribution. Janson and Öberg
[34] analyze the limit behavior in more detail, and also show that Thiele’s sequential
rule (aka SeqPAV) does converge to the ideal value.
1.2 Relation to other settings
We can position party-approval elections between two well-studied voting settings
(see Fig. 1).
First, our setting can be viewed as a special case of approval-based multiwinner
voting, in which voters cast candidate-approval votes. A party-approval election can
be embedded in this setting by replacing each party by multiple candidates belonging
123
Approval-Based apportionment
to this party, and by interpreting a voter’s approval of a party as approval of all of
its candidates. This embedding establishes party-approval elections as a subdomain
of candidate-approval elections (see arrow (i) in Fig. 1). In Sect. 3, we explore the
axiomatic and computational ramifications of this domain restriction.
Second, approval-based apportionment generalizes standard apportionment (arrow
(ii)), which corresponds to party-approval elections in which all approval sets are
singletons (i.e., party-choice elections). In Sect. 4, we propose a method to general-
ize apportionment methods to the party-approval setting using so-called portioning
methods.
1.3 Contributions
In this paper, we formally introduce the setting of approval-based apportionment
and explore different possibilities of constructing axiomatically desirable aggregation
methods for this setting. Besides its conceptual appeal, this setting is also interesting
from a technical perspective.
Exploiting the relations described in Sect. 1.2, we resolve problems that remain
open in the more general setting of candidate-approval elections. First, we show that
the core of an approval-based apportionment problem is always nonempty, and that
a popular multiwinner rule known as Proportional Approval Voting (PAV) always
returns a core-stable committee. We also present a polynomial-time variant of PAV
that is also core stable. Second, we prove that committee monotonicity is compatible
with extended justified representation (a representation axiom proposed by Aziz et al.
[3]) by providing a rule that satisfies both properties.
Some familiar multiwinner rules (in particular, PAV) provide stronger representa-
tionguaranteeswhenappliedintheparty-approval setting.However,formanystandard
multiwinner voting rules, we give examples that show that their axiomatic guarantees
do not improve in the party-approval setting. From a computational complexity per-
spective, we show that some rules known to be NP-hard in the candidate-approval
setting remain NP-hard to evaluate in the party-approval setting. However, it becomes
computationally easier to reason about proportionality axioms. Specifically, we show
that it is tractable to check whether a given committee satisfies extended justified rep-
resentation (or the weaker axiom of proportional justified representation). The analogs
of these problems for candidate-approval elections are coNP-hard. These tractability
results do not extend to checking whether a committee is core-stable: we show that this
problem is coNP-complete for both party-approval and candidate-approval elections.
2Themodel
Aparty-approval election is a tuple (N,P,A,k)consisting of a set of voters N=
{1,...,n}, a finite set of parties P, a ballot profile A=(A1,...,An)where each
ballot Ai⊆Pis the set of parties approved by voter i, and the committee size k∈N.
We assume that Ai=∅for all i∈N. When considering computational problems, we
assume that kis encoded in unary (see Remark 3.1). This is a mild restriction since
123
M. Brill et al.
in most applications (such as legislative elections), kis smaller than the number of
voters.
Acommittee in this setting is a multiset W:P→Nover parties, which determines
the number of seats W(p)assigned to each party p∈P. The size of a committee W
is |W|=p∈PW(p), and we denote multiset addition and subtraction by +and −,
respectively. For a voter iand a committee W, we write ui(W)=p∈AiW(p)for
the number of seats in Wthat are allocated to parties approved by voter i.Aparty-
approval rule is a function that takes a party-approval election (N,P,A,k)as input
and returns a committee Wof valid size |W|=k.1
In our axiomatic study of party-approval rules, we focus on two axioms capturing
proportional representation: extended justified representation and core stability. Both
are derived from their analogs in candidate-approval elections (see Sect. 3.2) where
they were proposed by Aziz et al. [3]. To state these axioms, it is helpful to define the
quota of a subset Sof voters as q(S)=k·|S|/n. Intuitively, q(S)corresponds to
the number of seats that the group S“deserves” to be represented by (rounded down).
Definition 2.1 A committee W:P→Nprovides extended justified representation
(EJR) for a party-approval election (N,P,A,k)if there is no subset S⊆Nof voters
such that i∈SAi=∅and ui(W)<q(S)for all i∈S.
In words, EJR requires that for every voter group Swith a commonly approved
party, at least one voter of the group must approve at least q(S)committee members. A
party-approval rule is said to satisfy EJR if it only produces committees providing EJR.
We can obtain a stronger representation axiom by removing the requirement of a
commonly approved party.
Definition 2.2 A committee W:P→Nis core stable for a party-approval election
(N,P,A,k)if there is no nonempty subset S⊆Nand committee T:P→Nof
size |T|≤q(S)such that ui(T)>ui(W)for all i∈S.Thecore of a party-approval
election is the set of all core-stable committees.
Core stability requires adequate representation even for voter groups that cannot
agree on a common party, by ruling out the possibility that the group can deviate to a
smaller committee that represents all voters in the group strictly better. It follows from
the definitions that core stability is a stronger requirement than EJR: If a committee
violates EJR, there is a group Sthat would prefer any committee of size q(S)that
assigns all seats to the commonly approved party.
Besides these representation axioms, a final axiom that we will discuss is committee
monotonicity (e.g., [8,24]). A party-approval rule fsatisfies this axiom if, for all party-
approval elections (N,P,A,k), it holds that f(N,P,A,k)⊆f(N,P,A,k+1).
The apportionment literature calls this house monotonicity. Committee monotonic
rules avoid the so-called Alabama paradox, in which a party loses a seat when the
committee size increases. They can also be used to construct proportional rankings [31,
53].
1This definition implies that rules are resolute, i.e., they only return a single committee. In the case of a
tie between multiple committees, a tiebreaking mechanism is necessary. Our results hold independently of
the choice of a specific tiebreaking mechanism.
123
Approval-Based apportionment
3 Constructing party-approval rules via multiwinner voting rules
In this section, we show how party-approval elections can be translated into candidate-
approval elections. This embedding allows us to apply established candidate-approval
rules to our setting. Exploiting this fact, we will prove the existence of core-stable
committees for party-approval elections.
3.1 Preliminaries
Acandidate-approval election is a tuple (N,C,A,k). Just as for party-approval elec-
tions, N={1,...,n}is a set of voters, Cis a finite set, Ais an n-tuple of nonempty
subsets of C, and k∈Nis the committee size. The conceptual difference is that C
is a set of individual candidates rather than parties. This difference manifests itself
in the definition of a committee because a single candidate cannot receive multiple
seats. That is, a candidate committee W is now simply a subset of Cwith cardinality
k. (Therefore, it is usually assumed that |C|≥k.) A candidate-approval rule is a
function that maps each candidate-approval election to a candidate committee.
A diverse set of such voting rules have been proposed since the late 19th cen-
tury [32,37,39], out of which we will only introduce the one which we use for our
main positive result. Let Hjdenote the jth harmonic number, i.e., Hj=j
t=11/t.
Given (N,C,A,k), the candidate-approval rule proportional approval voting (PAV),
introduced by Thiele [56], chooses a candidate committee Wmaximizing the PAV
score PAV(W)=i∈NH|W∩Ai|.
We now describe EJR and core stability in the candidate-approval setting, from
which we derived our versions. Recall that q(S)=k|S|/n. A candidate committee
Wprovides EJR if there is no subset S⊆Nand no integer >0 such that q(S)≥,
|i∈SAi|≥, and |Ai∩W|<for all i∈S. (The requirement |i∈SAi|≥
is often called cohesiveness.) A candidate-approval rule satisfies EJR if it always
produces EJR committees.
The definition of core stability is even closer to the version in party-approval elec-
tions: A candidate committee Wis core stable if there is no nonempty group S⊆N
and no set T⊆Cof size |T|≤q(S)such that |Ai∩T|>|Ai∩W|for all i∈S.
The core consists of all core-stable candidate committees.
3.2 Embedding party-approval elections
We have informally argued in Sect. 1.2 that party-approval elections constitute a
subdomain of candidate-approval elections. We formalize this notion by providing
an embedding of party-approval elections into the candidate-approval domain. Our
approach is similar to that of Brill et al. [18], who have formalized how apportionment
problems can be phrased as candidate-approval elections.
For a given party-approval election (N,P,A,k), we define a corresponding
candidate-approval election (N,C,A,k)with the same set of voters Nand the
same committee size k. The set of candidates contains kmany “clone” candi-
dates p(1),...,p(k)for each party p∈P,soC=p∈P{p(1),...,p(k)}. Voter
123
M. Brill et al.
iapproves a candidate p(j)in the candidate-approval election if and only if she
approves the corresponding party pin the party-approval election. Thus, A
i=
p∈Ai{p(1),...,p(k)}.
A candidate committee W⊆Ccorresponds to a committee W:P→Nfor the
party-approval election with W(p)=|W∩{p(1),...,p(k)}|. One can also convert
in the other direction: a committee W:P→Nfor the party-approval election
corresponds to the candidate committee W=p∈P{p(1),...,p(W(p))}.
This embedding establishes party-approval elections as a subdomain of candidate-
approval elections. As a consequence, we can apply rules from the more general
candidate-approval setting to the party-approval setting, by
1. translating the party-approval election into a candidate-approval election,
2. applying the candidate-approval rule, and
3. converting its chosen candidate committee into a committee over parties.
Any axiom for candidate-approval rules implies an axiom for the derived party-
approval rule. One can check that if a candidate-approval rule satisfies EJR or core
stability (as defined in Sect. 3.1) then the derived party-approval rule satisfies the
respective axiom (as defined in Sect. 2). In particular, note that by restricting our view
to party approval, the cohesiveness requirement of EJR is reduced to requiring a single
commonly approved party.
Remark 3.1 By ourassumption that kisencoded in unaryforthe purpose ofcomplexity
analysis (see Sect. 2), the translation of a party-approval election yields a polynomial-
sized candidate-approval election. Thus, a polynomial-time candidate-approval rule
applied to the party-approval election runs in polynomial time as well. If kwas instead
encoded in binary, elections with large kand few parties could be described so con-
cisely that even straightforward candidate-approval algorithms would formally have
exponential running time.2(The same issue does not appear in candidate-approval
elections, where we need to list at least kcandidates, which makes the description
verbose.)
In practice, rather than explicitly going via the embedding, it can be useful to write
down the induced party-approval rule directly in terms of a party-approval election.
For example, the party-approval version of PAV chooses a committee W:P→N
that maximizes PAV(W)=i∈NHui(W).
3.3 PAV guarantees core stability
A powerful stability concept in economics, core stability is a natural extension of EJR.
It is particularly attractive because blocking coalitions do not need to unanimously
approve any party; they only need to be able to coordinate for mutual gain.
2However, some rules may admit implementations that remain efficient for binary k. For example, Rule X
[43], also known as the Method of Equal Shares, will repeatedly assign seats to the same party until one of
its supporters runs out of virtual money. Since this happens at most ntimes, this observation can be used to
design an efficient algorithm (with runtime depending on log kinstead of k). Still, a linear time dependence
on kis acceptable in most applications.
123
Approval-Based apportionment
Unfortunately,itisstillunknownwhethercore-stablecandidatecommitteesexistfor
all candidate-approval elections.3All standard candidate-approval rules either already
fail weaker representation axioms such as EJR, or are known to fail core stability.
In particular, PAV satisfies EJR, but may produce non-core-stable committees for
candidate-approval elections [3]. Peters and Skowron [43] show that a large class of
candidate-approval rules (so-called welfarist rules) must all fail core stability.
For our main result, we show that core stability can always be achieved in the
party-approval setting. Specifically, the committee selected by PAV is core stable
for party-approval elections. Our proof uses a similar technique to the proof that PAV
satisfiesEJRfor candidate-approvalelections[3,Theorem 10]; wediscusstheessential
difference in Remark 3.4.
Theorem 3.2 For every party-approval election, PAV chooses a core-stable committee.
Hence, the core of a party-approval election is nonempty.
Proof Consider a party-approval election (N,P,A,k)and let W1:P→Nbe the
committee selected by PAV. Assume for a contradiction that W1is not core stable.
Then there is a nonempty coalition S⊆Nand a committee T:P→Nsuch that
|T|≤q(S)≤k|S|/nand ui(T)≥ui(W1)+1 for every voter i∈S.
For each party p,weletΔ+(p,W1)denote the marginal increase of the PAV score
when we allocate an extra seat to p. Thus,
Δ+(p,W1)=PAV(W1+{p})−PAV(W1)=
i∈Np
1
ui(W1)+1,
where Np={i∈N|p∈Ai}. Let us calculate the average marginal increase when
adding an elements of T:
1
|T|
p∈P
T(p)Δ
+(p,W1)=1
|T|
i∈N
p∈Ai
T(p)
ui(W1)+1≥1
|T|
i∈S
p∈Ai
T(p)
ui(W1)+1
≥1
|T|
i∈S
p∈Ai
T(p)
ui(T)=1
|T|
i∈S
ui(T)
ui(T)=|S|
|T|≥n
k.
Thus, there is a party p1with Δ+(p1,W1)≥n/k.LetW2=W1+{p1}.
Next, for each party pwith W2(p)>0, let Δ−(p,W2)be the marginal decrease
of the PAV score if we take away a seat from pin W2. Thus,
Δ−(p,W2)=PAV(W2)−PAV(W2−{p})=
i∈Np
1
ui(W2).
3However, it is known that approximately core-stable committees exist, for several different ways of
approximating the core notion [21,26,35,43].
123
M. Brill et al.
The average marginal decrease of taking away a seat from W2is
1
k+1
p∈P
W2(p)Δ
−(p,W2)=1
k+1
p∈P
i∈Np
W2(p)
ui(W2)
=1
k+1
i∈N
p∈Ai
W2(p)
ui(W2)
=1
k+1|{i∈N:ui(W2)>0}| ≤ n
k+1.
Thus, there is some party p2with W2(p2)>0 such that Δ−(p2,W2)≤n
k+1. Write
W3=W2−{p2}=W1+{p1}−{p2}. Then
PAV(W3)=PAV(W2)−Δ−(p2,W2)
=PAV(W1)+Δ+(p1,W1)−Δ−(p2,W2)
≥PAV(W1)+n
k−n
k+1
>PAV(W1),
contradicting the optimality of W1.
Remark 3.3 Our proof of Theorem 3.2 can be easily adapted to show that PAV satisfies
the stronger version of core defined with respect to the Droop quota [22,33], by
assuming |T|<(k+1)|S|/nrather than |T|≤k|S|/n.
Remark 3.4 For candidate-approval elections, the proof of Theorem 3.2 shows that
PAV satisfies core stability restricted to “disjoint objections”: if Wis the committee
selected by PAV, then there can be no set Twith T∩W=∅such that there is a coalition
Swith T≤q(S)and ui(T)>ui(W)for all i∈S. Note that with our embedding of
party-approval elections into candidate-approval elections, the disjointness assump-
tion is without loss of generality if there are enough virtual candidates representing
each party, and hence PAV satisfies core stability for party-approval elections. The
disjoint objections property also implies the result of Peters and Skowron [43, Theo-
rem 6] that PAV satisfies the “2-core” property in the candidate-approval context: If
there was an objection Tthat more than doubled the utility of each coalition member,
then T\Wwould be a disjoint core deviation, which is a contradiction.
Remark 3.5 Because Hj=Θ(log j), the PAV objective is closely related to the
classical maximum Nash welfare (MNW) solution [36,42]. One can see PAV as a dis-
cretizationof theMNW solution forselecting aprobability distributionσ:P→[0,1]
over parties, where we can interpret σ(p)as the fraction of seats that should be allo-
cated to party p. That rule satisfies a continuous analog of the core condition [5,25].
However, other natural discretizations of the Nash rule do not satisfy the core con-
dition. In the next section, we will see that discretizing the Nash rule using common
apportionment methods leads to violations of core stability. Furthermore, selecting a
committee that maximizes Nash welfare (rather than the PAV objective function) may
fail core stability, even in party-choice elections [18, Theorem 2].
123
Approval-Based apportionment
Given that PAV satisfies core stability in party-approval elections but not in
candidate-approval elections, do other candidate-approval rules satisfy stronger rep-
resentation axioms when restricted to the party-approval subdomain? We have studied
this question for various rules besides PAV, and the answer was always negative; see
Appendix Bfor details.4
Amajordrawbackof PAV is thatitfailscommitteemonotonicity,andPAVcontinues
to fail this axiom in the party-approval setting.5Therefore, parties may lose seats when
the committee size is increased. In the next section, we construct party-approval rules
that avoid this undesirable behavior.
4 Constructing party-approval rules via portioning and
apportionment
Party-approval elections are a generalization of party-choice elections, which can be
thought of as party-approval elections in which all approval sets are singletons. Since
there is a rich body of research on apportionment methods [7,48] which act on party-
choice elections, it is natural to examine whether we can employ these methods for our
setting as well. To use them, we will need to translate party-approval elections into the
party-choice domain on which apportionment methods operate. This translation thus
needs to transform a collection of approval votes over parties into vote shares for each
party. Motivated by time sharing, Bogomolnaia et al. [9] have developed a theory of
such transformation rules, further studied by Duddy [23], Aziz et al. [5], and Brandl
et al. [15]. We will refer to this framework as portioning.
The approach explored in this section, then, divides the construction of a party-
approval rule into two independent steps: (1) portioning, which maps a party-approval
electionto avectorofparties’ shares;followed by (2)apportionment, whichtransforms
the shares into a seat distribution.
Both the portioning and the apportionment literature have discussed representation
axioms similar in spirit to EJR and core stability. For both settings, several rules have
been found to satisfy these properties. One might hope that by composing two rules
that are each representative, we obtain a party-approval rule that is also representative
(and satisfies, say, EJR). If we succeed in finding such a combination, it is likely that
the resulting voting rule will automatically satisfy committee monotonicity since most
apportionment methods satisfy this property. In the general candidate-approval setting
(considered in Sect. 3), the existence of a rule satisfying both EJR and committee
monotonicity is an open problem [39].
4We present relevant counterexamples for the candidate-approval rules seq-Phragmén, leximax-Phragmén,
Eneström-Phragmén, Rule X, and the Maximin Support Method. In addition, we verified for the
candidate-approval rules SeqPAV, RevSeqPAV, var-Phragmén, Approval Voting (AV), SatisfactionAV, Min-
imaxAV, MonroeAV, GreedyMonroeAV, GreedyAV, HareAV, and Chamberlin–CourantAV that existing
counterexamples can easily be adjusted to the party-approval setting.
5Existing counterexamples for the candidate-approval setting [39] can be adapted in a straight-forward
way.
123
M. Brill et al.
4.1 Preliminaries
We start by introducing relevant notions from the literature on portioning [5,9] and
apportionment [7,48], with notation suitably adjusted to our setting.
4.1.1 Portioning
Aportioning problem is a triple (N,P,A), just as in party-approval voting but without
a committee size. A portioning is a function r:P→[0,1]with p∈Pr(p)=1. We
interpret r(p)as the vote share of party p.Aportioning method maps each portioning
problem (N,P,A)to a portioning.
Our minimum requirement on portioning methods will be that they uphold propor-
tionality if all approval sets are singletons, i.e., if we are already in the party-choice
domain. Formally, we say that a portioning method is faithful if for all (N,P,A)with
|Ai|=1 for all i∈N, the resulting portioning rsatisfies r(p)=|{i∈N|Ai=
{p}}|/nfor all p∈P. Among the portioning methods considered by Aziz et al. [5],
only three are faithful. They are defined as follows.
Conditional utilitarian portioning selects, for each voter i,pias a party in Ai
approved by the highest number of voters. Then, r(p)=|{i∈N|pi=p}|/n
for all p∈P.
Random priority computes n!portionings, one for each permutation σof N, and
returns their average. The portioning for σ=(i1,...,in)maximizes p∈Ai1r(p),
breaking ties by maximizing p∈Ai2r(p), and so forth.
Nash portioning selects the portioning rmaximizing the Nash welfare
i∈Np∈Air(p).
When computing the outcomes of these rules, ties may occur. For our results it will
not matter how ties are broken: we only use these rules in counterexamples in which
no ties occur.
On first sight, Nash portioning seems particularly promising because it satisfies
portioning versions of core stability and EJR [5,30]. Concretely, it satisfies a property
called average fair share introduced by Aziz et al. [5], which requires that there is no
subset S⊆Nof voters such that i∈SAi=∅and 1
|S|i∈Sp∈Air(p)<|S|/|N|.
However, despite these promising properties, we will see that Nash portioning does not
work for our purposes. Instead, we will need to make use of a more recent portioning
approach, which was proposed by Speroni di Fenizio and Gewurz [55] in the context
of party-approval voting.
Majoritarian portioning proceeds in rounds j=1,2,.... Initially, all parties and
voters are active. In iteration j, select the active party pjthat is approved by the
highest number of active voters. Let Njbe the set of active voters who approve
pj. Then, set r(pj)to |Nj|/n, and mark pjand all voters in Njas inactive. If
active voters remain, start the next iteration; otherwise, return r.
Under majoritarian portioning, we ignore the approval preferences of voters after they
have been “assigned” to a party. Note that conditional utilitarian portioning is a similar
sequential method which does, however, not ignore the preferences of inactive voters.
123
Approval-Based apportionment
4.1.2 Apportionment
An apportionment problem is a tuple (P,r,k), which consists of a finite set of parties
P, a portioning r:P→[0,1]specifying the vote shares of parties, and a com-
mittee size k∈N. Committees are defined as for party-approval elections, and an
apportionment method maps apportionment problems to committees Wof size k.
An apportionment method satisfies lower quota if each party pis always allocated
at least k·r(p)seats in the committee. Furthermore, an apportionment method fis
committee monotonic if f(P,r,k)⊆f(P,r,k+1)for every apportionment problem
(P,r,k).
Among the standard apportionment methods, only two satisfy both lower quota
and committee monotonicity: the D’Hondt method (aka Jefferson method) and the
quota method.6The D’Hondt method assigns the kseats iteratively, each time giving
the next seat to the party pwith the largest quotient r(p)/(s(p)+1), where s(p)
denotes the number of seats already assigned to p.Thequota method [6] is identical
to the D’Hondt method, except that, in the jth iteration, only parties psatisfying
s(p)/ j<r(p)are eligible for the allocation of the next seat. Ties should be broken
in a consistent fashion so as to ensure house monotonicity, for example using a fixed
tie-breaking order over parties.
4.1.3 Composition
If we take any portioning method and any apportionment method, we can compose
them to obtain a party-approval rule. Formally, the composition of portioning method
Rand apportionment method Mmaps each party-approval election (N,P,A,k)to a
committee M(P,R(N,P,A), k). Note that if the apportionment method is committee
monotonic then so is the composed rule, since the portioning is independent of k.
4.2 Composed rules that fail EJR
Perhaps surprisingly, many pairs of portioning and apportionment methods fail EJR.
This is certainly true if the individual parts are not representative themselves. For
example, if an apportionment method M“properly” fails lower quota (in the sense
that there is a rational-valued input ron which lower quota is violated), then one can
construct an example profile on which any composed rule using Mfails EJR: Construct
aparty-approvalelectionwith singleton approvalsets inwhich the voter counts arepro-
portional to the shares in the counterexample r. Then any faithful portioning method,
applied to this election, must return r. Since Mfails lower quota on r, the resulting
committee will violate EJR. By a similar argument, suppose that an apportionment
method violates committee monotonicity, and that there is a rational-valued counterex-
ample. Then the apportionment method, when composed with a faithful portioning
method, will give rise to a party-approval rule that fails committee monotonicity.
As mentioned above, D’Hondt and the quota method are the only standard appor-
tionment rules to satisfy both lower quota and committee monotonicity. However, the
6All other divisor methods fail lower quota, and the Hamilton method is not committee monotonic [7].
123
M. Brill et al.
composition of either option with the conditional utilitarian, random priority, or Nash
portioning methods fails EJR, as the following examples show.
Example 4.1 Let n=k=6, P={p0,p1,p2,p3}, and consider the ballot profile
A=({p0},{p0},{p0,p1,p2},{p0,p1,p2},{p1,p3},{p2,p3}).
Then, the conditional utilitarian solution sets r(p0)=4/6, r(p1)=r(p2)=1/6,
and r(p3)=0. Any apportionment method satisfying lower quota allocates four seats
to p0, one each to p1and p2, and none to p3. The resulting committee does not provide
EJR since the last two voters, who jointly approve p3, have a quota of q({5,6})=2
that is not met.
Example 4.2 Let n=k=6, P={p0,p1,p2,p3}, and consider the ballot profile
A=({p0},{p0},{p0,p1,p2},{p0,p1,p3},{p1},{p2,p3}).
Random priority chooses the portioning r(p0)=23/45, r(p1)=23/90, and
r(p2)=r(p3)=7/60. Both D’Hondt and the quota method allocate four seats
to p0, two seats to p1, and none to the other two parties. This violates the claim to
representation of the sixth voter (with q({6})=1).
Nashportioningproduces a fairlysimilar portioning, withr(p0)≈0.5302,r(p1)≈
0.2651, and r(p2)=r(p3)≈0.1023. D’Hondt and the quota method produce the
same committee as above, leading to the same EJR violation.
It might be surprising that Nash portioning combined with a lower-quota apportion-
ment method violates EJR. After all, Nash portioning satisfies core stability in the
portioning setting, which is a strong notion of proportionality, and the lower-quota
property limits the rounding losses when moving from the portioning to a committee.
As expected, in the election of Example 4.2, the portioning produced by Nash gives
sufficient representation to the sixth voter since r(p2)+r(p3)≈0.2047 >1/6.
However, since both r(p2)and r(p3)are below 1/6 on their own, lower quota does
not apply to either of the two parties, and the sixth voter loses all representation in the
apportionment step.7
4.3 Composed rules that satisfy EJR
As we have seen, several initially promising portioning methods fail to compose to a
rule that satisfies EJR. One reason is that these portioning methods are happy to assign
small shares to several parties. The apportionment method may round several of those
small shares down to zero seats. This can lead to a failure of EJR when not enough
parties obtain a seat. It is difficult for an apportionment method to avoid this behavior
since the portioning step obscures the relationships between different parties that are
apparent from the approval ballots of the voters.
Since majoritarian portioning maximizes the seat allocations to the largest parties, it
tends to avoid the problem we have just identified. While it fails the strong representa-
tion axioms that Nash portioning satisfies, this turns out not to be crucial: Composing
7There are similar examples where Nash portioning with D’Hondt apportionment violates EJR even though
every party receives at least one seat, and examples where EJR is violated by a margin of more than one
seat.
123
Approval-Based apportionment
majoritarian portioning with any apportionment method satisfying lower quota yields
an EJR rule. If we use an apportionment method that is also committee monotonic,
such as D’Hondt or the quota method, we obtain a party-approval rule that satisfies
both EJR and committee monotonicity.
Theorem 4.3 Let M be a committee monotonic apportionment method satisfying
lower quota. Then, the party-approval rule composing majoritarian portioning and
M satisfies EJR and committee monotonicity.
Proof Consider a party-approval election (N,P,A,k)and let rbe the outcome of
majoritarian portioning applied to (N,P,A).LetN1,N2,... and p1,p2,... be the
voter groups and parties in the construction of majoritarian portioning, so that r(pj)=
|Nj|/nfor all j.
Consider the committee W=M(P,r,k)and suppose that EJR is violated, i.e.,
that there exists a group S⊆Nwith i∈SAi=∅and ui(W)<q(S)for all i∈S.
Let jbe minimal such that S∩Nj=∅. We now show that |S|≤|Nj|.Bythe
definition of j, no voter in Sapproves of any of the parties p1,p2,...pj−1; thus,
all those voters remain active in round j. Consider a party p∗∈i∈SAi.Inthe jth
iteration of majoritarian portioning, this party had an approval score (among active
voters)ofatleast|S|. Therefore, the party pjchosen in the jth iteration has an approval
score that is at least |S|(of course, p∗=pjis possible). The approval score of party
pjequals |Nj|. Therefore, |Nj|≥|S|.
Since |Nj|≥|S|,wehaveq(Nj)≥q(S). Since Msatisfies lower quota, it assigns
at least k·r(pj)=k(|Nj|/n)=q(Nj)seats to party pj. Now consider a voter
i∈S∩Nj. Since this voter approves party pj,wehaveui(W)≥W(pj)≥q(Nj)≥
q(S), a contradiction.
This shows that EJR is indeed satisfied; committee monotonicity follows from the
committee monotonicity of M.
Whiletheparty-approvalrulesidentified by Theorem4.3satisfy EJR andcommittee
monotonicity, they do not reach our gold standard of representation, i.e., core stability:
Example 4.4 Let n=k=16, P={p0,...,p4}, and consider the following ballot
profile:
4×{p0,p1},3×{p1,p2},1×{p2}
4×{p0,p3},3×{p3,p4},1×{p4}
Majoritarian portioning allocates 1/2top0and 1/4 each to p2and p4.Anylower-
quota apportionment method must translate this into 8 seats for p0and 4 seats each
for p2and p4. This committee is not in the core: Let Sbe the coalition of all 14 voters
who approve multiple parties, and let Tallocate 4 seats to p0and 5 seats each to p1
and p3. This gives strictly higher representation to all members of the coalition.
The example makes it obvious why majoritarian portioning cannot satisfy core sta-
bility: All voters approving of p0get deactivated after the first round, which makes
123
M. Brill et al.
p2seem universally preferable to p1. However, p1is a useful vehicle for coopera-
tion between the group approving {p0,p1}and the group approving {p1,p2}. Since
majoritarian portioning is blind to this opportunity, it cannot guarantee core stability.
The example also illustrates the power of core stability: The deviating coalition
does not agree on any single party they support, but would nonetheless benefit from
the deviation. Core stability is sensitive to this demand for better representation.
5 Computational aspects
To use a voting rule, we need to compute its output. Ideally, we would like an efficient
(i.e., polynomial-time) algorithm for this task, so that we can announce the voting
outcome soon after all votes have been cast. Fortunately, many rules admit fast algo-
rithms. For example, the composed rules from Sect. 4.3 can be computed efficiently as
long as the employed portioning and apportionment methods are computable in poly-
nomial time (which is the case for majoritarian portioning as well as for D’Hondt and
the quota method). In addition, by our discussion in Remark 3.1, every multiwinner
voting rule that runs in polynomial time for the candidate-approval setting also runs
in polynomial time for the party-approval setting.
That being said, given our result about core stability in Sect. 3, we are particularly
interested in computing the outcome of PAV, which is NP-hard to compute in the
candidate-approval setting [2]. Since party-approval elections are a restricted domain,
it is in principle possible that PAV is easier to compute on that domain, but, as we
show in Appendix A, hardness still holds for party-approval elections.
Theorem 5.1 For a given party-approval election and threshold s ∈R, deciding
whether there exists a committee with PAV score at least s is NP-hard.
Equally confronted with the computational complexity of PAV, Aziz et al. [4]pro-
posed a local-search variant of PAV, which runs in polynomial time and guarantees EJR
in the candidate-approval setting. Using the same approach, we can find a core-stable
committee in the party-approval setting.
Theorem 5.2 Given a party-approval election, a core-stable committee can be
computed in polynomial time.
We defer the proof of this theorem to Appendix A. In Appendix B.1, we additionally
show that an optimization variant of Phragmén’s rule [17] remains intractable in the
party-approval subdomain.
Lackner and Skowron [39] posed as an open problem to determine the complexity of
checking whether a given committee satisfies core stability. We show that the problem
is coNP-complete. Our proof is written for party-approval elections, but the result
implies hardness for the candidate-approval setting because party-approval elections
are a special case of candidate-approval elections.
Theorem 5.3 For a given party-approval (or candidate-approval) election and a
committee W, it is coNP-complete to decide whether W satisfies core stability.
123
Approval-Based apportionment
Proof The complement problem is clearly in NP since a core deviation provides a
certificate. We reduce from the NP-complete problem exact cover by 3-sets (X3C).
Here, given a set Xwith |X|=3rand a collection Bof 3-element subsets of X,the
question is whether there exists a selection B⊆Bof rof the subsets such that every
element of Xoccurs in one of the sets in B.
We construct an instance of our problem as follows: For every set B∈Bwe
introduce a set candidate and for every element in Xwe introduce an element voter.
We set k=rand introduce one special voter,k−1private candidates and one dummy
candidate. The approval sets are as follows: Each element voter x∈Xapproves
exactly those set candidates B∈Bwith x∈Band the special voter approves
all candidates except the dummy candidate. (Thus, no voter approves the dummy
candidate.) Finally, let Wbe the committee consisting of the private candidates and
the dummy candidate.8Note that |W|=k. We claim that Wis not core stable if and
only if the X3C instance is a yes instance.
Suppose that Wis not core stable, and let S⊆Nand committee T:P→N
witness this fact. Without loss of generality, we may assume that Tonly gives seats
to set candidates, since all other candidates are dominated by set candidates. Suppose
|T|=t. Then Tprovides positive utility to at most 3telement voters. These 3tvoters
on their own can afford 3t·k/n≤3t·k/(3k+1)<tcandidates. Because all
element voters in Smust obtain positive utility from T, it follows that the special
voter must be part of S. Because the special voter ihas ui(T)>ui(W)=k−1, we
have ui(T)=k. Thus |T|=k, and a committee of this size can only be afforded
by the grand coalition, so S=N. Thus, every element voter is part of Sand thus
obtains positive utility from T, and hence for every element, Tcontains at least one
set candidate corresponding to a set containing that element. It follows that the X3C
instance has a solution.
Conversely, every solution to the X3C instance induces a committee Tconsisting of
the kset candidates chosen by the solution. Then Tgives positive utility to all element
voters and increases the special voter’s utility from k−1tok. Hence Ttogether with
S=Nshow that Wis not core stable.
In the candidate-approval setting, checking whether a given committee satisfies EJR
is coNP-complete [3,4]. In other words, given a committee, it is hard to find a cohesive
coalition of voters that is underrepresented. Interestingly, this task is tractable in party-
approval elections. Intuitively, checking becomes easier in party-approval elections as
groups of voters are already cohesive when they have only a single approved party in
common.
Theorem 5.4 Given a party-approval election (N,P,A,k)and a committee W :
P→N, it can be checked in polynomial time whether W satisfies EJR.
Proof We describe a procedure to check whether a given committee Wviolates EJR.
For each party p∈Pand each ∈[k], define
Sp, ={i∈N|p∈Aiand ui(W)≤}
8The committee Wassigns seats only to Pareto-dominated parties, making it clearly suboptimal. One can
adjust the reduction to show that the problem remains hard for committees Wthat do not give seats to
Pareto-dominated parties.
123
M. Brill et al.
and check whether <q(Sp,)holds. If so, the set Sp, induces an EJR violation.
This is because i∈Sp, Ai=∅and ui(W)≤<q(Sp,)holds for all i∈Sp,.
Now, assume that the condition is not satisfied for any party p∈Pand any
∈[k]. We claim that this proves the nonexistence of an EJR violation. Assume
for contradiction that there exists a group S⊆Ninducing an EJR violation. Let
p∈i∈SAiand =maxi∈Sui(W). By definition, S⊆Sp, and hence q(Sp,)≥
q(S)>, a contradiction. A straightforward implementation of this algorithm has
polynomial running time O(|P|kn).
We observe a similar effect for proportional justified representation (PJR), a pro-
portionality axiom introduced by [51] which is weaker than EJR. While checking
whether a committee satisfies PJR is coNP-complete in the candidate-approval set-
ting, we can solve the problem in polynomial time via submodular minimization in
our setting. For a formal definition and the proof, see Appendix A.3.
6 Discussion
In this paper, we have initiated the axiomatic analysis of approval-based apportion-
ment. On a technical level, it would be interesting to see whether the party-approval
domain allows us to satisfy other combinations of axioms that are not known to be
attainable in candidate-approval elections. For instance, the compatibility between
strong representation axioms and certain notions of support monotonicity is an open
problem [49].
We have presented our setting guided by the application of apportioning parliamen-
tary seats to political parties. But our formal setting has other interesting applications.
An example would be participatory budgeting settings where items all have equal costs
and come in different types. For instance, a university department could decide how
to allocate Ph.D. scholarships across different research projects, in a way that respects
the preferences of funding organizations.
As another example, the literature on multiwinner elections suggests many appli-
cations to recommendation problems [54]. For instance, one might want to display a
limited number of news articles, movies, or advertisements in a way that fairly repre-
sents the preferences of the audience. These preferences might be expressed not over
individual pieces of content, but over content producers (such as newspapers, stu-
dios, or advertising companies), in which case our setting provides rules that decide
how many items should be contributed by each source. Expressing preferences on the
level of content producers is natural in repeated settings, where the relevant pieces of
content change too frequently to elicit voter preferences on each occasion. Besides,
content producers might reserve the right to choose which of their content should be
displayed.
In the general candidate-approval setting, the search continues for rules that satisfy
EJR and committee monotonicity, or core stability. But for the applications mentioned
above, these guarantees are already achievable today.
123
Approval-Based apportionment
Acknowledgements We thank Steven Brams and Piotr Skowron for suggesting the setting of party approval
to us, and we thank Rupert Freeman, Levi Geiser, Anne-Marie George, Ayumi Igarashi, Svante Janson,
Jérôme Lang, Ariel Procaccia, and the anonymous reviewers for helpful comments and discussions.
Funding Open Access funding enabled and organized by Projekt DEAL. This work was partially supported
by the Deutsche Forschungsgemeinschaft under grant BR 4744/2-1.
Open Access This articleis licensedundera CreativeCommonsAttribution4.0InternationalLicense, which
permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give
appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence,
and indicate if changes were made. The images or other third party material in this article are included
in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If
material is not included in the article’s Creative Commons licence and your intended use is not permitted
by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the
copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
A Omitted proofs
A.1 Proof of Theorem 5.1
We show NP-hardness by reduction from the NP-complete problem Independent
Set [29].
Independent Set
Input: Undirected graph G=(V,E),t∈N.
Question: Is there a vertex subset V⊆Vof size |V|=tsuch that no two
vertices in Vare connected by an edge in G?
This problem is NP-hard even when restricted to cubic graphs (where every vertex
has degree 3) [29]. Our reduction is a simplified version of the reduction proposed by
Aziz et al. [2, Theorem 1].
Theorem 5.1 For a given party-approval election and threshold s ∈R, deciding
whether there exists a committee with PAV score at least s is NP-hard.
Proof For a given cubic graph G=(V,E)and independent set size t∈[|V|],we
construct a party-approval election (N,P,A,k)in the following. For each vertex
v∈V, there is a party pv∈P. For every edge e={u,v}∈E, there is one voter in
Nwho approves exactly puand pv.Lastly,wesetk=t.
This construction is clearly polynomial in the size of G. We show that Ghas an
independent set of size tiff there is a committee Wfor the election (N,P,A,k)with
PAV(W)≥s=3t.
“⇒”: Assume that Ghas an independent set V⊆Vof size |V|=t. Consider
the committee Wwhere for every vertex v∈V, the party pvreceives exactly one
seat (thus, the committee has size k=t). Each party pvis approved by three voters,
namely all those voters corresponding to edges that are incident to v. Because Vis
an independent set, no voter approves more than one party in the committee, and thus
only has a single seat on the committee belonging to an approved party. Consequently,
the total PAV score of Wis exactly 3t.
“⇐”: Assume that Wis a committee with PAV(W)≥3tfor the constructed
election. The PAV score of a given committee can be computed by starting with the
123
M. Brill et al.
empty committee and then iteratively adding up the marginal PAV score of each seat
within the committee. Every party pvis approved by exactly three voters and therefore,
giving one seat to pvin the committee can increase the PAV score by at most three. As
there are only tseats available, every seat assignment has to increase the PAV score by
exactly three. In order to achieve an increase of three when adding a seat to pv, all the
voters who approve pvmust have been previously completely unrepresented. Thus,
all parties present in Wreceive only one seat and do not have any common approving
voters. By construction, this implies that the set of vertices {v∈V:W(pv)>0}
corresponding to Wis an independent set of size t.
A.2 Proof of Theorem 5.2
In the following we prove that in the party-approval subdomain, core-stable commit-
tees can be computed in polynomial time. We make use of a local search procedure
(LS-PAV), introduced for the candidate-approval setting by Aziz et al. [4], which
approximatesa localmaximum of the PAV scorefunction. Aziz et al. [4]showthat their
algorithm runs in polynomial time and returns committees providing EJR. For party-
approval elections, we show that, by a minor adjustment of the algorithm, committees
computed by LS-PAV satisfy core stability. In Algorithm 1we slightly adjust the
original definition by parameterizing the procedure by the approximation threshold .
Note that, once again, the algorithm is defined in terms of candidate-approval elec-
tions; in Sect. 3.2 we show how to apply candidate-approval rules to party-approval
elections.
Algorithm 1 LS-PAV (Candidate-Approval Rule)
function LS- PAV(N,C,A,k,)
W←karbitrary candidates from C
while ∃c∈W,c∈C\Wsuch that PAV(W\{c}∪{c})≥PAV(W)+do
W←W\{c}∪{c}
end while
return W
end function
Theorem 5.2 Given a party-approval election, a core-stable committee can be
computed in polynomial time.
Proof We claim that LS-PAV with threshold =n
k(k+1)selects a core stable com-
mittee and can be computed in polynomial time. Assume for contradiction that W1
is a committee returned by LS-PAV which violates core stability. Then, by the same
argumentation as in the proof Theorem 3.2, there exists a committee W3such that
PAV(W3)≥PAV(W1)+n
k−n
k+1=PAV(W1)+,
which is a contradiction to the selection of W1by LS-PAV.
123
Approval-Based apportionment
Aziz et al. [4] showed that LS-PAV runs in polynomial time for =n
k2.Observing
that ∈Ω()and following their proof, it is easy to see that LS-PAV for runs in
polynomial time as well.
A.3 Checking PJR
We start by defining proportional justified representation (PJR) for party-approval
elections.
Definition A.1 A committee W:P→Nprovides proportional justified repre-
sentation (PJR),ifthereisnoS⊆Nsuch that i∈SAi=∅and p∈i∈SAi
W(p)<q(S).
Inwords,PJRrequiresthat for everyvotergroup Swith acommonlyapprovedparty,
the committee should contain at least q(S)candidates from the union of all parties
approved by voters in S. Observe that a committee providing EJR also provides PJR.
We use techniques from submodular optimization in order to check in polynomial
time whether a given committee satisfies PJR. Recall that, given a finite set U,a
function f:2U→Ris submodular if for all subsets X,Y⊆Uwith X⊆Yand for
every x∈U\Y, it holds that
f(X∪{x})−f(X)≥f(Y∪{x})−f(Y).
A submodular function f:2U→Zcan be minimized in time polynomial in |U|+
log max{| f(S)|:S⊆U}[38, Theorem 14.19]. Applying this result, one can check
whether a party-approval committee provides PJR in polynomial time.
Theorem A.2 Given a party-approval election (N,P,A,k)and a committee W :
P→N, it can be checked in polynomial time whether W satisfies PJR.
Proof We fix a committee W:P→Nand define the function h:2N→Nby
h(S)=
p∈i∈SAi
W(p),
i.e., for a voter group S⊆N,h(S)is the total number of seats that Wallocates to
to the union of all parties approved by voters in S. Moreover, for each party p∈P,
we let Np={i∈N|p∈Ai}denote the set of supporters of p. Observe that the
committee Wsatisfies PJR if and only if there is no party p∈Pand group of voters
S⊆Npwith h(S)<q(S).
We show how to check in polynomial time for a fixed party p∈P, whether there
exists such a group of voters S⊆Np. Then, this procedure can be repeated for every
party in P.
We define the function f:2Np→Rby
f(S)=h(S)−|S|k
n
123
M. Brill et al.
and show that fis submodular. To this end let X,Y⊆Npwith X⊆Yand
x∈Np\Y. Then,
f(X∪{x})−f(X)=
p∈Ax
W(p)−
p∈Ax∩(i∈XAi)
W(p)−k
n
≥
p∈Ax
W(p)−
p∈Ax∩(i∈YAi)
W(p)−k
n
=f(Y∪{x})−f(Y),
which suffices to prove the submodularity of f.
By multiplying fby n, we obtain an integer-valued submodular function with
max{n·|f(S)|:S⊆Np}≤kn; thus, we can minimize fin time O(n+log(kn)).
We show in the following that any S⊆Npis the witness of a PJR violation if and
only if f(S)≤−1.
For the direction from left to right, assume that S⊆Npshows a violation of
PJR, i.e., h(S)<q(S). Since both values are integers, we know in particular that
h(S)≤q(S)−1=|S|k
n−1≤|S|k
n−1 holds. This implies f(S)≤−1.
For the direction from right to left, fix some S⊆Npwith f(S)≤−1. It follows
that h(S)≤|S|k
n−1<q(S), a violation of PJR for the group S.
The above observation implies a natural procedure to check for a PJR violating
group within the supporters of some party p: Minimize the function fand check
whether its minimum is larger than −1. If not, we have found a violation. If the
minimum of fis larger than −1 for all p∈P, then Wsatisfies PJR. The described
algorithm runs in time O|P|(n+log(kn)).
B Results on further multiwinner voting rules
In this section we consider other approval-based multiwinner voting rules from the
literature and study their axiomatic properties in the party-approval subdomain. Note
that we use the language of the candidate-approval setting and in particular, Wis a
set (not a multiset) of candidates. In order to apply the described rules in the party-
approval setting, we can transform any party-approval election to a candidate-approval
election by introducing kclones of each party (see Sect. 3.2).
We focus on five rules that satisfy PJR in the candidate-approval setting, and briefly
comment on rules not satisfying PJR in Appendix B.4. For all five rules, we show that
they do not satisfy stronger proportionality axioms in the party-approval subdomain;
see Table 1 for a summary of our observations. Furthermore, we show that leximax-
Phragmén remains computationally intractable when restricting the domain to party-
approval elections.
123
Approval-Based apportionment
B.1 Phragmén’s rules
The first three rules we consider are (at least partially) due to Swedish mathematician
Lars Edvard Phragmén.9The first two rules, leximax-Phragmén and seq-Phragmén,
are based on the concept of load distributions: It is assumed that adding a candidate
to the committee incurs one unit of “load,” which needs to be distributed among the
approversofthiscandidate. The rulesaimto select committeesforwhichthe associated
load can be distributed as evenly as possible among the voters, where the balancedness
of a load distribution is measured by the maximal total load of a voter.
Formally, a real-valued vector (xi,c)i∈N,c∈Cis a load distribution for a candidate-
approval election (N,C,A,k)if the following properties hold [17]:
0≤xi,c≤1fori∈N,c∈C,(B.1)
xi,c=0ifc/∈Ai,(B.2)
i∈N
c∈C
xi,c=k,(B.3)
i∈N
xi,c∈{0,1}for c∈C.(B.4)
In this definition, xi,crepresents the load of candidate cthat is assigned to voter i.The
total load of voter iis given by c∈Cxi,c. Properties (B.3) and (B.4) ensure that each
load distribution corresponds to a committee of size k: candidate cis in the committee
if and only if i∈Nxi,c=1.
The rule leximax-Phragmén (aka max-Phragmén) globally minimizes the balanced-
ness of load distributions and returns committees corresponding to load distributions
(xi,c)such that maxi∈Nc∈Aixi,cis minimal. (Ties are broken in a leximax fashion;
for details, we refer to Brill et al. [17]). In candidate-approval elections, leximax-
Phragmén satisfies EJR and is NP-hard to compute [17]. We first show that the
computational intractability still holds for party-approval elections.
Theorem B.1 Computing a winning committee for leximax-Phragmén is NP-hard in
the party-approval subdomain.
Proof The notion of load distributions can be adapted in a straightforward manner
to party-approval elections, by replacing constraint (B.1) with 0 ≤xi,p≤kand
constraint (B.4) with i∈Nxi,p∈[k]for all p∈P. We prove that the following
problem is NP-hard:
Party Approval leximax- Phragmén
Input: party-approval election (N,¶,A,k), distribution bound s∈R
Question: Is there a load distribution (xi,p)such that maxi∈Np∈Aixi,p≤
s?
Similarly to the proof of Theorem 5.1, we use a polynomial reduction from Inde-
pendent Set on cubic graphs. The reduction is a variant of the one by Brill et al. [17],
which shows that leximax-Phragmén is NP-hard in the candidate-approval setting.
9Phragmén’s original papers are written in French or Swedish [44–47]; an English account of this work
was composed by Janson [32].
123
M. Brill et al.
Given a cubic graph G=(V,E)and independent set size t∈N, we define the
following party-approval election: For every vertex v∈V, there is a party pv∈P.
Additionally, for every edge e={u,v}∈E, there is a voter in Nwho approves
exactly puand pv. The committee shall be as large as the independent set, that is,
k=t. To prove that this reduction is sound, we show that Ghas an independent set of
size tif and only if there is a load distribution (xi,p)with maxi∈Np∈Aixi,p≤1
3.
“⇒”: Assume Ghas an independent set V⊆Vof size |V|=t. Because Gis
cubic, every party in the created election is approved by exactly 3 voters. We define a
valid load distribution, in which every party corresponding to a vertex in Vcreates a
load of 1
3on every approving voter. (This also implies that in the induced committee,
the parties corresponding to Vreceive exactly one seat.) Because Vis an independent
set, no voter receives load from multiple parties, and hence the maximal total load of
every voter is 1
3.
“⇐”: Assume there is a load distribution (xi,p)such that maxi∈Np∈Aixi,p≤1
3.
Since every party is approved by exactly 3 voters, it follows that xi,p=1
3for a voter i
who approves a party pthat receives a seat in the induced committee. Consequently,
no party receives more than one seat in the induced committee and no voter approves
more than one party in the committee. Thus, the committee induces the independent
set {v∈V:xi,pv>0forsomei∈N}of size t.
In order to prove that leximax-Phragmén does not satisfy EJR in the party-approval
setting, we use straightforward adaptation of an example by Aziz et al. [3](whichis
also used by Sánchez-Fernández et al. [51] and Brill et al. [17]).
Proposition B.2 leximax-Phragmén does not satisfy EJR for party-approval elections.
Proof Let n=8, k=4, and P={A,B,C,D,X}. The ballot profile is given by
1×{A,X},1×{B,X},1×{C,X},1×{D,X},
1×{A},1×{B},1×{C},1×{D}.
In this election, leximax-Phragmén gives one seat each to the parties A,B,C,Dand
thus achieves a perfectly balanced load distribution. Consider the group consisting of
the four voters approving party X. This group has a quota of 2, but no voter in this
group is represented twice in the leximax-Phragmén committee.
The instance from the proof of Theorem B.2 also shows that the incompatibility
of EJR and proportional representation (PR), a proportionality axiom proposed by
Sánchez-Fernández et al. [51], remains intact in the party-approval subdomain.
The rule seq-Phragmén constructs committee sequentially, starting with the empty
committee and iteratively adding a candidate that increases the maximum voter load
the least. For a formal definition, we again refer to Brill et al. [17]. Seq-Phragmén
does not satisfy EJR in candidate-elections, and the same is true for the party-approval
subdomain.
Proposition B.3 seq-Phragmén fails EJR in party-approval elections.
123
Approval-Based apportionment
Proof Fix a natural number k≥282. We construct a party-approval election with
parties A,B,C,D,E,X. The ballot profile of the n=2kmany voters is as follows:
1×{A,X},1×{B,X},1×{C,X},1×{D,X},
7×{A,B,C,D},(2k−11)×{E}.
We first ignore the voters approving Eand focus on the 11 remaining voters. Initially,
addinga seatto A,B,C,or Dwouldincreasethe maximalvoterload to 1
8,while giving
Xone seat would increase it to 1
4. Without loss of generality, assume Areceives this
seat. Then, giving the next seat to B,C,or Dwould increase the maximal load to
(7
8+1)·1
8=15
64 ;givingittoAwould increase it to 1+1
8=16
64 , and giving the seat to X
would increase it to 1
8+1
4=18
64 . Thus, we can assume Breceives the seat. Analogously,
the next two seats are allocated to Cand D, respectively—the exact computations can
be found in Table 2. The fifth seat would then be allocated again to A, increasing the
maximal voter load to 16473
32768 ≈0.50272.
Taking the voters for Einto account would not affect the computation above,
because all voters who approve Edo not approve any other party. Thus, in every
seq-Phragmén iteration, either Ereceives a seat or one of A,B,C,Dreceives a seat,
until A,B,C,Dall have one seat. Adding a seat to Eincreases the load of a voter
approving Eby 1
2k−11. Thus, if k−4 seats are allocated to E, each E-voter would
have a load of k−4
2k−11. Observe that limk→∞ k−4
2k−11 =1
2and indeed, k−4
2k−11 <0.50272
for all k≥282. Therefore, seq-Phragmén returns a committee where A,B,C,Deach
receive one seat and Ereceives the remaining k−4 seats.
This is a contradiction to EJR: Since n/k=2, EJR demands one of the four voters
approving Xto be represented at least twice in the committee. This is not the case for
the committee selected by seq-Phragmén.
Additionally, Phragmén developedavotingrulewhichadaptsthewell-knownsingle
transferable vote (STV) system to approval ballots. Following Camps et al. [20], we
refer to this method as Eneström-Phragmén. Like seq-Phragmén, this method selects
candidates iteratively. Initially, every voter has weight of 1 and a candidate’s score is
the sum of all approving voters’ weights. In every round, the candidate with the highest
score sis added to the committee. If a voter iwith weight fiapproves the candidate
who is added to the committee, then their weight will be updated to fi·(s−n/k)/s
if s>n/k, and to 0 otherwise. This process is repeated until all kseats are assigned.
The Eneström-Phragmén rule does not satisfy EJR in candidate-approval elections
[20,50], and the same holds for party-approval elections.
Proposition B.4 Eneström-Phragmén fails EJR in party-approval elections.
Proof For k≥18, consider an election with n=120kvoters and k+1 parties
A,X1,...,Xk. The ballot profile is as follows:
120 ×{A,X1},120 ×{A,X2},122 ×{X1,X3},
70 ×{X2,X4},120 ×{X4,X5},121 ×{X5,X6},
123
M. Brill et al.
61 ×{X3},50 ×{X4},65 ×{X6},
109 ×{Xj}for j∈{7,...,15},
110 ×{Xj}for j∈{16,17,18}.
If k>18, we also add 120 voters approving {Xj}for every j∈{19,...,k}.
First, consider the parties A,X1,...,X6only. In Table 3, the Eneström-Phragmén
calculation for an election restricted to these parties is described. Note that in the first 6
iterations, the parties X1,...,X6receive one seat each and all have, when selected as
winners, a score that exceeds 120. Afterwards, every party has a score strictly smaller
than 109.
Furthermore, observe that the parties X7,...,Xkare all approved by voters who
only approve this one particular party. As a result, their scores are not affected when
otherparties receive aseat. The parties X7,...,X15 have a scoreof 109, X16,X17,X18
a score of 110, and X19,...,Xk(if they exist) a score of 120. When any of these parties
receive a seat, their score is decreased to 0, as they are all approved by at most n/k
voters.
Together, this shows that Eneström-Phragmén firstly allots one seat each to
X1,...,X6. Then, the score of the parties A,X1,...,X6is always smaller than 109,
and therefore, X7,...,Xkall receive a seat, which fills the committee. Thus, in the
committee selected by Eneström-Phragmén, X1,...,Xkeach receive one seat. How-
ever, the 240 =2n/kvoters who approve Aform a cohesive group, where at least
one voter should be represented by at least two seats according to EJR. This is not the
case in the committee generated by Eneström-Phragmén.
B.2 Rule X
Rule X (aka Method of Equal Shares) has been proposed by Peters and Skowron [43].
Rule X is similar to seq-Phragmén, but satisfies stronger proportionality guarantees.
In particular, Rule X satisfies EJR, but not core stability [43]. The same holds for the
party-approval setting.
Proposition B.5 Rule X fails core stability in party-approval elections.
Proof Consider again the party-approval election from Example 4.4. In this election,
Rule X gives 8 seats to party p0and 4 seats each to parties p2and p4. As explained
in Example 4.4, this committee is not in the core.
B.3 Maximin support method
The maximin support method (MMS) has been proposed by Sánchez-Fernández et
al. [52]. The method has strong similarities to seq-Phragmén and selects candidates
sequentially. Sánchez-Fernández et al. [52] show that MMS satisfies PJR, but not EJR.
We adapt their EJR counterexample to the party-approval setting.
Proposition B.6 The maximin support method fails EJR in party-approval elections.
123
Approval-Based apportionment
Proof Let n=8, k=4, and P={A,B,C,X}. The ballot profile is given by
5×{A,X},4×{B,X},3×{C,X},
2×{A},1×{B},1×{C}.
In this election, MMS gives one seat each to the parties A,B,C,X. Consider the
group consisting of the 12 voters approving party X. This group has a quota of 3, but
no voter in this group is represented three times in the leximax-Phragmén committee.
B.4 Other rules
We also considered several other rules from the literature that are known to violate
PJR in the candidate setting: sequential PAV and reverse sequential PAV [32,56], sat-
isfaction approval voting [11], minimax approval voting [12], var-Phragmén [17],
GreedyMonroeAV [51], Approval Voting, MonroeAV, GreedyAV, HareAV, and
Chamberlin–CourantAV (for definitions of the latter five rules, we refer to the article
by Aziz et al. [3]). For each of these rules, we verified that they do not satisfy PJR
in the party-approval subdomain either. Since existing counterexamples can be easily
adjusted to the party-approval setting, we omit the details.
References
1. Alós-Ferrer, C.: A simple characterization of approval voting. Soc. Choice Welfare 27(3), 621–625
(2006)
2. Aziz, H., Gaspers, S., Gudmundsson, J., Mackenzie, S., Mattei, N., Walsh, T.: Computational aspects
of multi-winner approval voting. In: Proceedings of the 14th International Conference on Autonomous
Agents and Multiagent Systems (AAMAS), pp. 107–115. IFAAMAS (2015)
3. Aziz, H., Brill, M., Conitzer, V., Elkind, E., Freeman, R., Walsh, T.: Justified representation in approval-
based committee voting. Soc. Choice Welfare 48(2), 461–485 (2017)
4. Aziz, H., Elkind, E., Huang, S., Lackner, M., Sánchez-Fernández, L., Skowron, P.: On the complexity
of extended and proportional justified representation. In: Proceedings of the 32nd AAAI Conference
on Artificial Intelligence (AAAI), pp. 902–909. AAAI Press (2018)
5. Aziz, H., Bogomolnaia, A., Moulin, H.: Fair mixing: The case of dichotomous preferences. In:
Proceedings of the 2019 ACM Conference on Economics and Computation (EC), pp. 753–781 (2019)
6. Balinski, M.L., Young, H.P.: The quota method of apportionment. Am. Math. Mon. 82(7), 701–730
(1975)
7. Balinski, M.L., Young, H.P.: Fair Representation: Meeting the Ideal of One Man, One Vote. Yale
University Press (1982)
8. Barberà, S., Coelho, D.: How to choose a non-controversial list with knames. Soc. Choice Welfare
31(1), 79–96 (2008)
9. Bogomolnaia, A., Moulin, H., Stong, R.: Collective choice under dichotomous preferences. Journal of
Economic Theory 122(2), 165–184 (2005)
10. Brams, S.J., Fishburn, P.C.: Approval Voting, 2nd edn. Springer-Verlag (2007)
11. Brams, S.J., Kilgour, D.M.: Satisfaction approval voting. In: Voting Power and Procedures, Studies in
Choice and Welfare, pp. 323–346. Springer (2014)
12. Brams,S.J.,Kilgour,D.M.,Sanver,M.R.: A minimax procedure for electing committees. PublicChoice
132, 401–420 (2007)
13. Brams, S.J., Kilgour, D.M., Potthoff, R.F.: Multiwinner approval voting: an apportionment approach.
Public Choice 178(1–2), 67–93 (2019)
123
M. Brill et al.
14. Brandl, F., Peters, D.: Approval voting under dichotomous preferences: A catalogue of characteriza-
tions. 2021. Working Paper
15. Brandl, F., Brandt, F., Peters, D., Stricker, C.: Distribution rules under dichotomous preferences: Two
out of three ain’t bad. In: Proceedings of the 22nd ACM Conference on Economics and Computation
(EC), pp. 158–179 (2021)
16. Brill, M.: From computational social choice to digital democracy. In: Proceedings of the 30th Interna-
tional Joint Conference on Artificial Intelligence (IJCAI) Early Career Spotlight Track, pp. 4937–4939.
IJCAI (2021)
17. Brill,M.,Freeman,R., Janson,S.,Lackner,M.:Phragmén’svotingmethodsand justifiedrepresentation.
In: Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI), pp. 406–413. AAAI
Press (2017)
18. Brill, M., Laslier, J.-F., Skowron, P.: Multiwinner approval rules as apportionment methods. J. Theor.
Polit. 30(3), 358–382 (2018)
19. Brill, M., Gölz, P., Peters, D., Schmidt-Kraepelin, U., Wilker, K.: Approval-based apportionment. In:
Proceedings of the 34th AAAI Conference on Artificial Intelligence (AAAI), pp. 1854–1861. AAAI
Press (2020)
20. R.Camps, X.Mora, andL. Saumell.Themethod ofEneström andPhragmén forparliamentaryelections
by means of approval voting. Technical report, arXiv:1907.10590 [econ.TH], (2019)
21. Cheng, Y., Jiang, Z., Munagala, K., Wang, K.: Group Fairness in Committee Selection. In: Proceedings
of the 2019 ACM Conference on Economics and Computation (EC), pp. 263–279 (2019)
22. Droop, H.R.: On methods of electing representatives. J. Stat. Soc. Lond. 44(2), 141–202 (1881)
23. Duddy, C.: Fair sharing under dichotomous preferences. Math. Soc. Sci. 73, 1–5 (2015)
24. Elkind, E., Faliszewski, P., Skowron, P., Slinko, A.: Properties of multiwinner voting rules. Soc. Choice
Welfare 48, 599–632 (2017)
25. Fain, B., Goel, A., Munagala, K.: The core of the participatory budgeting problem. In: Proceedings of
the 12th International Conference on Web and Internet Economics (WINE), Lecture Notes in Computer
Science (LNCS), pp. 384–399 (2016)
26. Fain, B., Munagala, K., Shah, N.: Fair allocation of indivisible public goods. In: Proceedings of the
2018 ACM Conference on Economics and Computation (EC), pp. 575–592 (2018)
27. Fishburn, P.C.: Axioms for approval voting: Direct proof. Journal of Economic Theory 19(1), 180–185
(1978)
28. Fishburn, P.C.: Symmetric and consistent aggregation with dichotomous voting. In: Laffont, J.J. (ed.)
Aggregation and Revelation of Preferences. North-Holland (1979)
29. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness.
W. H. Freeman (1979)
30. Guerdjikova, A., Nehring, K.: Weighing experts, weighing sources: The diversity value. Mimeo (2014)
31. Israel, J., Brill, M.: Dynamic proportional rankings. In: Proceedings of the 30th International Joint
Conference on Artificial Intelligence (IJCAI), pp. 261–267. IJCAI (2021)
32. Janson, S.: Phragmén’s and Thiele’s election methods. Technical report, arXiv:1611.08826 [math.HO],
(2016)
33. Janson, S.: Thresholds quantifying proportionality criteria for election methods. Technical report,
arXiv:1810.06377 [cs.GT], (2018)
34. Janson, S., Öberg, A.: A piecewise contractive dynamical system and Phragmén’s election method.
Bull. Soc. Math. France 147(3), 395–441 (2019)
35. Jiang, Z., Munagala, K., Wang, K.: Approximately stable committee selection. In: Proceedings of the
52nd Annual ACM SIGACT Symposium on Theory of Computing (STOC), pp. 463–472 (2020)
36. Kaneko, M., Nakamura, K.: The Nash social welfare function. Econometrica 47(2), 423–435 (1979)
37. Kilgour, D.M., Marshall, E.: Approval balloting for fixed-size committees. In: Electoral Systems,
Studies in Choice and Welfare, pp. 305–326. Springer (2012)
38. Korte, B., Vygen, J.: Combinatorial Optimization, 6th edn. Springer (2018)
39. Lackner, M., Skowron, P.: Multi-winner voting with approval preferences. Technical report,
arXiv:2007.01795v3 [cs.GT] (2021)
40. Laslier, J.-F., Sanver, M.R.: (eds.) Handbook on Approval Voting. Studies in Choice and Welfare.
Springer-Verlag (2010)
41. Mora, X., Oliver, M.: Eleccions mitjançant el vot d’aprovació. El mètode de Phragmén i algunes
variants. Butl. Soc. Catalana Mat. 30(1), 57–101 (2015)
42. Nash, J.F.: The bargaining problem. Econometrica 18(2), 155–162 (1950)
123
Approval-Based apportionment
43. Peters, D., Skowron, P.: Proportionality and the limits of welfarism. In: Proceedings of the 21st
ACM Conference on Economics and Computation (EC), pp. 793–794. ACM Press, 2020. Full version
arXiv:1911.11747 [cs.GT]
44. Phragmén, E.: Sur une méthode nouvelle pour réaliser, dans les élections, la représentation propor-
tionnelle des partis. Öfversigt af Kongliga Vetenskaps-Akademiens Förhandlingar 51(3), 133–137
(1894)
45. Phragmén, E.: Proportionella val. En valteknisk studie. Svenska spörsmål 25. Lars Hökersbergs förlag,
Stockholm (1895)
46. Phragmén, E.: Sur la théorie des élections multiples. Öfversigt af Kongliga Vetenskaps-Akademiens
Förhandlingar 53, 181–191 (1896)
47. Phragmén, E.: Till frågan om en proportionell valmetod. Statsvetenskaplig Tidskrift 2(2), 297–305
(1899)
48. Pukelsheim, F.: Proportional Representation: Apportionment Methods and Their Applications.
Springer (2014)
49. Sánchez-Fernández, L., Fisteus, J.A.: Monotonicity axioms in approval-based multi-winner voting
rules. In: Proceedings of the 18th International Conference on Autonomous Agents and Multiagent
Systems (AAMAS), pp. 485–493 (2019)
50. Sánchez-Fernández, L., Elkind, E., Lackner, M.: Committees providing EJR can be computed
efficiently. Technical report, arXiv:1704.00356v3 [cs.GT] (2017)
51. Sánchez-Fernández, L., Elkind, E., Lackner, M., Fernández, N., Fisteus, J.A., Basanta Val, P., Skowron,
P.: Proportional justified representation. In: Proceedings of the 31st AAAI Conference on Artificial
Intelligence (AAAI), pp. 670–676. AAAI Press (2017)
52. Sánchez-Fernández,L.,Fernández, N., Fisteus, J.A., Brill, M.: The maximinsupportmethod: An exten-
sion of the D’Hondt method to approval-based multiwinner elections. Mathematical Programming,
2022. Forthcoming
53. Skowron, P., Lackner, M., Brill, M., Peters, D., Elkind, E.: Proportional rankings. In: Proceedings of
the 26th International Joint Conference on Artificial Intelligence (IJCAI), pp. 409–415. IJCAI (2017)
54. Skowron, P.K., Faliszewski, P., Lang, J.: Finding a collective set of items: From proportional
multirepresentation to group recommendation. Artif. Intell. 241, 191–216 (2016)
55. Speroni di Fenizio, P., Gewurz, D.A.: The space of all proportional voting systems and the most
majoritarian among them. Soc. Choice Welfare 52(4), 663–683 (2019)
56. Thiele, T.N.: Om flerfold valg. Oversigt over det Kongelige Danske Videnskabernes Selskabs
Fordhandlinger (1895)
Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps
and institutional affiliations.
123
