Modelo maximin de Wald

Modelo de toma de decisiones no probabilístico

En teoría de decisiones y teoría de juegos , el modelo maximin de Wald es un modelo de toma de decisiones no probabilístico según el cual las decisiones se clasifican en función de sus peores resultados: la decisión óptima es aquella con el peor resultado posible. Es uno de los modelos más importantes en la toma de decisiones robusta en general y en la optimización robusta en particular.

También se conoce con otros nombres, como regla maximin de Wald, principio maximin de Wald, paradigma maximin de Wald y criterio maximin de Wald. A menudo se utiliza " minimax " en lugar de "maximin".

Definición

Este modelo representa un juego de 2 personas en el que el jugador juega primero. En respuesta, el segundo jugador selecciona el peor estado en , es decir, un estado en que minimice la recompensa sobre en . En muchas aplicaciones, el segundo jugador representa la incertidumbre. Sin embargo, hay modelos maximin que son completamente deterministas. ${\displaystyle \max }$ ${\displaystyle S(d)}$ ${\displaystyle S(d)}$ ${\displaystyle f(d,s)}$ ${\displaystyle s}$ ${\displaystyle S(d)}$

El modelo anterior es el formato clásico del modelo maximin de Wald. Existe un formato equivalente de programación matemática (PM):

donde denota la recta real. ${\displaystyle \mathbb {R} }$

Al igual que en la teoría de juegos , el peor resultado asociado con la decisión , a saber, ${\displaystyle d}$

${\displaystyle v(d):=\min _{s\in S(d)}f(d,s)\ ,\ d\in D}$

se llama nivel de seguridad de decisión . ${\displaystyle d}$

La versión minimax del modelo se obtiene intercambiando las posiciones de las operaciones y en el formato clásico: ${\displaystyle \max }$ ${\displaystyle \min }$

${\displaystyle v^{\circ }:=\min _{d\in D}\max _{s\in S(d)}f(d,s).}$

El formato MP equivalente es el siguiente:

${\displaystyle v^{\circ }:=\min _{d\in D,\,z\in \mathbb {R} }\{z:z\geq f(d,s),\forall s\in S(d)\}}$

Historia

Inspirado por la teoría de juegos, Abraham Wald desarrolló este modelo ^{[1] [2] [3]} como un enfoque para escenarios en los que solo hay un jugador (el que toma las decisiones). El jugador 2 muestra un enfoque sombrío de la incertidumbre. En el modelo maximin de Wald, el jugador 1 (el jugador) juega primero y el jugador 2 (el jugador) conoce la decisión del jugador 1 cuando selecciona su decisión. Esta es una simplificación importante del clásico juego de suma cero de 2 personas en el que los dos jugadores eligen sus estrategias sin conocer la elección del otro jugador. El juego del modelo maximin de Wald también es un juego de suma cero de 2 personas , pero los jugadores eligen secuencialmente. ${\displaystyle \max }$ ${\displaystyle \min }$

Con el establecimiento de la teoría de decisiones moderna en la década de 1950, el modelo se convirtió en un ingrediente clave en la formulación de modelos de toma de decisiones no probabilísticos ante una incertidumbre severa. ^{[4] [5]} Se utiliza ampliamente en diversos campos como la teoría de decisiones , la teoría de control , la economía , las estadísticas , la optimización robusta , la investigación de operaciones , la filosofía , etc. ^{[6] [7]}

Ejemplo

Uno de los ejemplos más famosos de un modelo Maximin/Minimax es

${\displaystyle \min _{x\in \mathbb {R} }\max _{y\in \mathbb {R} }\ \{x^{2}-y^{2}\}}$

donde denota la recta real. Formalmente podemos establecer y . La imagen es esta ${\displaystyle \mathbb {R} }$ ${\displaystyle D=S(d)=\mathbb {R} }$ ${\displaystyle f(d,s)=d^{2}-s^{2}}$

La solución óptima es el punto de silla (rojo) . ${\displaystyle (x,y)=(0,0)}$

Tablas de decisión

Existen muchos casos en los que resulta conveniente "organizar" el modelo Maximin/Minimax como una "tabla". La convención es que las filas de la tabla representan las decisiones y las columnas representan los estados.

Ejemplo

