Risk-free games

---

The risk-free game (game with guaranteed win) is a type of perfect-information positional game with no draws of two players.

Introduction

The concept and constructions of a risk-free games were introduced by Chudnov for a family of positional games in which the sequence of player's moves is determined by a cyclic sequence (cyclic order) of length $n$. Such a game can be interpreted as a game in which $n$ participants are divided into two teams (coalitions), the first of which includes $k$ participants with the numbers $i_{1},i_{2},...,i_{k}\in \{0,1,...,n-1\}$, and the second is the remaining $n-k$ participants. Players make moves in turn, starting with the participant with the number 0, so the t-th move is made by the participant with the number $t-1\mod n$.

A positional perfect-information game of two coalitions is called a risk-free game for the first coalition (or a game with guaranteed win for the first coalition) if, for any cyclic shift of the number of the participant making the first move, the first coalition has a winning strategy.

The problem and example

Let the second coalition has a right, before the game commences, to assign a player with the first move and in this way move in cycle the numbers of participants by any number $j.$ So, in each such a game, which is selected by the second coalition, the 𝑡-th move is performed by the player with number $t+j-1\mod n.$ The question arises under which conditions on $k$ and $n$ this right does not guarantee the success to the second coalition. It is well known that for $n=2$ the player choosing a move secures his success by selecting a winning strategy. It is also easy to check that for $n\leq 5$ the sought-for game exists only for $k>n/2,$ which is indicative of the important role in this cases of the right of appointment of a player who moves first. At the same time, with increasing number of participants this right is not always decisive in the game.

Fig.1: A game in which the 1-coalition wins under any cyclic shift of players.

For example a positional game, in which a coalition consisting of 3 participants wins against a coalition consisting of 4 participants (the first move may be performed by any of the 7 participants) is considered on a digraph (Fig.1), where vertices correspond to possible positions in the game, the arcs correspond to admissible moves of players, and the initial node corresponds to the initial position of the game. To simplify the representation of the graph, the sequences of arcs forming simple chains (that is, the chains in which the in- and out-degrees of interior nodes are all 1) are labeled by a single arc with indication of its length at its terminal node.

The players are labeled by numbers 0,1,...,6; the players from the 1st coalition have numbers 0, 1, 3 and may act as players with numbers $j,j+1,j+3\mod 7,$ where $j\in \{0,1,...,6\}.$ Each player, starting from the player 0, transforms by its move the current position appeared (obtained from the previous player) into a new position which is attainable from the current one in accordance with the game rules; then the players passes the move to the player next in cycle. Actions of each player in the 1st coalition are labeled by the number of this player positioned above the arcs out going from the nodes corresponding to the game positions. A direct verification shows that, for all move variants of players of the 2nd coalition, only a player from the 1st coalition can move to a terminal node. Based on this, one can construct a game in which the 1st coalition can always transform the position to a given (winning) position and also construct games with other variants of assessing the game result (for example, a coalition with no ability to move loses the game).

Boundaries for k(n)

The problem of the existence of classes of games with guaranteed win iz closely related to the construction of difference sets and finite projective planes: the existence of a cyclic projective plane leads to the construction of a flat perfect difference set C containing | C | = k = q + 1 elements, on the basis of which an $(n,k)$ -game with guaranteed win can be constructed for any values $k=2,3,...$ and $n=k^{2}-k+1.$

The minimum value of $k=k(n)$ for which there exists a $(k,n)$-game with guaranteed winnings is defined by the boundaries:

a) $(1+{\sqrt {4n-3}})/2\leq k(n)\leq \lceil {\sqrt {2(n+2)}}\rceil ,$ where $\lceil \cdot \rceil$ -- rounding up;

b) if $s=\lceil {\sqrt {2(n+1)}}\rceil$ is even, then $k(n)\leq s.$

The exact values of $k(n)$ are known for all $n\leq 80$ and also for $n=q^{2}+q+1,$ where $q=k(n)-1$ is the power of a prime number. In view of it is also known that for $k\leq 2\cdot 10^{9},$ different from the values of $k=q+1,$ the inequality $n<k^{2}-k+1$ holds.

It should be noted that the dependence of $k(n)$ is not monotonous, and if, for example, there is a game in which a coalition of 9 participants has a guaranteed win against a coalition of 73 participants, then for game 9 against 66 (and also against 67, 68, ..., 72) such a game does not exist.

References

This article "Risk-free games" is from Wikipedia. The list of its authors can be seen in its historical and/or the page Edithistory:Risk-free games. Articles copied from Draft Namespace on Wikipedia could be seen on the Draft Namespace of Wikipedia and not main one.

---