北京大学 English
北京大学 English
人才队伍
首页 > 人才队伍 > 教学科研人员 > 邓小铁
邓小铁
邓小铁 讲席教授

+86 (0)10 6276-9219

xiaotie

静园五院205-1

 算法博弈论、计算经济学、区块链、组合优化 https://cfcs.pku.edu.cn/dengxiaotie/

简介

　　邓小铁教授，现任北京大学前沿计算研究中心讲席教授、CSIAM 区块链专委会主任，兼北京大学人工智能研究院多智能体中心主任。1982年于清华大学获得学士学位，1984年于中国科学院获得硕士学位，1989年于斯坦福大学获得博士学位。1984-1985年，任中国科学院系统科学研究所助理研究员；1991-1999年任加拿大约克大学计算机科学与工程系助理教授、副教授；1997-2012年任香港城市大学计算机科学与工程系副教授、教授、讲席教授，同时，于2010年-2012年兼任英国利物浦大学计算机科学与工程系讲席教授；2012-2017年任上海交通大学计算机科学与工程系讲席教授；2017年12月入职北京大学，任计算机学院前沿计算研究中心讲席教授。

 

　　他的主要科研方向为算法博弈论、区块链、互联网经济、在线算法及并行计算。2008年，他因在算法博弈论领域的贡献当选 ACM Fellow；2019年，因在不完全信息计算和交互环境计算领域的贡献当选 IEEE fellow；2020年当选欧洲科学院外籍院士；2021年当选中国工业与应用数学学会会士（CSIAM Fellow）；2021年被任命为博弈论学会（GTS）理事；2021年被聘为中国运筹学会博弈论分会荣誉理事；2021年获得 CCF 人工智能学会多智能体与多智能体系统研究成就奖；2022年获得 ACM 计算经济学的“时间检验奖”（Test of Time Award）。

 

　　邓小铁教授近期的科研重心主要在均衡计算、多智能体博弈、互联网经济和区块链中的博弈论研究，具体包括数据驱动博弈下的机器学习方法、认知理论、对手建模、学习算法、拍卖、广告、机制设计等。作为项目负责人，他曾承担几十项加拿大、香港、英国及国家基金委科研项目，并担任多种国际期刊编委。邓小铁担任多个国际学术会议主席，并发起由亚欧美三大洲循环举办的国际互联网经济学术会议（The Conference on Web and Internet Economics，WINE）和国际理论计算机联合大会（International Joint Conference on Theoretical Computer Science，IJTCS）。曾获得 IEEE 理论计算机学术会议 FOCS 最佳论文奖；其成果“关于图与组合优化的若干经典问题的研究”获2015年度高等学校科学研究优秀成果奖（自然科学）二等奖。应用方面曾获得多项专利，曾担任主要互联网公司机制设计顾问。

更多

发表论著

Selected publications

Algorithmic Game Theory

  • Xiaotie Deng, Christos H. Papadimitriou:
    On the complexity of cooperative solution concepts, Mathematics of Operations Research, 19(2): 257-266 (1994).
  • Xiaotie Deng, Toshihide Ibaraki, Hiroshi Nagamochi:
    Algorithmic aspects of the core of combinatorial optimization games, Mathematics of Operations Research, 24(3): 751-766 (1999).
  • Xiaotie Deng, Toshihide Ibaraki, Hiroshi Nagamochi, Wenan Zang:
    Totally balanced combinatorial optimization games, Mathematical Programming, 87(3): 441-452 (2000).

 

Equilibrium Computation

  • Xi Chen, Xiaotie Deng:
    Settling the complexity of two-player Nash equilibrium, FOCS 2006 : 261-272.
    Journal version in JACM 2009, with X. Chen and S. Teng.
  • Xiaotie Deng, Christos H. Papadimitriou, Shmuel Safra:
    On the complexity of equilibria, STOC 2002: 67-71.
  • Tian-Ming Bu, Xiaotie Deng, Qi Qi:
    Arbitrage opportunities across sponsored search markets, Theoretical Computer Science, 407(1-3): 182-191 (2008).
  • Tian-Ming Bu, Xiaotie Deng, Qi Qi:
    Forward looking Nash equilibrium for keyword auction, Information Processing Letters, 105(2): 41-46 (2008).
  • Xiaotie Deng, Qi Qi, Amin Saberi:
    Algorithmic solutions for envy-free cake cutting, Operations Research, 60(6): 1461-1476 (2012).
  • Xiaotie Deng, Jianping Wang, Juntao Wang:
    How to Design a Common Telecom Infrastructure for Competitors to be Individually Rational and Collectively Optimal, IEEE Journal on Selected Areas in Communications (IEEE-JSAC), 35(3): 736-750 (2017).
  • Xiaotie Deng, Zhe Feng, Christos H. Papadimitriou:
    Power-Law Distributions in a Two-Sided Market and Net Neutrality, WINE 2016 : 59-72.

 

Incentive Analysis in Market Equilibrium

  • Yukun Cheng, Xiaotie Deng, Yifan Pi, Xiang Yan:
    Can Bandwidth Sharing Be Truthful? SAGT 2015 : 190-202.
  • Ning Chen, Xiaotie Deng, Bo Tang, Hongyang Zhang:
    Incentives for Strategic Behavior in Fisher Market Games, AAAI 2016 : 453-459.
  • Yukun Cheng, Xiaotie Deng, Qi Qi, Xiang Yan:
    Truthfulness of a Proportional Sharing Mechanism in Resource Exchange, IJCAI 2016 : 187-193.

 

