Medidas de riesgo y su aplicación a ruteo en redes bajo incertidumbre

Abstract

Esta memoria aborda el problema de ruteo en redes bajo condiciones de incertidumbre, mediante el uso de funcionales no lineales que permiten cuantificar el riesgo de una ruta. En el caso determinista, el problema combinatorial de camino mínimo puede ser abordado desde dos enfoques: de forma dinámica, donde se busca en cada nodo la mejor opción para moverse hacia el siguiente vértice, o bien, de manera global, donde se busca el camino de menor costo desde el origen al destino. En este caso ambas ópticas coinciden, lo cual se ve reflejado en las ecuaciones de Bellman para encontrar caminos mínimos. Ambas perspectivas motivan el presente trabajo que trata el caso no determinista. El modelo general considera un grafo $G=(N,A)$ con nodos terminales $s,d\in N$, donde cada arco $a\in A$ tiene asociado un tiempo de viaje aleatorio $\tau_a$. En el Capítulo 2 se entregan las herramientas necesarias para los siguientes capítulos: medidas de riesgo; consistencia temporal y medidas de riesgo condicionales; procesos de Markov controlados; y por último, las teorías de elección bajo incertidumbre. En el Capítulo 3 se estudia un enfoque dinámico del problema utilizando la noción de medidas de riesgo condicionales, las cuales permiten satisfacer la condición de consistencia temporal. Usando los procesos de Markov controlados y el Average Value-at-Risk condicional, se aborda el problema de ruteo con aversión al riesgo. Se muestra que, bajo independencia de los tiempos de viaje, el problema se reduce a un modelo determinista en que el costo de cada arco corresponde al AVaR. Más aún, esta solución es consistente temporal. Sin embargo, mediante un contraejemplo con variables aleatorias normales se muestra que aún existen inconsistencias. En el Capítulo 4 se desarrolla un enfoque global en base a las teorías de elección, identificando la condición de consistencia aditiva como la propiedad que evita las inconsistencias temporales en las preferencias de los usuarios. De la teoría de desutilidad esperada, se obtiene la medida de riesgo entrópica como la única medida de riesgo que satisface su axiomatización. En el caso de la teoría dual de elección, la consistencia aditiva entrega al valor esperado como única solución. Por último, mediante la consistencia aditiva y la teoría de desutilidad rango-dependiente esperada --una combinación de las dos anteriores--, se obtiene nuevamente la medida de riesgo entrópica como única solución. Finalmente, en el Capítulo 5 se estudian modelos de equilibrio bajo incertidumbre para juegos de congestión no-atómicos y discretos. Para el caso independiente se tiene la existencia de equilibrios de Wardrop y Nash, respectivamente.