5
$\begingroup$

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?

$\endgroup$
2
  • 3
    $\begingroup$ The answer is simple: never assign group work! (I know some terrible stories.) $\endgroup$ Mar 11, 2010 at 8:22
  • 3
    $\begingroup$ @Qiaochu: frivolous and amusing, but of course completely incorrect. $\endgroup$ Mar 11, 2010 at 11:40

1 Answer 1

9
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks, I knew it must have been thought of before, just didn't know what to look for. $\endgroup$
    – Kiochi
    Mar 11, 2010 at 17:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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