Doubly Stochastic Sequential Assignment Problem

This article introduces the Doubly Stochastic Sequential Assignment Problem (DSSAP), an extension of the Sequential Stochastic Assignment Problem (SSAP), where sequentially arriving tasks are assigned to workers with random success rates. A given number of tasks arrive sequentially, each with a random value coming from a known distribution. On a task arrival, it must be assigned to one of the available workers, each with a random success rate coming from a known distribution. Optimal assignment policies are proposed for DSSAP under various assumptions on the random success rates. The optimal assignment algorithm for the general case of DSSAP, where workers have distinct success rate distribution, has an exponential running time. An approximation algorithm that achieves a fraction of the maximum total expected reward in a polynomial time is proposed. The results are illustrated by several numerical experiments.