[Todos CMAT] SEMINARIO DE PROBABILIDAD Y ESTADÍSTICA - ANUNCIO

[seminarios en cmat.edu.uy]

SEMINARIO DE PROBABILIDAD Y ESTADÍSTICA

Viernes 24 de agosto, de 10:30 AM a 11:30 AM, Salón de Seminario - Centro de Matemática



Expositor: Ernesto Mordecki, Centro de Matemática

Título: Juegos estocásticos simples (un resultado y una pregunta)

Resumen: En un juego estocástico simples participan dos oponentes en un grafo dirigido. Cada jugador controla un subconjunto de los vértices, pudiendo en cada vértice que controla elegir entre dos arcos, que trasladan una ficha a uno de dos vértices vecinos. Existe además un tercer conjunto de vértices de azar, en donde la ficha se traslada con probabilidad 1/2 a uno de otros dos nodos. El objetivo de cada jugador es que la ficha llegue a dos nodos distinguidos, recibiendo un pago de 1 el primero jugador y de 0 el segundo.  Es decir, tenemos tres tipos de vértices comunes, controlados por los dos jugadores y por el azar respectivamente, sumados a los vértices de fin de juego. De cada vértice común salen dos  arcos. En los arcos controlados por los jugadores, estos eligen por donde va la ficha, en los de azar se sortea.  El objetivo del jugador 1 es llegar al vértice 1, el del jugador 0 es llegar al jugador 0.  Se demuestra que existen un par de estrategias óptimas minimax, que dan la probabilidad óptima para ambos jugadores en cada nodo. Esa estrategia verifica las ecuaciones de Bellman.  El problema es encontrar un algoritmo que de una solución en tiempo polinomial. Se demuestra que las probabilidades son números racionales p/q, con q menor que 2^n, (donde n es el número de vértices de azar) mejorando resultados previos en donde se demostraba que q<\sqrt{6}^n. Se demuestra que cota es óptima. La pregunta de cómo encontrar soluciones en tiempo polinomial permanece abierta.

----------------------------------------------------------

Véalo aquí: http://www.cmat.edu.uy/events/seminarios