Need an adaptive algorithm for participant subgroups that balances repeated pairings

Question

I want to build a utility that helps manage small groups of participants. It is an acting class setting.

For each exercise, the facilitator will usually have some number of participants get up to do a scene. Two is the most common, but sometimes 1 or 3 or 4. More than 4 is not common.

I want the utility to have a list of participants and then the facilitator can just ask it for a specified number of people. E.g. 2.

The utility should do a good job of balancing combinations. For example, let's say there are 5 participants, A, B, C, D, E. If A and B work together, then ideally they should have also worked with C, D, and E before working together again.

I know how to manage this well if it's always just pairs. You can create, in advance an ordered list of all the pairings.

But once you add the possibility of other changeable group sizes, I don't know how to manage it.

My starting point is to keep track of how often each participant has worked with every other participant. So, I could look at A and know how often she has worked with B, C, D, and E, and then if A is due to get up, pair her with the person/people she has worked least often with.

The problem with this, is that it can lead to situations where the last remaining unmatched pair have already worked together.

As a simple counter-example: Say I have 6 participants - A - F. In the first lot of exercises, these are the pairs. AB CD EF. Then next round, I might (if not thinking) do AC, then BD, but now I'm left with E and F again. This is not ideal, and is what I need the algorithm to avoid.

I think part of the solution should be that everyone should get a roughly even number of turns. So, at any given point, we have a group of participants who have had fewer turns that the others, and we need to balance them out so that they don't work with people they've worked with (where possible) or at least with the people they've worked with least, and it needs to anticipate the possible remaining combinations and avoid duplication there too. Part of the complexity is that you don't know in advance what group sizes will be used for the remaining groups.

Does this type of algorithm / problem set have a specific name? Are there known algorithms for solving it?

(As an extra complication, there is the possibility of a participant having to leave unexpectedly, or an extra participant who arrives late, but that might be for later)

This is my first time asking here, so I hope I've posted this appropriately. Thanks for your patience and assistance!

Answer 1

It sounds like the stakes are low, so I would suggest something simple and "good enough", rather than looking for fancy algorithms that will be guaranteed to give the optimal solution. One approach is to take the approach you're already considering, but break ties randomly. This seems like it may do well enough in practice: it is possible to get into a bad situation, but the randomness might make that unlikely; and this might occasionally have one student participate a little more than they otherwise would, but that I'd expect that to average out over time and so maybe it isn't a big deal.

Answer 2

For anyone who may be interested, here's what I came up with.

I came up with a way to score a given subset of participants. The scoring is made of 4 parts.

1. scTogS = Togetherness score for the subset.
2. scTogO = Togetherness score for the other participants (those NOT in the subset).
3. scTurns = Score based on how many turns in total the members of the subset have had.
4. scRecent = Score based on how many members of the subset were in the most recent subset.

The "togetherness" score is the sum of how many times each member of a given set has played with other members of that set.

Each part of the score is given a weighting, so that the total score is:

total = scTogS + k1 x scTogO + k2 x scTurns + k3 * scRecent

A LOWER total score is a preferable subset.

What this scoring does is to favour combinations that:

1. are more diverse;
2. allow more diversity in the remaining group;
3. give participants a fair number of turns;
4. avoid people being up twice in a row.

Each time I need to provide a subset, I take one of two options depending on the total number of possible combinations.

For <= 2000 combinations: Consider all combinations.

For > 2000: Randomly choose 200 subsets, favouring those who have not played recently and who have played less often.

Evaluate the score for all subset combinations. Randomly select a subset from those with the lowest-equal score and return it.

I've run various scenarios and looked at the "fairness" of the results, tweaking the constants to get a good balance of people playing with a good variety of others, and also getting to play roughly an equal number of times.

Not sure how common this sort of problem is, but I thought these ideas might be useful to someone else.

Also open to any improvements to the overall idea! Thanks.