New Combinatorial Insights for Monotone Apportionment

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 US 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, i.e., every
state should receive $\lfloor q_i \rfloor$ or $\lceil q_i \rceil$ seats,
where $q_i$ 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, i.e., 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.

This is joint work with José Correa, Ulrike Schmidt-Kraepelin,
Alexandros Tsigonias-Dimitriadis, and Victor Verdugo.