Is Sortition Both Representative and Fair?

Soroush Ebadian, Gregory Kehne, Evi Micha, Ariel D. Procaccia, Nisarg ShahNeurIPS 2022 · OpenReview

Introduction

Can a randomly selected "citizens' assembly" be both perfectly fair and truly representative? This paper proves that it depends on your definition of representation: if you want a majority of the panel to reflect your interests, uniform random selection works beautifully. However, if you only need a small minority to represent you, perfect fairness and guaranteed representation are mathematically incompatible.

Sortition—the process of choosing political representatives by lottery rather than election—is seeing a modern resurgence in the form of "citizens' assemblies." Proponents argue sortition is the gold standard for fairness (everyone has an equal chance of being picked) and representation (the panel should be a "mini-public" that mirrors the population).

However, these two goals are often in tension. While uniform random selection is perfectly fair, it doesn't guarantee a representative outcome in every instance. The authors seek to formalize this tension using the lens of "distortion" from social choice theory. They ask: if we assume people exist in a "representation metric" (where distance equals dissimilarity), can a selection algorithm guarantee that the resulting panel's "social cost" (how poorly the population is represented) is close to the theoretical optimum?

Methods

The authors introduce a framework based on a representation metric—a distance function $d(i, j)$ between individuals. They define the $q$-cost of an individual as their distance to the $q$-th closest member of the panel.

  • If $q=1$, you only care about having one person like you on the panel.
  • If $q=k/2$ (where $k$ is panel size), you want a majority of the panel to be somewhat similar to you.

The paper evaluates algorithms based on two metrics:

  1. Fairness: The ratio of an individual's minimum selection probability to the "ideal" $k/n$.
  2. Representation: The ratio of the social cost of the optimal panel to the expected social cost of the chosen panel (a value of 1 is perfect).

The authors analyze Uniform Selection and propose a new algorithm, RANDOMREPLACE. This algorithm starts with an optimal (but unfair) panel and replaces a subset of members with randomly chosen individuals to "buy back" fairness while maintaining a provable representation floor.

Algorithm 1: RANDOMREPLACE

To move beyond worst-case theory, the authors tested their ideas on two real-world demographic datasets: the UCI Adult Dataset (1994 US Census data) and the European Social Survey (ESS). They constructed synthetic metrics by assigning random weights to these features, creating a high-dimensional space where "distance" represents how different two citizens are across demographic and ideological markers.

Key Insights and Results

  • The "Majority" Threshold: The paper discovers a sharp phase transition at $q = k/2$. If you define representation as "a majority of the panel should be near me" ($q > k/2$), then uniform random selection is excellent. It achieves a representation ratio of at least $\frac{1}{2} \cdot \frac{k-q+1}{k}$, proving that "perfect fairness" is compatible with "good representation" in the majority-rule regime.
  • The Fairness Trap: If you only care about a small number of representatives ($q \le k/2$), a mathematical "impossibility" emerges. Any algorithm with fairness strictly greater than $\approx 2q/k$ has a worst-case representation of zero.
  • The RANDOMREPLACE Tradeoff: The RANDOMREPLACE algorithm successfully bridges the gap. By relaxing the fairness requirement slightly (ensuring a $q/n$ probability instead of $k/n$), it guarantees a representation of at least $1/(q+1)$, providing a "knob" for practitioners to tune the balance between fairness and representation.
  • Real-World vs. Theory: While the math says uniform selection could be terrible for small $q$, experiments on Adult and ESS data show it actually performs quite well in practice (usually >55% representation). There is a visible "spike" in representation quality exactly at $q = k/2$, validating the theoretical prediction of a regime shift.

Limitations and Future Work

  • Metric Construction: The entire framework relies on the existence of a "representation metric." In the real world, deciding which features (age, race, income, religion) should define "distance" is a deeply political and subjective task.
  • Computational Complexity: Finding the "optimal" panel (the baseline for representation) is an NP-hard problem. While good approximations exist, it adds a layer of computational overhead.
  • Alternative Costs: The authors focused on the $q$-th closest neighbor. Future work could explore other cost functions, such as the average distance to all panel members or the maximum distance.

Summary updated

Abstract

Sortition is a form of democracy built on random selection of representatives. Two of the key arguments in favor of sortition are that it provides representation (a random panel reflects the composition of the population) and fairness (everyone has a chance to participate). Uniformly random selection is perfectly fair, but is it representative? Towards answering this question, we introduce the notion of a representation metric on the space of individuals, and assume that the cost of an individual for a panel is determined by the $q$-th closest representative; the representation of a (random) panel is measured by the ratio between the (expected) sum of costs of the optimal panel for the individuals and that of the given panel. For $k/2 < q \le k-\Omega(k)$, where $k$ is the panel size, we show that uniform random selection is indeed representative by establishing a constant lower bound on this ratio. By contrast, for $q \leq k/2$, no random selection algorithm that is almost fair can give such a guarantee. We therefore consider relaxed fairness guarantees and develop a new random selection algorithm that sheds light on the tradeoff between representation and fairness.
BibTeX
@inproceedings{ebadian2022is,
  author = {Soroush Ebadian and Gregory Kehne and Evi Micha and Ariel D. Procaccia and Nisarg Shah},
  title = {{Is Sortition Both Representative and Fair?}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=l7aekTjF6CO},
}
Figure