Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
3  
The answer is simple: never assign group work! (I know some terrible stories.) –  Qiaochu Yuan Mar 11 '10 at 8:22
3  
@Qiaochu: frivolous and amusing, but of course completely incorrect. –  Loop Space Mar 11 '10 at 11:40
add comment

1 Answer 1

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|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
add comment

Your Answer

 
discard

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.