Technical Note-Assortment Optimization with Small Consideration Sets

• 成果类型: Article
• 署名作者: Feldman, Jacob; Paul, Alice; Topaloglu, Huseyin
• 署名单位: Washington University (WUSTL); Brown University
• 刊物名称: OPERATIONS RESEARCH
• ISSN/ISSBN: 0030-364X
• DOI: 10.1287/opre.2018.1803
• 发表日期: 2019
• 页码: 1283-1299
• 关键词: Price optimization; choice model; logit model; algorithms; approximation; management

摘要

We study a customer choice model that captures purchasing behavior when there is a limit on the number of times that a customer will substitute among the offered products. Under this model, we assume each customer is characterized by a ranked preference list of products and, upon arrival, will purchase the highest ranking offered product. Because we restrict ourselves to settings in which customers consider a limited number of products, we assume that these rankings contain at most k products. We call this model the k-product nonparametric choice model. We focus on the assortment optimization problem under this choice model. In this problem, the retailer wants to find the revenue-maximizing set of products to offer when the buying process of each customer is governed by the k-product nonparametric choice model. First, we show that the assortment problem is strongly NP-hard even for k = 2. Motivated by this result, we develop a linear programming- based randomized rounding algorithm that gives the best known approximation guarantee. We tighten the approximation guarantee further when each preference list contains at most two products and consider the case in which there is a limit on the number of products that can be offered to the customers.