The Matroid Cup Game
Sungjin Im, Benjamin Moseley, Rudy Zhou · Operations Research Letters · 2021
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(logn) 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(rn) 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.