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 $i$th 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$.