skip to main content
Explore Scholarly Publications and Datasets in the NSF-PAR

  • NSF Public Access
  • Search Results
  • Accepted Manuscript: Revenue-Utility Tradeoff in Assortment Optimization Under the Multinomial Logit Model with Totally Unimodular Constraints
Title: Revenue-Utility Tradeoff in Assortment Optimization Under the Multinomial Logit Model with Totally Unimodular Constraints
We examine the revenue–utility assortment optimization problem with the goal of finding an assortment that maximizes a linear combination of the expected revenue of the firm and the expected utility of the customer. This criterion captures the trade-off between the firm-centric objective of maximizing the expected revenue and the customer-centric objective of maximizing the expected utility. The customers choose according to the multinomial logit model, and there is a constraint on the offered assortments characterized by a totally unimodular matrix. We show that we can solve the revenue–utility assortment optimization problem by finding the assortment that maximizes only the expected revenue after adjusting the revenue of each product by the same constant. Finding the appropriate revenue adjustment requires solving a nonconvex optimization problem. We give a parametric linear program to generate a collection of candidate assortments that is guaranteed to include an optimal solution to the revenue–utility assortment optimization problem. This collection of candidate assortments also allows us to construct an efficient frontier that shows the optimal expected revenue–utility pairs as we vary the weights in the objective function. Moreover, we develop an approximation scheme that limits the number of candidate assortments while ensuring a prespecified solution quality. Finally, we more » discuss practical assortment optimization problems that involve totally unimodular constraints. In our computational experiments, we demonstrate that we can obtain significant improvements in the expected utility without incurring a significant loss in the expected revenue. This paper was accepted by Omar Besbes, revenue management and market analytics. « less
Authors:
; ; ; ;
Award ID(s):
1825406
Publication Date:
NSF-PAR ID:
10293642
Journal Name:
Management Science
Volume:
67
Issue:
5
Page Range or eLocation-ID:
2845 to 2869
ISSN:
0025-1909
Sponsoring Org:
National Science Foundation
More Like this
  1. ; ; ; ; ; ; ( , Operations Research)
    We develop a variant of the multinomial logit model with impatient customers and study assortment optimization and pricing problems under this choice model. In our choice model, a customer incrementally views the assortment of available products in multiple stages. The patience level of a customer determines the maximum number of stages in which the customer is willing to view the assortments of products. In each stage, if the product with the largest utility provides larger utility than a minimum acceptable utility, which we refer to as the utility of the outside option, then the customer purchases that product right away. Otherwise, the customer views the assortment of products in the next stage as long as the customer’s patience level allows the customer to do so. Under the assumption that the utilities have the Gumbel distribution and are independent, we give a closed-form expression for the choice probabilities. For the assortment-optimization problem, we develop a polynomial-time algorithm to find the revenue-maximizing sequence of assortments to offer. For the pricing problem, we show that, if the sequence of offered assortments is fixed, then we can solve a convex program to find the revenue-maximizing prices, with which the decision variables are the probabilitiesmore »that a customer reaches different stages. We build on this result to give a 0.878-approximation algorithm when both the sequence of assortments and the prices are decision variables. We consider the assortment-optimization problem when each product occupies some space and there is a constraint on the total space consumption of the offered products. We give a fully polynomial-time approximation scheme for this constrained problem. We use a data set from Expedia to demonstrate that incorporating patience levels, as in our model, can improve purchase predictions. We also check the practical performance of our approximation schemes in terms of both the quality of solutions and the computation times.« less
  2. ; ; ( , Mathematics of Operations Research)
    We study the dynamic assortment planning problem, where for each arriving customer, the seller offers an assortment of substitutable products and the customer makes the purchase among offered products according to an uncapacitated multinomial logit (MNL) model. Because all the utility parameters of the MNL model are unknown, the seller needs to simultaneously learn customers’ choice behavior and make dynamic decisions on assortments based on the current knowledge. The goal of the seller is to maximize the expected revenue, or, equivalently, to minimize the expected regret. Although dynamic assortment planning problem has received an increasing attention in revenue management, most existing policies require the estimation of mean utility for each product and the final regret usually involves the number of products [Formula: see text]. The optimal regret of the dynamic assortment planning problem under the most basic and popular choice model—the MNL model—is still open. By carefully analyzing a revenue potential function, we develop a trisection-based policy combined with adaptive confidence bound construction, which achieves an item-independent regret bound of [Formula: see text], where [Formula: see text] is the length of selling horizon. We further establish the matching lower bound result to show the optimality of our policy. There aremore »two major advantages of the proposed policy. First, the regret of all our policies has no dependence on [Formula: see text]. Second, our policies are almost assumption-free: there is no assumption on mean utility nor any “separability” condition on the expected revenues for different assortments. We also extend our trisection search algorithm to capacitated MNL models and obtain the optimal regret [Formula: see text] (up to logrithmic factors) without any assumption on the mean utility parameters of items.« less
  3. ( , ProQuest Dissertations & Theses A&I)
    In mechanism design, the firm has an advantage over its customers in its knowledge of the state of the system, which can affect the utilities of all players. This poses the question: how can the firm utilize that information (and not additional financial incentives) to persuade customers to take actions that lead to higher revenue (or other firm utility)? When the firm is constrained to "cheap talk," and cannot credibly commit to a manner of signaling, the firm cannot change customer behavior in a meaningful way. Instead, we allow firm to commit to how they will signal in advance. Customers can then trust the signals they receive and act on their realization. This thesis contains the work of three papers, each of which applies information design to service systems and online markets. We begin by examining how a firm could signal a queue's length to arriving, impatient customers in a service system. We show that the choice of an optimal signaling mechanism can be written as a infinite linear program and then show an intuitive form for its optimal solution. We show that with the optimal fixed price and optimal signaling, a firm can generate the same revenue as itmore »could with an observable queue and length-dependent variable prices. Next, we study demand and inventory signaling in online markets: customers make strategic purchasing decisions, knowing the price will decrease if an item does not sell out. The firm aims to convince customers to buy now at a higher price. We show that the optimal signaling mechanism is public, and sends all customers the same information. Finally, we consider customers whose ex ante utility is not simply their expected ex post utility, but instead a function of its distribution. We bound the number of signals needed for the firm to generate their optimal utility and provide a convex program reduction of the firm's problem.« less
  4. ; ; ( , Management science)
    We consider dynamic assortment problems with reusable products, in which each arriving customer chooses a product within an offered assortment, uses the product for a random duration of time, and returns the product back to the firm to be used by other customers. The goal is to find a policy for deciding on the assortment to offer to each customer so that the total expected revenue over a finite selling horizon is maximized. The dynamic-programming formulation of this problem requires a high-dimensional state variable that keeps track of the on-hand product inventories, as well as the products that are currently in use. We present a tractable approach to compute a policy that is guaranteed to obtain at least 50% of the optimal total expected revenue. This policy is based on constructing linear approximations to the optimal value functions. When the usage duration is infinite or follows a negative binomial distribution, we also show how to efficiently perform rollout on a simple static policy. Performing rollout corresponds to using separable and nonlinear value function approximations. The resulting policy is also guaranteed to obtain at least 50% of the optimal total expected revenue. The special case of our model with infinite usagemore »durations captures the case where the customers purchase the products outright without returning them at all. Under infinite usage durations, we give a variant of our rollout approach whose total expected revenue differs from the optimal by a factor that approaches 1 with rate cubic-root of Cmin, where Cmin is the smallest inventory of a product. We provide computational experiments based on simulated data for dynamic assortment management, as well as real parking transaction data for the city of Seattle. Our computational experiments demonstrate that the practical performance of our policies is substantially better than their performance guarantees and that performing rollout yields noticeable improvements.« less
  5. ; ; ( , Production and Operations Management)

    Customer cancellations and no‐shows have an important impact on the performance of an airline's revenue management system. In this study, we study airline network revenue management problems with customer cancellations and no‐shows, considering two types of demand models: independent‐demand and choice‐based‐demand models. In independent‐demand models, the booking request rates for different products are independent of the assortment of products offered by the airline (exogenous), whereas in choice‐based‐demand models they depend on the airline's assortment (endogenous). The stochastic problems of optimizing the booking policies for the two demand models are not tractable because of the high‐dimensional state space. Therefore, for each model, we use the corresponding deterministic, continuous‐time, and continuous‐state model, known as the fluid model. A booking policy based on the fluid solution can be implemented for the original stochastic, discrete model. This fluid policy is shown to be asymptotically optimal when the arrival rates become high and the seat capacities become large. In the independent‐demand setting, an optimal fluid solution can be computed by solving a convex optimization problem for which efficient algorithms exist, whereas for some choice‐based‐demand models, the fluid control problems are known to be intractable. We also develop mixed fluid policies for the independent‐demand setting, takingmore »advantage of the real‐time booking state, to improve the performance over the fluid policy. In a factorial experiment of 20 small‐sized single‐leg problems, the revenue loss under one of the mixed fluid policies is demonstrated to be less than 1% of the optimal value for all problems.

    « less
  • Citation Formats
  • MLA
  • APA
  • Chicago
  • BibTeX
  • Save / Share this Record
  • Send to Email