Estudio del mecanismo de asignación proporcional aplicado a redes de congestión

Abstract

El objetivo principal de este trabajo de memoria de título es estudiar la unicidad del Equilibrio de Nash para el mecanismo de asignación proporcional aplicado a Redes de Congestión, descrito por Johari y Tsitsiklis, donde lo que se busca repartir es la capacidad de los arcos de la red entre varios agentes interesados, cada uno de los cuales cuenta con un conjunto de caminos en la red a través de los que pretende enviar flujo. En dicho trabajo, se muestra que el equilibrio es único para el caso en que la red es en realidad un solo arco, pero se deja como problema abierto la unicidad en una red general. Aportar al conocimiento sobre la unicidad del equilibrio en configuraciones más generales, es la principal motivación del trabajo desarrollado. En esta memoria se aborda el problema estudiando la unicidad desde casos particulares a situaciones más generales, obteniendo como resultado principal que el equilibrio es único para el caso de una red con arcos de distintas capacidades, y donde los jugadores están interesados cada uno en un solo camino (esto último se denomina \emph{Fixed Routing}). Para algunos casos particulares incluso fue posible explicitar las estrategias que definen el único equilibrio. El caso más general -donde cada jugador está interesado en varios caminos en la red- continúa como problema abierto, sin embargo se muestran aquí algunos contraejemplos a otras nociones de unicidad que se pierden en aquel caso. Como objetivo secundario, el trabajo desarrollado en el marco de esta memoria busca dar una nueva demostración de que el Precio de la Anarquía del juego en una red general es $3/4$, aplicando la técnica para el caso de un solo arco descrita por Correa et al. Dicho objetivo se logra, en primer lugar para el caso de \emph{Fixed Routing} y una red con la misma capacidad en todos los arcos, y también para el caso en que los jugadores tienen todos el mismo camino de interés, y las capacidades de los arcos son distintas. Por la experiencia adquirida durante el desarrollo del trabajo, es posible intuir que este es el caso más general en que se puede aplicar la técnica sin modificarla. Por último, se define para el caso de un solo arco, una versión secuencial del mecanismo de asignación proporcional, donde los jugadores no actúan simultáneamente sino que van llegando en orden. Para el caso de dos jugadores, se muestra explícitamente cuál es el único Equilibrio Perfecto en Subjuegos y se obtiene que el Precio de la Anarquía secuencial asociado es $0.875$. Este resultado coincide -tanto en la asignación que entrega el equilibrio, como en la eficiencia del mismo- con el mecanismo \emph{óptimo} para dos jugadores definido por Sanghavi y Hajek. Para el caso de tres jugadores no es posible encontrar analíticamente equilibrios, pero sí se encuentran relaciones implícitas entre las estrategias de los jugadores que permiten hallar numéricamente dos candidatos a equilibrio.