Shannon Switching Game and Directed Variants

Abstract

Shannon’s switching game is a combinatorial game invented by C. Shannon circa 1955 as a simple model for breakdown repair of the connectivity of a network. The game was completely solved by A. Lehman, shortly after, in what is considered the first application of matroid theory. In the middle 1980s Y. O. Hamidoune and M. Las Vergnas introduced and solved directed versions of the game for graphs considering their generalization to oriented matroids. We do a brief review of the main results and conjectures of the directed case.

These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.

1 Introduction

In the middle 1950s C. Shannon invented the following game: given a connected graph G with two distinguished vertices x and y, two players JOIN and CUT choose alternately one unplayed edge. JOIN reinforces the chosen edge that becomes invulnerable and CUT deletes the chosen edge. JOIN wins if he succeeds in making invulnerable the edges of a path connecting x to y. CUT wins otherwise.

Shannon’s game, like Hex, invented earlier by Piet Hein are examples of two player games where the objective of one or both players is to connect or keep connected some subset of nodes of a network.

Mathematically both games are well known combinatorial games where J. Nash’s stealing argument applies [2]. In the case of the Shannon switching game Nash’s argument guarantees that if one of the players, JOIN or CUT, has a winning strategy playing second then the same strategy applied to any fictitious first move of its opponent, guarantees that he, JOIN, respectively CUT, playing first will win the game too.

The game was completely solved by Lehman in 1964 [15] and is a classical game in combinatorics and its applications [2, 5, 11, 16].

Less known are the results and conjectures concerning the directed versions of Shannon’s switching game for graphs and oriented matroids that were introduced and studied by Hamidoune and Las Vergnas in [12, 13]. The detailed presentation and discussion of these directed versions in [12] makes it clear that the directed versions are considerably more difficult to analyse.

In general all these games were inspired and have direct applications in engineering problems and network analysis of electrical networks, optical networks, more generally, communication networks and information theory.

In what follows we recall Lehman’s results on Shannon’s game, and then briefly review the main results and conjecture of the directed case.

We have implemented a computational prototype of two games: TREE and ARBORESCENCE whose analysis, as the reader will see, is the key for solving respectively, the undirected and the directed, Shannon switching games. In both games the human player plays as JOIN, starts second, and has a winning strategy. However at his first mistake, the computer is expected to take the lead and win. The interested reader may download the games from [9]: http://shlvgraphgame.fc.ul.pt/.

2 Solution of Shannon’s Classical Game

2.1 Shannon’s Switching Game (G; e)

Shannon’s switching game (G; e) is a two player game played on a connected graph G with a distinguished edge $e =\{ x,y\},\ x\not =y$, not subject to play. Two players, JOIN and CUT, play alternately choosing one unplayed edge of the graph. JOIN reinforces the chosen edge, CUT deletes the chosen edge.

JOIN wins if he succeeds in reinforcing the edges of a path connecting x to y. CUT wins otherwise.

Shannon’s switching games (G; e) are combinatorial games that fall into one of the following three classes:

A JOIN GAME, if JOIN playing second has a winning strategy, a CUT GAME, if CUT playing second has a winning strategy or a NEUTRAL GAME, when the first player has a winning strategy (see Fig. 1).

Fig. 1

(a) JOIN game; (b) CUT game; (c) NEUTRAL game

The game was solved by A. Lehman who characterized each class of games. The clues of Lehman’s solution are the following:

• 1. The observation that the game depends exclusively on the matroid of cycles of the graph (see Definition 1).

  This observation enlightens the duality between the objectives of JOIN and CUT simplifying, on one hand, the analysis of the game and showing simultaneously, that the natural context of the game is matroids, rather than graphs or graphic matroids.

• 2. The strategies and characterization of Shannon’s game are derived from the strategies of an associated game: the TREE GAME on a particular kind of graph: blocks (see Definition 2).

  Constructive and algorithmic aspects of Lehman’s results for graphs were considered by Bruno and Weinberg in [6] exploring the notion of principal partition of a graph introduced by Kishi and Kajitani [14] that they have generalized to matroids in [7].

