A Practical and Worst-Case Efficient
Algorithm for Divisor Methods of
Apportionment
Raphael Reitzig∗

Sebastian Wild∗

arXiv:1504.06475v4 [cs.DS] 5 Dec 2017

December 6, 2017

Proportional apportionment is the problem of assigning seats to parties
according to their relative share of votes. Divisor methods are the de-facto
standard solution, used in many countries.
In recent literature, there are two algorithms that implement divisor methods: one by Cheng and Eppstein [CE14] has worst-case optimal running time
but is complex, while the other [Puk14] is relatively simple and fast in practice
but does not offer worst-case guarantees.
We demonstrate that the former algorithm is much slower than the other
in practice and propose a novel algorithm that avoids the shortcomings of
both. We investigate the running-time behavior of the three contenders in
order to determine which is most useful in practice.

1. Introduction
The problem of proportional apportionment arises whenever we have a finite supply
of k indivisible, identical resource units which we have to distribute across n parties
fairly, that is according to the proportional share of publicly known and agreed-upon
P
values v1 , . . . , vn (of the sum V = vi of these values). We elaborate in this section on
applications of and solutions for this problem.

∗

Department of Computer Science, University of Kaiserslautern; {reitzig, wild} @ cs.uni-kl.de

1

1. Introduction
Apportionment arises naturally in politics. Here are two prominent examples:
• In a proportional-representation electoral system we have to assign seats in parliament to political parties according to their share of all votes.
The resources are seats, and the values are vote counts.
• In federal states the number of representatives from each component state often
reflects the population of that state, even though there will typically be at least
one representative for any state no matter how small it is.
Resources are again seats, values are the numbers of residents.
In order to use consistent language throughout this article, we will stick to the first
metaphor. That is, we assign k seats to parties [1..n] proportionally to their respective
votes vi , and we call k the house size.
A fair allocation should assign vi /V seats to party i, where V = v1 + · · · + vn is the
total vote count of all parties. In case of electoral systems which exclude parties below a
certain threshold of overall votes from seat allocation altogether, we assume they have
already been removed from our list of n parties.
As seats are indivisible, this is only possible if, by chance, all vi /V are integers; otherwise
we have to come up with some rounding scheme. This is where apportionment methods
come into play. The books by Balinski and Young [BY01] and Pukelsheim [Puk14] give
comprehensive introductions into the topic with its historical, political and mathematical
dimensions.
Mathematically speaking, an apportionment method is a function f : Rn>0 × N → Nn0 that
maps vote counts v = (v1 , . . . , vn ) and house size k to a seat allocation s = (s1 , . . . , sn ) :=
f (v, k) so that s1 + · · · + sn = k. We interpret s as party i getting si seats.

There are many conceivable such methods, but there are at least three natural properties
one would like apportionment systems to have:

(P1) Pairwise vote monotonicity: When votes change, f should not take away seats
from a party that has gained votes while at the same time awarding seats to one
that has lost votes.
(P2) House monotonicity: f should not take seats away from any party when the house
grows (in number of seats) but votes do not change.
(P3) Quota rule: The number of seats of each party should be its proportional share,
rounded either up or down.
Balinski and Young have shown that
• (P1) implies (P2) [BY01, Cor. 4.3.1],

• no method can always guarantee (P1) and (P3) [BY01, Thm. 6.1], and

2

1. Introduction
Method

Divisor Sequence

δ(x)

Sandwich

Smallest divisors

0, 1, 2, 3, . . .

x

—

Greatest divisors

1, 2, 3, 4, . . .

x+1

—

Sainte-Laguë

1, 3, 5, 7, . . .

2x + 1

—

Modified Sainte-Laguë
Equal Proportions

1.4, 3, 5, 7, . . .
√ √ √
0, 2, 6, 12, . . .

Harmonic Mean

0, 43 ,

12 24
5 , 7 ,

...

Imperiali

2, 3, 4, 5, . . .

Danish

1, 4, 7, 10, . . .

 2x+1

x(x + 1)

x+

2x(x+1)
2x+1

6
5
1
4

x+

1
4

x≥1
1.6x+1.4 x<1

p

2x +

x+2

—

3x + 1

—

±
±
±

1
5
1
4
1
4

Table 1: Commonly used divisor methods [CE14, Table 1]. For each of the methods, we
give a possible continuation δ of the respective divisor sequence (cf. Section 2)
as well as linear sandwich bounds on δ, if non-trivial (cf. Lemma 2).

• (P1) holds exactly for divisor methods [BY01, Thm. 4.3].

Property (P1) is essential for upholding the principle of “one-person, one-vote”, an ideal
pursued by electoral systems around the globe and occasionally enforced by law [Puk14,
Section 2.4]. Therefore, divisor a. k. a. Huntington methods can be the only choice, for
the price of (P3). Other choices can be made, of course; the aforementioned books [BY01;
Puk14] discuss different trade-offs.
Divisor methods are characterized by divisor sequences which control the notion of
“fairness” implemented by the respective method. There are many popular choices (cf.
Table 1). It is not per se clear which divisor sequence is the best; there still seems to be
active discussion, e. g., for the U. S. House of Representatives. One reason is that no-one
has yet been able to propose a convincing, universally agreed-upon mathematical criterion
that would single out one method as superior to the others. In fact, there are competing
notions of fairness, each favoring a different divisor method [BY01, Section A.3]. A
reasonable approach is therefore to run computer simulations of different methods and
compare their outcomes empirically, for example w. r. t. the distribution of final average
votes per seat vi /si . For this purpose, many apportionments have to be computed, so
efficient algorithms can become an issue.
We thus study the problem of computing the final seat allocation by divisor methods
(given by their divisor sequences) according to vote counts and house size.
For the case of almost linear divisor sequences, the problem can be solved in time O(n);
this has been shown by Cheng and Eppstein [CE14] who propose a worst-case runningtime-optimal algorithm which we call ChengEppsteinSelect. It is quite involved and
rather difficult to implement (cf. Appendix C.3).

3

2. Divisor Methods Formalized
Pukelsheim [Puk14], on the other hand, proposes algorithm JumpAndStep whose
running time is not asymptotically optimal in the worst case but tends to perform well in
practice, at least if some insight about the used divisor sequence is available and inputs
are good-natured (cf. Appendix C.2).
After introducing divisor methods formally in Section 2, we propose a new algorithm in
Section 3 that also attains the O(n) worst-case running time bound but is straight-forward
to implement and efficient in practice as well. It is based on a generalization of our
solution for the envy-free stick-division problem [RW15b].
We finally compare the performance of the three contending algorithms with extensive
running time experiments, an executive summary of which we give in Section 4.
Additional material includes an index of notation in Appendix F.

