We study Network Maximum Congestion Games, a class of network games where players choose a path between two given nodes in order to minimize the congestion of the bottleneck (the most congested link) of their path. For single-commodity games, we provide an algorithm which computes a Pure Nash Equilibrium in polynomial time. If all players have the same weight, the obtained equilibrium has optimum social cost. If players are allowed to have different weights, the obtained equilibrium has social cost at most 4/3 times worst than the optimum. For multi-commodity games with a fixed number of commodities and a particular graph topology, we also provide an algorithm which computes a Pure Nash Equilibria in polynomial time. We also study some issues related to the quality of the equilibria in this kind of games. ; Postprint (published version)


    Zugriff

    Download


    Exportieren, teilen und zitieren



    Titel :

    Maximum congestion games on networks: How can we compute their equilibria?



    Erscheinungsdatum :

    2007-09-01


    Anmerkungen:

    LSI-07-30-R


    Medientyp :

    Paper


    Format :

    Elektronische Ressource


    Sprache :

    Englisch



    Klassifikation :

    DDC:    629



    Risk-Averse Equilibria for Vehicle Navigation in Stochastic Congestion Games

    Yekkehkhany, Ali / Nagi, Rakesh | IEEE | 2022

    Freier Zugriff

    Equilibrium Results for Dynamic Congestion Games

    Meunier, F. / Wagner, N. | British Library Online Contents | 2010


    Equilibrium Results for Dynamic Congestion Games

    Meunier, Frédéric | Online Contents | 2010



    Dynamic Congestion Pricing Model Based on Stackelberg Games

    Ding, Lili / Wang, Zhengwei / Li, Luyan | ASCE | 2013