In the next paragraphs we sketch the main results and strategies, starting with the description of the associated game: TREE.

We assume the reader is acquainted with the basic notions of graph theory. Good references are [1, 11]. In the next paragraph we recall some terminology and notation.

Notation

Given a graph G, we denote by V (G) the set of its vertices and by E(G) the set of its edges. A subgraph G ^′ of G is any graph satisfying the conditions V (G ^′) ⊆ V (G) and E(G ^′) ⊆ E(G). For every edge e, G ∖ e denotes the subgraph obtained from G deleting e, and G∕e the subgraph obtained from G contracting e. We recall that the contraction G∕e is the graph obtained from G identifying the vertices of the edge e and then eliminating e.

A tree T is a connected graph with minimum number of edges. The numbers of vertices and edges of a tree are related by: $\vert E(T)\vert = \vert V (T)\vert - 1$. A forest is a graph whose connected components are trees.

Given a connected graph G, a spanning tree T of G is a maximal tree that is a subgraph of G. One has V (T) = V (G) and $\vert E(T)\vert = \vert V (G)\vert - 1$.

Definition 1 (Matroid of Cycles of a Connected Graph)

The matroid of cycles of a connected graph G is the pair $M(G) = (E(G),\mathcal{B})$ where $\mathcal{B}\subseteq 2^{E(G)}$, the family of bases of the matroid, is defined as: $\mathcal{B}:=\{ E(T):\ T\ is\ a\ spanning\ tree\ of\ G\}$. The number of edges, | V (G) | − 1, of a (any) base is the rank of the cycle matroid.

The circuits of the matroid M(G) are the sets of edges of a minimal closed path of the graph. A cocircuit of M(G) is a minimal subset of edges whose removal disconnects the graph.

One says that an edge e is spanned by a subset of edges A ⊆ E(G) if there is a circuit C of M(G) such that $e \in C \subseteq A \cup e$. Clearly, given a connected graph G and a spanning tree T of G every edge e ∉ E(T) is spanned by E(T) or simply, by T. Moreover, there is a unique circuit C(T; e) such that $e \in C(T;e) \subseteq E(T) \cup e$.

A graphic matroid is the matroid of cycles of some graph.

For an introduction to matroids the reader may consult [18] or [17].

2.2 TREE

Like Shannon’s switching game TREE is a two person game played on a connected graph G. The two players, JOIN and CUT, play like in Shannon’s game: alternately, JOIN reinforcing one unplayed edge, CUT deleting one edge. The objective of JOIN is to reinforce the edges of a connected spanning tree of G. If he does not succeed, CUT wins.

Notice that CUT wins if he deletes the edges of a cocircuit of the graph G, equivalently, a cocircuit of the graphic matroid of G.

The analysis of this game depends exclusively on the notion of pair of maximally distant spanning trees of the graph G, resp. pair of maximally distant bases in the case of a matroid. In other words, the game depends on the matroid union $M(G)\bigvee M(G)$, with M(G) the cycle matroid of the graph.

Definition 2 (Blocks and Maximally Distant Spanning Trees)

A block is a matroid that is the union of two disjoint bases. A connected graph G is a (connected) block if $E(G) = E(T_{1}) \uplus E(T_{2})$ with $T_{1},T_{2}$ two edge-disjoint spanning trees of G.

A pair of maximally distant spanning trees of a connected graph G is a pair of spanning trees $(T_{1},T_{2})$ that maximizes the cardinal $\vert E(T) \cup E(T^{{\prime}})\vert$ with $(T,T^{{\prime}})$ a pair of spanning trees of the graph. A connected graph G is a (connected) block if and only every pair $(T_{1},T_{2})$ of maximally distant spanning trees satisfies the equalities: $\vert E(T_{1}) \cup E(T_{2})\vert = \vert E(T_{1})\vert + \vert E(T_{2})\vert = 2\vert E(T_{1})\vert$.

All the strategies to play TREE and Shannon’s switching game follow from the proof of the next Lemma:

Lemma 1

The TREE game on a connected block is a JOIN game.

The proof describes a recursive winning strategy for JOIN playing second.

Strategy for JOIN winning TREE on a connected block, playing second