2. Divisor Methods Formalized
Let d = (dj )∞
j=0 be an arbitrary divisor sequence, i. e. a nonnegative, strictly increasing
and unbounded sequence of real numbers. We formally set d−1 := −∞.

We require that there is a smooth continuation of d on the reals which is easy to invert.
That is, we assume a function δ : R≥0 → R≥d0 with
i) δ is continuous and strictly increasing,

ii) δ −1 (x) for x ≥ d0 can be computed with a constant number of arithmetic operations,
and
iii) δ(j) = dj (and thus δ −1 (dj ) = j) for all j ∈ N0 .

All the divisor sequences used in practice fulfill these requirements; cf. Table 1. For
convenience, we continue δ −1 on the complete real line requiring
iv) δ −1 (x) ∈ [−1, 0) for x < d0 .

Corollary 1: Assuming i) to iv), δ −1 (x) is continuous and strictly increasing on R≥d0 .
Furthermore, it is the inverse of j 7→ dj in the sense that
bδ −1 (x)c = max{j ∈ Z≥−1 | dj ≤ x}
for all x ∈ R.



In particular, bδ −1 (x)c = j for dj ≤ x < dj+1 so the floored δ −1 is the (zero-based) rank
function for the set of all dj as long as x ≥ d0 .

Note how this reproduces what is called d-rounding in the literature [BY01; Puk14]; we
obtain an efficient way of calculating this function via δ −1 .

4

2. Divisor Methods Formalized
Now the set of all seat assignments that are valid w. r. t. d is given by [BY01]
S(v, k) =

n

s ∈ Nn0

n
X
i=1

si = k ∧ ∃ a > 0. ∀ i ∈ [1..n]. si ∈ bδ −1 (vi · a)c + {0, 1} .
o

We call a realization of a proportionality constant a∗ ; intuitively, every seat corresponds
to roughly 1/a∗ votes.
An equivalent definition is by the set of possible results of the following algorithm [BY01,
Prop. 3.3].
Algorithm 1: IterativeMethodd (v, k) :
Step 1 Initialize s = 0n .
Step 2 While k > 0,
Step 2.1 Determine I = arg minni=1 dsi /vi .
Step 2.2 Update sI ← sI + 1 and k ← k − 1.

Step 3 Return s.

We can obtain a proportionality constant [Puk14, 59f] by
a∗ = max{dsi −1 /vi | 1 ≤ i ≤ n},

(1)

which in turn defines the set S(v, k).

Note that we work with dj /vi instead of vi /dj in the classical literature; Cheng and
Eppstein [CE14] and we prefer the reciprocals because the case d0 = 0 then handles
gracefully and without special treatment. Therefore, our a∗ is also the reciprocal of the
proportionality constant as e. g. Pukelsheim [Puk14] defines it, we multiply by a in the
definition of S and we take the minimum in IterativeMethod. It is important to note
that the defined set S remains unchanged by this switch.

Following the notation of Cheng and Eppstein [CE14], we furthermore define for given
votes v = (v1 , . . . , vn ) ∈ Qn>0 the sets
Ai :=

ai,j j = 0, 1, 2, . . .

n

o

with ai,j :=

dj
vi

and their multiset union
A :=

n
]

Ai .

i=1

As we will see later, the relative rank of elements in A turns out to be of interest; we
therefore define the rank function r(x, A) which denotes the number of elements in
5

3. Fast Apportionment by Rank Selection
multiset A that are no larger than x, that is
r(x, A) :=

A ∩ (−∞, x]

=

n
X
i=1

(2)

|{ai,j ∈ A | ai,j ≤ x}|.

We write r(x) instead of r(x, A) when A is clear from context.

We need two more convenient shorthands: Assuming we have a∗ ≤ x, we denote with
Ix :=



(3)

i ∈ {1, . . . , n} | vi > d0 /x

the set of parties that can hope for a seat, and with
x

A

:=

dj
∈A
<x
vi
vi

]  dj
i∈Ix



=

n 
]
dj
i=1

dj
∈A
<x
vi
vi



= A ∩ (−∞, x) (4)

the multiset of elements from sequences of these parties that are smaller than x, i. e.
reasonable candidates for a∗ .

3. Fast Apportionment by Rank Selection
From (1) together with strict monotonicity of d, we obtain immediately that a∗ = A(k) ,
i. e. the kth smallest element of A (counting duplicates) is a suitable proportionality
constant. This allows us to switch gears from the iteration-based world of Pukelsheim
[Puk14] to selection-based algorithms, as previously seen by Cheng and Eppstein [CE14].
Note that even though A is infinite, A(k) always exists because the terms ai,j = dj/vi are
strictly increasing in j for all i ∈ {1, . . . , n}.

Borrowing terminology from the field of mathematical optimization, we call a feasible if
r(a) ≥ k, otherwise it is infeasible. Feasible a 6= a∗ are called suboptimal. Our goal is to
find a subset of A that contains a∗ but as few infeasible or suboptimal a as possible; we
can then apply a rank-selection algorithm on this subset and obtain (via a∗ ) the solution
to the apportionment problem.
Now since d is unbounded, setting any upper bound x on the ai,j yields a finite search
space Ax . By choosing any such bound that maintains |Ax | ≥ k, we retain the property
that a∗ is the kth smallest element under consideration.
One naive way is to make sure that the party with the most votes (which should get
the most seats) contributes at least k values to A. This can be achieved by letting
x = dk−1 / max v + ε (cf. the proof of Theorem 3). This alone, however, leads only
to an algorithm with worst-case running time in Θ(kn), which is worse than even
IterativeMethod (with priority queues).
We can actually not improve this upper bound x; it is tight for the case that one party
has many more votes than all others and gets (almost) all of the seats. We can, however,

6

3. Fast Apportionment by Rank Selection
exclude many individual elements in Ax because they are too small to be feasible or too
large to be optimal.
Towards finding suitable upper and lower bounds on a∗ , we investigate its rank in the
multiset A of all candidates. All we know is that
k ≤ r(a∗ ) ≤ k + |Ix |
since we may have any number between one and |Ix | parties that tie for the last seat.
We can still make an ansatz with r(a) ≥ k + |Ix | and r(a) < k, express rank function r
in terms of δ −1 (cf. Lemma 4 in Appendix B) and derive that
X
i∈Ix

