# Maximizing Submodular Functions for Recommendation in the Presence of Biases

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 76 references that are in the map.
- First posted on arXiv 3 May 2023.

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

- [Preventing Fairness Gerrymandering: Auditing and Learning for Subgroup Fairness](https://mlsanity.com/paper/1711.05144/) (2017)
- [Fairness of Exposure in Rankings](https://mlsanity.com/paper/1802.07281/) (2018)
- [Fairness-Aware Ranking in Search & Recommendation Systems with Application to LinkedIn Talent Search](https://mlsanity.com/paper/1905.01989/) (2019)
- [Equity of Attention: Amortizing Individual Fairness in Rankings](https://mlsanity.com/paper/1805.01788/) (2018)
- [Lazier Than Lazy Greedy](https://mlsanity.com/paper/1409.7938/) (2014)
- [Beyond Parity: Fairness Objectives for Collaborative Filtering](https://mlsanity.com/paper/1705.08804/) (2017)
- [Fairness in Rankings and Recommendations: An Overview](https://mlsanity.com/paper/2104.05994/) (2021)
- [Selection Problems in the Presence of Implicit Bias](https://mlsanity.com/paper/1801.03533/) (2018)
- [Exploring Author Gender in Book Rating and Recommendation](https://mlsanity.com/paper/1808.07586/) (2018)
- [Fairness in Information Access Systems](https://mlsanity.com/paper/2105.05779/) (2021)
- [Interventions for Ranking in the Presence of Implicit Bias](https://mlsanity.com/paper/2001.08767/) (2020)
- [FairSearch: A Tool For Fairness in Ranked Search Results](https://mlsanity.com/paper/1905.13134/) (2019)
- [Fair ranking: a critical review, challenges, and future directions](https://mlsanity.com/paper/2201.12662/) (2022)
- [Distributed Submodular Maximization](https://mlsanity.com/paper/1411.0541/) (2014)
- [Balanced Ranking with Diversity Constraints](https://mlsanity.com/paper/1906.01747/) (2019)
- [Dialect Diversity in Text Summarization on Twitter](https://mlsanity.com/paper/2007.07860/) (2020)
- [Auditing Search Engines for Differential Satisfaction Across Demographics](https://mlsanity.com/paper/1705.10689/) (2017)
- [Allocating Opportunities in a Dynamic Model of Intergenerational Mobility](https://mlsanity.com/paper/2101.08451/) (2021)
- [On Fair Selection in the Presence of Implicit and Differential Variance](https://mlsanity.com/paper/2112.05630/) (2021)
- [Adaptive, Personalized Diversity for Visual Discovery](https://mlsanity.com/paper/1810.01477/) (2018)
- [Popularity Bias in Recommendation: A Multi-stakeholder Perspective](https://mlsanity.com/paper/2008.08551/) (2020)
- [The Effect of the Rooney Rule on Implicit Bias in the Long Term](https://mlsanity.com/paper/2010.10992/) (2020)
- [Selection in the Presence of Implicit Bias: The Advantage of Intersectional Constraints](https://mlsanity.com/paper/2202.01661/) (2022)
- [Mostra: A Flexible Balancing Framework to Trade-off User, Artist and Platform Objectives for Music Sequencing](https://mlsanity.com/paper/2204.10463/) (2022)
- [Team Performance with Test Scores](https://mlsanity.com/paper/1506.00147/) (2015)
- [Maximizing coverage while ensuring fairness: a tale of conflicting objective](https://mlsanity.com/paper/2007.08069/) (2020)
- [Fairness in Maximal Covering Location Problems](https://mlsanity.com/paper/2204.06446/) (2022)
- [Balancing Utility and Fairness in Submodular Maximization (Technical Report)](https://mlsanity.com/paper/2211.00980/) (2022)
- [The Complexity of Finding Fair Many-to-One Matchings](https://mlsanity.com/paper/2206.06988/) (2022)

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

- [Subset Selection Based On Multiple Rankings in the Presence of Bias: Effectiveness of Fairness Constraints for Multiwinner Voting Score Functions](https://mlsanity.com/paper/2306.09835/) (2023)
- [When Sample Selection Bias Precipitates Model Collapse](https://mlsanity.com/paper/2606.13732/) (2026)
- [Centralized Selection with Preferences in the Presence of Biases](https://mlsanity.com/paper/2409.04897/) (2024)
- [Theoretically Grounded Pruning of Large Ground Sets for Constrained, Discrete Optimization](https://mlsanity.com/paper/2410.17945/) (2024)
- [Online Two-Stage Submodular Maximization](https://mlsanity.com/paper/2510.19480/) (2025)

## Abstract (arXiv)

Subset selection tasks, arise in recommendation systems and search engines and ask to select a subset of items that maximize the value for the user. The values of subsets often display diminishing returns, and hence, submodular functions have been used to model them. If the inputs defining the submodular function are known, then existing algorithms can be used. In many applications, however, inputs have been observed to have social biases that reduce the utility of the output subset. Hence, interventions to improve the utility are desired. Prior works focus on maximizing linear functions -- a special case of submodular functions -- and show that fairness constraint-based interventions can not only ensure proportional representation but also achieve near-optimal utility in the presence of biases. We study the maximization of a family of submodular functions that capture functions arising in the aforementioned applications. Our first result is that, unlike linear functions, constraint-based interventions cannot guarantee any constant fraction of the optimal utility for this family of submodular functions. Our second result is an algorithm for submodular maximization. The algorithm provably outputs subsets that have near-optimal utility for this family under mild assumptions and that proportionally represent items from each group. In empirical evaluation, with both synthetic and real-world data, we observe that this algorithm improves the utility of the output subset for this family of submodular functions over baselines.