# Sequential Submodular Maximization and Applications to Ranking an Assortment of Products

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Feb 2020.

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

- [Beyond Submodularity: A Unified Framework of Randomized Set Selection with Group Fairness Constraints](https://mlsanity.com/paper/2304.06596/) (2023)
- [Sampling Individually-Fair Rankings that are Always Group Fair](https://mlsanity.com/paper/2306.11964/) (2023)
- [Non-monotone Sequential Submodular Maximization](https://mlsanity.com/paper/2308.08641/) (2023)
- [Misalignment, Learning, and Ranking: Harnessing Users Limited Attention](https://mlsanity.com/paper/2402.14013/) (2024)
- [Unifying and Optimizing Data Values for Selection via Sequential Decision-Making](https://mlsanity.com/paper/2502.04554/) (2025)
- [Learning Submodular Sequencing from Samples](https://mlsanity.com/paper/2409.05265/) (2024)

## Abstract (arXiv)

We study a submodular maximization problem motivated by applications in online retail. A platform displays a list of products to a user in response to a search query. The user inspects the first k items in the list for a k chosen at random from a given distribution, and decides whether to purchase an item from that set based on a choice model. The goal of the platform is to maximize the engagement of the shopper defined as the probability of purchase. This problem gives rise to a less-studied variation of submodular maximization in which we are asked to choose an textitordering of a set of elements to maximize a linear combination of different submodular functions. First, using a reduction to maximizing submodular functions over matroids, we give an optimal left(1-1/eright)-approximation for this problem. We then consider a variant in which the platform cares not only about user engagement, but also about diversification across various groups of users, that is, guaranteeing a certain probability of purchase in each group. We characterize the polytope of feasible solutions and give a bi-criteria ((1-1/e)2,(1-1/e)2)-approximation for this problem by rounding an approximate solution of a linear programming relaxation. For rounding, we rely on our reduction and the particular rounding techniques for matroid polytopes. For the special case in which underlying submodular functions are coverage functions -- which is practically relevant in online retail -- we propose an alternative LP relaxation and a simpler randomized rounding for the problem. This approach yields to an optimal bi-criteria (1-1/e,1-1/e)-approximation algorithm for the special case of the problem with coverage functions.