In This Apportionment Lottery, the House Always Wins

• 成果类型: Article; Early Access
• 署名作者: Golz, Paul; Peters, Dominik; Procaccia, Ariel D.
• 署名单位: University of California System; University of California Berkeley; Cornell University; Centre National de la Recherche Scientifique (CNRS); Harvard University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2022.0419
• 发表日期: 2025
• 关键词: of-representatives; allocation; individuals; algorithms; systems

摘要

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 qi of seats in expectation (ex ante proportionality) and receives either left perpendicular qi right perpendicular or inverted right perpendicular qi inverted left perpendicular 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.