Henri va a dar un paseo. Puede que brille el sol o puede que llueva. ¿Debería Henri llevar paraguas? A Henri no le gusta llevar paraguas, pero le disgusta aún más mojarse. Su " matriz de pagos ", que considera esto como un juego de Maximin que enfrenta a Henri contra la Naturaleza, es la siguiente.

Agregando una   columna de Peor pago y una columna de Mejor peor pago   a la tabla de pagos, obtenemos

El peor de los casos, si Henri sale sin paraguas, es definitivamente peor que el peor de los casos (el mejor) si lleva paraguas. Por lo tanto, Henri lleva su paraguas consigo.

Variaciones sobre un tema

A lo largo de los años se han desarrollado diversos modelos relacionados, principalmente para moderar el enfoque pesimista dictado por la orientación del modelo hacia el peor de los casos. ^{[4] [5] [8] [9] [10]} Por ejemplo,

El arrepentimiento minimax de Savage

El modelo de arrepentimiento minimax de Savage ^[11] está asociado con los arrepentimientos por los pagos.

Modelos deterministas

Los conjuntos de estados no necesariamente representan incertidumbre. Pueden representar variaciones (deterministas) en el valor de un parámetro. ${\displaystyle S(d),d\in D,}$

Ejemplo

Sea un conjunto finito que representa posibles ubicaciones de una instalación pública "indeseable" (por ejemplo, un vertedero de basura), y sea un conjunto finito de ubicaciones en el vecindario de la instalación planificada, que representan viviendas existentes. ${\displaystyle D}$ ${\displaystyle S}$

Tal vez sea conveniente construir la instalación de manera que la distancia más corta a una vivienda existente sea la mayor posible. La formulación maximin del problema es la siguiente:

${\displaystyle \max _{d\in D}\min _{s\in S}dist(d,s)}$

donde denota la distancia de desde . Nótese que en este problema no varía con . ${\displaystyle dist(d,s)}$ ${\displaystyle s}$ ${\displaystyle d}$ ${\displaystyle S(d)}$ ${\displaystyle d}$

En los casos en que sea deseable vivir cerca de las instalaciones, el objetivo podría ser minimizar la distancia máxima desde las mismas. Esto genera el siguiente problema de minimax:

${\displaystyle \min _{d\in D}\max _{s\in S}dist(d,s)}$

Se trata de problemas genéricos de ubicación de instalaciones .

Modelos Maximin disfrazadas

La experiencia ha demostrado que la formulación de modelos maximin puede ser sutil en el sentido de que problemas que "no parecen" problemas maximin pueden formularse como tales.

Ejemplo

Consideremos el siguiente problema:

Dado un conjunto finito y una función de valor real en , encuentre el subconjunto más grande de tal que   para cada en este subconjunto. ${\displaystyle X}$ ${\displaystyle g}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle g(x)\leq 0}$ ${\displaystyle x}$

La formulación maximin de este problema, en formato MP, es la siguiente:

${\displaystyle \max _{Y\subseteq X}\ \{|Y|:g(x)\leq 0,\forall x\in Y\}.}$

Problemas genéricos de este tipo aparecen en el análisis de robustez. ^{[12] [13]}

Se ha demostrado que el modelo de radio de estabilidad y el modelo de robustez de info-gap son instancias simples del modelo maximin de Wald. ^[14]

Modelos maximin restringidos

Las restricciones se pueden incorporar explícitamente en los modelos maximin. Por ejemplo, el siguiente es un problema maximin restringido planteado en el formato clásico

${\displaystyle v^{*}:=\max _{d\in D}\min _{s\in S(d)}\ \{f(d,s):g(d,s)\leq 0,\forall s\in S(d)\}.}$

Su formato MP equivalente es el siguiente:

${\displaystyle v^{*}:=\max _{d\in D,\,z\in \mathbb {R} }\{z:z\leq f(d,s),g(d,s)\leq 0,\forall s\in S(d)\}.}$

Estos modelos son muy útiles en la optimización robusta .

El precio de la robustez

Una de las "debilidades" del modelo Maximin es que la robustez que proporciona tiene un precio . ^[10] Al jugar a lo seguro, el modelo Maximin tiende a generar decisiones conservadoras, cuyo precio puede ser alto. El siguiente ejemplo ilustra esta importante característica del modelo.

Ejemplo

