Deng, Xiaotie

Professor

Research Interests:Algorithmic Game Theory, Computational Economics, Blockchain, Combinatorics and Optimization

Office Phone: 86-10-6276 9219

Email: xiaotie@pku.edu.cn

https://cfcs.pku.edu.cn/dengxiaotie/

Bio-Sketch

Xiaotie Deng got his BSc from Tsinghua University, MSc from Chinese Academy of Sciences, and PhD from Stanford University in 1989.

He is currently a chair professor at Peking University. He taught in the past at Shanghai Jiaotong University, University of Liverpool, City University of Hong Kong, and York University. Before that, he was an NSERC international fellow at Simon Fraser University. Deng's current research focuses on algorithmic game theory, with applications to Internet Economics and Finance including sponsored search auction, p2p network’s economics such as BitTorrent network, sharing economics, and blockchain. His other works cover online algorithms, parallel algorithms, and combinatorial optimization.

He is an ACM fellow for his contribution to the interface of algorithms and game theory, and an IEEE Fellow for his contributions to computing in partial information and interactive environments.

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