# How to optimize student happiness in group work?

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?

-
The answer is simple: never assign group work! (I know some terrible stories.) –  Qiaochu Yuan Mar 11 '10 at 8:22
@Qiaochu: frivolous and amusing, but of course completely incorrect. –  Loop Space Mar 11 '10 at 11:40

## 1 Answer

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.

-
Thanks, I knew it must have been thought of before, just didn't know what to look for. –  Kiochi Mar 11 '10 at 17:11