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.

  • $\begingroup$ This doesn't sound like a well-specific problem statement yet. Please take some time to think through what your requirements are, then edit the question to post a clear problem statement with all requirements. It's not clear how we are supposed to take into account people's "wants". Are they required? Optional? What exactly are the inputs, and exactly what requirements must a solution meet to count as a correct/valid output? $\endgroup$ – D.W. Nov 23 '20 at 22:48
  • $\begingroup$ Note that "has to be done in one round" makes no sense as a requirement, as that is a "how" rather than a "what you want achieved"; if I give you an algorithm that produces an output, it might be impossible to tell whether it used one round or multiple rounds. $\endgroup$ – D.W. Nov 23 '20 at 22:48
  • $\begingroup$ @D.W. "on round" in this context means that you don't ask the students again. you only use the initial data $\endgroup$ – Gomunkul Nov 23 '20 at 23:01
  • $\begingroup$ I modified the question to limit it. I'm actually interested in approaches to the splitting of students and a what would be a "fair" thing to maximize. $\endgroup$ – Gomunkul Nov 23 '20 at 23:09

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.

  • $\begingroup$ I'll check the "assignment problem", maybe you can provide an outline for this case? $\endgroup$ – Gomunkul Nov 24 '20 at 0:49
  • $\begingroup$ I don't think the "stable marriage" algorithms fits since the groups are not "wives", they don't provide a list of their priorities. if I understand correctly. $\endgroup$ – Gomunkul Nov 24 '20 at 0:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.