People
People
Faculty
Xiaotie Deng Professor

+86 (0)10 6276-9219

xiaotie

Room 202-2, Courtyard No.5, Jingyuan

Algorithmic Game Theory, Computational Economics, Blockchain, Combinatorics and Optimization https://cfcs.pku.edu.cn/dengxiaotie/

Bio-Sketch

Xiaotie Deng, Chair Professor of the Center on Frontiers of Computing Studies (CFCS) at Peking University, Director of Blockchain Committee at China Society for Industrial and Applied Mathematics (CSIAM), and Director of the Center for Multi-agent Research at Institute for Artificial Intelligence, Peking University. Before joining Peking University, he worked at Shanghai Jiaotong University, University of Liverpool, City University of Hong Kong, and York University. He received his Bachelor's degree from Tsinghua University in 1982, Master's degree from Chinese Academy of Sciences in 1984, and Ph.D. from Stanford University in 1989.

 

Xiaotie's main research interests are algorithmic game theory, blockchain, internet economy, online algorithms and parallel computing. His recent research focuses on equilibrium calculation, multi-agent game, internet economy, and game theory in blockchain.

 

Xiaotie was honored with the FOCS Best Paper Award in 2006. He is a fellow of the Association of Computing Machinery (ACM) for his contributions to the interface of algorithms and game theory (2008), and the Institute of Electrical and Electronics Engineers (IEEE) for his contributions to computing in partial information and interactive environments (2019). He was elected as foreign member of Academia Europaea in 2020, CSIAM fellow in 2021. In 2022, he won ACM SIGecom Test of Time Award.

 

Xiaotie has undertaken dozens of research projects as the principal investigator and has served on the editorial board of top international journals. He has chaired many top international conferences, in particular, he initiated the Conference on Web and Internet Economics (WINE) organized by the three continents in turn: Asia, Europe and the United States, and the International Joint Conference on Theoretical Computer Science (IJTCS).

Publications

