The difference between max-min and min-max

Question

I am solving two-stage optimization problems in the form of $$\max_{x \in X}\min_{y \in Y} f(x,y),$$ where $f(x,y)$ is the solution of a mixed integer linear program (MIP). As the constraints of the MIP link the $x$ and $y$ elements, it is clear that we cannot apply the classic minimax theorem to interchange the minimization and the maximization. (Actually, I am solving a trilevel optimization problem and interchanging the minimization and the maximization will be very helpful).

We all know that the minimax theorem states that $$\max_{x \in X}\min_{y \in Y} f(x,y) \leq \min_{y \in Y}\max_{x \in X} f(x,y)$$ for any function $f$ mapping the $X,Y$ space to a real set (assuming the max and min can be attained).

My question is the following: In the above sketched case, this equation will not be strict (i.e., it won't hold with equality). However, are there any particular useful results on how large this gap might be, both worst-case as well as numerically? If it is not too big (in general), it might suffice as a bound on the larger (and not relevant for this question) trilevel optimization problem.

Answer 1

While these equations have many interpretations in OR (e.g. robust optimization), in this case I like to understand what happens here using a Game Theory perspective. These two equations can be interpreted as a Stackelberg game, sometimes referred two as leader follower games. Consider a two player zero sum game, where player 1 has to pick an element from $X$ maximizing the outcome and player 2 has to pick an element from $Y$ minimizing the outcome. Let's say we have the following game matrix where $X$ is the set of rows and $Y$ is the set of columns: $$\left[ \begin{array}{cc} a & 0 \\ 0 & b \end{array} \right]$$ We assume w.l.o.g. that $a > b > 0$. Now we have that $$\max_{x\in X}\min_{y \in Y} f(x,y) = 0$$ as this corresponds to the situation where player 1 picks first and player 2 responds, and player 2 can always choose the column such that the outcome is $0$. On the right hand side, we get $$\min_{y \in Y}\max_{x \in X} f(x,y) = b$$ as now player 2 gets to pick first and player 1 responds. Obviously, player 2 prefers $b$ over $a$, but can't prevent the first player from getting a positive outcome. Since we can pick $a$ and $b$ arbitrarily large, this gap is clearly unbounded, both in a relative and absolute sense.

These kind of problems are particularly nasty if you are not able to exploit any special structure of your function, which is only possible if you are somewhat lucky, e.g. you can apply a strong duality results somewhere or have additional information that you can use to bound $f$. In fact, these problems are widely believed to be more difficult than NP-hard problems. Gerhard Woeginger gave a really good keynote on the difficulty of these multilevel problems at EURO2018 in Valencia from a computational complexity perspective (he talks mostly about universal and existential quantors, but the idea is the same). He mentions a few rare cases where you end up being lucky, and others where basically no-one knows what to do. There is a video available on the EURO2018 website.