Sesión Matemática Discreta y Teoría de JuegosEquilibrios de Nash y estrategias óptimas: la trampa de las matrices aleatorias
Mariano Fernández Zaragoza
Universidad de Buenos Aires, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Estudiamos la estructura de las matrices aleatorias en el contexto de la teoría de juegos de suma cero. Diversos trabajos de los últimos años utilizan estas matrices para evaluar el desempeño de sus algoritmos. Argumentamos que esta práctica presenta problemas. Entre ellos, que el tamaño y la distribución de la matriz sorteada afecta fuertemente las métricas reportadas. Es una crítica a la literatura, que suele reportar su desempeño para una única clase de matrices, o un único tamaño de los juegos. Presentamos algunos de los resultados novedosos: convergencias para variables subgaussianas y una condición general para la existencia de ε-equilibrios de Nash puros en juegos grandes sorteados i.i.d. Además, demostramos que si se acepta el supuesto de que los pagos de los juegos se distribuyen acorde a una variable subgaussiana i.i.d, la estrategia uniforme aproxima equilibrios de Nash en juegos grandes. Por último, discutimos las implicancias que estos resultados tienen para cómo debemos estimar, comparar y publicar las técnicas de aproximación de equilibrios.
Palabras claves: Juegos Suma Cero, Equilibrio de Nash, ε-equilibrio de Nash, Algoritmo, Matrices Aleatorias, Subgaussianas.
Trabajo en conjunto con: Juan Pablo Pinasco (Universidad de Buenos Aires).