Discrete Optimization Problems under Ranking-Based Choice Models
Paul, Alice Joanna
We consider revenue management problems when customers purchase products according to a nonparametric choice model. In the nonparametric choice model, each customer arrives with a preference list and will purchase the highest-ranking offered product in her preference list. This choice model has attracted a lot of attention recently as a broad alternative to parametric models. However, the corresponding revenue management problems under this general model are intractable. This thesis introduces three models that are restrictions of the full nonparametric choice model and correspond to practical settings in which a retailer may want to use the nonparametric choice model. The models we introduce are simple to describe, easy to estimate, and admit tractable and profitable solutions. First, we introduce the nonparametric tree choice model. In this model, we assume the set of customer classes is derived from paths in a tree, in which the order of nodes visited along each path gives the corresponding preference list. To start with, we study assortment problems, in which the goal is to find which products to offer to maximize expected revenue. We give a dynamic programming solution which can be extended to versions of the assortment problem when there are fixed costs for offering a product, shelf constraints, or substitution costs. We then study the joint assortment and pricing problem, in which the goal is to simultaneously select the set of offered products as well as their prices. We solve the pricing problem optimally when the products are vertically differentiated, and hence the tree takes the form of a single path. We also solve the problem optimally on the general tree when the prices are restricted to be quality consistent; higher quality products must be priced above lower quality products. Last, we present computational experiments on both synthetic data and real hotel purchase data. Our estimation procedure shows both how to build the tree of products and how to estimate the underlying arrival probabilities of each customer type from historical sales data. These experiments show that the nonparametric tree choice model captures customer purchasing behavior more accurately than the multinomial logit choice model in the majority of test cases. Second, we study a customer choice model that captures purchasing behavior when customers substitute a limited number of times. Again, under this model, we assume each customer is characterized by a ranked preference list of products and will purchase the highest ranking product in her list that is offered. Since we restrict ourselves to settings with limited substitution, we assume that these preference lists 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. First, we show that this problem is NP-hard even for k=2. Motivated by this result, we show that the assortment problem under the 2-product nonparametric choice model can be reduced to a well-known graph optimization problem. Further, we develop a novel linear programming based rounding algorithm for the assortment optimization problem for general k. Through a series of computational experiments, we show that the proposed algorithm is easy to implement, efficient to run, and performs significantly better than its theoretical guarantee. Third, we introduce the sequential flips nonparametric choice model. This model subsumes a classic linear utility model used when products are vertically differentiated and a customer's utility of a product is a random linear function of the product's price and quality. By framing this model as a nonparametric choice model, we develop an efficient dynamic program to solve the corresponding assortment optimization problem. Further, this algorithm can be extended to the joint assortment and pricing optimization problem. After introducing and studying all of these models, we lastly present a general approximation algorithm for the space constrained assortment optimization problem that applies to two of the models above. In this setting, the retailer wants to choose a subset of products to offer to maximize expected revenue but is restricted by a knapsack constraint on the total size of the offered assortment. This constraint might occur in online settings in which the retailer wants to choose which products to display on the first page of search results or in a setting where there is a fixed physical space to display products.
Williamson, David P.
Topaloglu, Huseyin; Shmoys, David B.
PHD of Operations Research
Doctor of Philosophy
dissertation or thesis