Sign games on graphs

Liz Blum, Ranjan Rohatgi · 2025

Read Sign games on graphs by Liz Blum, Ranjan Rohatgi (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-05451.txt.

Introduction

Liz Blum and co-authors define the Sign Game, a two-player game on a graph where players take turns to mark each vertex plus one or minus one. Edges then take the product of their end marks, and the final score is the sum over all edges.

One player wants a positive score, the other a negative one. The authors play the game on many graph types and work out who wins and how. A simple rule set hides rich structure, since early marks set up late edge signs. The results add a fresh game to the study of graphs.

Catalog record

CREATORLiz Blum, Ranjan Rohatgi
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE30 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-05451

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Sign games on graphs Liz Blum, Ranjan Rohatgi Abstract We define the Sign Game as a two-player game played on a simple undirected mathematical graph G G . The players alternate turns, assigning vertices of G G either 1 1 or − 1 -1 , and edges take on the value of the product of their endvertices. The game ends when all vertices are assigned values, and the score of the game is the sum of all edge values. One player’s goal is to make the score positive while the other’s is to make the score negative. In this paper we investigate the game being played on various types of graphs, determining outcomes and winning strategies. AMS Subject Classification: 91A43, 05C57 Keywords: games on graphs, simple graph 1 Introduction and definitions Nowadays people have strong opinions that oftentimes make their way into online social networks. When two people share the same (or opposite) opinion on a certain touchy subject, we might say that the social network connection between them is positive (resp. negative ) on this matter. Take politics, for example. When two friends in a social network share the same political affiliation, it is natural to say the political connection between them is positive , whereas it is negative if they have opposite affiliations. In this paper, rather than looking at these individual connections, we want to look at the entire friendship network and investigate it as a whole. Social networks are naturally represented modeled with mathematical graphs. Some, like X or Strava, give rise to directed graphs (an edge from v_{1} to v_{2} means v_{1} is following v_{2} in the network; a fan may follow a celebrity but the celebrity likely won’t follow the fan), while others, like Facebook, being friends is a two-way street (if v_{1} is friends with v_{2} , then v_{2} is friends with v_{1} ). Undirected simple graphs (those with no loops and no multiple edges) best represent these latter scenarios, and in this paper, all graphs are assumed to be of this type. A variety of two-player graph-labeling games appear in the literature. In 1991, Bodlaender, in [ 1 ] extended the famous map-coloring game to a game on arbitrary finite graphs. Since then, many more games have been introduced and analyzed, including the game chromatic index [ 3 ] , several graph labeling games in [ 6 ] , the game of cycles [ 5 ] , and the graceful game [ 4 ] . Here, we define a new two-player game, called the Sign Game, that mimics the concept of measuring how positive or negative the collection of a network’s connections are. 1.1 Defining the game Let G be a simple undirected graph. The Sign Game on G is a two-player game with two players Player P (for positive ) and Player N (for negative ) proceeding as follows. 1. Players alternate turns; the first player to play is referred to as Player 1 and the second player as Player 2 (so that Player P is one of Player 1 or Player 2, as is Player N). On a turn, a player assigns either a +1 or a -1 to any vertex on G that has not been assigned a value. 2. When both endvertices of an edge have been assigned a value, that edge takes on the value of the product of the vertices; this is called the score (in points) of the edge. When the second endvertex of an edge is assigned and the edge takes on a value of +1 (resp. -1 ), we say that Player P (resp. Player N) banks 1 (resp. -1 ) point(s). 3. The game concludes when all vertices have been assigned values (and consequently all edges have a score). Define the score s(G) of the game to be the sum of all edge scores. 4. Player P wins if s(G)>0 , Player N wins if s(G)<0 , and the game is a draw if s(G)=0 . The score of the game in Fig. 1.1 is -1 , resulting in Player N winning. Any game played on the graph in Fig. 1.1 would result in a winner (since the graph has 5 edges), but would the winner always be Player N? As we will see, the result of a game often, but not always, depends on which player plays first. + - + + - Figure 1.1: Player N wins Throughout this paper we will assume that both players choose to play optimally, with a primary goal of winning and a secondary goal of the game ending in a draw (that is, not allowing their opponent to win). 1.2 SG-equivalence Because the nature of the game makes brute force investigation of anything but the smallest graphs overwhelming, we introduce a method to “reduce” graphs to ones with fewer vertices for which playing the Sign Game on them yields the same result as playing the game on the original graph. Two graphs G_{1} and G_{2} , which may have some vertices assigned values, are said to be SG-equivalent if playing the Sign Game to completion on G_{2} (preserving the order of play for Players P and N) yields an equal score as if it were finished on G_{1} (that is, s(G_{1})=s(G_{2}) ). Figure 1.2 illustrates two SG-equivalent graphs. + - + (a) Graph G_{1} + (b) Graph G_{2} Figure 1.2: SG-equivalent graphs G_{1} and G_{2} 2 Graph types In this section we investigate playing the Sign Game on various categories of mathematical graphs, beginning with one representing a social network where every member is connected to every other member: complete graphs. 2.1 Complete graphs The complete graph K_{n} ( n\geq 2 ) is the graph with n vertices and an edge between every pair of distinct vertices. When the Sign Game is played on K_{n} , Player N almost always wins, as shown in Thm. 2.2 . Before proving it, we state the following lemma, whose proof is a simple counting argument left to the reader. Lemma 2.1 If the Sign Game is played to completion on G=K_{n} and a vertices are assigned +1 and b vertices assigned -1 (so that a+b=n , with a,b\geq 2 ), then s(G)=\binom{a}{2}+\binom{b}{2}-ab. (1) The result in Lem. 2.1 could be stated solely in terms of a and n , but the choice to introduce the variable b allows for a cleaner proof of this section’s main result, Thm. 2.2 . In the proof of this theorem, we will see in many instances where a player’s strategy is dependent upon what the other player just assigned. While the choice of vertex or vertex assignment will vary, we will refer to such a strategy as a mirroring strategy . Theorem 2.2 Player N will win the Sign Game played on K_{n} for n\geq 2 , unless Player N is Player 1 and either n=2 , in which case Player P wins, or n=4 , which results in a draw. Proof. As in Lem. 2.1 , suppose the Sign Game is played to completion on G=K_{n} ( n\geq 2 ) with a vertices assigned +1 and b vertices assigned -1 . Without loss of generality, we can assume a\geq b

Read the complete text