5

For example I have eight kids,

A,B,C,D,E,F,G,H

If I ask them to go into groups of two, their choices are

A->B
B->C
C->B
D->B
E->A
F->A
G->H
H->C

How to make sure they get their choices as much as possible?

Or similarly, to get into groups of four:

A->B,C,D
B->A,C,G
C->E,A,D
D->B,E,G
E->F,G,H
F->A,B,C
G->E,F,B
H->F,E,C

I am sure there are many ways to do this. But I just don't know where to start looking for algorithms. What is the mathematical term for such problems?

Chen Stats Yu
  • 293

2 Answers2

2

You're looking for matching algorithms. The alternating path algorithm is good for improving matchings when you are just trying to create pairs. Don't know about larger groups but they must follow the same pattern.

tomi
  • 9,594
2

At least for pairings, one way to look at this is basically the "stable roomates problem", except where instead of each person ranking everybody else in strict order, you basically have a "top choice" for each person and then everyone else for that person is ranked equally (and lower than the top choice). You can see https://en.wikipedia.org/wiki/Stable_roommates_problem for an efficient algorithm to find a stable roomates assignment solution provided a satisfactory solution exists (sometimes it doesn't).

I'm not sure how easy/how much studied the problem is for grouping people together in groups of $k$ people according to preferences, for $k > 2$. For one thing, there are many ways to define an "optimal solution". Do you want to maximize the number of ordered pairs $(X,Y)$ where $X$ would prefer to be in a group that had $Y$? Or maximize the number of pairs where both $X$ and $Y$ want each other to be in their group? Or maximize the number of $X$ such that $X$ gets everyone they want in their group? Or some weighted combining of these measures? For that matter, you could similarly modify the $k = 2$ case this way too and come up with a different objective than the stable roommates formulation.

user2566092
  • 26,142