Application of Mathematical
Methods in Artificial Intelligence

Deng Xiaotie

Peking University, China

On the complexity of computing Markov perfect equilibrium in general-sum stochastic games

Similar to the role of Markov decision processes in reinforcement learning, Markov games (also called stochastic games) lay down the foundation for the study of multi-agent reinforcement learning and sequential agent interactions. We introduce approximate Markov perfect equilibrium as a solution to the computational problem of finite-state stochastic games repeated in the infinite horizon and prove its PPAD-completeness. This solution concept preserves the Markov perfect property and opens up the possibility for the success of multi-agent reinforcement learning algorithms on static two-player games to be extended to multi-agent dynamic games, expanding the reign of the PPAD-complete class.

Speaker BIO

Xiaotie Deng, Chair Professor of the Center on Frontiers of Computing Studies (CFCS) at Peking University, Director of Blockchain Committee at China Society for Industrial and Applied Mathematics (CSIAM), and Director of the Center for Multi-agent Research at Institute for Artificial Intelligence, Peking University. Before joining Peking University, he worked at Shanghai Jiaotong University, University of Liverpool, City University of Hong Kong, and York University. He received his Bachelor's degree from Tsinghua University in 1982, Master's degree from Chinese Academy of Sciences in 1984, and Ph.D. from Stanford University in 1989.

Xiaotie's main research interests are blockchain, internet economy, online algorithms and parallel computing. His recent research focuses on equilibrium calculation, multi-agent game, internet economy, and blockchain.

Xiaotie was honored with the FOCS Best Paper Award in 2006. He is a fellow of the Association of Computing Machinery (ACM) for his contributions to the interface of algorithms and game theory (2008), and the Institute of Electrical and Electronics Engineers (IEEE) for his contributions to computing in partial information and interactive environments (2019). He was elected as foreign member of Academia Europaea in 2020, CSIAM fellow in 2021. In 2022, he won ACM SIGecom Test of Time Award.

Xiaotie has undertaken dozens of research projects as the principal investigator and has served on the editorial board of top international journals. He has chaired many top international conferences, in particular, he initiated the Conference on Web and Internet Economics (WINE) organized by the three continents in turn: Asia, Europe and the United States, and the International Joint Conference on Theoretical Computer Science (IJTCS).

Oleg Granichin

Saint-Petersburg State University, Russia

Decision making under uncertainties — Artificial intelligence

We will discuss the problems of artificial intelligence through the scope of decision making in real time under uncertainties. The main questions — what kind of information we can are able to get based on finite (small) number of noised observations. New estimated approach will be proposed and illustrative examples will be considered.

Speaker BIO

Professor O.N. Granichin is a member of IFAC Technical Committee 1.1 (Modeling, Identification and Signal Processing), a Senior member of IEEE, IEEE Control System Society, member of Academy of Navigation and Control of Moving. He has been researching control theory since the early 1980s, focusing on control problems under irregular unknown but bounded disturbances. The description of a minimax stabilizing controller for a nonminimum-phase control plant proposed by him in his student course work (1981) was one of the world's first significant theoretical results of the recently popular theory of ℓ1-optimization. Since 2010, under the guidance of professor O.N. Granichin at the Department of System Programming, Faculty of Mathematics and Mechanics, St. Petersburg State University, a constantly renewing scientific group of young researchers has been formed, engaged in robotics and the development of software tools for modeling the behavior of stochastic optimization algorithms in specific applied problems which are in part actual in medicine. The high professional level of the project's research team is proved by the available scientific results presented at numerous high-ranking international conferences and published in peer-reviewed international journals indexed in Scopus and Web of Science.

A distinctive feature of the scientific group can be called the ability to competently combine theoretical fundamental research and their practical application for more specific problems.