Supongamos que hay dos opciones, x' y ⁠ ⁠ ${\displaystyle x''}$ , y donde . El modelo es entonces el siguiente: ${\displaystyle S(x')=S(x'')=[a,b]}$

${\displaystyle \max _{d\in D}\min _{s\in S(d)}f(d,s)=\max _{d\,',d\,''}\ \min _{a\leq s\leq b}f(d,s)=\max \ \{\min _{a\leq s\leq b}f(d\,',s),\min _{a\leq s\leq b}f(d\,'',s)\}}$

Algoritmos

No existen algoritmos de propósito general para la solución de problemas maximin. Algunos problemas son muy sencillos de resolver, otros son muy difíciles. ^{[9] [10] [15] [16]}

Ejemplo

Consideremos el caso en el que la variable de estado es un "índice", por ejemplo let for all . El problema maximin asociado es entonces el siguiente: ${\displaystyle S(d)=\{1,2,\dots ,k\}}$ ${\displaystyle d\in D}$

${\displaystyle {\begin{aligned}\max _{d\in D}\min _{s\in S(d)}f(d,s)&=\max _{d\in D}\min _{1\leq s\leq k}\{f_{1}(d),\dots ,f_{k}(d)\}\\&=\max _{d\in D,z\in \mathbb {R} }\{z:z\leq f_{s}(d),\forall s=1,2,\dots ,k\}\end{aligned}}}$

dónde . ${\displaystyle f_{s}(d)\equiv f(d,s)}$

Si todas las funciones son lineales y están especificadas por un sistema de restricciones lineales en , entonces este problema es un problema de programación lineal que puede resolverse mediante algoritmos de programación lineal como el algoritmo simplex . ${\displaystyle d\in \mathbb {R} ^{n}}$ ${\displaystyle f_{s},s=1,2,\dots ,k,}$ ${\displaystyle d\in D}$ ${\displaystyle d}$

Referencias

1. Wald, A. (1939). Contribuciones a la teoría de la estimación estadística y la prueba de hipótesis. Annals of Mathematics, 10(4), 299-326.
2. Wald, A. (1945). Funciones de decisión estadística que minimizan el riesgo máximo. Annals of Mathematics, 46(2), 265-280.
3. Wald, A. (1950). Funciones de decisión estadística, John Wiley, NY.
4. Resnik, MD (1987). Opciones: una introducción a la teoría de la decisión, University of Minnesota Press, Minneapolis.
5. French, S. (1986). Teoría de la decisión: una introducción a las matemáticas de la racionalidad, Ellis Horwood, Chichester.
6. Sniedovich, M. (2007). El arte y la ciencia de modelar la toma de decisiones en condiciones de incertidumbre severa. Toma de decisiones en manufactura y servicios, 1(1-2), 111-136.
7. Sniedovich, M. (2008). El modelo maximin de Wald: ¡un tesoro disfrazado! Journal of Risk Finance, 9(3), 287-91.
8. Kouvelis P y Yu G. (1997). Optimización discreta robusta y sus aplicaciones, Kluwer, Boston.
9. Ben-Tal, A, El Gaoui, L, Nemirovski, A. (2009). Optimización robusta. Princeton University Press, Princeton.
10. Bertsimas D, y Sim, M. (2004). El precio de la robustez. Investigación de operaciones, 52(1), 35-53.
11. Savage, L. (1951). La teoría de la decisión estadística. Revista de la Asociación Estadounidense de Estadística, 46, 55–67.
12. L. Joe Moffitt, John K. Stranlund y Craig D. Osteen (2008). Protocolos de detección robustos para introducciones inciertas de especies invasoras. Journal of Environmental Management, 89(4), 293–299.
13. Jonathan Rosenhead, Martin Elton, Shiv K. Gupta. (1972). Robustez y optimalidad como criterios para decisiones estratégicas. Operational Research Quarterly, 23(4), 413-431.
14. Sniedovich, M. (2010). Una perspectiva general de la teoría de decisiones basada en la brecha de información. Journal of Risk Finance, 11(3), 268-283.
15. Reemstem, R. y R\"{u}ckmann, J. (1998). Programación semiinfinita, Kluwer, Boston.
16. Rustem, B. y Howe, M. (2002). Algoritmos para el diseño en el peor de los casos y aplicaciones para la gestión de riesgos, Princeton University Press, Princeton.