Equivalencia entre Juegos de Matrices y Programación Lineal: Un Descubrimiento

Описание: Este estudio revela una conexión fundamental entre cuatro tipos diferentes de problemas computacionales que, a primera vista, parecen no estar relacionados. El documento demuestra que resolver juegos de matrices, optimizar programas lineales, y encontrar las mejores aproximaciones lineales (tanto en la norma l∞ o de Chebyshev como en la norma l1 o de mínimas desviaciones absolutas) son, en esencia, problemas equivalentes. Esto significa que una solución para uno de ellos puede ser transformada para resolver los otros.

La investigación detalla los métodos para convertir un problema de un tipo en otro. Por ejemplo, se explica cómo un juego de matrices, un concepto de la teoría de juegos donde dos jugadores toman decisiones simultáneas, puede reducirse a un problema de aproximación de Chebyshev. De manera similar, se muestra cómo cualquier problema de programación lineal puede transformarse para ser resuelto como un juego de matrices simétrico, un tipo específico de juego donde la matriz de pagos es antisimétrica.

Las implicaciones de estos hallazgos son significativas para el campo de la computación y la optimización. Al establecer estas equivalencias, el estudio abre la puerta a la aplicación de algoritmos y métodos de un área para resolver problemas en otra. Por ejemplo, los métodos utilizados para resolver problemas de aproximación l1 podrían ahora emplearse para abordar juegos de matrices o programas lineales, ampliando así el conjunto de herramientas disponibles para científicos e ingenieros.


Link al paper: https://arxiv.org/pdf/cs/0609056


Autores del estudio: L. N. Vaserstein


Apoyanos en   / audioarxiv  


Unete en   / discord  


#Ciencia de la computación #TeoriaDeJuegos #ProgramacionLineal #Optimizacion #Matematicas #CienciaDeLaComputacion