Randomized Strategies for Ex-Ante Fairness

236 concepts141 papers1 proposal

Imagine you have a single kidney available for transplant and two patients who are equally good matches. A deterministic algorithm must choose one, leaving the other with nothing. In discrete optimization, machine learning, and resource allocation, forcing a decision-maker to make a single, fixed choice often introduces systemic bias or arbitrary unfairness. As Bonchi et al. point out, deterministic algorithms frequently make arbitrary choices among multiple optimal solutions, leading to individual inequity.

To resolve this, a major research direction shifts the problem from choosing a single deterministic outcome to optimizing a probability distribution over all possible outcomes. This is the core of ex-ante fairness: ensuring that every participant receives an equitable opportunity before any random choice is finalized.

Bypassing Computational and Mathematical Limits

Why do we randomize? The first reason is mathematical necessity. Many fairness objectives are completely intractable or impossible to approximate when restricted to deterministic choices.

For example, in influence maximization—the problem of choosing a set of "seed" users to spread information through a social network—achieving a fair distribution of information across different demographic groups is computationally impossible to approximate deterministically. However, Becker et al. demonstrate that introducing randomized seeding strategies changes the game, enabling a $(1 - 1/e)$ constant-factor approximation for group fairness. By optimizing over a distribution of possible seed sets rather than a single fixed set, the algorithm satisfies fairness constraints like maximin coverage much more effectively.

Similarly, in online resource allocation (where items arrive one by one and must be assigned immediately), deterministic algorithms hit a strict performance ceiling. Hosseini et al. note a $1/2$-approximation barrier for deterministic fairness metrics when items are indivisible, which randomized strategies can exceed.

By relaxing a discrete, combinatorial problem into a continuous probabilistic space, we can find fair solutions using efficient optimization tools like linear programming or greedy algorithms, as shown by Becker et al..

Smoothing Decision Boundaries

Randomization also provides a powerful mechanism to balance utility and equity near sharp decision thresholds. In traditional machine learning classifiers or search rankings, a deterministic "top-$k$" cutoff creates a harsh boundary: individuals just above the threshold receive the resource, while those just below receive nothing, even if their scores are statistically indistinguishable.

To satisfy strict fairness criteria like equalized odds, Hardt et al. introduced the concept of stochastic decision boundaries. By using randomized classification rules for individuals near a threshold, a decision-maker can bridge the gap between different groups' performance curves. Tang proves that incorporating this stochasticity into model predictions provides a mathematical guarantee for achieving perfect equalized odds, which is otherwise impossible for fixed, deterministic mappings.

This applies equally to algorithmic rankings and resource allocation. Singh et al. show that probabilistic rankings allow exposure to be allocated equitably in expectation across many queries, smoothing the trade-off between group equity and individual utility. Furthermore, the authors of a recent position paper argue that scarce resource allocations relying on machine learning should be randomized near decision boundaries. Combining a deterministic selection for top candidates with a randomized lottery for remaining slots maintains high selection quality while significantly reducing systemic exclusion.

From Expectation to Realization: The Ex-Ante to Ex-Post Bridge

The most significant challenge of randomized allocation is the tension between expectation and realization. A lottery might be perfectly fair ex-ante (everyone has a 50% chance), but the ex-post outcome (one person gets everything, the other gets nothing) can still be highly unequal. As the authors of work on simultaneous fairness and Sankararaman et al. emphasize, systems that are fair on average can still produce highly inequitable results in a single real-world execution.

To bridge this gap, researchers have developed sophisticated rounding and decomposition techniques that guarantee fairness both in expectation and in the final realized outcome.

The Bihierarchy Framework

One prominent approach is the bihierarchy framework and related matrix decomposition methods. As shown by Halpern et al. and in related work on simultaneous envy and equitability, researchers use the properties of totally unimodular matrices to decompose a fair fractional allocation into a probability distribution over deterministic allocations. Crucially, every single deterministic allocation in that distribution satisfies ex-post fairness properties. This ensures that the ex-ante fairness of the lottery translates directly into ex-post fairness once the final distribution of goods is determined, a property further extended to constrained environments by Cookson et al..

The Law of Large Numbers

Another mechanism relies on statistical concentration in large-scale or repeated settings. In problems like fair clustering or large cohort selection, algorithms first compute an optimal randomized distribution and then apply dependent rounding techniques, as explored by Henzinger et al.. As the size of the selected cohort or dataset grows, the variance inherent in probabilistic selection diminishes. This concentration of utility ensures that the actual group representation closely aligns with its expected value, providing robust ex-post fairness in practice without requiring hard deterministic constraints during the optimization phase, as demonstrated by Harb et al..

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_ex_ante_fairness_082d5939,
  title = {ex-ante fairness},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/ex-ante-fairness/rdr_082d5939661141f1ad2ea9922e52d225},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_ex_ante_fairness_082d5939_v1,
  title = {ex-ante fairness},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/ex-ante-fairness/rdr_082d5939661141f1ad2ea9922e52d225/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake