Question

There are $n$ students in a class, and they must be divided into, say, $k$ groups. Each student ranks the other students in order of preference of working together. Is there a way to generally optimize student happiness (where happiness is based on working with preferred teammates). We could assume for simplicity that happiness is correlated in a simple (say linear) way with preference rank of group members.

When will there be a unique optimal grouping?

What if the happiness is not linearly correlated to preference rank?

Answer 1

This is a generalization of the stable roommate problem (which is the same thing where $k = n/2$, ie, groups of 2). In general, there exist groups in which under any pair of groups contain members who would both like to switch teams.

From wikipedia:

For a minimal counterexample, consider 4 people A, B, C and D where all prefer each other to D, and A prefers B over C, B prefers C over A, and C prefers A over B (so each of A,B,C is the most favorite of someone). In any solution, one of A,B,C must be paired with D and the other 2 with each other, yet D's partner and the one for whom D's partner is most favorite would each prefer to be with each other.