and

δ −1 (vi · a) ≤ k − |Ix |

X
i∈Ix

δ −1 (vi · a) ≥ k.

(5)

This pair of inequalities is indeed a sufficient condition for admissible pairs of bounds
(a, a); we can conclude that a ≤ a∗ ≤ a. For a formal proof, see Lemma 5 in Appendix B.
We now want to derive a sandwich on a∗ by fulfilling the inequalities in (5) as tightly as
possible. Depending on δ −1 , this may be hard to do analytically. However, we can make
the same assumption as Cheng and Eppstein [CE14] and explicitly compute suitable
bounds for divisor sequences which behave roughly linearly. This does not limit the scope
of our investigation by much; see Appendix A for more on this.
Lemma 2: Assume the continuation δ of divisor sequence d fulfills
αx + β ≤ δ(x) ≤ αx + β
for all x ∈ R≥0 with α > 0, β ∈ [0, α] and β ≥ 0. Let further some x > a∗ be given.
Then, the pair (a, a) defined by


a := max 0,
with Vx :=

P

i∈Ix

αk − (α − β) · |Ix |
Vx



and a :=

αk + β · |Ix |
Vx

vi fulfills the conditions of Lemma 5, that is a ≤ a∗ ≤ a. Moreover,


A ∩ [a, a] ≤ 2 1 +

β−β
α



· |Ix |.

The proof consists mostly of rote calculation towards applying Lemma 5; see Appendix B
for the details.
We have now derived our main improvement over the work by Cheng and Eppstein
[CE14]; where they have only a one-sided bound on a∗ and thus have to employ an
involved search on A, we have sandwiched a∗ from both sides, and so tightly that the
remaining search space is small enough for a simple rank selection to be efficient.

7

3. Fast Apportionment by Rank Selection
Building on the bounds from Lemma 2, we can improve upon the naive idea using only
x by excluding also many more elements from A which are for sure not a∗ . Since we
remove in particular too small elements, this means that we also have to modify the rank
we select; we will see that our bounds are chosen so that we can use δ −1 to count the
number of elements we discard exactly.
Recall that we assume a fixed apportionment scheme, that is fixed d with known α, β
and β as per Lemma 2.
Algorithm 2: SandwichSelect(v, k)d :
Step 1 Find the v (1) = max{v1 , . . . , vn }.

Step 2 Set x := dk−1 /v (1) + ε for suitable1 constant ε > 0.

Step 3 Compute Ix as per (3).
Step 4 Compute a and a as per Lemma 2.
Step 5 Initialize Â := ∅ and k̂ := k.
Step 6 For all i ∈ Ix , do:

Step 6.1 Compute j := max 0, δ −1 (vi · a)






and j := bδ −1 (vi · a)c.

Step 6.2 Add all dj /vi to Â for which j ≤ j ≤ j.

Step 6.3 Update k̂ ← k̂ − j.
Step 7 Select and return Â(k̂) .

Theorem 3:
Algorithm 2 computes a∗ in time O(n) for any divisor sequence d that fulfills the
requirements of Lemma 2.
Proof: First, we have to show that Ix as we compute it in Steps 1-3 is correct. We
have x > a∗ = Ax as already r(x − ε) = r(dk−1 /v (1) ) ≥ k; at least the k elements
d
d0
(1) . We thus never need to consider elements
, . . . , vk−1
(1) ∈ A are no larger than dk−1 /v
v (1)
a ≥ x, and in particular A(k) = Ax(k) as Ax = A ∩ (−∞, x).

So far, we have needed no additional restriction on ε in Step 2; we only need it to be
positive so we do not discard a∗ by accident if it is exactly dk−1 /v (1) . However, the size
of Ax can be arbitrarily large – depending on the input values vi which we do not want.
Therefore, we require
0<ε<
1

dk − dk−1
;
v (1)

(6)

Neither correctness nor Θ-running-time is affected by the choice of ε here since it affects only the size
of Ix , which is bounded by n in any case. In particular, the size of Â is affected only up to a constant
factor. For tweaking performance in practice, see the proof of Theorem 3.

8

4. Comparison of Algorithms
such exists because d is strictly increasing. Note how then x < dk /v (1) so we do not keep
any additional suboptimal values.
From Step 4 on, we then construct multiset Â ⊆ A as the subsequent union of Ai ∩ [a, a],
that is
Â =

]  dj
i∈Ix

vi

]  dj

=

i∈Ix

vi

]  dj

=

i∈Ix

]

=

i∈Ix

vi



j(i) ≤ j ≤ j(i)
∈A δ

−1

(vi · a) ≤ j ≤ δ

∈ A vi · a ≤ dj ≤ vi · a

dj
dj
∈A a≤
≤a
vi
vi

−1

(vi · a)







= A ∩ [a, a].
In particular, the last step follows from (4) with x > a∗ . By Lemma 2, we know that
a ≤ a∗ ≤ a for the bounds computed in Step 4, so we get in particular that a∗ ∈ Â.

It remains to show that we calculate k̂ correctly. Clearly, we discard with (ai,0 , . . . , ai,j−1 )
exactly j elements in Step 6.2, that is |Ai ∩ (−∞, a)| = j(i). Therefore, we compute with
k̂ = k −

X
i∈Ix

Ai ∩ (−∞, a) = r(a∗ , A) − A ∩ (−∞, a) = r(a∗ , Â)

the correct rank of a∗ in Â.

For the running time, we observe that the computations in steps 1 to 5 are easily
done with O(n) primitive instructions. The loop in Step 6 and therewith steps 6.1
and 6.3 are executed |Ix | ≤ n times. The overall number of set operations in Step 6.2 is
|Â| ∈ O(|Ix |) ⊆ O(n) (cf. Lemma 2). Finally, Step 7 runs in time O(|Â|) ⊆ O(n) when
using a (worst-case) linear-time rank selection algorithm (e. g., the median-of-medians
algorithm [Blu+73]).


We have obtained a relatively simple algorithm that implements many divisor methods
and has optimal asymptotic running time in the worst case. It remains to be seen if it is
also efficient in practice.

4. Comparison of Algorithms
We have implemented all algorithms mentioned above in Java [RW15a] with a focus on clarity and performance. Reviewing the algorithms resp. implementations (cf. Appendix C),

