# Maximin without the min

Experience has shown that many scholars/analysts who are not at home with the modeling aspects of the maximin paradigm are surprised to learn that true-blue maximin models such as this

$\displaystyle z^{*}:= \max_{y\in Y}\min_{u\in \Pi(y)}\ \{g(y,u): C(y,u),\forall u\in \Pi(y)\}$

can have an equivalent phrasing, without the iconic inner $\displaystyle \min_{u\in \Pi(y)}$ operation. Here $C(y,u)$ represents a list of constraints on $(y,u)$ pairs.

The following result, that is used widely in game theory and robust optimization, explains how to dispose of this iconic operation:

$\textsc{Theorem}$.

$\displaystyle \min_{a\in A} h(a) \equiv \max_{\substack{a\in A\\ v\in \mathbb{R}}} \{v: v\le h(a)\}$

assuming that the $\min$ is attained on $A$, where $\mathbb{R}$ denotes the real line.

The $\equiv$ sign indicates that the two optimization problems are equivalent in the sense that they yield the same optimal value for the objective functions and the same optimal value(s) for the decision variable $a$. The optimal value of $v$ is equal to the optimal value of $h(a)$.

The following is then an immediate implication of the theorem:

$\textsc{Corollary}$.

$\begin{array}{rcl} \displaystyle z^{*} & \displaystyle := & \displaystyle \max_{y\in Y}\min_{u\in \Pi(y)}\ \{g(y,u): C(y,u),\forall u\in \Pi(y)\}\\ & \displaystyle \equiv & \displaystyle \max_{\substack{y\in Y\\ v\in \mathbb{R}}}\ \{v: v\le g(y,u), C(y,u),\forall u\in \Pi(y)\}\\ & \displaystyle \equiv & \displaystyle \max_{\substack{y\in Y\\ v\in \mathbb{R}}}\ \{v: CC(y,v,u),\forall u\in \Pi(y)\} \end{array}$

where $CC(y,v,u)$ consists of all the constraints in $C(y,u)$, as well as the additional constraint $v\le g(y,u)$.

Such formulations of maximin models are often called Mathematical Programming (MP) formulations. If you use maximin models often, you would do well to develop the skills to switch easily from the iconic formulations to the MP formulations and back.

More …