Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2022
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2202.11061 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866929391298150400 |
|---|---|
| author | Gölz, Paul Peters, Dominik Procaccia, Ariel D. |
| author_facet | Gölz, Paul Peters, Dominik Procaccia, Ariel D. |
| contents | Apportionment is the problem of distributing $h$ indivisible seats across states in proportion to the states' populations. In the context of the US House of Representatives, this problem has a rich history and is a prime example of interactions between mathematical analysis and political practice. Grimmett (2004) suggested to apportion seats in a randomized way such that each state receives exactly their proportional share $q_i$ of seats in expectation (ex ante proportionality) and receives either $\lfloor q_i \rfloor$ or $\lceil q_i \rceil$ 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 which 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2202_11061 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | In This Apportionment Lottery, the House Always Wins Gölz, Paul Peters, Dominik Procaccia, Ariel D. Computer Science and Game Theory Apportionment is the problem of distributing $h$ indivisible seats across states in proportion to the states' populations. In the context of the US House of Representatives, this problem has a rich history and is a prime example of interactions between mathematical analysis and political practice. Grimmett (2004) suggested to apportion seats in a randomized way such that each state receives exactly their proportional share $q_i$ of seats in expectation (ex ante proportionality) and receives either $\lfloor q_i \rfloor$ or $\lceil q_i \rceil$ 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 which 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. |
| title | In This Apportionment Lottery, the House Always Wins |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2202.11061 |