Modelo maximin de Wald

Modelo de toma de decisiones no probabilístico

En teoría de la decisión 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 menos malo. Es uno de los modelos más importantes en la toma de decisiones sólidas en general y en la optimización sólida en particular.

También se le conoce por una variedad de otros títulos, 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 minimiza el pago en . En muchas aplicaciones, el segundo jugador representa la incertidumbre. Sin embargo, existen 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 de programación matemática (MP) equivalente:

donde denota la línea real. ${\displaystyle \mathbb {R} }$

Como en la teoría de juegos , la peor recompensa asociada con la decisión , es decir ${\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

Inspirándose en la teoría de juegos, Abraham Wald desarrolló este modelo ^{[1] [2] [3]} como una aproximación a escenarios en los que hay un solo jugador (el que toma las decisiones). El jugador 2 muestra una actitud sombría ante 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 para dos 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 para dos personas , pero los jugadores eligen de forma secuencial. ${\displaystyle \max }$ ${\displaystyle \min }$

Con el establecimiento de la teoría de la decisión 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 frente a una incertidumbre severa. ^{[4] [5]} Es ampliamente utilizado en diversos campos como teoría de la decisión , teoría del control , economía , estadística , optimización robusta , investigación de operaciones , 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 línea real. Formalmente podemos establecer y . la foto 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

Hay muchos casos en los que es 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. ¿Henri debería llevar un paraguas? A Henri no le gusta llevar paraguas, pero le disgusta aún más mojarse. Su " matriz de pagos ", viendo esto como un juego de Maximin que enfrenta a Henri contra la Naturaleza, es la siguiente.

Al agregar 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 (mejor) peor caso cuando lleva paraguas. Por eso Henri se lleva su paraguas.

Variaciones sobre un tema

A lo largo de los años se ha desarrollado una variedad de modelos relacionados principalmente para moderar el enfoque pesimista dictado por la orientación del modelo al 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 de pago.

Modelos deterministas

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

Ejemplo

Sea un conjunto finito que represente posibles ubicaciones de una instalación pública "indeseable" (por ejemplo, un basurero), y denotemos un conjunto finito de ubicaciones en las proximidades de la instalación planificada, que representan viviendas existentes. ${\displaystyle D}$ ${\displaystyle S}$

Podría ser conveniente construir la instalación de modo que la distancia más corta desde 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 . Tenga en cuenta 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 los que sea deseable vivir cerca de la instalación, el objetivo podría ser minimizar la distancia máxima desde la instalación. Esto produce el siguiente problema minimax:

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

Estos son problemas genéricos de ubicación de instalaciones .

Modelos Maximin disfrazados.

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

Considere el siguiente problema:

Dado un conjunto finito y una función con 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 la brecha de información son ejemplos 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 de 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

Uno de los 'puntos débiles' del modelo Maximin es que la robustez que aporta tiene un precio . ^[10] Al ir 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 y donde . El modelo entonces es el siguiente: ${\displaystyle x''}$ ${\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

Considere 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 , 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. Los Anales de Matemáticas, 10(4), 299-326.
2. Wald, A. (1945). Funciones de decisión estadística que minimizan el máximo riesgo. Los Anales de Matemáticas, 46(2), 265-280.
3. Wald, A. (1950). Funciones de decisión estadística, John Wiley, Nueva York.
4. Resnik, MD (1987). Opciones: una introducción a la teoría de la decisión, University of Minnesota Press, Minneapolis.
5. francés, 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! Revista de financiación de riesgos, 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. Prensa de la Universidad de Princeton, Princeton.
10. Bertsimas D y Sim, M. (2004). El precio de la robustez. Investigación de operaciones, 52(1), 35-53.
11. Salvaje, 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 sólidos para introducciones inciertas de especies invasoras. Revista de Gestión Ambiental, 89(4), 293–299.
13. Jonathan Rosenhead, Martin Elton, Shiv K. Gupta. (1972). Robustez y Optimidad como Criterios para las Decisiones Estratégicas. Investigación operativa trimestral, 23(4), 413-431.
14. Sniedovich, M. (2010). Una visión panorámica de la teoría de la decisión sobre la brecha de información. Revista de financiación de riesgos, 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 del peor de los casos y aplicaciones a la gestión de riesgos, Princeton University Press, Princeton.