In This Apportionment Lottery, the House Always Wins

Apportionment is the problem of distributing h indivisible seats across states in proportion to the states’ populations. In the context of the U.S. House of Representatives, this problem has a rich history and is a prime example of interactions between mathematical analysis and political practice. Grimmett suggests to apportion seats in a randomized way such that each state receives exactly its proportional share $q_i$ of seats in expectation (ex ante proportionality) and receives either $\lfloor q_i\rfloor$ or $\lceil q_i\rceil$ 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 that 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.

Funding: This work was supported by the National Science Foundation [Grants CCF-1733556, CCF-2007080, DMS-2023505, IIS-2024287, IIS-2147187, IIS-2229881] and the Office of Naval Research [Grant N00014-20-1-2488].

Supplemental Material: The online appendix is available at https://doi.org/10.1287/opre.2022.0419.