Near-Optimal Dropout-Robust Sortition
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866917096529592320 |
|---|---|
| author | Gambhir, Maya Pal Flanigan, Bailey Roth, Aaron |
| author_facet | Gambhir, Maya Pal Flanigan, Bailey Roth, Aaron |
| contents | Citizens' assemblies - small panels of citizens that convene to deliberate on policy issues - often face the issue of panelists dropping out at the last-minute. Without intervention, these dropouts compromise the size and representativeness of the panel, prompting the question: Without seeing the dropouts ahead of time, can we choose panelists such that after dropouts, the panel will be representative and appropriately-sized? We model this problem as a minimax game: the minimizer aims to choose a panel that minimizes the loss, i.e., the deviation of the ultimate panel from predefined representation targets. Then, an adversary defines a distribution over dropouts from which the realized dropouts are drawn. Our main contribution is an efficient loss-minimizing algorithm, which remains optimal as we vary the maximizer's power from worst case to average case. Our algorithm - which iteratively plays a projected gradient descent subroutine against an efficient algorithm for computing the best-response dropout distribution - also addresses a key open question in the area: how to manage dropouts while ensuring that each potential panelist is chosen with relatively equal probabilities. Using real-world datasets, we compare our algorithms to existing benchmarks, and we offer the first characterizations of tradeoffs between robustness, loss, and equality in this problem. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_16897 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Near-Optimal Dropout-Robust Sortition Gambhir, Maya Pal Flanigan, Bailey Roth, Aaron Computer Science and Game Theory Citizens' assemblies - small panels of citizens that convene to deliberate on policy issues - often face the issue of panelists dropping out at the last-minute. Without intervention, these dropouts compromise the size and representativeness of the panel, prompting the question: Without seeing the dropouts ahead of time, can we choose panelists such that after dropouts, the panel will be representative and appropriately-sized? We model this problem as a minimax game: the minimizer aims to choose a panel that minimizes the loss, i.e., the deviation of the ultimate panel from predefined representation targets. Then, an adversary defines a distribution over dropouts from which the realized dropouts are drawn. Our main contribution is an efficient loss-minimizing algorithm, which remains optimal as we vary the maximizer's power from worst case to average case. Our algorithm - which iteratively plays a projected gradient descent subroutine against an efficient algorithm for computing the best-response dropout distribution - also addresses a key open question in the area: how to manage dropouts while ensuring that each potential panelist is chosen with relatively equal probabilities. Using real-world datasets, we compare our algorithms to existing benchmarks, and we offer the first characterizations of tradeoffs between robustness, loss, and equality in this problem. |
| title | Near-Optimal Dropout-Robust Sortition |
| topic | Computer Science and Game Theory |
| url | https://arxiv.org/abs/2511.16897 |