Mathematical Programming
https://doi.org/10.1007/s10107-023-01926-8
FULL LENGTH PAPER
Series B
Phragmén’s voting methods and justified representation
Markus Brill1,2 ·Rupert Freeman3·Svante Janson4·Martin Lackner5
Received: 31 January 2021 / Accepted: 12 January 2023
© The Author(s) 2023
Abstract
In the late 19th century, Swedish mathematician Edvard Phragmén proposed a load-
balancing approach for selecting committees based on approval ballots. We consider
three committee voting rules resulting from this approach: two optimization variants—
one minimizing the maximum load and one minimizing the variance of loads—and
a sequential variant. We study Phragmén’s methods from an axiomatic point of view,
focusingonpropertiescapturingproportionalrepresentation.Weshowthatthesequen-
tial variant satisfies proportional justified representation, which is a rare property
for committee monotonic methods. Moreover, we show that the optimization vari-
ants satisfy perfect representation. We also analyze the computational complexity of
Phragmén’s methods and provide mixed-integer programming based algorithms for
computing them.
Mathematics Subject Classification 91B14
A preliminary version of this paper has appeared in the Proceedings of the 31st AAAI Conference on
Artificial Intelligence [12].
BMarkus Brill
Rupert Freeman
Svante Janson
Martin Lackner
1TU Berlin, Berlin, Germany
2University of Warwick, Coventry, UK
3University of Virginia, Charlottesville, VA, USA
4Uppsala University, Uppsala, Sweden
5TU Wien, Vienna, Austria
123
M. Brill et al.
1 Introduction
While most of the social choice literature is focused on single-winner scenarios, recent
years have witnessed an increasing interest in committee voting rules (e.g., [19,21,
31,60]). In this setting, a fixed-size subset of alternatives has to be selected based
on the preferences of a group of voters. In this paper, we assume that the preferences
of individual voters are given by approval ballots, specifying which alternatives are
“approved” by the voters. For an overview of research on approval-based committee
elections, we refer to the recent survey by Lackner and Skowron [31].
A crucial issue in group decision making is (proportional) representation. Infor-
mally speaking, an outcome of a decision-making process is representative if it reflects
the preferences of the members of the group. In the context of approval-based commit-
tee elections, reasoning about representation is non-trivial. Since approval sets may
overlap arbitrarily, there are many different ways in which the set of voters can be
split into more or less “cohesive” subgroups. Whether a given subgroup has a justified
claim to be represented in the committee depends on the size of the subgroup as well
as on its level of cohesiveness.
Aziz et al. [5] and Sánchez-Fernández et al. [56] have identified axiomatic proper-
ties capturing the intuitive notion that subgroups that are “large enough” and “cohesive
enough” deserve to be represented in the committee: justified representation (JR),pro-
portional justified representation (PJR), and extended justified representation (EJR).
While a number of standard committee voting rules have been shown to satisfy the
basic requirement of JR, it turns out that the more demanding properties PJR and EJR
are much harder to satisfy.
In this paper, we consider committee voting rules that are due to Swedish mathe-
matician Edvard Phragmén (we provide brief biographical information in Sect. 1.2).
Phragmén phrases committee elections as load balancing problems: Adding a candi-
date to the committee incurs some load, and this load should be shared among the
voters approving this candidate. Phragmén suggests choosing committees in such a
way that the corresponding load distributions are as balanced as possible, and differ-
ent ways of measuring balancedness result in different optimization objectives. This
approach yields two optimization variants, one minimizing the maximum load and
one minimizing the variance of loads, and one sequential variant, which proceeds by
greedily selecting candidates so as to keep the maximum load as small as possible.
In addition to the load balancing rules, Phragmén also proposed a rule that adapts the
principle behind Single Transferable Vote (STV) to approval ballots.
Although Phragmén’s methods were proposed in the same era as Proportional
Approval Voting (PAV),1they have received hardly any attention until very recently.
Since the publication of the conference version of this paper [12] in 2017, Phragmén’s
methods became increasingly central in the analysis of approval-based committee
rules.2In politics, variants of both Phragmén’s methods and PAV have been used
1Proportional Approval Voting is a prominent committee voting rule due to Danish polymath Thorvald
N. Thiele [64]. For a detailed comparison between PAV and Phragmén’s methods, we refer to the works of
Janson [26] and Peters and Skowron [40].
2Two notable studies that predate the conference version of this paper are a survey by Janson [25](in
Swedish) and a paper by Mora and Oliver [36] (in Catalan).
123
Phragmén’s voting methods and justified representation
in Swedish parliamentary elections (for distribution of seats within parties), and a
version of one of Phragmén’s methods is still part of the election law, although in a
minor role [26]. Further, Phragmén’s sequential method is often used for the selection
of “validators” who participate in a blockchain consensus protocol: In the recently
introduced nominated proof-of-stake (NPoS) mechanism, members of a blockchain
community can nominate other members to become validators, and the selection of a
representativesetofvalidators playsanimportant roleforthe securityofthe blockchain
[15,18,49].
1.1 Results and outline of the paper
After briefly reviewing related work in Sect. 2and introducing some basic notation
in Sect. 3, we formally define Phragmén’s methods in Sect. 4. In Sect. 5, we analyze
the computational complexity of Phragmén’s methods and we provide algorithms for
computing them. The algorithms for the optimization variants are based on mixed-
integer linear and quadratic programming. In Sect. 6, we consider the representation
axioms mentioned above. We show that the sequential variant satisfies PJR, making it
one of few committee monotonic methods with this property. Moreover, we show that
the optimization variants satisfy perfect representation (PR), a further representation
axiomintroduced bySánchez-Fernándezet al.[56].Thelatter resultprovidesacontrast
to PAV, which is known to violate PR. In Sect. 7, we discuss the relation between
Phragmén’s methods and the apportionment problem [8].
1.2 A brief biography of Phragmén
Lars Edvard Phragmén (1863–1937) was a Swedish mathematician, actuary and insur-
ance executive. He began his mathematical university studies in Uppsala in 1882,
but transferred in 1883 to Stockholm, where he became a student (and later con-
fidant) of Gösta Mittag-Leffler [63]. In 1888, Phragmén was appointed coeditor of
Mittag-Leffler’s journal Acta Mathematica, where he immediately made an impor-
tant contribution by finding an error in a paper by Henri Poincaré on the three-body
problem. The paper had been awarded a prize in a competition that Mittag-Leffler had
persuaded King Oscar II to arrange, but Phragmén found a serious mistake when the
journal had already been printed; the copies that had been released were recalled and
a new corrected version was printed.
In 1892, Phragmén became a professor of mathematics at Stockholm University. In
1897, he additionally became an actuary in a private insurance company. His interest
in actuarial science and insurance companies appears to have grown in these years,
as in 1904 he left his professorship to become the first head of the Swedish Insurance
Supervisory Authority. In 1908 he became director of a private insurance company,
which he remained until 1933. His involvement in mathematics is witnessed, e.g., by
his attendance at the 1924 International Mathematical Congress in Toronto, where he
was elected one of the vice-presidents of the International Mathematical Union [16].
Phragmén also continued to be an editor of Acta Mathematica until his death in 1937.
123
M. Brill et al.
Fig. 1 Edvard Phragmén
His best known mathematical work is the Phragmén–Lindelöf principle in complex
analysis, a joint work with Finnish mathematician Ernst Lindelöf [47]. His interest
in election methods is witnessed by his publications [42–46]. Moreover, he was a
member of the Royal Commission on a Proportional Election Method 1902–1903 and
of a new Royal Commission on the Proportional Election Method 1912–1913.For
further information we refer the reader to the survey by Janson [26] and to the book
by Stubhaug [63] (in particular for his relation with Mittag-Leffler).
2 Related work
Proportional representation is an important issue in committee voting (see the influ-
ential paper by Monroe [34] and the references therein) and methods ensuring
representation often lead to interesting computational problems [9,32,50,51].
The problem of choosing representative committees based on approval ballots can
be seen as a generalization of the classical apportionment problem [8]. The latter
setting corresponds to the special case in which candidates are arranged into party lists
and each voter chooses a single list; see Sect. 7for details. Voting settings between
apportionment and approval-based committee voting have also been studied [14].
For the setting of approval-based committee voting [29,31], Aziz et al. [5] proposed
two representation axioms: justified representation (JR) and its strengthening extended
justified representation (EJR). Later, Sánchez-Fernández et al. [56] observed that EJR
is not compatible with what they call perfect representation and proposed an axiomatic
property, proportional justified representation (PJR), that is compatible. EJR implies
PJR, which in turn implies JR.
Aziz et al. [5] and Sánchez-Fernández et al. [56] showed that most common com-
mittee voting rules fail EJR and PJR. A notable exception is Thiele’s PAV [64], which
satisfies EJR (and thus PJR). Interestingly, variants of PAV based on different weight
vectors fail both EJR and PJR (and even weaker proportionality requirements) [5,13].
Moreover, a greedy approximation algorithm for PAV known as sequential PAV or
reweighted approval voting fails JR (and consequently PJR and EJR) [5,56].
123
Phragmén’s voting methods and justified representation
Computing the outcome of PAV is NP-hard [4,60] and thus not feasible in poly-
nomial time unless P =NP. Prior to our work, it had remained an open question
whether there exist polynomial-time computable rules satisfying EJR or PJR. Phrag-
mén’s sequential rule, as we show in this paper, is polynomial-time computable and
satisfies PJR.
Recent work has established that even EJR can be guaranteed by a polynomial-
time voting rule. This was first shown by Aziz et al. [6]. Later, Peters and Skowron
[40] presented the Method of Equal Shares (MES), which is also polynomial-time
computable and satisfies EJR. Interestingly, MES is based on the same principle as
Phragmén’s sequential method and shares some of its desirable properties (such as
laminar proportionality and priceability [40]). None of these rules, however, are com-
mittee monotonic,3i.e., an increase in the committee size by one may result in a
completely different committee. In many settings, committee monotonicity is highly
desirable (e.g., when generating rankings [24,53,61]), and thus Phragmén’s sequential
method—which is committee monotonic by definition—has gained much attention in
recent years. Phragmén’s sequential method also satisfies further monotonicity axioms
[26,54].
The maximin support method, introduced by Sánchez-Fernández et al. [57], is
closely related to Phragmén’s sequential method and shares many of its axiomatic
properties (including PJR and committee monotonicity). The optimization variant
of the maximin support method coincides with one of the optimization variants of
Phragmén’s methods, and yields an equivalent formulation of the latter in terms of
maximin support [57]. An interesting distinction between Phragmén’s sequential rule
and the maximin support method concerns their ability to approximate the optimal
solution of the maximin support problem [18].
Proportional representation has also been studied in settings where voters have
ordinal preferences over candidates [19,21] and in participatory budgeting, a gener-
alization of committee elections where candidates have costs and the set of selected
candidatesneeds to satisfy a budgetconstraint [3,41]. Differentvariantsof Phragmén’s
methods have been generalized to those settings [1,7,26]. Further generalizations of
Phragmén’s methods have been considered in the context of degressive and regressive
proportionality [28] and in the context of perpetual voting [30].
3 Preliminaries
We consider a social choice setting with a finite set N={1,...,n}of voters and a
finite set Cof candidates. Throughout the paper we let m=|C|denote the number of
candidates and n=|N|the number of voters. The preferences of each voter i∈Nare
given by a subset Ai⊆C, representing the subset of candidates that the voter approves
of. We refer to the list A=(A1,...,An)as the preference profile. For a candidate
3A committee voting rule is committee monotonic if increasing the committee size results in a winning
committee that is a superset of the previously winning committee. An example showing that MES violates
committee monotonicity can be found in the survey by Lackner and Skowron [31]. We are not aware of
a formal proof that the rules by Aziz et al. [6] fail committee monotonicity, but the way they are defined
makes this claim very plausible.
123
M. Brill et al.
c∈C,weletNcdenote the set of voters approving c, i.e., Nc={i∈N:c∈Ai}.To
avoid trivialities, we assume that Nc=∅for all c∈C.
We want to select a subset consisting of exactly kcandidates, for a given natural
number k≤m.Anapproval-based committee voting rule (henceforth simply rule)
maps an instance (A,k)to a subset S⊆Cof size k,thecommittee. In general, there
may be ties, and we then allow the rule to yield several choices, so formally the rule
is a map from instances to non-empty sets of committees.
Finally, for a tuple of real numbers z=(z1,...,zn),weletz() denote the -th
largest element in z, so that z(1)≥z(2)≥···≥z(n).
4 Phragmén’s methods
The main idea behind Phragmén’s methods is to identify committees whose “support”
is distributed as evenly as possible among the electorate. Phragmén used different
formulations for explaining his methods; we refer the reader to the survey by Janson
[26] for an overview and more details. In this paper, we adopt the formulation from
the 1899 paper [46]. In this formulation, every candidate in the committee is thought
of as incurring one unit of “load,” and the load incurred by candidate cneeds to be
distributed among the voters in Nc. The goal is to find a committee of size kfor which
the corresponding load distribution is as balanced as possible.
Formally, a load distribution is a two-dimensional array x=(xi,c)i∈N,c∈Csatisfy-
ing the following four constraints:
0≤xi,c≤1 for all i∈Nand c∈C(4.1)
xi,c=0ifc/∈Ai(4.2)
i∈N
c∈C
xi,c=k(4.3)
i∈N
xi,c∈{0,1}for all c∈C(4.4)
Here, xi,ccorresponds to the load that voter ireceives from candidate c. Constraint
(4.2) ensures that the load incurred by candidate cis distributed among voters in Nc
only, and constraints (4.3) and (4.4) ensure that xcorresponds to a size-kcommittee
{c∈C:i∈Nxi,c=1}.
For a load distribution x,welet¯xidenote the total load of voter i∈N, i.e.,
¯xi=c∈Cxi,c, and we refer to (¯x1,..., ¯xn)as the vector of voter loads. Using this
notation, constraint (4.3) reads i∈N¯xi=k. Note that constraint (4.3)impliesthat
the average voter load is k
n.
There are different ways of measuring how balanced a given load distribution is,
each giving rise to a different optimization objective. One such objective is to minimize
the maximum load assigned to a voter, i.e., minxmaxi∈N¯xi. (This is equivalent to
minimizing the maximum difference between a voter load and the average voter load.)
Obviously, the average voter load k
nis a lower bound on the maximum voter load, and
we call a load distribution x perfect if ¯xi=k
nfor all i∈N. Another objective is
123
Phragmén’s voting methods and justified representation
to minimize the variance of voter loads, i.e., the sum of squared distances from the
average voter load. Again, a perfect load distribution is optimal for this objective.
We further distinguish between “optimization” methods, where we solve a global
optimization problem to find a load distribution optimizing the objective, and “sequen-
tial” methods, where we iteratively construct a load distribution, in each round greedily
choosing a candidate optimizing the objective at that iteration.
In this paper, we focus on three rules: the optimization methods leximax-Phragmén
and var-Phragmén—minimizing the maximum voter load and the variance of
voter loads, respectively—and the sequential method seq-Phragmén, which greedily
minimizes the maximum voter load. For completeness, we also consider the Eneström-
Phragmén method (see Sect. 4.3).
The method seq-Phragmén was introduced by Phragmén in several papers [43–
46], and it is the variant that he proposed to be used in actual elections. Phragmén
defined this method as a generalization of D’Hondt’s apportionment method to the case
without party lists (see Sect. 7). Optimization variants and the objective of minimizing
the variance are discussed in the 1896 paper [45].
4.1 Optimization variants
We start by defining the optimization variants. The first optimization variant selects
committees corresponding to load distributions minimizing the maximum voter load.
In case that two or more committees have the same (minimal) maximum load, we
employ a specific way of breaking ties. This is because it might be the case that for
two load distributions xand y, although maxi∈N¯xi=maxi∈N¯yi, one load distribution
is clearly preferable to the other.
Example 4.1 Let C={a,b,c},k=2, and A=({a},{a},{b},{c}). Any committee
of size 2 contains either bor c, which are approved by only one voter each, so the
maximumloadis 1 forallcommittees.However, the committeescontainingarepresent
three voters, while the committee {b,c}only represents two.
In order to refine the set of winning committees, we compare two vectors of voter
loads according to the leximax ordering.4
Definition 4.2 For y=(y1,...,yn)and z=(z1,...,zn),yis leximax-smaller than z,
denoted y˙<z, if there exists j≤nsuch that y(j)<z(j)and y(i)=z(i)for alli≤j−1.
We are now ready to define the first optimization variant.
leximax-Phragmén: The rule leximax-Phragmén selects all committees correspond-
ing to load distributions xsuch that (¯x1,..., ¯xn)is leximax-optimal, i.e., minimal with
respect to ˙<.
As we will see in Sect. 6.3, leximax tie-breaking is necessary in order to guarantee
strong representation properties.
4The leximax ordering is defined analogously to the more commonly used leximin ordering (see, e.g.,
Moulin [37], Definition 1.1). In the literature, the leximax ordering is referred to as “lexicographic minimax”
by Ogryczak [38] and as “lexicographical” by Schmeidler [58].
123
M. Brill et al.
Fig. 2 Illustration of Example 4.3. The diagram on the left illustrates a load distribution minimizing the
maximum voter load maxi∈N¯xi, and the diagram on the right illustrates the unique load distribution
minimizing i∈N¯x2
i
The second optimization variant is based on a different optimization objective.
var-Phragmén: The rule var-Phragmén selects all committees corresponding to load
distributions minimizing i∈N¯x2
i.
Minimizing i∈N¯x2
iindeed minimizes the variance of (¯x1,..., ¯xn), as is well-
known: Since 1
ni∈N¯xi=k
n, it holds that the variance of (¯x1,..., ¯xn)equals
1
n
i∈N¯xi−k
n2
=1
n
i∈N¯x2
i−2¯xi·k
n+k2
n2
=1
n
i∈N
¯x2
i−1
n·2k·k
n+1
n·n·k2
n2
=1
n
i∈N
¯x2
i−k2
n2.
When minimizing this expression, we can ignore multiplicative or additive constants
(nand k) and thus equivalently minimize i∈N¯x2
i.
The following example demonstrates that the maximum voter load under var-
Phragmén may indeed be greater than under leximax-Phragmén.
Example 4.3 Let C={a,b,c,d},k=3, and consider the preference profile
A=({a},{b},{b,c},{a,b,c},{d}). For this instance, leximax-Phragmén selects the
committee {a,b,c}and var-Phragmén selects the committee {a,b,d}. Optimal load
distributions corresponding to these committees are illustrated in Fig. 2. Load dis-
tributions minimizing the maximum voter load (like the one illustrated by the first
diagram in Fig. 2) satisfy maxi∈N¯xi=3
4and i∈N¯x2
i=4(3
4)2=9
4, and the load
distribution minimizing the variance of voter loads (illustrated by the second diagram
in Fig. 2) satisfies maxi∈N¯xi=1 and i∈N¯x2
i=4(1
2)2+12=2.
Remark 4.4 Rather than minimizing the maximum load, one could also aim to max-
imize the minimum voter load. This variant would select committees minimizing the
number of unrepresented voters, even in the face of large cohesive groups of vot-
ers. Therefore, this method will not do well in terms of the representation axioms
considered in Sect. 6. For this reason, we do not consider it further in this paper.
123
Phragmén’s voting methods and justified representation
4.2 Sequential method
We now introduce the sequential method, which can be seen as a greedy algorithm for
minimizing the maximum voter load.
seq-Phragmén: The rule seq-Phragmén starts with an empty committee and iter-
atively adds candidates, always choosing the candidate that minimizes the (new)
maximum voter load (under the assumption that previously assigned loads cannot
be redistributed). Let ¯x(j)
idenote the voter loads after round j. At first, all voters have
a load of 0, i.e., ¯x(0)
i=0 for all i∈N. In each round, we keep the already assigned
loads, but we may further increase them and give the additional load to a new candi-
date c. In other words, we require ¯x(j)
i≥¯x(j−1)
ifor all i, with equality unless i∈Nc.
Moreover, the sum of the loads added in the round should be 1. (Hence, the total load
after jrounds is j, which is the sequential version of constraint (4.3).) We select the
candidate cand the loads ¯x(j)
ithat satisfy these conditions and minimize maxi¯x(j)
i.
(If there are several candidates achieving the minimum, we use a fixed tie-breaking
rule to decide which candidate to add.)
The candidates and loads chosen by this procedure have the following properties.
Lemma 4.5 In round j, given the voter loads ¯x(j−1)
ifor all i ∈N and a candidate c
that was not selected in earlier rounds, let
s(j)
c=1+i∈Nc¯x(j−1)
i
|Nc|.(4.5)
Then, the maximum load s(j)=maxi¯x(j)
iafter round j will be
s(j)=min
cs(j)
c,(4.6)
taking the minimum over the candidates that remain in round j, and a candidate c is
elected that achieves the minimum in (4.6). Moreover, if c is elected, the new loads
after round j will be
¯x(j)
i=s(j)
cif i ∈Nc
¯x(j−1)
iotherwise. (4.7)
Furthermore, both individual loads and the maximum load sequence are weakly
increasing: 0≤¯x(1)
i≤...≤¯x(k)
ifor every i ∈N, and 0≤s(1)≤...≤s(k).
Proof We use induction on j, so we assume that the claims hold for all rounds before j.
We claim first that the following inequalities hold for every remaining candidate cand
for all i∈N:
s(j)
c≥s(j−1)≥¯x(j−1)
i.(4.8)
123
M. Brill et al.
It is obvious that (4.8) holds for j=1. If j>1, then, by the induction hypothesis,
¯x(j−1)
i≥¯x(j−2)
ifor every i. Hence, (4.5) yields s(j)
c≥s(j−1)
cfor every remaining
candidate c. Furthermore, (4.6)(for j−1) yields s(j−1)
c≥s(j−1)for every remaining
candidate c, and thus (4.8) holds in this case too, recalling the definition s(j−1)=
maxi¯x(j−1)
i.
Next, since (4.8) holds, for any remaining candidate c, the assignment (4.7) satisfies
¯x(j)
i≥¯x(j−1)
ifor every i, with equality if i/∈Nc. Moreover, the sum of the added
loads is, by (4.7) and (4.5),
i∈Nc¯x(j)
i−¯x(j−1)
i=|Nc|s(j)
c−
i∈Nc
¯x(j−1)
i=1.(4.9)
Thus, (4.7) yields a valid load distribution for round j.Itfollowsfrom(4.8) that its
maximum load is s(j)
c.
Conversely, any distribution of an additional load 1 on the voters in Ncwill give
these voters an average load of s(j)
c, and thus the maximum load will be at least s(j)
c
(and strictly greater for loads differing from (4.7)).
Hence, the maximum load after round jis minimized by one of the assignments
(4.7), where obviously cshould be chosen to minimize s(j)
c. This proves (4.6), and the
remaining assertions follow.
Note that (4.5)–(4.7) (together with a tie-breaking rule) give a simple polynomial-
time algorithm for computing the outcome of seq-Phragmén: In each round j, compute
s(j)
cfor all remaining candidates c, select a candidate minimizing this quantity (poten-
tiallyusing thetie-breakingrule),and updatevoterloads according to(4.7).Weanalyze
the running time of this algorithm in more detail in Sect. 5.
Phragmén [46] illustrates his sequential method by imagining the different ballots
as represented by cylindrical vessels, with base area proportional to the number of
voters casting that ballot. The already elected candidates are represented by a liquid
that is fixed in the vessels, and the additional unit of load incurred by adding another
candidate to the committee is represented by pouring 1 unit of a liquid into the vessels
representing voters approving this candidate. The liquid then distributes among these
vessels so that the height of the liquid is the same in all vessels. This is to be tried
for each candidate; the candidate that requires the smallest height is elected, and the
corresponding amounts of liquid are added to the vessels and fixed there.
An alternative interpretation of the sequential method is in terms of money: Imagine
that voters have initially empty bank accounts and earn money continuously (at a
constant rate) over time. As soon as the approvers of a candidate jointly own one dollar,
they “buy” this candidate and their bank accounts are reset to zero. This interpretation
wasutilized by Peters and Skowron [40] when introducing the MethodofEqualShares.
Phragmén’s sequentialmethodiscommittee monotonic bydefinition.Asmentioned
above, seq-Phragmén can be seen as a (polynomial-time computable) heuristic to
123
Phragmén’s voting methods and justified representation
Fig. 3 Illustration of Example 4.6. The diagram on the left (respectively, right) illustrates the load distribu-
tions obtained by seq-Phragmén with ties broken in favor of candidate c(respectively, d)
approximate the optimization method leximax-Phragmén. Unsurprisingly, the load
distribution constructed by seq-Phragmén might not be optimally balanced.5
Example 4.6 Consider again the instance from Example 4.3. In the first round, we
have s(1)
b=1
3,s(1)
a=s(1)
c=1
2, and s(1)
d=1. Therefore, candidate bis chosen. In the
second round, we have s(2)
a=2
3,s(2)
c=5
6, and s(2)
d=1, so candidate ais chosen. In
the third round, there is a tie between cand dbecause s(3)
c=s(3)
d=1. Thus, the final
committee is either {a,b,c}or {a,b,d}, depending on which tie-breaking rule is used.
Figure 3illustrates the resulting load distributions, both of which are suboptimal for
the optimization problems corresponding to leximax-Phragmén and var-Phragmén.
One can also define a sequential version of var-Phragmén, by in each iteration
selecting a candidate minimizing the variance of the resulting load distribution [35].
This variant does not fare well in terms of the representation axioms considered in
Sect. 6, and we therefore do not consider it any further.
4.3 Eneström-Phragmén method
In addition to the methods described in the previous sections, there is another rule that
is attributed, at least partially, to Phragmén.6Following Camps et al. [17], we refer to
this method as Eneström-Phragmén.
The method predates the load balancing methods and is similar in spirit to single
transferable vote (STV) methods [65]. It uses a quota q, which is defined either as
the Hare quota qH=n
kor as the Droop quota qD=n
k+1. The choice between
qHand qDdoes not affect the axiomatic performance of the rule with respect to the
properties studied in this paper. While Eneström-Phragmén is indistinguishable from
seq-Phragmén with respect to the representation properties studied in Sect. 6, a crucial
difference is that Eneström-Phragmén is not committee monotonic [17].
Eneström-Phragmén: Initially, all voters have a voting weight of 1. Each ballot is
counted fully, with its present voting weight, for each unelected candidate on the
5The approximability of leximax-Phragmén has recently been studied by Cevallos and Stewart [18], who
showed, in particular, that seq-Phragmén does not offer a constant-factor approximation guarantee.
6For details on the origin of this rule, see footnote 38 in the paper by Janson [26], who refers to this method
as Phragmén’s first method. Sánchez-Fernández et al. [55] refer to the method as Phragmén-STV.
123
M. Brill et al.
ballot. In each round, a candidate with maximum weighted approval score is chosen
and the voting weights of voters approving this candidate are reduced: If the maximum
weighted approval score vis strictly greater than the quota (i.e., v>q), then each
of these ballots has its voting power multiplied by v−q
v;ifv≤q, then these ballots
all get voting power 0 (and are thus ignored in the sequel). This is repeated until the
desired number of candidates are elected.
Note that the total voting weight of all voters is decreased by (q/v) ·v=qeach
time, as long as some candidate reaches the quota. This rule has been extensively
analyzed by Camps et al. [17] (mostly using qD). Independently, it has been studied
by Sánchez-Fernández et al. [55](usingqH). In the following example, we use qH.
Example 4.7 Consider again the instance from Example 4.3.WehaveqH=n
k=5
3.
In the first round, candidate bis chosen with a (weighted) approval score of 3. Since
3>qH, the voting power of the three voters approving bis multiplied by 3−qH
3=4
9.
In the second round, the weighted approval scores of the remaining candidates are
1+4
9=13
9for a,4
9+4
9=8
9for c, and 1 for d. Therefore, candidate ais chosen.
Since 13
9≤qH, both voters approving ahave their voting power reduced to 0. In the
third and final round, the weighted approval score of cis 4
9and candidate dis chosen
with a weighted approval score of 1.
5 Computational aspects
In this section, we study the computational complexity of Phragmén’s methods, and
we provide algorithms for finding winning committees. Sánchez-Fernández et al. [56]
have shown that every rule satisfying perfect representation (see Sect. 6) is NP-hard
to compute; this essentially follows from earlier work by Procaccia et al. [51]. Since
we show that leximax-Phragmén and var-Phragmén both satisfy this condition (Theo-
rems 6.10 and 6.14), it follows that there do not exist polynomial-time algorithms for
computing a committee for either of these rules, unless P =NP.
We complement these hardness results by considering two basic decision prob-
lems. leximax-Phragmén asks whether an instance allows a load distribution x
such that (¯x1,..., ¯xn)˙<(y1,...,yn)for some given n-tuple (y1,...,yn)∈Rn
≥0.
var-Phragmén asks whether an instance allows a load distribution xsuch that
i∈N¯x2
i<αfor some given threshold value α>0. Both problems can be interpreted
as asking whether a given load distribution is optimal. We show that both problems are
NP-complete even for rather restricted instances. For a preference profile A,lets(A)
denote the maximum number of candidates a voter approves, and let d(A)denote the
maximum number of voters that approve a candidate.
Theorem 5.1 The decision problems leximax-Phragmén and var-Phragmén are
NP-complete, even restricted to instances with s(A)=2and d(A)=3.
Proof To show hardness for both problems, we reduce from the NP-complete problem
Independent Set on cubic graphs [22,23], which is defined as follows: given a cubic
graph (V,E)(i.e., a graph such that every vertex has degree 3) and a positive integer k,
is there a set of vertices S⊆Vwith |S|=ksuch that |e∩S|≤1 for all edges e∈E?
123
Phragmén’s voting methods and justified representation
Let E=(e1,...,en). We construct an instance of leximax-Phragmén and var-
Phragmén by identifying candidates with vertices (C=V) and voters with edges,
i.e., A=(e1,...,en). It is easy to see that s(A)=2 and d(A)=3. Without loss
of generality we assume that n≥3kbecause cubic graphs with fewer than 3kedges
cannot have an independent set of size k.7
To prove that leximax-Phragmén is NP-hard, we claim that (V,E)has an
independent set of size kif and only if there exists a load distribution xwith
(¯x1,..., ¯xn)˙<(y1,...,yn), where (y1,...,yn)is the sequence containing 3kentries
of 1
3+1
9kfollowed by zeros. If Sis an independent set, then S, viewed as a committee,
contains candidates that are approved by disjoint sets of (three) voters. Hence, there
are exactly 3kvoters that bear a load of 1
3; all others have load 0. Conversely, let Sbe
a committee such that (¯x1,..., ¯xn)˙<(y1,...,yn). Since candidates are approved by
three voters, if there exists a voter with more than one approved candidate in S, then
the average load (and thus the maximum load) is at least k
3k−1>1
3+1
9k, which con-
tradicts our assumption that (¯x1,..., ¯xn)˙<(y1,...,yn). Hence Sis an independent
set.
To prove that var-Phragmén is NP-hard, we claim that (V,E)has an independent
set of size kif and only if there exists a load distribution xwith i∈N¯x2
i<k
3+1
9.
It is straightforward to see that an independent set Scorresponds to a committee
with i∈N¯x2
i=3k·1
32=k
3. For the other direction, let Sbe a committee with
i∈N¯x2
i<k
3+1
9. Note that at most 3kvoters have approved candidates in the
committee. Let N⊆Nbe such that it contains all voters iwith ¯xi>0. Hence
i∈N¯x2
i=i∈N¯x2
i.Thevalueofi∈N¯x2
iis minimal only if all ¯xi,i∈N,are
equal and we then have i∈N¯x2
i=|N|·(k
|N|)2=k2
|N|.If|N|<3k, we thus
see that i∈N¯x2
i≥k2
3k−1>k
3+1
9. Hence |N|=3kand we can conclude that S
corresponds to an independent set.
It remains to be shown that leximax-Phragmén and var-Phragmén are contained
in NP. This is not immediate as a witness for a Yes-Instance (i.e., a load distribution)
may not have a polynomially-sized bit representation. In other words, the fractions in
the load distribution may have very large numerators and denominators. To resolve
this issue, we encode leximax-Phragmén as a mixed-integer linear program (see
the discussion following this proof). Solving a mixed-integer linear program (i.e., its
corresponding decision problem) is known to be NP-complete [59].8For showing
NP-membership of var-Phragmén, we proceed in a similar fashion: we encode it as
a mixed-integer quadratic program (see Theorem 5.3). NP-membership then follows
from a result by Pia et al. [48].
We now turn to algorithms for computing Phragmén’s methods. First, we show how
the outcome of leximax-Phragmén can be computed with the help of mixed-integer
7To see this, consider a cubic graph with an independent set of size k.Allkvertices in the independent
set have three outgoing edges and these 3kedges must all be distinct, since vertices in an independent set
must not be connected via an edge.
8This result essentially shows that mixed-integer linear programs have solutions of polynomial size.
123
M. Brill et al.
linear programs (MILPs).9We start by formulating a MILP that solves the decision
problem leximax-Phragmén. We are thus given a load vector y=(y1,...,yn)and
ask whether an improvement is possible. Without loss of generality we assume that
y1≥... ≥yn. The general idea is to find an index twhere an improvement over
y=(y1,...,yn)is possible. This requires a new load vector x=(¯x1,..., ¯xn)such
that ¯x(1),..., ¯x(t−1)remain equal to y1,...,yt−1, respectively, and that ¯x(t),..., ¯x(n)
are each less than or equal to yt−for some >0. We thus guess the index tand a
mapping from indices 1,...,t−1tovoters.
We use variables xi,c(for i∈N,c∈C), ei,j(for i,j∈N), si(for i∈N), tj
(for j∈N), and . Recall that ¯xi=c∈Cxi,c. For a given n-tuple y,letP(y)be the
MILP that maximizes under the constraints (4.1)–(4.4) and (5.1)–(5.8).
ei,j∈{0,1}for all i,j∈N(5.1)
si∈{0,1}for all i∈N(5.2)
tj∈{0,1}for all j∈N(5.3)
si+
j∈N
ei,j=1 for all i∈N(5.4)
tj+
i∈N
ei,j≤1 for all j∈N(5.5)
j∈N
tj=1 (5.6)
¯xi−k(1−ei,j)≤yjfor all i,j∈N(5.7)
¯xi−k(2−si−tj)≤yj−for all i,j∈N(5.8)
This MILP can be understood as follows: The variables ei,jencode a partial bijec-
tion πfrom a subset of Nto a subset of N(those indices where no improvement
occurs); the variables siencode the subset S⊆Nwhere πis not defined (those
indices where the loads are less than or equal to yt−); and the variables tjencode
t∈N, an index of an element in {yj:j/∈range(π)}(the index twhere an actual
improvement occurs). Constraint (5.4) encodes the relation between πand S: for every
i∈N, either si=1orei,j=1forsome j∈N. In a similar fashion, constraint
(5.5) encodes the relation between πand t: for every i∈N,ti=1 only if ei,j=0
for all j∈N. Together with constraint (5.6), we enforce that there exists exactly one
j∈Nsuch that tj=1. Hence at least one voter has a load strictly smaller than yt
and (¯x1,..., ¯xn)˙<(y1,...,yn).
The final two constraints ensure that indeed (¯x1,..., ¯xn)˙<(y1,...,yn).From
constraint (5.7) it follows that ¯xi≤yjwhenever π(i)=j. This is because if ei,j=0
(i.e., π(i)= j), constraint (5.7) reduces to ¯xi−k≤yj, which is trivially satisfied
because every load distribution xsatisfies ¯xi≤kfor all i∈N.Ifei,j=1 (i.e.,
π(i)=j), however, constraint (5.7) reads ¯xi≤yj. Similarly, constraint (5.8) enforces
9For a general discussion on lexicographic optimization in MILPs, we refer the reader to a paper by
Ogryczak and Sliwinski [39] and references therein.
123
Phragmén’s voting methods and justified representation
that ¯xi≤yt−≤maxj∈N\range(π) yj−for i∈S. As we maximize , we look
for a solution where ¯xi<maxj∈N\range(π) yj. We conclude that a feasible solution
with objective function value >0 encodes a load distribution xwith (¯x1,..., ¯xn)˙<
(y1,...,yn). Observe that P(y)solves the leximax-Phragmén decision problem:
given voter loads y,P(y)returns >0 if and only if leximax-Phragmén with input
yis a Yes-instance.
We now present a MILP-based algorithm that computes the outcome of leximax-
Phragmén. Our algorithm solves a sequence of at most2ninstantiations of the MILP P,
usingthe optimal solutions of previouslysolvedinstancesasconstraints for subsequent
calls. We assume that Preturns the load distribution xand the objective function value
. For an overview of the procedure, see Algorithm 1.
Algorithm 1: Computing leximax-Phragmén
y←(k,0,...,0)
for =1...ndo
x, ←P(y)
¯x←(¯x1,..., ¯xn)// ¯x(1),..., ¯x() optimal
if =0then // no improvement
x,←P(¯x)
if =0then // ¯xoptimal
return {c∈C:i∈Nxi,c=1}
y←(¯x(1),..., ¯x(+1),0,...,0)
return {c∈C:i∈Nxi,c=1}
We start with y=(k,0,...,0),ann-tuple consisting of one kand n−1 zeros. We
employ Pto find a strictly better solution. The only entry of ythat can be improved
is y(1)=kand hence the solution xreturned by Pminimizes the largest load; let
¯x(1)be the largest load and ¯x(2)the second-largest. We repeat this procedure with
y=(¯x(1),¯x(2),0,...,0). We already know that ¯x(1)is optimal and cannot be further
decreased (and 0 cannot be improved), hence the next Pinstance minimizes the second-
largest load. We iterate this process and in step guarantee that the -th largest load
is optimal. If at some point Preturns =0, we verify whether the current solution is
optimal: if P(¯x)also returns =0, the load distribution xis indeed optimal and the
algorithm terminates. In any case Algorithm 1returns {c∈C:i∈Nxi,c=1},the
committee corresponding to the load distribution x.
We have therefore proven the following result.
Theorem 5.2 leximax-Phragmén can be computed by solving at most 2n mixed-integer
linear programs with O(nm +n2)variables.
To compute var-Phragmén, we solve a mixed-integer quadratic program (MIQP),
i.e., a program consisting of linear constraints and a quadratic optimization statement.
123
M. Brill et al.
Theorem 5.3 var-Phragmén can be computed by solving one mixed-integer quadratic
program with O(nm)variables.
Proof Our MIQP uses the variables xi,c(for i∈N,c∈C) and the constraints
(4.1)–(4.4). The quadratic optimization statement is
min
i∈N
c∈C
xi,c2
.
Since minimizing i∈N¯x2
iminimizes the variance (see Sect. 4.1), this MIQP com-
putes load distributions corresponding to var-Phragmén committees.
Finally, we study the runtime for computing seq-Phragmén. A naive estimate is that
seq-Phragmén can be computed in O(kmn)time. This estimate ignores the cost of
computing the quantities s(j)
c, i.e., numerical operations are assumed to require con-
stant time. While this is a sensible assumption in many cases, here it is questionable
since computing s(j)
cexactly requires fractions with large numerators and denomi-
nators. Indeed, the denominator of s(j)
ccan grow exponentially with j. Hence, the
following theorem also takes the complexity of these operations into account.
Theorem 5.4 The output of seq-Phragmén can be computed in O(k3mn(log n)2)time.
Proof In the following analysis we also consider the complexity of arithmetic oper-
ations in the algorithms, as exact numerical computation of the involved quantities
may require numbers of substantial size. Let us consider the procedure described in
Sect. 4.2. In each of the krounds, one candidate is chosen. For this, the quantity s(j)
c
is computed for every cnot yet placed in the committee. To ensure correct results, we
represent s(j)
cas fractions, i.e., pairs of integers. Let {c1,...,cj−1}be the first j−1
chosen candidates. It is easy to see that the denominator of s(j)
ccan be bounded by
|Nc1|·...·|Ncj−1|·|Nc|≤nj≤nk, assuming we reduce fractions. Furthermore, since
s(j)
c≤k, the numerator of s(j)
cis at most knk. Hence, the space required to store s(j)
c
is bounded by O(klog n). The necessary computations for calculating s(j)
c(addition,
division, reducing fractions) can all be performed in O(b2)time,10 where bis the
number of bits required to store any of s(j−1)
c, and O(n)such operations are required.
Since b=O(klog n), we conclude that s(j)
ccan be computed in O(nk2(log n)2)time.
This has to be done in each of the krounds for at most |C|=mmany candidates
c∈C. The consequent update of ¯x(j)
idoes not increase the runtime bound further.
6 Phragmén’s methods and representation
In this section, we study which representation axioms are satisfied by Phragmén’s
methods. Our results are summarized in Table 1. Particularly noteworthy are the results
10 This quadratic bound is a very rough estimate and does not use any of the more sophisticated methods for
multiplication such as the Schönhage–Strassen algorithm [62] or computing greatest common divisors [11,
33].
123
Phragmén’s voting methods and justified representation
Table 1 Phragmén’s methods and representation axioms
JR PJR EJR PR
seq-Phragmén (Corollary 6.8)(Theorem 6.5)–(Example6.9)–(Example6.3)
leximax-Phragmén (Corollary 6.13)(Theorem 6.11)–(Example6.3)(Theorem 6.10)
var-Phragmén (Theorem 6.16)–(Example6.15)–(Example6.3)(Theorem 6.14)
Eneström-Phragmén [17,55][17,55]–[17,55]–(Example6.3)
that seq-Phragmén satisfies PJR and that leximax-Phragmén and var-Phragmén satisfy
PR. For completeness, the table also contains results obtained by Sánchez-Fernández
et al. [55] and Camps et al. [17] regarding Eneström-Phragmén.
6.1 Representation axioms
We start by stating the definitions of Aziz et al. [5] and Sánchez-Fernández et al. [56].
Definition 6.1 A committee S⊆Cwith |S|=kprovides
–justified representation (JR) if there does not exist a set N∗⊆Nof voters with
|N∗|≥n
k,|i∈N∗Ai|≥1 and |S∩Ai|=0 for all i∈N∗.
–proportional justified representation (PJR) if there does not exist an integer >0
and a set N∗⊆Nof voters with |N∗|≥n
k,|i∈N∗Ai|≥and |S∩
(i∈N∗Ai)|<.
–extended justified representation (EJR) if there does not exist an integer >0 and
asetN∗⊆Nof voters with |N∗|≥n
k,|i∈N∗Ai|≥and |S∩Ai|<for all
i∈N∗.
Arule f satisfies JR (respectively, PJR or EJR) if, for every instance (A,k),every
committee S∈f(A,k)provides JR (respectively, PJR or EJR).
It follows immediately from the definitions that a rule satisfying EJR also satisfies
PJR, and that a rule satisfying PJR also satisfies JR.11
The following definition is due to Sánchez-Fernández et al. [56].
Definition 6.2 Consider an instance (A,k)such that kdivides n=|N|. A committee
S={c1,...,ck}⊆Cprovides perfect representation if there exists a partition of
the set Nof voters into kpairwise disjoint subsets N1,...,Nksuch that, for all j∈
{1,...,k},|Nj|=n
kandcj∈i∈NjAi.LetPR(A,k)denotethesetofallcommittees
providing perfect representation for the instance (A,k).Arule fsatisfies perfect
representation (PR) if, for every instance (A,k)where kdivides nand PR(A,k)=∅,
we have f(A,k)⊆PR(A,k).
The following example, which also appears in the papers by Aziz et al. [5] and
Sánchez-Fernández et al. [56], illustrates the requirements of the different axioms.
11 Aziz et al. [5] have introduced an additional proportionality axiom known as core stability. Since core
stability is more demanding than EJR, the rules considered in this paper do not satisfy core stability.
123
M. Brill et al.
Example 6.3 Let C={a,b,c,d,e,f}and consider the 8-voter preference profile
given by A1={a},A2={b},A3={c},A4={d},A5={a,e,f},A6={b,e,f},
A7={c,e,f},A8={d,e,f}.Letk=4 and assume that ties are broken alpha-
betically. Then, seq-Phragmén chooses e,f,a, and b(in this order). The final loads
are (¯x1,..., ¯x8)=(3
4,3
4,0,0,3
4,3
4,1
2,1
2). This is indeed not optimal as there is a
perfect load distribution ywith ¯yi=1
2for all i∈N. The corresponding committee
{a,b,c,d}is selected by both leximax-Phragmén and var-Phragmén.
Let =2 and consider the voter group N∗={5,6,7,8}of size n
k=28
4=4.
Since the voters in N∗all approve candidates eand f,asetofsize=2, the conditions
for JR, PJR, and EJR all bind. JR requires that at least one candidate approved by at
least one voter in N∗is chosen. PJR requires that at least 2 candidates are chosen that
are each supported by at least one voter from N∗, while EJR requires that some voter
from N∗is represented twice. Thus, EJR dictates that either eor fis chosen. On the
other hand, the only committee providing PR is {a,b,c,d}. As a consequence, no rule
can satisfy both PR and EJR.12 Note that leximax-Phragmén and var-Phragmén both
violate EJR in this example, and that seq-Phragmén violates PR. Eneström-Phragmén
also yields {e,f,a,b}, and thus violates PR.
6.2 Results for seq-Phragmén
In this section we establish our main result: seq-Phragmén satisfies proportional jus-
tified representation.
We use the following notation. For the committee Sthat is selected by seq-
Phragmén (using a fixed tie-breaking rule), we can relabel the candidates so that
S={c1...,ck}and candidate cjwas chosen in round j. Then, we have cj=
arg minc∈C\{c1,...,cj−1}s(j)
c, and the maximum load after round jis s(j)=s(j)
cj.The
following lemma formalizes the intuitively obvious fact that, when computing the
optimal distribution of the load of a candidate camong its voters, it never helps to
restrict attention to a subset N⊂Nc.
Lemma 6.4 Fix an instance (A,k).For j ≤k, a candidate c ∈C that has not been
elected before round j, and a nonempty subset N⊆Nc, let, as a generalization of
(4.5),
s(j)
c[N]=1+i∈N¯x(j−1)
i
|N|.(6.1)
Then s(j)
c[N]is the maximum voter load after optimally distributing an additional
load of 1among all voters in N, on top of the loads ¯x(j−1)
i. In particular, s(j)
c=
s(j)
c[Nc]≤s(j)
c[N]for all N⊆Nc.
Proof That s(j)
c[N]is the maximum voter load after optimally distributing an addi-
tional load 1 among Nfollows by Lemma 4.5 (or its proof) by replacing Ncby N;
the only non-obvious part is that s(j)
c[N]≥ ¯x(j−1)
ifor all i∈N.
12 The incompatibility of PR and EJR was first observed by Sánchez-Fernández et al. [56].
123
Phragmén’s voting methods and justified representation
Since the optimal distribution of the addional load among Nis a possible distri-
bution among the larger set Nc, it is obvious that the optimal distribution among Nc
is at least as good, and thus s(j)
c[Nc]≤s(j)
c[N].
We are now ready to prove our main theorem.
Theorem 6.5 seq-Phragmén satisfies PJR.
Proof PJR requires that |S∩(i∈N∗Ai)|≥for all groups N∗⊆Nof voters
satisfying |N∗|≥n
kand |i∈N∗Ai|≥for some integer >0. We show that seq-
Phragmén satisfies a strictly stronger property by weakening the constraint |N∗|≥n
k
to |N∗|> n
k+1.
Consider an instance (A,k)and let Sbe the committee selected by seq-Phragmén.
Assume for contradiction that there exists a voter group N∗⊆Nand an integer >0
with |N∗|> n
k+1such that |i∈N∗Ai|≥and |S∩(i∈N∗Ai)|≤−1.
Let c∈(i∈N∗Ai)\Sand consider round k(the last round) of the seq-Phragmén
procedure. Adding candidate cto the committee would have caused a maximum voter
load of
s(k)
c=1+i∈Nc¯x(k−1)
i
|Nc|≤1+i∈N∗¯x(k−1)
i
|N∗|
≤1+( −1)
|N∗|=
|N∗|<k+1
n.(6.2)
Here, the first inequality follows from Lemma 6.4 (observe that N∗⊆Nc), the second
inequality follows from |S∩(i∈N∗Ai)|≤−1, and the strict inequality follows
from |N∗|> n
k+1.
Let ckbe the candidate that was chosen in round k. Since candidate cwas not
chosen, we have c= ckand s(k)
ck≤s(k)
c. Using Lemma 4.5 and (6.2), we have
s(k)=s(k)
ck≤s(k)
c<k+1
n. In particular, this implies that at the end of round k,every
voter i∈Nhas a load ¯x(k)
ithat is strictly less than k+1
n. Summing the loads over all
voters, we get
i∈N
¯x(k)
i=
i∈N∗
¯x(k)
i+
i∈N\N∗
¯x(k)
i
≤( −1)+|N\N∗|·s(k)
<−1+n
k+1(k+1−)k+1
n=k,
where we have used the fact that |N\N∗|≤ n
k+1(k+1−).Buti∈N¯x(k)
i<k
is a contradiction, because the sum of all voter loads (at the end of the seq-Phragmén
procedure) must equal k. This completes the proof.
123
M. Brill et al.
Remark 6.6 We note that the proof of Theorem 6.5 shows that seq-Phragmén satisfies
a property that is strictly stronger than PJR, because the constraint on the size of the
group N∗has been relaxed.13
Remark 6.7 In fact, in recent work Peters and Skowron [40] have shown that seq-
Phragmén satisfies a stronger property that they call priceability. This in turn implies
that seq-Phragmén satisfies Inclusion Proportionality for Solid Coalitions (IPSC) [2],
a property that lies between priceability and PJR.14
An immediate corollary of Theorem 6.5 is that seq-Phragmén satisfies JR.
Corollary 6.8 seq-Phragmén satisfies JR.
However, seq-Phragmén violates EJR, as the following example demonstrates.
Example 6.9 Let C={a,b,c1,c2,...,c12},k=12, and consider the following
profile with n=24 voters:
2×{a,b,c1}6×{c1,c2,...,c12}
2×{a,b,c2}5×{c2,c3,...,c12}
9×{c3,c4,...,c12}
seq-Phragmén selects S={c1,c2,...,c12}. (For details of the calculation, see Table 2
in the appendix.) To see that Sdoes not provide EJR, consider the group N∗consisting
of the four voters on the left. We have |N∗|=4=2n
kand |i∈N∗Ai|=|{a,b}| = 2.
Therefore, EJR requires that at least one voter in N∗approves at least 2 candidates in
S, which is not the case.
Note that seq-Phragmén also fails PR (see Example 6.3). This is not surprising,
considering that PR is computationally intractable [56].
6.3 Results for leximax-Phragmén
In Example 6.3, leximax-Phragmén selects the committee providing perfect represen-
tation. We now show that leximax-Phragmén satisfies PR in general.
Theorem 6.10 leximax-Phragmén satisfies PR.
Proof Consider an instance (A,k)and assume that PR(A,k)=∅(otherwise, there
is nothing to show). Recall that a load distribution x=(xi,c)i∈N,c∈Cis perfect if
¯xi=k
nfor all i∈N. We first show that there is a perfect load distribution. Let
13 Replacing the constraint |N∗|≥n
kwith |N∗|> n
k+1is similar to replacing the Hare quota with the
Droop quota in the context of single transferable vote elections (see Sect. 4.3). The condition |N∗|> n
k+1
is the best possible here; see the paper by Janson [27].
14 We thank Jannik Peters for pointing out to us that the proof of Peters and Skowron [40] showing that
priceability implies PJR can be easily adapted to show that priceability implies IPSC.
123
Phragmén’s voting methods and justified representation
{c1,...,ck}⊆Cbe a committee providing perfect representation and let N1,...,Nk
be a corresponding partition of N. Define load distribution x∗by
x∗
i,cj=k
nif i∈Nj,
0 otherwise.
It is straightforward to check that x∗is a valid load distribution and that x∗is perfect.
Clearly, a perfect load distribution is an optimal solution for the minimization
probleminleximax-Phragmén.It followsthatevery optimalload distributionis perfect.
We nowshowthateveryperfect load distributioncorresponds to a committee providing
perfect representation. It then follows that every committee Soutput by leximax-
Phragmén provides perfect representation for (A,k).
Let x=(xi,c)i∈N,c∈Cbe a perfect load distribution and let Sbe the corresponding
committee, i.e., S={c∈C:i∈Nxi,c=1}.
Define Mto be an n×nmatrix with rows corresponding to voters and, for each
c∈S,n
kcolumns c1,c2,...cn
kcorresponding to candidate c.Fori∈Nand c∈S,
define the entry of Min row iand column cj(for all 1 ≤j≤n
k)tobexi,c.Everyrow
of Msums to c∈Sxi,cn
k=n
k¯xi=1, and every column of Msums to i∈Nxi,c=1,
so Mis doubly stochastic. We can now apply the Birkhoff–von Neumann theorem and
get that Mis a convex combination of permutation matrices. Choose a permutation
matrix Pin this convex combination. Pencodes a bijection between the sets N
and c∈Sn/k
j=1cj. From this bijection, we can extract a partition {N(c):c∈S}
of Nby defining N(c)as the set of voters that are mapped to an element of the set
{c1,c2,...cn
k}, for each c∈S. It is easily verified that this partition satisfies the
conditions in Definition 6.2. Therefore, Sprovides perfect representation for (A,k).
SinceEJRis incompatible with PR (see Example 6.3), leximax-PhragménfailsEJR.
However, it satisfies PJR.
Theorem 6.11 leximax-Phragmén satisfies PJR.
Proof We introduce one new piece of notation for this proof. For a committee S⊆C,
let xSbe a leximax-optimal load distribution, given that Sis selected. As usual, we
let ¯xS
i=c∈SxS
i,c.
Consider an instance (A,k)and a committee Soutput by leximax-Phragmén.
Assume that Sdoes not satisfy PJR. That is, there exists >0 and a group N∗⊆N
of voters with |N∗|≥n/k,|i∈N∗Ai|≥and |S∩(i∈N∗Ai)|≤−1. Note
that there must exist a candidate c∗∈∩
i∈N∗Ai\S.
The average load among the voters in N∗is
1
|N∗|
i∈N∗
¯xS
i≤|S∩(i∈N∗Ai)|
|N∗|≤−1
|N∗|≤k
n−1
|N∗|.(6.3)
Further, since the average load among voters in N∗is strictly less than k
nand the total
load among all nvoters is k, the average load among voters in N\N∗is strictly greater
123
M. Brill et al.
than k
n. In particular, consider a leximax-optimal load distribution xSand let ibe a
voter with maximum load among all voters in N\N∗according to xS.Itmustbethe
case that this voter has load ¯xS
i>k
n.
We can now complete the proof by constructing a committee which has a leximax-
smaller vector of voter loads than S, contradicting the optimality of S. Consider a
candidate cwith xS
i,c>0. Such a candidate must exist because ¯xS
i>0. Consider
replacing cby c∗to form committee S=S∪{c∗}\{c}. We construct a valid load
distribution yfor committee Sas follows. Distribute the load of c∗among voters in
N∗only in such a way that for each i∈N∗,yi,c≤max(k
n−¯xS
i,0). This is possible
because j∈N∗max(k
n−¯xS
j,0)≥j∈N∗(k
n−¯xS
j)≥1, where the last inequality
follows from (6.3). Setting yi,c=xS
i,cfor every voter iand every candidate c∈S∩S
yields
¯yi≤¯xS
i+max k
n−¯xS
i,0=max k
n,¯xS
ifor all i∈N∗
¯yi<¯xS
i, and
¯yi≤¯xS
ifor all i∈N\N∗.
In particular, since ¯xS
i>k
nand ¯yi≤k
nfor all iwith ¯yi>¯xS
i,yis a leximax-smaller
vector of loads than xS, contradicting optimality of S.
Remark 6.12 As is the case for seq-Phragmén, leximax-Phragmén also satisfies price-
ability [40] and therefore IPSC (see Remark 6.7).
Corollary 6.13 leximax-Phragmén satisfies JR.
We note that Example 4.1 shows that simply minimizing the maximum voter load
(without leximax tie-breaking) does not even yield committees satisfying JR.
6.4 Results for var-Phragmén
The proof of Theorem 6.10 directly applies to var-Phragmén.
Theorem 6.14 var-Phragmén satisfies PR.
Unlike leximax-Phragmén, var-Phragmén fails PJR.
Example 6.15 Let C={a,b,c,d,e,f,g},k=6, and consider the following profile
with100voters: 67 votersapprove{a,b,c,d},12votersapprove{e},11votersapprove
{f}, and 10 voters approve {g}.LetN∗be the set of voters approving {a,b,c,d}.
We have |N∗|=67 ≥4n
kand |i∈N∗Ai|=4. Thus, PJR requires that all four
candidates in i∈N∗Ai={a,b,c,d}are selected. However, var-Phragmén selects
{a,b,c,e,f,g}.
The previous example also shows that the sequential version of var-Phragmén vio-
lates PJR. Finally, we show that var-Phragmén satisfies JR.
Theorem 6.16 var-Phragmén satisfies JR.
The proof of Theorem 6.16 can be found in the appendix.
123
Phragmén’s voting methods and justified representation
7 Relationship to apportionment methods
As mentioned in Sect. 2, the well-studied apportionment problem [8] constitutes a
special case of approval-based committee elections. To see this, define a party-list
profile as a preference profile A=(A1,...,An)for which the set Cof candidates
can be partitioned into “parties” C=P1˙
∪P2˙
∪... ˙
∪Ppin such a way that each party
Pjcontains at least kcandidates and each voter approves precisely the candidates of
one party (i.e., for all i∈N, there exists a j∈{1,...,p}such that Ai=Pj). Each
party-list profile Acan be summarized by a vote vector VA=(v1,...,vp), where
vj=|{i∈N:Ai=Pj}| is the total number of votes for party Pj.Anapportionment
method is a function that maps a vote vector V=(v1,...,vp)and a natural number
kto a seat distribution z =(z1,...,zp)∈Np
0with p
j=1zj=k. Since vote
vectors correspond to party-list profiles, approval-based committee voting rules are
generalizations of apportionment methods. As a consequence, every approval-based
committee voting rule Rinduces an apportionment method MR[13]: The number zj
of seats that MRallocates to a party Pjis given by the number |S∩Pj|of candidates
from party Pjthat are members of the committee Sselected by the rule R.
Apportionment methods have been extensively studied by Balinski and Young [8]
and Pukelsheim [52]. Three of the most widely-used apportionment methods are
–theD’Hondt method (aka Jefferson method or greatest divisors method),
–theSainte-Laguë method (aka Webster method or major fractions method), and
–thelargest remainder method (aka Hamilton method or Hare–Niemeyer method).
Interestingly, all three apportionment methods are induced by different variants
of Phragmén’s methods: seq-Phragmén and leximax-Phragmén both induce the
D’Hondt method [13,26,44], var-Phragmén induces the Sainte-Laguë method [13],
and Eneström-Phragmén (using the Hare quota qH) induces the largest remainder
method [17].15
Some of the representation axioms discussed in Sect. 6have analogies in the
apportionment literature: When restricted to party-list profiles, both EJR and PJR
(see Definition 6.1) coincide with the requirement that the seat distribution satisfies
lower quota (i.e., zj≥kvj
nfor all j). Therefore, an apportionment method MR
induced by an approval-based committee voting Rsatisfies lower quota whenever R
satisfies PJR. This observation, which was first made by Brill et al. [13], gives rise to
an alternative proof for the fact that var-Phragmén fails PJR: var-Phragmén induces
the Sainte-Laguë method [13], which is well-known to fail lower quota ([8], p. 130).16
Two further properties that are often studied in the apportionment setting are
house monotonicity and population monotonicity ([8], p. 117). House monotonicity
prescribes that no party loses seats when the house size is increased; this directly corre-
spondstocommittee monotonicity forapproval-basedcommitteevotingrules.Whereas
seq-Phragmén satisfies committee monotonicity by definition, the non-sequential vari-
15 Undertheassumptionthat there areatleastas manyseatsas there areparties(i.e.,k≥p),the optimization
variant that maximizes the minimum voter load (see Remark 4.4) induces the Adams method.Thiswas
remarked by Janson [26] and also follows from Proposition 3.11 of Balinski and Young [8].
16 Indeed, the profile in Example 6.15 is a party-list profile with vote vector (67,12,11,10), for which the
Sainte-Laguë method fails lower quota for k=6.
123
M. Brill et al.
ants leximax-Phragmén and var-Phragmén fail the property. This is implicit already
in Phragmén’s 1896 paper [45], and stated explicitly in the paper by Mora and Oliver
[36]; here is a simple example.
Example 7.1 Let C={a,b,c}and consider the following profile with 10 voters:
2×{a}3×{a,c}3×{b,c}2×{b}
Both leximax-Phragmén and var-Phragmén select {c}for k=1 and {a,b}for k=2.
The D’Hondt method and the Sainte-Laguë method satisfy house monotonicity
([8], p. 100). Consequently, leximax-Phragmén and var-Phragmén satisfy committee
monotonicity on party-list profiles. In contrast, the largest remainder method fails
house monotonicity and, therefore, Eneström-Phragmén fails committee monotonicity
even on party-list profiles.
Population monotonicity prescribes that, if the ratio vi
vjincreases, then it should not
be the case that zidecreases and zjincreases. Population monotonicity is satisfied
by the D’Hondt method and the Sainte-Laguë method, but not by the largest remain-
der method ([8], p. 117). We are not aware of a direct generalization of this property
to approval-based committee voting rules; however, it is similar in spirit to support
monotonicity, introduced by Sánchez-Fernández and Fisteus [54], who showed posi-
tive results for seq-Phragmén and leximax-Phragmén.
8 Conclusion
We have shown that Phragmén’s load-balancing methods satisfy interesting represen-
tation axioms. In particular, the polynomial-time computable variant seq-Phragmén
satisfies PJR. Moreover, both leximax-Phragmén and var-Phragmén satisfy PR and
leximax-Phragmén additionally satisfies PJR. Arguably, leximax-Phragmén is the first
known example of a “natural” rule satisfying both PR and PJR—the only other rule
known to satisfy these two properties is an artificial construct that returns a PR com-
mittee if one exists and otherwise runs PAV [56].
Since seq-Phragmén violates EJR, it remains an open problem whether EJR is
compatible with committee monotonicity.17 Further, the intricate nature of Exam-
ple 6.9 seems to suggest that instances on which seq-Phragmén violates EJR are rare.
It would be interesting to see whether seq-Phragmén satisfies EJR for realistic distri-
butions of preferences and/or for reasonable domain restrictions.18 Finally, it would
be of great interest to find axiomatic characterizations of Phragmén’s rules, i.e., to find
sets of axiomatic properties that uniquely define leximax-Phragmén, var-Phragmén,
seq-Phragmén, and Eneström-Phragmén.
17 Intheapproval-basedapportionmentsetting,wherecandidatescanobtainmultipleseatsinthecommittee,
EJR and committee monotonicity can be achieved simultaneously [14].
18 Recent experimental work by Bredereck et al. [10] showed that committees satisfying JR very often
satisfy EJR as well, supporting the hypothesis that instances for which seq-Phragmén fails EJR are rare. An
overview of domain restrictions for approval preferences can be found in the survey by Elkind et al. [20].
123
Phragmén’s voting methods and justified representation
Acknowledgements We would like to thank Xavier Mora for many fruitful discussions and for providing
us with copies of the original papers by Phragmén. We also thank Marie-Louise Lackner for pointing
out essential literature and providing us with translations. Furthermore, we thank Vincent Conitzer, Edith
Elkind, Dominik Peters, Jannik Peters, Luis Sánchez-Fernández, and Piotr Skowron for helpful comments.
We are thankful to the Institut Mittag-Leffler for permitting the use of Phragmén’s photograph (Fig. 1). This
material is based on work supported by ERC-StG 639945, NSF IIS-1527434 and ARO W911NF-12-1-0550,
by a Feodor Lynen return fellowship of the Alexander von Humboldt Foundation, by COST Action IC1205
on Computational Social Choice, by a grant from the Knut and Alice Wallenberg Foundation, by the Isaac
Newton Institute for Mathematical Sciences (EPSRC Grant Number EP/K032208/1), by a grant from the
Simons foundation, by the Deutsche Forschungsgemeinschaft (DFG) under grant BR 4744/2-1, and by the
Austrian Science Foundation FWF, grant P31890.
Funding Open Access funding enabled and organized by Projekt DEAL.
Declarations
Conflict of Interest All authors declare that they have no conflicts of interest.
Open Access This articleislicensedunderaCreative CommonsAttribution4.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 Appendix
A.1 Proof of Theorem 6.16
We first prove a lemma.
Lemma A.1 Let 0<α<1and (xi)1≤i≤nbe a sequence with 0≤xi≤αfor all
i∈{1,...,n}and n
i=1xi=1. Then, n
i=1x2
i≤α.
Proof n
i=1x2
i≤n
i=1αxi=α.
We can now prove Theorem 6.16.
Proof of Theorem 6.16 Consider an instance (A,k)and a committee Soutput by var-
Phragmén. Assume that Sdoes not satisfy JR. That is, there exists a group N∗with
|N∗|≥n
k, such that i∈N∗Ai=∅and |S∩(i∈N∗Ai)|=∅. Clearly, |N∗|<n.
Let ibe a voter with maximum load (i.e., ¯xi≥¯xifor all i∈N), and let cbe a
candidate with xi,c>0. Such a cmust exist because the total load on iis non-zero.
First note that the average load on voters in N\N∗is
k
|N\N∗|≥k
n−n
k
=k2
kn −n.
Therefore, since iis a voter with maximum load, it must be the case that ¯xi≥k2
kn−n.
Further, ¯xi=¯xifor all voters i∈Nc. If this were not the case for some voter i,it
123
M. Brill et al.
would be possible to decrease the variance of the load distribution by reducing xi,c
by some small amount and increasing xi,caccordingly, thus reducing the difference
between the loads on iand iwhile leaving all other loads unchanged, which reduces
the variance.
Let d∈i∈N∗Ai, and let T=S∪{d}\{c}. That is, Tis the committee obtained
by starting with Sand replacing cwith a candidate approved by all voters in N∗.To
complete the proof, we consider the effect that this replacement has on the quanity
i∈N¯x2
i, which is the objective minimized by var-Phragmén.
It is possible to distribute the load of candidate devenly across all (previ-
ously unrepresented) voters in N∗. Therefore, the addition of dcontributes at most
i∈N∗1
|N∗|2=1
|N∗|≤k
nto the objective. On the other hand, removing cfrom the
committee decreases the objective by
i∈Nc
(¯x2
i−(¯xi−xi,c)2)=
i∈Nc
(¯x2
i−¯x2
i+2¯xixi,c−x2
i,c)=
i∈Nc
(2¯xixi,c−x2
i,c)
=
i∈Nc
(2¯xixi,c−x2
i,c)=2¯xi−
i∈Nc
x2
i,c≥2¯xi−¯xi=¯xi≥k2
kn −n>k
n,
where the first inequality follows from Lemma A.1. Therefore, replacing cby dcauses
a net decrease to the objective, contradicting minimality of the variance of committee
S. We have thus obtained a contradiction to our assumption that Sdoes not provide
JR.
A.2 seq-Phragmén violates EJR
Table 2shows the necessary calculations for computing seq-Phragmén in Example 6.9.
123
Phragmén’s voting methods and justified representation
Table 2 The values s(j)
c(rounded to three decimal places) for each remaining candidate c∈Cand each round j∈{1,...,12}in Example 6.9
cs
(1)
cs(2)
cs(3)
cs(4)
cs(5)
cs(6)
cs(7)
cs(8)
cs(9)
cs(10)
cs(11)
cs(12)
c
c10.125 0.163 0.2 0.238 0.275 0.310 0.332 0.369 ––––
c20.077 0.119 0.162 0.204 0.246 –––––––
c30.05 –––––––––––
c40.05 0.1 ––––––––––
c50.05 0.1 0.15 –––––––––
c60.05 0.1 0.15 0.2 ––––––––
c70.05 0.1 0.15 0.2 0.25 0.275 ––––––
c80.05 0.1 0.15 0.2 0.25 0.275 0.325 –––––
c90.05 0.1 0.15 0.2 0.25 0.275 0.325 0.375 0.388 –––
c10 0.05 0.1 0.15 0.2 0.25 0.275 0.325 0.375 0.388 0.438 ––
c11 0.05 0.1 0.15 0.2 0.25 0.275 0.325 0.375 0.388 0.438 0.488 –
c12 0.05 0.1 0.15 0.2 0.25 0.275 0.325 0.375 0.388 0.438 0.488 0.538
a0.25 0.25 0.25 0.25 0.25 0.373 0.373 0.373 0.558 0.558 0.558 0.558
b0.25 0.25 0.25 0.25 0.25 0.373 0.373 0.373 0.558 0.558 0.558 0.558
Entries in bold distinguish the candidate with lowest s(j)
cvalue (up to tie-breaking) in each round
123
M. Brill et al.
References
1. Aziz, H., Lee, B.E.: The expanding approvals rule: improving proportional representation and mono-
tonicity. Soc. Choice Welfare 54, 1–45 (2020)
2. Aziz, H., Lee, B.E.: Proportionally representative participatory budgeting with ordinal preferences. In:
Proceedings of the 35th AAAI Conference on Artificial Intelligence (AAAI), pp. 5110–5118. AAAI
Press (2021)
3. Aziz, H., Shah, N.: Participatory budgeting: models and approaches. In: Rudas T., Péli, G., (eds)
Pathways Between Social Science and Computational Social Science. Springer, Berlin, pp. 215–236
(2021)
4. 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)
5. 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)
6. 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 (2018a)
7. Aziz, H., Lee, B.E., Talmon, N.: Proportionally representative participatory budgeting: axioms and
algorithms. In: Proceedings of the 17th International Conference on Autonomous Agents and Multia-
gent Systems (AAMAS), pp. 23–31. IFAAMAS (2018b)
8. Balinski, M., Young, H.P.: Fair representation: meeting the ideal of one man, one vote. Yale University
Press, 1982. (2nd Edition [with identical pagination], Brookings Institution Press, 2001)
9. Betzler, N., Slinko, A., Uhlmann, J.: On the computation of fully proportional representation. J. Artif.
Intell. Res. 47, 475–519 (2013)
10. Bredereck, R., Faliszewski, P., Kaczmarczyk, A., Niedermeier, R.: An experimental view on commit-
tees providing justified representation. In: Proceedings of the 28th International Joint Conference on
Artificial Intelligence (IJCAI), pp. 109–115. IJCAI (2019)
11. Brent, R.P., Zimmermann, P.: Modern Computer Arithmetic, vol. 18. Cambridge University Press,
Cambridge (2010)
12. Brill,M.,Freeman,R.,Janson,S.,Lackner,M.:Phragmén’svotingmethodsandjustifiedrepresentation.
In: Proceedings of the 31st AAAI Conference on Artificial Intelligence (AAAI), pp. 406–413. AAAI
Press (2017)
13. Brill, M., Laslier, J.-F., Skowron, P.: Multiwinner approval rules as apportionment methods. J. Theor.
Polit. 30(3), 358–382 (2018)
14. Brill, M., Gölz, P., Peters, D., Schmidt-Kraepelin, U., Wilker, K.: Approval-based apportionment.
Math. Program. (2022). https://doi.org/10.1007/s10107-022-01852-1.(Forthcoming)
15. Burdges, J., Cevallos, A., Czaban, P., Habermeier, R., Hosseini, S., Lama, F., Alper, H. K., Luo, X.,
Shirazi, F., Stewart, A., Wood, G.: Overview of Polkadot and its design considerations. Technical
report, arXiv:2005.13456 [cs.CR] (2020)
16. Cairns, W.D.: The international mathematical congress at Toronto. Am. Math. Mon. 31(9), 411–417
(1924)
17. Camps, R., Mora, X., Saumell, L.: The method of Eneström and Phragmén for parliamentary elections
by means of approval voting. Technical report, arXiv:1907.10590 [econ.TH] (2019)
18. Cevallos, A., Stewart, A.: A verifiably secure and proportional committee election rule. In: Proceedings
of the 3rd ACM Conference on Advances in Financial Technologies (AFT), pp. 29–42. ACM (2021)
19. Elkind, E., Faliszewski, P., Skowron, P., Slinko, A.: Properties of multiwinner voting rules. Soc. Choice
Welfare 48(3), 599–632 (2017)
20. Elkind, E., Lackner, M., Peters, D.: Structured preferences. In: Endriss, U., (ed), Trends in Computa-
tional Social Choice, chapter 10, pp. 187–207. AI Access (2017)
21. Faliszewski, P., Skowron, P., Slinko, A., Talmon, N.: Multiwinner voting: a new challenge for social
choice theory. In: Endriss, U., (ed), Trends in Computational Social Choice, chapter 2. AI Access
(2017)
22. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness.
W. H. Freeman (1979)
23. Garey, M.R., Johnson, D.S., Stockmeyer, L.J.: Some simplified NP-complete graph problems. Theor.
Comput. Sci. 1(3), 237–267 (1976)
123
Phragmén’s voting methods and justified representation
24. Israel, J., Brill, M.: Dynamic proportional rankings. In: Proceedings of the 30th International Joint
Conference on Artificial Intelligence (IJCAI), pp. 261–267. IJCAI (2021)
25. Janson, S.: Proportionella valmetoder. Unpublished manuscript. Available at http://www2.math.uu.se/
~svante/papers/sjV6.pdf (2012)
26. Janson, S.: Phragmén’s and Thiele’s election methods. Technical report, arXiv:1611.08826v2
[math.HO] (2018)
27. Janson, S.: Thresholds quantifying proportionality criteria for election methods. Technical report,
arXiv:1810.06377 [cs.GT] (2018)
28. Jaworski, M., Skowron, P.: Phragmén rules for degressive and regressive proportionality. In: Proceed-
ings of the 31st International Joint Conference on Artificial Intelligence (IJCAI), pp. 328–334. IJCAI
(2022)
29. Kilgour, D.M.: Approval balloting for multi-winner elections. In: Handbook on Approval Voting,
chapter 6. Springer (2010)
30. Lackner, M., Maly, J.: Proportional decisions in perpetual voting. In: Proceedings of the 37th AAAI
Conference on Artificial Intelligence (AAAI). AAAI Press (2023). (Forthcoming)
31. Lackner, M., Skowron, P.: Multi-Winner Voting with Approval Preferences. Springer, Berlin (2022)
32. Lu, T., Boutilier, C.: Budgeted social choice: from consensus to personalized decision making. In:
Proceedings of the 22nd International Joint Conference on Artificial Intelligence (IJCAI), pp. 280–
286. AAAI Press (2011)
33. Möller, N.: On Schönhage’s algorithm and subquadratic integer GCD computation. Math. Comput.
77(261), 589–607 (2008)
34. Monroe, B.L.: Fully proportional representation. Am. Polit. Sci. Rev. 89(4), 925–940 (1995)
35. Mora, X.: Phragmén’s sequential method with a variance criterion. Technical report, arXiv:1611.06833
[math.OC] (2016)
36. 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)
37. Moulin, H.: Axioms of Cooperative Decision Making. Cambridge University Press, Cambridge (1988)
38. Ogryczak, W.: On the lexicographic minimax approach to location problems. Eur. J. Oper. Res. 100(3),
566–585 (1997)
39. Ogryczak, W., Sliwinski, T.: On direct methods for lexicographic min-max optimization. In: Gavrilova,
M.L., Gervasi, O., Kumar, V., Tan, C.J.K., Taniar, D., Laganà, A., Mun, Y., Choo, H. (eds) Computa-
tional Science and Its Applications - ICCSA 2006, volume3982 of Lecture Notes in Computer Science,
pp. 802–811. Springer (2006)
40. Peters, D., Skowron, P.: Proportionality and the limits of welfarism. In: Proceedings of the 21st
ACM Conference on Economics and Computation (ACM-EC), pp. 793–794 (2020). Full version
arXiv:1911.11747 [cs.GT]
41. Peters, D., Pierczy´nski, G., Skowron, P.: Proportional participatory budgeting with additive utilities.
In: Proceedings of the 35th Annual Conference on Neural Information Processing Systems (NeurIPS),
pp. 12726–12737 (2021)
42. Phragmén, E.: Om proportionella val. Stockholms Dagblad, 14 March 1893 (1893). Summary of a
public lecture published in a newspaper
43. 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)
44. Phragmén, E.: Proportionella val. En valteknisk studie. Svenska spörsmål 25. Lars Hökersbergs förlag,
Stockholm (1895)
45. Phragmén, E.: Sur la théorie des élections multiples. Öfversigt af Kongliga Vetenskaps-Akademiens
Förhandlingar 53, 181–191 (1896)
46. Phragmén, E.: Till frågan om en proportionell valmetod. Statsvetenskaplig Tidskrift 2(2), 297–305
(1899)
47. Phragmén, E., Lindelöf, E.: Sur une extension d’un principe classique de l’analyse et sur quelques
propriétés des fonctions monogènes dans le voisinage d’un point singulier. Acta Math. 31(1), 381–406
(1908)
48. Pia, A.D., Dey, S.S., Molinaro, M.: Mixed-integer quadratic programming is in NP. Math. Program.
162, 225–240 (2017)
49. Polkadot Wiki. NPoS election algorithms. https://wiki.polkadot.network/docs/learn-phragmen (2021).
Accessed: 01 Jan 2023
123
M. Brill et al.
50. Potthof, R.F., Brams, S.J.: Proportional representation: broadening the options. J. Theor. Polit. 10(2),
147–178 (1998)
51. Procaccia, A.D., Rosenschein, J.S., Zohar, A.: On the complexity of achieving proportional represen-
tation. Soc. Choice Welfare 30, 353–362 (2008)
52. Pukelsheim, F.: Proportional Representation: Apportionment Methods and Their Applications.
Springer, Berlin (2014)
53. Rosenfeld, A., Shapiro, E., Talmon, N.: Proportional ranking in primary elections: a case study. Party
Politics (2022). https://doi.org/10.1177/13540688211066711.(Forthcoming)
54. 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. IFAAMAS (2019). Full version arXiv:1710.04246v3 [cs.GT]
55. Sánchez-Fernández, L., Elkind, E., Lackner, M.: Committees providing EJR can be computed effi-
ciently. Technical report, arXiv:1704.00356v3 [cs.GT] (2017a)
56. 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 (2017b)
57. Sánchez-Fernández, L., Fernández, N., Fisteus, J.A., Brill, M.: The maximin support method: an
extension of the D’Hondt method to approval-based multiwinner elections. Math. Program. (2022).
https://doi.org/10.1007/s10107-022-01805-8.(Forthcoming)
58. Schmeidler, D.: The nucleolus of a characteristic function game. SIAM J. Appl. Math. 17(6), 1163–
1170 (1969)
59. Schrijver, A.: Theory of Linear and Integer Programming. Wiley, London (1986)
60. Skowron, P., Faliszewski, P., Lang, J.: Finding a collective set of items: from proportional multirepre-
sentation to group recommendation. Artif. Intell. 241, 191–216 (2016)
61. 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)
62. Strassen, A.S.V.: Schnelle Multiplikation großer Zahlen. Computing 7(3–4), 281–292 (1971)
63. Stubhaug, A.: Gösta Mittag-Leffler: A man of conviction. Springer, Berlin (2010)
64. Thiele, T.N.: Om flerfoldsvalg. Oversigt over det Kongelige Danske Videnskabernes Selskabs Forhan-
dlinger, pp. 415–441 (1895)
65. Tideman, N.: The single transferable vote. J. Econ. Perspect. 9(1), 27–38 (1995)
Publisher’s Note Springer Nature remains neutral with regard to jurisdictional claims in published maps
and institutional affiliations.
123
