Seminario de estudiantes

Imaginemos una aguja de longitud uno que queremos girar 180 grados, permitiéndonos
trasladarla libremente por el plano. El problema de Kakeya pregunta cuál es la menor área
de una región que permite realizar este movimiento. La respuesta resulta sorprendente:
existen regiones de área arbitrariamente pequeña en las que es posible hacerlo.
En esta charla veremos una construcción de Besicovitch, basada en árboles de Perron, que
explica cómo puede ocurrir este fenómeno. Esto nos llevará a una pregunta natural: si una
región puede tener un área tan pequeña como queramos y, al mismo tiempo, contener una
aguja en todas las direcciones, ¿qué significa realmente que un conjunto sea grande o
pequeño? Para abordar esta pregunta introduciremos las dimensiones de Minkowski y de
Hausdorff y terminaremos con la conjetura de Kakeya, que propone una forma precisa de
cuantificar el tamaño geométrico de estos conjuntos.

Una sucesión de Goodstein es una sucesión generada por tomar un numero base n y escribirlo en base pura 2, luego remplazar los 2s por 3s y restarle 1. El resultado se escribe en base pura 3, luego remplazar los 3s por 4s y restar 1. Así ir modificando el numero. La intuición nos dice que este numero debería aumentar indefinidamente, pero de hecho siempre converge a 0.
El camino que nos lleva a este resultado pasa por usar aritmetica ordinal y trabajar con el infinito. De hecho dado el numero base uno siempre puede saber cuantos pasos va a llevar llegar a 0 usando una tecnica muy interesante.

Muchas aplicaciones utilizan grandes cantidades de servidores alojados en la nube. Los usuarios de una aplicación generan tareas que deben ser distribuidas y ejecutadas por los servidores a medida que llegan al sistema. Un problema de load balancing consiste en determinar cómo deben distribuirse las tareas entre los servidores para minimizar el tiempo promedio que las tareas permanecen pendientes. Estos problemas son desafiantes porque muchas veces deben resolverse con información parcial y respetando restricciones de compatibilidad entre tareas y servidores.

En la práctica, los tiempos entre arribos y de ejecución de las tareas son aleatorios, por lo que el vector que describe la cantidad de tareas en cada servidor es un proceso estocástico. Para simplificar el análisis, se asume que estos tiempos tienen distribución exponencial y se obtiene una cadena de Markov de tiempo continuo. Resultados clásicos sobre load balancing se basan en obtener el límite fluido de este proceso cuando la cantidad de servidores y la tasa de arribos de las tareas tienden a infinito proporcionalmente. Este límite es una ley de grandes números funcional que permite aproximar el comportamiento del proceso por la solución de un sistema infinito de ecuaciones diferenciales. Cuando existen restricciones de compatibilidad no siempre es posible probar límites fluidos y por lo tanto debe recurrirse a otras técnicas.

La charla intentará ser autocontenida y hará énfasis en la intuición por encima de los detalles técnicos. En primer lugar, hablaremos brevemente sobre cadenas de Markov de tiempo continuo y un par de modelos básicos de teoría de colas. Luego, presentaremos algunos resultados clásicos sobre load balancing basados en límites fluidos. Por último, hablaremos de load balancing con restricciones de compatibilidad dadas por un grafo.

En la teoría de juegos clásica, los jugadores eligen acciones con el objetivo de maximizar su beneficio, sin conocer la estrategia del otro jugador. En la teoría de juegos de código abierto, en cambio, cada jugador está representado por un programa que puede inspeccionar el código de los demás antes de decidir qué hacer.

Esta modificación aparentemente sencilla cambia de manera profunda el comportamiento de juegos clásicos como el dilema del prisionero. En particular, aparecen estrategias capaces de condicionar su cooperación a la existencia de demostraciones formales sobre el comportamiento del oponente.

En esta charla introduciremos este modelo a partir del dilema del prisionero y estudiaremos varios ejemplos de estrategias, sus ventajas y desventajas, y como interactúan entre ellas. La explicación de este fenómeno involucra autorreferencia, demostrabilidad y una teoremas de la lógica matemática.

El objetivo será mostrar cómo ideas elementales de teoría de juegos, computación y lógica se combinan para producir comportamientos inesperados y dar lugar a una familia de problemas todavía abiertos.