Sequential Submodular Maximization and Applications to Ranking an Assortment of Products
Arash Asadpour, Rad Niazadeh, Amin Saberi, Ali Shameli · Proceedings of the 23rd ACM Conference on Economics and Computation · 2022
We introduce and study a variation of the 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 ordering of a set of elements to maximize a linear combination of different submodular functions.