The Price of Anarchy for Selfish Load Balancing

Speaker: Dr. Yaonan Jin
Assistant Professor
Department of Computer Science and Engineering
The Hong Kong University of Science and Technology

Title: The Price of Anarchy for Selfish Load Balancing

Date: Monday, 23 November 2026

Time: 4:00pm - 5:00pm

Venue: Lecture Theater F (Leung Yat Sing Lecture Theater), near lift 25/26, HKUST

Abstract:

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 (both pure and mixed) under independent priors, we establish the first nontrivial upper bounds: O(log m / log log m) for identical links and O(log m / log log log m) for related links. Both bounds match the previously known lower bounds by Gairing, Monien, and Tiemann (SPAA'05 and TOCS'08), thereby fully characterizing the inefficiency of Bayesian Nash equilibria (both pure and mixed) under independent priors.

For Bayesian Nash equilibria (both pure and mixed) under correlated priors, we derive exact bounds: m for identical links and 1 + (m - 1) * s1 / sm for related links. This indicates dramatic efficiency degradation when prior correlations are permitted, in stark contrast to the sub-logarithmic bounds under independent priors.

For Correlated Equilibria, we also obtain the first nontrivial upper bounds, namely sqrt(m) +/- Theta(1) for both identical and related links, thereby closing the gaps left by prior work by Blum, Hajiaghayi, Ligett, and Roth (STOC'08).

Moreover, for Coarse Correlated Equilibria, we prove the first nontrivial upper bounds: sqrt(m) +/- Theta(1) for identical links, and O(sqrt(m * s1 / sm)) for related links, together with a matching lower bound, where s1 / sm >= 1 is the ratio of the fastest to the slowest link speed. This again resolves an open problem posed by Blum, Hajiaghayi, Ligett, and Roth (STOC'08).

Biography:

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.