Games – JMFT's Website

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$ ?

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

Category: Games

Speed dating and graph theory

Doubling in backgammon

The problem