9

4. Comparison of Algorithms

Average running time in µs/n

(α, β) = (2, 1) and k = 100n

(α, β) = (1, 3/4) and k = 10n

4

0.6

3
0.4
2
0.2

1
0
2

4

6
n

8

0

10

0

50

100
n

150

200

Figure 1: This figure shows average running times of SandwichSelect , ChengEppsteinSelect , JumpAndStep with naive resp. priority-queue minimum
selection, and IterativeMethod with naive resp. priority-queue minimum
selection, normalized by the number of parties n. The inputs are random apportionment instances with vote counts vi drawn i. i. d. uniformly from [1, 3]. The
numbers of parties n, house size k and method parameters (α, β) have been
chosen to resemble national parliaments in Europe (left) and the U. S. House of
Representatives (right), respectively.

we observe that neither IterativeMethod nor JumpAndStep are asymptotically
worst-case efficient whereas ChengEppsteinSelect does not seem to be practical
regarding implementability. SandwichSelect does not have either deficiency and is
still the shortest of the non-trivial algorithms.
We evaluate relative practical efficiency by performing running time experiments on
artificial instances; we fix the number of parties n, house size k and the used divisor
method and draw multiple vote vectors v at random according to different distributions.
Where possible, we draw votes from a continuous distribution with fixed expectation;
this ensures that vote proportions do not devolve to trivial situations as n grows.
In order to keep the parameter space manageable, we use n as free variable and fix k to
a multiple of n. For ease of implementation, we restrict ourselves to divisor sequences of
the form (αj + β)j∈N0 ; this still allows us to cover a range of relevant divisor methods at
least approximately (cf. Table 1). We describe the machine configuration used for the
experiments and further details of the setup in Appendix D.
Figure 1 shows the results of two experiments with practical parameter choices. It is clear
that JumpAndStep dominates the field; of the other algorithms, only SandwichSelect
comes close in performance. These observations are stable across many parameter
choices; see also Appendix E. We will therefore restrict ourselves to JumpAndStep and
SandwichSelect in the sequel.
Towards understanding what influences the performance of these algorithms the most,

10

4. Comparison of Algorithms

Running time in ms

8
10

6
4

5

2
0

0
0

1,000

2,000

0

3,000

0.5

1
|Â|

|∆a |

1.5
·105

Figure 2: Running times on individual inputs plotted against |∆a | for JumpAndStep (left)
resp. |Â| for SandwichSelect (right). Inputs are random with exponentially
distributed vi for n ∈ {1 , 5 , 10 , 20 , 30 , 40 , 50 , 75 , 100 }·103 and k = 5n;
they have been apportioned w. r. t. (α, β) = (2, 1).

we have investigated how ∆a (the number of seats JumpAndStep assigns too much, i. e.
P
k − si ) resp. |Â| (the number of candidates SandwichSelect selects from) relate to
the measured running times. While the connection is clear for SandwichSelect, we
need to look at cases where Pukelsheim’s estimators are bad; as long as |∆a |  n, the
Θ(n) portions of JumpAndStep dominate. Figure 2 exhibits such a setting.
While JumpAndStep is faster than SandwichSelect in the experiments of Figure 1
and similar ones, we observe that SandwichSelect is more robust against changing
parameters. Figure 3 exhibits this for switching between different vote distributions:
the average running times of SandwichSelect are close to each other where those of
JumpAndStep spread out quite a bit. It may be noteworthy that each algorithm has
one “outlier” distribution but they are not the same.
JumpAndStep does indeed seem to outperform SandwichSelect consistently so far,
if not by much in some cases. We have found a parameterization which, even though
it is admittedly rather artificial, clearly suggests that JumpAndStep does indeed have
ω(n) worst-case behavior and that SandwichSelect can be faster; see Figure 4. The
question after realistic settings for which this is the case remains open.
In summary, we have seen that SandwichSelect provides good performance in a reliable
way, i. e., its efficiency does not depend much on divisor sequence or input. On the other
hand, JumpAndStep is faster on average when good estimators are available, but can
be slower in certain settings.

11

Average running time in µs/n

4. Comparison of Algorithms

0.1

0.1

8 · 10−2

8 · 10−2

6 · 10−2

6 · 10−2
50

100
n

150

4 · 10−2

200

0

50

100
n

150

200

0.12

0.26

0.1
0.24

8 · 10−2

|∆a |/n

Average running time in µs/n

Figure 3: Normalized average runtimes of SandwichSelect (left) and JumpAndStep
(right) on vi drawn randomly from uniform , exponential , Poisson and Pareto
distributions, respectively, and with k = 5n and (α, β) = (2, 1).

6 · 10−2

0.22

4 · 10−2
2 · 10−2

0.2

0

0

0.2

0.4

0.6
n

0.8

1

0

0.2

0.4

0.6
n

·105

0.8

1
·105

Figure 4: The left plot shows normalized running times of SandwichSelect and
JumpAndStep on instances with k = 2n and Pareto-distributed vi for
(α, β) = (1.0, 0.001). The right plot shows that the average of |∆a | seems to
converge towards a constant fraction of n in this case.

12

5. Conclusion

5. Conclusion
We have derived an algorithm implementing divisor methods of apportionment that is
worst-case efficient, simple and practicable. As such, it does not have the shortcomings of
previously known algorithms. Even though it can not usually outperform JumpAndStep,
its robustness against changing parameters makes it a viable candidate for use in practice.

Acknowledgments
We thank Chao Xu for pointing us towards the work by Cheng and Eppstein [CE14] and
noting that the problem of envy-free stick-division [RW15b] is related to proportional
apportionment as discussed there. He also observed that our approach for cutting sticks –
the core ideas of which turned out to carry over to this article – could be improved to
run in linear time.
Furthermore, we owe thanks to an anonymous reviewer whose constructive feedback
sparked broad changes which have greatly improved the article over its first incarnation.

References
[Blu+73]

Manuel Blum et al. “Time Bounds for Selection.” In: Journal of Computer
and System Sciences 7.4 (Aug. 1973), pp. 448–461. doi: 10.1016/S00220000(73)80033-9.

[BY01]

Michel L. Balinski and H. Peyton Young. Fair Representation. Meeting the
Ideal of One Man, One Vote. 2nd. Brookings Institution Press, 2001. isbn:
978-0-8157-0111-8.

