City Sampling for Citizens' Assemblies
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914029680721920 |
|---|---|
| author | Gölz, Paul Maly, Jan Schmidt-Kraepelin, Ulrike Utke, Markus Verpoort, Philipp C. |
| author_facet | Gölz, Paul Maly, Jan Schmidt-Kraepelin, Ulrike Utke, Markus Verpoort, Philipp C. |
| contents | In citizens' assemblies, a group of constituents is randomly selected to weigh in on policy issues. We study a two-stage sampling problem faced by practitioners in countries such as Germany, in which constituents' contact information is stored at a municipal level. As a result, practitioners can only select constituents from a bounded number of cities ex post, while ensuring equal selection probability for constituents ex ante.
We develop several algorithms for this problem. Although minimizing the number of contacted cities is NP-hard, we provide a pseudo-polynomial time algorithm and an additive 1-approximation, both based on separation oracles for a linear programming formulation. Recognizing that practical objectives go beyond minimizing city count, we further introduce a simple and more interpretable greedy algorithm, which additionally satisfies an ex-post monotonicity property and achieves an additive 2-approximation. Finally, we explore a notion of ex-post proportionality, for which we propose two practical algorithms: an optimal algorithm based on column generation and integer linear programming and a simple heuristic creating particularly transparent distributions. We evaluate these algorithms on data from Germany, and plan to deploy them in cooperation with a leading nonprofit organization in this space. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_07557 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | City Sampling for Citizens' Assemblies Gölz, Paul Maly, Jan Schmidt-Kraepelin, Ulrike Utke, Markus Verpoort, Philipp C. Computer Science and Game Theory Probability In citizens' assemblies, a group of constituents is randomly selected to weigh in on policy issues. We study a two-stage sampling problem faced by practitioners in countries such as Germany, in which constituents' contact information is stored at a municipal level. As a result, practitioners can only select constituents from a bounded number of cities ex post, while ensuring equal selection probability for constituents ex ante. We develop several algorithms for this problem. Although minimizing the number of contacted cities is NP-hard, we provide a pseudo-polynomial time algorithm and an additive 1-approximation, both based on separation oracles for a linear programming formulation. Recognizing that practical objectives go beyond minimizing city count, we further introduce a simple and more interpretable greedy algorithm, which additionally satisfies an ex-post monotonicity property and achieves an additive 2-approximation. Finally, we explore a notion of ex-post proportionality, for which we propose two practical algorithms: an optimal algorithm based on column generation and integer linear programming and a simple heuristic creating particularly transparent distributions. We evaluate these algorithms on data from Germany, and plan to deploy them in cooperation with a leading nonprofit organization in this space. |
| title | City Sampling for Citizens' Assemblies |
| topic | Computer Science and Game Theory Probability |
| url | https://arxiv.org/abs/2509.07557 |