Research map / Learning theory and algorithms / Fairness

The Panel Complexity of Sortition: Is 12 Angry Men Enough?

NeurIPS 2026 · Learning theory and algorithms › Fairness · approach: Causal and policy fairness in decisions · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Defines Wasserstein-based representative panels and derives panel-size bounds (panel complexity) for participatory budgeting and facility location under uniform sortition, with matching lower bounds.

Problem

How large must a uniformly random sortition panel be so that its decisions in social choice settings (participatory budgeting, facility location) yield welfare, core fairness, or outlier guarantees for the whole population?

Approach

Measures panel representativeness via Wasserstein-1 distance between panel and population feature distributions, giving a panel size independent of population size and of the number of features; combines this with sampling-without-replacement reductions, concentration, and camouflaged-population lower bounds.

Key results

• Panel of size O((1/eps)^2 (log ell + log(1/delta))) is eps-representative for ell real-valued features with probability 1-delta, independent of population size.
• For participatory budgeting with Lipschitz costs, panel size O((1/eps)^2 m log(1/eps)) gives expected social cost within additive tau+eps and multiplicative rho; a matching Omega((1/eps^2) m) lower bound is shown.
• For facility location in any metric space, panel size O(log(1/delta)) suffices for distance at most T*Opt with prob 1-delta for T>2; the guarantee fails for T<=2.

Surprising findings

• No panel decision rule can give a purely multiplicative social cost approximation in participatory budgeting, regardless of panel size.
• Stochastic dominance of Wasserstein distance under sampling without replacement versus with replacement fails in general (counterexample given).

Limitations

• Analysis restricted to uniform panel selection, which rules out ex-post guarantees for every panel in the lottery support.
• Upper bounds for participatory budgeting assume constant multiplicative factor rho; non-constant rho would increase panel complexity.

Experimental setup

Metrics: panel size bound expected social cost approximation core approximation parameters

Baselines: random dictatorship distance-minimizing panel selection

Builds on: Wasserstein distance (optimal transport) Hoeffding's inequality for sampling without replacement McDiarmid-style inequality for sampling without replacement

Closest papers by meaning

• Can a Few Decide for Many? The Metric Distortion of Sortition (ICML 2024 · similarity 0.89)
• Maintaining Proportional Committees with Dynamic Candidate Sets (ICML 2025 · similarity 0.83)
• Proportional Fairness in Clustering: A Social Choice Perspective (NeurIPS 2024 · similarity 0.82)
• Constant-Factor Distortion Mechanisms for k-Committee Election (AAAI 2025 · similarity 0.82)
• Unravelling Expressive Delegations: Complexity and Normative Analysis (AAAI 2024 · similarity 0.82)
• On the Distortion of Committee Election with 1-Euclidean Preferences and Few Distance Queries (AAAI 2025 · similarity 0.82)