Sequential Submodular Maximization and Applications to Ranking an Assortment of Products

• 成果类型: Article
• 署名作者: Asadpour, Arash; Niazadeh, Rad; Saberi, Amin; Shameli, Ali
• 署名单位: City University of New York (CUNY) System; Baruch College (CUNY); University of Chicago; Stanford University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2022.2370
• 发表日期: 2023
• 页码: 1154-1170
• 关键词: MULTINOMIAL LOGIT MODEL; multilinear relaxation; revenue management; choice model; optimization; approximation

摘要

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 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 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 bicriteria ((1 - 1/e)(2), (1 - 1/e)(2))-approximation for this problem by rounding an approximate solution of a linear-programming (LP) 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 bicriteria (1 - 1/e, 1 - 1/e)-approximation algorithmfor the special case of the problem with coverage functions.