A game on tournaments with multiple edges

Wildon's Weblog 2020-08-21

Here is a quick post to record a combinatorial game that I think might be of interest, but I don’t have time to think about seriously now.

When Person A plays Person B on the online chess server on which I spend far too much time, the server looks to see who has the longest run of consecutive games as black, and chooses that person to be white. Ties are broken randomly. This is a simple but effective rule: for instance it guarantees that in a series of games, the players alternate colours.

Now suppose a team of people want to manipulate the server into giving one of their members a long run of consecutive games as white. (This would of course be strictly against the server policies.) How big must the team be to guarantee that some member gets $n$ consecutive games as white?

A quick look at the small cases reveals the answer. With three people, having arbitrary past histories (this matters below), A plays B and the black player, B say, then plays C. If B is white, then when A plays B again, either A or B establishes a run of two games as white. If B is black (for instance this always happens if C has had a run of two black games), then when A plays C, either A or C gets the same run. Note that in the first case, A never plays C, but instead plays B twice.

With four people, we use the strategy above to give A a run of two white games, and then using B, C, D, give B say, another run of two white games. Now when A and B play, a run of three white games is established. Continuing inductively we see that $n$ people can force $n-1$ consecutive white games.

One might also ask for the analogous result where multiple games between the same people are not allowed. If the aim is instead to maximize the number of games as white, then we obtain the combinatorial game where the ‘Picker’ picks an edge of the complete graph $K_n$ and the ‘Chooser’ chooses its orientation. Since in the end all edges are picked exactly once, the role of the ‘Picker’ is defunct: the Chooser can choose an $n$ vertex tournament before play begins, and follow its recommendations. By Theorem 1.2 in this article of Alspach and Gavlas, when $n$ is odd, $K_n$ can be decomposed into $n(n-1)/2m$ edge cycles of length $m$ if and only if $m$ divides $n$ . Directing each cycle in an arbitrary way then gives a tournament where every vertex has the same in- and out-degree. A simple solution when $n$ is prime is to take $m=n$ and use the cycles $(0,d,2d,\ldots,(n-1)d)$ for $1 \le d \le (n-1)/2$ on the vertex set $\{0,1,\ldots, n-1\}$ , working modulo $n$ . When $n$ is even, a discrepancy of $1$ between the in- and out-degrees of every vertex is inevitable, and it’s not hard to use the construction for $n$ odd to see that this can be achieved.

Returning to the original setting where we care about runs of white games, this shows that the Chooser can guarantee the longest run is at most the maximum out-degree, namely $\lfloor n/2 \rfloor$ .

I’ll end with two natural questions suggested by this quick analysis.

Question 1

Let $G$ be a finite graph. In each step the Picker chooses an edge of $G$ , and the Chooser directs it; multiple picks are allowed, and the Chooser may choose a different orientation on different picks. Say that vertex $v$ has a run of length $m$ if in the most recent $m$ picks involving this vertex, it was always the source. What is the maximum run length that the Picker can force somewhere in this graph?

Question 2

As Question 1, but now each edge may only be picked once.

For the first in the case of the complete graph, the analysis above shows that the Picker can force a run of length $n-1$ , and since the chooser can make the next directed edge involving this vertex an in-edge, this is best possible. For the second in the case of the complete graph, the Picker cannot do better than $\lfloor n/2 \rfloor$ , but I do not know if this is always possible.