静5青年讲座 | The Price of Anarchy for Selfish Load Balancing

We revisit the canonical Koutsoupias--Papadimitriou model, also known as the Selfish Load Balancing problem, providing a fairly complete picture of the Price of Anarchy (PoA) under several standard equilibrium concepts.

For Bayesian Nash equilibria (including both pure and mixed equilibria) under independent priors, we establish the first nontrivial upper bounds,  for identical links and  for related links. Both bounds match the previously known lower bounds from (Gairing, Monien, and Tiemann, SPAA'05 & TOCS'08), and thus fully characterize the inefficiency of both equilibrium concepts.

For Bayesian Nash equilibria (including both pure and mixed equilibria) under correlated priors, we even derive the exact tight bounds,   for identical links and  for related links. This indicates dramatic efficiency degradations when prior correlations are permitted, in stark contrast to the sub-logarithmic bounds under independent priors.

For Correlated Equilibria, we obtain the first nontrivial upper bounds as well, namely  for identical links and  for related links, thereby closing the gaps left by prior work of (Blum, Hajiaghayi, Ligett, and Roth, STOC'08).

Moreover, for Coarse Correlated Equilibria, we prove the first nontrivial upper bounds:  for identical links, and  for related links together with a matching lower bound, where  is the aspect ratio of the fastest and slowest link speeds. This again resolves an open problem of (Blum, Hajiaghayi, Ligett, and Roth, STOC'08).

Yaonan Jin is an Assistant Professor in the Department of Computer Science and Engineering at the Hong Kong University of Science and Technology. Before joining HKUST, he conducted theoretical computer science research at Huawei's Taylor Lab, working with Pinyan Lu. He obtained his PhD from Columbia University in 2023 (advised by Xi Chen and Rocco Servedio). Prior to that, he obtained his MPhil from Hong Kong University of Science and Technology (advised by Qi Qi) and his BEng from Shanghai Jiao Tong University.