MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 9 down vote accepted

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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