Randomized Minmax Regret for Combinatorial Optimization Under Uncertainty

Abstract

The minmax regret problem for combinatorial optimization under uncertainty\ncan be viewed as a zero-sum game played between an optimizing player and an\nadversary, where the optimizing player selects a solution and the adversary\nselects costs with the intention of maximizing the regret of the player. The\nexisting minmax regret model considers only deterministic solutions/strategies,\nand minmax regret versions of most polynomial solvable problems are NP-hard. In\nthis paper, we consider a randomized model where the optimizing player selects\na probability distribution (corresponding to a mixed strategy) over solutions\nand the adversary selects costs with knowledge of the player's distribution,\nbut not its realization. We show that under this randomized model, the minmax\nregret version of any polynomial solvable combinatorial problem becomes\npolynomial solvable. This holds true for both the interval and discrete\nscenario representations of uncertainty. Using the randomized model, we show\nnew proofs of existing approximation algorithms for the deterministic model\nbased on primal-dual approaches. Finally, we prove that minmax regret problems\nare NP-hard under general convex uncertainty.\n