Stable pairing algorithm with only set of priorities?

Question

Consider the Stable Marriage Algorithm:

In mathematics and computer science, the stable marriage problem (SMP) is the problem of finding a stable matching between two sets of elements given a set of preferences for each element. A matching is a mapping from the elements of one set to the elements of the other set. A matching is stable whenever it is not the case that both:

The stable marriage algorithm is a complete and optimal solution to the stable marriage problem.

However, I have a different, yet similar, problem. I need an algorithm that, when given a pair of elements, will find a stable and optimal pairing between them. The catch is that in my problem, only one pair of the elements has preferences, the other side doesn't care.

To bring a real life analogy to this, consider the problem of job assigning:

In a group software engineering project, there are m employees and n different tasks to be accomplished. Each employee has his/her own experiences and expertise so cares about which task he/she gets to work on. The manager asks each employee to write down a preference list of the tasks, ranking each task. What would be an algorithm to pair each employee with ONE task, so that employee satisfaction is maximized.

If n > m, there will be left over tasks, this is ok, they can be completed by interns or contractors.

Note: one easy way to quantize employee satisfaction is by simply adding up the rankings of the jobs that each employee got.

For example: if employee a got his first choice, and employee b got her third choice, and employee c got his 2nd choice, the overall employee satisfaction is 1 + 3 + 2 = 6.

Minimizing this number will maximize satisfaction.

Answer 1

This is known as the assignment problem. The textbook example is transportation: n number of packages need to be transferred while there are only m drivers(m < n) and where there is a cost associated with each transport. I believe your problem can be cast into that form.

The most common algorithm to solve this is the Kuhn-Menkres algorithm, also known as the Hungarian algorithm. This algorithm is available online in many programming languages, so google and go forth!