Assume that there are n students, who have to be evenly assigned to m groups. For every student, a preference ranking of of the m groups is given.

I partially order assignment by pointwise preference, i.e. one is better or equal to another if for every student, the assigned group is ranked higher or equal.

What algorithm can I use find “locally optimal” solutions, i.e. assignments where there are no strictly better solutions?

I assume there will be multiple locally optimal solutions. Is there a sensible way to order them without giving the students an incentive to be dishonest in their ranking, i.e. without encouraging strategic voting? If so, can that be solved?

And finally: What are the right terms to search for research that solves this and related problems?

  • $\begingroup$ Check out the "stable marriage" problem. $\endgroup$ Nov 6, 2015 at 12:30
  • $\begingroup$ Right, that’s related. I’ll see what I can find starting from there. $\endgroup$ Nov 6, 2015 at 12:49
  • 1
    $\begingroup$ Did you end up solving this problem in a satisfiable manner? It appears to be a non-trivial step to go from the SMP to this particular problem. $\endgroup$
    – Joost
    Mar 24, 2016 at 15:19
  • $\begingroup$ I did not solve it at all, sorry. $\endgroup$ Mar 24, 2016 at 17:30
  • $\begingroup$ This post describes a similar problem and might be of use to you. $\endgroup$
    – Pim
    Feb 23, 2021 at 21:08

1 Answer 1


The terms you can use to search the literature are stable marriage and the assignment problem.

As far as discouraging strategic voting, one relevant term might be strategy-proof. This might also be relevant to the general area of mechanism design. My vague recollection is that discouraging strategic voting in stable-marriage-like problems is a hard problem, but I don't know if I'm remembering that right.

For instance, consider stable marriage. The traditional algorithm gives a matching that is male-optimal and female-pessimal (every male gets the best possible mate he possibly could have received in any stable matching; and every female gets the worst possible mate she could have received in any stable matching). Now suppose the females all get together and collude. In a world of perfect information, they can compute what the female-optimal matching would be, and then change their reported preferences to ensure that the female-optimal matching will be selected.

In fact, collusion is not necessary -- the same result happens if each female individually acts in their own self-interest, without any cooperation or conspiracy. Assume again a world of perfect information, where everyone's true preferences are known (to the females, at least). Then each female can compute the best possible mate she could hope for, i.e., the best mate out of all possible matches in all possible stable matchings; she can then change her reported preferences to list that male as her first preference. If the men use their true preferences and each woman uses this procedure to select her preferences strategically, and then we run the traditional algorithm, we end up with the female-optimal (and male-pessimal) matching. Each woman has an incentive to behave in this way, and no collusion is necessary (assuming perfect information).


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.