Logarithmic Regret in Multisecretary and Online Linear Programming
  Problems with Continuous Valuations
  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
\mathbb{R}_{+} $ and decreases your inventory holdings by $ A_{t} \in
\mathbb{R}_{+}^{M} $. The customer vectors, $ (u_{t}, A_{t}')' $, are i.i.d.,
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
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 Arlotto and
Gurich's (2019) multisecretary problem with uniformly distributed secretary
valuations.
