Núcleo Milenio Información y Coordinación en Redes, ICR

La falta de información o de coordinación entre agentes que interactúan en redes de gran tamaño es habitual en un sinnúmero de situaciones cotidianas. Un ejemplo típico de esto ocurre con el desplazamiento de los santiaguinos a sus respectivos lugares de trabajo. Cada conductor decide qué ruta tomar basado en una diversidad de variables: algunas constantes (por ejemplo, la distancia al objetivo o los límites de velocidad en distintas calles), otras dependen del comportamiento de los distintos agentes (congestión por exceso de tránsito) y otras pueden ser externas al sistema (accidentes, cortes de luz en semáforos, etc.). El problema es que la información que cada agente dispone para tomar su decisión es local, incompleta y estocástica, por lo que se hace imposible determinar con certeza la mejor ruta a su destino.

En situaciones como la descrita no es posible encontrar soluciones óptimas, al menos no de manera eficiente, por lo cual gran parte de su estudio consiste en el desarrollo de algoritmos que encuentren soluciones aproximadas (cercanas al óptimo), robustas (útiles para distintos escenarios cuando hay incertidumbre), dinámicas (que se actualicen a medida que el sistema evolucione) o en línea (que se renueven de acuerdo a la cantidad de información disponible).

Consecuentemente, el objetivo principal de este Núcleo Milenio es consolidar un polo de investigación de clase mundial en los campos de Algoritmos, Combinatoria, Teoría de Juegos y Optimización, en sus conexiones a problemas en red que se caracterizan por la falta de información y la falta de coordinación. Nuestro grupo persigue tres líneas de investigación relevantes a las problemáticas descritas:

• La teoría de juegos algorítmica que estudia algoritmos eficientes para determinar el comportamiento de un conjunto de agentes que optimizan objetivos independientes.
• El estudio de problemas de big data, desde los algoritmos en línea que funcionen con información parcial hasta la representación comprimida de los datos.
• La investigación sobre la estructura de las grandes redes, su dinámica y sus protocolos.