Research Article
Stabilization of the minimum latency flow in Braess graphs by state-dependent tax
@INPROCEEDINGS{10.4108/ICST.BIONETICS2008.4700, author={Takurou Misaka and Takafumi Kanazawa and Toshimitsu Ushio and Yasuhiko Fukumoto}, title={Stabilization of the minimum latency flow in Braess graphs by state-dependent tax}, proceedings={1st International ICST Workshop on Technologies for Ambient Information Society}, publisher={ACM}, proceedings_a={TAIS}, year={2010}, month={5}, keywords={Selfish routing Braess’s paradox evolutionary game theory tax and subsidy}, doi={10.4108/ICST.BIONETICS2008.4700} }- Takurou Misaka
Takafumi Kanazawa
Toshimitsu Ushio
Yasuhiko Fukumoto
Year: 2010
Stabilization of the minimum latency flow in Braess graphs by state-dependent tax
TAIS
ICST
DOI: 10.4108/ICST.BIONETICS2008.4700
Abstract
A selfish routing game is a simple model of selfish behaviors in networks. Braess's paradox is a well-known example of inefficiencies existing in the selfish routing games and it is an important problem to reduce such inefficiencies. To resolve such a problem, a notion of a marginal cost tax has been proposed. Although the marginal cost tax makes the minimum latency flow a Nash equilibrium, it also imposes an additional latency on the minimum latency flow. Thus, we apply replicator dynamics with a subsidy and a capitation tax to Braess graphs and extend the capitation tax to a state-dependent one. Using two simplest Braess graphs B1 and B2, we show that the minimum latency flow of the Braess graphs can be stabilized by our proposed state-dependent tax.