• (1) Let $G = T_{1} \uplus T_{2}$ be a connected block, with set of edges $E(G) = E(T_{1}) \uplus E(T_{2})$, $T_{1},T_{2}$ two edge disjoint spanning trees of G.

• (2) Denote by c the edge deleted by CUT in his first move. Assume w.l.o.g. that c ∈ E(T ₁).

  Notice that once c is deleted T ₁ ∖ c has exactly two connected components, say R and S.

• (3) JOIN then responds reinforcing(contracting) any edge j ∈ E(T ₂) that has one vertex in R and the other in S, equivalently, j is any edge of T ₂ such that the unique circuit - C(T ₁ ;j)—contained in $E(T_{1}) \cup j$ contains c.

  For every such j, the graph $G_{1} = G\setminus c/j$ is a connected block whose rank is rank(G) − 1. The game continues with G replaced by G ₁.

Figure 2, below, illustrates the strategy.

Fig. 2

JOIN possible responses to CUT playing c

From the above strategy one concludes that the game TREE is a JOIN game for any connected graph G containing a spanning block. Notice that when the graph strictly contains a spanning block $T_{1} \cup T_{2}$, CUT may delete an edge outside $E(T_{1}) \cup E(T_{2})$. In this case JOIN imagines a possible move for CUT in the block and replies to that fictitious move of CUT.

If a graph G does not contain a spanning block then every pair $(T_{1},T_{2})$ of maximally distant spanning trees of G satisfies one of the following two conditions: either $(i)\ \ \vert E(T_{1}) \cap E(T_{2})\vert = 1$ or $(ii)\ \ \vert E(T_{1}) \cap E(T_{2})\vert \geq 2$. It is not hard to derive from the proof of the lemma winning strategies for the first player, JOIN or CUT, in case (i), as well as winning strategies for CUT playing second in case (ii).

Notice also that the above algorithm gives the strategy for JOIN playing second in Shannon’s switching game when the distinguished edge e is spanned by a (connected) block not containing it. The fact that JOIN can reinforce a spanning tree of such a block will certainly guarantee that JOIN reinforces the edges of a circuit contained in that block union e, in other words that block contains a circuit of the graph, broken at e.

The next theorem solves TREE. Theorem 2, a direct consequence of Theorem 1, solves Shannon’s switching Game.

Theorem 1 (Classification of TREE [15], See Also [12])

Let G be a connected graph. Consider a pair $(T_{1},T_{2})$ of maximally distant spanning trees of G.

• 1. If $\vert E(T_{1}) \cap E(T_{2})\vert$ the TREE game is a JOIN game.

• 2. If $\vert E(T_{1}) \cap E(T_{2})\vert$ the TREE game is a NEUTRAL game.

• 3. If $\vert E(T_{1}) \cap E(T_{2})\vert$ the TREE game is a CUT game.

Theorem 2 (Classification of Shannon’s Switching game [15], See Also [12])

A Shannon’s switching Game (G,e) is:

• 1. a JOIN game if and only if G contains a block spanning, but not containing e;

• 2. a NEUTRAL game if and only if G contains a block spanning e and every such block contains e;

• 3. a CUT game if and only if there is no block spanning e.

3 Hamidoune-Las Vergnas Directed Switching Games

In the 1980s Hamidoune and Las Vergnas [12] studied generalizations of Lehman’s results to oriented matroids. They defined two types of directed variants of Shannon’s game: in the first type CUT plays as in the original game, deleting edges, but JOIN plays differently. Each move of JOIN consists in directing one edge of the graph. In the second type of variants both players direct edges.

The objectives of JOIN are then translated in terms of directed paths, positive directed circuits or cocircuits.

Concerning the games of the second type, very little is known about them. Even their classification is not clear. In contrast with the undirected case, where a player having a winning strategy playing second has a winning strategy playing first, there are examples [12] of games of the second type where J. Nash stealing argument does not apply, games where a player has a winning strategy playing second but looses when playing first.

Concerning the directed games of the first type, Hamidoune and Las Vergnas proved that, in this case, the classification of the directed and undirected Shannon’s switching games are exactly the same. Their proofs for the directed case, follow the same ideas of the non-oriented case, however the strategies described are more elaborate and not generalizable to oriented matroids in general.

