# Balancing Utility and Fairness in Submodular Maximization (Technical Report)

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 89 references that are in the map.
- First posted on arXiv 2 Nov 2022.

## Builds on (most cited first, 30 of 33)

- [Equality of Opportunity in Supervised Learning](https://mlsanity.com/paper/1610.02413/) (2016)
- [A Survey on Bias and Fairness in Machine Learning](https://mlsanity.com/paper/1908.09635/) (2019)
- [Lazier Than Lazy Greedy](https://mlsanity.com/paper/1409.7938/) (2014)
- [Fairness in Graph Mining: A Survey](https://mlsanity.com/paper/2204.09888/) (2022)
- [Fair k-Center Clustering for Data Summarization](https://mlsanity.com/paper/1901.08628/) (2019)
- [Discrimination in the Age of Algorithms](https://mlsanity.com/paper/1902.03731/) (2019)
- [Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints](https://mlsanity.com/paper/1311.2106/) (2013)
- [Designing Fair Ranking Schemes](https://mlsanity.com/paper/1712.09752/) (2017)
- [Robust Optimization for Non-Convex Objectives](https://mlsanity.com/paper/1707.01047/) (2017)
- [Approximation Algorithms for Socially Fair Clustering](https://mlsanity.com/paper/2103.02512/) (2021)
- [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)
- [Distributed Submodular Maximization](https://mlsanity.com/paper/1411.0541/) (2014)
- [Maxmin-Fair Ranking: Individual Fairness under Group-Fairness Constraints](https://mlsanity.com/paper/2106.08652/) (2021)
- [Algorithms for Approximate Minimization of the Difference Between Submodular Functions, with Applications](https://mlsanity.com/paper/1408.2051/) (2014)
- [Diversity-aware k-median : Clustering with fair center representation](https://mlsanity.com/paper/2106.11696/) (2021)
- [Fair-by-design matching](https://mlsanity.com/paper/1802.02562/) (2018)
- [Robust Monotone Submodular Function Maximization](https://mlsanity.com/paper/1507.06616/) (2015)
- [On Fair Selection in the Presence of Implicit and Differential Variance](https://mlsanity.com/paper/2112.05630/) (2021)
- [Leveraging Sparsity for Efficient Submodular Data Summarization](https://mlsanity.com/paper/1703.02690/) (2017)
- [An Efficient Framework for Balancing Submodularity and Cost](https://mlsanity.com/paper/2002.07782/) (2020)
- [Rawlsian Fairness in Online Bipartite Matching: Two-sided, Group, and Individual](https://mlsanity.com/paper/2201.06021/) (2022)
- [Structured Robust Submodular Maximization: Offline and Online Algorithms](https://mlsanity.com/paper/1710.04740/) (2017)
- [Trade-offs between Group Fairness Metrics in Societal Resource Allocation](https://mlsanity.com/paper/2202.12334/) (2022)
- [Submodular Optimization over Sliding Windows](https://mlsanity.com/paper/1610.09984/) (2016)
- [Multi-Objective Maximization of Monotone Submodular Functions with Cardinality Constraint](https://mlsanity.com/paper/1711.06428/) (2017)
- [SAGA: A Submodular Greedy Algorithm For Group Recommendation](https://mlsanity.com/paper/1712.09123/) (2017)
- [Maximizing coverage while ensuring fairness: a tale of conflicting objective](https://mlsanity.com/paper/2007.08069/) (2020)
- [Real-Time Influence Maximization on Dynamic Social Streams](https://mlsanity.com/paper/1702.01586/) (2017)
- [Balancing spreads of influence in a social network](https://mlsanity.com/paper/1906.00074/) (2019)

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

- [Maximizing Submodular Functions for Recommendation in the Presence of Biases](https://mlsanity.com/paper/2305.02806/) (2023)
- [Fairness in Submodular Maximization over a Matroid Constraint](https://mlsanity.com/paper/2312.14299/) (2023)

## Abstract (arXiv)

Submodular function maximization is a fundamental combinatorial optimization problem with plenty of applications -- including data summarization, influence maximization, and recommendation. In many of these problems, the goal is to find a solution that maximizes the average utility over all users, for each of whom the utility is defined by a monotone submodular function. However, when the population of users is composed of several demographic groups, another critical problem is whether the utility is fairly distributed across different groups. Although the utility and fairness objectives are both desirable, they might contradict each other, and, to the best of our knowledge, little attention has been paid to optimizing them jointly. To fill this gap, we propose a new problem called Bicriteria Submodular Maximization (BSM) to balance utility and fairness. Specifically, it requires finding a fixed-size solution to maximize the utility function, subject to the value of the fairness function not being below a threshold. Since BSM is inapproximable within any constant factor, we focus on designing efficient instance-dependent approximation schemes. Our algorithmic proposal comprises two methods, with different approximation factors, obtained by converting a BSM instance into other submodular optimization problem instances. Using real-world and synthetic datasets, we showcase applications of our proposed methods in three submodular maximization problems: maximum coverage, influence maximization, and facility location.