時(shí)間：2023年3月25日（周六）上午10:30

地點(diǎn)：武漢大學(xué)櫻頂老圖書(shū)館

主講人：鄧小鐵教授 歐洲科學(xué)院院士

題目：MARL=PPAD

主講人簡(jiǎn)介：

鄧小鐵教授，ACM/IEEE/CSIAM Fellow，歐洲科學(xué)院外籍院士。CSIAM區(qū)塊鏈專(zhuān)委會(huì)首任主任、CCF計(jì)算經(jīng)濟(jì)專(zhuān)業(yè)組首任主任、北京大學(xué)前沿計(jì)算中心講席教授。主要研究方向?yàn)樗惴安┺恼?、互?lián)網(wǎng)經(jīng)濟(jì)、在線(xiàn)算法，及并行計(jì)算。作為項(xiàng)目負(fù)責(zé)人，他曾承擔(dān)十幾項(xiàng)加拿大、香港、英國(guó)，及國(guó)家基金委科研項(xiàng)目，發(fā)表論文200余篇，被引用數(shù)千次；多次做國(guó)際學(xué)術(shù)會(huì)議特邀報(bào)告；曾獲得IEEE理論計(jì)算機(jī)學(xué)術(shù)會(huì)議FOCS的最佳論文獎(jiǎng)；其成果“關(guān)于圖與組合優(yōu)化的若干經(jīng)典問(wèn)題的研究”獲高等學(xué)?？茖W(xué)研究?jī)?yōu)秀成果獎(jiǎng)（自然科學(xué)）二等獎(jiǎng)（排名第二）。2022年獲選ACM SIGecom時(shí)間檢驗(yàn)獎(jiǎng)。應(yīng)用方面獲得多項(xiàng)專(zhuān)利，曾擔(dān)任主要互聯(lián)網(wǎng)公司機(jī)制設(shè)計(jì)顧問(wèn)。

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.

摘要：

馬爾科夫博弈（也稱(chēng)為隨機(jī)博弈）為多智能體強(qiáng)化學(xué)習(xí)和順序智能體交互的研究奠定了基礎(chǔ)。我們研究折扣通用和有限狀態(tài)隨機(jī)博弈中（近似）馬爾科夫完美均衡的計(jì)算復(fù)雜度，并證明其為PPAD完備問(wèn)題。這為開(kāi)發(fā)多智能體強(qiáng)化學(xué)習(xí)算法以與普通納什均衡計(jì)算方式相同地處理通用和有限狀態(tài)隨機(jī)博弈開(kāi)辟了可能性。