<figure><img src="image_1.png" /></figure>

HAL
open science

# In This Apportionment Lottery, the House Always Wins

Paul Gölz, Dominik Peters, Ariel Procaccia

► To cite this version:

Paul Gölz, Dominik Peters, Ariel Procaccia. In This Apportionment Lottery, the House Always Wins. Operations Research, In press, 10.1287/opre.2022.0419. [https://hal.science/hal-05367822v1](https://hal.science/hal-05367822v1)

HAL Id: hal-05367822

https://hal.science/hal-05367822v1

Submitted on 17 Nov 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# In This Apportionment Lottery, the House Always Wins

Paul Gölz¹, Dominik Peters², and Ariel D. Procaccia³

¹UC Berkeley, Cornell University

²CNRS, LAMSADE, Université Paris Dauphine - PSL

³School of Engineering and Applied Sciences, Harvard University

Version accepted to Operations Research · April 2024

## Abstract

Apportionment is the problem of distributing *h* indivisible seats across states in proportion to the states' populations. In the context of the US House of Representatives, this problem has a rich history and is a prime example of interactions between mathematical analysis and political practice. Grimmett (2004) suggested to apportion seats in a randomized way such that each state receives exactly their proportional share *q*ᵢ of seats in expectation (ex ante proportionality) and receives either [qᵢ] or [qᵢ] many seats ex post (quota). However, there is a vast space of randomized apportionment methods satisfying these two axioms, and so we additionally consider prominent axioms from the apportionment literature. Our main result is a randomized method satisfying quota, ex ante proportionality and house monotonicity — a property that prevents paradoxes when the number of seats changes and which we require to hold ex post. This result is based on a generalization of dependent rounding on bipartite graphs, which we call cumulative rounding and which might be of independent interest, as we demonstrate via applications beyond apportionment.

<table><tr><td>1</td><td>Introduction</td><td>2</td></tr><tr><td>2</td><td>Model</td><td>7</td></tr><tr><td>3</td><td>Population Monotonicity</td><td>8</td></tr><tr><td>4</td><td>House Monotonicity</td><td>11</td></tr><tr><td>5</td><td>Proof of Cumulative Rounding</td><td>15</td></tr><tr><td>6</td><td>Other Applications of Cumulative Rounding</td><td>19</td></tr><tr><td>7</td><td>Discussion</td><td>21</td></tr><tr><td>8</td><td>Bibliography</td><td>22</td></tr><tr><td colspan="2">Appendices</td><td>27</td></tr></table>
# 1 Introduction

The Constitution of the United States says that

> "Representatives [in the US House of Representatives] shall be apportioned among the several States according to their respective numbers, counting the whole number of persons in each State ..."

These "respective numbers," or populations, of the states are determined every decade through the census. For example, on April 1, 2020, the population of the United States was 331,108,434, and the state of New York had a population of 20,215,751. New York therefore deserves 6.105% of the 435 seats in the House, which is 26.56 seats, for the next ten years. The puzzle of apportionment is what to do about New York's 0.56 seat — in this round of apportionment it was rounded down to 0, and New York lost its 27th seat.

The mathematical question of how to allocate these fractional seats has riveted the American political establishment since the country's founding (Szpiro, 2010). In 1792, Congress approved a bill that would enact an apportionment method proposed by Alexander Hamilton, the first secretary of the treasury and star of the eponymous musical. If we denote the *standard quota* of state *i* by $q_i$ ($q_i = 26.56$ in the case of New York in 2020), Hamilton's method allocates to each state its *lower quota* $\lfloor q_i \rfloor$ (26 for NY). Then, Hamilton's method goes through the states in order of decreasing *residue* $q_i - \lfloor q_i \rfloor$ (0.56 for NY) and allocates an additional seat to each state until all house seats are allocated.

As sensible as Hamilton's method appears, it repeatedly led to bizarre results, which became known as *apportionment paradoxes*.

**The Alabama paradox:** Using the 1880 census results, the chief clerk of the Census Office calculated the apportionment according to Hamilton's method for all House sizes between 275 and 350, and discovered that, as the size increased from 299 to 300, Alabama lost a seat. In 1900, the Alabama paradox reappeared, this time affecting Colorado and Maine.

**The population paradox:** In 1900, the populations of Virginia and Maine were 1,854,184 and 694,466, respectively. Over the following year, the populations of the two states grew by 19,767 and 4,649, respectively. Even though Virginia's growth was larger even relative to its population, Hamilton's method would have transferred a seat from Virginia to Maine.

Past occurrences of these paradoxes invited partisan strife, which is only natural since a state's representatives have a strong personal stake in their state not losing seats. Both in Congress and the courts, this strife took the form of a tug-of-war over the choice of apportionment method, the size of the House, and the census numbers, driven by the states', parties', and individual representatives' self-interest rather than the public good.

This state of affairs improved in 1941 when Congress adopted an apportionment method that provably avoids the Alabama and population paradoxes, which had been developed by Edward Huntington, a Harvard mathematician, and Joseph Hill, the chief statistician of the Census Bureau. While the Huntington–Hill method is *house monotone* (i.e., it avoids the Alabama paradox) and *population monotone* (i.e., it avoids the population paradox), it has a different, equally bizarre weakness: it does not *satisfy quota*, that is, the allocation of some states may be different from $\lfloor q_i \rfloor$ or $\lceil q_i \rceil$. A striking impossibility result by Balinski and Young (1982) shows that this tension is inevitable: no apportionment method can simultaneously satisfy quota and be population monotone. (We will revisit this result in Section 3 and show that, while Balinski and Young's theorem makes additional implicit assumptions, the incompatibility between quota and population monotonicity continues to hold without these assumptions.)

While the Balinski–Young impossibility is troubling, in our view there is an even larger source of unfairness that plagues apportionment methods, which is rooted in their determinism. In addition
to introducing bias (the Huntington-Hill method disadvantages larger states), deterministic methods often lead to situations where small counting errors can change the outcome. For example, based on the 2020 census, New York lost its 27th House seat, but it would have kept it had its population count been higher by 89 residents! Indeed, current projections suggest that New York would have kept its seat were it not for distortions in census response rates (Elliott et al., 2021, p. 20). After the 1990 and 2000 censuses, similar circumstances were the basis for lawsuits brought by Massachusetts and Utah. A second shortcoming of deterministic apportionment methods is a lack of fairness over time: For example, if the states' populations remain static, a state with a standard quota of, say, 1.5 might receive a single seat in every single apportionment and therefore only receive 2/3 of its deserved representation. Using randomized apportionment, the long-term average of a state's number of seats is proportional to the state's average share of the total population.

To address these issues, an obvious solution is to use randomization in order to realize the standard quota of each state in expectation, as Grimmett proposed in 2004 (Grimmett, 2004). If such a randomized method was used, 89 additional residents would have shifted New York's expected number of seats by a negligible 0.0001, and the decision between 26 or 27 seats would have been made by an impartial random process, which is less accessible to political maneuvering than, say, the census (Stone, 2011).

Grimmett's proposed apportionment method is easy to describe. First, we choose a random permutation of the states; without loss of generality, that permutation is identity. Second, we draw $U$ uniformly at random from $[0, 1]$, and let $Q_i := U + \sum_{j=1}^{i} q_j$. Finally, we allocate to each state $i$ one seat for each integer contained in the interval $[Q_{i-1}, Q_i)$. (In particular, this implies that the allocation will satisfy quota.)

Why this particular method? Grimmett (2004, p. 302) writes:

> “We offer no justification for this scheme apart from fairness and ease of implementation.”

Grimmett's method is easy to implement for sure, and what he refers to as “fairness” — realizing the fractional quotas in expectation—is arguably a minimal requirement for any randomized apportionment method. But his two axioms, “fairness” and quota, allow for a vast number of randomized methods: Indeed, after allocating $\lfloor q_i \rfloor$ seats to each agent, the problem of determining which states to round up reduces to so-called “$\pi$ ps sampling” (“inclusion probability proportional to size”), and dozens of such schemes have been proposed in the literature (Brewer and Hanif, 1983). We believe, therefore, that additional criteria are needed to guide the design of randomized apportionment methods. To identify such criteria, we return to the classics: house and population monotonicity.

## 1.1 Our Approach and Results

In this paper, we seek randomized apportionment methods that satisfy natural extensions of house and population monotonicity to the randomized setting. We want these monotonicity axioms to hold even *ex post*, i.e., after the randomization has been realized. We find such methods by taking a parameterized class of deterministic methods all of which satisfy the desired *ex post* axioms (in our case, subsets of population monotonicity, house monotonicity, and quota), and to then randomize over the choice of parameters such that *ex ante* properties hold (here: *ex ante* proportionality). In mechanism design, a similar approach extends strategyproofness to universal strategyproofness (Nisan and Ronen, 2001).

Guaranteeing monotonicity axioms *ex post* is helpful for preventing certain kinds of manipulation in the apportionment process. For instance, say that the census concludes and a randomized apportionment is determined, and only then does a state credibly contest that its population was undercounted (in the courts or in Congress with the support of a majority). Using an
<figure><img src="image_3.png" /><figcaption>Figure 1: Illustration of cumulative rounding. Dashed lines indicate edges $e \in E$ in the bipartite graph $(V, E)$, which are labeled with weights $w_e^t$. The red lines indicate a possible random outcome of cumulative rounding.</figcaption></figure>

apportionment method without population monotonicity, states might strategically undercount their population in the census and only reveal the true count in case this turns out to be beneficial once the randomness is revealed. When using a population monotone method, by contrast, any revised apportionment would be made using the same deterministic and population monotone method, which implies that immediately revealing the full population count is a dominant strategy.

In Section 3, we first show that no such randomized methods exist for population monotonicity. This impossibility is not due to randomization or ex ante proportionality, but due to the fact that population monotonicity and quota are outright incompatible. Thus, there do not exist suitable deterministic apportionment methods that a randomized apportionment method could randomize over. That population monotonicity and quota are incompatible is well-known from the Balinski-Young impossibility theorem (Balinski and Young, 1982). But their proof uses some “mild” background conditions that are not mild for our randomized purposes since, to provide ex ante proportionality, the randomized method must sometimes prioritize smaller states over larger states with positive probability, which is ruled out by those background conditions. We are able to prove a stronger version of their theorem, which derives the impossibility with no assumptions other than population monotonicity and quota. The deterministic apportionment methods that are most commonly used in practice (so called divisor methods, which include the Huntington-Hill method) satisfy population monotonicity but fail quota. So it makes sense to ask whether population monotonicity can be combined with ex ante proportionality (without requiring quota). We construct such a method, which is reminiscent of the family of divisor methods, except that the so-called “divisor criterion” (Balinski and Young, 1982) is specific to each state and is given by a sequence of Poisson arrivals.

For house monotonicity, we provide in Section 4 a randomized apportionment method that satisfies house monotonicity, quota, and ex ante proportionality. To obtain this result, we generalize the classic result of Gandhi et al. (2006) on dependent rounding in a bipartite graph. We call this method *cumulative dependent randomized rounding* or just *cumulative rounding* (Theorem 4). Cumulative rounding allows to correlate dependent-rounding processes in multiple copies of the same bipartite graph such that the result satisfies an additional guarantee across copies of the graph. This guarantee, which we describe in the next paragraph, generalizes the quota axiom of apportionment. As a side product, our existence proof for house monotonicity provides a new characterization of the deterministic apportionment methods satisfying house monotonicity and quota, which is based on the corner points of a bipartite matching polytope.

To describe cumulative rounding more precisely, we first sketch the result of Gandhi et al. (2006). For a bipartite graph $(V, E)$ and edge weights $\{w_e\}_{e \in E}$ in $[0, 1]$, dependent rounding randomly generates a subgraph $(V, E')$ with $E' \subseteq E$ providing three properties: *marginal distribution* (each edge $e \in E$ is contained in $E'$ with probability $w_e$), *degree preservation* (in the rounded graph, the degree of a vertex $v$ is the floor or the ceiling of $v$'s fractional degree $\sum_{v \in E \subseteq E} w_e$), and *negative
*correlation*. Cumulative rounding allows us to randomly round *T* many copies of (*V*, *E*), where each copy $1 \le t \le T$ has a set of weights {$w_e^t$}$_{e \in E}$. Each copy will provide marginal distribution, degree preservation, and negative correlation. As we prove in Section 5, cumulative rounding additionally guarantees *cumulative degree preservation*: for each vertex *v* and $1 \le t \le T$, the sum of degrees of *v* across copies 1 through *t* equals the sum of fractional degrees of *v* across copies 1 through *t*, either rounded up or down. For example, node $v_1$ in Fig. 1 is incident to edges with a total fractional weight of $2 \cdot 1/4 + 2 \cdot 1/2 = 1.5$ across copies $t=1,2$, and must hence be incident to 1 or 2 edges in total across the rounded versions of copies $t=1,2$. Since, across copies $t=1,2,3$, $v_1$'s total fractional degree is $1.5 + 2 \cdot 3/4 = 3$, $v_1$ must be incident to a total of exactly 3 rounded edges across the copies $t=1,2,3$. By applying cumulative rounding to a star graph, we obtain a randomized apportionment method satisfying house monotonicity, quota, and ex-ante proportionality.

We believe that cumulative rounding is of broader interest, and in Section 6, we present applications of cumulative rounding beyond apportionment. First, we consider a proposal of Buchstein and Hein (2009) for reforming the European Commission of the European Union: They propose a weighted lottery to determine which countries nominate commissioners. Using cumulative rounding to implement this lottery would eliminate two key problems the authors identified in a simulation study, in particular the possibility that some member states may not nominate any commissioners for a long time. We also describe how to apply cumulative rounding to round fractional allocations of goods or chores, and we discuss a specific application of assigning faculty to teach courses.

## 1.2 Related Work

We have already mentioned several seminal works of apportionment theory. Besides the axiomatic approach (e.g., Balinski and Young, 1975, 1982; Balinski and Ramírez, 1999; Balinski and Ramirez, 2014; Palomares et al., 2024), which has arguably proved the most influential, deterministic apportionment has been extensively studied through the lens of constrained optimization (e.g., Huntington, 1928; Burt and Harris, 1963; Ernst, 1994; Agnew, 2008), with respect to bias against larger or smaller states (e.g., Pólya, 1919; Balinski and Young, 1982; Marshall et al., 2002; Lauwers and Van Puyenbroeck, 2006; Janson, 2014), and in multi-dimensional generalizations (e.g., Balinski and Demange, 1989a,b; Maier et al., 2010; Cembrano et al., 2022; Mathieu and Verdugo, 2022). For a comprehensive treatment of this theory, we refer the reader to Balinski and Young (1982) and Pukelsheim (2017).

A naïve form of randomized apportionment was suggested by Balinski (1993), who immediately rejected it: “It is trivial to propose an unbiased method: assign the *h* seats at random with probabilities proportional to the fair shares. In this case none of the other desirable properties is guaranteed.” The proposal by Grimmett (2004), which we discussed above, makes a much stronger case for randomized apportionment by showing one desirable property — quota — which can, in fact, be guaranteed ex post. Our work adds house and population monotonicity to the set of achievable properties. More recently, Aziz et al. (2019) developed a randomized rounding scheme as part of a mechanism for strategy-proof peer selection, which they simultaneously proposed as a randomized apportionment method. Just like Grimmett’s method, their method satisfies ex ante proportionality and quota. Aziz et al. argued that the main advantage of their method is that its support consists of only linearly (not exponentially) many deterministic apportionments. This, they claimed, is useful in repeated apportionment settings, where one could repeat a periodic sequence of these deterministic apportionments and thereby limit the possibility of selecting the same state much too frequently or much too rarely due to random fluctuations. If this is the goal, cumulative rounding will arguably give better guarantees (see Section 6.1).
Apportionment can be seen as a special case of the fair division of indivisible goods, which has recently received increased attention in operations research (e.g., Sandomirskiy and Segal-Halevi, 2022; Aziz et al., 2023a; Benadè et al., 2023). The apportionment setting is characterized by the fact that the goods (i.e., the seats) are interchangeable and that the agents (i.e., the states) are *weighted* (in other words, have different entitlements) (e.g., Barbanel, 1996; Aziz et al., 2020). Though the focus on interchangeable goods may appear very restrictive at first glance, Chakraborty et al. (2021) showed that house monotone apportionment methods, when interpreted as *picking sequences*, induce allocation algorithms for the full setting of weighted fair division. In particular, an apportionment method satisfying house monotonicity and quota yields a fair-division algorithm satisfying *weighted proportionality up to one good (WPROP1)* (Chakraborty et al., 2021, Prop. 4.8). Hence, our randomized method in Section 4 can be seen as a randomized picking-sequence algorithm that ensures WPROP1 ex post, and ex ante satisfies that each agent *i* will get the *t*th pick (for each *t* = 1, 2, ... ) with probability proportional to *i*'s weight. This latter property is not only an intuitively appealing fairness guarantee in its own right, but also immediately implies *weighted proportionality* (Barbanel, 1996).

Our work is part of a larger thrust to develop allocation mechanisms that combine desirable ex-ante and ex-post guarantees, which have been termed best-of-both-worlds guarantees (Aziz et al., 2023a). The works of Hylland and Zeckhauser (1979) and Bogomolnaia and Moulin (2001) were early precursors to this idea, in the setting of matchings where the space of realizable ex-ante probabilities has a very clean structure (Birkhoff, 1946; von Neumann, 1953). Budish et al. (2013) generalized this approach to more general combinatorial constraints. Aziz et al. (2023a) first studied classic fair-division axioms in this way, and Babaioff et al. (2022) and Feldman et al. (2023) extended this approach to additional fairness axioms and more general valuations. The corollary in the previous paragraph is a best-of-both-worlds fairness guarantee for weighted fair division; recently, Aziz et al. (2023b) and Hoefer et al. (2023) have obtained best-of-both-world guarantees for this setting.

As a consequence of the Birkhoff–von Neumann Theorem (Birkhoff, 1946; von Neumann,
1953), any fractional matching in a bipartite graph can be implemented as a lottery over integral
matchings, in the sense that each edge is present in the random matching with probability
equal to its weight in the fractional matching. One algorithm for rounding a bipartite matching
is pipage rounding (Ageev and Sviridenko, 2004), which Gandhi et al. (2006) randomized in
their dependent rounding technique. This rounding technique is powerful since it can directly
accommodate fractional degrees larger than 1 and can provide negative-correlation properties
such that Chernoff concentration bounds apply (Panconesi and Srinivasan, 1997). The technique
of Gandhi et al. has found many applications in approximation algorithms (Gandhi et al., 2006;
Kumar et al., 2009; Bansal et al., 2012) and in fair division (Saha and Srinivasan, 2018; Akbarpour
and Nikzad, 2020; Cheng et al., 2019).

Steiner and Yeomans (1993) studied a problem in just-in-time industrial manufacturing: how to alternate between the production of different types of goods in a way that produces each type in specified proportions. As pointed out by Bautista et al. (1996) and expanded upon by Balinski and Shahidi (1998), this problem is related to apportionment. In particular, a production schedule resembles a deterministic, house monotone apportionment method: as the available production time increases by one slot, the schedule needs to decide which type to produce in the next slot. Steiner and Yeomans ended up with a property that nearly guarantees quota because they aim to minimize how far the prevalence of types among the goods produced so far deviates from the desired proportions. (Most of the literature on this just-in-time production problem minimized other measures of deviation (see Kubiak, 1993), which are not connected to quota.) Now, Steiner and Yeomans (1993) only produce deterministic schedules, and the existence of deterministic house monotone and quota apportionment methods has long been known (Balinski and Young, 1975; Still, 1979). But we believe that the main construction in
their proof could be randomized to obtain an alternative proof of Theorem 5, without however providing the generality of cumulative rounding. In fact, a similar graph construction to that by Steiner and Yeomans is randomly rounded within a proof by Gandhi et al. (2006) to obtain an approximation result about broadcast scheduling.

## 2 Model

Throughout this paper, fix a set of $n \ge 2$ states $N = \{1, 2, \dots, n\}$. For a given population profile $\vec{p} \in \mathbb{N}^n$, which assigns a population of $p_i \in \mathbb{N}$ to each state $i$, and for a house size $h \in \mathbb{N}$, an apportionment solution deterministically allocates to each state $i$ a number $a_i \in \mathbb{Z}_{\ge 0}$ of house seats such that the total number of allocated seats is $h$. Formally, a solution is a function $f: \mathbb{N}^n \times \mathbb{N} \to \mathbb{Z}_{\ge 0}^n$ such that, for all $\vec{p}$ and $h$, $\sum_{i \in N} f_i(\vec{p}, h) = h$. For a population profile $\vec{p}$ and house size $h$, state $i$'s standard quota is $q_i := \frac{p_i}{\sum_{i \in N} p_i} h$. Next, we define three axioms for solutions:

**Quota:** A solution $f$ satisfies quota if, for any $\vec{p}$ and $h$, it holds that $f_i(\vec{p}, h) \in \{\lfloor q_i \rfloor, \lfloor q_i \rfloor\}$ for all states $i$.

**House monotonicity:** A solution $f$ satisfies house monotonicity if, for any $\vec{p}$ and $h$, increasing the house size to $h+1$ does not reduce any state's seat number, i.e., if $f_i(\vec{p}, h) \le f_i(\vec{p}, h+1)$ for all $i \in N$.

**Population monotonicity:** We say that a solution $f$, some $\vec{p}, \vec{p}' \in \mathbb{N}^n$, and some $h, h' \in \mathbb{N}$ exhibit a *population paradox* if there are two states $i \ne j$ such that $p_i' \ge p_i, p_j' \le p_j, f_i(\vec{p}', h') < f_i(\vec{p}, h)$, and $f_j(\vec{p}', h') > f_j(\vec{p}, h)$, or, in words, if state $i$ loses seats and $j$ wins seats even though $i$'s population weakly grew and $j$'s population weakly shrunk. A solution $f$ is *population monotone* if it exhibits no population paradoxes for any $\vec{p}, \vec{p}', h, h'$. By setting $\vec{p} = \vec{p}'$, one easily verifies that population monotonicity implies house monotonicity.

Note that the apportionment literature often considers two components of the quota axiom separately: *lower quota* ("$f_i(\vec{p}, h) \ge \lfloor q_i \rfloor$") and *upper quota* ("$f_i(\vec{p}, h) \le \lfloor q_i \rfloor$"). Also note that our definition of population monotonicity, taken from Robinson and Ullman (2010), is slightly weaker than the definition of other authors, whose violation we describe in the introduction. All results extend to this alternative notion of *relative population monotonicity* (Robinson and Ullman, 2010): the proof of Theorem 1 immediately applies, and the proof of Theorem 2 is easy to adapt. Our results also continue to apply if one weakens population monotonicity by requiring that $h' = h$.

Finally, we will define randomized apportionment methods. One potential definition, used by Grimmett (2004), is a function that for each $\vec{p}$ and $h$ specifies a probability distribution over seat allocations $(a_i)_{i \in N}$. For us, an apportionment method is instead a random process that determines an entire (deterministic) apportionment solution, i.e., apportionments for all population profiles $\vec{p}$ and house sizes $h$. The advantage of this definition is that it allows us to formulate axioms relating these different apportionments. We will specify our apportionment methods by giving two components: first, a probability distribution for selecting some outcome $\omega$ from some suitable set $\Omega$ of possible outcomes; and, second, the apportionment solution $F^\omega$ parameterized by $\omega$. We will refer to such an apportionment method as $F$, leaving the distribution over $\omega$ implicit. We treat an apportionment method $F$ as a solution-valued random variable, so that $F(\vec{p}, h)$ refers to the method's random apportionment for $\vec{p}, h$ and $F_i(\vec{p}, h)$ refers to the random number of seats apportioned to state $i$. (We can ignore the measure-theoretic complications of this statement as long as, for each $\vec{p}, h$, the random apportionment $F^\omega(\vec{p}, h)$ is a valid random variable, which is the case for all natural constructions following the two-component
<table><caption>Table 1: Populations and standard quotas for three population profiles, used in showing that population monotonicity and quota are incompatible. The house size is $h = 10$.</caption><thead><tr><th rowspan="2">state <i>i</i></th><th colspan="2">profile <i>p</i><sup>A</sup></th><th colspan="2">profile <i>p</i><sup>B</sup></th><th colspan="2">profile <i>p</i><sup>C</sup></th></tr><tr><th><i>p</i><sub><i>i</i></sub><sup>A</sup></th><th><i>q</i><sub><i>i</i></sub><sup>A</sup></th><th><i>p</i><sub><i>i</i></sub><sup>B</sup></th><th><i>q</i><sub><i>i</i></sub><sup>B</sup></th><th><i>p</i><sub><i>i</i></sub><sup>C</sup></th><th><i>q</i><sub><i>i</i></sub><sup>C</sup></th></tr></thead><tbody><tr><td>1</td><td>824</td><td>8.24</td><td>824</td><td>6.99</td><td>824</td><td>9.02</td></tr><tr><td>2</td><td>44</td><td>0.44</td><td>44</td><td>0.37</td><td>1</td><td>0.01</td></tr><tr><td>3</td><td>44</td><td>0.44</td><td>44</td><td>0.37</td><td>1</td><td>0.01</td></tr><tr><td>4</td><td>44</td><td>0.44</td><td>44</td><td>0.37</td><td>44</td><td>0.48</td></tr><tr><td>5</td><td>44</td><td>0.44</td><td>222</td><td>1.88</td><td>44</td><td>0.48</td></tr></tbody></table>

structure.) Our axioms, described in the next paragraph, constrain both the random behavior of $F$ and the consistency of any solution $F^\omega$ in $F$'s support across inputs.

A method $F$ satisfies *ex ante proportionality* if, for any $\vec{p}, h$ and for any state $i$, $i$'s expected number of seats equals $i$'s standard quota, i.e., if $\mathbb{E}[F_i(\vec{p}, h)] = q_i$, where the expected value is over the random choice of apportionment solution. A method $F$ satisfies *quota, house monotonicity*, or *population monotonicity* if all solutions in the method's support satisfy the respective axiom. In this paper, we mainly search for apportionment methods that combine quota and ex ante proportionality—the two axioms obtained by Grimmett (2004)—with either population or house monotonicity.

# 3 Population Monotonicity

## 3.1 Population Monotonicity Is Incompatible with Quota

We begin by showing that no apportionment method satisfies population monotonicity, quota, and ex ante proportionality. In fact, quota and population monotonicity alone are incompatible: We will show that no solution satisfies these two axioms. Since a method satisfying quota and population monotonicity would be a random choice over such solutions, no such method exists either.

At first glance, the incompatibility of quota and population monotonicity might seem to follow from existing results, but these results implicitly make assumptions that are not appropriate for randomized apportionment. Indeed, Balinski and Young (1982), who originally proved this incompatibility, as well as variations of their proof (Robinson and Ullman, 2010; El-Helaly, 2019) all assume what Robinson and Ullman (2010) call the *order-preserving property*, i.e., if state $i$ has strictly larger population than state $j$, then $i$ must receive at least as many seats as $j$. This property is usually proved as a consequence of neutrality together with population monotonicity.

While the order-preserving property is reasonable for developing deterministic apportionment methods, it is not desirable for the component solutions of a randomized apportionment method. This is clear for $h = 1$: The order-preserving property would mean that only the very largest state(s) can get a seat with positive probability; by contrast, the strength of randomization is that it allows us to allocate the seat to smaller states with some positive probability. To our knowledge, the existence of quota and population monotone solutions without the assumption of the order-preserving property was an open problem.

**Theorem 1** No (deterministic) apportionment solution satisfies population monotonicity and quota.

*Proof.* Fix a set of 5 states, and let $f$ be a solution satisfying quota. We will show that $f$ must violate population monotonicity by analyzing three types of population profiles, which are given
in Table 1, all for house size $h = 10$. The starting profile is $\vec{p}^A$ in this table. By quota, state 1 must receive either 8 or 9 seats on this profile, but we will show that either choice leads to a violation of population monotonicity: First, we show that allocating 9 seats implies a violation of population monotonicity with respect to profile $\vec{p}^B$; second, we show that allocating 8 seats contradicts population monotonicity with respect to $\vec{p}^C$.

*Allocating 9 seats contradicts population monotonicity.* Suppose that $f_1(\vec{p}^A, 10) = 9$. Then, the remaining seat must be given to either state 2, 3, 4, or 5. Without loss of generality, we may assume that $f(\vec{p}^A, 10) = (9, 0, 0, 0, 1)$.

Next, consider the profile $\vec{p}^B$. Since quota prevents us from allocating more than 7 seats to state 1 or more than 2 seats to state 5, at least one of the states 2, 3, and 4 must receive a seat on $\vec{p}^B$. Thus, this state's allocation strictly increases from its allocation of zero seats on $\vec{p}^A$, even though the state's population has not changed. Moreover, state 1 can receive at most 7 seats on this profile by quota, which is strictly below the 9 seats on $\vec{p}^A$, and state 1's population has also remained the same. But population monotonicity forbids there to be a pair of states with unchanged population, such that one gains a seat and the other loses a seat. Hence, if state 1 receives 9 seats on $\vec{p}^A$, then $f$ violates population monotonicity.

*Allocating 8 seats contradicts population monotonicity.* Now, suppose that $f_1(\vec{p}^A, 10) = 8$. The remaining two seats must be given to two states out of 2, 3, 4, and 5; without loss of generality, we may assume that $f(\vec{p}^A, 10) = (8, 0, 0, 1, 1)$.

On profile $\vec{p}^C$, quota implies that state 1 receives at least 9 seats—strictly more than the 8 given on $\vec{p}^A$ even though the population has not changed. Given that there is at most one more seat to hand out, at least one state out of 4 and 5 must receive zero seats on $\vec{p}^C$, which is a strict reduction with respect to $\vec{p}^A$ even though the state's population is the same. Thus, allocating 8 seats to state 1 on $\vec{p}^A$ also leads to a violation of population monotonicity.

Since both possible choices for $f_1(\vec{p}^A, 10)$ imply a monotonicity violation, no solution can satisfy both quota and population monotonicity. □

## 3.2 A Population Monotone and Ex Ante Proportional (But Not Quota) Method

The incompatibility between population monotonicity and quota leaves open whether there are apportionment methods satisfying population monotonicity and ex ante proportionality. The answer is positive, and we construct a method satisfying both axioms in the following.

Since population monotonicity relates a solution's result for one input with those for infinitely many other inputs, it highly constrains the shape of population monotone solutions. In fact, under widely assumed regularity conditions, population monotone solutions are exactly characterized (Balinski and Young, 1982) by the class of divisor methods (for consistency with our terminology, divisor solutions), which will inspire our randomized method. A divisor solution is defined by a divisor criterion, which is a monotone increasing function $d: \mathbb{Z}_{\ge 0} \to \mathbb{R}_{\ge 0}$. (For instance, the Huntington-Hill solution is induced by $d(t) := \sqrt{t(t+1)}$.) For a population profile $\vec{p}$ and house size $h$, the divisor solution corresponding to $d$ can be calculated by considering the sets $\{p_i/d(t) \mid t \in \mathbb{Z}_{\ge 0}\}$ for each state $i$, determining the $h$ largest values across all sets, and allocating to each state $i$ a number of seats equal to how many of the $h$ largest values came from $i$'s set. When state populations change, the values $p_i/d(t)$ evolve in a way that ensures population monotonicity: if state $i$ grows and state $j$ shrinks, a value belonging to state $i$ might overtake a value belonging to $j$ that was originally larger, but none of $j$'s values can overtake any of $i$'s values. As a result, $i$'s number of seats cannot decrease if $j$'s number of seats increases.

To avoid the order-preserving property (for reasons described in Section 3.1), we will (randomly) choose a different divisor criterion for each state, which leaves the above argument for population monotonicity intact. The question is how to sample these divisor criteria such that ex ante
<figure><img src="image_4.png" /><figcaption>Figure 2: Illustration of the population-monotone method in Theorem 2.</figcaption></figure>

proportionality holds. The answer lies in the properties of Poisson arrival processes: Across independent, scaled Poisson processes, which process yields the first arrival is distributed with probabilities that are proportional to the reciprocals of the scaling factors; and, since the interarrival times of the processes are memoryless, the same holds for each subsequent arrival. These properties allow us to randomly construct a “generalized divisor solution” such that the overall distribution satisfies population monotonicity and ex ante proportionality.

**Theorem 2** *There exists an apportionment method F that satisfies population monotonicity and ex ante proportionality.*

*Proof.* Which solution is randomly chosen by the method will depend on the values taken on by $n$ independent Poisson arrival processes with rate 1, which we define as our outcome $\omega$. We now construct the solution $F^\omega$ corresponding to any given $\omega$. For each state $i$, $\omega$ determines an infinite sequence $0 < x_1^i < x_2^i < \dots$ of arrival times. We will describe the apportionment given by $F^\omega$ on input $\vec{p}$ and $h$, which we illustrate in Fig. 2: First, we divide each arrival time $x_t^i$ by the corresponding state’s population, i.e., we set $y_t^i := x_t^i/p_i$. Second, we combine the $y_t^i$ for all $t$ and $i$ in a single arrival sequence $(z_1, i_1), (z_2, i_2), \dots$ labeled with states, i.e., each $(z_j, i_j)$ corresponds to some arrival $y_t^i$ for some $i$ and $t$, such that $z_j = y_t^i$ is the arrival time, $i_j = i$ is the agent label, and the $z_j$ are sorted in increasing order. Third, we allocate $|\{1 \le j \le h \mid i_j = i\}|$ many seats to each state $i$, i.e., a number of seats equal to how many among the $h$ smallest scaled arrival times belonged to $i$'s arrival process. This specifies the solution $F^\omega$, and, hence, the entire apportionment method $F$. Note that $F^\omega$ closely resembles a divisor solution, where state $i$'s set is $\{1/y_t^i \mid t \in \mathbb{Z}_{\ge 0}\} = \{p_i/x_t^i \mid t \in \mathbb{Z}_{\ge 0}\}$, i.e., where, for each state $i$, $t \mapsto x_t^i$ plays the role of a state-specific divisor criterion.

First, we show that $F$ satisfies ex ante proportionality. For this, fix some $\vec{p}$ and $h$. Then, the $\{y_t^i\}_{t \ge 1}$ for each $i$ are distributed as the arrival sequences of independent Poisson processes, where $i$'s arrival process has a rate of $p_i$. As stated by the coloring theorem for Poisson processes (Kingman, 1993, p. 53), our labeled arrival sequence $(z_j, i_j)$ has the same distribution as if we had sampled a Poisson arrival process $0 < z_1 < z_2 < \dots$ with arrival rate $\sum_{i \in N} p_i$ and had drawn each $i_j$ independently, choosing each $i \in N$ with probability proportional to $p_i$. Since the $z_j$ and $i_j$ are independent in this way, $F(\vec{p}, h)$ is distributed as if sampling $h$ states, with probability proportional to the states’ populations and with replacement. In particular, this implies ex ante proportionality.

It remains to show that $F$ satisfies population monotonicity. Fix an $\omega$, i.e., the $x_t^i$, as well as two inputs $\vec{p}, h$ and $\vec{p}', h'$, for which we will show that $F^\omega$ does not exhibit a population paradox. Denoting the inputs’ respective variables by $y_t^i, z_j$ and $y_t^{i'}, z_j'$, it is easy to see that, for all $i$ for which $p_i' \ge p_i$, $y_t^{i'} \le y_t^i$ for all $t$, and that, for all $i$ for which $p_i' \le p_i$, $y_t^{i'} \ge y_t^i$ for all $t$. Observe that each state $i$ receives a number of seats equal to the number of its scaled arrival times $y_t^i$
(resp., $y_t^{i'}$) that are at most $z_h$ (resp., $z_h'$).

Suppose that $z_h' \ge z_h$ (the reasoning for the case $z_h' \le z_h$ is symmetric). Then, whenever $y_t^i \le z_h$ for a state $i$ for which $p_i' \ge p_i$, then $y_t^{i'} \le y_t^i \le z_h \le z_h'$, which shows that $i$'s seat number must weakly increase. One verifies that this rules out a population paradox on $\vec{p}, h$ and $\vec{p}', h'$. Together with the symmetric argument for $z_h' \le z_h$, this establishes population monotonicity. $\square$

