The Matroid Cup Game

Abstract In this paper we introduce the Matroid Cup Game. This cup game generalizes the One- and p-Cup Games. We show that a natural greedy strategy maintains max fill O ( log ⁡ n ) in the Matroid Cup Game with mild resource augmentation. Further, we introduce a new objective for cup game: the total water, which is the amount of water across all cups. We develop a novel Emptier strategy that maintain O ( r n ) total water without resource augmentation. We also reveal a novel relationship between max fill and total water, which leads to an intuitive analysis of the max fill bounds in the One- and p-Cup Games.