Trading-off price for data quality to achieve fair online allocation

Mathieu Molina, Nicolas Gast, Patrick Loiseau, Vianney Perchet

TL;DR

This paper tackles the challenge of fair online allocation when sensitive user attributes (like gender or ethnicity) are hidden but can be purchased from third-party sources of varying quality and cost. By combining dual gradient descent with an adversarial bandit algorithm (EXP3), the authors present a method that jointly optimizes data purchasing and fair allocation, achieving an optimal $\mathcal{O}(\sqrt{T})$ regret bound. Crucially, they prove that randomizing between different data sources is mathematically required to achieve long-term fairness.

What Problem Does This Paper Address?

Online allocation algorithms—such as those used in targeted job advertising, workforce hiring, or refugee resettlement—typically aim to maximize a cumulative reward (clicks, hires, successful placements) while satisfying long-term group fairness constraints.

However, almost all existing literature assumes a major luxury: that the decision-maker can perfectly observe users' protected attributes upfront. In reality, privacy regulations (like GDPR), user opt-outs, or missing data make this assumption unrealistic. A decision-maker often has to buy proxy data from third-party brokers to estimate these attributes.

This introduces a complex trade-off: higher-quality data gives better fairness estimates but costs more. The decision-maker faces a coupled problem: When and from which source should they buy data, and how should they allocate resources fairly based on imperfect estimates?

Methods

The authors model this problem as a multi-armed bandit problem coupled with an online allocation task under a long-term fairness penalty. They introduce Algorithm 1 (and generalized variants), which concurrently solves both challenges using two main components:

  1. Dual Gradient Descent: The algorithm maintains and updates a dual parameter ($\lambda_t$) that acts as a running tally of the system's unfairness. If the allocation becomes unbalanced, $\lambda_t$ adjusts to penalize choices that worsen the disparity.
  2. Adversarial Bandit Selection (EXP3): To decide which data source to buy from at each step, the algorithm uses the EXP3 framework. Instead of optimizing for raw utility, it optimizes a virtual reward that subtracts the cost of the data and a fairness penalty weighted by the current dual parameter $\lambda_t$.

A key technical novelty is that the algorithm actively randomizes its source selection rather than trying to converge on a single "best" source. This convexifies the strategy space, allowing the dual parameters to remain bounded and stable.

Datasets

The paper does not use real-world datasets. Instead, the authors validate their theoretical findings using a stylized synthetic data model (detailed in Appendix F):

  • Data Setup: A binary setting where utilities ($u_t \in \{-1, 1\}$) and protected attributes ($a_t \in \{-1, 1\}$) are equiprobable.
  • Sources: Two symmetric information sources, each capable of identifying "good" individuals from one specific group while providing noisy/default data for the other.

This simulated environment allows the authors to precisely isolate and analyze how varying data prices ($p$) and fairness scaling factors ($r$) impact the optimal allocation strategy.

Key Insights and Ideas

  • The Necessity of Randomization: In standard multi-armed bandit problems, randomization is just an exploration mechanism to find the single best arm. Here, the authors prove that randomization is part of the optimal exploitation strategy. Because the long-term fairness penalty couples all decisions across time, any static policy (always picking the same data source) results in linear regret. Alternating between sources is required to maintain balance.
  • Artificial Non-Stationarity: Updating the dual parameter $\lambda_t$ changes the virtual rewards for the bandit algorithm at every step. This creates an artificial non-stationarity feedback loop. The authors successfully prove that their single-phase algorithm can stabilize this loop.
  • Learning on the Fly: The authors demonstrate that the decision-maker doesn't even need to know the expected utilities conditional on the context beforehand; the framework can be extended to learn these utilities dynamically using linear contextual bandit techniques.

Key Results

  • Sub-linear Regret Bound: The authors prove that their algorithm achieves an expected regret bound of $\mathcal{O}(\sqrt{T})$, which matches the theoretical lower bound for standard stochastic bandits and proves the algorithm's efficiency over long horizons.
  • Outperforming Static Policies: Both theoretically (Proposition 2.1) and numerically, the authors show that $\text{static-OPT} + bT < \text{OPT}$ (where $b > 0$). In simulations, Algorithm 1 closely tracks the true offline optimum ($\text{OPT}$), while an algorithm restricted to the single "best" fixed source fails to achieve fairness and drops to a total utility of zero.
Total Utility after 100,000 rounds (from simulation):
│
├─ Offline Optimum (OPT): ~25,000
├─ Algorithm 1 (Proposed): ~24,000
└─ Static Source Baseline: 0 (Cannot be fair without shutting down)

Limitations and Future Work

  • The i.i.d. Assumption: The core proof relies on the assumption that users arrive in an independent and identically distributed (i.i.d.) manner. While common, this doesn't capture environments with seasonal trends or adversarial shifts.
  • No Hard Budgets: The model treats data costs and fairness violations as soft penalties within the objective function. It does not accommodate hard, unyielding budget constraints (e.g., "you only have \$1,000 to spend on data total").
  • Non-Stationary Distributions: The authors note that extending the algorithm to handle intermediate, non-stationary scenarios—where the distribution of protected attributes shifts over time—remains an open and challenging question.

Summary updated

Abstract

We consider the problem of online allocation subject to a long-term fairness penalty. Contrary to existing works, however, we do not assume that the decision-maker observes the protected attributes -- which is often unrealistic in practice. Instead they can purchase data that help estimate them from sources of different quality; and hence reduce the fairness penalty at some cost. We model this problem as a multi-armed bandit problem where each arm corresponds to the choice of a data source, coupled with the online allocation problem. We propose an algorithm that jointly solves both problems and show that it has a regret bounded by $\mathcal{O}(\sqrt{T})$. A key difficulty is that the rewards received by selecting a source are correlated by the fairness penalty, which leads to a need for randomization (despite a stochastic setting). Our algorithm takes into account contextual information available before the source selection, and can adapt to many different fairness notions. We also show that in some instances, the estimates used can be learned on the fly.
BibTeX
@inproceedings{molina2023trading,
  author = {Mathieu Molina and Nicolas Gast and Patrick Loiseau and Vianney Perchet},
  title = {{Trading-off price for data quality to achieve fair online allocation}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2023},
  url = {https://openreview.net/forum?id=KUBFYAPdqN},
}
Figure