Clearly, the solutions' resemblance to divisor solutions enabled our proof of population monotonicity. At the same time, using different "divisor criteria" for different states allowed to avoid the order-preserving property, which would have prevented ex ante proportionality as described in Section 3.1. Less satisfying is that, whereas classic divisor criteria satisfy bounds such as $t \le d(t) \le t+1$, the "divisor criteria" used in the last theorem do not satisfy any such bounds. As a result, solutions are likely to substantially deviate from proportionality ex post. An interesting question for future work is whether Theorem 2 can be strengthened to additionally satisfy lower quota or upper quota.

# 4 House Monotonicity

While we cannot obtain population monotonicity without giving up on quota, we now propose an apportionment method that combines *house monotonicity* with quota and ex ante proportionality.

## 4.1 Examples of Pitfalls

An intuitive strategy for constructing a house monotone randomized apportionment method is to do it inductively, seat-by-seat. Thus, we would need a strategy for extending a method that works for all house sizes $h' \le h$ to a method that also works for house size $h+1$. In this section, we give examples suggesting that this does not work, by showing that some reasonable methods cannot be extended without violating quota or ex ante proportionality. This motivates a search for a more "global" strategy for constructing a house-monotone method.

**Example 1.** Our first example will show that there are apportionments for a given $h$ that satisfy quota, but that are "toxic" in that they can never be chosen by a house monotone solution which satisfies quota. Suppose that we have four states with populations $\vec{p} = (1, 2, 1, 2)$. The distribution that we will consider is the one given by Grimmett's method (Grimmett, 2004) (as described in the introduction) for these inputs. Let $h=2$. Observe that, if the random permutation chosen by Grimmett's method is identity and if furthermore $U > 2/3$, then Grimmett's method will return the allocation $(1, 0, 1, 0)$. But we will show that no solution $f$ such that $f(\vec{p}, 2) = (1, 0, 1, 0)$ can satisfy house monotonicity and quota. Indeed, if $f$ is house monotone, then at least one out of state 2 or state 4 must still be given zero seats by $f$ when $h=3$, but quota requires that both states receive exactly one seat when $h=3$. It follows that Grimmett's method, the apportionment method of Aziz et al. (2019), or any other method satisfying quota and whose support contains solutions $f$ with $f(\vec{p}, 2) = (1, 0, 1, 0)$, cannot be house monotone.

Thus, a first challenge that any quota and house monotone method must overcome is to never produce a toxic apportionment for a specific $h$ that cannot be extended to all larger house sizes in a house monotone and quota-compliant way. Still (1979) and later Balinski and Young (1979) give a characterization of non-toxic apportionments, but we found no way of transforming this characterization into an apportionment method that would be ex ante proportional.

**Example 2.** Our second example shows that, even if there are no toxic apportionments in the support of a distribution, the wrong distribution over apportionments might still lead to violations of one of the axioms. Let there be four states with populations $\vec{p} = (45, 25, 15, 15)$
and let $h = 3$; thus, the standard quotas are $(1.35, 0.75, 0.45, 0.45)$. We consider the following distribution over allocations:

$$ \vec{a} = \begin{cases} (2, 1, 0, 0) & \text{with probability } 35\%, \quad (1, 1, 0, 1) \text{ with probability } 20\%, \text{ and} \\ (1, 1, 1, 0) & \text{with probability } 20\%, \quad (1, 0, 1, 1) \text{ with probability } 25\%. \end{cases} $$

As we show in Appendix EC.1, none of these allocations is toxic, and the distribution can be part of an apportionment method in which all three axioms hold for $\vec{p}$ and all $h' \le 3$. Nevertheless, we show in the following that any apportionment method $F$ that satisfies house monotonicity and quota and that has the above distribution for $F(\vec{p}, 3)$ must violate ex ante proportionality. Indeed, fix such an $F$. On the one hand, note that, for $h = 4$, state 2's standard quota is $4 \cdot \frac{25}{100} = 1$, so any quota apportionment must give the state 1 seat. Since any solution $f$ in the support of $F$ satisfies house monotonicity and quota by assumption, any $f$ such that $f(\vec{p}, 3) = (1, 0, 1, 1)$ must satisfy $f(\vec{p}, 4) = (1, 1, 1, 1)$. Thus, with at least 25% probability, $F_1(\vec{p}, 4) = 1$. On the other hand, since state 1's standard quota for $h = 4$ is $1.8 \le 2$, $F_1(\vec{p}, 4) \le 2$ holds deterministically, by quota. It follows that $E[F_1(\vec{p}, 4)] \le 25\% \cdot 1 + 75\% \cdot 2 = 1.75 < 1.8$, which means that $F$ must violate ex ante proportionality as claimed. To avoid this kind of conflict between house monotonicity, ex ante proportionality, and quota, the distribution of $F(\vec{p}, 3)$ must allocate at least 5% combined probability to the allocations $(2, 0, 1, 0)$ and $(2, 0, 0, 1)$, which to us is not obvious other than by considering the specific implications on $h = 4$ as above.

## 4.2 Cumulative Rounding

The examples of the last section showed that it is difficult to construct house monotone apportionment methods seat-by-seat. In this section, we develop an approach that is able to explicitly take into account how rounding decisions constrain each other across house sizes. Our approach will be based on dependent randomized rounding in a bipartite graph that we construct. First, we state the main theorem by Gandhi et al. (2006):

**Theorem 3 (Gandhi et al.)** Let $(A \cup B, E)$ be an undirected bipartite graph with bipartition $(A, B)$. Each edge $e \in E$ is labeled with a weight $w_e \in [0, 1]$. For each $v \in A \cup B$, we denote the fractional degree of $v$ by $d_v := \sum_{v \in e \in E} w_e$.

Then there is a random process, running in $O((|A| + |B|) \cdot |E|)$ time, that defines random variables $X_e \in \{0, 1\}$ for all $e \in E$ such that the following properties hold:

**Marginal distribution:** for all $e \in E$, $E[X_e] = w_e$,

**Degree preservation:** for all $v \in A \cup B$, $\sum_{v \in e \in E} X_e \in \{[d_v], [d_v]\}$, and

**Negative correlation:** for all $v \in A \cup B$ and $S \subseteq \{e \in E \mid v \in e\}$, $\mathbb{P}[\bigwedge_{e \in S} X_e = 1] \le \prod_{e \in S} w_e$ and $\mathbb{P}[\bigwedge_{e \in S} X_e = 0] \le \prod_{e \in S} (1 - w_e)$.

If $X_e = 1$ for an edge $e$, we say that $e$ gets rounded up, and if $X_e = 0$ then $e$ gets rounded down. We do not use negative correlation in our apportionment results, but it is crucial in many applications of dependent rounding since it implies that linear combinations of the shape $\sum_{e \in S} a_e X_e$ for some $a_e \in [0, 1]$ obey Chernoff concentration bounds (Panconesi and Srinivasan, 1997).

To see the connection to apportionment, let $\vec{p}$ be a population profile. Then to warm up, the problem of apportioning a single seat can be easily cast as dependent rounding in a bipartite graph: Indeed, let $A$ consist of a single special node $a$ and let $B$ contain a node $b_i$ for each state $i$. We draw an edge $e = \{a, b_i\}$ with weight $w_e = p_i / \sum_{j \in N} p_j$ for each state $i$. Apply dependent rounding to this star graph. Then $a$'s fractional degree of exactly 1 means that, by degree preservation, exactly one edge $\{a, b_i\}$ gets rounded up, which we interpret as the seat
being allocated to state $i$. Moreover, marginal distribution ensures that each state receives the seat with probability proportional to its population. This shows that randomized rounding can naturally express ex ante proportionality, which will become a useful building block in the following.

