时间：2023年3月25日（周六）上午10:30

地点：武汉大学樱顶老图书馆

主讲人：邓小铁教授 欧洲科学院院士

题目：MARL=PPAD

主讲人简介：

邓小铁教授，ACM/IEEE/CSIAM Fellow，欧洲科学院外籍院士。CSIAM区块链专委会首任主任、CCF计算经济专业组首任主任、北京大学前沿计算中心讲席教授。主要研究方向为算法及博弈论、互联网经济、在线算法，及并行计算。作为项目负责人，他曾承担十几项加拿大、香港、英国，及国家基金委科研项目，发表论文200余篇，被引用数千次；多次做国际学术会议特邀报告；曾获得IEEE理论计算机学术会议FOCS的最佳论文奖；其成果“关于图与组合优化的若干经典问题的研究”获高等学校科学研究优秀成果奖（自然科学）二等奖（排名第二）。2022年获选ACM SIGecom时间检验奖。应用方面获得多项专利，曾担任主要互联网公司机制设计顾问。

Brief Introduction of Professor Xiaotie Deng

Professor Xiaotie Deng is a Chair Professor at Peking University with a Ph.D. from Stanford University. His research focuses on algorithmic game theory, particularly in the con-text of the Internet and Blockchain Economics. Deng has taught at several universi-ties and is a Fellow of the ACM, CSIAM, IEEE. He is a foreign member of Academia Europaea. He was awarded the 2022 Test of Time Award from ACM SIGecom.

摘要：

马尔科夫博弈（也称为随机博弈）为多智能体强化学习和顺序智能体交互的研究奠定了基础。我们研究折扣通用和有限状态随机博弈中（近似）马尔科夫完美均衡的计算复杂度，并证明其为PPAD完备问题。这为开发多智能体强化学习算法以与普通纳什均衡计算方式相同地处理通用和有限状态随机博弈开辟了可能性。