Authors are listed alphabetically, following the convention in theoretical computer science.
Xihan Deng, Yaonan Jin, Wenqian Wang, Yuhao Zhang
67th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2026)
We revisit the canonical Koutsoupias--Papadimitriou model, also known as the 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), we obtain the first non-trivial upper bounds on the $\textsf{PoA}$: $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. These bounds match the previously known lower bounds of (Gairing, Monien, and Tiemann, SPAA'05 & TOCS'08), and thus fully characterize the inefficiency of both equilibrium concepts. For $\textsf{Correlated Equilibria}$, we obtain the first non-trivial upper bounds as well, namely $\sqrt{m} \pm \Theta (1)$ for identical links and $\tilde{\Theta}(\sqrt{m})$ for related links, thereby closing the gaps left by prior work of (Blum, Hajiaghayi, Ligett, and Roth, STOC'08). Finally, for $\textsf{Coarse Correlated Equilibria}$, we prove the first non-trivial upper bounds: $\sqrt{m} \pm \Theta (1)$ for identical links, and $O(\sqrt{m \cdot s_1/s_m})$ 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 question of (Blum, Hajiaghayi, Ligett, and Roth, STOC'08).
Xihan Deng, Yaonan Jin, Wenqian Wang, Yuhao Zhang
67th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2026)
We revisit the canonical Koutsoupias--Papadimitriou model, also known as the 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), we obtain the first non-trivial upper bounds on the $\textsf{PoA}$: $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. These bounds match the previously known lower bounds of (Gairing, Monien, and Tiemann, SPAA'05 & TOCS'08), and thus fully characterize the inefficiency of both equilibrium concepts. For $\textsf{Correlated Equilibria}$, we obtain the first non-trivial upper bounds as well, namely $\sqrt{m} \pm \Theta (1)$ for identical links and $\tilde{\Theta}(\sqrt{m})$ for related links, thereby closing the gaps left by prior work of (Blum, Hajiaghayi, Ligett, and Roth, STOC'08). Finally, for $\textsf{Coarse Correlated Equilibria}$, we prove the first non-trivial upper bounds: $\sqrt{m} \pm \Theta (1)$ for identical links, and $O(\sqrt{m \cdot s_1/s_m})$ 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 question of (Blum, Hajiaghayi, Ligett, and Roth, STOC'08).