Abstract
Digital platforms frequently encounter online combinatorial optimization problems, such as product ranking and assortment planning, where the goal is to maximize total utility. However, purely utilitarian objectives often marginalize minority demographic groups. This paper presents a general primal-dual framework that integrates group fairness constraints into complex online optimization tasks. By framing the problem as a max-min game between a utility-maximizing player and a fairness-auditing player, the proposed algorithm achieves sub-linear $\gamma$-regret while ensuring that group fairness violations remain within a specified tolerance.
Introduction
Online combinatorial optimization is a cornerstone of modern recommendation systems. Platforms like Amazon or Netflix must select subsets or rankings of items in real-time to maximize user engagement. A significant challenge arises when the preferences of minority groups diverge from the majority; a standard objective function may ignore these groups to maximize aggregate market share.
Existing solutions often struggle with the computational complexity of discrete decision spaces (e.g., submodular maximization) or are limited to offline settings. This work addresses the gap by providing a "fairness wrapper" for existing online algorithms, ensuring minority groups receive a "fair share" of the objective without requiring a complete redesign of the underlying optimization logic.
Methodology: A Primal-Dual Framework
The authors introduce a Robust Online Algorithm based on a primal-dual approach, conceptualized as a repeated game between two entities:
- The Max Player (Primal): This player aims to maximize the platform's utility objective using a "black-box" $\gamma$-no-regret online oracle. This modularity allows the framework to be applied to any combinatorial problem with an existing approximation algorithm.
- The Min Player (Dual): Acting as a fairness auditor, this player employs a no-regret Online Linear Optimization (OLO) algorithm, such as Projected Online Gradient Descent. It manages dual variables ($\alpha$) that serve as dynamic penalties. If a group's fairness threshold is not met, its corresponding dual variable increases, incentivizing the Max Player to prioritize that group in subsequent rounds.
Experimental Evaluation
The framework was evaluated using the MovieLens 1M dataset to simulate a movie recommendation system. Users were partitioned by gender and age, and the goal was to maximize "market share" (the probability of a user selecting at least one recommended movie) subject to group-specific fairness thresholds ($\tau$).
Performance and Regret
A key theoretical and empirical result is the achievement of sub-linear $\gamma$-regret. This indicates that the algorithm's performance relative to an approximate optimal benchmark improves over time, effectively learning the optimal fair strategy.
Fairness-Utility Trade-offs
By adjusting the fairness threshold $\tau$, the algorithm can trace the Pareto frontier between total utility and group equity. The experiments demonstrate that the algorithm successfully manages the trade-off between aggregate market share and group-level fairness, maintaining violations within acceptable bounds until the limit of feasibility is reached.
Key Results
- Theoretical Convergence: The algorithm guarantees that fairness violations converge to a small, user-defined threshold $\delta$ as time $T$ increases.
- Empirical Robustness: In MovieLens simulations, the algorithm maintained fairness violations within a 1% limit ($\delta = 0.01$) for a wide range of thresholds, only exceeding this when constraints became mathematically impossible.
- Dynamic Adaptation: The dual variables effectively "price" fairness, ensuring that underserved groups are prioritized dynamically based on historical performance.
Conclusion and Future Work
This research provides a robust, modular solution for incorporating fairness into online combinatorial optimization. While highly effective in stochastic environments, future work could explore adaptations for fully adversarial settings where rewards change dynamically. Additionally, investigating interior point methods for managing dual variables might further reduce the theoretical "slack" in fairness guarantees.
Summary updated