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.
What you are describing is a "greedy heuristic", and no, it is not guaranteed to find an optimal assignment. To expand on the comment by Marcus Ritt, see this description of the assignment problem.