Loading Events

Marco Scarsini (Luiss University)

5 April 2017 @ 12:00

 

  • Past event

Details

Date:
5 April 2017
Time:
12:00
Event Category:

“On the asymptotic behavior of the price of anarchy”

abstract

This paper examines the asymptotic behavior of the price of anarchy as a function of the total traffic inflow in nonatomic congestion games with multiple origin-destination pairs.We first show that the price of anarchy may remain bounded away from 1, even in simple three-link parallel networks with convex cost functions. On the other hand, empirical studies show that the price of anarchy is close to 1 in highly congested real-world networks, thus begging the question: under what assumptions can this behavior be justified analytically?

To that end, we prove a general result showing that for a large class of cost functions (defined in terms of regular variation and including all polynomials), the price of anarchy converges to 1 in the high congestion limit. In particular, specializing to networks with polynomial costs, we show that this convergence follows a power law whose degree can be computed explicitly.