AI Adapts to Unpredictable Inventory Changes

Online platforms from retail to ride-sharing face a constant : managing inventory that can change unpredictably. Products might be rented out and returned later, or new stock might arrive without warning. Traditional algorithms for optimizing sales assortments assume stable inventory, but real-world supply is often volatile. A new study introduces an algorithm that adapts to these shocks, proving that simple balancing strategies can remain effective even when inventory levels fluctuate in complex ways.

The researchers developed the Batched Inventory Balancing (BIB) algorithm, which groups inventory units into batches based on when they enter the system, such as through initial stock or unexpected replenishments. This approach allows the algorithm to penalize prices based on batch availability, encouraging balanced consumption across products. The key finding is that BIB achieves a competitive ratio—a measure of performance against an ideal offline benchmark—that asymptotically approaches 1 - 1/e, or about 63%, as initial inventory grows large. This matches the optimal guarantee previously known for settings without inventory shocks, demonstrating robustness in more dynamic environments.

Ology involves treating different units of the same product separately, assigning them to batches that become 'ready' for use once they reach a threshold size. At each time step, when a consumer arrives, the algorithm adjusts product prices using a concave penalty function applied to the normalized inventory levels of ready batches. It then selects an assortment by querying an offline solver with these penalized prices. If a product is chosen, a unit is allocated from the batch with the highest normalized inventory level. This process handles both endogenous shocks, where units return after a fixed usage duration, and exogenous shocks, where new units are added unpredictably.

Show that BIB's competitive ratio is characterized by a function Γ(Ψ, γ), which depends on the penalty function Ψ and batch-size threshold γ. For the exponential penalty function and a batch size scaled with the square root of initial inventory, the ratio converges to 1 - 1/e. The analysis uses a novel randomized primal-dual framework, reducing the problem to a combinatorial interval assignment problem to address non-monotonic inventory changes. This ensures the algorithm's revenue is at least a Γ fraction of the clairvoyant optimum, with the bound matching known for shock-free cases.

Are significant for practical applications like cloud computing, rental marketplaces, and volunteer platforms, where inventory can vary due to returns or new additions. BIB offers a simple, transparent that doesn't require tracking full restocking states, making it appealing for real-world implementation. It maintains performance guarantees even under adversarial conditions, providing a reliable tool for revenue management in dynamic environments.

Limitations include the assumption of fixed usage durations for endogenous shocks and non-negative exogenous shocks, though the paper notes extensions to stochastic durations are possible. The analysis focuses on large initial inventories, and performance in small-inventory regimes may differ. Future work could explore negative shocks, heterogeneous return times, or incorporating costs, as outlined in the open problems section.