1
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • $\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. ♦
    Commented Nov 23, 2020 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. ♦
    Commented Nov 23, 2020 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
    Commented Nov 23, 2020 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
    Commented Nov 23, 2020 at 23:09

1 Answer 1

Reset to default
0
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ I'll check the "assignment problem", maybe you can provide an outline for this case? $\endgroup$
    – Gomunkul
    Commented Nov 24, 2020 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
    Commented Nov 24, 2020 at 0:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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