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.
No comments:
Post a Comment