Precio de la anarquía en mecanismos de asignación de recursos

Abstract

En esta memoria estudiaremos el problema de asignar un recurso divisible a un conjunto de n jugadores cuyas valoraciones por el recurso o una fracción de este son desconocidas. Kelly (1997) propuso el mecanismo de asignación proporcional en que los jugadores ofrecen cierta cantidad, y reciben una fracción del bien proporcional a su oferta. Johari y Tsitsiklis en 2004 demuestran que este mecanismo entrega siempre soluciones cuya utilidad social es al menos un 75\% de la \'optima. En esta memoria estudiaremos una extensión de este mecanismo. En ella, se consideran dos etapas y en cada una de ellas se utiliza el mecanismo proporcional, con la salvedad que en la segunda etapa los jugadores tienen dotaciones iniciales del recurso. Este juego es bastante mas complejo pues en particular requiere que los jugadores anticipen el resultado de la segunda etapa para determinar sus ofertas \'optimas en la primera. Esto nos lleva al concepto de equilibrio perfecto en subjuegos. Nuestro principal resultado es un teorema de existencia de equilibrio en estrategias mixtas para este juego. Observamos que esto no se deduce del teorema de Nash pues el conjunto de estrategias puras en nuestro caso no es finito. Luego demostramos que en el caso de dos jugadores y funciones de utilidad lineal el juego posee un equilibrio en estrategias puras. Finalmente demostramos que el precio de la anarquía, que cuantifica la ineficiencia de los equilibrios con respecto a la solución socialmente óptima es a lo más $2\sqrt{2}-2$, complementando un resultado de Prakash Azad y Musacchio. En el camino demostramos numerosas propiedades estructurales de los equilibrios en nuestro juego.