Population Games:
Strategic Multi-Agent Interactions at Scale
Organizers: Shinkyu Park, Murat Arcak, and Nuno Martins
Invited Speakers: Negar Mehr and Sarah H.Q. Li
Workshop Presentation Slides and References Available. Click on Schedule below.
* Funding Acknowledgements: KAUST, NSF CNS-2135791, NSF ECCS-2139713, AFOSR FA-95502310467
Abstract
Motivation and Objectives:
For a complex system consisting of many agents interacting strategically with one another, key research themes are to understand how individual agents' decision-making influences the emergent behavior of the system and analyze the system's long-term behavior. To model the dynamics of decision-making in response to payoff mechanisms, researchers have turned to population game frameworks in recent decades. These frameworks have been employed in applications as diverse as transportation networks, wireless networks, smart grids, and cloud computing.
The traditional population game formalism, in which a static (memoryless) payoff mechanism influences the agents' decisions, has recently been extended by the controls community to include dynamics in the payoff mechanism. In the prescriptive scenario in which the payoff mechanism is engineered to be carried out by a coordinator, the dynamics may result from learning behavior, the ever-present inertia in the reward/price-setting mechanism, or the anticipative effects caused by the agents’ attempt to react to predicted future changes in rewards/prices. Allowing for dynamics in the payoff mechanism opened up immense possibilities to employ the formalism of population games to solve a wider variety of research challenges in control systems and related disciplines. As a case in point, in epidemiology, a dynamic payoff mechanism can be designed to minimize the long-term infection prevalence with an anytime bound on the peak of infections. In multi-robot system applications, a payoff mechanism can be designed to coordinate multiple robots in carrying out assigned tasks in dynamically changing environments.
System theoretic dissipativity methods, which were originally introduced in Willems's seminal article, play an important role in compositional verification and design of large-scale dynamical systems. In the new formulation of population games, one can model the agents' decision making under a dynamic payoff mechanism as a feedback interconnection of two separate dynamical system models -- payoff dynamics model and evolutionary dynamics model. Consequently, dissipativity-based techniques become an essential tool in verifying stability of equilibrium states of the feedback interconnection. In addition, leveraging the compositional nature of the dissipativity analysis, one can design new mechanisms underlying the games and agent decision-making models ensuring the stability in a large class of population games, despite time delays in the agent decision making.
It is most likely that the full potential of considering more sophisticated agent decision-making models, dynamic payoff mechanisms, and disspativity-based techniques in engineering applications has not yet been exploited because the key concepts and results needed for such work have been originally published in disparate venues that pose a steep language, stylistic, and conceptual barrier to their assimilation by the control systems community. The proposed workshop intends to bridge this gap, while also putting forward new dissipativity-based techniques for verification and design in population games and their applications in engineering fields.
Expected Outcomes:
The workshop will be organized into multiple tutorial-style sessions to rigorously cover foundational topics ranging from the basic tenets of population games to recent advances in dissipativity-based techniques for mechanism design and dynamic model analysis. Newcomers to population games will be better equipped to understand technical details after the first few sessions. Also, the audience already familiar with game theory will benefit from the subsequent sessions on mechanism design and dynamic model analysis, and their applications to epidemiology and autonomous systems research. We expect to inform attendees of the workshop on the following topics.
Basic definitions and concepts in population games.
Dissipativity-based analysis of payoff dynamics models and evolutionary dynamics models.
Mechanism design and development of agent decision-making models using dissipativity-based approaches.
Applications of population games, payoff dynamics model, and dissipativity-based techniques in epidemiology and autonomous systems research.
Schedule
08:30 ~ 09:15
Introduction and basic tenets of population games
Speaker: Murat Arcak
09:15 ~ 10:00
Strategy revision processes and evolutionary dynamics
Speaker: Nuno Martins
Reference:
Semih Kara, Nuno C. Martins, "Differential Equation Approximations for Population Games using Elementary Probability," arXiv:2312.07598 [cs.GT] (or arXiv:2312.07598v1 [cs.GT] for this version) https://doi.org/10.48550/arXiv.2312.07598
10:30 ~ 11:15
Dissipativity as compositional verification and design tools
Speaker: Murat Arcak
Reference:
Murat Arcak and Nuno Martins. Dissipativity tools for convergence to Nash equilibria in population games. https://ieeexplore.ieee.org/document/9219202
Brendon G. Anderson, Somayeh Sojoudi, Murat Arcak. Evolutionary games on infinite strategy sets: convergence to Nash equilibria via dissipativity. https://arxiv.org/abs/2312.08286
11:15 ~ 12:00
Learning with delayed payoffs in population games
Speaker: Shinkyu Park
Reference:
S. Park, J. S. Shamma, and N. C. Martins, From Population Games to Payoff Dynamics Models: A Passivity-Based Approach, IEEE Conference on Decision and Control (tutorial), 2019. https://ieeexplore.ieee.org/document/9029756
S.Park and N. E. Leonard, Learning with Delayed Payoffs in Population Games using Kullback-Leibler Divergence Regularization, https://arxiv.org/abs/2306.07535
13:30 ~ 14:15
Application in epidemiology: Epidemic population games
Speaker: Nuno Martins
Reference:
Nuno C. Martins, Jair Certório, Richard J. La, "Epidemic population games and evolutionary dynamics," Automatica, Volume 153, 2023. https://doi.org/10.1016/j.automatica.2023.111016
J. Certório, N. C. Martins and R. J. La, "Epidemic Population Games With Nonnegligible Disease Death Rate," in IEEE Control Systems Letters, vol. 6, pp. 3229-3234, 2022, doi: 10.1109/LCSYS.2022.3183477
14:15 ~ 15:00
Application in autonomous systems 1: Reshaping urban mobility in traffic networks with mixed vehicle autonomy
Speaker: Negar Mehr
15:30 ~ 16:15
Application in autonomous systems 2: Modeling and resolving congestion for non-cooperative autonomous systems via Markov decision process (MDP) congestion games
Speaker: Sarah Li
Reference:
Li, Sarah HQ, Daniel Calderone, and Behçet Açıkmeşe. "Congestion-aware path coordination game with Markov decision process dynamics." IEEE Control Systems Letters 7 (2022): 431-436.
Li, Sarah HQ, et al. "Adaptive constraint satisfaction for Markov decision process congestion games: Application to transportation networks." Automatica 151 (2023): 110879.
Li, Sarah HQ, et al. "Tolling for constraint satisfaction in Markov decision process congestion games." 2019 American Control Conference (ACC). IEEE, 2019.
16:15 ~ 17:00
Application in autonomous systems 3: Task allocation games in multi-robot systems
Speaker: Shinkyu Park
Reference:
S. Park, Y. Desmond Zhong, and N. E. Leonard, Multi-Robot Task Allocation Games in Dynamically Changing Environments, IEEE International Conference on Robotics and Automation (ICRA), 2021. https://ieeexplore.ieee.org/document/9561809
S.Park, Tuning Rate of Strategy Revision in Population Games, American Control Conference (ACC) 2023. https://ieeexplore.ieee.org/abstract/document/10156113
17:00 ~ 17:30
Discussions: Future research directions
Speaker: Organizers
Speakers
Shinkyu Park
(KAUST)
Murat Arcak
(UC Berkeley)
Nuno Martins
(UMD)
Negar Mehr
(UIUC)
Sarah H. Q. Li
(ETH)
Speaker Bio
Shinkyu Park is the Assistant Professor of Electrical and Computer Engineering and Principal Investigator of Distributed Systems and Autonomy Group at King Abdullah University of Science and Technology (KAUST). Prior to joining KAUST, he was Associate Research Scholar at Princeton University engaged in cross-departmental robotics projects. He received the Ph.D. degree in electrical engineering from the University of Maryland College Park in 2015. Later he held Postdoctoral Fellow positions at the National Geographic Society (2016) and Massachusetts Institute of Technology (2016-2019). Park’s research focuses on the learning, planning, and control in multi-agent/multi-robot systems. He is a recipient of 2022 O. Hugo Schuck Best Paper Award (Theory) from the American Automatic Control Council (AACC).
Murat Arcak is a professor at U.C. Berkeley in the Electrical Engineering and Computer Sciences Department, with a courtesy appointment in Mechanical Engineering. He received the B.S. degree in Electrical Engineering from the Bogazici University, Istanbul, Turkey (1996) and the M.S. and Ph.D. degrees from the University of California, Santa Barbara (1997 and 2000). His research is in dynamical systems and control theory with applications in multi-agent systems and transportation. He received a CAREER Award from the National Science Foundation in 2003, the Donald P. Eckman Award from the American Automatic Control Council in 2006, the Control and Systems Theory Prize from the Society for Industrial and Applied Mathematics (SIAM) in 2007, and the Antonio Ruberti Young Researcher Prize from the IEEE Control Systems Society in 2014. He is a member of ACM and SIAM, and a fellow of IEEE and the International Federation of Automatic Control (IFAC).
Nuno C. Martins is Professor in the Electrical and Computer Engineering Department of the University of Maryland at College Park, where he also holds a joint appointment with the Institute for Systems Research (ISR). He was Director of the Maryland Robotics Center from 2012 until 2014. He received a M.S. degree in Electrical Engineering from I.S.T., Portugal, in 1997, and a Ph.D. degree in Electrical Engineering and Computer Science with a minor in Mathematics from Massachusetts Institute of Technology (MIT), Cambridge, in 2004. His research interests are in distributed/networked control, team decision theory, population games and fundamental limits. Prof. Martins received the 2006 American Automatic Control Council O. Hugo Schuck Award, a National Science Foundation CAREER Award in 2007, an 2008 IEEE CSS Axelby Award, the 2010 Outstanding ISR Faculty Award, the 2010 George Corcoran Award from the ECE Department / UMD and he was an UMD/ADVANCE Leadership Fellow in 2013.
Negar Mehr is an assistant professor of Aerospace Engineering at the University of Illinois Urbana-Champaign. She is also affiliated with the Coordinated Science Laboratory and the Electrical and Computer Engineering department at UIUC. Previously, she was a postdoctoral scholar at Stanford Aeronautics and Astronautics department from 2019 to 2020. She received her PhD in Mechanical Engineering from UC Berkeley in 2019 and her B.Sc. in Mechanical Engineering from Sharif University of Technology, Tehran, Iran, in 2013. Her research interests lie at the intersection of control theory, game theory, and machine learning. Specifically, she is interested in developing control algorithms that enable safe and intelligent multi-agent interactions. Negar recently won the NSF CAREER award. She was awarded the IEEE Intelligent Transportation Systems best Ph.D. dissertation award in 2020. Negar was recognized as a rising star in EECS, Aeronautics \& Astronautics, and Civil and Environmental Engineering.
Sarah H.Q. Li is a postdoctoral scholar at the Automatic Control Laboratory at ETH and an incoming assistant professor of Aerospace Engineering at Georgia Tech. She received her Ph.D. in Aeronautics and Astronautics Engineering at the University of Washington in 2023 and B.A.Sc in Engineering Physics from the University of British Columbia in 2017. Her research combines game theory, stochastic control, and optimization to enable large-scale autonomous interactions in disruption-prone environments such as roadways and urban air spaces. She is a 2020 Zonta International Amelia Earhart Fellow, a 2022 UW Aero&Astro Condit Fellow, and a rising star in Cyber-physical Systems and Aeronautics and Astronautics.