The Price of Anarchy for Selfish Load Balancing
- Dr. Yaonan Jin, HKUST
- Time: 2026-09-08 15:00
- Host: Dr. Shaofeng Jiang
- Venue: Room 204, Courtyard No.5, Jingyuan
Abstract
We revisit the canonical Koutsoupias--Papadimitriou model, also known as the \textsc{Selfish Load Balancing} problem, providing a fairly complete picture of the \textsf{Price of Anarchy} (\textsf{PoA}) under several standard equilibrium concepts.
For \textsf{Bayesian Nash equilibria} (including both pure and mixed equilibria) under independent priors, we establish the first nontrivial upper bounds, $O\bigl(\frac{\log m}{\log\log m}\bigr)$ for identical links and $O\bigl(\frac{\log m}{\log\log\log m}\bigr)$ 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 \textsf{Bayesian Nash equilibria} (including both pure and mixed equilibria) under correlated priors, we even derive the exact tight bounds, $m$ for identical links and $1 + (m - 1) \cdot s_{1} / s_{m}$ 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 \textsf{Correlated Equilibria}, we obtain the first nontrivial upper bounds as well, namely $\sqrt{m} \pm \Theta(1)$ for identical links and $\Theta(\sqrt{m})$ for related links, thereby closing the gaps left by prior work of (Blum, Hajiaghayi, Ligett, and Roth, STOC'08).
Moreover, for \textsf{Coarse Correlated Equilibria}, we prove the first nontrivial upper bounds: $\sqrt{m} \pm \Theta(1)$ for identical links, and $O\bigl(\sqrt{m \cdot s_{1}/s_{m}}\bigr)$ for related links together with a matching lower bound, where $s_{1}/s_{m} \ge 1$ 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).
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.