The complete characterization of the winning positions, which is known from [13] only for blocks, requires in that case, and in contrast with the undirected case, the analysis of all previous moves evidentiating the complexity of the analysis of the directed case.

In the next paragraphs we briefly review the main results of Hamidoune and Las Vergnas.

In what follows, we shall call the JOIN player in the directed games d-JOIN. Also the directed Shannon’s switching game, introduced in [12], will be called Hamidoune-Las Vergnas switching game.

3.1 Hamidoune-Las Vergnas Switching Game (G; e)

Let (G; e) be a graph (or a digraph) with a distinguished arc e = (x, y), not subject to play. Two players d-JOIN and CUT play alternately choosing one unplayed edge of the graph. d-JOIN directs the chosen edge and CUT deletes the chosen edge. d-JOIN wins if he succeeds in directing a path from x to y. CUT wins otherwise.

It is clear that we can import several results from Lehman’s study of the undirected case namely that a winning strategy for CUT in the associated undirected game (G; e) must be a winning strategy for CUT in the directed game (G; e). The, non obvious question is then whether the existence of a winning strategy for JOIN in Shannon’s Game implies the existence of a strategy for d-JOIN in the corresponding Hamidoune-Las Vergnas Game or not.

Hamidoune and Las Vergnas, in [12] and [13], prove that this is the case. Although the winning strategies for the undirected game can not, in general, be adapted do the directed case they follow a similar approach, starting with the analysis of a directed TREE game, ARBORESCENCE, on a connected block.

3.2 ARBORESCENCE (G; x)

ARBORESCENCE is a game played on a connected graph G with a distinguished vertex x. The two players CUT and d-JOIN play as in Hamidoune-Las Vergnas directed switching game. In this case the objective of d-JOIN is to direct the edges of an arborescence rooted at x.

Lemma 2

ARBORESCENCE on a connected block is a d-JOIN game.

3.2.1 Hamidoune-Las Vergnas Strategy for d-JOIN Playing Second on a Connected Block [13]

This is the crucial step of the Hamidoune-Las Vergnas results. We use the short proof in [13] that works by induction on the number of edges of the block.

Let G be a connected block. If | E(G) | = 2 obvious. If | E(G) | > 2 and CUT deletes an edge c then either there is a nonempty connected block X of G ∖ c incident to x or not.

In the first case G ^′, the subgraph induced by X, and $G^{{\prime\prime}}:= G/X$ are both connected blocks. By induction d-JOIN has winning strategies, Σ ^′ and Σ ^{′ ′}, for winning playing second, resp. in G ^′ and in G ^{′ ′}. The strategy of d-JOIN in G is the following: if the move c of CUT falls into X he responds directing an edge j given by strategy Σ ^′, if the move c falls into E(G)∖ X he answers directing an edge according to strategy Σ ^{′ ′}.

In the second case, G itself is the only connected block incident to x. In this case d-JOIN must respond to the move c of CUT by directing one edge j of G ∖ c incident to x (outgoing from x).

The game restarts with G replaced by $G_{1}:= G\setminus c/j$.

Example 1

In this example we play ARBORESCENCE in the connected block represented in the next Fig. 3a. The player d-JOIN plays second and wins using the strategy described in the proof of the Lemma. The i-th moves of CUT is denoted c _i and the i-th move of d-JOIN is denoted j _i .

The first move of CUT is c ₁ = 8. Since the smallest block incident to x is G itself, JOIN responds directing one edge incident to x, outgoing from x. d-JOIN played the edge j ₁ = 7 in the first figure. The game continues in $G1:= G\setminus c_{1}/j_{1}$ represented in Fig. 3b.

Fig. 3

Game played on a block with d-JOIN answering with Hamidoune-Las Vergnas strategy

