Sequential Submodular Maximization and Applications to Ranking an Assortment of Products

Arash Asadpour (), Rad Niazadeh (), Amin Saberi () and Ali Shameli ()
Additional contact information
Arash Asadpour: Zicklin School of Business, City University of New York, New York, New York 10010
Rad Niazadeh: Chicago Booth School of Business, University of Chicago, Chicago, Illinois 60637
Amin Saberi: Management Science and Engineering, Stanford University, Stanford, California 94305
Ali Shameli: Core Data Science, Meta, Menlo Park, California 94025

Operations Research, 2023, vol. 71, issue 4, 1154-1170

Abstract: 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 algorithm for the special case of the problem with coverage functions.

Keywords: Revenue Management and Market Analytics; submodular maximization; product ranking; online retail; combinatorial optimization (search for similar items in EconPapers)
Date: 2023
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.2022.2370 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:71:y:2023:i:4:p:1154-1170

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().