Accumulation games on graphs

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