Monotone Randomized Apportionment

Apportionment is the act of distributing the seats of a legislature among political parties (or states) in proportion to their vote shares (or populations). A famous impossibility proven by Balinski and Young shows that no apportionment method can be proportional up to one seat (i.e., quota) while also responding monotonically to changes in the votes (i.e., population monotone). Grimmett proposed to overcome this impossibility by randomizing the apportionment, which can achieve quota as well as perfect proportionality and monotonicity—at least in terms of the expected number of seats awarded to each party. Still, the correlations between the seats awarded to different parties may exhibit bizarre nonmonotonicities. When parties or voters care about joint events, such as whether a coalition of parties reaches a majority, these nonmonotonicities can cause paradoxes, including incentives for strategic voting. In this paper, we propose monotonicity axioms ruling out these paradoxes, and we study which of them can be satisfied jointly with Grimmett’s axioms. Essentially, we require that if a set of parties receives more votes, the probability of those parties jointly receiving more seats should increase. Our work draws on a rich literature on unequal-probability sampling in statistics (studied as dependent randomized rounding in computer science). Our main result shows that a sampling scheme owing to Sampford satisfies Grimmett’s axioms and a notion of higher-order correlation monotonicity.

Funding: This work was partially supported by the National Science Foundation [Grant DMS-1928930] and the Alfred P. Sloan Foundation [Grant G-2021-16778] while three of the authors were in residence at the Simons Laufer Mathematical Sciences Institute in Berkeley, California during the fall 2023 semester. Additionally, this work was partially supported by the National Science Foundation [Graduate Research Fellowship Program Grant DGE174] and the National Agency for Research and Development [Grant ACT210005], Center for Mathematical Modeling [Grant FB210005], and Fondo Nacional de Desarrollo Científico y Tecnológico [Grant 1241846].