AI summaryⓘ
The authors examined how to fairly distribute integer seats across groups arranged in a hierarchy, known as multi-level apportionment. Previous work showed it was possible to meet fairness rules called lower and upper quotas separately while keeping the allocation consistent when the total number of seats changes (house monotonicity). This paper proves that no single rule can simultaneously satisfy lower quota, upper quota, and house monotonicity at the same time for certain structured groupings called binary combs. They show this by linking the problem to mathematical bounds on discrepancies and sequences, concluding that any rule trying to satisfy all conditions will face an unavoidable contradiction.
Multi-level apportionmentLower quotaUpper quotaHouse monotonicityBinary combDiscrepancy theorySeat allocationVan der Corput sequenceQuantization penaltyMonotone path
Abstract
Multi-level apportionment allocates integer seats through a hierarchy of groups. Schmidt-Kraepelin, Suksompong, and Wijaya proved that, at every fixed house size, lower and upper quota can be satisfied simultaneously; they also constructed house-monotone rules satisfying either quota separately. They left open whether one rule can satisfy lower quota, upper quota, and house monotonicity together, even when quota is required only relative to the root. We give a negative answer. For a full binary comb with $D$ equally entitled leaves, every house-monotone allocation sequence induces a sequence of seat recipients. Quota for the nested comb groups would force every grid-aligned prefix discrepancy to be below one. A midpoint embedding then bounds the full interval discrepancy by this quantity plus $1/2$, contradicting Schmidt's logarithmic lower bound. Conversely, a binary van der Corput seat schedule has comb-prefix error at most $\log D/(3\log 2)+1$. Thus the optimal worst-case error on the comb is $Θ(\log D)$, and for sufficiently large finite $D$ no house-monotone quota rule exists. The proof isolates a static--dynamic gap: each house size admits a quota-feasible allocation, but the feasible allocations cannot be embedded into one monotone path. In quantization language, the result characterizes the order of the embedded-quantization penalty for progressive one-hot rounding on the comb.