Text

Selfishness Need Not Be Bad

We investigate the price of anarchy (PoA) in nonatomic congestion games when the total demand T gets very large. First results in this direction have recently been obtained by Colini-Baldeschi et al. (2016, 2017, 2020) for routing games and show that the PoA converges to one when the growth of the total demand T satisfies certain regularity conditions. We extend their results by developing a new framework for the limit analysis of the PoA that offers strong techniques such as the limit of games and applies to arbitrary growth patterns of T. We show that the PoA converges to one in the limit game regardless of the type of growth of T for a large class of cost functions that contains all polynomials and all regularly varying functions. For routing games with Bureau of Public Road (BPR) cost functions, we show in addition that socially optimal strategy profiles converge to equilibria in the limit game and that the PoA converges to one at a power law with exponent β, where β > 0 is the degree of the BPR functions. However, the precise convergence rate depends crucially on the the growth of T, which shows that a conjecture proposed by O’Hare et al. (2016) need not hold.

Ketersediaan

Informasi Detail

Judul Seri

OPERATIONS RESEARCH; Vol.69 No.2 March-April 2021

No. Panggil

-

Penerbit

: .,

Deskripsi Fisik

p. 410 - 435

Bahasa

English

ISBN/ISSN

-

Klasifikasi

-

Tipe Isi

-

Tipe Media

-

Tipe Pembawa

-

Edisi

-

Subjek

PRICE OF ANARCHY
SELFISH ROUTING
ROUTING GAME
USER BEHAVIOR
NONATOMIC CONGESTION GAME
STATIC TRAFFIC

Info Detail Spesifik

https://doi.org/10.1287/opre.2020.2036

Pernyataan Tanggungjawab

Zijun Wu, Rolf H. Möhring, Yanyan Chen, Dachuan Xu

Versi lain/terkait

Lampiran Berkas

Komentar