Speed dating and graph theory

Suppose you are organising a speed dating event. You are given a graph G = (S,P). The event consists of a number of rounds; in the ith round of the event, you must pick a subset P_i\in P such that no s\in S appears in two elements of P_i, and P_i\cap P_j = \varnothing for all j < i. (That is, no person may be in two dates at the same time, and the same date may not occur in two rounds.) The event lasts for R rounds, finishing when \cup_{1\leq i\leq R} P_i = P. (That is, when all possible dates have occurred). The ‘idle time’ is defined as T = \sum_{1\leq i\leq R} \sum_{s\in S} 1(s \not\in p \forall p\in P_i).

For example, consider an event for M straight men and N straight women. Then G is the complete bipartite graph K_{M,N}, and a simple solution is to have all the men seated around the inside of a ring-shaped table, all the women around the outside, and to have one set rotate around after each round while the other set stays still. In this case, R = \max(M,N) and T = R |M-N|.

How can you choose the P_i to minimise T?

Doubling in backgammon

You are playing backgammon (wlog as white). (The rules of backgammon are explained more clearly here.) At any given point during a round, there are six possible outcomes of the round, with corresponding values:

  • white wins by a backgammon (+3n)
  • white wins by a gammon (+2n)
  • white wins (+n)
  • red wins (-n)
  • red wins by a gammon (-2n)
  • red wins by a backgammon (-3n)

At the start of a round, n=1 and both players have control of the doubling cube.

When it is Alice’s turn, she may offer a double if and only if she controls the doubling cube. If Alice offers a double, then Bob must accept or decline. If Bob declines, then Bob forfeits the round and Alice gains n points. If Bob accepts, then Alice ceases to control the cube, Bob gains control of the cube, and n is multiplied by 2.

(There are other rules.)

The problem

Suppose that both you and your opponent can perfectly calculate the probability of each of the above outcomes.

  • It is your turn. Should you offer a double?
  • It is your opponent’s turn, and they have offered a double. Should you accept?

For a harder problem, suppose that you assign probabilities p_i to each of the above outcomes, and your opponent assigns different probabilities q_i, but you know both the p_i and the q_i.