Two-Stage Robust Optimization Problems with Two-Stage Uncertainty

We consider robust two-stage optimization problems, which can be considered as a game between the decision maker and an adversary. After the decision maker fixes part of the solution, the adversary chooses a scenario from a specified uncertainty set. Afterwards, the decision maker can react to this scenario by completing the partial first-stage solution to a full solution. We extend this classic setting by adding another adversary stage after the second decision-maker stage, which results in min-max-min-max problems, thus pushing two-stage settings further towards more general multi-stage problems. We focus on budgeted uncertainty sets and consider both the continuous and discrete case. In the former, we show that a wide range of robust combinatorial problems can be decomposed into polynomially many subproblems, which in turn can often be solved in polynomial time. For the latter, we prove NP-hardness for a wide range of problems, but note that the special case where first- and second-stage adversarial costs are equal can remain solvable in polynomial time.