The maximin connection

Wald’s famous maximin model (circa 1940) is based on a worst case approach to uncertainty/variability. The Maximin Rule argues as follows:

Rank alternatives according to their worst outcome. Hence, select the alternative whose worst outcome is at least as good as the worst outcome of any other alternative.

For our purposes, the most suitable formulation of the maximin is that of the following generic model:

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

where

• $Y$ = set of available alternatives.
• $u$ = state of Nature.
• $\Pi(y)$ = set of states associated with alternative $y$.
• $C(x,u)$ = list of constraints on $(y,u)$ pairs.
• $g(y,u)$ = outcome generated by alternative $y$ and state $u$.

We shall refer to this formulation as the full Monty model.

This model seeks robustness with respect to both the outcomes $g(y,u)$ — via the $\displaystyle \min_{u\in Pi(y)}$ operation — and the constraints $con(y,u)$ — via the clause $C(y,u), \forall u\in \Pi(y)$.

Now, consider the rather simple case where robustness is sought only with respect to the constraints, namely the case where the outcome $g(y,u)$ is independent of the state $u$. In this case the full Monty model is simplified to

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

observing that since the outcome $f(y)$ is independent of the state $u$, the iconic $\displaystyle \min_{u\in \Pi(y)}$ operation is superfluous. We shall refer to this maximin model as the C model.

With this as background, it is straightforward to show that info-gap’s robustness model, namely

$\rho(x,\tilde{u}):= \displaystyle \max_{\rho\ge 0}\ \{\rho: r^{*}\le r(x,u),\forall u\in N(\rho,\tilde{u})\}$

is a simple maximin model, by demonstrating that it is an instance of the C model.

$\textsc{Theorem 1:}$ Info-gap’s robustness model is a simple instance of Wald’s maximin model, say the C model.

Proof.

Consider the instance of the C model that is based on the correspondence $y\equiv \rho$, namely let

$Y=[0,\infty);\ f(y) \equiv y;\ C(y,u) \equiv r^{*}\le r(x,u)$

$\Pi(y) \equiv N(y,\tilde{u})$

In this case, the C model — for given values of $x$ and $\tilde{u}$ — is as follows:

$\begin{array}{rl} \displaystyle z^{*}(x,\tilde{u}):= & \displaystyle \max_{y\in Y} \{f(y): C(y,u),\forall u\in \Pi(y)\}\\ \displaystyle \equiv & \displaystyle \max_{y\ge 0} \{y: r^{*} \le r(x,u),\forall u\in N(y,\tilde{u})\}\\ \displaystyle \equiv & \displaystyle \max_{\rho\ge 0} \{\rho: r^{*} \le r(x,u),\forall u\in N(\rho,\tilde{u})\} \ \ \textrm{QED}\end{array}$

Now consider the correspondence $y \equiv (x,\rho)$ and the specification

$Y=X\times [0,\infty);\ f(x,\rho) \equiv \rho;\ C(x,\rho,u) \equiv r^{*}\le r(x,u)$

$\Pi(x,\rho) \equiv N(\rho,\tilde{u})$

The corresponding instance of the C model is then as follows:

$\begin{array}{rl} \displaystyle z^{*} := & \displaystyle \max_{y\in Y} \{f(y): C(y,u),\forall u\in \Pi(y)\}\\ \displaystyle \equiv & \displaystyle \max_{\substack{x\in X\\\rho\ge 0}} \{y: r^{*} \le r(x,u),\forall u\in N(\rho,\tilde{u})\} \end{array}$

Observe that this is none other than info-gap’s decision model for robustness. Hence,

$\textsc{Theorem 2:}$ Info-gap’s decision model for robustness is an instance of Wald’s maximin model.

More …