Occupation games on graphs in which the second player takes almost all vertices
Given a connected graph G=(V,E) G = ( V , E ) , two players take turns occupying vertices v?V v ? V by placing black and white tokens so that the current vertex sets B,W?V B , W ? V are disjoint, B?W=0? B ? W = 0? , and the corresponding induced subgraphs G[B] G [ B ] and G[W] G [ W ] are connected any time. A player must pass whenever (s)he has no legal move. (Obviously, after this, the opponent will take all remaining vertices, since G G is assumed connected.) The game is over when all vertices are taken, V=B??W? V = B ? ? W ? . Then, Black and White get b=|B?|/|V| b = | B ? | / | V | and w=|W?|/|V| w = | W ? | / | V | , respectively. Thus, the occupation game is one-sum, b+w=1 b + w = 1 , and we could easily reduce it to a zero-sum game by simply shifting the payoffs, b?=b?1/2,w?=w?1/2 b ? = b ? 1 / 2 , w ? = w ? 1 / 2 . Let us also notice that b?0 b ? 0 and w?0 w ? 0 ; moreover, b>0 b > 0 and w>0 w > 0 whenever |V|>1 | V | > 1 . [Let us remark that the so-called Chinese rules define similar payoffs for the classic game of GO, yet, the legal moves are defined in GO differently.] Like in GO, we assume that Black begins. It is easy to construct graphs in which Black can take almost all vertices, more precisely, for each ?>0 ? > 0 there is a graph G G for which b>1?? b > 1 ? ? . In this paper we show that, somewhat surprisingly, there are also graphs in which White can take almost all vertices.
occupation games go