Selected Papers in major journals/conferences

 

  • Xiaotie Deng ; Tao Xiao ; Keyu Zhu, Learn to Play Maximum Revenue Auction, IEEE Transaction on Cloud Computing 7(4), 1057-1067 (2019)
  • Yukun Cheng, Xiaotie Deng, Dominik Scheder: Recent studies of agent incentives in Internet resource allocation and pricing.  4OR 16(3): 231-260 (2018)
  • How to Design a Common Telecom Infrastructure for Competitors to be Individually Rational and Collectively Optimal. IEEE Journal on Selected Areas in Communications 35(3): 736-750 (2017)
  • Xiaotie Deng, Qi Qi, Amin Saberi: Algorithmic Solutions for Envy-Free Cake Cutting. Operations Research 60(6): 1461-1476 (2012)
  • X. Deng, Q. Qi, A. Saberi, J. Zhang, Discrete Fixed Points: Models, Complexities and Applications, Mathematics of Operations Research. Vol. 36, No. 4, 2011.
  • Xi Chen, Xiaotie Deng, Shang-Hua Teng: Settling the complexity of computing two-player Nash equilibria. J. ACM 56(3): (2009)
  • Deng XT, Huang LS, Li MM. On Walrasian price of CPU time, ALGORITHMICA 48 (2): 159-172 JUN 2007.
  • Haodi Feng, Kang Chen, Xiaotie Deng, Weimin Zheng: Accessor Variety Criteria for Chinese Word Extraction. Computational Linguistics 30(1): 75-93 (2004).
  • X. Deng, C. Papadimitriou, and S. Safra, On the Complexity of Price Equilibrium. Journal of Computer and System Sciences Volume 67, Issue 2 , September 2003 , Pages 311-324. A Special Issue on STOC 2002.
  • Mao-Cheng Cai, Xiaotie Deng, and Wenan Zang. A Min-Max Theorem on Feedback Vertex Sets. Mathematics of Operations Research Vol. 27 No.2, pp.361-371, May 2002.
  • Shunming Zhang, Chunlei Xu, Xiaotie Deng. Dynamic Arbitrage-free Asset Pricing with Proportional Transaction Costs. Mathematical Finance, vol. 12, No. 1, pp.1-9, January, 2002.
  • Mao-Cheng Cai, Xiaotie Deng, and Wenan Zang. An Approximation Algorithms for Feedback Vertex Sets in Tournaments. SIAM Journal on Computing, Vol. 30, No.6,  pp. 1993 – 2007, 2001.
  • Xiaotie Deng, Nian Gu, Tim Brecht, KaiCheng Lu: Preemptive Scheduling of Parallel Jobs on Multiprocessors. SIAM J. Comput. 30(1): 145-160 June 2000. (P)
  • Xiaotie Deng, Toshihide Ibaraki, Hiroshi Nagamochi, Wenan Zang. Totally balanced combinatorial optimization games, Math. Program. 87 (May 2000) 3, 441-452.
  • X. Deng and C.H. Papadimitriou. Decision making by Hierarchies of Discordant Agents. Mathematical Programming 86(2), pp.417-431, November 1999.
  • Xiaotie Deng, Toshihide Ibaraki, Hiroshi Nagamochi. Algorithms Aspects of Combinatorial Optimization Games. Mathematics of Operations Research, Vol. 24(3), pp.751-766, 1999.
  • X. Deng, E. Koutsoupias and P. McKenzie. Competitive Implementation of Parallel Programs. Algorithmica, Vol. 23 No.1, 1999, pp.14-30.
  • Xiaotie Deng, Tiko Kameda, and Christos Papadimitriou.  How to Learn an Unknown Environment I: The Rectilinear Case.  Journal of the ACM, Vol. 45, No.2, 1998, pp. 215-245.
  • X. Deng and S. Mahajan. The Cost of Derandomization: Computability or Competitiveness. SIAM J. Comput., Vol. 26, No. 3, June, 1997, pp.786-802.
  • X. Deng, P. Hell and J. Huang. Linear Time Representation Algorithms for Proper Circular Arc Graphs and Proper Interval Graphs. SIAM J. Computing, Vol. 25, No.2, (1996), pp.390—403.
  • X. Deng and A. Mirzaian .  Competitive Robot Mapping with Homogeneous Markers.  IEEE transactions on Robotics and Automation, Vol. 12, No.4, (1996), pp. 532—542.
  • X. Deng and C. Papadimitriou. On the Complexity of Cooperative Game Solution Concepts. Mathematics of Operations Research, Vol. 19, No. 2 (1994), pp. 257—266.
  • Chenchen Li, Xiang Yan, Xiaotie Deng, Yuan Qi, Wei Chu, Le Song, Junlong Qiao, Jianshan He, Junwu Xiong: Latent Dirichlet Allocation for Internet Price War. AAAI 2019: 639-646.
  • Xiaotie Deng, Jack R. Edmonds, Zhe Feng, Zhengyang Liu, Qi Qi, Zeying Xu: Understanding PPA-Completeness. Conference on Computational Complexity 2016: 23:1-23:25
  • Yukun Cheng, Xiaotie Deng, Qi Qi, Xiang Yan: Truthfulness of a Proportional Sharing Mechanism in Resource Exchange. IJCAI 2016: 187-193
  • Juntao Wang, Xun Xiao, Jianping Wang, Kejie Lu, Xiaotie Deng, Ashwin Gumaste: When group-buying meets cloud computing. INFOCOM 2016: 1-9
  • Xiaotie Deng, Zhe Feng, Christos H. Papadimitriou: Power-Law Distributions in a Two-Sided Market and Net Neutrality. WINE 2016: 59-72
  • Xiaotie Deng, Jianping Wang, Juntao Wang: How to design a common telecom infrastructure by competitors individually rational and collectively optimal. INFOCOM Workshops 2015: 552-557
  • Yukun Cheng, Xiaotie Deng, Yifan Pi, Xiang Yan: Can Bandwidth Sharing Be Truthful? SAGT 2015: 190-202
  • Simina Brânzei, Yiling Chen, Xiaotie Deng, Aris Filos-Ratsikas, Søren Kristoffer Stiil Frederiksen, Jie Zhang: The Fisher Market Game: Equilibrium and Welfare. AAAI 2014: 587-593
  • Ning Chen, Xiaotie Deng, Jie Zhang: How Profitable Are Strategic Behaviors in a Market? ESA 2011: 106-118
  • Xiaodong Li, Chao Wang, Jiawei Dong, Feng Wang, Xiaotie Deng, Shanfeng Zhu: Improving Stock Market Prediction by Integrating Both Market News and Stock Prices. DEXA (2) 2011: 279-293

Research Lab

Name

Distributed and Automated Games And Managerial Economics (daGAME) Lab

 

Introduction

The research subjects of lab are algorithmic game theory, Internet and blockchain economics, theory of multi-agents and deep reinforcement learning. We focuses on the methodological studies for the interactions of human with agents, in the epistemological changes with respect to acquisition of data and information, equilibrium and game dynamics among human and agents, computational and communication complexity, design and analysis of algorithms and protocols. We are especially interested in applications in the Internet market design,  analysis of incentives and cooperative competition, as well as high performance consensus, reputation system design, as well as cross-chain mechanism design in Blockchain economics and technology.

 

https://cfcs.pku.edu.cn/english/research/researchlabs/237314.htm