1108.0025 (Rui Carvalho et al.)

Fair sharing of resources in a supply network with constraints    [PDF]

Rui Carvalho, Lubos Buzna, Wolfram Just, Dirk Helbing, David K. Arrowsmith

This paper investigates the effect of network topology on the fair allocation
of network resources among a set of agents, an all-important issue for the
efficiency of transportation networks all around us. We analyse a generic
mechanism that distributes network capacity fairly among existing flow demands.
The problem can be solved by semi-analytical methods on a nearest neighbour
graph with one source and sink pair, when transport occurs over shortest paths.
For this setup, we uncover a broad range of patterns of intersecting shortest
paths as a function of the distance between the source and the sink. When the
number of intersections is the maximum and the distance between the source and
the sink is large, we find that a fair allocation implies a decrease of at
least 50% from the maximum throughput. We also find that the histogram of the
flow allocations assigned to the agents decays as a power-law with exponent -1.
Our semi-analytical framework suggests possible explanations for the well-known
reduction of the throughput in fair allocations. It also suggests that the
combination of network topology and routing rules can lead to highly uneven
(but fair) distributions of resources, a remark of caution to network
designers.

View original: http://arxiv.org/abs/1108.0025