Sort objects into groups based on group size preference

Question

I have a research question that involves human subjects being sorted into groups before playing a social game.

Before sorting, each person decides on their preferred group size, from 1 to n; where n is the total number of players.

I want to be able to sort people into groups of their preferred size, allowing a given level of tolerance for being in a group size that differs from the preferred group size.

For example, in the simplest case we allow no tolerance. Consider the set of group size preferences for a population of 25 players

G = [1 1 1 1 2 2 2 3 3 3 3 3 3 3 3 4 4 4 4 4 4 5 5 5 5].

This will result in the following sorting:

Group a: [ 1 ]

Group b: [ 1 ]

Group c: [ 1 ]

Group d: [ 1 ]

Group e: [ 2 2 ]

Group f: [ 3 3 3 ]

Group g: [ 3 3 3 ]

Group h: [ 4 4 4 4 ]

and the group of remainders: [ 2 3 3 4 4 5 5 5 5 ].

Note how group size equals group size preference and the remainders are all those individuals that could not be put into a group of preferred size.

I want to be able to extend this by allowing some level of tolerance in acceptable group size compared to the preference. For instance, an individual that prefers to be in a group of 3, with tolerance of 1, would be willing to be in any group of size 2-4, but would otherwise be a remainder. However, being in a group of preferred size should have more weight than being assigned to a different group.

Can this problem be solved to minimise: a.) the number of individuals that are left as a remainder b.) the number of people that are put into groups different to their preference c.) the level of tolerance?

Even pointing to similar problems would be much appreciated.

Thank you for any assistance!

Answer 1

Dr. Stevil:

First, I'll address your three optimization goals and then offer a possible solution:

• Goal A: The remainder is not an useful objective function in this case, as you can force it to be zero with a high enough tolerance.
• Goal B: This is a reasonable goal. You've already done half the work by getting the low-hanging fruit. Just need to allocate the reminder to maximimze preference matching.
• Goal C: Tolerance is the decison variable in your case. You would need auxillary constraints on the maximum remainder size or something like that, otherwise you just set tolerance = 0 and be done.

Based on the above, I'll offer an extension for Goal B: Maximize the number of people in their preferred group size.

The approach is done in two steps: First, form groups as you did in your example, forming groups of size i from the individuals with preference i. For the remainder group, calculate the difference between the number of individuals with preference i and i (i.e., $D_{i}=i-N(i)$). Sort the remainder group according to $D_{i}$ (in increasing order) with $N(i)$ serving to break ties. In your case, you would get: $\{5,5,5,5,3,3,2,4,4\}$. Form an ordered set of preferences by sequentially indexing the preferences, moving from left to right (i.e, $S_{1}=5,S_{2}=3,S_{3}=2...S_{m}=\;$rightmost preference) Now, sequentially add $D_{S_{1}}$ individuals to the group formed from individuals with preference $S_{1}$ starting with individuals with preference $S_{m}$ and working towards $S_{1}$ until you have assigned $D_{S_{1}}$ individuals. Repeat this for the next leftmost group, $S_{2}$ from the remaining individuals, again assigning from the rightmost side of the remaining set.

In your case, you would get: {5,5,5,5,4}, {3,3,4}, {2} for a total of 6 satisfied individuals, plus the ones you assigned previously.