Assignment based on ranked preference

Question

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?

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).