Monotone Randomized Apportionment

• 成果类型: Article; Early Access
• 署名作者: Correa, Jose; Golz, Paul; Schmidt-Kraepelin, Ulrike; Tucker-Foltz, Jamie; Verdugo, Victor
• 署名单位: Universidad de Chile; Cornell University; Eindhoven University of Technology; Yale University; Pontificia Universidad Catolica de Chile; Pontificia Universidad Catolica de Chile
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2024.1362
• 发表日期: 2026-07-09
• 关键词: apportionment; randomized rounding; sampling; NEGATIVE DEPENDENCE; replacement

摘要

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.