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:
- 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.
- 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