Permuting 9 people such that all people are grouped with each other the nearest number of times

Question

So I'm working on a problem which involves 9 agents which will be separated as follows. Each round, one of the agents will be put into a group on their own, ie. they will "sit out", whilst the other 8 agents will be divided into 2 groups of 4. There will be 9 rounds in total so that each agent will sit out one time. My questions are as follows:

1. Is it possible that each agent could be grouped with every other agent the exact same number of times?
2. If not, what is the smallest range of the number of times each agent will be grouped with another?
3. Can you design a schema to arrange $a_1, \cdots, a_9$ into such groups?

My initial thoughts are that 1 is not possible, 2 is likely going to be only a range of 1 (each agent grouped with some agents 4 times, some 3 times), and I have no idea how to mathematically formulate this so couldn't devise any sort of permutation schema to ensure this setup. I've looked at similar questions and answers on here which, while interesting and insightful to this problem, do not as far as I can tell contain the complete information to solve it.

Thanks for your help.

Answer 1

It is possible to find a solution where each agent is assigned to each other agent in the same group in three of the nine rounds.

I tackled this problem using the MiniZinc constraint solver:

include "globals.mzn"; 

int: n = 9;
int: rounds = n;
set of int: Agents = 1..n;
set of int: Rounds = 1..rounds;

int: SitOut = 1;
set of int: Group1 = 2 .. n div 2 + 1;
set of int: Group2 = n div 2 + 2 .. n;

%  each agents gets a "seat" in each round
array[Agents, Rounds] of var Agents: seats;

%  count number of allocations to same group (assuming > 0)
array[Agents, Agents] of var Rounds: counts;

%  every agents sits out once 
%  we assert that the sit out order is according to the rounds
constraint 
  forall(round in Rounds) (
    seats[round, round] == SitOut
  );

%  different seat allocations in all rounds
constraint
  forall(round in Rounds) (
        all_different([seats[agent, round] | agent in Agents])
    );

function var 0..2: agentGroup(Agents: agent, Rounds: round) =
  if seats[agent, round] == SitOut then 0
  else
    if seats[agent, round] in Group1 then 1 else 2 endif
  endif;

%  counts are symmetric; we assume i > j
constraint
  forall(i, j in Agents where i > j) (
     counts[i, j] = 
         sum([ agentGroup(i, round) == agentGroup(j, round) | 
               round in Rounds])
  );   

var Rounds: maxCount = max([counts[i, j] | i, j in Agents where i > j]);
var Rounds: minCount = min([counts[i, j] | i, j in Agents where i > j]);

solve minimize (maxCount - minCount);

function var string: groupMembers(string: groupName, set of int: group, Rounds: round) =
  ", " ++ groupName ++ ": " ++ 
  join(" ", [ if fix(seats[agent, round]) in group then show(agent) else " " endif 
  | agent in Agents]);

output 
  ["counts = \(minCount)..\(maxCount)"] ++
  [ "\nround \(round):: sit out: \(round)"
     ++ groupMembers("group 1", Group1, round) 
     ++ groupMembers("group 2", Group2, round)
    | round in Rounds ] ++
  ["\n\ncount the numbers of assigments to the same group:\n  "] ++
  [" \(agent)" | agent in Agents] ++
  [ if j == 1 then "\n\(i):" else "" endif ++ 
    if i == j then " -" else " " ++ 
    if i > j then show(counts[i, j]) 
             else show(counts[j, i]) 
    endif 
    endif | i, j in Agents]
  ; 

Solution (edited):

    counts = 3..3
    rd. sit  group 1             group 2
   +---+----+-------------------+-----------------
    1:: 1,       3     6 7 8  ,    2   4 5       9
    2:: 2,   1   3   5 6      ,        4     7 8 9
    3:: 3,     2       6   8 9,  1     4 5   7    
    4:: 4,   1         6 7   9,    2 3   5     8  
    5:: 5,       3 4   6     9,  1 2         7 8  
    6:: 6,   1       5     8 9,    2 3 4     7    
    7:: 7,   1 2 3           9,        4 5 6   8  
    8:: 8,   1 2   4   6      ,      3   5   7   9
    9:: 9,   1   3 4       8  ,    2     5 6 7  
   +---+----+-------------------+-----------------

count the numbers of assigments to the same group:
   1 2 3 4 5 6 7 8 9
1: - 3 3 3 3 3 3 3 3
2: 3 - 3 3 3 3 3 3 3
3: 3 3 - 3 3 3 3 3 3
4: 3 3 3 - 3 3 3 3 3
5: 3 3 3 3 - 3 3 3 3
6: 3 3 3 3 3 - 3 3 3
7: 3 3 3 3 3 3 - 3 3
8: 3 3 3 3 3 3 3 - 3
9: 3 3 3 3 3 3 3 3 -

For $3$ agents/rounds, the number of matching group assignments is $0$. This cannot be found by my model, as it restricts/assumes the counts to values greater than $0$.

Assuming that the two groups have the same size, the total number of agents must be odd. It appears that the number of matching group assignments for $2k+1$ agents is $k-1$. The model can show this for $5, 7, 9$ agents. For $11$ agents, the solver narrowed down the interval to $3..5$ but has been unable to arrive at the expected value $4$.

For $2k+1$ agents/rounds, each of the agents takes part in $2k$ rounds. Per round, he is assigned to the same group as $k-1$ other agents. Therefore, the total number of assignments to other agents is $2k(k-1)$. On average, this is $k-1$ for each of the other $2k$ agents.

---

Update:

A simplified MiniZinc model capable to solve the problem for larger teams:

include "globals.mzn"; 

int: n = 9;
int: rounds = n;
set of int: Agents = 1..n;
set of int: Rounds = 1..rounds;
set of int: Groups = 0..2;

int: SitOut = 0;
int: Group1 = 1;
int: Group2 = 2;

%  each agents gets a "group" in each round
array[Agents, Rounds] of var Groups: groups;

%  every agents sits out once 
%  we assert that the sit out order is according to the rounds
constraint
  forall(round in Rounds, agent in Agents)  (
    (groups[agent, round] == SitOut) == (agent == round)
  );

%  counts are symmetric; we assume i > j
constraint
  forall(i, j in Agents where i > j) (
     (n div 2 - 1) == 
         sum([ groups[i, round] == groups[j, round] | 
               round in Rounds])
  );   

solve satisfy;

function var string: groupMembers(Groups: group, Rounds: round) =
  ", " ++  
  join(" ", [ if fix(groups[agent, round]) == group then show_int(2, agent) else "  " endif 
  | agent in Agents]);

output 
  ["round sit group " ++ show_int(-2*n,1) ++ "group " ++ show_int(-2*n, 2)] ++
  [ "\n#" ++ show_int(2, round) ++ "   " ++ show_int(2, round)
     ++ groupMembers(Group1, round) 
     ++ groupMembers(Group2, round)
    | round in Rounds ] 
  ; 

The difference compared to the first model is that there are fewer decision variables with smaller value domains. Rather than narrowing down the interval of matching assignments, the number of assignments is enforced as constraint. This leads to faster solution times.

Answer 2

I'm still not sure whether a solution is possible, but randomising and running 1 million iterations of this brute force code did not give me the range of 0 that I wanted. It did give me a range of 1 though, which for my use case is just about sufficient, but I'm still interested in the general solution if anyone has any ideas. Anyway here's a link to my github for the brute force code!

https://github.com/jjalexander1/mimir_scheduler/blob/master/mimir_scheduler.py