Sequential stochastic assignment under uncertainty: estimation and convergence

This paper generalizes the sequential stochastic assignment problem, involving the assignment of workers to sequentially arriving jobs, by introducing uncertainty into the job value distribution. Three estimators are presented that address various levels of uncertainty while simultaneously improving worker assignments. Specifically, each estimator is designed to utilize the unbiased and consistent properties of the sample mean to estimate the expected job value, while suppressing high variance effects during start-up. The key contribution is that closed-loop decision policies involving past job value observations can responsively adapt to changing environments and improve the overall reward resulting from pairing workers with jobs. Examples of applications that can benefit from these results include aviation passenger screening and the real estate market, as well as applications of the stochastic knapsack problem.