TL;DR
This paper introduces a new framework for online sales of perishable items with uncertain lifespans, aiming to maximize social welfare. They develop a novel online pricing strategy that achieves a constant competitive ratio against an omniscient prophet, even with stochastic item horizons, a significant improvement over prior work.
What Problem Does This Paper Address?
The paper tackles the challenge of online selling when both buyers and the items themselves have uncertain arrival and departure times. Traditional online selling models often assume fixed supply or known item lifespans. However, modern "sharing economy" platforms (like ride-sharing or rental services) and perishable goods markets face a more complex reality: items (e.g., available cars, fresh produce) arrive and depart the system in an uncertain manner. The goal is to design an online pricing strategy that, without knowing future buyer valuations or item lifespans in advance, can still extract a significant portion of the maximum possible social welfare (what a "prophet" who knows everything could achieve). This is framed as a prophet inequality problem, seeking algorithms that perform close to optimal in hindsight.
Methods
The authors introduce a "balancing policy" as the core idea: the rate at which buyers are accepted should be balanced against the rate at which items naturally depart due to their uncertain horizons. To implement this, they develop a novel technique of "simulating departures." Instead of precisely modeling the complex departure process, they probabilistically simulate item departures at future times to inform their pricing decisions. This allows them to construct a feasible online policy that approximates the prophet's welfare.
For the specific case of a single item with a "monotone-hazard-rate" (MHR) horizon distribution, they derive a tight result for a fixed pricing scheme. For multiple items, they break down the problem into stages and use different algorithms for "long" and "short" stages, as well as a final stage, combining them to achieve the overall result.
Datasets
Not discussed in the paper.
Key Insights and Ideas
- Balancing Act: The core insight is that in the face of uncertain supply (item departures), a successful online strategy must actively balance buyer acceptance with item departure rates, not just focus on maximizing immediate matches.
- Simulating Uncertainty: Directly modeling complex stochastic processes can be intractable. The paper's novel "simulating departures" technique offers a way to handle this uncertainty by probabilistically mimicking future events, leading to a practical algorithm.
- MHR is Key: The "monotone-hazard-rate" (MHR) condition on item horizons is crucial. Without it, even for a single item, achieving a constant competitive ratio is impossible. This highlights the importance of certain structural properties of supply uncertainty.
- Surprising Optimality: For the single-item MHR case, a simple fixed pricing scheme achieves a tight competitive ratio of $2 - 1/\mu$ (where $\mu$ is the mean horizon). This is surprising because fixed pricing is often suboptimal in related problems.
- Lower Bounds Matter: The paper establishes non-trivial lower bounds, showing that even with MHR horizons, a constant competitive ratio is not trivial for multiple items, and that without MHR, the gap between an online algorithm and the prophet can be arbitrarily large.
Key Results
- Constant Approximation for Multiple Items: The paper presents a constant-competitive online policy for social welfare maximization for any number of items with independent MHR horizon distributions and i.i.d. buyer valuations.
- Tight Single-Item Result: For a single item with an MHR horizon distribution with mean $\mu$, a fixed pricing scheme achieves a competitive ratio of $2 - 1/\mu$, which is shown to be tight for geometric horizons.
- Lower Bounds:
- For i.i.d. geometric horizons, a lower bound of 1.57 is shown for any dynamic pricing scheme, improving to 2 in the limit of many items.
- No fixed pricing scheme can be $o(\log \log m)$-competitive for $m$ items.
- Without the MHR assumption, the competitive ratio can be unbounded, even for a single item.
Limitations and Future Work
- Approximation Factor Gap: The constant factor in the main multi-item result (53) is not tight and does not match the lower bound (2). Closing this gap is identified as an important future direction.
- Generalizations: The authors suggest extending the work to more general prophet inequality settings (e.g., those in reference [10]) and to cases where items arrive and depart in a more general stochastic fashion, not just limited by their horizons.
Summary updated