Approximation algorithms for dynamic pricing and assortment problems
The session started with Stephanus Jasin presenting their work on
Multi-product Dynamic Pricing with Limited Inventories under a Cascade Click Model. Click through rates modelling even though popular in CS literature has not been addressed in the OM literature, where customer choice models are dominant modeling strategies. He focuses on the Cascade Click Model as you can see in the picture. He models maximizing expected revenue subject to inventory constraint. The revenue to go is defined recursively. In a Theorem, they gives a characterization of optimal price, and showed an intuitive interpretation for the characterization. As is true for most revenue management problems, computing the optimal solution is intractable. They then give a tractable heuristic by making some structural assumptions.
The next talk was given by Heng Zhang on Assortment Optimization Under the Paired Combinatorial Logit Model. They study the PCL customer choice model model that had not been previously studied for Assortment Optimization. For assortment optimization, the customer choice models that have been widely studeied are the MNL, Nested Logit and MMNL. While MNL model is quite tractable, it is sometimes too simple to capture real world data. MMNL is a very general model under which the assortmentment optimization is NP hard. An intemediate model is the nested logit model in which products are divided into nests.
Though this model is relatively tractable and more general than MNL, they suffer because the choice of nests affect the optimal assortment. PCL model alleviates this drawback of the nested logit model. In PCL two products make a nest.
Each nest is characterized by a similarity score between the two products.
They showed assortment optimization under PCL as strongly NP hard (reduction from Max Cut). They also give a 2 approximation algorithm for the unconstrained version and 1/4 approximation algorithm for cardinality constrained version.
This was followed by Mika Sumida who spoke on An Approximation Algorithm For Network Revenue Management Under Nonstationary Arrivals.
In their model customer arrives, uses a set of resources, and by doing so, they consume capacity. Online decisions, arrivals stochatic but nonstationay in time. Some applications could be where customers request bundles of products like multile flight legs; or hotel rooms in consecutive nights on same room (each night is a product); or a modern on where a server farm rents cloud space for consecutive timeslots.
Their approximation algorithm gives a bound of 1/(1+L) where L is the maximum number of resources/products used by a customer. The intractable Markov Decision Process Dynamic Program is approximated by the basis function technique (one of the tools used in Approximate Dynamic Programming). They show the properties of the family of functions which if used as basis functions give the 1/(1+L) bound. However, to answer a query from the audience, the speaker did confirm that the choice of the basis function does have a significant impact on the solution empirically.
Jackie Baek presented her work on Bifurcating Constraints to Improve Approximation Ratios For Online (reusable) Resource Allocation. The work heavily relies on the 1/(1+L) results of Mika Sumida in the previous talk. The setting is almost similiar to the previous talk. What differs is that in this work they assume that the network constraints are structured, meaning that there is a pattern for resources/products that a customer requests for. The motivating example is vacation packages with add-on structure: let’s say there are 4 resources – hotel, city-tour, dinner and flight. City tour can only be claimed as an add-on to hotel and dinner can be only used as an add -on to the city-tour. The resulting network constraints can be bifurcated into two sets: one belonging to the hotel, city-tour and dinner (which is the structured set); and the other for flight (non structured). The structured constraints in the example are an example of matroid constraints and their work assumes the structured constraints are matroid.
Matroids can model more general add-on structure of trees. Prophet inequalities based approximation algorithms (work by Kleinberg and co-authors) are known to give 1/2 approximation. Their approximation algorithm for the bigger problem yields a an approximation ratio (1/2)*(1/(1+L’)) wher L’ is the maximum number of products/ resources requested by a customer among the products that belong to the non-structed set.
The proof technique has similarities with the previous work. The intutitive way to treat the variable x in the deterministic LP (that gives an upper bound) is to treat it as the probability that product i sold at time T
The optimal policy is of bid price policy type. Once component of of bid price uses x* from the deterministic LP in the same way as the previous talk. The second component of bid price is obtained from x* using prophet
Both components use the same x* which comes from the deterministic LP with the entire set of constraints.
They also work on extensions: modeling reusable products within the matroid set of constraints, and the other incorporating customer choice models.