# Beyond Submodularity: A Unified Framework of Randomized Set Selection with Group Fairness Constraints

arXiv: https://arxiv.org/abs/2304.06596 · HTML: https://mlsanity.com/paper/2304.06596/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 37 references that are in the map.
- First posted on arXiv 13 Apr 2023.

## Builds on (most cited first, 19 of 19)

- [Convex Optimization: Algorithms and Complexity](https://mlsanity.com/paper/1405.4980/) (2014)
- [Fair Clustering Through Fairlets](https://mlsanity.com/paper/1802.05733/) (2018)
- [Fairness in Learning: Classic and Contextual Bandits](https://mlsanity.com/paper/1605.07139/) (2016)
- [Fairness in Recommendation Ranking through Pairwise Comparisons](https://mlsanity.com/paper/1903.00780/) (2019)
- [Ranking with Fairness Constraints](https://mlsanity.com/paper/1704.06840/) (2017)
- [Pairwise Fairness for Ranking and Regression](https://mlsanity.com/paper/1906.05330/) (2019)
- [The Fairness of Risk Scores Beyond Classification: Bipartite Ranking and the xAUC Metric](https://mlsanity.com/paper/1902.05826/) (2019)
- [Fair and Diverse DPP-based Data Summarization](https://mlsanity.com/paper/1802.04023/) (2018)
- [Optimal approximation for submodular and supermodular optimization with bounded curvature](https://mlsanity.com/paper/1311.4728/) (2013)
- [Mitigating Bias in Set Selection with Noisy Protected Attributes](https://mlsanity.com/paper/2011.04219/) (2020)
- [Fairness in Streaming Submodular Maximization: Algorithms and Hardness](https://mlsanity.com/paper/2010.07431/) (2020)
- [Group-Fairness in Influence Maximization](https://mlsanity.com/paper/1903.00967/) (2019)
- [Constrained Submodular Maximization via a Non-symmetric Technique](https://mlsanity.com/paper/1611.03253/) (2016)
- [Online Submodular Maximization with Preemption](https://mlsanity.com/paper/1501.05801/) (2015)
- [Fair Assortment Planning](https://mlsanity.com/paper/2208.07341/) (2022)
- [On Maximizing Sums of Non-monotone Submodular and Linear Functions](https://mlsanity.com/paper/2205.15874/) (2022)
- [Sequential Submodular Maximization and Applications to Ranking an Assortment of Products](https://mlsanity.com/paper/2002.09458/) (2020)
- [Group Fairness in Non-monotone Submodular Maximization](https://mlsanity.com/paper/2302.01546/) (2023)
- [Achieving Long-term Fairness in Submodular Maximization through Randomization](https://mlsanity.com/paper/2304.04700/) (2023)

## Built on by (most cited first, 2 of 2)

- [Fairness in Submodular Maximization over a Matroid Constraint](https://mlsanity.com/paper/2312.14299/) (2023)
- [Towards Fairness and Privacy: A Novel Data Pre-processing Optimization Framework for Non-binary Protected Attributes](https://mlsanity.com/paper/2410.00836/) (2024)

## Abstract (arXiv)

Machine learning algorithms play an important role in a variety of important decision-making processes, including targeted advertisement displays, home loan approvals, and criminal behavior predictions. Given the far-reaching impact of these algorithms, it is crucial that they operate fairly, free from bias or prejudice towards certain groups in the population. Ensuring impartiality in these algorithms is essential for promoting equality and avoiding discrimination. To this end we introduce a unified framework for randomized subset selection that incorporates group fairness constraints. Our problem involves a global utility function and a set of group utility functions for each group, here a group refers to a group of individuals (e.g., people) sharing the same attributes (e.g., gender). Our aim is to generate a distribution across feasible subsets, specifying the selection probability of each feasible set, to maximize the global utility function while meeting a predetermined quota for each group utility function in expectation. Note that there may not necessarily be any direct connections between the global utility function and each group utility function. We demonstrate that this framework unifies and generalizes many significant applications in machine learning and operations research. Our algorithmic results either improves the best known result or provide the first approximation algorithms for new applications.