# Algorithm to assign tasks

We have $$n$$ tasks, each has its own price: $$a_i$$. We also have $$n$$ workers, each can do task $$i$$ with a probability $$b_i^k$$. Each worker should do only 1 task. I am trying to find out what will be the best algorithm to maximize the expectation of money that workers can earn (this will be a sum: $$\sum\limits_i a_ib_i^{k_i},$$where $$k_i$$ are some permutation of $$1,..n$$).

My idea was to sort probabilities of success for each of the tasks and compare products of its prices and difference of the top 2 probabilities. When I will get the maximum of such function, I will assign this task to a worker with the best probability to successfully finish it and after that do the whole procedure again. Unfortunately, I was stuck trying to prove it, also I am not even sure that this is the best possible algorithm. I will really appreciate any help or a hint.

• You can always rephrase it as an IP problem if nothing else, however, I doubt that this is the solution you need. If the defining matrix is totally unimodular, it is not that bad, otherwise it may be worth finding a faster algorithm. – rss Apr 30 at 15:06
• Hint: matching. – Marcus Ritt Apr 30 at 19:06