Next, we will expand our construction to multiple house seats, and to satisfying house monotonicity across different house sizes. The most natural way is to duplicate the star graph from the last paragraph, once per house size $h = 1, 2, \dots$ with nodes $a^h, \{b_i^h\}_{i \in N}$ and edges $\{{a^h, b_i^h}\}_{i \in N}$. (In this intuitive exposition, we will not consider any explicit upper bound on the house sizes. Our formal result in Theorem 5 will round a finite graph but this will suffice to obtain house monotonicity for all house sizes $h \in \mathbb{N}$.) If $\{a^h, b_i^h\}$ gets rounded up in the $h$-th copy of the star graph, we interpret this as the $h$-th seat going to state $i$. In other words, we determine how many seats get apportioned to state $i$ for a house size $h$ by counting how many edges $\{a^{h'}, b_i^{h'}\}$ got rounded up across all $h' \le h$. This construction automatically satisfies house monotonicity, and satisfies ex ante proportionality by the marginal distribution property, but may violate quota by arbitrary amounts.

To explain how randomized rounding might be useful for guaranteeing quota, let us give a few details on how Gandhi et al.'s pipage rounding procedure randomly rounds a bipartite graph. In each step, pipage rounding selects either a cycle or a maximal path consisting of edges with fractional weights in $(0,1)$. The edges along this cycle or path are then alternatingly labeled "even" or "odd", which is possible because each cycle in a bipartite graph has an even number of edges. Depending on a biased coinflip and appropriate numbers $\alpha, \beta > 0$, the algorithm either (1) increases all odd edge weights by $\alpha$ and decreases all even edge weights by $\alpha$, or (2) decreases all odd edge weights by $\beta$ and increases all even edge weights by $\beta$. In this process, more and more edge weights become zero or one, which determines the $X_e$ once no fractional edges remain.

The cycle/path rounding steps in pipage rounding represent an opportunity to couple the seat-allocation decisions across $h$, in a way that ultimately will allow us to guarantee quota. In our current graph consisting of disjoint stars, there are no cycles and the maximal paths are always pairs of edges $\{a^h, b_i^h\}, \{a^h, b_j^h\}$ for two states $i, j$ and some $h$. Thus, pipage rounding correctly anti-correlates the decision of giving the $h$-th seat to state $i$ and the decision of giving the $h$-th seat to state $j$, but decisions for different seats remain independent. To guarantee quota, increasing (resp., decreasing) the probability of the $h$-th seat going to state $i$ should also decrease (resp., increase) the probability of some nearby seats $h'$ going to state $i$ and increase (resp., decrease) the probability of seats $h'$ going to some other state $j$. The difficulty is to choose these $h'$ and $j$ to provide quota, which is particular tricky since, in the course of running pipage rounding, some of the edge weights will be rounded to zero and one and no longer be available for paths or cycles.

Not only are we able to use pipage rounding to guarantee quota, but we will do so through a general construction that adds quota-like guarantees to an arbitrary instance of repeated randomized rounding; we refer to this technique as *cumulative rounding*. In the following statement, the "time steps" $t$ take the place of our possible house sizes $h$.

**Theorem 4** Let $(A \cup B, E)$ be an undirected bipartite graph. For each time step $t = 1, \dots, T$, consider a set of edge weights $\{w_e^t\}_{e \in E}$ in $[0, 1]$ for this bipartite graph. For each $v \in A \cup B$ and $1 \le t \le T$, we denote the fractional degree of $v$ at time $t$ by $d_v^t := \sum_{v \in e \in E} w_e^t$.

Then there is a random process, running in $O(T^2 \cdot (|A| + |B|) \cdot |E|)$ time, that defines random variables $X_e^t \in \{0, 1\}$ for all $e \in E$ and $1 \le t \le T$, such that the following properties hold for all $1 \le t \le T$. Let $D_v^t := \sum_{v \in e \in E} X_e^t$ denote the random degree of $v$ at time $t$.

**Marginal distribution:** for all $e \in E$, $\mathbb{E}[X_e^t] = w_e^t$,

**Degree preservation:** for all $v \in A \cup B$, $D_v^t \in \{\lfloor d_v^t \rfloor, \lceil d_v^t \rceil\}$,
**Negative correlation:** for all $v \in A \cup B$ and $S \subseteq \{e \in E | v \in e\}$, $\mathbb{P}[\Lambda_{e \in S} X_e^t = 1] \le \prod_{e \in S} w_e^t$ and $\mathbb{P}[\Lambda_{e \in S} X_e^t = 0] \le \prod_{e \in S} (1 - w_e^t)$,

**Cumulative degree preservation:** for all $v \in A \cup B$, $\sum_{t'=1}^t D_v^{t'} \in \{\lfloor \sum_{t'=1}^t d_v^{t'} \rfloor, \lceil \sum_{t'=1}^t d_v^{t'} \rceil\}$.

The first three properties could be achieved by applying Theorem 3 in each time step independently. Cumulative rounding correlates these rounding processes such that cumulative degree preservation (a generalization of quota) is additionally satisfied.

## 4.3 House Monotone, Quota-Compliant, and Ex Ante Proportional Apportionment

Before we prove Theorem 4, we will explain how cumulative rounding can be used to construct an apportionment method that is house monotone and satisfies quota and ex ante proportionality.

None of these three axioms connects the outcomes at different population profiles $\vec{p}$ and so it suffices to consider them independently. Thus, let us fix a population profile $\vec{p}$. Denote the total population by $p := \sum_{i \in N} p_i$. The behavior of a house monotone solution on inputs with profile $\vec{p}$ and arbitrary house sizes can be expressed through what we call an infinite seat sequence, an infinite sequence $\alpha = \alpha_1, \alpha_2, \dots$ over the states $N$. We will also define finite seat sequences, which are sequences $\alpha = \alpha_1, \dots, \alpha_p$ of length $p$ over the states. Either sequence represents that, for any house size $h$ (in the case of a finite seat sequence: $h \le p$), the sequence apportions $a_i(h) := \{1 \le h' \le h | \alpha_{h'} = i\}$ seats to each state $i$. We can naturally express the quota axiom for seat sequences: $\alpha$ satisfies quota if, for all $h$ ($h \le p$ if $\alpha$ is finite) and all states $i$, we have $a_i(h) \in \{\lfloor h p_i / p \rfloor, \lceil h p_i / p \rceil\}$.

The main obstacle in obtaining a house monotone method via cumulative rounding is that we can only apply cumulative rounding to a finite number $T$ of copies, whereas the quota axiom must hold for all house sizes $h \in \mathbb{N}$. However, it turns out that for our purposes of satisfying quota, we can treat the allocation of seats $1, 2, \dots, p$ separately from the allocation of seats $p+1, \dots, 2p$, the allocation of seats $2p+1, \dots, 3p$, and so forth. The reason is that, when $h$ is a multiple $kp$ of $p$ (for some $k \in \mathbb{N}$), each state $i$'s standard quota is an integer $kp_i$. Thus, any solution that satisfies quota is forced to choose exactly the allocation $(kp_1, \dots, kp_n)$ for house size $h$. At this point, the constraints for satisfying quota and house monotonicity reset to what they were at $h=1$. We make this precise in the following lemma, proved in Appendix EC.2:

**Lemma 1** An infinite seat sequence $\alpha$ satisfies quota iff it is the concatenation of infinitely many finite seat sequences $\beta^1, \beta^2, \beta^3, \dots$ of length $p$ each satisfying quota, i.e.,

$$ \alpha = \beta_1^1, \beta_2^1, \dots, \beta_p^1, \beta_1^2, \beta_2^2, \dots, \beta_p^2, \beta_1^3, \dots $$

This lemma allows us to apply cumulative rounding to only $T = p$ many copies of a star graph. Then, cumulative rounding produces a random matching that encodes a finite seat sequence satisfying quota, and Lemma 1 shows that the infinite repetition of this finite sequence describes an infinite seat sequence satisfying quota. This implies the existence of an apportionment method satisfying all three axioms we aimed for. The formal proof is in Appendix EC.2.

**Theorem 5** There exists an apportionment method $F$ that satisfies house monotonicity, quota, and ex ante proportionality.

**Implications for deterministic methods** Our construction also increases our understanding of deterministic apportionment solutions satisfying house monotonicity and quota: Indeed, the possible roundings of the bipartite graph constructed for cumulative rounding (plus some minor modifications, described in the proof) turn out to correspond one-to-one to the finite seat sequences satisfying quota. Together with Lemma 1, this gives a characterization of all seat sequences that satisfy quota, providing a graph-theoretic alternative to the characterizations by Still (1979) and Balinski and Young (1979).
**Theorem 6** For any population profile $\vec{p}$, we can construct a bipartite graph whose perfect matchings are in one-to-one correspondence with the finite seat sequences satisfying quota.

The proof is deferred to Appendix EC.2. Together with Lemma 1 this characterizes the set of infinite seat sequences satisfying quota and hence the apportionment solutions satisfying house monotonicity and quota.

A qualitative difference to the previous characterizations (Still, 1979; Balinski and Young, 1979) of apportionment solutions satisfying house monotonicity and quota is that the matchings allow for a *geometric* description as the corner points of the bipartite graph's matching polytope. Since a fractional matching assigning each edge $\{a, b_i\}$ a weight of $p_i/p > 0$ lies in the interior of this polytope of perfect fractional matchings, one immediate consequence of this characterization (equivalently, of ex ante proportionality in Theorem 5) is that, for each state $i$ and $h \in \mathbb{N}$, there is a house monotone and quota-compliant solution that assigns the $h$-th seat to $i$. To our knowledge, this result is not obvious based on the earlier characterizations. More generally, the polytope characterization might be useful in answering questions such as “For a set of pairs $(h_1, i_1)$, $(h_2, i_2)$, ..., $(h_t, i_t)$, is there a population-monotone and quota-compliant solution that assigns the $h_j$-th seat to state $i_j$ for all $1 \le j \le t$?” To answer this question, one can remove the nodes $a^{h_j}$ and $b_{ij}^{h_j}$ from the graph (simulating that they got matched) and check whether the remaining graph still permits a perfect matching, say, with the help of Hall's marriage theorem (Hall, 1935). Finally, our formulation allows to optimize linear objectives over the space of solutions satisfying quota and house monotonicity. For example, such an optimization formulation might highlight natural quota-compliant and house monotone solutions other than the one by Balinski and Young (1975).

**Computation** Before we prove the cumulative rounding result in Section 5, let us quickly discuss computational considerations of our house-monotone apportionment method. While it is possible to run dependent rounding on the constructed graph (for a given population profile $\vec{p}$), the running time would scale in $O(p^2 n^2)$, and the quadratic dependence on the total population $p$ might be prohibitive. In practice, we see two ways to avoid this computational cost:

First, one might often not require a solution that is house monotone on all possible house sizes $h \in \mathbb{N}$; instead, it might suffice to rule out Alabama paradoxes for house sizes up to an upper bound $h_{max}$. In this case, it suffices to apply cumulative rounding on $h_{max}$ many copies of the graph, leading to a much more manageable running time of $O(h_{max}^2 n^2)$.

A second option would be to apply cumulative rounding on all $p$ copies of the graph, but to stop pipage rounding once all edge weights in the first $h$ copies of the graph are integral, even if edge weights for higher house sizes are still fractional. This would allow to return an apportionment for inputs $\vec{p}, h$ while randomly determining not a single house-monotone solution, but a conditioned distribution $F^c$ over house-monotone solutions, all of which agree on the apportionment for $\vec{p}$ and $h$. Since all solutions are house monotone, the expected number of seats for a party will always monotonically increase in $h$ across the conditioned distribution. Should it become necessary to determine apportionments for larger house sizes, one can simply continue the cumulative-rounding process where it left off. Since the pipage rounding used to prove Theorem 4 leaves open which cycles or maximal paths get rounded next, it seems likely that one can deliberately choose cycles/paths such that the apportionment for the first $h$ seats is determined in few rounds.

# 5 Proof of Cumulative Rounding

We will now prove Theorem 4 on cumulative rounding. Our proof will construct a weighted bipartite graph including $T$ many copies of $(A \cup B, E)$, connected by appropriate additional edges
<figure><img src="image_5.png" /><figcaption>Figure 3: Interpretation of each edge being rounded up in the constructed graph, for arbitrary nodes $v, v' \in A \cup B$ and $1 \le t \le T$. The correctness of this characterization will be shown along the proof of Theorem 4, specifically in the sections on degree preservation and cumulative degree preservation.</figcaption></figure>

and nodes, and then applying dependent rounding to this constructed graph. The additional edges and vertices ensure that if too many edges adjacent to some node $v$ are rounded up in one copy of the graph, then this is counterbalanced by rounding down edges adjacent to $v$ in another copy.

**Construction 7.** Let $(A \cup B, E)$, $T$, and $\{w_e^t\}_{e,t}$ be given as in Theorem 4. We construct a new weighted, undirected, and bipartite graph as follows: For each node $v \in A \cup B$ and for each $t = 1, \dots, T$, create four nodes $v^t$, $\bar{v}^t$, $\bar{v}^t$, and $v^{t+1}$; furthermore, create a node $v^{0:1}$ for each node $v$. For each $\{a, b\} \in E$ and $t = 1, \dots, T$, connect the nodes $a^t$ and $b^t$ with an edge of weight $w_{\{a,b\}}^t$. Additionally, for each node $v \in A \cup B$ and each $t = 1, \dots, T$, insert edges with the following weights:

$$v^{t+1:t} \frac{v^t \left| 1 - d_v^t + \lfloor d_v^t \rfloor \right.}{\sum_{t'=1}^{t-1} d_v^{t'} - \lfloor \sum_{t'=1}^{t-1} d_v^{t'} \rfloor} \frac{\bar{v}^t \left| d_v^t - \lfloor d_v^t \rfloor \right.}{1 - \sum_{t'=1}^{t-1} d_v^{t'} + \lfloor \sum_{t'=1}^{t-1} d_v^{t'} \rfloor} v^{t:t+1}$$

Before we go into the proof, we give in Fig. 3 an interpretation for what it means for each edge in the constructed graph to be rounded up. One can easily verify that, under the (premature) assumption that cumulative rounding satisfies marginal distribution, degree preservation, and cumulative degree preservation, the edge weights coincide with the probabilities of each interpretation's event. We want to stress that it is not obvious that these descriptions will indeed be consistent for any dependent rounding of the constructed graph, and we will not make use of these descriptions in the proof of Theorem 4. Instead, the characterizations will follow from intermediate results in the proof. We give these interpretations here to make the construction seem less mysterious. We begin the formal analysis of the construction with a sequence of simple observations about the constructed graph (proofs are in Appendix EC.3).

**Lemma 2** The graph produced by Construction 7 is bipartite.
**Lemma 3** All edge weights lie between 0 and 1.

**Lemma 4** For each node $v \in A \cup B$, the following table gives the fractional degrees of various nodes in the constructed graph, all of which are integer:

