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.

Working Paper

2020

Citations

Bray, Robert. 2020. Logarithmic Regret in Multisecretary and Online Linear Programming Problems with Continuous Valuations.

KELLOGG INSIGHT

Find articles, podcast episodes, and videos that spark ideas in lifelong learners, and inspire those looking to advance in their careers.

COURSE CATALOG

Review Courses & Schedules

Access information about specific courses and their schedules by viewing the interactive course scheduler tool.