Overview
This research investigates a continuous-time, K-unit online resource allocation problem characterized by nonhomogeneous Poisson arrivals and time-varying valuation distributions. The study focuses on evaluating stock-based threshold policies, a simplified class where thresholds depend solely on the number of units remaining, rather than the more complex dynamic policies that consider both remaining inventory and time in the horizon. These policies are assessed against a multi-unit prophet benchmark, which retrospectively selects the best K realized values. The primary contribution is a novel competitive-analysis framework specifically designed for continuous-time stock-based thresholds.
Research Context
The core problem addresses online resource allocation under specific stochastic conditions: nonhomogeneous Poisson arrival processes and valuation distributions that change over time. The optimal policy for such problems is generally intricate, requiring consideration of both the available inventory and the remaining duration of the allocation horizon. The research positions stock-based threshold policies as a more practical alternative due to their inherent simplicity, as their decision logic is limited to the current stock level without direct reliance on calendar time.
Approach
The research establishes a new competitive-analysis framework for continuous-time stock-based thresholds. The initial step involves reformulating the problem through a type-covering dual. Analyzing this dual presents two primary challenges: it is infinite-dimensional, and it is non-convex. Furthermore, the adversarial components—time-varying arrival and valuation processes—can be chosen by an adversary, and the policy's performance is nonlinearly dependent on the stochastic trajectory of the inventory.
To address these complexities, the continuous-time adversarial problem is reduced to a Poisson optimization problem, designated as $PoisOPTRe_K$. This reduction facilitates the proof of sharp structural properties concerning the worst-case solutions. Specifically, the analysis reveals that adversarial arrivals exhibit cutoff and late-filling structures. These structures enable an exact four-parameter formulation for scenarios involving two thresholds, and a finite nested-interval representation when considering general thresholds. These analytical reductions render the performance guarantees directly computable.
Findings
- The competitive analysis framework is applied to stock-based threshold policies in continuous time.
- The problem is reformulated through a type-covering dual, which is identified as infinite-dimensional and non-convex.
- The continuous-time adversarial problem is reduced to a Poisson optimization problem, $PoisOPTRe_K$.
- Worst-case solutions for $PoisOPTRe_K$ exhibit adversarial arrival patterns with cutoff and late-filling structures.
- For two thresholds, these structures yield an exact four-parameter formulation.
- For general thresholds, a finite nested-interval representation is achieved.
- These reductions allow for direct computation of policy guarantees.
- For $K=2$, employing two thresholds results in a competitive ratio of $0.6269$.
- For $K=3$, utilizing three thresholds yields a competitive ratio of $0.6816$.
- These results indicate that simple stock-based thresholds maintain strong prophet-inequality guarantees even though they do not incorporate calendar time into their decision logic.