CUT’s second move is c ₂ = 2. Now there is a connected block incident to x contained in $G_{1}\setminus c_{2}$, namely the block with edges X = { 1, 5}. According to the above strategy d-JOIN plays in $G_{1}'':= G_{1}/X$. Since the edge c ₂ = 2 is contained in the block $X_{1} =\{ c_{2} = 2,6\}$ of $G_{1}^{{\prime}}$, incident to x, according to the above strategy d-JOIN answers j ₂ = 6.

The game continues in the graph $G_{2} = G1\setminus c_{2}/j_{2}$, represented in Fig. 4a.

Fig. 4

Game played on a block with d-JOIN answering with Hamidoune-Las Vergnas strategy

The reader may easily see from G ₂ that, according to the strategy defined, the answer to CUT’s move c ₃ = 3 must be j ₃ = 4. The last Fig. 4b, represents $G_{3} = G_{2}\setminus c_{3}/j_{3}$, and it is clear that JOIN’s answer to c ₄ = 1 must be j ₄ = 5.

In Fig. 5 we have represented all the moves of the previous game in the original graph G.

Fig. 5

The previous ARBORESCENCE game in the original graph

The next Theorem is a direct consequence of the above lemma:

Theorem 3 (Classification of ARBORESCENCE and Hamidoune-Las Vergnas Switching Game [12, 13])

• 1. ARBORESCENCE in a connected graph G with root x is a d-JOIN game (resp. a CUT game or a NEUTRAL game) if and only if TREE is a JOIN game on G (resp. a CUT game or a NEUTRAL game on G).

• 2. A Hamidoune-Las Vergnas switching game (G; e ) is a d-JOIN game (resp. a CUT game or a NEUTRAL game) if and only if the corresponding undirected switching game is a JOIN game on G (resp. a CUT game or a NEUTRAL game on G).

We point out that from a computational point of view all the algorithms involved in evaluating a position and playing strategically any one of the unoriented games, TREE or Shannon’s switching game, are polynomial time algorithms. For the directed games, ARBORESCENCE and Hamidoune-Las Vergnas switching game, this is not known except in very particular cases [12]. The reason being that there is no general theorem characterizing all the winning positions at some point of the game.

Since TREE and Shannon switching games have natural generalized versions in terms of matroids, one would expect that Hamidoune-Las Vergnas switching game and ARBORESCENCE had a natural generalized version in terms of oriented matroids. Although ARBORESCENCE, at least so far, has no natural generalization to oriented matroids Hamidoune-Las Vergnas switching game does have. In the next paragraph we consider the generalization of both switching games to configurations of (real) vectors a particular case of matroids and oriented matroids.

The interested reader may consult [3] for an introduction to oriented matroids.

3.3 Shannon Switching Game, TREE and Hamidoune-Las Vergnas Switching Game on Configurations of Vectors

Shannon switching game (V;e) and TREE on a configuration of vectors are particular cases of the generalized versions of the games for matroids. The board instead of a graph is now a (finite) configuration of vectors V in some linear space over an arbitrary field. In both games the two players JOIN and CUT choose alternately one unplayed vector of V, CUT deletes it, JOIN reinforces/marks it.

In Shannon’s switching game (V, e), where e is a distinguished vector not subject to play, JOIN wins if he succeeds in marking a set of vectors whose linear span contains e. CUT wins otherwise.

In TREE on a configuration of vectors V, JOIN wins if he succeeds in marking a base of the linear span of V.

Lehman’s results [15] on Shannon’s switching game and TREE, namely Theorems 1 and 2 of the last section, hold for the more general games on matroids and therefore on configurations of vectors which correspond to coordinatizable matroids (see [17, 18]). We recall that a matroid is a block if it the union of two disjoint bases. In terms of coordinatizable matroids or configurations vectors this translates as: a configuration V of vectors of some linear space is a block iff V it is the union of two disjoint bases of the linear span of V.

Concerning the directed versions of these games, Hamidoune-Las Vergnas switching game and ARBORESCENCE, only the first has a generalization to configurations of vectors necessarily over an ordered field which may be assumed to be the reals.

3.3.1 Hamidoune-Las Vergnas Switching Game (V; e) on a Configuration of Vectors