<table><thead><tr><th>nodes</th><th>fractional degree</th></tr></thead><tbody><tr><td>$v^t$ ($\forall 1 \le t \le T$)</td><td>$\lfloor d_v^t \rfloor + 1$</td></tr><tr><td>$\bar{v}^t$ ($\forall 1 \le t \le T$)</td><td>$\lfloor \sum_{t'=1}^t d_v^{t'} \rfloor - \lfloor \sum_{t'=1}^{t-1} d_v^{t'} \rfloor - \lfloor d_v^t \rfloor + 1$</td></tr><tr><td>$\bar{v}^t$ ($\forall 1 \le t \le T$)</td><td>1</td></tr><tr><td>$v^{t:t+1}$ ($\forall 1 \le t \le T-1$)</td><td>1</td></tr><tr><td>$v^{0:1}$</td><td>0</td></tr></tbody></table>

*Proof of Theorem 4.* We define cumulative rounding as the random process that follows Construction 7 and then applies dependent rounding (Theorem 3) to the constructed graph, which is valid since the graph is bipartite and all edge weights lie in $[0, 1]$ (Lemmas 2 and 3). For an edge $e$ in the constructed graph, let $\hat{X}_e$ be the random variable indicating whether dependent rounding rounds it up or down. For any edge $\{a, b\} \in E$ in the underlying graph and some $1 \le t \le T$, we define the random variable $X_{\{a,b\}}^t$ to be equal to $\hat{X}_{\{a^t, b^t\}}$. Recall that we defined $D_v^t = \sum_{v \in e \in E} X_e^t$.

To prove the theorem, we have to bound the running time of this process, and provide the four guaranteed properties: marginal distribution, degree preservation, negative correlation, and cumulative degree preservation, out of which the last property takes by far the most work.

**Running time.** Without loss of generality, we may assume that each vertex $v \in A \cup B$ is incident to at least one edge, since, otherwise, we could remove this vertex in a preprocessing step. From this, it follows that $|E| \in \Omega(|A| + |B|)$. Constructing the graph takes $O(T|E|)$ time, which will be dominated by the time required for running dependent rounding on the constructed graph. The constructed graph has $(1 + 4T)(|A| + |B|) \in O(T(|A| + |B|))$ nodes and $T|E| + 4T(|A| + |B|) \in O(T|E|)$ edges. Since the running time of dependent rounding scales in the product of the number of vertices and the number of edges, our procedure runs in $O(T^2(|A| + |B|)|E|)$ time, as claimed.

**Marginal distribution.** For an edge $\{a, b\} \in E$ and $1 \le t \le T$, $\mathbb{E}[X_{\{a,b\}}^t] = \mathbb{E}[\hat{X}_{\{a^t, b^t\}}] = w_{\{a,b\}}^t$, where the last equality follows from the marginal-distribution property of dependent rounding.

**Degree preservation.** Fix a node $v \in A \cup B$ and $1 \le t \le T$. By Lemma 4, the fractional degree of $v^t$ is $\lfloor d_v^t \rfloor + 1$, and thus, by degree preservation of dependent rounding, exactly $\lfloor d_v^t \rfloor + 1$ edges adjacent to $v^t$ must be rounded up. The only of these edges that does not count into $D_v^t$ is $\{\bar{v}^t, v^t\}$; depending on whether this edge is rounded up or down, $D_v^t$ is either $\lfloor d_v^t \rfloor$ or $\lfloor d_v^t \rfloor + 1$. If $d_v^t$ is not integer, the latter number equals $\lfloor d_v^t \rfloor$, which proves degree preservation. Else, if $d_v^t$ is an integer, the edge weight of $\{\bar{v}^t, v^t\}$ is 1. Dependent rounding always rounds up edges with weight 1, which means that $D_v^t$ is definitely $\lfloor d_v^t \rfloor$ in this case. Thus, degree preservation holds in either case.

