2019 Theses Doctoral
Dynamic Pricing and Demand Shaping: Theory and Applications in Online Assortments, Ride Sharing and Smart Grids
This dissertation consists of three papers in revenue management: on-line assortment optimization with reusable resources, spatial distribution of surge price under incentive compatible assignment for drivers and optimal price rebates for demand response under power flow constraints.
In Chapter 2, we study an on-line assortment optimization problem of substitutable products with fixed reusable capacities. At any time, a potential user with her preference model (possibly adversarially chosen) arrives to the selling platform and the platform offers a subset of products from the available set of products to the user. The user selects a product with probability given by her preference model, uses it for a random duration, which is distributed according to a distribution that only depends on the product selected, and generates revenue to the seller. The revenue contribution depends on the product selected and the actual usage time of this user. The goal of the seller is to find a policy for determining the assortment offered to each arrival to maximize the expected cumulative revenue over a time horizon.
We find that a simple myopic policy offering the available assortment that maximizes the expected revenue from a single user at her arrival time provides a good approximation for the problem. In particular, we show that the myopic policy is $1/2$-competitive, i.e., the expected cumulative revenue of the myopic policy is at least $1/2$ times the expected cumulative revenue of an optimal clairvoyant policy that has full information about the adversarially chosen user sequence, including their preference models and arrival epochs. The proof is based on partitioning the expected revenue of optimal clairvoyant policy into two parts and a coupling argument that allows us to bound the two parts in terms of the expected revenue of the myopic policy.
In Chapter 3, we study the surge pricing problem on a ride sharing platform when there is a demand shock to the traffic network. The goal of the platform is to maximize the revenue by setting the prices over the network and the assignments between drivers and riders. In particular, we model the city as a continuous two dimensional network with exogenous arrivals of baseline riders, available drivers and demand shocks. We consider the demand shock only exists in a short time scale, so the rider chooses to request the ride or not depending on their willingness to pay and the price quoted to them, and the driver accepts any price to provide service. Since drivers can see the price distribution on driver app, they only accept the assignment from the locations that are incentive compatible for them. Thus, the price change at one location may affect the operations over the network and the platform must consider the incentive of drivers when assigning them.
We develop a model for this surge pricing problem and show the structural properties of an optimal solution. Once the prices at the location with demand shock is determined, we can determine the optimal prices on other part of the network. Then, the optimal assignments between riders and drivers can be determined analytically. The surge pricing problem reduces to one that only depends on the price at the location with demand shock. We then extend our model by including strategic behavior of riders, using throughput as objective, dealing with multiple demand shocks, un-constraining the price and considering movement time. We also conduct numerical experiments to study the properties of the model which can not be explored analytically.
In Chapter 4, we study the demand response problem of computing price rebates to offer to the customers to reduce the consumption in the presence of power flow constraints and transmission losses on the distribution grid. In particular, we employ alternating current power flow model for the power flow constraints with transmission loss. However, the demand response problem with alternating current power flow constraints is known as a non-convex problem, which is in-tractable to solve. To overcome this, we apply a semi-definite relaxation of alternating current power flow model to obtain a convex approximation for the problem. At the same time, to handle the uncertainty in the power reduction of customers, we use sample average to approach the expected cost and linear injection approximation to estimate the impact of uncertainty in the power reduction. Based on these relaxations and approximations, we propose an efficient iterative heuristic to solve the near-optimal offer price under alternating current power flow constraints and transmission losses. We conduct a substantial amount of numerical tests on our heuristic and compare its performance with other popular models. The result shows that our iterative heuristic leads to a significant reduction in the rebates that one needs to offer to shed a certain demand than the solution which does not consider full transmission loss in its model.
- Wang_columbia_0054D_15134.pdf application/pdf 514 KB Download File
More About This Work
- Academic Units
- Industrial Engineering and Operations Research
- Thesis Advisors
- Goyal, Vineet
- Ph.D., Columbia University
- Published Here
- March 29, 2019