Eric Duchêne

Nacim Oijid

Aline Parreau

Bipartite instances of INFLUENCE

The game influence is a scoring combinatorial game that has been introduced in 2020 by Duchene et al [DGP + 21]. It is a good representative of Milnor's universe of scoring games, i.e. games where it is never interesting for a player to miss his turn. New general results are first given for this universe, by transposing the notions of mean and temperature derived from non-scoring combinatorial games. Such results are then applied to influence to refine the case of unions of segments started in [DGP + 21]. The computational complexity of the score of the game is also solved and proved to be PSPACE-complete. We finally focus on some specific cases of influence when the graph is bipartite, by giving explicit strategies and bounds on the optimal score on structures like grids, hypercubes or torus.

Introduction

influence is a two player scoring combinatorial game introduced by Duchene et al in [DGP + 21]. It is played on a directed graph where each vertex is colored either black or white. Alternately, both players (called Left and Right) take a vertex of their color: if it is Left's turn, she takes a black vertex, remove it and all its successors. If it is Right's turn, he takes a white vertex, remove it and all its predecessors. The game ends when the graph is empty. Each player scores the total number of vertices that he/she removed. Naturally, the objective of each player is to maximize his/her score.

The work presented in [DGP + 21] is the first study of a particular combinatorial game within the recent scoring framework of Larsson et al. [START_REF] Larsson | Scoring games: the state of play[END_REF]. Indeed, if scoring combinatorial game theory has been introduced by Milnor [Mil53] and Hanner [START_REF] Hanner | Mean play of sums of positional games[END_REF] in the 50's, their work was not followed up, partly because of the hardness of solving such games. This is only since the last decade that new results appeared on the topic, in particular with the introduction of general frameworks of resolution, for particular families (also called universes) of scoring games.

In [DGP + 21], the authors show that influence belongs to the so-called Milnor's universe of scoring games. Roughly speaking, the major property that derived from this universe is that a player has never interest to miss his/her turn. They also partially solve the game on particular classes of digraphs, called segments, that correspond to alternated black and white oriented paths, with arcs from black to white vertices.

In this paper, we extend the case of segments to more general families of bipartite graphs having the same properties. For that purpose, we consider a particular version of influence that is played on bipartite digraphs, where each set of the bipartition corresponds to vertices of the same color. In addition, all the arcs are oriented from black to white vertices. According to these constraints, this version amounts to playing the game on an undirected bipartite graph (where black and white vertices form the two sets of the bipartition), and where each player takes a vertex of his/her color, removes it and all its neighbours. To simplify the notation, this particular version of influence will be called bipartite influence.

Bipartite Influence is somehow very natural to play with, as bipartite bicolored graphs are a model for many 2-player abstract games. This is for example the case for checkerboard grids. Figure 1 illustrates the first two moves of a bipartite influence game played on a 5 × 5 checkerboard grid. After these first two moves, Left has scored 5 points (first move in the center), and Right 4 points (second move with the white bottom left vertex ). As discussed in [DGP + 21], since isolated vertices can only be taken by the player who owns them, they are generally 1 immediately removed from the graph and added to the score of the corresponding player. In addition, this version of the game can be considered as a scoring variation of the well-known combinatorial game node-kayles (in its partisan version). Indeed, in node-kayles, each player removes a vertex and its neighborhood. The goal of each player is to be the last player to move. The correlation between node-kayles and Bipartite Influence is thus immediate.

For the rest of the paper, each instance of Bipartite Influence will be denoted by a bipartite graph G = (B ∪ W, E), where B and W correspond respectively to the sets of black and white vertices, and every edge of E is between a vertex of B and W .

The main issue when studying a combinatorial game is the computation of the highest score of each player, by assuming both are playing optimally. This score is well defined as the game is finite and with no chance nor hidden information. The main results of this paper are described below.

In Section 2, we provide the necessary material from scoring combinatorial theory that applies for the game. In particular and for the first time, we provide a formal framework inspired from Milnor and Hanner, and also from combinatorial (non-scoring) game theory [START_REF] Siegel | Combinatorial Game Theory[END_REF] for the concept of temperature and mean of a scoring game. In Section 3, we give general basic or known results on Bipartite Influence. In Section 4, we prove that influence and even bipartite influence are PSPACE-complete. The next section deals with bipartite influence on graphs having some symmetry properties that induce a draw strategy. Section 6 is about a refinement of the results of [DGP + 21] on segments, in particular by using the concepts of mean and temperature. Finally, the game is considered on grids with two and three rows, with an exact value or a bound for the score in almost all cases. A conjecture is given for general grids.

Background for scoring combinatorial game theory

If scoring combinatorial game theory has been introduced in the 50's, the results of Milnor and Hanner have mainly been a bootstrap for combinatorial and economic game theory. A couple of recent studies (see [START_REF] Larsson | Scoring games: the state of play[END_REF] for a survey) have settled general results for scoring game theory. For the reasons detailed in [START_REF] Larsson | Scoring games: the state of play[END_REF], the one of Larsson et al. in [START_REF] Larsson | When waiting moves you in scoring combinatorial games[END_REF] unifies the different previous frameworks. It has also more advantages, in particular because of its proximity with classical Combinatorial Game Theory. Our results will be presented according to this framework.

Main definitions and notations

The definitions below are derived from [START_REF] Larsson | When waiting moves you in scoring combinatorial games[END_REF].

A scoring game G is recursively defined as a couple G L |G R where G L (resp. G R ) are two sets of scoring games. G L (resp. G R ) is called the set of Left (resp. Right) options. In terms of play, the Left (resp. Right) options of G correspond to the games that can be reached by Left (resp. Right) in one move.

If G is a game with no Left option, then we write G L as ∅ s (with s being a real number) to indicate that if it is Left's turn, the game is over and the score of the game is s. The same notation applies for Right. Final positions 2 5 -5

5

-1 -1 -5

Figure 2: Example of a game tree from a position of Bipartite Influence correspond to games of the form ∅ s |∅ t .

Note that in the rest of the paper, we will consider only short games, i.e. games G L |G R where the sets G L and G R are finite sets of short games.

In many games having symmetric rules, there exist no position of the form ∅ s |∅ t with s = t. In particular, this is the case of influence. As they correspond to final positions, games of the form ∅ s |∅ s are called numbers and will be simply denoted by s.

In scoring combinatorial game theory, the so-called game tree is a nice way to represent a game and all the possible moves. Given a game G, the set of nodes of its game tree are all the positions that can be reached when playing from G. The root of the tree is the starting position of the game. Given a node, its left (resp. right) sons are the Left (resp. Right) options. An example of game tree for Bipartite Influence is given in Figure 2. The scores on the leaves correspond to the difference between the number of vertices removed by Left and Right during the play.

If the notion of score is well defined when G L or G R is empty, Larsson et al. [START_REF] Larsson | When waiting moves you in scoring combinatorial games[END_REF] extended it recursively to any game G. Inspired by the notions of Left and Right stops in combinatorial game theory [START_REF] Siegel | Combinatorial Game Theory[END_REF], they defined in a similar way the notions of Left and Right scores corresponding to the score of the game depending on whether Left or Right starts the game.

Definition 1 (Larsson et al [START_REF] Larsson | When waiting moves you in scoring combinatorial games[END_REF]). Let G = G L |G R be a scoring game. We call Left score and Right score of G, respectively denoted by Ls(G) and Rs(G), the following functions :

Ls( ∅ s |G R ) = Rs( G L |∅ s ) = s if s is a real number Ls( G L |G R ) = max G l ∈G L Rs(G l ) if G L = ∅ s Rs( G L |G R ) = min G r ∈G R Ls(G r ) if G R = ∅ s
These definitions yield a partial order on the games. The convention is that positive scores are in favor of Left, whereas negative scores are for Right. Games with a score equal to zero are draws. On the example of Figure 2, if G is the root, we have Ls(G) = 5 and Rs(G) = -5. This means that the player who starts wins the game.

The following definition concerns the length of a game.

Definition 2. Let G = G L |G R be a scoring game. We define the length of G, denoted by l(G) as the size of the longest sequence of moves in G.

Recursively, l(G) is thus defined as follows:

l( ∅ s |∅ t ) = 0 for any real numbers s and t l( G L |G R ) = 1 + max G ∈G L ∪G R l(G )
As for standard combinatorial games, the disjunctive sum operator + applied to scoring games is defined as follows:

Definition 3 (Larsson et al. [START_REF] Larsson | When waiting moves you in scoring combinatorial games[END_REF]). Given two games G 1 and G 2 , their disjunctive sum , written G 1 + G 2 is defined as the following game:

G 1 + G 2 = ∅ 1+ 2 |∅ r1+r2 if G 1 = ∅ 1 |∅ r1 and G 2 = ∅ 2 |∅ r2 = ∅ 1+ 2 |G R 1 + G 2 , G 1 + G R 2 if G 1 = ∅ 1 |G R 1 and G 2 = ∅ 2 |G R 2 and at least G R 1 or G R 2 is not empty = G L 1 + G 2 , G 1 + G L 2 |∅ r1+r2 if G 1 = G L 1 |∅ r1 and G 2 = G L 2 |∅ r2 and at least G L 1 or G L 2 is not empty = G L 1 + G 2 , G 1 + G L 2 |G R 1 + G 2 , G 1 + G R 2 otherwise
For the accuracy of this definition, note that

G L 1 + G 2 does not exist if G L 1 is empty.
In addition, the opposite (or negative) of a game G, denoted by -G, is defined as the game where the roles of Left and Right are exchanged. In Bipartite Influence, it consists in exchanging the colors of the vertices. By definition of the scores, we have ([DGP + 21], after Corollary 15) that for all G, Ls(-G) = -Rs(G).

Finally, the notion of equivalence has been defined in order to replace big games by smaller ones in disjunctive sums, without changing the score: Definition 4 (Milnor [START_REF] Milnor | Sums of positional games[END_REF]). Two games G 1 and G 2 are equivalent (write G 1 = G 2 ) if for any game G, we have

Ls(G + G 1 ) = Ls(G + G 2 ) and Rs(G + G 1 ) = Rs(G + G 2 ).
Note that this definition makes sense when G, G 1 and G 2 have similar properties (same universe -see next paragraph -or same ruleset).

Milnor's Universe

In scoring combinatorial game theory, a universe is generally defined as a set of games closed under disjunctive sum, by taking options and negative [START_REF] Larsson | When waiting moves you in scoring combinatorial games[END_REF]. Several universes of scoring games have been considered in the literature (Stewart [Ste11], Ettinger [START_REF] Ettinger | Topics in Combinatorial Games[END_REF], Larsson [START_REF] Larsson | When waiting moves you in scoring combinatorial games[END_REF]). In his paper, although it is not formulated in this way, Milnor introduced the universe of dicotic and nonzugzwang games [START_REF] Milnor | Sums of positional games[END_REF]. Note that in [START_REF] Larsson | When waiting moves you in scoring combinatorial games[END_REF], this universe is also denoted PS. It is defined as follows:

Definition 5 (Milnor [Mil53]). A game G is dicotic if both players can move from every nonempty position in the game tree of G.

Formally, it is equivalent to say that for all

G = G L |G R , G L = ∅ ⇔ G R = ∅.
Definition 6 (Milnor [Mil53]). A game is nonzugzwang , or with no zugzwang , if for each position G in its game tree, we have Ls(G) ≥ Rs(G).

Roughly speaking, in a nonzugzwang game, a player never has interest in skipping his turn.

The disjunctive sum of games is natural for games that split into several small components during the play. Although the score of a sum of games is in general not equal to the sum of the scores of each game, it can be bounded according to the following theorem for the games that belong to Milnor's universe:

Theorem 7 (Milnor [Mil53]). Let G and H be two dicotic nonzugzwang games, we have

