CDAM: Computational, Discrete and Applicable Mathematics@LSE

CDAM Research Report, LSE-CDAM-2008-18

September 2008

Accumulation Games on Graphs

Steve Alpern and Robbert Fokkink

Accumulation 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
Houghton Street
London WC2A 2AE, U.K.

Phone: +44(0)-20-7955 7494.
Fax: +44(0)-20-7955 6877.
Email: info@maths.lse.ac.uk

		Introduction to the CDAM Research Report Series.
		CDAM Homepage.

		CDAM Research Reports Series Centre for Discrete and Applicable Mathematics London School of Economics Houghton Street London WC2A 2AE, U.K.
		Phone: +44(0)-20-7955 7494. Fax: +44(0)-20-7955 6877. Email: info@maths.lse.ac.uk