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.
