Suppose you are organising a speed dating event. You are given a graph . The event consists of a number of rounds; in the th round of the event, you must pick a subset such that no appears in two elements of , and for all . (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 rounds, finishing when . (That is, when all possible dates have occurred). The ‘idle time’ is defined as .
For example, consider an event for straight men and straight women. Then is the complete bipartite graph , 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, and .
How can you choose the to minimise ?
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 ()
- white wins by a gammon ()
- white wins ()
- red wins ()
- red wins by a gammon ()
- red wins by a backgammon ()
At the start of a round, 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 points. If Bob accepts, then Alice ceases to control the cube, Bob gains control of the cube, and is multiplied by 2.
(There are other rules.)
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 to each of the above outcomes, and your opponent assigns different probabilities , but you know both the and the .