Rs(G) + Rs(H) ≤ Rs(G + H) ≤ Ls(G) + Rs(H) ≤ Ls(G + H) ≤ Ls(G) + Ls(H).
In particular, if H is a number s we have Ls(G + s) = Ls(G) + s and Rs(G + s) = Rs(G) + s.

Being in Milnor's universe induces a couple of nice properties concerning the equivalence of games. The first result below means that every game G of Milnor's universe has an inverse (i.e. -G), leading to the fact that this universe is an abelian group. This is not the case of the other universes studied in the literature. The second result yields a simple test to show that two games are equivalent.

Lemma 8. For any games G and H that are dicotic nonzugzwang, we have:

• Ls(G -G) = Rs(G -G) = 0; • Ls(G -H) = Rs(G -H) = 0 if and only if G and H are equivalent.
As for standard combinatorial games, a relation order can be set on general scoring games (not necessary from Milnor's universe) [START_REF] Ettinger | Topics in Combinatorial Games[END_REF]. In Milnor's universe, this relation can be defined as follows:

Definition 9. Let G and H be two games that are dicotic and nonzugzwang. We says that G dominates H, and denote it by

G ≥ H, if Rs(G -H) ≥ 0.
If a game has dominated options, then it can be simplified by simply removing them:

Theorem 10. Let G = G L |G R be a dicotic nonzugzwang game. Assume that there exist two options G 1 and G 2 in G L such that G l 2 ≥ G l 1 . Then G = G L \ G l 1 |G R . Similarly, if there exist G r 1 ≥ G r 2 in G R , then G = G L |G R \ G r 1 .
Proof. By symmetry, we just prove the first part of the theorem. Let G = G L \ G l 1 |G R . We first prove that G belongs to Milnor's Universe. Since G is dicotic and G has at least two left options, G is still dicotic. All the positions of G are positions of G except G itself. Thus to prove that G is nonzugzwang, we just need to prove that Ls(G ) ≥ Rs(G ). Since G l 2 dominates G l 1 , we have in particular Rs(G l 2 ) ≥ Rs(G l 1 ). Indeed, by Theorem 7,

Rs(G l 2 ) ≥ Rs(G l 2 -G l 1 ) + Rs(G l 1 ) and Rs(G l 2 -G l 1 ) ≥ 0. Thus max G l ∈G L (Rs(G l )) = max G l ∈G L \G l 1 (Rs(G l ))
(G l 1 -G l 2 ) = -Rs(G l 2 -G l 1 ) ≤ 0.
Thus Right has a strategy in second to insure non-positive score, which means that Ls(G -G ) ≤ 0.

Application to Bipartite Influence

In [DGP + 21], the authors proved that influence belongs to Milnor's universe. It also naturally holds for Bipartite Influence:

Theorem 11 ([DGP + 21]). For any instance G of Bipartite Influence, we have that G is dicotic and nonzugzwang.

Consequently, all the properties of Milnor's universe detailed above apply to Bipartite Influence. In addition, Example 12 below illustrates equivalent games in Bipartite Influence, as well as dominated options.

Example 12. Denote by S 5 the path of length 5, with the two extremities and the middle vertex colored black, and the two other vertices colored white. Denote also by S 2 the path of length two with one black and one white vertex. See Figure 3.

We will prove that 2S 5 = 2 + S 2 . According to Lemma 8, it is sufficient to prove Ls(2S 5 -(2 + S 2 )) = Rs(2S 5 -(2 + S 2 )) = 0. As S 2 = -S 2 and as numbers can be removed from a sum according to Theorem 7, we will prove Ls(2S 5 + S 2 ) = Rs(2S 5 + S 2 ) = 2. As a first step, when considering the Left options from 2S 5 + S 2 , playing an extremity of a S 5 (i.e. the vertex u in Figure 3) always leads to a position that is dominated by playing the middle of S 5 (i.e. the vertex v). Therefore, when computing Ls(2S 5 + S 2 ), one only take into account the option v (that yields 5 points) and the move on S 2 (that yields 2 points):

Ls(2S 5 + S 2 ) = max (5 + Rs(S 5 + S 2 ), 2 + Rs(2S 5 )) = max 5 + min -2 + Ls(S 5 ), -3 + Ls(S 2 + S 2 ) , 2 -3 + Ls(S 5 + S 2 ) = max 5 + min 3, -3 , -1 + max 5 + Rs(S 2 ), 2 + Rs(S 5 ) = max 2, -1 + max 3, 2 -3 + Ls(S 2 ) = max 2, -1 + max 3, -1 + 2 = 2. Rs(2S 5 + S 2 ) = min (-3 + Ls(S 5 + S 2 + S 2 ), -2 + Ls(2S 5 )) = min (-3 + Ls(S 5 ), -2 + 5 + Rs(S 5 )) = min (2, 3 -3 + Ls(S 2 )) = min (2, 2) = 2.
This proves that 2S 5 = 2 + S 2 . Moreover, as S 2 = -S 2 , we also have that 4S 5 = 2 + S 2 + 2 + S 2 = 4.

u v S 5 + S 5 = 2 + S 2
Figure 3: In Bipartite Influence, the game S 5 + S 5 is equivalent to the game 2 + S 2 .

Mean and Temperature

In this section, we develop the so-called concepts of mean and temperature of a game. These two notions have been introduced by Milnor and Hanner [START_REF] Milnor | Sums of positional games[END_REF][START_REF] Hanner | Mean play of sums of positional games[END_REF] for scoring games, and then have been formalized in the context of combinatorial game theory by Conway [START_REF] Conway | On number and games[END_REF]. In his book, Siegel [START_REF] Siegel | Combinatorial Game Theory[END_REF] gives formal definitions and proofs about them. In this section, we propose to do a similar work in the context of scoring combinatorial game theory.

Our results cover the results of Hanner and extend them by following the CGT formalism. In addition, some of them will be used in Section 6 to yield results about Bipartite Influence on segments. While playing on a (disjunctive) sum of games, general information can be deduced from the information on each term of the sum. As said previously, the Left score of a sum of games is not generally the sum of the Left scores. Nevertheless, Milnor and Hanner have introduced several tools to get some knowledge on sums of games. The most intuitive one is the mean of a game, which is very useful if the same game is repeated many times in a sum.

Definition 13 (Hanner [Han59]). The left (resp. right) mean of a game G, denoted m L (resp. m R ), is the score obtained in average by playing G a huge number of times if Left (resp. Right) starts, if it exists. More formally:

m L (G) = lim n→∞ Ls(nG) n m R (G) = lim n→∞ Rs(nG) n
where nG corresponds to the disjunctive sum G + • • • G with n terms. In Milnor's universe, both left and right means always exist:

Theorem 14 (Milnor [Mil53]). Let G be a dicotic nonzugzwang game. The values m L (G) and m R (G) exist and are equal.

The proof derives from the fact that asymptotically, the first move is made on a game that cannot significantly modify the rest of the sum. According to this result, in Milnor's universe, the mean value is thus unique and will be denoted m(G).

The mean of a game can be interpreted as what a player can expect from a game in a large sum. However, it gives no clue about which game of the sum it is strategic to play in. In order to answer to this question, Hanner [START_REF] Hanner | Mean play of sums of positional games[END_REF] introduced the so-called parameter σ(G). The more σ(G) is high, the more the game is said hot , meaning a player will want to play in it in priority. This parameter is similar to the temperature notion known in standard combinatorial games [START_REF] Siegel | Combinatorial Game Theory[END_REF]. Nevertheless, Hanner's definition of σ requires the use of an algorithm and is not very tractable. In what follows, we propose a formalization of this notion of temperature for scoring games, by adapting the formalism used in combinatorial games. Many results from Hanner [START_REF] Hanner | Mean play of sums of positional games[END_REF] about σ remain true within this formalism.

Definition 15. Let G = G L |G R be a dicotic nonzugzwang game. Given a real number t ≥ 0, we define G cooled by t, denoted by G t , as follows. If G is a real number k, put G t = k and t 0 = 0. Otherwise, let G t = G L t -t|G R t +t , t 0 = min {t ≥ 0|Ls( G t ) = Rs( G t )} and define G t = G t if t ≤ t 0 Ls(G t0 ) otherwise
The value t 0 is called the temperature of G and is denoted by σ(G).

If t is higher or equal to the temperature of G, the game G t is said to be frozen as it behaves as a number. If t is lower than the temperature of G, playing in G t can be understood as "playing in G but each move costs t to the player". This definition of temperature matches with the usual definition of temperature in combinatorial games without scores. In both cases, the temperature is defined as a minimum value, which may not exist.

Before proving that the temperature is well-defined, we give an example of the computation of the temperature.

Example 16. We compute in this example the temperature of the instance S 5 of Bipartite Influence defined in Example 12. The tree of S 5 is given in Figure 4 where the dominated moves corresponding to the extremities have been removed. We have S 5 = 5| -1|5 . Let t ≥ 0. By definition of a cooled game, we have

(S 5 ) t = 5 t -t| -1, -5 t + t .
Since numbers are already cooled, we have

(S 5 ) t = 5 -t| -1, -5 t + t .
The temperature of -1| -5 is 2. Hence, for t ≤ 2, we have that -1| -5 t + t = -1| -5 + 2t , and (S 5 ) t = 5 -t| -1| -5 + 2t which corresponds to the second case of Figure 4. For t ≥ 2, the game -1| -5 t is frozen and equals to -3. Thus (S 5 ) t = 5 -t| -3 + t which corresponds to the rightmost case of Figure 4. When t = 4, we have for the first time Ls( (S 5 ) t ) = Rs( (S 5 ) t ) and thus the temperature of (S 5 ) equals 4. After t = 4, (S 5 ) t is frozen and equals to 1.

-1 -5

Tree of S 5

5 -t -1 -5 + 2t Tree of S 5 cooled by t for t ∈ [0, 2] 5 -t -3 + t Tree of S 5 cooled by t for t ∈ [2, 4]
Figure 4: Tree of the game S 5 and the same game cooled by t for different values of t.

Proof of validity of Definition 15. We prove by induction on the length of G that for any t ≥ 0, G t exists and the two maps t → Rs(G t ) and t → Ls(G t ) are continuous.

If G is a number, its temperature is 0 and is well defined. Hence G t exists for all t ≥ 0 and the two score functions are constant.

Otherwise, G = G L |G R with G L and G R non empty since the game is dicotic. By induction, the temperature of all the games in G L and G R are well defined. Thus the games in G L t and G R t exist for all t ≥ 0 and the corresponding score functions are continuous.

Therefore, the functions t → Ls( G t ) and t → Rs( G t ) exist and are continuous as maximum and minimum of (a finite number of) continuous functions.

Consider now the function

f : t → Ls( G t ) -Rs( G t ) defined on R + . The function f is well defined, continuous and f (t) = max G l ∈G L Rs(G l t ) -min G r ∈G R Ls(G r t ) -2t.
We have

f (0) = Ls(G) -Rs(G) ≥ 0 as G is nonzugzwang. Furthermore, lim t→∞ f (t) = -∞ since the functions t → Rs(G l t
) and t → Ls(G r t ) are in a finite number and, by definition, constant for t large enough. Since f is continuous, there exists a minimum t 0 such that f (t 0 ) = 0 which guarantees the existence of the temperature and the game G t .

Moreover, for any 0 ≤ t ≤ t 0 , Ls(G t ) and Rs(G t ) are continuous as minimum and maximum of continuous functions; for t ≥ t 0 , they are constant so continuous. Finally, Ls(G t ) and Rs(G t ) are continuous in t 0 since Ls(G t0 ) = Rs(G t0 ).

With a similar induction, one can prove the following corollary.

Corollary 17. Let G be dicotic nonzugzwang game. Then for any t ≥ 0, G t is a dicotic nonzugzwang game. The function t → Ls(G t ) and t → Ls( G t ) are decreasing functions. Symmetrically, t → Rs(G t ) and t → Rs( G t ) are increasing functions.

In particular

, if t ≥ σ(G), we have Ls( G t ) ≤ G σ(G) ≤ Rs( G t ).
A natural question is about how a cooled game is far from the original game, in terms of Left and Right scores. The following property yields an answer.

Proposition 18. Let G be a dicotic nonzugzwang game and let t ≥ 0. We have

0 ≤ Ls(G) -Ls(G t ) ≤ t and 0 ≥ Rs(G) -Rs(G t ) ≥ -t Proof. By considering -G instead of G, it suffices to prove the result for Ls since Rs(-G) = -Ls(G) and Rs(-G t ) = -Ls(G t ). By Corollary 17, t → Ls(G t ) is decreasing, which implies that Ls(G) -Ls(G t ) ≥ 0. It remains to prove that Ls(G) -Ls(G t ) ≤ t
If G is a number, we have for any t ≥ 0, G t = G, which implies the result. Otherwise, consider the case 0 ≤ t ≤ σ(G). Let G l be an optimal move for Left in G, we have

Ls(G) = Rs(G l ). Since Ls(G t ) = max l ∈L (Rs(G l t ) -t), we have in particular Ls(G t ) ≥ Rs(G l t ) -t. Thus, Ls(G) -Ls(G t ) ≤ Rs(G l ) -Rs(G l t ) + t. Since t → Rs(G l t ) is increasing, Rs(G l ) -Rs(G l t ) ≤ 0 leading to Ls(G) -Ls(G t ) ≤ t.
Consider now the case t > σ(G), we have

Ls(G) -Ls(G t ) = Ls(G) -Ls(G σ(G) )
. By the last inequality above, we have t > σ(G) ≥ Ls(G) -Ls(G t ).

As said before, this definition of a cooled game can be understood as a game where moving has a cost. Hence, the temperature is defined as the highest cost that can be set such that the game remains nonzugzwang. Since the temperature has been defined to handle sums of games, we state preliminary results about the sum of two cooled games, starting by the case where one the games is a number.

Lemma 19. Let G be a dicotic nonzugzwang game. Let s be a number. Then

(G + s) t = G t + s. In particular, σ(G + s) = σ(G).
Proof. The result is prove by induction on the length of G. If G is a number, so is G + s and we have (G + s) t = G + s = G t + s.

Otherwise:

(G + s) t = (G L + s) t -t|(G R + s) t + t = G L t + s -t|G R t + s + t by induction = G L -t|G R + t + s = G t + s. In particular, Ls( (G + s) t ) = Ls( G t ) + s and Rs( (G + s) t ) = Rs( G t ) + s. This implies that σ(G + s) = σ(G) and that (G + s) t = G t + s.
Despite the above result, it is not clear in our opinion that the cooling function is a homomorphism for any two scoring games. If this result is true in the CGT context, a direct adaptation in Milnor's universe is not guaranteed, as G t can be outside this universe. However, if the cooled games are not equivalent, the result below show that it is true for the scores. In addition, as for CGT, we also show that the temperature is a submaximal function.

Theorem 20. Let G and H be two dicotic nonzugzwang games. We have Ls(

(G + H) t ) = Ls(G t + H t ) and Rs((G+H) t ) = Rs(G t +H t ). Moreover, σ(G+H) ≤ max(σ(G), σ(H)) and if σ(H) < σ(G), then σ(G+H) = σ(G).
In particular, we have:

(G + H) σ(G+H) = G σ(G) + H σ(H)
Proof. We prove the proposition by induction on the length of G + H.

If G or H is a number, the proposition is a direct consequence of Lemma 19.

From now on, we assume that both G and H are not numbers, and, without loss of generality, we assume that σ(G) ≥ σ(H). We first prove that Ls(

(G + H) t ) = Ls(G t + H t ) for any t ≤ σ(G). Let t ≥ 0. Ls( (G + H) t ) = max G l ∈G L ,H l ∈H L {Rs((G l + H) t -t), Rs((G + H l ) t -t)} = max G l ∈G L ,H l ∈H L {Rs((G l + H) t ), Rs((G + H l ) t )} -t = max G l ∈G L ,H l ∈H L {Rs(G l t + H t ), Rs(G t + H l t )} -t by induction = max G l ∈G L ,H l ∈H L {Rs(G l t + H t -t), Rs(G t + H l t -t)}.
Assume first that t ≤ σ(H), then

G t + H t = G L t -t|G R t + t + H L t -t|H R t + t Ls(G t + H t ) = max G l ∈G L ,H l ∈H L {Rs(G l t + H t -t), Rs(G t + H l t -t)} and Ls( (G + H) t ) = Ls(G t + H t ). Assume now that σ(H) ≤ t ≤ σ(G).
In particular, H t is a number equal to H σ(H) . We prove that there is an option in G L t + H t -t that has a Right Score greater all the options in

G t + H L t -t. Let G l ∈ G L such that Ls(G t ) = Rs(G l t -t) (G l exists since G t is not a number). Let any H l ∈ H L . Since t ≥ σ(H) and since t → Ls( H t ) is, by Corollary 17, a decreasing function, we have Rs(H l t -t) ≤ Ls( H t ) ≤ Ls( H σ(H) ) = H σ(H) .
Therefore, we have the following inequalities:

Rs(G t + H l t -t) ≤ Ls(G t ) + Rs(H l t -t) since all the components are in Milnor's universe (see 7 ≤ Rs(G l t -t) + H σ(H) ≤ Rs(G l t -t + H t ) since H t = H σ(H)
Thus, the Left score of (G + H) t is computed only on the options G L + H t -t and thus:

Ls( (G + H) t ) = max G l ∈G L {Rs(G l t + H t -t} = max G l ∈G L {Rs(G l t -t)} + H σ(H) = Ls(G t ) + H σ(H) since t ≤ σ(G) = Ls(G t + H t ).
We have proved that if t ≤ σ(G), then Ls( (G + H) t ) = Ls(G t + H t ). In a similar way, one can prove that

Rs( (G + H) t ) = Rs(G t + H t ).
The two functions t → Ls( (G + H) t ) and t → Rs( (G + H) t ) are respectively decreasing and increasing functions. They are both equal to G σ(G) + H σ(H) in t = σ(G). Thus the first time they are equal is before (or in) σ(G) which means precisely that σ(G + H) ≤ σ(G). Furthermore, we have:

• for 0 ≤ t < σ(G + H), Ls((G + H) t ) = Ls( (G + H) t ) = Ls(G t + H t ) and Rs((G + H) t ) = Rs( (G + H) t ) = Rs(G t + H t ); • for σ(G + H) ≤ t ≤ σ(G), t → Ls( (G + H) t
) and t → Rs( (G + H) t ) are constant and both equal to the value in σ(G + H) and σ(G). In particular,

Ls((G + H) t ) = Ls( (G + H) t ) = Ls(G t + H t ) = (G + H) σ(G)+σ(H) = G σ(G) + H σ(H) , Rs((G + H) t ) = Rs( (G + H) t ) = Rs(G t + H t ) = (G + H) σ(G)+σ(H) = G σ(G) + H σ(H) . If σ(H) < σ(G), then for any σ(H) < t < σ(G), Ls( (G + H) t ) = Ls(G t ) + H σ(H) > Rs(G t ) + H σ(H) = Rs( (G + H) t ),
and therefore

σ(G + H) = σ(G). Finally, for t ≤ σ(G + H), Ls((G + H) t ) = (G + H) σ(G)+σ(H) and Ls(G t + H t ) = G σ(G) + H σ(H) .
From what precedes, the two values are equal, which concludes the proof.

The score after having cooled a game is defined as the score obtained after having increased the cost of the plays. At the temperature, one can also consider it as the score on which Left and Right agree to play the game regardless who starts. In this sense, this definition is close to the mean of the game. As first announced in [START_REF] Hanner | Mean play of sums of positional games[END_REF] in another format, the following result formalizes the connection between the two notions.

Proposition 21. Let G be a nonzugzwang dicotic game. We have G σ(G) = m(G).

Proof. We denote by x the number G σ(G) . We prove that m(G) = x By Theorem 20, σ(nG) ≤ σ(G) and (nG) σ(nG) = nG σ(G) = nx. In particular, for t large enough, (nG) t = nx.

Therefore = m(G), and t n → n→∞ 0, we have x = m(G).

Next theorem expresses in which sense a small temperature means that playing first is not very important.

Theorem 22. Let G be a nonzugzwang dicotic game, we have

m(G) -σ(G) ≤ Rs(G) ≤ m(G) ≤ Ls(G) ≤ m(G) + σ(G).
Proof. As G is supposed to be dicotic and nonzugzwang, by symmetry, it suffices to prove m(G) ≤ Ls(G) ≤ m(G) + σ(G). Indeed, by considering -G instead of G, we have:

m(-G) ≤ Ls(-G) ≤ m(-G) + σ(-G) ⇔ -m(G) ≤ -Rs(G) ≤ -m(G) + σ(G) as σ(G) = σ(-G) and m(G) = -m(G) ⇔ m(G) ≥ Rs(G) ≥ m(G) -σ(G) By Corollary 17, the function t → Ls(G t ) is decreasing. Since G 0 = G and Ls(G t ) = m(G) for t large enough, we have Ls(G) ≥ m(G). By Proposition 18, Ls(G) -Ls(G σ(G) ) ≤ σ(G) which is equivalent to Ls(G) ≤ m(G) + σ(G).
Theorem 22 can be applied to sum of games to bound the overall score according to the mean and the temperature of each term of the sum. The following corollary confirms Theorem 1 of [START_REF] Hanner | Mean play of sums of positional games[END_REF] with our definition of the temperature. We will use this result for Bipartite Influence on sum of segments in Section 6.

Corollary 23. Let G = G 1 + • • • + G n be a sum of dicotic nonzugzwang games. Let m i be the mean of G i and σ = max 1≤i≤n σ(G i ). We have n i=0 m i -σ ≤ Rs(G) ≤ n i=0 m i ≤ Ls(G) ≤ n i=0 m i + σ.
Proof. This result is straightforward as we know that m(G) = n i=1 m(G i ) (as a sum of limits) and σ(G) ≤ max 1≤i≤n σ(G i ) (from Theorem 20).

General results on Bipartite Influence

The current section gives general results about Bipartite Influence that will be useful in the rest of the paper. We first recall a property introduced in [DGP + 21] about the so-called relevant graphs. In the context of Bipartite Influence, the vertices from a graph G that can be directly removed by playing a vertex v are v itself, its neighbors and the isolated vertices that possibly appeared (with the same color as v). We denote by Rmv(G, v) this set of removed vertices. Consequently, the score functions can also be expressed as follows:

Ls(G) = max x∈B |Rmv(G, x)| + Rs(G \ Rmv(G, x))
and

Rs(G) = min y∈W -|Rmv(G, y)| + Ls(G \ Rmv(G, y)) .

Included moves

In Influence, it has been proved that a move included in another is dominated by it [DGP + 21]. More formally, we have the following theorem that is a restatement of Corollary 13 in [DGP + 21].

Theorem 24 ([DGP + 21]). Let G = (B ∪ W, E) be a bipartite graph and u, v two vertices of the same colour such that Rmv(G, u) ⊆ Rmv(G, v). Then, the option of playing v dominates the option of playins u. Otherwise said, playing v is always at least as good as playing u.

Removing and adding vertices

A way to obtain bounds on the score is to consider that some vertices are automatically given to the opponent, in order to simplify the structure of the graph without those vertices. The following result explains how the score may vary when sets of vertices of the same color are removed.

Theorem 25. Let G = (B ∪ W, E) be a bipartite graph. Let B 0 ⊆ B and W 0 ⊆ W . We have:

Ls(G) ≤ Ls(G\W 0 ) + |W 0 | (1)
Rs(G) ≥ Rs(G\B 0 ) -|B 0 | (2) Ls(G) ≥ Ls(G\B 0 ) -|B 0 | (3) Rs(G) ≤ Rs(G\W 0 ) + |W 0 |. (4)
Roughly speaking, it can be explained by the fact that removing a set of white vertices and giving them to Left may prevent Right from doing some good moves but does not prevent Left to apply the same strategy.

Proof. By symmetry, it suffices to prove (1) and (4). We do this by induction on |V |. The result is trivially true if W 0 is empty, if |V | = 1, or if the first player has no move. Assume it is true for any graph with at most n ≥ 1 vertices and where the first player has a move.

Let G = (B ∪ W, E) be a graph with n + 1 vertices and let W 0 ⊂ W be a set of white vertices. The main idea of the proof is that by applying the optimal strategy existing in G on the graph with the removed vertices, the player scores at least the same number of points.

We first prove (1) : let v ∈ B be a vertex played by Left in an optimal move in G. Denote by W 1 the white vertices of W 0 removed by playing v. Namely, we have W 1 = W 0 ∩ Rmv(G, v), and define W 2 as the other white vertices of W 0 , i.e. W 2 = W 0 \W 1 . Consider now a strategy for Left that starts by playing v in G\W 0 . By definition of Ls, we have :

Ls(G\W 0 ) ≥ Rs (G\W 0 )\Rmv(G\W 0 , v) + Rmv(G\W 0 , v) Since W 1 = W 0 ∩ Rmv(G, v) ⊂ Rmv(G, v), we have W 0 ∪ Rmv(G, v) = W 1 ∪ W 2 ∪ Rmv(G, v) = W 2 ∪ Rmv(G, v).
Therefore, we have:

Ls(G\W 0 ) + |W 0 | ≥ |Rmv(G\W 0 , v)| + Rs (G\W 2 )\Rmv(G, v) + |W 1 | + |W 2 |
Now, by induction we know that Rs(G\Rmv(G, v)) ≤ Rs((G\Rmv(G, v))\W 2 ) + |W 2 |. Thus, by applying this equality to the previous one, we get Ls(G\W

0 ) + |W 0 | ≥ |Rmv(G\W 0 , v)| + |W 1 | + Rs(G\Rmv(G, v). Finally, by the triangular inequality |Rmv(G\W 0 , v)| + |W 1 | ≤ |Rmv(G\W 0 , v) ∪ W 1 |, and as Rmv(G\W 0 , v) ∪ W 1 = Rmv(G, v), we obtain Ls(G\W 0 ) + |W 0 | ≥ |Rmv(G, v)| + Rs(G\Rmv(G, v)).
Finally, as the move v was supposed optimal in G, recall that Ls(G) = |Rmv(G, v)| + Rs(G\Rmv(G, v)), yielding to the desired result. Now, we prove (4) : Let v ∈ W be a vertex played by Right in an optimal move in G\W 0 . By definition, we have

Rs(G\W 0 ) = -|Rmv(G\W 0 , v)| + Ls(G\W 0 \Rmv(G\W 0 , v))
Denote by W 1 the white vertices of W 0 taken by playing v, i.e. W 1 = W 0 ∩ Rmv(G, v), and by W 2 the other white vertices of W 0 , i.e. W 2 = W 0 \W 1 .

We have Ls(G\W 0 \Rmv(G\W 0 , v)) = Ls(G\W 2 \Rmv(G, v)). Now, by induction hypothesis and by applying (1) to Ls(G\W 2 \Rmv(G, v)), we have

Ls(G\W 2 \Rmv(G, v)) ≥ Ls(G\Rmv(G, v)) -|W 2 | As Rmv(G\W 0 , v) ⊂ Rmv(G, v), we have -|Rmv(G\W 0 , v)| ≥ -|Rmv(G, v)|.

Putting together the previous inequalities we get Rs(G\W

0 ) ≥ -|Rmv(G, v)| + Ls(G\Rmv(G, v)) -|W 2 |. Since -|Rmv(G, v)|+Ls(G\Rmv(G, v)) is the score obtained by playing v in G, we have Rs(G\W 0 ) ≥ Rs(G)-|W 2 |. Finally, as W 2 ⊂ W 0 , we obtain Rs(G\W 0 ) ≥ Rs(G) -|W 0 |.
Example 26. The graph G of Figure 5 is the sum of a graph and its negative with only two additional black vertices (v 7 and v 8 ). To evaluate the score of this sum, Left can give these two vertices to Right, and know that on the remaining graph, the score will be 0 (as being the sum of a graph with its negative). Therefore, by applying (2) and (3) of the above theorem, we deduce that Ls(G) ≥ -2 and Rs(G) ≥ -2.

v 1 v 2 v 3 v 4 v 5 v 6 v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8

Twins

Two vertices are called twins if they have the same color and the same neighborhood. In Bipartite Influence, twin vertices are necessarily removed together.

Lemma 27. In Bipartite Influence, if a move removes a vertex v of the graph, then this move also removes all the vertices that are twins of v.

Proof. Let G = (B ∪ W, E) be a bipartite graph and let a and a be two twin vertices of G. Without loss of generality, suppose that a and a are white. Consider a move that removes the vertex a.

If the move is played from a white vertex w, it takes a if and only if it takes all its neighborhood. Thus N (a) ⊆ N (w). But, as N (a) = N (a ), we also have N (a ) ⊆ N (w). Therefore, a and a have an empty neighborhood after this move and are won by white.

If the move that removes a is played on a black vertex b, then a must be in the neighborhood of b. Therefore, since a and a have the same neighborhood, a is also in the neighborhood of b, which concludes the proof.

Pspace-completeness

In this section, we prove that computing the Left score of an instance of Bipartite Influence is Pspace-complete.

Bipartite Influence

Instance: A bipartite graph G = (B ∪ W, E), an integer k ∈ N Question: Is it true that Ls(G) ≥ k? Theorem 28. Bipartite Influence is Pspace-complete.

Proof. First, Bipartite Influence is in Pspace since a game ends after at most |B ∪ W | moves. To prove the completeness, we do a reduction from the game POS CNF. An instance of POS CNF is a CNF formula ϕ over a set of variables X = {X 1 , . . . , X n } where all the variables are positive. Alice and Bob alternately choose a variable that has not been chosen yet. Variables chosen by Alice are set to true, those chosen by Bob are set to false. Alice wins if and only if ϕ is true at the end. The related decision problem is the following one and has been proved to be Pspace-complete by Schaefer in 1978 [START_REF] Schaefer | On the complexity of some two-person perfect-information games[END_REF].

Pos Cnf

Instance: A set of variable X and a positive CNF formula ϕ Question: Does Alice win the game Pos Cnf played on (X, ϕ) playing first? Let (X, ϕ) be an instance of Pos Cnf. Without loss of generality, by adding a useless variable, one can assume

that n = |X| is even. Denote ϕ = m j=1 C j and, for 1 ≤ j ≤ m, denote C j = nj i=1 X j
i where n j is the number of variables in C j . We construct an instance of Bipartite Influence G = (B ∪ W, E) as follows:

• For each clause C j , 1 ≤ j ≤ m, we add a white vertex c j .

• For each variable X i , 1 ≤ i ≤ n, we add a white and a black vertex x i w , x i b , and m + 2n -1 black vertices v i 1 , . . . v i m+2n-1 . • We finally add all the edges (x i w , x i b ) and (x i w , v i k ) for 1 ≤ i ≤ n and 1 ≤ k ≤ m + 2n; and the edges (x i b , c j ) whenever X i ∈ C j .

See Figure 6 for an illustration of the construction for the formula ϕ = (X 1 ∨X 2 )∧(X 2 ∨X 3 )∧(X 3 ∨X 4 )∧(X 4 ∨X 1 ). The big black vertices represent the m + 2n -1 = 11 black leaves attached to each vertex x i w . Before proving the reduction, we prove that there are optimal strategies for Left or Right in G consisting in playing only vertices

x i w or x i b (for 1 ≤ i ≤ n). For 1 ≤ i ≤ n, let B i be the set of m + 2n -1 black vertices v i k .
We call such set a bag. All these vertices are twins and by Lemma 27 will be removed at the same time, together with the vertex x w i , scoring at least 2n + m points. However, a move can remove at most one bag at a time, and actually any move except the moves on vertices c j removes a bag. As a consequence, if at some point Right chooses to play on a vertex c j whereas a bag is still present, Left will manage to take n/2 + 1 bags and will remove at least n 2 + 1 (2n + m) = n 2 + nm 2 + 2n + m vertices. On the contrary, if Right always takes a bag when one is left, Left can take at most n/2 bags, plus maybe the n + m remaining vertices, removing at most n 2 (2n + m) + n + m = n 2 + nm 2 + n + m vertices. Thus, until all the bags are removed, Right must always choose to play on a vertex x w i . When the bag B i is removed (by Left or Right), the only other vertices that can be removed in the same move are x w i , x b i and maybe some clause vertices, but no vertices of other variables can be removed. Thus, if Left would have play on a vertex v i k in a bag, the vertex x b i is still present in the graph. Since Rmv(G, v i k , ⊂)Rmv(G, x i b ,) , by Theorem 24, playing on x b i is always better. Finally, we can suppose that both Left and Right plays on vertices x b i and x r i until all the bags are removed. But then the graph is empty since only clauses variables could remain and they form an independent set.

Note that the final Left score is exactly the difference between the number of vertices c j removed by Left (by taking one adjacent vertex x b i of c j ) and thus isolated by Right (by removing all the black vertices x b i adjacent to c j ).

Assume Alice has a winning strategy in Pos Cnf on (X, ϕ). Then Left follows the same strategy than Alice: when Alice chooses variable X i , Left removes vertex x b i . If Right answers vertex x w i , we assume that Bob plays variable X i and so on. At the end, Left will have take one neighbour of each clause vertex and thus will have removed the m clause vertices. At the end, Ls(G) ≥ m.

Similarly, if Left has a strategy to have Ls(G) ≥ m, it means that she can choose vertices x b i in such a way that she will touch all the clause variables. If Alice follows the same strategy, ϕ will be true at the end of the game.

Remark 29. In Bipartite Influence, the question was to know whether Ls(G) ≥ k. Since free points can be given to a player by adding isolated vertices in the graph, the problem is still Pspace-complete with k = 0 by adding k white vertices if k > 0 or -k black vertices if k < 0. Thus, determining which player has a winning strategy is also Pspace-complete.

of φ = (X 1 ∨ X 2 ) ∧ (X 2 ∨ X 3 ) ∧ (X 3 ∨ X 4 ) ∧ (X 4 ∨ X 1
) to Bipartite Influence. Big black vertices represent 11 pendant vertices.

Corollary 30. influence is Pspace-complete, even for bipartite graphs.

A sufficient condition to have a draw

Identifying draw games, i.e. games that are equivalent to 0, is essential in the study of a game in Milnor's universe since they can be removed from any sum. However, as seen in the previous section, determining in general if a game is a draw is hard (since it is already hard to determine if Ls(G) = 0). In this section, we give a sufficient condition to have a draw when the graph has some symmetries and we apply it to hypercubes, cylinders and torus.

Sufficient condition

An automorphism ϕ of a graph G is a function from V (G) to V (G) that preserves edges, i.e. if (u, v) ∈ E(G) if and only if (ϕ(u), ϕ(v)) ∈ E(G). It is said to be involutive if ϕ(ϕ(u)) = u for all u ∈ V (G). We denote the usual distance (i.e the length of the shortest path) between two vertices u and v by d(u, v). If u and v are not in the same connected component, we let d(u, v) = ∞.

Definition 31. Let G = (B ∪ W, E) be a bipartite graph. An automorphism ϕ of G is a BW-automorphism if it is involutive, exchanging the colours of the vertices, and if for any v ∈ V (G), d(v, ϕ(v)) ≥ 3.

Theorem 32. Let G = (B ∪ W, E) be a bipartite graph that has a BW-automorphism, then G = 0.

Proof. Let G = (B ∪ W, E) a bipartite graph, and let ϕ be a BW-automorphism of G. To prove that G = 0, we just need to prove that LS(G) = RS(G) = 0. By symmetry of G and ϕ(G), we actually just need to prove that Ls(G) ≤ 0, that is to prove that the second player can achieve to take as many vertices as the second player. The strategy of the second player will consist in always playing the image by ϕ of the vertex played by the first player.

To prove that this strategy works, it is sufficient to prove that Rmv(G, ϕ(u)) = ϕ(Rmv(G, u)) for all u ∈ G and that Rmv(G, ϕ(u)) ∩ Rmv(G, u) = ∅. Indeed, if these two conditions are satisfied, then the second player can always remove the image by ϕ of the moved played by the first player and will take the same number of vertices. Then after two moves, the graph will still have a BW-automorphism and the second player can repeat his strategy.

Let u ∈ V and v ∈ Rmv(G, ϕ(u)). If v is a neighbour of ϕ(u), we have : If v is not a neighbour of ϕ(u), v is isolated by playing ϕ(u), i.e. each neighbour w of v is also a neighbour of ϕ(u). As ϕ preserves edges, the neighbours of ϕ(v) are the images by ϕ of the neighbours of v. Therefore, they are all removed by playing ϕ(ϕ(u)) = u. This proves that ϕ(v) is isolated by playing u, and thus is in Rmv(G, u).

(v, ϕ(u)) ∈ E ⇔ (ϕ(v), ϕ(ϕ(u))) ∈ E as ϕ respects edges ⇔ (ϕ(v), u) ∈ E as ϕ is involutive.
In both cases, ϕ(v) ∈ Rmv(G, u) and thus v = ϕ(ϕ(v) is in ϕ(Rmv(G, u)). This proves Rmv(G, ϕ(u)) ⊆ ϕ(Rmv(G, u)) for all u ∈ V .

To prove the other direction, we have the following equivalences:

∀u ∈ V, ϕ(Rmv(G, ϕ(u))) ⊆ ϕ(ϕ(Rmv(G, u))) ⇔∀u ∈ V, ϕ(Rmv(G, ϕ(u))) ⊆ Rmv(G, u) as ϕ is involutive ⇔∀v ∈ V, ϕ(Rmv(G, ϕ(ϕ(v)))) ⊆ Rmv(G, ϕ(v)) as ϕ is a bijection, by taking v = ϕ(u) ⇔∀v ∈ V, ϕ(Rmv(G, v)) ⊆ Rmv(G, ϕ(v)) as ϕ is involutive.
Finally, we have Rmv(G, ϕ(u)) = ϕ(Rmv(G, u)) for all u ∈ V . A move in Bipartite Influence removes vertices at distance at most 2, and the vertices at distance 2 are removed only if they are made isolated. Assume by contradiction there exists v ∈ Rmv(G, ϕ(u)) ∩ Rmv(G, u). Then d(v, u) ≤ 2 and d(v, ϕ(u)) ≤ 2. Since d(u, ϕ(u)) ≥ 3, we actually have d(u, ϕ(u)) = 3 (since u and ϕ(u) does not have the same colour, and without loss of generality, we can assume that d(v, u) = 2 and d(v, ϕ(u)) = 1. But then v cannot be isolated when playing u since it will still be connected to ϕ(u). Thus Rmv(G, ϕ(u)) ∩ Rmv(G, u) = ∅.

Applications

In this subsection, we apply Theorem 32 to hypercubes, torus and cylinders.

Definition 33 (Hypercube). We denote by H n be the n-dimensional hypercube. The set of vertices of H n is {0, 1} n and two vertices are adjacent if and only if they differ on exactly one digit. We set black vertices to be the vertices with an odd number of nonzero digits. See Figure 7 for a representation of H 4 .

Proposition 34. For n ≥ 3, H n = 0.

Proof. By Theorem 32, we just need to find a BW-automorphism. Let n ≥ 3 and

ϕ : {0, 1} n → {0, 1} n (ε 1 , . . . , ε n ) → (1 -ε 1 , 1 -ε 2 , 1 -ε 3 , ε 4 , . . . , ε n ) .
The automorphism ϕ is involutive and d(u, ϕ(u)) = 3 for any vertex u, which implies that ϕ exchanges black and white vertices and. Thus ϕ is a BW-automorphism and H n = 0.

Definition 35 (Cylinder). Let n, m be two positive integers with n even. We denote C n,m the cylinder defined as follows. The n × m vertices of C n,m are denoted by v i,j with 1 ≤ i ≤ n and 1 ≤ j ≤ m. Vertices v i,j and v i ,j are adjacent if and only if i = i and j = j ± 1 or j = j and i = i ± 1 mod n. We set black vertices to be the vertices with i + j = 0 mod 2.

Definition 36 (Torus). Let n, m two even positive integers. We denote by T n,m the torus defined as follows. The n × m vertices of T n,m are denoted by v i,j with 1 ≤ i ≤ n and 1 ≤ j ≤ m. Vertices v i,j and v i ,j are adjacent if and only if i = i and j = j ± 1 mod m or j = j and i = i ± 1 mod n. We set black vertices to be the vertices with i + j = 0 mod 2. If n ≥ 4 and m is even or if n = 4k + 2 for a positive integer k, we have C n,m = 0.

Proof. By symmetry of the torus, we can assume that n ≥ 4. Assume first that n = 2 mod 4. Consider the following morphism on the vertices of C n,m or T n,m :

ϕ : v i,j → v ((i+ n 2 ) mod n),j)
. It is sending vertices to the symmetric vertex of that is in the same cycle. Thus ϕ is involutive. Since n = 2 mod 4, the colour of u and ϕ(u) are opposite. Since n ≥ 6, they are distance at least 3. Thus ϕ is a BW-automorphism and C n,m = T n,m = 0.

Assume now that n = 0 mod 4 and that both n and m are even. Consider now the morphism

ψ : v i,j → v ((i+ n
2 ) mod n),(m+1-j) . One can check that ψ is an automorphism. Furthermore,

ψ(ψ(v i,j )) = ψ(v ((i+ n 2 ) mod n),(m+1-j) ) = v ((i+ n 2 + n 2 ) mod n),(m+1-(m+1-j)) = v i,j
and thus ψ is involutive. Since i + j and i + n 2 + m + 1 -j have not the same parity, ψ is exchanging black and white vertices. Finally, d(v i,j , ψ(v i,j )) ≥ n 2 + 1 ≥ 3. Indeed, to go from v i,j to ψ(v i,j ) one needs already n/2 steps to go to the same line, and at least one more step to go to the same column since m + 1 -j = j (m is even).

Thus ψ is a BW-automorphism and by Theorem 32 we can conclude that T n,m = C n,m = 0.

Limits of Theorem 32

Despite Theorem 32 gives a good condition to find some draw graphs, we prove now that deciding if a BWautomorphism exists in a graph is not solvable in polynomial time, unless the graph isomorphism problem is.

Definition 38 (Graph Isomorphism problem). We recall here that given two graphs G 1 and G 2 , determining if G 1 and G 2 are isomorphic is not known to be solvable in polynomial time. Problems that are known to be at least as difficult as this problems are called GI-Hard problems.

Note that the graph isomorphism problem is known to be computable in quasi-polynomial time [START_REF] Babai | Graph isomorphism in quasipolynomial time[END_REF].

Theorem 39. Let G = (B ∪ W, E) be a bipartite graph, deciding if G admits a BW-automorphism is GI-Hard.

Proof. We give a reduction from the graph isomorphism problem. Let

G 1 = (V 1 , E 2 ), G 2 = (V 2 , E
2 ) be two graphs.

We construct an instance H = (B ∪ W, E) of Bipartite Influence as follows. The graph H will be divided into two bipartite graphs, H 1 and H 2 . Let i ∈ {1, 2}. The graph H i is the incidence graph of G i where a leaf is added to each vertex of H i that corresponds to a vertex of G i . More precisely, the vertex set of

H i is V i ∪ E i ∪ V i
where V i is a copy of V i . Two vertices u and v are adjacent in H i if and only if one of the following items is satisfied

• u ∈ V i and v is the copy of u in V i , or • u ∈ V i , v ∈ E i and v is an edge incident to u in G i .
The graph H i is bipartite with parts V i and E i ∪ V i . Note that the only vertices of degree 1 are the vertices in

V i . Then H = H 1 ∪ H 2 . We choose as set of black vertices the set B = V 1 ∪ E 2 ∪ V 2 and as set of white vertices the set W = V 2 ∪ E 1 ∪ V 1 .
We now prove that G 1 and G 2 are isomorphic if and only if there exists a BW-automorphism of H. First suppose that G 1 and G 2 are isomorphic. Let φ be an isomorphism from G 1 to G 2 . We construct a BWautomorphism ϕ of H as follows. Vertices of V 1 and V 2 are exchanged as in φ. Since φ preserves edges, a vertex of H 1 corresponding to an edge (u, v) of G 1 is send to the vertex of H 2 corresponding to the edge (φ(u), φ(v)) of G 2 , and conversely for the vertices of H 2 corresponding to the edges of G 2 . Finally, a vertex of V 1 (respectively V 2 ) that is a copy of a vertex u of V 1 (resp. V 2 ) is send to the copy of φ(u) in V 2 (resp. to the copy of φ -1 (u) in V 1 ). Clearly, ϕ is an automorphism that is involutive, is inversing the colour of the vertices, and since it is sending a vertex to a vertex not in the same component, the distance between u and ϕ(u) is infinite. Thus, ϕ is a BW-automorphism of H.

Assume now that a BW-automorphism ϕ of H exists. Since V 1 and V 2 are the only vertices of degree 1 of H 1 and H 2 respectively, they must be stable by ϕ. To respect the exchange of colours, ϕ must induced a bijection between V 1 and V 2 . Indeed, the set V 1 corresponds to the unique neighbours of the vertices of V 1 and thus must be sent to the unique neighbours of the vertices of V 2 that correspond to the set V 2 . Finally, the vertices of E 1 can only be sent to the vertices of E 2 .

Let φ : V 1 → V 2 be the restriction of ϕ to V 1 . Then φ is an isomorphism of G 1 . Indeed, ϕ is involutive so φ is a bijection. Consider u and v to neighbours in G 1 and e = (u, v). Then ϕ(e) must be incident to φ(u) and φ(v) and thus φ(u) and φ(v) are adjacent in G 2 . The reverse can be proved in the same way.

To conclude, G admits a BW-automorphism if and only if G 1 and G 2 are isomorphic, which proves that determining whether a bipartite graph admits a BW-automorphism or not is GI-Hard.

Segments

State of the art

Recall that segments, as defined in [DGP + 21], correspond to instances of Bipartite Influence played on paths. Despite their simple graph structure, their resolution is not obvious. When playing on a segment, the graph may be split into two smaller segments. This led the study to consider the class of disjunctive sum of segments (also corresponding to unions of paths), in order to play on a family that is closed by a move operation.

Definition 41. The class C represents the class of all bipartite graphs that are finite disjunctive sums of elements in C segment .

A segment of n vertices starting with a black (resp. white) vertex will be denoted by S n (resp. S -n ). See Figure 9 for an example. On the class C without isolated vertex (as such vertices can be immediately removed from any instance), remark that a move removes between 2 and 5 vertices. A move that removes k vertices will be called a k-move. 4-moves are the moves made by playing the vertex at distance 2 from the extremity of a segment. 5-moves can only be made by Right on S -5 and by Left on S 5 , by playing the middle vertex.

By definition of the negative of a game, remark also that S -n = -S n for all n ∈ N. Moreover, by symmetry, we have S 2n = S -2n .

On the class C segment , Duchêne et al. [DGP + 21] showed that the first player always wins. More precisely, the scores are bounded according to the following result:

Theorem 42 (Duchêne et al [DGP + 21]). Let S n ∈ C segment . We have: -5 ≤ Rs(S n ) < 0 < Ls(S n ) ≤ 5
The main idea of the proof of this theorem is that, by playing in the middle vertex of a segment, the first player can create two segments having a number of vertices that is very close. Consequently, this player can ensure to lose at most two vertices in the remaining game. As his first move scores three vertices, it ensures a win for the first player.

In addition to this result, there are certain values of n for which the exact value of Ls(S n ) is known (e.g. when n ≡ 1 mod 4). Yet, for the majority of them, the exact value of the score is an open problem. In the study Such a periodicity of the score would directly induce a polynomial time algorithm to solve the game on segments.

Concerning sums of segments, Theorem 42 does not hold when extended to the class C. The best bounds that are currently known are given by the result below. • -4 ≤ Rs(G) ≤ 0 ≤ Ls(G) ≤ 4 if all the segments of G have even size,

(S n ) 1 2 3 4 5 2 1 2 3 2 1 2 3 4 3 2 3 2 3 Rs(S n ) 1 -2 -3 -4 -1 -2 -3 -2 -1 -2 -3 -2 -1 -4 -3 -2 -1 -2 -
(S n ) 2 5 4 3 2 3 2 3 2 5 4 3 2 3 2 3 2 5 2 Rs(S n ) -2 -1 -4 -3 -2 -1 -2 -3 -2 -1 -4 -3 -2 -1 -2 -3 -2 -1 -2
• -5 ≤ Rs(G) ≤ 1 and -1 ≤ Ls(G) ≤ 5 if all the segments of G have even size except one.

In addition, the bounds in this result are tight. For example, consider the sum G = S 9 +S 2 for which Rs(G) = 1. This case is the smallest non-trivial graph in C where the first player does not win.

Mean and temperature of segments

As mentioned above, sums of segments have not been considered when there are at least two odd segments in the sum. A way to address this issue is to consider the notion of mean and temperature of segments, by applying Corollary23.

We first deal with the computation of the mean of segments. Recall first that m L (S n ) = m R (S n ) by Theorem 14. Consequently, we will denote

m n = m L (S n ) = m R (S n ). Theorem 45. Let n ∈ Z. We have    m n = 0 if n ≡ 0 mod 2 0 ≤ m n ≤ 1 if n ≡ 1 mod 2 and n ≥ 0 -1 ≤ m n ≤ 0 if n ≡ 1 mod 2 and n ≤ 0
Proof. First, suppose that n is even. We know that S n = S -n . Therefore, if p is even, Ls Now suppose that n is odd. Since S -n = -S n , and as the mean is linear, we can assume, without loss of generality, that n ≥ 0. We will show that 0 ≤ m n ≤ 1. If n = 1, we have Ls(pS 1 ) = Rs(pS 1 ) = p as no move is available. Thus m 1 = 1. If n = 3, any move of a player removes all the three vertices of S 3 . Ls and Rs can thus be computed as follows:

Ls(2pS 3 ) = 3 + Rs (2p -1)S 3 = 3 -3 + Ls (2p -2)S 3 = • • • = 0 Ls (2p + 1)S 3 = 3 + Rs 2pS 3 = 3 -3 + Ls (2p -1)S 3 = • • • = 3
This proves that 0 ≤ Ls(pS 3 ) ≤ 3 for all p. Consequently, m 3 = lim p→∞ Ls(pS3) p = 0.

If n = 5, by Example 12, we have 4S 5 = 4. By denoting p = 4q + r with 0 ≤ r < 4, we have Ls(pS 5 ) = Ls(rS 5 ) + 4q. Thus, since 0 ≤ r < 4, Ls(rS 5 ) is bounded, lim p→∞ Ls(pS5) p = 1.

Suppose n ≥ 7. We first prove that Ls(pS n ) ≤ p + 8. Assuming that Left starts, we denote by p k the number of segments of odd length in the resulting graph after the k-th move, and by s k the relative score, i.e. the difference between the number of vertices taken by Left and the number of vertices taken by Right after the k-th move. We will define a strategy for Right that has the following invariant property: for any k ≥ 0, if there exists at least one segment of length four or greater, we have p 2k + s 2k ≤ p. Since we have p 0 = p and s 0 = 0, the invariant is true before the first move. Note that we will only consider p 2k and s 2k to focus on the state of the game after each move of Right. The strategy of Right is the following: while there exists one segment of size at least four, Right considers a segment of highest length (if there are several, consider any of them). If it has odd length, Right can, by playing a 3-move on it on an extremity, transform it into a segment of even length; if it has even length, Right can, by playing a 4-move on it (which is always available on an even length segment of size greater than four) take four vertices and leave a segment of the same parity. Therefore, after the k-th move of Right, we have s 2k + p 2k = s 2k-1 + p 2k-1 -4. Note that with such a strategy, Right does not create new odd segment. Now, we consider the variation of the sequences s k and p k after the (k + 1)-th move of Left.

• If the move of Left is a 5-move, necessarily, it is played on a S 5 that is removed. We have p 2k+1 = p 2k -1 and s 2k+1 = s 2k + 5, thus p 2k+1 + s 2k+1 = p 2k + s 2k + 4.

• If the move of Left is a 4-move, it does not change the number of segments of odd length. We have p 2k+1 = p 2k and s 2k+1 = s 2k + 4, and thus p 2k+1 + s 2k+1 = p 2k + s 2k + 4.

• If the move of Left is a 3-move, and if it is in an even segment, it creates one odd segment and one even segment. If it is in an odd segment, it creates two odd segments, unless it is on a S 3 . In both cases, the number of odd segments is increased by at most one. We have p 2k+1 ≤ p 2k + 1 and s 2k+1 = s 2k + 3, thus p 2k+1 + s 2k+1 ≤ p 2k + s 2k + 4. Note that since the odd segments are positive (i.e. n ≥ 0) at the beginning of the game, and since Right's strategy does not create new odd segment, Left cannot create negative odd segment when playing.

• If the last move of Left is a 2-move, it does not change the parity of the number of odd segments. We have p 2k+1 = p 2k and s 2k+1 = s 2k + 2, thus p 2k+1 + s 2k+1 = p 2k + s 2k + 2.

Finally, we always have p 2k+1 + s 2k+1 ≤ p 2k + s 2k + 4. Thus, as p 2k + s 2k = p 2k-1 + s 2k-1 -4, the invariant property is satisfied until all segments have length three or less. In the final part of the game when all segments have length three or less, as any move in a segment removes it fully, a greedy strategy ensures that Left takes at most three vertices more than Right. As the largest available value for s k is p + 5 (i.e., after a 5-move of Left, according to the invariant), we obtain Ls(pS n ) ≤ p + 5 + 3 = p + 8.

It remains to prove that Ls(pS n ) ≥ 0. We consider a strategy for Left that preserves the following invariant: at any moment of the game, Left has taken at least the same number of vertices than Right. Moreover, if it is Right's turn, there is no segment S k with k < 0, i.e. all the remaining segments have at least one extremity black, and Left has taken at least four vertices more then Right. We define here the first part of the strategy for Left. Until all segments have size 3 or less, Left considers the following strategy:

• First, Left takes four vertices on a segment. This move is available as we assumed n ≥ 7.

• If the last move of Right does not create a segment with both extremities white, if at least one segment has size four or more, Left plays a 4-move on it (it might be a 5-move if the segment has length 5). In this way, Left has taken at least four vertices and Right at most four, as 5-moves are only available for Right on S -5 and the invariant ensures that there is no segment of this form when it is Right's turn. Therefore, the invariant is satisfied as Left does not create a S k with k < 0.

• If the last move of Right creates a segment with both extremities white, by induction, such a segment did not exist before he made this move. Thus, it has been created by a 3-move on a segment with extremities of different colors. Therefore, this move has created a segment with two white extremities and an even segment (eventually of size zero). Left answers by playing a 3-move on an extreme black vertex of the segment which has two white extremities. Playing so, Left takes also three vertices and this segment now has a black extremity. Once again, the invariant is still satisfied.

This strategy guarantees that the invariant is satisfied until all segments have size 3 or less. At this moment of the game, if it is Left's turn, by a greedy strategy, Left can ensure to take at least the same number of vertices than Right for the rest of the game. Thus, as she already has at least the same number of vertices that Right, Left is not losing. If it is Right's turn, by the invariant property, Left has taken at least four vertices more than Right (the four vertices played at the beginning). Thus, regardless the move that Right does, Left will get more vertices than Right as any segment has size three or less. This strategy ensures Ls(pS n ) ≥ 0. By gluing the two above results, we get 0 ≤ Ls(pS n ) ≤ p + 8, implying 0 ≤ Ls(pSn) p ≤ 1 + 8 p . By taking the limit, as we know from Theorem 14 that m n exists, we have 0 ≤ m n ≤ 1.

The above result about the mean is very useful to estimate the score of a sum of segments according to Corollary 23. Yet, it remains to have an upper bound on the temperature of a segment. The following theorem provides such a bound.

if this move creates two instances S 4m+1 +S 4n (with 0 < n, m < k), Right can answer by playing a 3-move in S 4k+2 that creates S -(4m+1) + S 4n+2 . The resulting game is S 4m+1 + S 4n + S -(4m+1) + S 4n+2 + S 2 = S 4n + S 4n+2 + S 2 that is not losing for Right by induction hypothesis.

if this move creates two instances S 4m+3 + S 4n+2 , Right can answer by playing a 3-move in S 4k+2 that creates S -(4m+5) + S 4n+2 . The resulting game becomes S -(4m+5) + S 4n+2 + S 4m+3 + S 4n+2 + S 2 = S 4m+3 + S -(4m+5) + S 2 that is also not losing for Right by induction hypothesis.

• If Left plays a 3-move in S 4k+2 :

if she creates two instances S 4m+2 + S 4n+1 , Right can answer by playing a 3-move in S 4k that creates S 4m + S -(4n+1) . The game becomes S 4m+2 + S 4n+1 + S 4m + S -(4n+1) + S 2 = S 4m + S 4m+2 + S 2 and we conclude as previously by induction.

- The above result yields a very significant way to make the computation of the values faster. In fact, as our program is based on a dynamic programming approach, all sums of segments need to be stored. Thanks to this result, all sums containing a S 4k+2 can be simplified by replacing it with a S 4k + S 2 .

Table 11 expands the result presented in [DGP + 21] by giving the first 120 values of the score (instead of 80). A careful analysis of this table suggests that Conjecture 43 holds, with a period of 40 and a preperiod of 30. In addition, one can remark that after the preperiod, the structure of the values is very regular (almost of period 8), except for n = 37, 77, 117 that correspond to the rare values satisfying Rs(S n ) = -5. This new table is however not sufficient to prove the ultimate periodicity of the structure, as the conjectured period of 40 does not appear frequently enough to be used in a general proof. In addition, the segments S n and S n+40 are not equivalent for almost all values of (up to n = 40), which is another pitfall to prove the conjecture. A first step towards it would be to prove that the values of Ls(S n ) are equal to 2 for all even n ≥ 32.

(S n ) 1 2 3 4 5 2 1 2 3 2 1 2 3 4 3 2 3 2 3 2 Rs(S n ) 1 -2 -3 -4 -1 -2 -3 -2 -1 -2 -3 -2 -1 -4 -3 -2 -1 -2 -3
(S n ) 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 Rs(S n ) -1 -2 -3 -2 -1 -2 -3 -2 -1 -2 -3 -2 -1 -2 -3 -2 -1 -2 -3
(S n ) 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 5 2 3 2 Rs(S n ) -1 -2 -3 -2 -1 -2 -3 -2 -1 -2 -3 -2 -1 -2 -3 -2 -1 -2 -3
(S n ) 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 Rs(S n ) -1 -2 -3 -2 -1 -2 -3 -2 -1 -2 -3 -2 -1 -2 -3 -2 -1 -2 -3 -
(S n ) 3 2 3 2 3 2 3 2 3 2 3 2 3 2 3 2 5 2 3 2 Rs(S n ) -1 -2 -3 -2 -1 -2 -3 -2 -1 -2 -3 -2 -1 -2 -3 -2 -1 -2 -3 -2
Figure 11: New values on Segments

Grids

As a natural extension to paths, we consider in this section rectangular grids. We denote by G n,m the grid with n rows and m columns, with alternated black and white vertices and a black vertex in the top left corner. See Figure 12 for an illustration of G 2,7 . Despite their symmetry, there is no BW-automorphism in rectangular grids. Indeed, the vertices close to the center of the grid are necessarily sent to each other by any automorphism, and thus could not be sufficiently distant. The results of Section 5 cannot therefore be applied. Moreover, it seems that there are neither draws nor games favourable to the second player in rectangular grids. Actually, all the computations made so far lead to a victory of the first player. This induces the following conjecture.

Conjecture 49. Let n, m ≥ 2. We have Ls(G n,m ) > 0 > Rs(G n,m ). In particular, the first player wins and there is no draw.

Note that if n or m is even, the grid is symmetric by exchanging the roles of Left and Right. Since the game is nonzugzwang, Ls(G n,m ) = -Rs(G n,m ). Moreover, as Ls(G n,m ) ≥ Rs(G n,m ), it implies directly that Ls(G n,m ) ≥ 0 ≥ Rs(G n,m ). However, if n and m are odd, this argument cannot be used.

In the rest of the section, we give some partial results supporting the conjecture for rectangular grids with two and three rows.

Grids with two rows

In this subsection, we prove Conjecture 49 on grids with only two rows. As said before, since the number of rows is even, we just need to consider the Left score. We actually prove a stronger result when the number of columns is odd, by giving the exact value of Ls(G 2,m ).

Theorem 50. Let m ≥ 3 be an odd integer. We have Ls(G 2,m ) = -Rs(G 2,m ) = 4 if m ≥ 5 and Ls(G 2,3 ) = -Rs(G 2,3 ) = 6.

For even m, we just manage to prove a lower bound on the score.

Lemma 51. Let m ≥ 4 be an even integer. We have Ls(G 2,m ) ≥ 2.

Before proving Theorem 50 and Lemma 51, we introduce some notations that will be used in both proofs. As each column contains at most one white and one black vertex, we will say playing i for playing the vertex of the current player's color in column i. Consider a connected component G at some point of a game played in a grid with two rows. Note that G can only have columns with one vertex at its extremities. Thus the full columns are consecutive. We encode G as a triplet (x, n, y) with x, y ∈ {0, -1, 1} and n an integer. The integer n corresponds to the number of consecutive full columns, x represents the first column of G and y the last one with the following convention: x = 0 (y = 0 resp.) if the column is full, x = 1 if there is a black vertex and x = -1 if there is a white vertex. In Figure 14, the two grids have respectively forms (-1, 2 -1) and (1, 4, 1). Note that the form of a partial grid completely characterizes it and that (x, n, y) and (y, n, x) correspond to the same graph.

Proof of Theorem 50. For m = 3, the first player can take the whole grid in one move, which implies that Ls(G 2,3 ) = -Rs(G 2,3 ) = 6.

Let m ≥ 5 be an odd integer. We first prove that Ls(G) ≥ 4. Indeed, Left can play m+1 2 , i.e in the middle column. This way, she takes four vertices and cuts the game in two parts of form (0, n-3 2 , 1) (see Figure 13). Then, each time Right decides to play on column i, Left plays symmetrically on column m -i + 1. If Right plays m+1 2 -2 (respectively m+1 2 + 2) and removes the single black vertex of column m+1 2 -1 (resp. m+1 2 + 1), the symmetric move of Left will remove the symmetric vertices of Right's move plus the other single black vertex. In all the other cases, Left's move removes exactly the symmetric vertices (considering a central symmetry) that Right has taken. This way, Left can finish the game without loosing any vertex and Ls(G n ) ≥ 4.

. . . . . . We now prove that Ls(G 2,m ) ≤ 4 by induction. First, we prove that if G has the form G 1 +G 2 with G 1 = (x, n, y) and G 2 = (-x, n + 2, -y), then Ls(G) ≤ 4 (see Figure 14).

We prove this result by induction on n the number of full columns of G 1 (G 2 has n+2 full columns). Note that G 2 has four more vertices than G 1 . Consider the first move of Left. Assume first that Left did not take a full component and that Left plays in G 1 . By symmetry, we can assume Left has play in some column i with i ≤ n+1 2 (starting to count from the first full column). The whole graph after this move can be written as R + (1, n -i -1, y) + G 2 with R that might be empty (and necessarily, i + 1 ≤ n). Then Right can answer by playing in column i of G 2 . He takes the same number of vertices than Left. The remaining graph after these two moves has the form R + (1, n -i -1, y) + R + (-1, n -i + 1, -y) where R and R are opposite (and might be empty). Hence, R and R cancelled each other. By induction, Left can score at most 4 in (1, n -i -1, y) + (-1, n -i + 1, -y), and thus can score at most 4 in total.

Assume now that Left plays in G 2 but did not take the whole graph. Again, by symmetry, we can assume Left has play in some column i with i ≤ n+3 2 and that it remains

G 1 + R + (1, n + 1 -i, -y)
, where R might be empty but where (1, n + 1 -i, -y) contains at least two vertices. If Right can take fully G 1 , he takes it and at the end, the score will be at most 4. Otherwise, we must have n ≥ 2 and then we have i ≤ n. Right plays in column i of G 1 and take as many vertices as Left. Then it is remaining after the two moves R + (1, n -i -1, y) + R + (-1, n -i + 1, -y) and we can conclude as before.

Finally, assume that Left takes a full component. If Right can take the other component, the game ends with a score of at least 4. Otherwise, it means that Left played in G 1 and that n ≤ 3. Let i ≤ 2 be the column where Left played. If n = 1, the only case where Right cannot take the whole G 2 is when G 2 has form (1, 3, 1) or (0, 3, 1). In the first case, Right can take four vertices and then both players take two vertices, ending in a draw. In the second case, Right takes five vertices, Left can take the two remaining vertices, and the games end in a draw. If n = 2, Left took at most six vertices. If x or y is equal to -1, then Right can take four vertices in G 2 and leaves a graph with two components of size at least 2 by playing in column 2 or 3. Thus at the end, Right will win at least six vertices. If x = y = 1, Right can directly take six vertices in G 2 by playing in column 2. In both cases, Left takes at most ten vertices, ending with a score of at most 4. If x = 0 or y = 0, Right can take 5 vertices and there are at most 14 vertices in total, thus the score is also at most 4. Finally, if n = 3, Left took at most eight vertices. As before, Right can take at least |G 1 | vertices by taking four vertices in his first move and splitting G 2 in two components of size at most 3 (if

|G 1 | = 7) or 4 (if |G 1 | = 8).
Turn back to our original graph G 2,m . Right can follow the following strategy :

• While Left does not play in the five columns in the middle, play the symmetric. The most left and most right graphs are opposite and thus simplify each other. The remaining graph has form (1, m , -1) with m odd. In particular, there is still a symmetry center.

• If Left plays column (m + 1)/2 -2 (or the symmetric), play the symmetric. The components on the left and the right simplify. Only four vertices are left in the middle, so Left win at most four vertices. We have Ls(G 2,m ) ≤ 4.

• If Left plays at distance 1 to the central column, i.e. she plays (m + 1)/2 -1, then play the symmetric. The two remaining graphs are opposite. So Ls(G 2,m ) ≤ 0.

• If Left plays the central column (m + 1)/2:

-If the vertices in column (m + 1)/2 -3 have been played, the graph was (before the move of Left) of the form (1, 3, -1). Thus Left took six vertices and let a S 2 . Right can take it. The final score is 6 -2 = 4.

-If the vertices in column (m + 1)/2 -3 have not been played, Right plays in column (m + 1)/2 -2 and takes four vertices (like Left did). Then the remaining graph has form (x, n, 1) + (-1, n + 2, -x). Using the result proved above (recall that (-1, n + 2, -x) = (-x, n + 2, -1), the score is at most 4 at the end.

Finally, Ls(G 2,m ) ≤ 4, and the theorem is proven.

Proof of Lemma 51. Let m ≥ 4 be an even integer. We prove that Ls(G 2,m ) ≥ 2 by giving a strategy for Left to score 2. Left can start by playing in column m/2 (it corresponds to the vertex marked by a circle on Figure 15). Denote by G the remaining graph after this first move. Left can then decide to "give" the two vertices marked by blue triangles in the graph of Figure 15. More precisely, we apply Theorem 25 with B 0 = {x 1 , x 2 } where x 1 and x 2 are the black vertices of columns m/2 + 1 and m/2 + 2. We obtain Rs(G ) ≥ Rs(G \B 0 ) -|B 0 | ≥ -2, since G \B 0 is the sum of a game and its opposite, and thus a score 0. Finally, Ls(G 2,m ) ≥ 4 -Rs(G ) ≥ 2.

. . . . . .

Grids of three rows

As detailed in the previous sections, in the cases of segments and grids of two rows, a common technique to prove that the first player has a winning strategy consists in cutting the graph into two "similar" parts and then guarantee that he will not lose many points on the rest of the game. Unfortunately, this technique is no more available for grids having at least four rows, as single moves generally keep the graph connected. Yet, in the case of grids of three rows, some moves split the grid into two parts, but other moves keep it connected. This is sufficient to yield strategies for the first player in almost all configurations.

First note that if m is odd, as the grid is not symmetric, having Ls(G 3,m ) ≥ 0 or Rs(G 3,m ) ≤ 0 is not straightforward at first sight. However, we will prove Conjecture 49 for grids of three rows in almost all cases.

Theorem 53. Let G 3,m be a grid of three rows and m columns, with a black vertex at the top left. We have Ls(G 3,m ) > 0, and if m ≡ 3 mod 4, Rs(G 3,m ) < 0.

Proof. To make the proof more understandable, in the following figures, we will mark by a red circle the vertex played by the first player, by red squares the vertices taken by this move, and by blue triangles the vertices freely given to the opponent using Theorem 25.

Let G = G 3,m be a grid of three rows.

• If m ≡ 0 mod 2. We already know by symmetry that Ls(G) = -Rs(G). So, without loss of generality, it is sufficient to prove that Ls(G) > 0.

Left can adopt the following strategy: play the black vertex on column m 2 marked by a red circle (see Figure 17). Left takes all vertices marked by red squares and scores 5 points. Then, she can give the two black vertices • If m ≡ 1 mod 4 and Left starts, she can play the black vertex at the bottom of column m+1 2 marked by a red circle (see Figure 18). Then, by giving to Right the two black vertices in top corners and the black vertex in the middle of the first row, she creates two identical symmetric graphs. Note this set of three vertices B 0 = {x 1 , x 2 , x 3 } and the resulting graph H sym . Therefore, the score satisfies Ls(G) ≥ 4 + Rs(H sym ) -|B 0 | = 4 + 0 -3 = 1. • If m ≡ 1 mod 4 and Right starts, he can play the vertex in the middle of the graph (see Figure 19), and then give the two black vertices x 1 and x 2 of the columns m-1 • If m ≡ 3 mod 4 and Left starts, she can play the middle vertex of the graph and give the four black vertices at its diagonals to Right (see Figure 20). Note these four vertices B 0 = {x 1 , x 2 , x 3 , x 4 }. The remaining graph H sym is composed of two instances of G 3, m-3 2 , so it is equivalent to 0 as m -3 ≡ 0 mod 4. Finally, the score satisfies Ls(G) ≥ 5 + Rs(H sym ) -|B 0 | = 5 + 0 -4 = 1.

The case of grids of three rows is almost solved from the above result. As an open problem, it remains to show that if m ≡ 3 mod 4 and Right starts, he has a winning strategy.

Figure 1 :

 1 Figure 1: First moves of Bipartite Influence on a 5 × 5 grid

  and Ls(G) = Ls(G ). On the other side, Rs(G ) = Rs(G) since the Right options of G and G are the same. Thus Ls(G ) ≥ Rs(G ) and G is dicotic nonzugzwang. Therefore, to prove that G = G , one need to prove that Ls(G -G ) = Rs(G -G ) = 0. Since G -G is dicotic nonzugzwang, we already have Ls(G -G ) ≥ Rs(G -G ). Thus one just need to prove that Ls(G -G ) ≤ 0 and that Rs(G -G ) ≥ 0. Left can answer to any Right move in G -G by a move leading to a game H -H = 0 since all the Right options in G -G have a symmetric Left option. Hence Left has a strategy to insure a score 0 when playing second, which means that Rs(G -G ) ≥ 0. Assume now that Left starts in the game G -G . If Left does not play to G l 1 -G , then Right can answer to a game H -H = 0 and insure a score of 0. If Left play to G l 1 -G , Right can answer to G l 1 -G l 2 and insure a non positive score since Ls

Figure 5 :

 5 Figure 5: Left, by "giving" the two black vertices v 7 and v 8 , can ensure a score of -2 in this graph since the rest of the graph has a (Left and Right) score of 0.

  Figure 6: Reductionof φ = (X 1 ∨ X 2 ) ∧ (X 2 ∨ X 3 ) ∧ (X 3 ∨ X 4 ) ∧ (X 4 ∨ X 1 )to Bipartite Influence. Big black vertices represent 11 pendant vertices.

Figure 7 :

 7 Figure 7: Hypercube H 4

Figure 8 :

 8 Figure 8: Cylinder C 4,6 (Torus T 4,6 with the dashed edges)

Definition 40 (

 40 Duchêne et al [DGP + 21]). The class C segment represents the class of all Bipartite Influence graphs that are paths.

Figure 9 :

 9 Figure 9: Segment S -7

  [DGP + 21], the first 80 values of Ls and Rs are computed on segments, yielding Figure 10 (depicting the first 38 values). The structure of these results led to the following conjecture: Conjecture 43 (Duchêne et al [DGP + 21]). The sequences Ls(S n ) and Rs(S n ) are ultimately periodic.

Figure 10 :

 10 Figure 10: Left and Right score for segments in [DGP + 21]

  if p is odd, we have Ls(pSn) p = Ls(Sn) p . As -5 p ≤ Ls(Sn) p ≤ 5 p , we have Ls(Sn) m n = 0.

Figure 12 :

 12 Figure 12: Grid G 2,7

Figure 13 :

 13 Figure13: An optimal strategy for Left when the number of columns is odd, is to take the central black vertex (marked with a red circle) and then playing the symmetric column. This strategy gives a final score of 4.

Figure 14 :

 14 Figure 14: In (-1, 2, -1) + (1, 4, 1), Left can score at most 4.

x 1 x 2 Figure 15 :

 215 Figure 15: Strategy if the number of columns is even

Figure 16 :

 16 Figure 16: Example of grid of three rows and eight columns.

  x 1 and x 2 of column m 2 + 1 to Right, and apply Theorem 25 with B 0 = {x 1 , x 2 }. The remaining graph is composed of two grids G 3, m 2 -1 . But the left part has one missing white vertex marked by a red square square. Add it to the graph by giving one more point to Right once again according to Theorem 25 with W 0 = {x 3 }. Note H sym the symmetric graph obtained. The final score thus satisfies Ls(G) ≥ 5 + Rs(H sym ) -|W 0 | -|B 0 | ≥ 5 -1 -2 = 2 .

Figure 17 :x 2 x 1 x 3 Figure 18 :

 17318 Figure 17: Strategy if m ≡ 0 mod 2 x 2 x 1x 3

2 and m+3 2 tox 1 x 2 Figure 19 :

 2219 Figure 19: Strategy for Right if m ≡ 1 mod 4.

  , from Proposition 18, we have Ls(nG) -t ≤ Ls((nG) t ) = nx = Rs((nG) t ) ≤ Rs(nG) + t

	By dividing by n, we have
				Ls(nG) n	-	t n	≤ x ≤	Rs(nG) n	+	t n
	.
	Finally, as lim n→∞	Ls(nG) n	= lim n→∞	Rs(nG) n

  if she creates two instances S 4m + S 4n+3 , Right can answer by playing a 3-move in S 4k that creates S 4m + S -(4n+1) . The game becomes S 4m + S 4n+3 + S 4m + S -(4n+1) + S 2 = S 4n+3 + S -(4n+1) + S 2 and we can conclude by induction. If the game is S 4k+3 + S -(4k+5) + S 2 : • if Left makes a 3-move in S 4k+3 , it necessarily creates two instances S 4m+1 and S 4n+3 . Right can answer by playing a 3-move in S -(4k+5) that creates S -(4m+1) and S -(4n+5) . The resulting game is S 4m+1 + S 4n+3 + S -(4m+1) + S -(4n+5) + S 2 = S 4n+3 + S -(4n+5) + S 2 , and thus not losing for Right by induction hypothesis. • if Left makes a 3-move in S -(4k+5) , it creates two instances S 4m and S 4n+2 . Right can answer by playing a 3move in S -(4k+3) that creates S 4m and S 4n . The game becomes S 4m +S 4n+2 +S 4m +S 4n +S 2 = S 4n +S 4n+2 +S 2 , and we can conclude by induction. If the game is S 4k+3 + S -(4k+1) : • if Left makes a 3-move in S 4k+3 , she creates two instances S 4m+1 and S 4n+3 . Right can answer by playing a 3-move in S -(4k+1) that creates S -(4m+1) and S -(4n+1) . The resulting game is S 4m+1 + S 4n+3 + S -(4m+1) + S -(4n+1) + S 2 = S 4n+3 + S -(4n+1) + S 2 , and hence not losing for Right by induction. • if Left makes a 3-move in S -(4k+1) , she creates two instances S 4m+2 and S 4n . Right can answer by playing a 3move in S 4k+3 that creates S 4m+2 and S 4n+2 . The resulting game becomes S 4m+2 +S 4n +S 4m+2 +S 4n+2 +S 2 = S 4n + S 4n+2 + S 2 and we can conclude by induction.

v 1,1 v 1,2 v 1,3 v 1,4 v 1,5 v 1,6 v 2,1 v 2,2 v 2,3 v 2,4 v 2,5 v 2,6 v 3,1 v 3,2 v 3,3 v 3,4 v 3,5 v 3,6 v 4,1 v 4,2 v 4,3 v 4,4 v 4,5 v 4,6

Theorem 46. Let n ∈ Z. We have σ(S n ) ≤ 4.

Proof. Up to switching Right and Left, we can assume without loss of generality that n ≥ 0. We prove the result by induction on n. If n ≤ 4, the result is straightforward as the temperature cannot be larger than the maximum score on the game. If n = 5, one can prove that σ(S n ) = 4 according to Figure 4.

Assume now that n ≥ 6. By Definition 15 of the temperature, to prove that σ(S n ) ≤ 4, it is enough to prove that for t ≥ 4, Ls(( S n ) t ) ≤ Rs(( S n ) t ). Let t ≥ 4. We recall that ( S n ) t = (S L n ) t -t|(S R n ) t + t . Consider a Left option g L and a Right option g R of S n .

A move in S n splits the segment into at most two parts, thus we can write

2 with α, β > 0 the scores obtained by each move. By induction, we have σ(S i L 1 ), σ(S i L 2 ), σ(S i R 1 ), σ(S i R 2 ) ≤ 4. Thus, g L t and g R t are frozen for t ≥ 4 and, by Proposition 21, equal to their means. In particular, since the mean is linear, we have Rs(

). Assume first that n is odd. Right can only play 3-moves from S n , thus β = 3 and both S i R 1 and S i R 2 are of even length. Therefore, by Theorem 45, m(S i R 1 ) = m(S i R 2 ) = 0 and we have:

) ≤ 1 by Theorem 45, and we have:

Finally, we obtain, for any options g L and g R :

In particular, this is true if g L t -t and g R t + t are the best options of (S n ) t . Then we have:

Assume now that n is even. If Left made a 3-move, one of the remaining path is even and the other is odd. Without loss of generality, we can assume that S i L 2 has even length. By Theorem 45, m(S L i2 ) = 0 and

Otherwise, Left made a 4-move and only one path is remaining, and has even length . Thus we also have:

Symmetrically, Ls(G R t ) + t ≤ -4 + t. Therefore, if t ≥ 4, we have for any options g L and g R , Rs(g L t ) -Ls(g R t ) ≤ 8 -2t ≤ 0 and so, as before, Ls(

Finally, regardless if n is odd or even, we have Ls( (S n ) t ) -Rs( (S n ) t ) ≤ 0 for any t ≥ 4. In particular, this means that σ(S n ) ≤ 4.

We now have all the material to give an estimate of the score on a sum of segments.

Corollary 47. Let n 1 , . . . , n p ∈ Z, with exactly k of the n i of odd value. We have

Proof. This result is directly deduced from Theorem 46, Theorem 45 and Corollary 23.

Note that the bounds of Corollary 47 are tight. Consider for example a sum of 4n + 1 segments S 5 . Since 4S 5 = 4 according to Example 12, we have Ls((4n + 1)S 5 ) = 4n + Ls(S 5 ) = 4n + 5.

Additional results about the periodicity conjecture of segments

In order to explore the validity of Conjecture 43, more values are required. Recall that in [DGP + 21], only the first 80 values of the score has been computed. The computation of the scores of segments can be boosted by using equivalences between sums. Recall that in a sum of games, any component can be replaced by another component equivalent to it.

The following result shows that two consecutive segments of even size (starting by the one that is a multiple of 4) can be replaced by the segment S 2 in a sum.

Theorem 48. Let k ∈ N, we have S 4k + S 4k+2 = S 2 .

Proof. According to Lemma 8, it suffices to show that Ls(S 4k + S 4k+2 + S 2 ) = 0.

We will prove by induction on k that for any k ∈ N, we have :

First, we give strategies for Left to ensure the following inequalities:

In S 4k + S 4k+2 + S 2 , Left can play a move on a extremal vertex in S 4k+2 that takes exactly two vertices. After that, it is Right's turn and the game is S 4k + S 4k + S 2 that is equivalent to S 2 . Therefore, Right also scores two points and we have Ls(S 4k+2 + S 4k + S 2 ) ≥ 0.

In S -(4k+5) + S 4k+3 + S 2 , Left can first play S 2 and scores two points. Then, by Theorem 25 (third inequality), imagine that Left gives the second vertex of S -(4k+5) to Right. After this move, the game is equivalent to S -(4k+3) + S 4k+3 + S -1 = -1. Once again, we have Ls(S -(4k+5) + S 4k+3 + S 2 ) ≥ 0.

In S 4k+3 + S -(4k+1) + S 2 , Left can first play an extremal move on S 4k+3 that takes exactly two vertices. After that, it is Right's turn and the game is S 4k+1 + S -(4k+1) + S 2 = S 2 . Therefore, Right scores two points on it and we have Ls(S 4k+3 + S -(4k+1) + S 2 ) ≥ 0. Now, we give strategies for Right that ensure the other inequalities (i.e. Right is the second player and is not losing). If k = 0 or k = 1, the induction hypothesis is true by checking by hand all the possible options. Now assume k ≥ 2 and that the induction hypothesis is true for all 0 ≤ k < k. First, remark that no 5-move is available in any of these games for Left as there is no S 5 component. Secondly, if Left plays a 4-move in any of these games, Right can answer by a 4-move in the other component that is not S 2 and then obtains an instance that is strictly smaller that the initial one and where he will not be losing by induction. Thirdly, since 2-moves are dominated, one can suppose, without loss of generality, that Left never plays one of them. It thus remains to consider which strategy can be used by Right when Left starts with a 3-move. If the game is S 4k + S 4k+2 + S 2 :

• If Left plays a 3-move in S 4k :