[CE14]

Zhanpeng Cheng and David Eppstein. “Linear-time Algorithms for Proportional Apportionment.” In: International Symposium on Algorithms and
Computation (ISAAC) 2014. Springer, 2014. doi: 10 . 1007 / 978 - 3 - 319 13075-0_46.

[GKP94]

Ronald L. Graham, Donald E. Knuth, and Oren Patashnik. Concrete mathematics: a foundation for computer science. Addison-Wesley, 1994. isbn:
978-0-20-155802-9.

[Puk14]

Friedrich Pukelsheim. Proportional Representation. Apportionment Methods
and Their Applications. 1st ed. Springer, 2014. isbn: 978-3-319-03855-1. doi:
10.1007/978-3-319-03856-8.

[RW15a]

Raphael Reitzig and Sebastian Wild. Companion Source Code. revision
db43ee7f05. 2015. url: https://github.com/reitzig/2015_apportionment.

[RW15b]

Raphael Reitzig and Sebastian Wild. Efficient Algorithms for Envy-Free Stick
Division With Fewest Cuts. 2015. arXiv: 1502.04048.

13

References
[SW11]

Robert Sedgewick and Kevin Wayne. Algorithms. 4th. Addison-Wesley, 2011.
isbn: 978-0-321-57351-3. url: http://algs4.cs.princeton.edu.

14

A. Our Scope of different Methods of Apportionment

A. Our Scope of different Methods of Apportionment
As we have seen in Section 2 there are many possible divisor sequences. For our main
result (cf. page 7) we follow Cheng and Eppstein [CE14] and require the sequences to
be “almost” linear; we should check that we do not unduly restrict the scope of our
investigation.
We refer to the recent reference work by Pukelsheim [Puk14] and, by extension, to
Balinski and Young [BY01] who classify different divisor methods of apportionment in
terms of signpost sequences, a concept equivalent to the divisor sequences we use. They
distinguish these classes of such sequences (cf. [Puk14, Sections 3.11-12]):
• stationary sign-posts of the form s(n) = n − 1 + r with r ∈ (0, 1);

• power-mean sign-posts defined by
s̃p (0) = 0,
s̃p (n) =



(n − 1)p + np
2

1/p

,

for p 6= −∞, 0, ∞;

• and special cases s̃−∞ (n) = n − 1, s̃0 (n) =

(n − 1)n, and s̃∞ (n) = n.

p

It is easy to see that stationary sign-posts correspond do divisor sequences dj = j + β
with β ∈ (0, 1) (up to a shift by one); as such, Lemma 2 applies immediateley with α = 1
and β = β = β, and yields a particularly nice (and tight, for our choices of a and a)
upper bound on the size of the candidate set A. We cover the special cases as well; see
Table 1 for the corresponding sandwich bounds.
As for the remaining power-mean sign-posts, the trivial bounds β = 0 and β = 1 already
work. One can apply the power-mean inequality and use the slightly better bounds
for p ∈ {−∞, −1, 0, 1, ∞} as given in Table 1. Even better bounds can be gleaned
from observing that s̃p (n) converges to n − 1/2 from one side, and quickly so; s̃p (1) thus
determines either β or β and the other can be chosen as 1/2.
In summary, our algorithm SandwichSelect applies to all divisor methods treated by
Pukelsheim [Puk14] and Balinski and Young [BY01]

B. Lemmata and Proofs
Lemma 4: For rank function r(x, A),
r(x, A) =

n
X
i=1

bδ −1 (vi · x)c + 1.

15

B. Lemmata and Proofs
Moreover, for x < x we have
r(x, A) =

X

bδ −1 (vi · x)c + 1

i∈Ix

with Ix = i ∈ {1, . . . , n} | vi > d0 /x .


B.1. Proof of Lemma 4
By eq. (2) on page 6, it suffices to show that
{ai,j | ai,j ≤ x} = bδ −1 (vi · x)c + 1
for each i ∈ {1, . . . , n}. Now, if x ≥ ai,j = dj/vi for some j, then vi · x ≥ dj , and so
bδ −1 (vi · x)c is the largest index j 0 for which ai,j 0 = dj 0 /vi ≤ x. As dj is zero-based, there
are j 0 + 1 ≥ 1 such elements ai,j ≤ x and the equation follows.

Otherwise, that is ai,j > x for all j, we have j 0 = bδ −1 (vi · x)c = −1 by iv) and Corollary 1
and the equality holds with 0 on both sides.
For the second equality, we only have to show that the omitted summands are zero. So
let i ∈
/ Ix be given, that is vi ≤ d0 /x. For x < x, we have
vi · x ≤

d0
d0
·x <
· x = d0 ,
x
x

and hence bδ −1 (vi · x)c = −1 by iv).

Lemma 5: Let x > a∗ and assume a and a are chosen so that they fulfill
X
i∈Ix

δ −1 (vi · a) ≤ k − |Ix |

X

and

i∈Ix

δ −1 (vi · a) ≥ k.

Then, a ≤ a∗ ≤ a.
The lemma follows more or less directly; one uses the sandwich bounds on r to show
that a < a are infeasible, i. e., r(a) < k, and that a is feasible, and thus all a > a are
suboptimal since a∗ is the smallest feasible element in A.

B.2. Proof of Lemma 5
As a direct consequence of Lemma 4 together with the fundamental bounds y−1 < byc ≤ y
on floors, we find that
X
i∈Ix

δ −1 (vi · x) < r(x, A) ≤

X
i∈Ix

δ −1 (vi · x) + 1

16



= |Ix | +

X
i∈Ix

δ −1 (vi · x) (7)

B. Lemmata and Proofs
for any x and all x < x. We can therewith pin down the value of r to an interval of
width |Ix | using only δ −1 . We can use this to derive upper and lower bounds on a∗ .

We show that smaller a are infeasible and larger a are clearly suboptimal, so the optimal
a∗ must lie in between. Let us first consider a < a. There are two cases: if there is a vi ,
such that vi a ≥ d0 , we get by strict monotonicity of δ −1
r(a) ≤ |Ix | +
(7)

< |Ix | +

X
i∈Ix

X
i∈Ix

δ −1 (vi · a)
δ −1 (vi · a)

≤ k

