Teorema del minimax

Da condiciones que garantizan que la desigualdad máxima-mínima se cumple con la igualdad

En el área matemática de la teoría de juegos y de la optimización convexa , un teorema minimax es un teorema que afirma que

${\displaystyle \max _{x\in X}\min _{y\in Y}f(x,y)=\min _{y\in Y}\max _{x\in X}f(x,y)}$

bajo ciertas condiciones en los conjuntos y y en la función . ^[1] Siempre es cierto que el lado izquierdo es como máximo el lado derecho ( desigualdad máx-mín ) pero la igualdad solo se cumple bajo ciertas condiciones identificadas por los teoremas minimax. El primer teorema en este sentido es el teorema minimax de von Neumann sobre juegos de suma cero para dos jugadores publicado en 1928, ^[2] que se considera el punto de partida de la teoría de juegos . Se cita a von Neumann diciendo " Hasta donde puedo ver, no podría haber teoría de juegos... sin ese teorema... pensé que no había nada que valiera la pena publicar hasta que se demostrara el teorema minimax ". ^[3] Desde entonces, han aparecido en la literatura varias generalizaciones y versiones alternativas del teorema original de von Neumann. ^{[4] [5]} ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle f}$

Funciones bilineales y juegos de suma cero

El teorema original de von Neumann ^[2] fue motivado por la teoría de juegos y se aplica al caso donde

• ${\displaystyle X}$y son símplex estándar : y , y ${\displaystyle Y}$ ${\textstyle X=\{(x_{1},\dots ,x_{n})\in [0,1]^{n}:\sum _{i=1}^{n}x_{i}=1\}}$ ${\textstyle Y=\{(y_{1},\dots ,y_{n})\in [0,1]^{m}:\sum _{j=1}^{m}y_{j}=1\}}$
• ${\displaystyle f(x,y)}$es una función lineal en ambos argumentos (es decir, es bilineal ) y por lo tanto puede escribirse para una matriz finita , o equivalentemente como . ${\displaystyle f}$ ${\displaystyle f(x,y)=x^{\mathsf {T}}Ay}$ ${\displaystyle A\in \mathbb {R} ^{n\times m}}$ ${\textstyle f(x,y)=\sum _{i=1}^{n}\sum _{j=1}^{m}A_{ij}x_{i}y_{j}}$

Bajo estos supuestos, von Neumann demostró que

${\displaystyle \max _{x\in X}\min _{y\in Y}x^{\mathsf {T}}Ay=\min _{y\in Y}\max _{x\in X}x^{\mathsf {T}}Ay.}$

En el contexto de los juegos de suma cero para dos jugadores , los conjuntos y corresponden a los conjuntos de estrategias del primer y segundo jugador, respectivamente, que consisten en loterías sobre sus acciones (las llamadas estrategias mixtas ), y sus pagos están definidos por la matriz de pagos . La función codifica el valor esperado del pago para el primer jugador cuando el primer jugador juega la estrategia y el segundo jugador juega la estrategia . ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle A}$ ${\displaystyle f(x,y)}$ ${\displaystyle x}$ ${\displaystyle y}$

Funciones cóncavas-convexas

La función f ( x , y ) = x ² − y ² es cóncava-convexa.

El teorema minimax de von Neumann se puede generalizar a dominios que son compactos y convexos, y a funciones que son cóncavas en su primer argumento y convexas en su segundo argumento (conocidas como funciones cóncavo-convexas). Formalmente, sean y conjuntos convexos compactos . Si es una función continua que es cóncava-convexa, es decir ${\displaystyle X\subseteq \mathbb {R} ^{n}}$ ${\displaystyle Y\subseteq \mathbb {R} ^{m}}$ ${\displaystyle f:X\times Y\rightarrow \mathbb {R} }$

${\displaystyle f(\cdot ,y):X\to \mathbb {R} }$es cóncava para cada fijo , y ${\displaystyle y\in Y}$

${\displaystyle f(x,\cdot ):Y\to \mathbb {R} }$es convexo para cada fijo . ${\displaystyle x\in X}$

Entonces tenemos eso

${\displaystyle \max _{x\in X}\min _{y\in Y}f(x,y)=\min _{y\in Y}\max _{x\in X}f(x,y).}$

Teorema del minimax de Sion

El teorema minimax de Sion es una generalización del teorema minimax de von Neumann debido a Maurice Sion , ^[6] relajando el requisito de que establece: ^{[6] [7]}

Sea un subconjunto convexo de un espacio topológico lineal y sea un subconjunto convexo compacto de un espacio topológico lineal . Si es una función de valor real en con ${\displaystyle X}$ ${\displaystyle Y}$ ${\displaystyle f}$ ${\displaystyle X\times Y}$

${\displaystyle f(\cdot ,y)}$ superior semicontinua y cuasi-cóncava en , para cada fijo , y ${\displaystyle X}$ ${\displaystyle y\in Y}$

${\displaystyle f(x,\cdot )}$inferior semicontinua y cuasi-convexa en , para cada fijo . ${\displaystyle Y}$ ${\displaystyle x\in X}$

Entonces tenemos eso

${\displaystyle \sup _{x\in X}\min _{y\in Y}f(x,y)=\min _{y\in Y}\sup _{x\in X}f(x,y).}$

Véase también

• Teorema de Parthasarathy : una generalización del teorema minimax de Von Neumann
• Se puede utilizar un programa lineal dual para demostrar el teorema minimax para juegos de suma cero.
• Principio minimax de Yao

Referencias

1. Simons, Stephen (1995), Du, Ding-Zhu; Pardalos, Panos M. (eds.), "Teoremas minimax y sus demostraciones", Minimax and Applications , Boston, MA: Springer US, págs. 1–23, doi :10.1007/978-1-4613-3557-3_1, ISBN 978-1-4613-3557-3, consultado el 27 de octubre de 2024
2. Von Neumann, J. (1928). "Zur Theorie der Gesellschaftsspiele". Matemáticas. Ana. 100 : 295–320. doi :10.1007/BF01448847. S2CID  122961988.
3. John L Casti (1996). Cinco reglas de oro: grandes teorías de las matemáticas del siglo XX y por qué son importantes . Nueva York: Wiley-Interscience. p. 19. ISBN 978-0-471-00261-1.
4. Du, Ding-Zhu; Pardalos, Panos M., eds. (1995). Minimax y aplicaciones . Boston, MA: Springer US. ISBN 9781461335573.
5. Brandt, Felix; Brill, Markus; Suksompong, Warut (2016). "Un teorema ordinal minimax". Juegos y comportamiento económico . 95 : 107–112. arXiv : 1412.4198 . doi :10.1016/j.geb.2015.12.010. S2CID  360407.
6. Sion, Maurice (1958). "Sobre teoremas generales de minimax". Revista del Pacífico de Matemáticas . 8 (1): 171–176. doi : 10.2140/pjm.1958.8.171 . MR  0097026. Zbl  0081.11502.
7. Komiya, Hidetoshi (1988). "Prueba elemental del teorema minimax de Sion". Revista matemática Kodai . 11 (1): 5–7. doi : 10.2996/kmj/1138038812. SEÑOR  0930413. Zbl  0646.49004.