**Negative correlation.** Negative correlation for $v \in A \cup B$, $S \subseteq \{e \in E | v \in e\}$, and $1 \le t \le T$ directly follows from the negative-correlation property of dependent rounding for the node $v^t$ and the edge set $S' := \{\{v^t, (v')^t\} | \{v, v'\} \in S\}$.
<figure><img src="image_6.png" /><figcaption>Figure 4: Illustration of the counting argument for proving cumulative degree preservation. Edges in the figure are edges from the constructed graph, a superset of the edges in the rounded graph. Node color and shape indicate the set that a node belongs to, as indicated in the legend.</figcaption></figure>

**Cumulative degree preservation.** Fix a node $v \in A \cup B$ and $1 \le t \le T$. We will consider the “rounded version” of the constructed graph, i.e., the unweighted bipartite graph over the nodes of the constructed graph in which exactly those edges are present that got rounded up by the randomized rounding process. We define five sets of nodes in the rounded graph (Fig. 4):

$$V := \{v^{t'} | 1 \le t' \le t\} \qquad V' := \{(v')^{t'} | v' \in (A \cup B) \setminus \{v\}, 1 \le t' \le t\}$$
$$\bar{V} := \{\bar{v}^{t'} | 1 \le t' \le t\} \qquad \bar{V} := \{\bar{v}^{t'} | 1 \le t' \le t\} \qquad V' := \{v^{t:t+1} | 0 \le t' \le t\}$$

For any set of nodes $V_1$ in the rounded graph, we denote its neighborhood by $N(V_1)$, and we will write $deg(V_1)$ for the sum of degrees of $V_1$ in the rounded graph. For any two sets of nodes $V_1, V_2$, we write $cut(V_1, V_2)$ to denote the number of edges between $V_1$ and $V_2$ in the rounded graph.

Note that $\sum_{t'=1}^t D_v^{t'}$, which we must bound, equals $cut(V, V')$. We will bound this quantity by repeatedly using the following fact, which we refer to *pivoting*: For pairwise disjoint sets of nodes $V_0, V_1, V_2$, if $N(V_0) \subseteq V_1 \cup V_2$, then $deg(V_0) = cut(V_0, V_1) + cut(V_0, V_2)$. Since Lemma 4 gives us a clear view of the fractional degrees of nodes in the constructed graph, and since, by degree preservation, a node's degree in the rounded graph must equal the fractional degree whenever the latter is an integer, this property allows us to express cuts in terms of other cuts. Figure 4 illustrates which of these sets border on each other, and helps in following along with the derivation.

$$\begin{align*}
\sum_{t'=1}^{t} D_v^{t'} &= cut(V, V') \\
&= deg(V) - cut(V, \bar{V}) \tag*{(pivot $V_0 = V, V_1 = V', V_2 = \bar{V}$)} \\
&= t + \sum_{t'=1}^{t} \lfloor d_v^{t'} \rfloor - cut(V, \bar{V}) \tag*{(deg(V) = t + \sum_{t'=1}^{t} \lfloor d_v^{t'} \rfloor \text{ by Lemma 4)}} \\
&= t + \sum_{t'=1}^{t} \lfloor d_v^{t'} \rfloor - deg(\bar{V}) + cut(\bar{V}, \bar{V}) \tag*{(pivot $V_0 = \bar{V}, V_1 = V, V_2 = \bar{V}$)} \\
&= \sum_{t'=1}^{t} \lfloor d_v^{t'} \rfloor + cut(\bar{V}, \bar{V}) \tag*{(deg(\bar{V}) = t \text{ by Lemma 4)}} \\
&= \sum_{t'=1}^{t} \lfloor d_v^{t'} \rfloor + deg(\bar{V}) - cut(\bar{V}, V') \tag*{(pivot $V_0 = \bar{V}, V_1 = \bar{V}, V_2 = V'$)} \\
&= \sum_{t'=1}^{t} \lfloor d_v^{t'} \rfloor - cut(\bar{V}, V') + \sum_{t'=1}^{t} \left( \lfloor \sum_{t''=1}^{t'} d_v^{t''} \rfloor - \lfloor \sum_{t''=1}^{t'-1} d_v^{t''} \rfloor - \lfloor d_v^{t'} \rfloor + 1 \right) \tag*{(Lemma 4)} \\
&= \sum_{t'=1}^{t} \lfloor d_v^{t'} \rfloor - cut(\bar{V}, V') + \lfloor \sum_{t''=1}^{t} d_v^{t''} \rfloor - \sum_{t'=1}^{t} \lfloor d_v^{t'} \rfloor + t \tag*{(telescoping sum)} \\
&= \lfloor \sum_{t'=1}^{t} d_v^{t'} \rfloor + t - cut(\bar{V}, V').
\end{align*}$$
To bound cut($\overline{V}$, $V^*$) in the last expression, observe that $N(V^* \setminus \{v^{t:t+1}\}) \subseteq \overline{V}$, from which it follows that cut($\overline{V}$, $V^* \setminus \{v^{t:t+1}\}$) = deg($V^* \setminus \{v^{t:t+1}\}$) = $t-1$. Thus, cut($\overline{V}$, $V^*$) = $t-1 + 1\{\hat{X}_{\{\overline{v}^t, v^{t:t+1}\}}\}$, and we resume the above equality

$$ \sum_{t'=1}^{t} D_v^{t'} = \lfloor \sum_{t'=1}^{t} d_v^{t'} \rfloor + t - (t-1 + 1\{\hat{X}_{\{\overline{v}^t, v^{t:t+1}\}}\}) = \lfloor \sum_{t'=1}^{t} d_v^{t'} \rfloor + 1 - 1\{\hat{X}_{\{\overline{v}^t, v^{t:t+1}\}}\}. $$

If $\sum_{t'=1}^{t} d_v^{t'}$ is not an integer, the above shows that $\sum_{t'=1}^{t} D_v^{t'}$ is either the floor or ceiling of $\sum_{t'=1}^{t} d_v^{t'}$, establishing cumulative degree preservation. Else, if $\sum_{t'=1}^{t} d_v^{t'}$ is integer, note that the weight of the edge $\{\overline{v}^t, v^{t:t+1}\}$ in the constructed graph is 1. Since dependent rounding always rounds such edges up, $\sum_{t'=1}^{t} D_v^{t'} = \lfloor \sum_{t'=1}^{t} d_v^{t'} \rfloor$. This establishes cumulative degree preservation, the last of the properties guaranteed by the theorem. □

# 6 Other Applications of Cumulative Rounding

Our exploration of house monotone randomized apportionment led us to the more general technique of cumulative rounding, which we believe to be of broader interest. We next illustrate this by discussing additional applications.

## 6.1 Sortition of the European Commission

The European Commission is one of the main institutions of the European Union, in which it plays a role comparable to that of a government. The commission consists of one commissioner from each of the 27 member states, and each commissioner is charged with a specific area of responsibility. Since the number of EU member states has nearly doubled in the past 20 years, so has the size of the commission. Besides making coordination inside the commission less efficient, the enlargement of the commission has led to the creation of areas of responsibility much less important than others. Since the important portfolios are typically reserved for the largest member states, smaller states have found themselves with limited influence on central topics being decided in the commission.

To remedy this imbalance, Buchstein and Hein (2009) propose to reduce the number of commissioners to 15, meaning that only a subset of the 27 member states would send a commissioner at any given time. Which states would receive a seat would be determined every 5 years by a weighted lottery ("sortition"), in which states would be chosen with degressive proportional weights. Degressive means that smaller states get non-proportionately high weight; such weights are already used for apportioning the European parliament. The authors argue that by the law of large numbers, political representation on the commission would be essentially proportional to these weights in politically relevant time spans.

However, a follow-up simulation study by Buchstein et al. (2013) challenges this assertion on two fronts: (1) First, the authors find that their implementation of a weighted lottery chooses states with probabilities that deviate from proportionality to the weights in a way that is not analytically tractable (see Brewer and Hanif 1983, p. 24). (2) Second, and more gravely, their simulations undermine “a central argument in favor of legitimacy” in the original proposal, namely, that “in the long term, the seats on the commission would be distributed approximately like the share of lots” (Buchstein et al., 2013, own translation). From a mathematical point of view, the authors had overestimated the rate of concentration across the independent lotteries. Instead, in the simulation, it takes 30 lotteries (150 years) until there is a probability of 99% that all member states have sent at least one commissioner.

These serious concerns could be resolved by using cumulative rounding to implement the weighted lotteries. Specifically, we would again construct a star graph with a special node a and one node $b_i$ for each state i, setting $T$ to the desired number of consecutive lotteries. For
each $1 \le t \le T$, each edge $\{a, b_i\}$ would be weighted by $\frac{15 w_i}{\sum_{j \in N} w_j}$ where $w_j$ is state $j$'s degressive weight. Degree preservation on $a$ would ensure that in each lottery $t$, exactly 15 distinct states are selected. By marginal distribution, the selection probabilities would be exactly proportional to the degressive weights, resolving issue (1). Furthermore, cumulative degree preservation on the state nodes would eliminate issue (2). If we take the effective selection probabilities of Buchstein et al. (2013) as the states' weights, even the smallest states $i$ would have an edge weight $w_{\{a,b_i\}} \approx 0.187$. Then, cumulative quota prevents any state from getting rounded down in $11 = \lceil 2/0.187 \rceil$ consecutive lotteries: Indeed, fixing any $0 \le t_0 \le T - 11$,

$$ \sum_{t'=1}^{t_0+11} D_{b_i}^{t'} \ge \lfloor (t_0+11) 0.187 \rfloor \ge \lfloor t_0 0.187 \rfloor + 2 \ge \lfloor t_0 0.187 \rfloor + 1 \ge \sum_{t'=1}^{t_0} D_{b_i}^{t'} + 1, $$

which means that state $i$ must have been selected at least once between time $t_0 + 1$ and $t_0 + 11$. In political terms, this means that 55, not 150, years would be enough to deterministically ensure that each member state send a commissioner at least once in this period.

This cumulative rounding approach can accommodate weights that change across lotteries according to population projections (which Buchstein et al. do for some of their experiments), simply by choosing different weights across the copies of the star graph. It is necessary, however, that these population changes are known in advance, since no algorithm can guarantee cumulative degree preservation in an iterated apportionment setting in which population changes are observed online (i.e., just in time for the next apportionment to be made). This is shown by the following example: Let there be 4 states, and allocate a single seat per time step. At time $t = 1$, all four states have an equal population, thus an edge weight of $1/4$. Without loss of generality, the first seat goes to state 4. At time $t = 2$, state 4 disappears while states 1 through 3 have equal population, thus each an edge weight of $1/3$. Without loss of generality, the second seat goes to state 3. At time $t = 3$, states 3 and 4 have zero population whereas states 1 and 2 have equal population (i.e., an edge weight of $1/2$). Since states 1 and 2 have a cumulative quota of $1/4 + 1/3 + 1/2 > 1$, cumulative degree preservation requires both states to have at least one among the first three seats, but this is clearly impossible. We have presented this argument for an adaptive adversary; for a non-adaptive adversary, essentially the same argument shows that any online apportionment mechanism will violate cumulative degree preservation with probability at least $1/12$. Note that this impossibility holds even in the absence of marginal distribution and negative correlation. It is an intriguing question how one should design an online apportionment method that keeps violations from cumulative degree preservation at a minimum, and ensures that the cost or benefit of such deviations is fairly spread across the remaining states.

## 6.2 Repeated Allocation of Courses to Faculty Or Shifts to Workers

A common paradigm in fair division is to first create a fractional assignment between agents and resources, and to then implement this fractional assignment in expectation, through randomized rounding. Below, we describe a setting of allocating courses to faculty members in a university department, in which implementing a fractional assignment using cumulative rounding is attractive.

For a university department, denote its set of faculty members by $A$ and the set of possible courses to be taught by $B$. For each faculty member $a$ and course $b$, let there be a weight $w_{\{a,b\}} \in [0, 1]$ indicating how frequently course $b$ should be taught by $a$ on average. These numbers could be derived using a process such as probabilistic serial (Bogomolnaia and Moulin, 2001), the Hylland-Zeckhauser mechanism (Hylland and Zeckhauser, 1979), or the mechanisms by Budish et al. (2013), which would transform preferences of the faculty over which courses to teach into such weights. (Although these mechanisms are formulated for goods, they can be applied to bads when the number of bads allocated to each agent is fixed, as it is when allocating courses to faculty or shifts to workers.) We will allow arbitrary fractional degrees on the faculty
side (so one person can teach multiple courses) while assuming that the fractional degree of any course *b* is at most 1.

When applying cumulative rounding to this graph (using the same edge weights in each period) for consecutive semesters $1 \le t \le T$, we observe the following properties.

* Marginal distribution implies that, in each semester, faculty member *a* has a probability $w_{\{a,b\}}$ of teaching course *b*.

* Degree preservation on the course side means that a course is never taught by two different faculty members in the same semester.

* Degree preservation on the faculty side implies that a faculty member *a*'s teaching load does not vary by more than 1 between semesters; it is either the floor or the ceiling of *a*'s expected teaching load.

* Cumulative degree preservation on the course side ensures that courses are offered with some regularity. For example, if a course's fractional degree is $1/2$, it will be taught exactly once in every academic year (either in Fall or in Spring).

* Cumulative degree preservation on the faculty side allows for non-integer teaching load. For example, a faculty member with fractional degree 1.5 will have a "2-1" teaching load, i.e., they will teach 3 courses per year, either 2 in the Fall and one in the Spring or vice versa.

The same approach is applicable for matching workers to shifts.

One could also use cumulative rounding to repeatedly round a fractional assignment of general chores, such as the ones computed by the online platform spliddit.org (Goldman and Procaccia, 2014). In this case, a caveat is that (cumulative) degree preservation only ensures that the number of assigned chores is close to its expected number per time period, not necessarily the cost of the assigned chores. However, if many chores are allocated per time step, and if costs are additive, then an agent's per-timestep cost is well-concentrated, which follows from the negative-correlation property that permits the application of Chernoff concentration bounds (Panconesi and Srinivasan, 1997).

# 7 Discussion

Though our work is motivated by the application of apportioning seats at random, the technical questions we posed and addressed are fundamental to the theoretical study of apportionment. In a sense, any deterministic apportionment solution is "unproportional" — after all, its role is to decide which agents receive more or fewer seats than their standard quota. By searching for randomized methods satisfying ex ante proportionality, we ask whether these unproportional solutions can be combined (through random choice) such that these deviations from proportionality cancel out to achieve perfect proportionality, and whether this remains possible when we restrict the solutions to those satisfying subsets of the axioms population monotonicity, house monotonicity, and quota. Naturally, this objective pushes us to better understand the whole space of solutions satisfying these subsets of axioms, including the space's more extreme elements. Therefore, it is in hindsight not surprising that our work led to new insights for deterministic apportionment: a more robust impossibility between population monotonicity and quota (Theorem 1), an exploration of solutions generalizing the divisor solutions (Theorem 2), and a geometric characterization of house monotone and quota compliant solutions (Theorem 6).

Concerning the cumulative rounding technique introduced in this paper, we have only scratched the surface in exploring its applications. In particular, we hope to investigate whether cumulative
rounding can extend existing algorithmic results that use dependent rounding, and whether it can be used to construct new approximation algorithms. For both of these purposes, the negative-correlation property, which we have not used much so far, will hopefully turn out to be valuable.

Despite their advantageous properties, randomized mechanisms have in the past often met with resistance by practitioners and the public (Kurokawa et al., 2018), but we see signs of a shift in attitudes. *Citizens' assemblies*, deliberative forums composed of a random sample of citizens, are quickly gaining usage around the world (OECD, 2020) and proudly point to their random selection — often carried out using complex algorithms from computer science (Flanigan et al., 2021) — as a source of legitimacy. If this trend continues, randomness will be associated by the public with neutrality and fairness, not with haphazardness. Hence, randomized apportionment methods (though, perhaps, simpler ones than the ones we developed here) might yet receive serious consideration.

## Acknowledgements

We thank Bailey Flanigan, Hadi Hosseini, Peyton Young, and David Wajc for helpful discussions.

## 8 Bibliography

A. A. Ageev and M. I. Sviridenko. 2004. Pipage Rounding: A New Method of Constructing Algorithms with Proven Performance Guarantee. *Journal of Combinatorial Optimization* 8, 3 (2004), 307–328. [→ p. 6]

R. A. Agnew. 2008. Optimal Congressional Apportionment. *The American Mathematical Monthly* 115, 4 (2008), 297–303. [→ p. 5]

M. Akbarpour and A. Nikzad. 2020. Approximate Random Allocation Mechanisms. *The Review of Economic Studies* 87, 6 (2020), 2473–2510. [→ p. 6]

H. Aziz, R. Freeman, N. Shah, and R. Vaish. 2023a. Best of Both Worlds: Ex Ante and Ex Post Fairness in Resource Allocation. *Operations Research* (Jan. 2023), opre.2022.2432. [→ p. 6]

H. Aziz, A. Ganguly, and E. Micha. 2023b. Best of Both Worlds Fairness under Entitlements. In *Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems (AAMAS)*. 941–948. [→ p. 6]

H. Aziz, O. Lev, N. Mattei, J. S. Rosenschein, and T. Walsh. 2019. Strategyproof Peer Selection Using Randomization, Partitioning, and Apportionment. *Artificial Intelligence* 275 (2019), 295–309. [→ p. 5, 11]

H. Aziz, H. Moulin, and F. Sandomirskiy. 2020. A Polynomial-Time Algorithm for Computing a Pareto Optimal and Almost Proportional Allocation. *Operations Research Letters* 48, 5 (2020), 573–578. [→ p. 6]

M. Babaioff, T. Ezra, and U. Feige. 2022. On Best-of-Both-Worlds Fair-Share Allocations. In *Web and Internet Economics (WINE 2022)*. Lecture Notes in Computer Science, Vol. 13778. Springer, 237–255. [→ p. 6]

M. Balinski. 1993. The Problem with Apportionment. *Journal of the Operations Research Society of Japan* 36, 3 (1993), 134–148. [→ p. 5]

M. Balinski and V. Ramírez. 1999. Parametric Methods of Apportionment, Rounding and Production. *Mathematical Social Sciences* 37, 2 (March 1999), 107–122. [→ p. 5]
M. Balinski and V. Ramirez. 2014. Parametric vs. Divisor Methods of Apportionment. *Annals of Operations Research* 215, 1 (April 2014), 39–48. [→ p. 5]

M. Balinski and N. Shahidi. 1998. A Simple Approach to the Product Rate Variation Problem via Axiomatics. *Operations Research Letters* 22, 4-5 (May 1998), 129–135. [→ p. 6]

M. L. Balinski and G. Demange. 1989a. Algorithms for Proportional Matrices in Reals and Integers. *Mathematical Programming* 45, 1-3 (Aug. 1989), 193–210. [→ p. 5]

M. L. Balinski and G. Demange. 1989b. An Axiomatic Approach to Proportionality Between Matrices. *Mathematics of Operations Research* 14, 4 (Nov. 1989), 700–719. [→ p. 5]

M. L. Balinski and H. P. Young. 1975. The Quota Method of Apportionment. *The American Mathematical Monthly* 82, 7 (1975), 701–730. [→ p. 5, 6, 15, 27]

M. L. Balinski and H. P. Young. 1979. Quotatone Apportionment Methods. *Mathematics of Operations Research* 4, 1 (1979), 31–38. [→ p. 11, 14, 15]

M. L. Balinski and H. P. Young. 1982. *Fair Representation: Meeting the Ideal of One Man, One Vote*. Yale University Press. [→ p. 2, 4, 5, 8, 9]

N. Bansal, A. Gupta, J. Li, J. Mestre, V. Nagarajan, and A. Rudra. 2012. When LP Is the Cure for Your Matching Woes: Improved Bounds for Stochastic Matchings. *Algorithmica* 63, 4 (2012), 733–762. [→ p. 6]

J. Barbanel. 1996. Game-Theoretic Algorithms for Fair and Strongly Fair Cake Division with Entitlements. In *Colloquium Mathematicae*, Vol. 69. 59–73. [→ p. 6]

J. Bautista, R. Companys, and A. Corominas. 1996. A Note on the Relation between the Product Rate Variation (PRV) Problem and the Apportionment Problem. *Journal of the Operational Research Society* 47, 11 (1996), 1410–1414. [→ p. 6]

G. Benadè, A. M. Kazachkov, A. D. Procaccia, A. Psomas, and D. Zeng. 2023. Fair and Efficient Online Allocations. *Operations Research* (Nov. 2023), opre.2022.0332. [→ p. 6]

G. Birkhoff. 1946. Three Observations on Linear Algebra. *Universidad Nacional de Tucumán, Revista A* 5 (1946), 147–151. [→ p. 6]

A. Bogomolnaia and H. Moulin. 2001. A New Solution to the Random Assignment Problem. *Journal of Economic Theory* 100 (2001), 295–328. [→ p. 6, 20]

K. R. W. Brewer and M. Hanif. 1983. *An Introduction to Sampling with Unequal Probabilities*. Lecture Notes in Statistics, Vol. 15. Springer. [→ p. 3, 19]

H. Buchstein and M. Hein. 2009. Randomizing Europe: The Lottery as a Decision-Making Procedure for Policy Creation in the EU. *Critical Policy Studies* 3, 1 (2009), 29–57. [→ p. 5, 19]

H. Buchstein, M. Hein, and J. Jünger. 2013. Die „EU-Kommissionslotterie“. Eine Simulationsstudie. In *Die Versprechen der Demokratie*. Nomos, 190–227. [→ p. 19, 20]

E. Budish, Y.-K. Che, F. Kojima, and P. Milgrom. 2013. Designing Random Allocation Mechanisms: Theory and Applications. *American Economic Review* 103, 2 (2013), 585–623. [→ p. 6, 20]
O. R. Burt and C. C. Harris. 1963. Letter to the Editor—Apportionment of the U.S. House of Representatives: A Minimum Range, Integer Solution, Allocation Problem. *Operations Research* 11, 4 (Aug. 1963), 648–652. [→ p. 5]

J. Cembrano, J. Correa, and V. Verdugo. 2022. Multidimensional Political Apportionment. *Proceedings of the National Academy of Sciences* 119, 15 (April 2022), e2109305119. [→ p. 5]

M. Chakraborty, U. Schmidt-Kraepelin, and W. Suksompong. 2021. Picking Sequences and Monotonicity in Weighted Fair Division. *Artificial Intelligence* 301 (Dec. 2021), 103578. [→ p. 6]

Y. Cheng, Z. Jiang, K. Munagala, and K. Wang. 2019. Group Fairness in Committee Selection. In *Proceedings of the 20th ACM Conference on Economics and Computation (EC)*. 263–279. [→ p. 6]

S. El-Helaly. 2019. *The Mathematics of Voting and Apportionment: An Introduction*. Springer. [→ p. 8]

D. Elliott, S. Martin, J. Shakesprere, and J. Kelly. 2021. *Simulating the 2020 Census. Miscounts and the Fairness of Outcomes*. Research Report. Urban Institute. [→ p. 3]

L. R. Ernst. 1994. Apportionment Methods for the House of Representatives and the Court Challenges. *Management Science* 40, 10 (Oct. 1994), 1207–1227. [→ p. 5]

M. Feldman, S. Mauras, V. V. Narayan, and T. Ponitka. 2023. Breaking the Envy Cycle: Best-of-Both-Worlds Guarantees for Subadditive Valuations. arXiv:2304.03706 [cs] [→ p. 6]

B. Flanigan, P. Gölz, A. Gupta, B. Hennig, and A. D. Procaccia. 2021. Fair Algorithms for Selecting Citizens’ Assemblies. *Nature* 596, 7873 (2021), 548–552. [→ p. 22]

R. Gandhi, S. Khuller, S. Parthasarathy, and A. Srinivasan. 2006. Dependent Rounding and Its Applications to Approximation Algorithms. *Journal of the ACM* 53, 3 (2006), 324–360. [→ p. 4, 6, 7, 12, 13]

J. Goldman and A. D. Procaccia. 2014. Splridit: Unleashing Fair Division Algorithms. *SIGecom Exchanges* 13, 2 (2014), 41–46. [→ p. 21]

G. Grimmett. 2004. Stochastic Apportionment. *American Mathematical Monthly* 11, 4 (2004), 299–307. [→ p. 1, 3, 5, 7, 8, 11]

P. Hall. 1935. On Representatives of Subsets. *Journal of the London Mathematical Society* s1-10, 1 (1935), 26–30. [→ p. 15]

M. Hoefer, M. Schmalhofer, and G. Varricchio. 2023. Best of Both Worlds: Agents with Entitlements. In *Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems (AAMAS)*. 564–572. [→ p. 6]

E. V. Huntington. 1928. The Apportionment of Representatives in Congress. *Trans. Amer. Math. Soc.* 30, 1 (1928), 85–110. [→ p. 5]

A. Hylland and R. Zeckhauser. 1979. The Efficient Allocation of Individuals to Positions. *Journal of Political Economy* 87, 2 (1979), 293–314. [→ p. 6, 20]

S. Janson. 2014. Asymptotic Bias of Some Election Methods. *Annals of Operations Research* 215, 1 (April 2014), 89–136. [→ p. 5]
J. F. C. Kingman. 1993. *Poisson Processes*. Clarendon Press. [→ p. 10]

W. Kubiak. 1993. Minimizing Variation of Production Rates in Just-in-Time Systems: A Survey. *European Journal of Operational Research* 66, 3 (May 1993), 259–271. [→ p. 6]

V. A. Kumar, M. V. Marathe, S. Parthasarathy, and A. Srinivasan. 2009. A Unified Approach to Scheduling on Unrelated Parallel Machines. *Journal of the ACM* 56, 5 (2009), 1–31. [→ p. 6]

D. Kurokawa, A. D. Procaccia, and N. Shah. 2018. Leximin Allocations in the Real World. *ACM Transactions on Economics and Computation* 6, 3–4 (2018), article 11. [→ p. 22]

L. Lauwers and T. Van Puyenbroeck. 2006. The Hamilton Apportionment Method Is Between the Adams Method and the Jefferson Method. *Mathematics of Operations Research* 31, 2 (May 2006), 390–397. [→ p. 5]

S. Maier, P. Zachariassen, and M. Zachariasen. 2010. Divisor-Based Biproportional Apportionment in Electoral Systems: A Real-Life Benchmark Study. *Management Science* 56, 2 (Feb. 2010), 373–387. [→ p. 5]

A. W. Marshall, I. Olkin, and F. Pukelsheim. 2002. A Majorization Comparison of Apportionment Methods in Proportional Representation. *Social Choice and Welfare* 19, 4 (Oct. 2002), 885–900. [→ p. 5]

C. Mathieu and V. Verdugo. 2022. Apportionment with Parity Constraints. *Mathematical Programming* (Dec. 2022). [→ p. 5]

N. Nisan and A. Ronen. 2001. Algorithmic Mechanism Design. *Games and Economic Behavior* 35, 1–2 (2001), 166–196. [→ p. 3]

OECD. 2020. *Innovative Citizen Participation and New Democratic Institutions: Catching the Deliberative Wave*. OECD. [→ p. 22]

A. Palomares, F. Pukelsheim, and V. Ramírez. 2024. Note on Axiomatic Properties of Apportionment Methods for Proportional Representation Systems. *Mathematical Programming* 203, 1-2 (Jan. 2024), 169–185. [→ p. 5]

A. Panconesi and A. Srinivasan. 1997. Randomized Distributed Edge Coloring via an Extension of the Chernoff–Hoeffding Bounds. *SIAM Journal on Computing* 26, 2 (1997), 350–368. [→ p. 6, 12, 21]

G. Pólya. 1919. Proportionalwahl und Wahrscheinlichkeitsrechnung. *Zeitschrift für die gesamte Staatswissenschaft* 74, 3 (1919), 297–322. [→ p. 5]

F. Pukelsheim. 2017. *Proportional Representation: Apportionment Methods and Their Applications* (2nd edition ed.). Springer, New York, NY. [→ p. 5]

E. A. Robinson and D. Ullman. 2010. *A Mathematical Look at Politics*. CRC Press. [→ p. 7, 8]

B. Saha and A. Srinivasan. 2018. A New Approximation Technique for Resource-Allocation Problems. *Random Structures & Algorithms* 52, 4 (2018), 680–715. [→ p. 6]

F. Sandomirskiy and E. Segal-Halevi. 2022. Efficient Fair Division with Minimal Sharing. *Operations Research* 70, 3 (2022), 1762–1782. [→ p. 6]

G. Steiner and S. Yeomans. 1993. Level Schedules for Mixed-Model, Just-in-Time Processes. *Management Science* 39, 6 (1993), 728–735. [→ p. 6, 7]
J. W. Still. 1979. *A Class of New Methods for Congressional Apportionment*. *SIAM Journal on Applied Mathematics* 37, 2 (1979), 401–418. [→ p. 6, 11, 14, 15]

P. Stone. 2011. *The Luck of the Draw: The Role of Lotteries in Decision Making*. Oxford University Press. [→ p. 3]

G. G. Szpiro. 2010. *Numbers Rule: The Vexing Mathematics of Democracy, from Plato to the Present*. Princeton University Press. [→ p. 2]

J. von Neumann. 1953. *A Certain Zero-Sum Two-Person Game Equivalent to the Optimal Assignment Problem*. In *Contributions to the Theory of Games*, W. Kuhn and A. W. Tucker (Eds.). Vol. 2. Princeton University Press, 5–12. [→ p. 6]
# Proofs of Statements

## EC.1 Pitfalls in the Development of House Monotone Methods

In Section 4.1, we claimed that for the population profile $\vec{p} = (45, 25, 15, 15)$ and house size $h = 3$ — thus, the standard quotas $(1.35, 0.75, 0.45, 0.45)$ — the following distribution over apportionments can be part of an apportionment method in which house monotonicity, quota, and ex ante proportionality hold across the inputs $\{(\vec{p}, h') | h' \le 3\}$:

$$ \vec{a} = \begin{cases} (2, 1, 0, 0) & \text{with probability } 35\%, \quad (1, 1, 0, 1) \text{ with probability } 20\%, \text{ and} \\ (1, 1, 1, 0) & \text{with probability } 20\%, \quad (1, 0, 1, 1) \text{ with probability } 25\%. \end{cases} $$

To obtain such an apportionment method, consider the following capacitated flow network:

<figure><img src="image_7.png" /></figure>

One easily verifies that it is possible to send a total flow of 1 through this network, which necessarily uses all edges at their capacity. Consider any decomposition of this flow into paths. Our method will be defined as (1) choosing one of these paths $\vec{a}_1 \to \vec{a}_2 \to \vec{a}_3$ with probability proportional to its amount of flow and (2) returning a solution $f$ such that $f(\vec{p}, j) = \vec{a}_j$ for $j = 1, 2, 3$, and some canonical apportionment for all other inputs.

Across the inputs $\{(\vec{p}, h') | h' \le 3\}$, this method does not violate house monotonicity since edges in the flow network are such that no agent's seat number decreases along an edge. Since one verifies that all apportionments labeling the nodes of the flow network satisfy quota, the method satisfies quota on $\{(\vec{p}, h') | h' \le 3\}$. On the same set of inputs, the method satisfies ex-ante proportionality, which follows from the fact that, for $h' = 1, 2, 3$, weighting the apportionments of the $h'$-th layer of the flow network by their internal flow, we obtain the vector of standard quotas for $\vec{p}$ and house size $h'$. The egress edges also ensure that, indeed, the method's distribution over apportionments on $\vec{p}, h$ is as given above.

Finally, we must prove that none of the apportionments in the last layer of the flow network are toxic. For this, observe that the quota solution by Balinski and Young (1975) (which is house monotone and satisfies quota), for one way of breaking ties in the definition, produces the following apportionments on $\vec{p}$: $(1, 0, 0, 0) \to (1, 1, 0, 0) \to (2, 1, 0, 0) \to (2, 1, 1, 0) \to (2, 1, 1, 1), \dots$. Since
(2, 1, 0, 0) coincides with one of these values, it can be extended by the suffix of the quota solution and is therefore not toxic. Furthermore, we can extend (1, 1, 1, 0) → (2, 1, 1, 0), and then continue as the quota solution; (1, 1, 0, 1) → (2, 1, 0, 1) → (2, 1, 1, 1), and then as the quota solution; and (1, 0, 1, 1) → (1, 1, 1, 1) → (2, 1, 1, 1), and then as the quota solution. The claim follows by verifying that these extensions do not violate quota until merging with the quota solution.

## EC.2 Deferred Proofs for House Monotone Apportionment

**Lemma 1** An infinite seat sequence $\alpha$ satisfies quota iff it is the concatenation of infinitely many finite seat sequences $\beta^1, \beta^2, \beta^3, \dots$ of length $p$ each satisfying quota, i.e.,

$$ \alpha = \beta_1^1, \beta_2^1, \dots, \beta_p^1, \beta_1^2, \beta_2^2, \dots, \beta_p^2, \beta_1^3, \dots $$

*Proof.* “⇒”: Fix $\alpha$ and some $k \in \mathbb{Z}_{\ge 0}$. We must show that the finite seat sequence $\beta^{k+1} := \alpha_{kp+1}, \alpha_{kp+2}, \dots, \alpha_{(k+1)p}$ satisfies quota. Indeed, for any $1 \le r \le p$, the number of seats allocated by $\beta^{k+1}$ to state $i$ at house size $r$ is

$$ \begin{aligned} |\{1 \le h' \le r \mid \beta_{h'}^{k+1} = i\}| &= |\{1 \le h' \le r \mid \alpha_{kp+h'} = i\}| \\ &= a_i(kp + r) - a_i(kp) \\ &\in \{\lfloor (kp + r) p_i / p \rfloor, \lceil (kp + r) p_i / p \rceil\} - k p_i \quad (\text{since } \alpha \text{ satisfies quota}) \\ &= \{\lfloor r p_i / p \rfloor + k p_i, \lceil r p_i / p \rceil + k p_i\} - k p_i \\ &= \{\lfloor r p_i / p \rfloor, \lceil r p_i / p \rceil\}, \end{aligned} $$

which shows that $\alpha$ can be decomposed into finite seat sequences $\{\beta^k\}_{k \in \mathbb{N}}$ satisfying quota.

“⇔”: Fix some $h$ and choose $k := \lfloor (h-1)/p \rfloor + 1$ and $r := ((h-1) \mod p) + 1$ such that $h = (k-1)p + r$, $k \ge 1$ and $1 \le r \le p$. We will show that $\alpha$'s allocation $a(h)$ on $h$ satisfies quota. Denoting $\beta^k$'s allocation for a house size $h'$ by $b^k(h')$, it holds for all states $i$ that $a_i(h) = \sum_{k'=1}^{k-1} b^k(p) + b^k(r)$. By quota, $b^k(p) = p_i$ for all $k$, and $b^k(r) \in \{\lfloor r p_i / p \rfloor, \lceil r p_i / p \rceil\}$. Thus, $a_i(h) \in \{(k-1)p_i + \lfloor r p_i / p \rfloor, (k-1)p_i + \lceil r p_i / p \rceil\}$. The conclusion follows since $h p_i / p = ((k-1)p + r) p_i / p = (k-1)p_i + r p_i / p$. $\square$

**Lemma 5** For any population profile $\vec{p}$, there is a probability distribution $\mathcal{D}$ over finite seat sequences such that one can sample a finite seat sequence $\alpha \sim \mathcal{D}$ in $\mathcal{O}(p^2 n^2)$ randomized time, such that all finite seat sequences in the support of $\mathcal{D}$ satisfy quota, and such that, for all states $i$ and $1 \le h \le p$,

$$ \mathbb{P}[\alpha_h = i] = p_i / p. $$

*Proof.* As sketched in Section 4.2, we define $\mathcal{D}$ by invoking Theorem 4 on a star graph with $A = \{a\}, B = \{b_i \mid i \in N\}$, and $E = \{\{a, b_i\} \mid i \in N\}$. We set $T := p$, and, for each $1 \le t \le T$ and state $i$, set $w_{\{a,b_i\}}^t := p_i / p$.

**Theorem 4** now defines a joint distribution over variables $X_e^t$ satisfying marginal distribution, degree preservation, and cumulative degree preservation (as well as negative correlation, which we will not use). We will describe how each joint realization of the $X_e^t$ can be mapped to a finite seat sequence and that the distribution $\mathcal{D}$ that arises from applying this mapping to the dependent-rounding distribution has the properties claimed in the statement. The running time follows from the running time of applying dependent rounding, and the fact that the transformation for translating the outcome into a finite seat sequence requires only $\mathcal{O}(pn)$ time.

For a given joint realization of the $X_e^t$, let $\alpha$ be the finite seat sequence that maps each $h \in \{1, \dots, p\}$ to the state $i$ such that $X_{\{a,b_i\}}^h = 1$. This definition presupposes that there is
exactly one such $i$ for each $h$, which follows from the degree-preservation guarantee for vertex $a$ at time step $h$ and from the fact that $d_a^h = \sum_{i \in N} p_i / p = 1$. This seat sequence $\alpha$ furthermore satisfies quota, which directly follows from cumulative degree preservation and from $\sum_{t'=1}^h d_{b_i}^{t'} = h p_i / p$. It only remains to show that $\alpha_h$ has value $i$ with a probability of $p_i / p = w_{\{a,b_i\}}^h$ for all $i \in N$ and $1 \le h \le p$, but this immediately follows from the marginal distribution guarantee of Theorem 4. $\square$

**Theorem 5** There exists an apportionment method $F$ that satisfies house monotonicity, quota, and ex ante proportionality.

*Proof.* For each population profile $\vec{p}$, Lemma 5 provides a probability distribution over finite seat sequences for that population profile. We define the outcomes such that $\omega$ contains, for each $\vec{p}$, a separate, independent $\alpha^{\vec{p}}$ following the distribution from Lemma 5.

From now on, we fix an $\omega \in \Omega$, which determines the values of all $\alpha^{\vec{p}}$. For this $\omega$, we must construct an apportionment solution $f = F^{\omega}$. For a given input $\vec{p}, h$, let $\alpha$ be the concatenation of infinitely many copies of $\alpha^{\vec{p}}$ as in Lemma 1. Then, we define $f(\vec{p}, h)$ as the apportionment giving $a_i(h) = \{1 \le h' \le h \mid \alpha(h') = i\}$ seats to each state $i$.

By Lemma 5, $\alpha^{\vec{p}}$ satisfies quota, and, thus, $\alpha$ satisfies quota by Lemma 1, from which it follows immediately that $f$ satisfies quota. Since $f$ was constructed from a seat sequence allocating one seat at a time, it clearly satisfies house monotonicity.

It remains to argue that $F$ satisfies ex ante proportionality. Fix any $\vec{p}$ and $h$. By construction, $F_i(\vec{p}, h) - F_i(\vec{p}, h-1) = 1 \{\alpha_{1+(h-1 \bmod p)}^{\vec{p}} = i\}$, setting $F_i(\vec{p}, 0) = 0$. Hence,

$$ \mathbb{E}[F_i(\vec{p}, h) - F_i(\vec{p}, h-1)] = \mathbb{P}[\alpha_{1+(h-1 \bmod p)}^{\vec{p}} = i] = p_i/p, $$

where the last equality follows from Lemma 5. By linearity of expectation, it follows that,

$$ \mathbb{E}[F_i(\vec{p}, h)] = \sum_{h'=1}^{h} \mathbb{E}[F_i(\vec{p}, h) - F_i(\vec{p}, h-1)] = h p_i / p, $$

which shows ex ante proportionality. $\square$

**Theorem 6** For any population profile $\vec{p}$, we can construct a bipartite graph whose perfect matchings are in one-to-one correspondence with the finite seat sequences satisfying quota.

*Proof.* We will first show a variant of the theorem, in which the finite seat sequences correspond not to perfect matchings but to perfect $b$-matchings, i.e., where each node is labeled with a target degree in $\mathbb{Z}_{\ge 0}$, and where a subset of edges is a perfect $b$-matching when each node has its target degree in the induced subgraph. We will then show how to modify the graph to obtain the claimed result for perfect matchings.

Then, the bipartite graph is the one to which we applied cumulative rounding in Lemma 5 (without the weights), with the following (technically necessary) modifications:

1. We set each node's target degree to its fractional degree as in Lemma 4. This is possible since all nodes have integer weight, including the nodes $v^{T:T+1}$ which have weight 1 given that $\sum_{t'=1}^T d_v^{t'}$ is an integer for all nodes $v$ in the underlying graph for the chosen $T = p$.

2. Then, we delete all edges with zero weight (to ensure that they are never part of the $b$-matching).

3. Finally, for each edge with weight 1, we delete the edge and decrement the target degree of both adjacent nodes (simulating the constraint that these edges must be present in any $b$-matching).
The proof of Lemma 5 indicated a way to map perfect b-matchings to finite seat sequences, and we have to show that this mapping is a bijection, i.e., that it is injective and surjective.

To show that the mapping is injective, observe that two perfect b-matchings that differ in whether a certain edge {$v^t, (v')^t$} is included lead to different seat sequences. Furthermore, the characterization of the edges in Fig. 3 (whose correctness follows from the proof of Theorem 4 and does not rely on properties of the result of dependent rounding other than those required by our b-matchings) implies that the set of edges of shape {$v^t, (v')^t$} in the matching uniquely determines which of the other edges are included in the perfect b-matching, which means that there are never multiple perfect b-matchings that would be mapped to the same finite seat sequence.

It is more involved to show that the mapping is surjective. For a given finite seat sequence $\alpha$, we will construct a perfect b-matching which is mapped to $\alpha$. Clearly, each edge {$a^t, (b_i)^t$} is included in the matching iff $\alpha_t = i$ (none of these edges have weight zero or one since $n \ge 2$ and each state has a positive population). We label all other edges according to the edges' events described in Fig. 3. One verifies that, by quota, this step would not have taken any edges with zero weight in the cumulative-rounding graph and would have taken all edges with weight one in the cumulative-rounding graph, which allows us to pretend for ease of exposition that we are producing a b-matching on the labeled graph before the preprocessing steps (2) and (3). One easily verifies that the resulting edge set gives the target degree to all nodes of shape $v^t$, $\bar{v}^t$, and $v^{t:t+1}$ (including the special cases $v^{0:1}$ and $v^{T:T+1}$).

It only remains to show that the nodes $\bar{v}^t$ have their target degree, $\left\lfloor \sum_{t'=1}^t d_v^{t'} \right\rfloor - \left\lfloor \sum_{t'=1}^{t-1} d_v^{t'} \right\rfloor - \lfloor d_v^t \rfloor + 1$. For nodes $v = a^t$, it holds that $d_v^{t'} = D_v^{t'} = 1$ for all $t'$, which means that the target degree is one and indeed only one adjacent edge, namely, $\{\bar{v}^t, v^{t:t+1}\}$, is taken.

We will now consider the case of a node $v = b_i^t$. Observe that $d_v^{t'} = p_i / \sum_{j \in N} p_j < 1$ for all $t'$, which means that $\sum_{t''=1}^{t'} d_v^{t''} = t' p_i / \sum_{j \in N} p_j$, which is just $i$'s standard quota for house size $t'$, which we will write as $q_i(t')$. Furthermore, note that $\sum_{t''=1}^{t'} D_v^{t'} = a_i(t')$. With this, the target degree of $v$ is just $\lfloor q_i(t) \rfloor - \lfloor q_i(t-1) \rfloor + 1$, and the three edges incident to $v$ are selected if

$$ (a) \quad a_i(t) = a_i(t-1) + 1 \text{ (rather than } a_i(t) = a_i(t-1)), $$

$$ (b) \quad a_i(t-1) = \lfloor q_i(t-1) \rfloor + 1 \text{ (rather than } a_i(t-1) = \lfloor q_i(t-1) \rfloor), \text{ and} $$

$$ (c) \quad a_i(t) = \lfloor q_i(t) \rfloor \text{ (rather than } a_i(t) = \lfloor q_i(t) \rfloor), $$

respectively, where the values in parentheses are the only alternatives to the properties, by house monotonicity and quota. That is, we want to show that, for our house monotone and quota $\alpha$, exactly $\lfloor q_i(t) \rfloor - \lfloor q_i(t-1) \rfloor + 1 \in \{1, 2\}$ many out of the statements (a), (b), and (c), are true. In Table 2, we rule out all other cases via a case distinction, which shows that we indeed produced a perfect b-matching, and that the mapping is surjective.

The above establishes the one-to-one correspondence to the vertices on the polytope of perfect fractional b-matchings. Though this polytope is very nicely behaved already, we prefer to state the theorem for a classical perfect matching polytope, which is more widely known. Thus, we will adapt the bipartite graph above such that all nodes have target degree one, while keeping the perfect b-matchings in one-to-one correspondence. First, we remove all nodes with target degrees zero from the graph, which clearly does not change the set of perfect b-matchings. Looking at Lemma 4, only two kinds of nodes can have a target degree larger than one: nodes $a^t$ and some nodes $\bar{b}_i^t$. In fact, the nodes $a^t$ are no problem: While they have degree 2 in the cumulative-rounding construction, one of their adjacent edges, {$a^t, \bar{a}^t$} had weight 1, and thus the target degree of $a^t$ was already lowered to one in step (3) of the preprocessing.

Thus, once more, the only issue are nodes of the form $\bar{b}_i^t$, specifically, when their target degree is 2 (it is never higher, as discussed above). If such a node only has two adjacent edges remaining
<table><caption>Table 2: Case distinction for proving that nodes of the shape $\tilde{b}_i^t$ have the target degree in the proof of Theorem 6.</caption><thead><tr><th>[q<sub>i</sub>(t)] - [q<sub>i</sub>(t-1)] + 1</th><th>(a)?</th><th>(b)?</th><th>(c)?</th><th>Impossibility proof</th></tr></thead><tbody><tr><td>2</td><td>✓ a<sub>i</sub>(t) = a<sub>i</sub>(t-1) + 1</td><td>✓ a<sub>i</sub>(t-1) = [q<sub>i</sub>(t-1)] + 1</td><td>✓ a<sub>i</sub>(t) = [q<sub>i</sub>(t)]</td><td>a<sub>i</sub>(t-1) = [q<sub>i</sub>(t-1)] + 1 = [q<sub>i</sub>(t)] =<br/>a<sub>i</sub>(t) = a<sub>i</sub>(t-1) + 1</td></tr><tr><td>2</td><td>a<sub>i</sub>(t) = a<sub>i</sub>(t-1)</td><td>a<sub>i</sub>(t-1) = [q<sub>i</sub>(t-1)]</td><td>?</td><td>[q<sub>i</sub>(t)] = [q<sub>i</sub>(t-1)] + 1 = a<sub>i</sub>(t-1) + 1 =<br/>a<sub>i</sub>(t) + 1 &gt; a<sub>i</sub>(t), violates quota</td></tr><tr><td>2</td><td>✓ a<sub>i</sub>(t) = a<sub>i</sub>(t-1) + 1</td><td>a<sub>i</sub>(t-1) = [q<sub>i</sub>(t-1)]</td><td>a<sub>i</sub>(t) = [q<sub>i</sub>(t)] + 1</td><td>a<sub>i</sub>(t-1) = [q<sub>i</sub>(t-1)] = [q<sub>i</sub>(t)] - 1 =<br/>a<sub>i</sub>(t) - 2 = a<sub>i</sub>(t-1) - 1</td></tr><tr><td>2</td><td>a<sub>i</sub>(t) = a<sub>i</sub>(t-1)</td><td>✓ a<sub>i</sub>(t-1) = [q<sub>i</sub>(t-1)] + 1</td><td>a<sub>i</sub>(t) = [q<sub>i</sub>(t)] + 1</td><td>a<sub>i</sub>(t-1) = [q<sub>i</sub>(t-1)] + 1 = [q<sub>i</sub>(t)] =<br/>a<sub>i</sub>(t) - 1 = a<sub>i</sub>(t-1) - 1</td></tr><tr><td>1</td><td>a<sub>i</sub>(t) = a<sub>i</sub>(t-1)</td><td>a<sub>i</sub>(t-1) = [q<sub>i</sub>(t-1)]</td><td>a<sub>i</sub>(t) = [q<sub>i</sub>(t)] + 1</td><td>a<sub>i</sub>(t-1) = [q<sub>i</sub>(t-1)] = [q<sub>i</sub>(t)] =<br/>a<sub>i</sub>(t) - 1 = a<sub>i</sub>(t-1) - 1</td></tr><tr><td>1</td><td>✓ a<sub>i</sub>(t) = a<sub>i</sub>(t-1) + 1</td><td>?</td><td>✓ a<sub>i</sub>(t) = [q<sub>i</sub>(t)]</td><td>a<sub>i</sub>(t-1) = a<sub>i</sub>(t) - 1 = [q<sub>i</sub>(t)] - 1 =<br/>[q<sub>i</sub>(t-1)] - 1, violates quota</td></tr><tr><td>1</td><td>✓ a<sub>i</sub>(t) = a<sub>i</sub>(t-1) + 1</td><td>✓ a<sub>i</sub>(t-1) = [q<sub>i</sub>(t-1)] + 1</td><td>a<sub>i</sub>(t) = [q<sub>i</sub>(t)] + 1</td><td>a<sub>i</sub>(t-1) = [q<sub>i</sub>(t-1)] + 1 = [q<sub>i</sub>(t)] + 1 =<br/>a<sub>i</sub>(t) = a<sub>i</sub>(t-1) + 1</td></tr><tr><td>1</td><td>a<sub>i</sub>(t) = a<sub>i</sub>(t-1)</td><td>✓ a<sub>i</sub>(t-1) = [q<sub>i</sub>(t-1)] + 1</td><td>✓ a<sub>i</sub>(t) = [q<sub>i</sub>(t)]</td><td>a<sub>i</sub>(t-1) = [q<sub>i</sub>(t-1)] + 1 = [q<sub>i</sub>(t)] + 1 =<br/>a<sub>i</sub>(t) + 1 = a<sub>i</sub>(t-1) + 1</td></tr></tbody></table>
in the graph these edges must be taken in any perfect b-matching, so we can eliminate $\bar{b}_i^t$ and its neighbors. Thus, say that the node still has all three adjacent edges, $\{\bar{b}_i^t, \bar{b}_i^{t'}\}$, $\{\bar{b}_i^t, b_i^{t-1:t}\}$, and $\{\bar{b}_i^t, b_i^{t:t+1}\}$. In this case, replace node $\bar{b}_i^t$ by two fresh nodes $n_1$ and $n_2$, both with target degree 1, and connect these nodes using four edges $(n_1, \bar{b}_i^t)$, $(n_1, b_i^{t-1:t})$, $(n_2, b_i^{t-1:t})$, $(n_2, b_i^{t:t+1})$. One verifies that, that in any perfect b-matching on the graph before replacement, one can replace the two edges incident to $\bar{b}_i^t$ by exactly one subset of the new edges to obtain a perfect b-matching on the new graph, and that the analogous step in the other direction also works in one unique way. Thus, after making these replacements, the finite seat sequences satisfying quota correspond one-to-one to the perfect matchings of the graph, which are the corner points of the polytope of fractional perfect matchings by the Birkhoff-von Neumann Theorem. $\square$

## EC.3 Deferred Proofs for Cumulative Rounding

**Lemma 2** The graph produced by Construction 7 is bipartite.

*Proof.* Note that the set of nodes

$$ \{a^t \mid a \in A, 1 \le t \le T\} \cup \{\bar{a}^t \mid a \in A, 1 \le t \le T\} \cup \{\bar{b}^t \mid b \in B, 1 \le t \le T\} \cup \{b^{t:t+1} \mid b \in B, 0 \le t \le T\} $$

has no internal edges, and neither does the complement of this set. $\square$

**Lemma 3** All edge weights lie between 0 and 1.

*Proof.* If the edge has the shape $\{v^t, (v^t)^t\}$ for some $v, v^t \in A \cup B$, then the edge weight is one of the $w_e^t$, which are in $[0, 1]$ by assumption. All other edge weights either have the shape $x - \lfloor x \rfloor$ or the shape $1 - x + \lfloor x \rfloor = 1 - (x - \lfloor x \rfloor)$ for some $x \in \mathbb{R}$. The claim follows since $x - 1 < \lfloor x \rfloor \le x$. $\square$

**Lemma 4** For each node $v \in A \cup B$, the following table gives the fractional degrees of various nodes in the constructed graph, all of which are integer:

<table><thead><tr><th>nodes</th><th>fractional degree</th></tr></thead><tbody><tr><td>$v^t$ ($\forall 1 \le t \le T$)</td><td>$\lfloor d_v^t \rfloor + 1$</td></tr><tr><td>$\bar{v}^t$ ($\forall 1 \le t \le T$)</td><td>$\lfloor \sum_{t'=1}^t d_v^{t'} \rfloor - \lfloor \sum_{t'=1}^{t-1} d_v^{t'} \rfloor - \lfloor d_v^t \rfloor + 1$</td></tr><tr><td>$\bar{v}^t$ ($\forall 1 \le t \le T$)</td><td>1</td></tr><tr><td>$v^{t:t+1}$ ($\forall 1 \le t \le T-1$)</td><td>1</td></tr><tr><td>$v^{0:1}$</td><td>0</td></tr></tbody></table>

*Proof.* Within this proof, denote by $frac(\cdot)$ the fractional degree of a vertex in the constructed graph.

$$ \text{frac}(v^t) = \underbrace{\sum_{v \in E} w_e^t}_{=d_v^t} + (1 - d_v^t + \lfloor d_v^t \rfloor) = \lfloor d_v^t \rfloor + 1 $$

$$ \text{frac}(\bar{v}^t) = (d_v^t - \lfloor d_v^t \rfloor) + (\sum_{t'=1}^{t-1} d_v^{t'} - \lfloor \sum_{t'=1}^{t-1} d_v^{t'} \rfloor) + (1 - \sum_{t'=1}^t d_v^{t'} + \lfloor \sum_{t'=1}^t d_v^{t'} \rfloor) \\ = \lfloor \sum_{t'=1}^t d_v^{t'} \rfloor - \lfloor d_v^t \rfloor - \lfloor \sum_{t'=1}^{t-1} d_v^{t'} \rfloor + 1 $$

$$ \text{frac}(\bar{v}^t) = (1 - d_v^t + \lfloor d_v^t \rfloor) + (d_v^t - \lfloor d_v^t \rfloor) = 1 $$

$$ \text{frac}(v^{t:t+1}) = (1 - \sum_{t'=1}^t d_v^{t'} + \lfloor \sum_{t'=1}^t d_v^{t'} \rfloor) + (\sum_{t'=1}^t d_v^{t'} - \lfloor \sum_{t'=1}^t d_v^{t'} \rfloor) = 1 \quad (\text{if } 1 \le t \le T-1) $$

$$ \text{frac}(v^{0:1}) = \sum_{t'=1}^{0} d_v^{t'} - \lfloor \sum_{t'=1}^{0} d_v^{t'} \rfloor = 0 - \lfloor 0 \rfloor = 0 $$

$\square$