and a is infeasible. If otherwise vi a < d0 , i. e., a < d0 /vi , for all i, a must clearly have
rank r(a) = 0 as it is smaller than any element ai,j ∈ A. In both cases we found that
a < a has rank r(a) < k.
Now consider the upper bound, i. e., we have a > a. In case a ≥ x, we have a > x > a∗
by assumption and any such a cannot be optimal. Otherwise, for a < x, we have
r(a) >

(7)

X
i∈Ix

δ −1 (vi · a) ≥ k,

so a is feasible. Any element a > a can thus not be the optimal solution a∗ , which is the
minimal a with r(a) ≥ k.

B.3. Proof of Lemma 2
We consider the linear divisor sequence continuations
δ(j) = αj + β

and

δ(j) = αj + β

for all j ∈ R≥0 and start by noting that the inverses are
δ −1 (x) = x/α − β/α

and

δ −1 (x) = x/α − β/α

for x ≥ δ(0) = β and x ≥ δ(0) = β, respectively. For smaller x, we are free to choose the
value of the continuation from [−1, 0) (cf. iv)); noting that x/α − β/α < 0 for x < β, a
choice that will turn out convenient is
δ

−1

x β
(x) := max
− , −1
α α




resp.

δ

−1

x β
(x) := max
− , −1 .
α α




(8)

We state the following simple property for reference; it follows from δ(j) ≤ δ(j) ≤ δ(j)
and the definition of the inverses (recall that β ≤ α):
x β
x β
−
≤ δ −1 (x) ≤ δ −1 (x) ≤ δ −1 (x) ≤
− ,
α α
α α
17

for x ≥ 0.

(9)

B. Lemmata and Proofs
Equipped with these preliminaries, we compute
a =
⇐⇒

αk + β|Ix |
.
Vx

a X
β
·
vi = k +
· |Ix |,
α i∈I
α
x

⇐⇒ k =

X  vi · a

α

i∈Ix

β
−
α



X

≤

(9) i∈I
x

δ −1 (vi · a),

so a satisfies the condition of Lemma 5. Similarly, we find
a =

αk − (α − β) · |Ix |
,
Vx

a
· Vx = k − (1 − β/α) · |Ix |,
α

X  vi · a
X
β
⇐⇒ k = |Ix | +
≥ |Ix | +
−
δ −1 (vi · a),
α
α
(9)
i∈I
i∈I
⇐⇒

x

x

that is a also fulfills the conditions of Lemma 5.
For the bound on the number of elements falling between a and a, we compute
A ∩ [a, a]

=

X
i∈Ix

=

Ai ∩ [a, a]

X 
i∈Ix

=

≤

j ∈ N0 δ −1 (vi · a) ≤ j ≤ δ −1 (vi · a)

X 
X
i∈Ix

X

(9) i∈I
x

≤

j ∈ N0

j ∈ N0 vi · a ≤ dj ≤ vi · a

i∈Ix

≤

δ −1 (vi · a) − δ −1 (vi · a) + 1
δ −1 (vi · a) − δ

X  vi · a − β

α

(9) i∈I
x

=

X

1+

i∈Ix

=



X 
i∈Ix

=

dj
a≤
≤a
vi



1+

−

−1

(vi · a) + 1






vi · a − β
+1
α

β−β
vi · a − vi · a 
+
α
α

β−β
α



· |Ix | + (a − a) ·

18

Vx
α

C. Implementing the Algorithms
=

β−β
1+
α





β−β
= 2 1+
α


· |Ix | +



(α + β − β) · |Ix | Vx
·
Vx
α

· |Ix |.

C. Implementing the Algorithms
In this section, we review existing algorithms for divisor methods. In particular, we
elaborate on how we have implemented them for our experiments [RW15a], and on
problems we have encountered in this process.
We have taken care not to render the algorithm unnecessarily inefficient in order to
perform a fair comparison of running times; the result is to the best of our abilities
conditioned on a limited time budget. In particular, all of our implementations have
been refined on the programming level to roughly the same degree.
For the purpose of a fair comparison, all implementation have to conform to the same
interface.
Parameters: A pair (α, β) ∈ R2 with α > 0 and β > 0.
Input: Votes v and house size k.

Output: A (symbolic) representation of all seat assignments valid w. r. t. divisor sequence
(αj + β)j≥0 , as well as proportionality constant a∗ .
More specifically, the output is encoded as a vector of undisputed seats and a binary
vector indicating which parties are tied for the remaining seats. We skip the step from
a∗ resp. a valid seat assignment to this representation in the pseudo code since it is
elementary: all parties with “current” resp. “next” value vi /dsi −1 resp. vi /dsi equal a∗
are tied. A simple Θ(n)-time post-processing identifies these in all cases.
We have established confidence in the correctness of our implementations by extensive
random testing [RW15a, TestMain.java]; every implementation has been run on thousands of instances. The correctness of the results has been confirmed, besides rudimentary
sanity checks such as matching vector dimensions, by checking Pukelsheim’s Max-Min
Inequality [Puk14, Theorem 4.5].
All implementations share the same numerical weakness, though: using fixed-precision
arithmetics, two computations that should lead to the same result (say, a∗ ) yield different
numbers. We compensate for that by using fuzzy comparisons: we identify numbers if
they are within some constant  of each other. Thus, we can reliably identify tied parties,
for instance.
There is a drawback, though: if distinct values vi /dj are closer than  (or, even without
the adaption, the resolution of the chosen fixed-precision number representation), we
may identify them and thus compute wrong seat assignments.

19

C. Implementing the Algorithms
This issue can not be circumvented on the algorithmic level. The only robust resort
we know of is using arbitrary-precision arithmetics, inevitably slowing down all the
algorithms.

C.1. Iterative Divisor Method
Implementing IterativeMethod is straight-forward. An implementation using a priority
queue implementation from the standard library runs in time Θ(n + k log n). Since we
expect overhead for the queue to be significant for small n, we also implement a variant
which determines I using a simple linear scan, resulting in a total running time in Θ(kn).
Shared code aside, IterativeMethod takes about 50 resp. 65 lines of code with resp.
without priority queues.

C.2. Jump-and-Step
The jump-and-step algorithm [Puk14, Section 4.6] can be formulated using our notation
as follows:
Algorithm 3: JumpAndStepd (v, k) :
Step 1 Compute an estimator a for a∗ .
Step 2 Initialize si = bδ −1 (vi · a)c + 1.

Step 3 Iterate similarly to IterativeMethod until
I=


arg maxn
i=1 vi /dsi ,

P

si < k;

arg minn

P

