New Combinatorial Insights for Monotone Apportionment
研究了单调席位分配方法的设计，将其与离散几何和组合优化中的经典问题联系起来，并探讨随机化如何增强比例性。发现除数方法族产生的不同输出数量略超线性，且填补其上下界差距可解决离散几何中k级复杂度的长期开放问题。
The apportionment problem constitutes a fundamental problem in democratic societies: How to distribute a fixed number of seats among a set of states in proportion to the states’ populations? This—seemingly simple—task has led to a rich literature and has become well known in the context of the U.S. House of Representatives. In this paper, we connect the design of monotone apportionment methods to classic problems from discrete geometry and combinatorial optimization and explore the extent to which randomization can enhance proportionality. We first focus on the well-studied family of stationary divisor methods, which satisfy the strong population monotonicity property, and show that this family produces only a slightly superlinear number of different outputs as a function of the number of states. While our upper and lower bounds leave a small gap, we show that—surprisingly—closing this gap would solve a long-standing open problem from discrete geometry, known as the complexity of k-levels in line arrangements. The main downside of divisor methods is their violation of the quota axiom, that is, every state should receive [Formula: see text] or [Formula: see text] seats, where [Formula: see text] is the proportional share of the state. As we show that randomizing over divisor methods can only partially overcome this issue, we propose a relaxed version of divisor methods in which the total number of seats may slightly deviate from the house size. By randomizing over these methods, we can simultaneously satisfy population monotonicity, quota, and ex-ante proportionality. Finally, we turn our attention to quota-compliant methods that are house-monotone, that is, no state may lose a seat when the house size is increased. We provide a polyhedral characterization based on network flows, which implies a simple description of all ex-ante proportional randomized methods that are house-monotone and quota-compliant. Funding: This work was supported by National Science Foundation (DMS-1928930); Agencia Nacional de Investigación y Desarrollo (Anillo ACT210005, Center for Mathematical Modeling FB210005, FONDECYT 1241846); Alfred P. Sloan Foundation (G-2021-16778).