Near-Optimal Dropout-Robust Sortiton

Citizens' assemblies - small panels of citizens that convene to deliberate and make policy recommendations - often face the issue of panelists dropping out last-minute. These dropouts undermine two key goals: that the panel is (a) of a desired size, and (b) is descriptively representative of the population. This dropouts problem motivates the question: how can we choose the panel -or add extra participants to an existing panel - to ensure that after dropouts, the panel satisfied desiderata (a) and (b) to some guaranteed degree? The practical challenge is that panelists (or extras) must be selected before seeing who ultimately drops out. We model this problem as a minimax game: the minimizer chooses a panel (or extras); then, an adversary defines a randomization over dropouts from which the realized dropouts are drawn. The loss is then the deviation of the resulting panel from predefined descriptive representation targets. Our main contribution is an efficient loss-minimizing algorithm for selecting a panel (or extras), which achieves optimal expected loss even as we vary the adversary's power from worst case to average case. Our algorithm - which iteratively plays a projected gradient descent subroutine against a best-responder - also addresses a key issue left open by prior work on this problem: it allows us to control the selection probabilities with which we choose each potential panelist (or extra). We implement our algorithms and run them on datasets from real assemblies. We show robustness gains over previous algorithms, and we use our control over selection probabilities to offer the first exploration of trade-offs between randomness and representation in handling dropouts.