{
  "id": "1703.00927",
  "version": "v1",
  "published": "2017-03-02T19:35:48.000Z",
  "updated": "2017-03-02T19:35:48.000Z",
  "title": "On the asymptotic behavior of the price of anarchy: Is selfish routing bad in highly congested networks?",
  "authors": [
    "Riccardo Colini Baldeschi",
    "Roberto Cominetti",
    "Panayotis Mertikopoulos",
    "Marco Scarsini"
  ],
  "comment": "24 pages, 4 figures",
  "categories": [
    "cs.GT",
    "math.OC"
  ],
  "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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2017-03-02T19:35:48.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "91A13",
      "91A43"
    ],
    "keywords": [
      "highly congested networks",
      "asymptotic behavior",
      "selfish routing bad",
      "simple three-link parallel networks",
      "nonatomic congestion games"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 24,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}