Accumulation games on discrete locations were introduced by Ruckle and Kikuta. The Hider secretly distributes his total wealth h ≥ 1 over locations 1,2,…,n. The Searcher confiscates the material from any r of these locations. The Hider wins if the wealth remaining at the n − r unsearched locations sums to at least 1; otherwise the Searcher wins. Their game models problems in which the Hider needs to have, after confiscation (or loss by natural causes), a sufficient amount of material (food, wealth, arms) to carry out some objective (survive the winter, buy a house, start an insurrection). The conjecture of Kikuta and Ruckle shows that there is always an optimal Hider strategy which places equal amounts of material on certain locations (and nothing on the rest) is still open and known to be hard. This article takes the hiding locations to be the nodes of a graph and restricts the node sets which the Searcher can remove to be drawn from a given family: the edges, the connected r‐sets, or some other given sets of nodes. This models the case where the pilferer, or storm, is known to act only on a set of close locations. Unlike the original game, our game requires mixed strategies. We give a complete solution for certain classes of graphs. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 64(1), 40–47 2014

Abstract We introduce the notion of a Utilitarian Postman (UP) path on a network Q as one which minimizes the expected time required to find a random (uniformly distributed) point, and show that UP paths must be used in a minimax search of a symmetric network. For any network Q, one may consider the zero‐sum search game Γ(Q) in which the (minimizing) Searcher picks a unit speed path S(t) in Q, the Hider picks a point H in Q, and the payoff is the meeting time T = min{t : S(t) = H}. We show first that if Q is symmetric (edge and vertex transitive), then it is optimal for the Hider to pick H uniformly in Q, so that the Searcher must follow a UP path. We then show that if Q is symmetric of odd degree, with n vertices and m unit length edges, the value V of Γ(Q) satisfies $ V \geq {m \over 2} + {n^{2}-2n \over 8m} $ , with equality if and only if (*): Q has a path P = v1, v2,…,vn−1 of distinct vertices, such that the edge set Q′ = Q−∪ (v2i,v2i+1) is connected. In this case, there is a UP path for Q consisting of P followed by an Eulerian path E of Q′. The condition (*) is satisfied by many symmetric graphs, including all complete graphs, complete bipartite graphs, hypercube graphs, high valency graphs, and the Petersen graph. We know of no odd degree symmetric graph not satisfying (*). © 2009 Wiley Periodicals, Inc. NETWORKS, 2009

Abstract We analyze the hide‐and‐seek game Γ ( G ) on certain networks G . The hider picks a hiding point y in G and the searcher picks a unit speed path S ( t ) in G , starting at any point S (0). The payoff in this zero‐sum game is the capture time T = T ( S , y ) = min{ t : S ( t ) = y }. Such games have been studied before, but mainly with the simplifying assumption that the searcher's starting point S (0) is specified and known to the hider. We call a network partly Eulerian if it consists of a tree (of length a and radius r ) to which a finite number of disjoint Eulerian networks (of total length b ) are attached, each at a single point. We show that for such networks, a strategy consisting equiprobably of a minimal (Chinese Postman) covering path and its reverse path is optimal for the searcher, while the optimal hider strategy is to assume that the searcher must start at the center of the tree, and to optimize in that (known) game. The value of the game Γ ( G ) is a + b /2 ‐ r . This simplifies and extends a similar result of Dagan and Gal for search games on trees. © 2008 Wiley Periodicals, Inc. NETWORKS, 2008

Abstract Let Q be a connected network with a distinguished (starting) point q0, whose are lengths sum to one. We associate with Q a “search value” V(Q) representing the expected time needed for a searcher, starting at q0 and moving at unit speed, to find a moving hider. We assume neither sees the other until they meet. We demonstrate that the “figure‐eight” network, consisting of two equal loops joined at a central starting point, has a search value not exceeding 15/16. This contradicts a conjecture of Gal that the search value of any network is at least 1. In the other direction, we show that V(Q) ≦ 6kD for a network with k edges and diameter D.