si > k.

i=1 vi /dsi −1 ,

P

si = k with

The performance of this algorithm clearly depends on ∆a := si − k after Step 2; the
running time is in Θ(n + |∆a | · log n) when using priority queues for Step 3 (which may
not be advisable in practice if |∆a | can be expected to be very small). As such, the
running time is not per se bounded in n and k.
P

We follow the recommendations of Pukelsheim and use the estimator [Puk14, Section 6.1]
α k + n · (β/α − 1/2),
a :=
·
V k + n · bβ/αc,


0 ≤ β/α ≤ 1;
else.

The first case corresponds to Pukelsheim’s recommended estimator for stationary signpost
sequences, the second to his good universal estimator generalized to divisor sequences
that are not signpost sequences in the strict sense. The additional factor α rescales the
value appropriately; Pukelsheim only considers α = 1.

20

C. Implementing the Algorithms
Given that these estimators guarantee |∆a | ≤ n in the worst case, we can assume
that JumpAndStep runs in time O(n log n). Furthermore, Pukelsheim claims that the
recommended estimator is good in practice in the sense that |∆a | ∈ O(1) in expectation,
so JumpAndStep may be efficient in practice for large n as well. Since their proof is
limited to uniformly distributed votes and k → ∞, we investigate this in Section 4.
Shared code aside, JumpAndStep takes about 120 lines of code, with or without priority
queues.

C.3. The Algorithm of Cheng and Eppstein
Cheng and Eppstein [CE14] do not give pseudocode for the main procedure of their
algorithm which would combine the individual steps to compute A(k) . For the reader’s
convenience and for clarity concerning our running-time comparisons we give this top-level
procedure as we have inferred it.
Algorithm 4: ChengEppsteinSelectd (v, k) :
Step 1 Compute a suitable finite representation of A.
Step 2 C := FindContributingSequences(A, k).

Step 3 ξ := s−1 (k) [CE14, (3)].

Step 4 If r(ξ, A) ≥ k then
ξ := LowerRankCoarseSolution(A, k, ξ).
Step 5 Return CoarseToExact(A, k, ξ).
The subroutines are given in sufficient detail in their Algorithms 1 to 3, respectively.
The pseudo code given uses some high-level set operations which we did not implement
naively due to performance concerns; we compute several steps during a single iteration
over the respective sets of sequences.
Note that we have (hopefully) fixed an off-by-one mistake in the text. The definition of
rank r(x, A) is, “the number of elements of A less than or equal to x”; that is, the rank
of A(j) is j + 1 since A is zero-based (the first element is A(0)). However, the authors
continue to say that r(x, A) “is the index j such that A(j) ≤ x < A(j + 1).”

Regarding performance, Cheng and Eppstein show that their algorithm runs in time Θ(n)
in the worst case. Since ChengEppsteinSelect computes a linear number of medians
and requires a linear number of evaluations of rank function r(x, A) (with geometrically
shrinking |A| – otherwise the algorithm would not run in linear time), it is unclear
whether the algorithm is efficient in practice.
Shared code aside, ChengEppsteinSelect take about 300 lines of code. By this
measure, it is the most complex of the algorithms we consider.

21

C. Implementing the Algorithms

Additional Issues with Numerics
In addition to the concerns expressed above, there are additional numerical issues when
implementing ChengEppsteinSelect using fixed-precision floating-point arithmetics.
In short, we have to compute certain floors and ceilings of real numbers exactly or we
may compute a wrong result.
More specifically, we evaluate r(x, A) several times by computing terms of the form
bδ −1 (_)c (cf. Lemma 4). The problem is that the result of δ −1 (_) is non-integral in
general, but is integral when the argument evaluates exactly to a dj . With the usual
floating-point arithmetic the result might be slightly smaller, though. We then erroneously
round down to the next smaller integer – a critical error!
In practice, we can add a small constant to the mantissa before taking the floor. This
constant has to be chosen large enough to cover potential rounding errors, but also
small enough so as to not change subsequent calculations; ChengEppsteinSelect may
compute a wrong answer otherwise. This is a very delicate requirement we do not know
how to fulfill in general.

C.4. SandwichSelect
We already discuss our algorithm at length in Section 3. Since we want to investigate
practical performance, we implement rank-selection using average-case efficient Quickselect
as opposed to using a linear-time algorithm with large constant factors.
We want to emphasize that our final algorithm SandwichSelect is conceptually simple
in the sense that there is little hidden complexity. We need exactly one call to a rank
selection algorithm on a linear-size list which takes five additional linear-time operations
to come up with: finding the maximal value v (1) , constructing index set Ix , computing Vx ,
constructing multiset Â and computing k̂. These are all quite elementary tasks in that
they use one for-loop each which run for at most n iterations with only few operations
in each. We therefore think that we can outperform ChengEppsteinSelect in practice,
and should not be far behind JumpAndStep, either.
Regarding implementation, the delicate part was to get the bounds on j (cf. Step 6.1)
right. We use floor and ceiling functions on real numbers, so rounding errors that occur
in fixed-precision floating-point arithmetic can cause harm. We can circumvent this by
adding (subtracting) a conservatively large constant to the mantissa of the floats before
taking floors (ceilings). If this constant is larger than necessary for covering rounding
errors, we might add slightly more candidates to Â (at most two per party) which
would slightly degrade performance. Correctness, however, is not affected (in contrast to
ChengEppsteinSelect).
We also remark here that the code [RW15a] for the experimental results discussed in
Section 4 is based on an earlier version of Lemma 2 with slightly weaker bounds (cf.

22

D. Experimental Setup
Appendix G). Experiments with the updated code are to follow, and might yield slight
improvements for SandwichSelect.
Shared code aside, SandwichSelect takes about 100 lines of code. By this measure, it
is the least complex of the non-trivial algorithms we consider.

D. Experimental Setup
We have run the experiments with Java 7 on Ubuntu 14.04 LTS running kernel 3.13.0-34generic x86_64 GNU/Linux. The hardware platform is a ThinkPad T430s Tablet with
the following core parameters according to lshw.
CPU: Intel R CoreTM i5-3320M CPU @ 2.60GHz
Cache: L1 32KiB, L2 256KiB, L3 3MiB
RAM: 4+4GiB SODIMM DDR3 Synchronous 1600 MHz (0.6 ns)
As our code is written in Java, we include a warm-up phase to trigger just-in-time
compilation of the relevant methods. All times are measured using the built-in method
System.nanoTime(). We use the same set of inputs for all algorithms, all of which have
to construct the full set S(v, k) for each input (v, k) during the measurement.

