Bottleneck Routing Games with Low Price of Anarchy - Computer Science > Computer Science and Game TheoryReportar como inadecuado




Bottleneck Routing Games with Low Price of Anarchy - Computer Science > Computer Science and Game Theory - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Abstract: We study {\em bottleneck routing games} where the social cost is determinedby the worst congestion on any edge in the network. In the literature,bottleneck games assume player utility costs determined by the worst congestededge in their paths. However, the Nash equilibria of such games are inefficientsince the price of anarchy can be very high and proportional to the size of thenetwork. In order to obtain smaller price of anarchy we introduce {\emexponential bottleneck games} where the utility costs of the players areexponential functions of their congestions. We find that exponential bottleneckgames are very efficient and give a poly-log bound on the price of anarchy:$O\log L \cdot \log |E|$, where $L$ is the largest path length in theplayers- strategy sets and $E$ is the set of edges in the graph. By adjustingthe exponential utility costs with a logarithm we obtain games whose playercosts are almost identical to those in regular bottleneck games, and at thesame time have the good price of anarchy of exponential games.



Autor: Rajgopal Kannan, Costas Busch

Fuente: https://arxiv.org/







Documentos relacionados