A piecewise-constant congestion taxing policy for repeated routing games. (August 2015)

• Record Type: Journal Article
• Authors: Farokhi, Farhad; Johansson, Karl H.
• Is Part Of: Transportation research. Volume 78(2015)
• Page Start: 123
• Page End: 143
• Publication Date: 2015-08
• Subjects: Game theory -- Control -- Networks -- Pricing -- Traffic; Transportation -- Research -- Periodicals; Transportation -- Mathematical models -- Periodicals
• DOI: 10.1016/j.trb.2015.04.003
• Languages: English
• ISSNs: 0191-2615

Abstract

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.