Balancing Traffic in Networks: Redundancy, Learning and the Effect of Stochastic Fluctuations

Details Balancing Traffic in Networks: Redundancy, Learning and the Effect of Stochastic Fluctuations Balancing Traffic in Networks: Redundancy, Learning and the Effect of Stochastic Fluctuations

2009-12-21

arxiv.org/abs/0912.4012v2

Mathematics

Probability

39 pages, 4 figures. Incorporated material on nonatomic potential games and Braess's paradox; some minor typos have now been c

Scientific paper

We study the distribution of traffic in networks whose users try to minimise their delays by adhering to a simple learning scheme inspired by the replicator dynamics of evolutionary game theory. The stable steady states of these dynamics coincide with the network's Wardrop equilibria and form a convex polytope whose dimension is determined by the network's redundancy (an important concept which measures the "linear dependence" of the users' paths). Despite this abundance of stationary points, the long-term behaviour of the replicator dynamics turns out to be remarkably simple: every solution orbit converges to a Wardrop equilibrium. On the other hand, a major challenge occurs when the users' delays fluctuate unpredictably due to random external factors. In that case, interior equilibria are no longer stationary, but strict equilibria remain stochastically stable irrespective of the fluctuations' magnitude. In fact, if the network has no redundancy and the users are patient enough, we show that the long-term averages of the users' traffic flows converge to the vicinity of an equilibrium, and we also estimate the corresponding invariant measure.

Affiliated with

Also associated with

No associations

Rating

Balancing Traffic in Networks: Redundancy, Learning and the Effect of Stochastic Fluctuations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Balancing Traffic in Networks: Redundancy, Learning and the Effect of Stochastic Fluctuations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Balancing Traffic in Networks: Redundancy, Learning and the Effect of Stochastic Fluctuations will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-301573