We study a general model of reusable resource allocation problems. Customers of different types arrive according to a stationary stochastic process. The firm's goal is to maximize multiple kinds of rewards generated by customers. We develop an online policy for deciding on actions to take without knowing the distribution of customer types and show that when the usage duration is small compared with the length of the planning horizon, our policy achieves a near optimal performance.

We study the multisecretary problem with a capacity to hire up to B out of T candidates with their values drawn i.i.d from a distribution F on [0,1]. We investigate the achievable regret performance where our benchmark is the offline optimal policy. We establish the insufficiency of the common certainty equivalent heuristic for distributions with many types and gaps. We devise a new algorithmic principle called "Conservatism wrt Gaps" and use this to derive near-optimal regret scaling.

Prophet inequalities are a useful tool for designing online allocation procedures and comparing their performance to the optimal offline allocation. In this paper we derive the best-known guarantee for $k$-unit prophet inequalities for all $k>1$. We also provide a tight resolution to the related Magician's problem. Finally, we improve the guarantee from 0.2 to 0.319 for online knapsack, and from 0.321 to 0.3557 for unit-density online knapsack.