Highlights We consider repeated routing games with piecewise-constant congestion taxing. The central planner announces the taxes for fixed windows of time in advance. The dynamics converge to a socially optimal flow when using vanishing step sizes. For constant step sizes, the dynamics converge to a neighborhood of an optimal flow.

    Abstract In this paper, we consider repeated routing games with piecewise-constant congestion taxing in which a central planner sets and announces the congestion taxes for fixed windows of time in advance. Specifically, congestion taxes are calculated using marginal congestion pricing based on the flow of the vehicles on each road prior to the beginning of the taxing window (and, hence, there is a time-varying delay in setting the congestion taxes). We motivate the piecewise-constant taxing policy by that users or drivers may dislike fast-changing prices and that they also prefer prior knowledge of the prices. We prove for this model that the multiplicative update rule and the discretized replicator dynamics converge to a socially optimal flow when using vanishing step sizes. Considering that the algorithm cannot adapt itself to a changing environment when using vanishing step sizes, we propose adopting constant step sizes in this case. Then, however, we can only prove the convergence of the dynamics to a neighborhood of the socially optimal flow (with the size of the neighbourhood being of the order of the selected step size). The results are illustrated on a nonlinear version of Pigou’s famous routing game.


    Access

    Check access

    Check availability in my library

    Order at Subito €


    Export, share and cite



    Title :

    A piecewise-constant congestion taxing policy for repeated routing games


    Contributors:


    Publication date :

    2015-04-17


    Size :

    21 pages




    Type of media :

    Article (Journal)


    Type of material :

    Electronic Resource


    Language :

    English





    Taxing congestion of the space commons

    Béal, Sylvain / Deschamps, Marc / Moulin, Hervé | Elsevier | 2020



    Urgency-aware optimal routing in repeated games through artificial currencies

    Salazar M. / Paccagnan D. / Agazzi A. et al. | BASE | 2021

    Free access

    Urgency-aware optimal routing in repeated games through artificial currencies

    Salazar, Mauro / Paccagnan, Dario / Agazzi, Andrea et al. | BASE | 2021

    Free access