Risk-Sensitive Online Selection with Bounded Adaptivity
For researchers and practitioners in online decision-making, this work provides a principled method to control tail risk in randomized online algorithms under adaptivity constraints, though the results are specific to the adversarial selection setting.
This paper addresses tail-risk sensitivity and bounded adaptivity in online adversarial selection, proposing a correlated posted-price mechanism that uses a single random seed to coordinate pricing decisions. The mechanism improves lower-tail performance under CVaR objectives while respecting adaptivity constraints, and experiments on real airline pricing data demonstrate its empirical impact on welfare concentration.
Designing randomized online algorithms that perform reliably not only in expectation but also under unfavorable realizations of randomness is a fundamental challenge in online decision-making. In this paper, we study this challenge in online adversarial selection, where a decision maker allocates $k$ units of a resource to sequentially arriving buyers through posted prices. We focus on two intertwined considerations that are often overlooked simultaneously: tail-risk sensitivity and bounded adaptivity, where tail risk is measured using conditional value-at-risk (CVaR) and bounded adaptivity limits the number of allowable policy updates over time. Our main contribution is a correlated posted-price mechanism that uses a single random seed to coordinate pricing decisions across time. This correlation induces a monotonic ordering of pricing profiles across sample paths, improving lower-tail performance while respecting the adaptivity constraint. More broadly, our results highlight correlation as a mechanism for controlling tail risk in randomized online algorithms. Using this framework, we derive competitive guarantees for several regimes of the problem under both static and dynamic pricing. Our analysis develops a risk-sensitive randomized online primal-dual framework tailored to CVaR objectives and reveals a systematic trade-off between allowable adaptivity, risk sensitivity, and competitive performance. Experiments on real airline pricing data further illustrate the empirical impact of correlated pricing on welfare concentration and tail behavior.