Online Learning and Optimization for Revenue Problems with Add-on Discounts

• 成果类型: Article
• 署名作者: Simchi-Levi, David; Sun, Rui; Zhang, Huanan
• 署名单位: Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); Massachusetts Institute of Technology (MIT); University of Colorado System; University of Colorado Boulder
• 刊物名称: MANAGEMENT SCIENCE
• ISSN/ISSBN: 0025-1909
• DOI: 10.1287/mnsc.2021.4222
• 发表日期: 2022
• 页码: 7402-7421
• 关键词: revenue management; add-on discount; online learning; approximation algorithm

摘要

We study in this paper a revenue-management problem with add-on discounts. The problem is motivated by the practice in the video game industry by which a retailer offers discounts on selected supportive products (e.g., video games) to customers who have also purchased the core products (e.g., video game consoles). We formulate this problem as an optimization problem to determine the prices of different products and the selection of products for add-on discounts. In the base model, we focus on an independent demand structure. To overcome the computational challenge of this optimization problem, we propose an efficient fully polynomial-time approximation scheme (FPTAS) algorithm that solves the problem approximately to any desired accuracy. Moreover, we consider the problem in the setting in which the retailer has no prior knowledge of the demand functions of different products. To solve this joint learning and optimization problem, we propose an upper confidence bound???based learning algorithm that uses the FPTAS optimization algorithm as a subroutine. We show that our learning algorithm can converge to the optimal algorithm that has access to the true demand functions, and the convergence rate is tight up to a certain logarithmic term. We further show that these results for the independent demand model can be extended to multinomial logit choice models. In addition, we conduct numerical experiments with the real-world transaction data we collect from a popular video gaming brand???s online store on Tmall.com. The experiment results illustrate our learning algorithm???s robust performance and fast conver