Teorema del minimax

Da condiciones que garantizan que la desigualdad máxima-mínima también sea una igualdad

En el área matemática de la teoría de juegos , un teorema minimax es un teorema que proporciona condiciones que garantizan que la desigualdad máxima-mínima sea también una igualdad. El primer teorema en este sentido es el teorema minimax de von Neumann sobre juegos de suma cero publicado en 1928, ^[1] que se consideró 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 ". ^[2]

Desde entonces, han aparecido en la literatura varias generalizaciones y versiones alternativas del teorema original de von Neumann. ^{[3] [4]}

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

Formalmente, el teorema minimax de von Neumann establece:

Sean y conjuntos convexos compactos . Si es una función continua que es cóncava-convexa, es decir ${\displaystyle X\subset \mathbb {R} ^{n}}$ ${\displaystyle Y\subset \mathbb {R} ^{m}}$ ${\displaystyle f:X\times Y\rightarrow \mathbb {R} }$

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

${\displaystyle f(x,\cdot ):Y\to \mathbb {R} }$es convexo para fijo . ${\displaystyle 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).}$

Caso especial: Función bilineal

El teorema se cumple en particular si es una función lineal en ambos argumentos (y por lo tanto es bilineal ) ya que una función lineal es a la vez cóncava y convexa. Así, si para una matriz finita , tenemos: ${\displaystyle f(x,y)}$ ${\displaystyle f(x,y)=x^{\mathsf {T}}Ay}$ ${\displaystyle A\in \mathbb {R} ^{n\times m}}$

${\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.}$

El caso especial bilineal es particularmente importante para los juegos de suma cero , cuando el conjunto de estrategias de cada jugador consiste en loterías sobre acciones ( estrategias mixtas ) y los pagos son inducidos por el valor esperado . En la formulación anterior, es la matriz de pagos . ${\displaystyle A}$

Véase también

• Teorema del minimax de Sion
• 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. Von Neumann, J. (1928). "Zur Theorie der Gesellschaftsspiele". Matemáticas. Ana. 100 : 295–320. doi :10.1007/BF01448847. S2CID  122961988.
2. 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.
3. Du, Ding-Zhu; Pardalos, Panos M., eds. (1995). Minimax y aplicaciones . Boston, MA: Springer US. ISBN 9781461335573.
4. 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.