Fixed point computation

  • Xi Chen, Xiaotie Deng:
    Matching algorithmic bounds for finding a Brouwer fixed point, Journal of the ACM (JACM), 55(3): 13:1-26 (2008).
  • Xiaotie Deng, Qi Qi, Amin Saberi, Jie Zhang:
    Discrete fixed points: Models, complexities, and applications, Mathematics of Operations Research, 36(4): 636-652 (2011).
  • Xiaotie Deng, Jack R. Edmonds, Zhe Feng, Zhengyang Liu, Qi Qi, Zeying Xu:
    Understanding PPA-completeness, Conference on Computational Complexity 2016 : 23:1-25.

 

Approximate Computing under Incomplete Information 

  • Xiaotie Deng, Tiko Kameda, Christos H. Papadimitriou:
    How to learn an unknown environment I: the rectilinear case, Journal of the ACM (JACM), 45(2): 215-245 (1998). 
  • Xiaotie Deng, Christos H. Papadimitriou:
    Exploring an unknown graph, Journal of Graph Theory, 32(3): 265-297 (1999). 
  • Xiaotie Deng, Andranik Mirzaian:
    Competitive robot mapping with homogeneous markers, IEEE Transactions on Robotics and Automation, 12(4): 532-542 (1996).

 

Multi-Agent Protocols

  • Amotz Bar-Noy, Xiaotie Deng, Juan A. Garay, Tiko Kameda:
    Optimal amortized distributed consensus, Information and Computation, 120(1): 93-100 (1995).
  • Xiaotie Deng, Sanjeev Mahajan:
    Infinite games: randomization, computability, and applications to online problems, STOC 1991 : 289-298.
  • Anthony Y. Fu, Liu Wenyin, Xiaotie Deng:
    Detecting phishing web pages with visual similarity assessment based on earth mover's distance (EMD), IEEE Transactions on Dependable and Secure Computing (IEEE-TDSC), 3(4): 301-311 (2006).
  • Guomin Yang, Duncan S. Wong, Xiaotie Deng:
    Anonymous and authenticated key exchange for roaming networks, IEEE Transactions on Wireless Communications (IEEE-TWC), 6(9): 3461-3472 (2007).
  • Guomin Yang, Qiong Huang, Duncan S. Wong, Xiaotie Deng:
    Universal authentication protocols for anonymous wireless communications, IEEE Transactions on Wireless Communications (IEEE-TWC), 9(1): 168-174 (2010).

 

Parallel Algorithms

  • Frank K. H. A. Dehne, Xiaotie Deng, Patrick W. Dymond, Andreas Fabri, Ashfaq A. Khokhar:
    A randomized parallel 3D convex hull algorithm for coarse grained multicomputers, SPAA 1995 : 27-33.
  • Xiaotie Deng, Nian Gu, Tim Brecht, KaiCheng Lu:
    Preemptive scheduling of parallel jobs on multiprocessors, SIAM Journal on Computing, 30(1): 145-160 (2000).

 

Combinatorics

  • Xiaotie Deng, Pavol Hell, Jing Huang:
    Linear-time representation algorithms for proper circular arc graphs, SIAM Journal on Computing, 25(2): 390-403 (1996). 
  • Xiaotie Deng, Guojun Li, Zimao Li, Bin Ma, Lusheng Wang:
    Genetic design of drugs without side-effects, SIAM Journal on Computing, 32(4): 1073-1090 (2003).
  • Mao-cheng Cai, Xiaotie Deng, Wenan Zang:
    A min-max theorem on feedback vertex sets, Mathematics of Operations Research, 27(2): 361-371 (2002).
  • Mao-cheng Cai, Xiaotie Deng, Wenan Zang:
    An approximation algorithm for feedback vertex sets in tournaments, SIAM Journal on Computing, 30(6): 1993-2007 (2001).

 

Information Retrievals

  • Haodi Feng, Kang Chen, Xiaotie Deng, Weimin Zheng:
    Accessor variety criteria for Chinese word extraction, Computational Linguistics, 30(1): 75-93 (2004).
  • Hung Chim, Xiaotie Deng:
    A new suffix tree similarity measure for document clustering, WWW 2007 : 121-130.
  • Jianfeng Si, Arjun Mukherjee, Bing Liu, Qing Li, Huayi Li, Xiaotie Deng:
    Exploiting topic based twitter sentiment for stock prediction, ACL (2) 2013 : 24-29.

更多

实验室

 

　　算法博弈论实验室由邓小铁教授于2019年创立，研究方向为算法博弈论、互联网和区块链经济学、多智能体及强化深度学习理论。科研兴趣聚焦在人和智能体在互联网、物联网和区块链交互环境下多方博弈的理论与方法论建立，包括数据信息的认识论刻画、均衡和动力学分析、计算复杂性和算法设计。对在计算与通讯技术兴起中应用领域问题特别关注互联网广告机制设计，共享经济中的激励分析和合作竞争，以及区块链的高效共识、声誉机制和跨链机制设计。

　　　　　　 

 

　　区块链前沿研究实验室由邓小铁教授于2020年创立，旨在于走在当今世界区块链理论、技术、应用等三方面的前沿。从理论上，深入研究与区块链领域相关的基本理论，包括密码学、分布式系统、博弈论、经济学等。从技术上，特别注重区块链当下发展的最新进展，包括智能合约、侧链技术、跨链通信技术、隐私性以及声誉机制等。在应用上，明确区块链应用边界、推动区块链治理体系的建设，并对区块链应用领域前沿难题以及其他交叉领域的问题提出解决方案。

更多