Triply stochastic sequential assignment problem with the uncertainty in worker survival

The Sequential Stochastic Assignment Problem (SSAP), introduced by Derman et al. [1], lies in non-anticipatively assigning workers with given success rates to sequentially arriving jobs to maximize the total expected reward over all assignments; every job’s value follows a given distribution and remains unknown until the job presents itself to the workers. The problem’s variations have practical significance in multiple applications, such as in healthcare (organ allocation) and military operations (target assignment). This paper formulates and solves the Triply Stochastic Sequential Assignment Problem (3SSAP): a generalized SSAP, where (1) the job values, (2) the number of jobs yet to arrive, and (3) the future worker availability - all experience stochasticity. To this end, the paper relies on a decision analysis logic and explains what variations of 3SSAP can be solved with simple threshold policies and why. Closed-form 3SSAP optimal assignment policies are presented, accompanied by illustrative numerical examples of policy application.