UC Berkeley

Online recommendation systems ask these questions everyday: How to describe customers' purchasing behavior? How to design a product assortment in order to maximize their expected profit/revenue with given customers' behavior? What is the optimal pricing strategy for an assortment? Even further, how to jointly design optimal assortment and pricing at the same time in an efficient way? The answers to these questions have a direct influence to the profitability and feasibility of the recommendation systems.

My thesis handles assortment and price optimization problems with various applications in online e-commerce and travel related recommendations, such as flight, rental car and hotels. For example, for car rentals in Expedia, they would like to offer customers a recommendation page of cars with different brands, prices, types, options, etc. What is a good recommendation for the customers so that they would have a good shopping and traveling experiences? First, it needs to be relevant to customers' choice behavior that can be learned from previous purchasing history or from marketing surveys; second, the recommendation cannot be too specified, which means that those rental cars in the recommendation page cannot be too similar in terms of their attributes; third, it cannot take too long to show the recommendations to the customers - an efficient algorithm is required. In this thesis, we will show our approach to assortment and price optimization problems.

The main contributions of my thesis is: 1) We formulate the assortment and price optimization problems in a choice-based way, which provides a good balance between relevance and variance of the products in an assortment; 2) We develop applicable recommendation algorithms that run in polynomial time and can be dynamically adapted; 3) Compared to the previous literature, our results are more advanced in terms of efficiency and applicability. Specifically, this thesis is consist of three essays in choice-based assortment and price optimization problems.

In the first essay, we study the joint constrained assortment and price optimization problem under the nested logit model with a no-purchase option in every choice stage. The cardinality or space constraints are imposed separately on the assortment of products that are offered in each nest. Specifically, cardinality constraint on a nest limits the total number of products that can be offered in that nest, and space constraint on a nest limits the total space consumption of products within that nest. The goal is to jointly determine the optimal assortment with optimal prices to maximize the expected profit per customer under cardinality or space constraints. By using our solution approach, this problem is simplified to find the fixed point of a single-variable unimodal expected profit function, where efficient searching algorithms can be applied. Furthermore, we provide a piecewise convex fixed point representation to facilitate computing. The optimal solution under cardinality constraints and a 2-approximate solution under space constraints can be obtained efficiently.

In the second essay, we study choice-based constrained assortment and price optimization problems under the multilevel nested logit model with a no-purchase option in every choice stage. For the constrained assortment optimization problem, each candidate product is associated with a fixed profit. The goal is to identify the optimal assortment satisfying cardinality or space constraints to maximize the expected profit per customer. Under cardinality constraints, there is a limitation imposed on nodes in the second lowest level. A polynomial-time algorithm with computational complexity $O(n\max\{m, k\})$ is provided to locate the optimal assortment for the $m$-level nested logit model with $n$ products, where $k$ is the maximum number of products within any node in level $m-1$. Under space constraints, every product consumes a certain amount of space and candidate assortments must satisfy the space limitation. However, the assortment optimization problem becomes NP-hard under space constraints, thus we develop an algorithm to find a 2-approximate solution in $O(mnk)$ operations. For the price optimization problem, we aim to find the profit-maximizing prices for all products. With product-differentiated price sensitivities, the expected profit function is no longer concave even under the two-level nested logit model, but we are able to reduce the multiproduct price optimization problem from a high dimensional optimization to the maximization of a unimodal function in single-dimensional searching space, in which the optimal prices can be found in a tractable manner.

In the third essay, we know that assortment and pricing decisions are of significant importance to firms and have huge influences on profit. How to jointly optimize over both assortment and prices draws increasing attention recently. However, in the most existing literature that considers joint optimization problem, they either impose strong restrictions on the choice structure or have strong assumptions on the price sensitivity parameters. Moreover, currently there is no flexible and comprehensive way to deal with the joint effect of assortment and pricing under multistage choice structure since the tangle between the assortment and prices makes the joint optimization problem less tractable. In this paper, we study the joint capacitated assortment and price optimization problem where the consumer choosing behavior is governed by the multistage tree logit model. Under the cardinality constraints, we develop an efficient algorithm that runs in polynomial time to find the optimal assortment with optimal prices. Under the space constraints, the assortment optimization problem is NP-hard even under tree logit model with only two levels. We can obtain a 2-approximate solution within the same time scale compared to the joint optimization problem under cardinality constraints. For a tree logit model with $N$ candidate products, both algorithms run in $O(GN\log G)$ where $G$ is the number of grid points for each node. The complexity can be further reduced to $O(GN\log K)$ under mild conditions, where $K$ is the maximum number of children nodes that a nonleaf node could have in the tree structure.