Take Action
Research Details
Logarithmic Regret in Multisecretary and Online Linear Programming Problems with Continuous Valuations
Abstract
I study a general revenue management problem in which $ n $ customers arrive sequentially over $ n $ periods, and you must dynamically decide which to satisfy. Satisfying the period-$ t $ customer yields utility $ u_{t} \in \mathbbm{R}_{+} $ and decreases your inventory holdings by $ A_{t} \in \mathbbm{R}_{+}^{M} $. The customer vectors, $ (u_{t}, A_{t}')' $, are \iid, with $ u_{t} $ drawn from a finite-mean continuous distribution and $ A_{t} $ drawn from a bounded discrete or continuous distribution. I study this system's \emph{regret}, which is the additional utility you could get if you didn't have to make decisions on the fly. I show that if your initial inventory endowment scales linearly with $ n $ then your expected regret is $ \Theta(\log(n)) $ as $ n \rightarrow \infty $. I provide a simple policy that achieves this $ \Theta(\log(n)) $ regret rate. Finally, I extend this result to \cites{Arlotto2019} multisecretary problem with uniformly distributed secretary valuations.
Type
Working Paper
Author(s)
Date Published
2020
Citations
Bray, Robert. 2020. Logarithmic Regret in Multisecretary and Online Linear Programming Problems with Continuous Valuations.
LINK