Sequential Submodular Maximization and Applications to Ranking an Assortment of Products

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 makes a decision 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 ordering 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 (1-1/e)-approximation for this problem. We then consider a variant in which the platform not only cares about user engagement, but also cares 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)^3,(1-1/e)^3)-approximation for this problem by rounding an approximate solution of a linear programming relaxation which might be of independent interest . For the special case when underlying submodular functions are coverage functions -- which is practically relevant in online retail -- we propose an alternative LP relaxation and rounding for the problem. This approach yields to an optimal bi-criteria (1-1/e,1-1/e)-approximation algorithm