Sequential Stochastic Assignment with Unknown Worker Quality

The Sequential Stochastic Assignment Problem (SSAP), lies in anticipatively assigning workers with given success rates to sequentially-arriving tasks in order to maximize the total expected reward; every task value follows a given distribution and remains unknown until the task presents itself to the workers. This work studies a real-world extension of this problem in which the quality of the workers is not known prior to making assignments. Such a problem setting has practical significance in multiple real-world instances owing to the fact that the true success rate of a worker is seldom easily obtained. We use techniques for inferring the ranking of the workers and provide a policy that dictates the assignment of workers to the incoming tasks. The inference techniques in question are borrowed from existing work in the literature, one of which uses a random-walk based approach to ranking-inference and another that uses an ℓ1 - based heuristic to infer ranking information. We use the idea behind the random walk based inference to incorporate two methods - node based and permutation based random walk SSAP - to devise rankings and employ them with the standard SSAP results. We also compare these three methods against the case where complete information about worker rankings is known. Although the SSAP with complete information about worker rankings provides us with the highest expected reward, we note that the node-based random walk SSAP is better in the absence of complete information.