A Control Method of Dynamic Selfish Routing Based on a State-Dependent Tax

Takafumi KANAZAWA  Takurou MISAKA  Toshimitsu USHIO  

Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E96-A   No.8   pp.1794-1802
Publication Date: 2013/08/01
Online ISSN: 1745-1337
DOI: 10.1587/transfun.E96.A.1794
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Concurrent Systems
Keyword: 
selfish routing,  Braess's paradox,  replicator dynamics,  subsidy and capitation tax,  state-dependent tax,  

Full Text: PDF(1.6MB)
>>Buy this Article


Summary: 
A selfish routing game is a simple model of selfish behaviors in networks. It is called that Braess's paradox occurs in the selfish routing game if an equilibrium flow achieved by players' selfish behaviors is not the optimal minimum latency flow. In order to make the minimum latency flow a Nash equilibrium, a marginal cost tax has been proposed. Braess graphs have also been proposed to discuss Braess's paradox. In a large population of selfish players, conflicts between purposes of each player and the population causes social dilemmas. In game theory, to resolve the social dilemmas, a capitation tax and/or a subsidy has been introduced, and players' dynamical behaviors have been formulated by replicator dynamics. In this paper, we formulate replicator dynamics in the Braess graphs and investigate stability of the minimum latency flow with and without the marginal cost tax. An additional latency caused by the marginal cost tax is also shown. To resolve the problem of the additional latency, we extend the capitation tax and the subsidy to a state-dependent tax and apply it to the stabilization problem of the minimum latency flow.