In order to increase accuracy, we repeat the execution of each algorithm on each input
several times and measure the total time; we then report the average time per execution.

For the selection-based algorithms, we use the randomized Quickselect-based implementation by Sedgewick and Wayne [SW11] as published on the book website. We use
the (pseudo) random number generators for several distributions from the same library
(download of stdlib-package.jar on August 11th, 2015).
For reproducing our running time experiments, make sure you have working GNU/Linux2
installation with Ruby, Java 7 and Ant; then execute
ruby run_experiments.rb arxiv.experiment
for the data represented in Section 4 and Appendix E. Be warned: this may run for a
long time, and it will create lots of images (provided you have gnuplot installed).

E. More Running-Time Experiments
We apologize to only offer draft graphics without commentary for the time being.

2

Our framework may work on other platforms, maybe with small adjustments to the Ruby code, but we
have not tried. See README.md for a workaround.

23

E. More Running-Time Experiments
Average normalized runtimes for several input distributions and across several orders of
magnitudes of n.

24

E. More Running-Time Experiments
Normalized runtimes of ChengEppsteinSelect for several input distributions and
across several orders of magnitudes of n.

25

E. More Running-Time Experiments
Normalized runtimes of JumpAndStep for several input distributions and across several
orders of magnitudes of n.

26

E. More Running-Time Experiments
Normalized runtimes of SandwichSelect for several input distributions and across
several orders of magnitudes of n.

27

E. More Running-Time Experiments
Normalized ∆a of JumpAndStep for several input distributions and across several orders
of magnitudes of n.

28

E. More Running-Time Experiments
Normalized |Â| of SandwichSelect for several input distributions and across several
orders of magnitudes of n.

29

E. More Running-Time Experiments
Runtimes against ∆a of JumpAndStep for several input distributions and across several
orders of magnitudes of n. Each color stands for one n.

30

E. More Running-Time Experiments
Runtimes against |Â| of SandwichSelect for several input distributions and across
several orders of magnitudes of n. Each color stands for one n.

31

F. Index of Used Notation

F. Index of Used Notation
In this section, we collect the notation used in this paper. Some might be seen as
“standard”, but we think including them here hurts less than a potential misunderstanding
caused by omitting them.

Generic Mathematical Notation
bxc, dxe . . . . . . . . floor and ceiling functions, as used in [GKP94].

M(k) . . . . . . . . . . The kth smallest element of (multi)set/vector M (assuming it exists);
if the elements of M can be written in non-decreasing order, M is given
by M(1) ≤ M(2) ≤ M(3) ≤ · · · .
Example: For M = {5, 8, 8, 8, 10, 10}, we have M(1) = 5,
M(2) = M(3) = M(4) = 8, and M(5) = M(6) = 10.
M (k) . . . . . . . . . . Similar to M(k) , but M (k) denotes the kth largest element.
x = (x1 , . . . , xd ) . . . to emphasize that x is a vector, it is written in bold;
components of the vector are written in regular type.
M . . . . . . . . . . . to emphasize that M is a multiset, it is written in calligraphic type.

M1 ] M2 . . . . . . . multiset union; multiplicities add up.

Notation Specific to the Problem
party, seat, vote (count), chamber size
Parties are assigned seats (in parliament), so that the number of seats
si that party i is assigned is (roughly) proportional to that party’s vote
count vi and the overall number of assigned seats equals the chamber
size k.
d = (dj )∞
j=0 . . . . . . the divisor sequence used in the highest averages method; d must be a
nonnegative, (strictly) increasing and unbounded sequence.
δ, δ −1 . . . . . . . . . a continuation of j 7→ dj on the reals and its inverse, both of which can
be evaluated in constant time.
n . . . . . . . . . . . . number of parties in the input.
v, vi . . . . . . . . . . v = (v1 , . . . , vn ) ∈ Qn>0 , vote counts of the parties in the input.

V . . . . . . . . . . . . the sum v1 + · · · + vn of all vote counts.

k . . . . . . . . . . . . k ∈ N, the number of seats to be assigned; also called house size.

s, si . . . . . . . . . . s = (s1 , . . . , sn ) ∈ N0 , the number of seats assigned to the respective
parties; the result.
ai,j . . . . . . . . . . . ai,j := dj /vi , the ratio used to define divisor methods; i is the party, j
is the number of seats i has already been assigned.

32

G. Changelog
Ai . . . . . . . . . . . For party i, Ai := {ai,0 , ai,1 , ai,2 , . . .} is the list of (reciprocals of)
party i’s ratios.
a . . . . . . . . . . . . We use a as a free variable when an arbitrary ai,j is meant.
A . . . . . . . . . . . . A := A1 ] · · · ] An is the multiset of all averages.

r(x, A) . . . . . . . . . the rank of x in A, that is the number of elements in multiset A that
are no larger than x; r(x) for short if A is clear from context.
a∗ . . . . . . . . . . . . the ratio a∗ = ai∗,j ∗ selected for assigning the last (i. e. the kth) seat;
corresponds to s by si = r(a∗ , Ai ); a∗ = A(k) (cf. Section 2 and
Section 3).
x . . . . . . . . . . . . an upper bound x > a∗ ; we use x = dk−1 /v1 + ε, where ε > 0 is a
suitable constant.
Ix . . . . . . . . . . . . Ix := {i | vi > d0 /x}; the set of parties i whose vote count is large
enough, so that ai,0 < x, i. e. so that they contribute to the rank of x in
A.

Vx . . . . . . . . . . . the sum of the vote counts of all parties in Ix .

Ax . . . . . . . . . . . the elements in A that are smaller than x, i. e., A ∩ (−∞, x).

a, a . . . . . . . . . . . lower and upper bounds on candidates a ≤ a ≤ a such that still
a∗ ∈ A ∩ [a, a].

G. Changelog
The following (substantial) changes have been made from arXiv version 2 to 3.
• Lemma 2 has been strengthened; both a and the upper bound on |A ∩ [a, a]| have
been improved. Both changes are due to the observation that we could require
β ≤ α without loss of generality.
Related notation update: (β̌, β)

(β, β).

• We have added Appendix A in order to clarify that the assumptions we make for
our main result do restrict the scope of divisor methods we cover by too much.

33

