2023-5-17

5月11日上午，由中科院数学与系统科学研究院、国家数学与交叉科学中心设立的“复杂系统博弈”和“人工智能数学理论”系列报告联合邀请北京大学计算机学院前沿计算研究中心讲席教授邓小铁作报告，题目是“The complexity of computing Markov perfect equilibrium in general-sum stochastic games”。报告会由杨晓光研究员主持，中科院数学与系统科学研究院副院长戴彧虹研究员等多位师生参加了报告会。

随机博弈/马尔可夫博弈是研究多智能体强化学习的基础模型，也是最复杂最接近现实的博弈模型。邓小铁教授及其合作者引入了近似马尔可夫完美均衡(MPE)作为无限时间带折扣因子的有限状态随机博弈均衡概念，并证明了求解近似MPE问题是PPAD-完全的。这一结果从理论上给出了随机博弈均衡求解的计算复杂度，其研究方法和技巧对设计均衡求解算法和对更复杂的博弈学习系统进行理论分析具有启发性。

邓小铁教授，北京大学计算机学院前沿计算研究中心讲席教授，于1982年在清华大学获得学士学位，于1984年在中国科学院获得硕士学位，于1989年在斯坦福大学获得博士学位。2017年12月他入职北京大学，任计算机学院前沿计算研究中心讲席教授。他曾任教于上海交通大学、利物浦大学、香港城市大学和约克大学。在此之前，他还是西蒙菲莎大学的 NSERC 国际研究员。邓小铁教授的主要科研方向为算法博弈论、区块链、互联网经济、在线算法及并行计算。2008年，他因在算法博弈论领域的贡献当选 ACM Fellow；2019年，因在不完全信息计算和交互环境计算领域的贡献当选 IEEE fellow；2020年当选欧洲科学院外籍院士；2021年当选中国工业与应用数学学会会士（CSIAM Fellow）；2021年被任命为博弈论学会（GTS）理事；2021年被聘为中国运筹学会博弈论分会荣誉理事；2021年获得 CCF 人工智能学会多智能体与多智能体系统研究成就奖；2022年获得 ACM 计算经济学的“时间检验奖”（Test of Time Award）。