Looking for an algorithm for splitting a list of people (S) into groups (G), |S| <= |G|, more than one person wants to be in a certain group.
Every person has a monotone ranking from highest (most desired) to lowest of all the groups.
Using this list I want to find the "best matching".
"best matching" is when you maximize the "score of the matching".
"score of the matching" is the sum of the group rankings of the people that got matched with the group, i.e. summing the ranking that the people gave to the group which was chosen for them.
I’m also interested in ideas for other "fairness" values for maximization.
If you want to maximize the sum of the scores for each participant, this is an instance of the assignment problem; use the Hungarian algorithm, or any other algorithm for computing a maximum matching.
You might also be interested in stable marriage algorithms, which have a different notion of fairness.
Answered by D.W. on December 15, 2020
Get help from others!