CDAM Research Report, LSE-CDAM-2008-18
Accumulation Games on Graphs
Steve Alpern and Robbert FokkinkAccumulation games on discrete locations were introduced by W. Ruckle and K. Kikuta. The Hider secretly distributes his total wealth h>1 over locations 1, 2,...,n. The Searcher con.scates 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).
This paper takes the hiding locations to be the nodes of a graph and restricts the node sets 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.
A PDF file (234 kB) with the full contents of this report can be downloaded by clicking here.
Alternatively, if you would like to get a free hard copy of this report, please send the number of this report, LSE-CDAM-2008-18, together with your name and postal address to:
CDAM Research Reports Series
Centre for Discrete and Applicable Mathematics
London School of Economics
London WC2A 2AE, U.K.
Phone: +44(0)-20-7955 7494.
Fax: +44(0)-20-7955 6877.
|Introduction to the CDAM Research Report Series.|