Optimization of decentralized traffic networks

Abstract

The Thesis presents an optimization problem of flow in decentralized networks like data transportation, traffic, population, work flow, etc., where their latency-cost functions are congestion-dependent. In the presence of congestion dependency, the shortest path is not trivially determined, but evolves in current flow, which is more realistic feature. Then we consider this system evolves as to optimize either the total cost or elemental costs individually. Accordingly, the flow pattern can be either intentionally regulated by a global optimization or emerged by individual optimization depending on type of the systems. The latter is known for settling at Nash equilibrium in game theory context. By definition,individual optimization mostly results in worse than a global optimum. This gap has been coined "the Price of Anarchy", indicating the worst inefficiency of selfishness. Nevertheless, this price can get lowered, according to Braess``s paradox, by removals of edges in a given system. Consequently, the Thesis investigates tendencies of the price of anarchy in a real system, a simplified Boston road network, and our work promises a potential implication of new methods to optimize flow in decentralized system, which is closer to reality in diverse systems.