  We consider a max-min variation of the classical problem of maximizing a
linear function over the base of a polymatroid. In our problem we assume that
the vector of coefficients of the linear function is not a known parameter of
the problem but is some vertex of a simplex, and we maximize the linear
function in the worst case. Equivalently, we view the problem as a zero-sum
game between a maximizing player whose mixed strategy set is the base of the
polymatroid and a minimizing player whose mixed strategy set is a simplex. We
show how to efficiently obtain optimal strategies for both players and an
expression for the value of the game. Furthermore, we give a characterization
of the set of optimal strategies for the minimizing player. We consider four
versions of the game and discuss the implications of our results for problems
in search, sequential testing and queueing.
