Online Combinatorial Optimization with Group Fairness Constraints

Negin Golrezaei, Rad Niazadeh, Kumar Kshitij Patel, Fransisca SusanIJCAI 2024

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:

  1. 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.
  2. 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.

Figure 1: Cumulative regret over time for different parameter settings, demonstrating sub-linear growth and effective learning.

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.

Figure 4: Comprehensive results showing (a) total market share, (b) average violation, and (c/d) group market shares across varying fairness thresholds.

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

BibTeX
@inproceedings{golrezaei2024online,
  author = {Negin Golrezaei and Rad Niazadeh and Kumar Kshitij Patel and Fransisca Susan},
  title = {{Online Combinatorial Optimization with Group Fairness Constraints}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure