Farbod Ekbatani

We study a dynamic pricing problem in which a seller with limited inventory must sequentially price a perishable product for arriving customers with heterogeneous valuations. The key difficulty lies in balancing immediate sales against future opportunities under capacity constraints and stochastic customer valuations. We propose a simple, interpretable, and asymptotically optimal dynamic pricing algorithm, called Dynamic Run-Out Pricing (DROP), that adjusts prices in real time based on current inventory and anticipated future demand. Under the assumption that customers' valuations follow bounded or exponential distributions, our theoretical results show that DROP's expected revenue converges to the optimal revenue as market size grows. Unlike traditional notions of near-optimality, where the ratio of the algorithm's revenue to the optimal revenue converges to 1, we show that the absolute difference between the two revenues converges to 0 as the market size increases, underscoring the algorithm's effectiveness. Furthermore, we extend our analysis to heavy-tailed valuation distributions, specifically the Pareto distribution, where standard run-out heuristics severely underprice inventory by ignoring the value of waiting for extreme valuations. To correct this, we introduce the Tail-Aware DROP (TA-DROP) heuristic, which intentionally inflates prices to protect inventory, and we prove that it restores asymptotic optimality with a strict polynomial convergence rate. We complement the theoretical results with numerical experiments to demonstrate the practical applicability and competitive performance of these algorithms across a range of dynamic pricing scenarios.

Problem definition: Intense competition in the travel industry has increasingly shifted focus toward ancillary services, particularly seat upgrades in airlines and room upgrades in hotels. In response to this trend, several innovative solutions have emerged, among which Nor1’s eStandby Upgrade program stands out by offering discounted, availability-based room upgrades. Revenue management for these upgrades is complex because customers may request multiple upgrades, whereas hotels allocate them based on availability and typically grant at most one upgrade per customer. Methodology/results: Partnering with Oracle, which acquired Nor1, we develop a state-of-the-art framework for prediction, pricing, and allocation to maximize total revenue from eStandby upgrades. We first model customer decision making using a novel copula-based multivariate choice model that captures complex dependencies among multiple decisions made by the same customer. Next, we develop efficient pricing and allocation algorithms to address the challenges associated with offering multiple availability-based upgrades and tracking customer requests. Managerial implications: Validated with real-world data and data-driven numerical experiments, our choice model for upgrade requests and algorithms for pricing and allocation demonstrate significant revenue potential by capturing dependencies across customers’ multiple decisions. History: This paper has been accepted as part of the 2025 Manufacturing & Service Operations Management Practice-Based Research Competition. Funding: This work was supported by Oracle Research [Grant CR 4223]. Supplemental Material: The online appendix is available at https://doi.org/10.1287/msom.2025.0328 .

Ride-hailing platforms increasingly rely on non-exclusive notifications—broadcasting a single request to multiple drivers simultaneously—to mitigate inefficiencies caused by uncertain driver acceptance. In this paper, the first in a two-part collaboration with Lyft, we formally model the Notification Set Selection Problem for a single decision cycle, where the platform must determines the optimal subset of drivers to notify for each incoming ride request. We analyze this combinatorial optimization problem under two contention-resolution protocols: First Acceptance (FA), which prioritizes speed by assigning the ride to the first responder, and Best Acceptance (BA), which prioritizes match quality by selecting the highest-valued accepting driver. We show that welfare maximization under both mechanisms is strongly NP-hard, ruling out a Fully Polynomial Time Approximation Scheme (FPTAS). Despite this, we derive several positive algorithmic results. For FA, we present a Polynomial Time Approximation Scheme (PTAS) for the single-rider case and a constant-factor approximation (factor 4) for the general matching setting. We highlight that the FA valuation function can be viewed as a novel discrete choice model with theoretical properties of independent interest. For BA, we prove that the objective is monotone and submodular, admitting a standard (1 - 1/e)-approximation. Moreover, using a polynomial-time demand oracle that we design for this problem, we show it is possible to surpass the (1 - 1/e) barrier. Finally, in the special case of homogeneous acceptance probabilities, we show that the BA problem can be solved exactly in polynomial time via a linear programming formulation. We validate the empirical performance of our algorithms through numerical experiments on synthetic data and on instances calibrated using real ride-sharing data from Lyft.

Ride-hailing platforms increasingly face uncertain driver acceptance, which makes traditional one-to-one exclusive dispatch (ED) less efficient: rejections and timeouts force sequential retries and lengthen rider wait times, which in turn creates friction in the marketplace. Non-exclusive dispatch (NED) mitigates this friction by broadcasting a request to multiple drivers in parallel. While NED can reduce latency, it introduces new design challenges—most notably, how to choose notification sets and how to resolve driver contention (when multiple drivers accept the same ride). In this paper—the second in a two-part collaboration with Lyft—we develop a theoretically grounded framework to evaluate the long-run performance and marketplace effects of transitioning from ED to NED. We bridge theory and practice by combining (i) an optimization model that formulates NED as a constrained welfare maximization problem with (ii) large-scale discrete-event simulations on proprietary Lyft traces and (iii) a stylized macroscopic equilibrium model. Across simulation and equilibrium analysis, we find that NED improves key fulfillment metrics relative to ED: it reduces match time (and hence rider reneging) while increasing both the number and the average quality of completed matches. We also quantify the speed--quality trade-off between two common contention rules, First-Accept and Best-Accept: First-Accept maximizes speed and throughput, whereas Best-Accept is required to maximize per-match quality. Finally, we show that slightly conservative notification heuristics can improve long-run efficiency by avoiding excessive locking of high-value drivers and preserving future availability.

Most of the literature on online algorithms and sequential decision-making focuses on settings with “irrevocable decisions” where the algorithm’s decision upon arrival of the new input is set in stone and can never change in the future. One canonical example is the classic prophet inequality problem, where realizations of a sequence of independent random variables X₁, X₂,… with known distributions are drawn one by one and a decision maker decides when to stop and accept the arriving random variable, with the goal of maximizing the expected value of their pick. We consider “prophet inequalities with recourse” in the linear buyback cost setting, where after accepting a variable X_i, we can still discard X_i later and accept another variable X_j, at a buyback cost of f × X_i. The goal is to maximize the expected net reward, which is the value of the final accepted variable minus the total buyback cost. Our first main result is an optimal prophet inequality in the regime of f ≥ 1, where we prove that we can achieve an expected reward 1+f/1+2f times the expected offline optimum. The problem is still open for 0<ff and provide almost matching upper and lower bounds that show a factor of 1−Θ(flog(1/f)). Our results are obtained by two fundamentally different approaches: One is inspired by various proofs of the classical prophet inequality, while the second is based on combinatorial optimization techniques involving LP duality, flows, and cuts.

Motivated by applications in cloud computing spot markets and selling banner ads on popular websites, we study the online resource allocation problem with costly buyback. To model this problem, we consider the classic edge-weighted fractional online matching problem with a tweak, where the decision maker can recall (i.e., buyback) any fraction of an offline resource that is pre-allocated to an earlier online vertex; however, by doing so not only the decision maker loses the previously allocated reward (which equates the edge-weight), it also has to pay a non-negative constant factor f of this edge-weight as an extra penalty. Parameterizing the problem by the buyback factor f, our main result is obtaining optimal competitive algorithms for all possible values of f through a novel primal-dual family of algorithms. We establish the optimality of our results by obtaining separate lower-bounds for each of small and large buyback factor regimes, and showing how our primal-dual algorithm exactly matches this lower-bound by appropriately tuning a parameter as a function of f. The optimal competitive ratio Γ_gen(f) and the optimal competitive ratio Γ_det-int(f) of deterministic integral algorithms are as follows, [EQUATION] where W₋₁ : [⁻¹/e, 0) → (−∞, −1] is the non-principal branch of the Lambert W function.

Motivated by applications in cloud computing spot markets and selling banner ads on popular websites, we study the online resource allocation problem with "costly buyback". To model this problem, we consider the classic edge-weighted fractional online matching problem with a tweak, where the decision maker can recall (i.e., buyback) any fraction of an offline resource that is pre-allocated to an earlier online vertex; however, by doing so not only the decision maker loses the previously allocated reward (which equates the edge-weight), it also has to pay a non-negative constant factor f of this edge-weight as an extra penalty. Parameterizing the problem by the buyback factor f, our main result is obtaining optimal competitive algorithms for all possible values of f through a novel primal-dual family of algorithms. We establish the optimality of our results by obtaining separate lower-bounds for each of small and large buyback factor regimes, and showing how our primal-dual algorithm exactly matches this lower-bound by appropriately tuning a parameter as a function of f. We further study lower and upper bounds on the competitive ratio in variants of this model, e.g., single-resource with different demand sizes, or matching with deterministic integral allocations. We show how algorithms in the our family of primal-dual algorithms can obtain the exact optimal competitive ratio in all of these variants --- which in turn demonstrates the power of our algorithmic framework for online resource allocations with costly buyback.