Randomized min-max optimization: The exact risk of multiple cost levels