Overview
This study investigates multi-level apportionment, which involves allocating integer seats across a hierarchy of groups. Specifically, it addresses whether a single rule can simultaneously satisfy lower quota, upper quota, and house monotonicity, a question previously left open by Schmidt-Kraepelin, Suksompong, and Wijaya.
Research Context
Schmidt-Kraepelin, Suksompong, and Wijaya had previously established that, for any fixed house size, both lower and upper quotas could be met concurrently in multi-level apportionment. They also developed house-monotone rules capable of satisfying either lower or upper quota independently. However, the possibility of a single rule achieving lower quota, upper quota, and house monotonicity simultaneously, even when quota was defined only relative to the root, remained unaddressed.
Approach
The research employed a theoretical approach focusing on a specific hierarchical structure: a full binary comb with $D$ equally entitled leaves. The analysis involved:
- Examining the sequence of seat recipients induced by every house-monotone allocation sequence on this comb structure.
- Assessing the implications of quota requirements for nested comb groups, which would necessitate every grid-aligned prefix discrepancy to be below one.
- Utilizing a midpoint embedding to establish a bound on the full interval discrepancy. This bound was set as the grid-aligned prefix discrepancy plus $1/2$.
- Contrasting this bound with Schmidt's established logarithmic lower bound for discrepancy.
- Introducing a binary van der Corput seat schedule to quantify the comb-prefix error.
Findings
The study yielded a negative answer to the open question regarding the simultaneous satisfaction of lower quota, upper quota, and house monotonicity. Key findings include:
- For a full binary comb with $D$ equally entitled leaves, any house-monotone allocation sequence generates a sequence of seat recipients.
- Maintaining quota for the nested comb groups would require all grid-aligned prefix discrepancies to be less than one.
- A midpoint embedding demonstrates that the full interval discrepancy is bounded by the grid-aligned prefix discrepancy plus $1/2$. This finding contradicts Schmidt's logarithmic lower bound.
- Conversely, a binary van der Corput seat schedule exhibits a comb-prefix error of at most $\log D/(3\log 2)+1$.
- The optimal worst-case error for this comb structure is $\Theta(\log D)$.
- For sufficiently large finite $D$, it is impossible for a house-monotone quota rule to exist.
- The proof highlights a static-dynamic gap: while each specific house size can accommodate a quota-feasible allocation, these feasible allocations cannot be integrated into a single monotone path.
- In the context of quantization, the result quantifies the embedded-quantization penalty associated with progressive one-hot rounding on the comb.