Approximation Methods for Pricing Problems Under the Nested Logit Model with Price Bounds

We consider two variants of a pricing problem under the nested logit model. In the first variant, the set of products offered to customers is fixed, and we want to determine the prices of the products. In the second variant, we jointly determine the set of offered products and their corresponding prices. In both variants, the price of each product has to be chosen within given upper and lower bounds specific to the product, each customer chooses among the offered products according to the nested logit model, and the objective is to maximize the expected revenue from each customer. We give approximation methods for both variants. For any ρ > 0, our approximation methods obtain a solution with an expected revenue deviating from the optimal expected revenue by no more than a factor of 1 + ρ. To obtain such a solution, our approximation methods solve a linear program whose size grows at rate 1/ρ. In addition to our approximation methods, we develop a linear program that we can use to obtain an upper bound on the optimal expected revenue. In our computational experiments, we compare the expected revenues from the solutions obtained by our approximation methods with the upper bounds on the optimal expected revenues and show that we can obtain high-quality solutions quite fast.