Xiaotie Deng

Xiaotie Deng (Chinese: 邓小铁) is a computer scientist and Chair Professor at Peking University. He serves as the Executive Director of the Center of Frontiers on Computing Studies^[1] and the Director of Multiagent System Research at the Institute of AI, Peking University.^[2] His research spans algorithmic game theory, computational economics, and artificial intelligence, particularly multi-agent systems and learning-based approaches to mechanism design and equilibrium computation, as well as applications to blockchain and multi-agent reinforcement learning.

Deng received his B.Sc. from Tsinghua University in 1982. He obtained his M.Sc. from the Institute of Systems Sciences at the Academia Sinica in 1984. He completed his Ph.D. at Stanford University in 1989.^[3]

Following his doctoral studies, Deng held an NSERC International Postdoc Fellowship at Simon Fraser University from 1989 to 1991. He joined York University, Canada, serving as an Assistant Professor from 1991 to 1996 and as a tenured Associate Professor from 1996 to 1999.^[4]

In 1997, he moved to the City University of Hong Kong, where he advanced from Associate Professor to Professor, eventually serving as Chair Professor of Computer Science from 2007 to 2013.^[5]

Deng served as a Chair Professor in Economics and Computation at the University of Liverpool from 2010 to 2012.^[6] From 2012 to 2017, he was a Zhiyuan Chair Professor in Computer Science at Shanghai Jiao Tong University.^[7] Since 2017, he has served as a Chair Professor in Computer Science at Peking University.^[8]

Deng’s research focuses on algorithmic game theory and computational economics, particularly the computational complexity of equilibrium concepts, incentive analysis, and mechanism design. His work studies the interaction between strategic behavior, algorithms, and economic models.

A major strand of Deng’s research examines the complexity of computing equilibria in games and markets. His early work with Christos Papadimitriou analyzed the computational difficulty of cooperative solution concepts and Nash equilibriums, contributing to complexity-theoretic approaches to equilibrium computation and connections to fixed-point problems and PPAD.^[9] He has also studied the complexity of cooperative concepts such as the core in succinctly represented games.^[10]

Deng has contributed to the theory of market equilibria. In joint work with Papadimitriou and Shmuel Safra, he examined the hardness of computing equilibria in general economic models, including results showing that finding market equilibria in certain Arrow–Debreu markets is computationally intractable in the worst case.

Beyond Nash equilibrium, Deng has studied other solution concepts, including correlated equilibrium and equilibrium notions in congestion games and graphical games, with emphasis on succinct representations and computational tractability.

Deng has applied algorithmic game theory to internet and digital platforms, including sponsored search auctions, matching markets, and resource-sharing systems. His work on sponsored search and keyword auctions explores equilibrium behavior and strategic bidding in online advertising markets.^[11]

Deng’s research also addresses fair division and resource allocation. For example, in Algorithmic Solutions for Envy-Free Cake Cutting (with Qi Qi and Amin Saberi), he analyzed the computational aspects of achieving fair, envy-free allocations.^[12]

More recently, his research has extended to incentive analysis in blockchain and cryptoeconomic systems, including transaction fee mechanisms, committee selection, and decentralized governance.^[13]

Deng has held a range of professional service roles within the scientific community, including editorial and organizational appointments. He has served as a council member of the Game Theory Society since 2021,^[14] and advisory committee of the Microsoft Research Asia Theory Center^[15] He became the founding editor-in-chief of the journal Blockchain in 2022,^[16] and was elected the first director of the China Computer Federation (CCF) Computational Economics Committee the same year.^[17] He has also served on the editorial boards of several academic journals, including National Science Review (since 2015),^[18] Algorithmica (since 2012),^[19] SIAM Journal on Computing (2019–2024), and Theoretical Computer Science (2007–2024).^[20]

• NSERC International Research Fellowship, Simon Fraser University (1990)^[21]
• Invitation Fellowship, Japan Society for the Promotion of Science, Kyoto University (1996, 2005)^[21]
• Best Paper Award, Symposium on Foundations of Computer Science (FOCS) (2006)^[22]
• ACM Fellow (2008)^[23]
• IEEE Fellow (2019)^[24]
• Foreign Member, Academia Europaea (2020)^[21]
• China Society for Industrial and Applied Mathematics Fellow (CSIAM) (2021)^[25]
• CCFAI Achievement Award of China's Agent and Multi-agent System Research (2021)^[26]
• Test of Time Award, Association for Computing Machinery SIGEcom (2022)^[27]

• Deng, Xiaotie; Papadimitriou, Christos H. (1994). "On the Complexity of Cooperative Game Solution Concepts". Mathematics of Operations Research. 19 (2): 257–266.
• Deng, Xiaotie; Li, Ningyuan; Mguni, David; Wang, Jun; Yang, Yaodong (2023). "On the complexity of computing Markov perfect equilibrium in general-sum stochastic games". National Science Review. 10 (1). doi:10.1093/nsr/nwac256. PMC 9843164.
• Cheng, Yukun; Deng, Xiaotie; Li, Yuhao; Yan, Xiang (2024). "Tight incentive analysis of Sybil attacks against the market equilibrium of resource exchange over general networks". Games and Economic Behavior. 148: 566–610.
• Deng, Xiaotie; Li, Hanyu (2025). "How large language models need symbolism". National Science Review. 12 (10). doi:10.1093/nsr/nwaf339. PMC 12448383.
• Deng, Xiaotie; Gafni, Yotam; Lavi, Ron; Lin, Tao; Ling, Hongyi (2025). "From monopoly to competition: When do optimal contests prevail?". Games and Economic Behavior. 153: 268–293.