Let (V; e) be a configuration of vectors of $\mathbb{R}^{d}$, e a distinguished vector not subject to play. The two players CUT and d-JOIN choose alternately one unplayed vector. CUT deletes it and d-JOIN decides if he leaves the vector or if he replaces it by its opposite before marking the chosen one.

The objective of d-JOIN is to capture the distinguished vector e inside the positive cone spanned by his marked vectors.

We recall that the following conjecture of Hamidoune and Las Vergnas is open even for configurations of real vectors:

Conjecture 1 (Hamidoune-Las Vergnas [12])

The classification of a directed switching game (M; e) on an oriented matroid M is the same as the classification of the associated undirected game $(\underline{M};e)$ on the underlying matroid $\underline{M}$. More precisely, a directed switching game (M; e) is:

• 1. a JOIN game if and only if there is a block of $\underline{M}$ spanning but not containing e.

• 2. a CUT game if and only if there is a block of $\underline{M}^{{\ast}}$ spanning but not containing e.

• 3. a NEUTRAL game if and only if both $\underline{M}$ and $\underline{M}^{{\ast}}$ have blocks containing e.

The structure of the positive cones spanned by a configuration of vectors is encoded by the associated oriented matroid.

In the case of configurations of vectors corresponding to graphs, and since graphic matroids have a unique class of orientations [4] or [3], the structure of positive cones is actually encoded in the underlying matroid.

The opposite situation occurs on configurations of vectors admitting many orientation classes. This is the case of the uniform matroids, U _n, d corresponding to configurations of n vectors in general position in $\mathbb{R}^{d}$ (every d-subset of vectors is a base of $\mathbb{R}^{d}$). An important step would be to understand Hamidoune-Las Vergnas conjecture in this class of oriented matroids.

Notice that because Lehman’s results hold for matroids, in order to prove the conjecture for uniform matroids one only needs to prove that d-JOIN has a winning strategy playing first when playing in a block, i.e. in an oriented uniform matroid U _2d, d .

Example 2

Shannon and Hamidoune-Las Vergnas switching games on a configuration of vectors that is a block.

The next figure, Figure 6, represents a configuration (V; e) of four vectors in general position of $\mathbb{R}^{2}$. The corresponding matroid and oriented matroid are U _4, 2 and one of its orientations. This is a first example which is not included in Theorem 3, because U _4, 2 is not the matroid of cycles of a graph [17, 18] (Fig. 6).

Fig. 6

A configuration (V; e) of 4 vectors in general position in $\mathbb{R}^{2}$

3.3.1.1 Analysis of the Shannon Switching Game (V; e)

In this game JOIN playing first wins, independently of how he plays. In fact, JOIN, starting first will mark two vectors $j_{1},j_{2} \in \{\mathbf{1,2,3}\}$. Every subset of two vectors of {1,2,3} is an (unordered) basis of $\mathbb{R}^{2}$ and therefore $\{j_{1},j_{2},e\}$ contains (actually is) a minimal linearly dependent subset of V, i.e. a circuit of the matroid U _4, 2 containing e.

3.3.1.2 Analysis of the Hamidoune-Las Vergnas Switching Game (V; e)

In this game d-JOIN playing first has a winning strategy. In contrast with the non oriented case d-JOIN must define carefully his strategy. Notice that if in his first move d-JOIN marks one of the vectors 1 or its opposite, −1, he may loose. In fact, if he marks 1, CUT eliminates 2 and e does not belong to poscone({1,3}) nor to poscone({1,−3}) so d-JOIN loses. Similarly if he plays −1, CUT wins responding 3.

The winning strategy for d-JOIN consists in playing in the first move either 2 or −3. Only playing in this way he guarantees that he has a good answer to every possible move of CUT.

Recently, Chatelain and Ramirez [8], extending previous results of Forge and Vielleiribière [10], proved that d-JOIN has a winning strategy playing first in the orientations of U _2d, d that are obtained as unions of rank 1/or rank 2 uniform oriented matroids. We point out that the oriented matroids arising in this way all correspond to vector configurations of vectors in general position in some $\mathbb{R}^{d}$ and do not cover all the possible orientations of U _2d, d .

The Hamidoune-Las Vergnas conjecture, for oriented matroids, even for configurations of vectors, remains open.