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

The Price of Anarchy for Selfish Load Balancing 报告人 Dr.

Yaonan Jin HKUST 时 间 2026年9月8日 星期二 3:00pm 地 点 静园五院204 Host 姜少峰 助理教授 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 (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).

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.

往 期 讲 座 静5杰出讲座回顾 | 周红院长谈协同发展准确、高效与创造性智能 静5杰出讲座回顾 | 马毅教授谈智能本质与人工智能的未来发展 静5杰出讲座回顾 | Bart Selman教授谈人工智能如何加速科学与数学发现 静5前沿讲座回顾 | 姚鹏晖教授谈Pauli analysis在量子算法中的应用 — 版权声明 — 本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。

本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。内容中包含的图片若涉及版权问题，请及时与我们联系删除