How to calculate correlation amongst preferences?

Question

I have to split a group of x people into 3 or 4 groups, most likely 3.

I want people to be happy, so I'm having each person rate the other members of the big group from 1 to (x-1).

How do I optimize preferences to create 3 groups?

Answer 1

Here is a method that is likely to get a good arrangement, even if it is not an optimal arrangement:

First create a ranking function that can take any pair of groupings and determine whether one is better than the other. Then apply the following algorithm:

1. Randomly assign people into groups.
2. Randomly pick one person from each group.
3. Create new groupings in which each combination of reassignments is performed on the people chosen in step 2. (For 3 groups there will be 6 such reassignments. For 4, 24.)
4. Of all possible reasignments, pick the best one.
5. Repeat steps 2–4 one million times.

UPDATE

If there are only 18 people that need to be assigned, then that's just (18 choose 6) * (12 choose 6) / 6 = 2,858,856 possible groupings. (Or, in the case of four groups it's (18 choose 4) * (14 choose 4) * (10 choose 5) / 4 = 192,972,780 groupings.)

You can just try each one and pick the best.

I guess the ranking algorithm itself is really the hard part of this assignment.

You could just give each person a score based on summing the scores of the people selected to be in their group, then sum the scores of each person together.

The problem is that you're going to end up with all the popular people in one group, and all the unpopular people in another group, and all the telephone handset cleaners in another group.

You should just assign people randomly, and then tell them that you used some really scientific system. That way everybody gets a good mix.

Answer 2

Measure the total satisfaction of a given configuration by calculating the distance between the actual positions and the stated preferences. Start with a randomized set of groups. Then use something like hill climbing or simulated annealing to optimise.

http://en.wikipedia.org/wiki/Hill_climbing

http://en.wikipedia.org/wiki/Simulated_annealing

Simulated annealing sounds complicated, but it's really just a cleverer version of hill-climbing.