  We propose a class of two person perfect information games based on weighted
graphs. One of these games can be described in terms of a round pizza which is
cut radially into pieces of varying size. The two players alternately take
pieces subject to the following rule: Once the first piece has been chosen, all
subsequent selections must be adjacent to the hole left by the previously taken
pieces. Each player tries to get as much pizza as possible. The original pizza
problem was to settle the conjecture that Player One can always get at least
half of the pizza. The conjecture turned out to be false. Our main result is a
complete solution of a somewhat simpler class of games, concatenations of
stacks and two-ended stacks, and we provide a linear time algorithm for this.
The algorithm and its output can be described without reference to games. It
produces a certain kind of partition of a given finite sequence of real
numbers. The conditions on the partition involve alternating sums of various
segments of the given sequence. We do not know whether these partitions have
applications outside of game theory. The algorithm leads to a quadratic time
algorithm which gives the value and an optimal initial move for pizza games. We
also provide some general theory concerning the semigroup of equivalence
classes of graph games.
