Xihan Deng
Hi, I'm Xihan Deng (邓熙涵), an undergraduate student at Shanghai Jiao Tong University, majoring in Computer Science and Technology with a double major in Mathematics and Applied Mathematics. I expect to graduate in June 2027. I currently have a GPA of 4.07/4.30 (93.8/100) and received the China National Scholarship in 2025.
My research interests lie broadly in theoretical computer science, particularly algorithmic game theory, online algorithms, and approximation algorithms. I am currently advised by Prof. Yuhao Zhang at the John Hopcroft Center and have worked with Prof. Yaonan Jin and Wenqian Wang on the price of anarchy in selfish load balancing. Our paper, The Price of Anarchy for Selfish Load Balancing, will appear at FOCS 2026.
From August to December 2026, I will be a visiting student intern at DIMACS, Rutgers University, supervised by Prof. Kangning Wang and Prof. Lirong Xia.
I plan to apply to Ph.D. programs for Fall 2027. Please feel free to contact me by email if you are interested in my research.
My CV is available below.
Education
-
Shanghai Jiao Tong UniversityB.Eng. in Computer Science and Technology. Double Major in Mathematics and Applied MathematicsSep. 2023 - Expected Jun. 2027
Honors & Awards
-
China National Scholarship for Undergraduate Students2025
Publications (view all )
The Price of Anarchy for Selfish Load Balancing
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).
The Price of Anarchy for Selfish Load Balancing
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).