4. Population Games: Strategic Multi-Agent Interactions at Scale

Organizers: Shinkyu Park, Murat Arcak, Nuno C. Martins

Location: Orchid Junior 4312

Website: https://sites.google.com/view/cdc2023-population-games/home

Abstract: 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 [1, 2, 3]. 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 [4]. In multi-robot system applications, a payoff mechanism can be designed to coordinate multiple robots in carrying out assigned tasks in dynamically changing environments [5].

System theoretic dissipativity methods, which were originally introduced in Willems’s seminal article [6], play an important role in compositional verification and design of large-scale dynamical systems [7]. 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 [8]. 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 [9, 10, 11].

It is most likely that the full potential of considering more sophisticated agent decision-making models, 1 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.


[1] S. Park, N. C. Martins, and J. S. Shamma, “From population games to payoff dynamics models: A passivity-based approach,” in 2019 IEEE 58th Conference on Decision and Control (CDC), 2019, pp. 6584–6601.

[2] ——, “Payoff dynamics model and evolutionary dynamics model: Feedback and convergence to equilibria (arxiv:1903.02018),” arXiv.org, March 2019.

[3] M. J. Fox and J. S. Shamma, “Population games, stable games, and passivity,” Games, vol. 4, pp. 561–583, Oct. 2013.

[4] N. C. Martins, J. Cert´orio, and R. J. La, “Epidemic population games and evolutionary dynamics,” Automatica, vol. 153, p. 111016, 2023.

[5] S. Park, Y. D. Zhong, and N. E. Leonard, “Multi-robot task allocation games in dynamically changing environments,” in 2021 IEEE International Conference on Robotics and Automation (ICRA), 2021, pp. 8678–8684.

[6] J. C. Willems, “Dissipative dynamical systems part I: General theory,” Arch. Ration. Mech. Anal., vol. 45, no. 5, pp. 321–351, Jan. 1972.

[7] M. Arcak, “Compositional design and verification of large-scale systems using dissipativity theory: Determining stability and performance from subsystem properties and interconnection structures,” IEEE Control Systems Magazine, vol. 42, no. 2, pp. 51–62, 2022.

[8] M. Arcak and N. C. Martins, “Dissipativity tools for convergence to Nash equilibria in population games,” IEEE Transactions on Control of Network Systems, vol. 8, no. 1, pp. 39–50, 2021.

[9] S. Park and N. E. Leonard, “KL divergence regularized learning model for multi-agent decision making,” in 2021 American Control Conference (ACC), 2021, pp. 4509–4514.

[10] ——, “Learning with delayed payoffs in population games using Kullback-Leibler divergence regularization (arxiv:2306.07535),” arXiv.org, June 2023.

[11] S. Park, “Tuning rate of strategy revision in population games,” in 2023 American Control Conference (ACC), 2023, pp. 423–428.

Lecture Schedules: https://sites.google.com/view/cdc2023-population-games/home#h.u52kl7gs7zj2

  • 8:30 ∼ 9:15 Introduction and basic tenets of population games (Speaker: Murat Arcak)
  • 9:15 ∼ 10:00 Strategy revision processes and evolutionary dynamics (Speaker: Nuno Martins)
  • 10:00 ∼ 10:30 Break
  • 10:30 ∼ 11:15 Dissipativity as compositional verification and design tools (Speaker: Murat Arcak)
  • 11:15 ∼ 12:00 Learning with delayed payoffs in population games (Speaker: Shinkyu Park)
  • 12:00 ∼ 13:30 Lunch Break
  • 13:30 ∼ 14:15 Application in epidemiology: Epidemic population games (Speaker: Nuno Martins)
  • 14:15 ∼ 15:00 Application in autonomous systems 1: Reshaping Urban Mobility in Traffic Networks with Mixed Vehicle Autonomy (Speaker: Negar Mehr)
  • 15:00 ∼ 15:30 Break
  • 15:30 ∼ 16:15 Application in autonomous systems 2: Modeling and Resolving Conflicts for Noncooperative Autonomous Systems via Markov Games (Speaker: Sarah Li)
  • 16:15 ∼ 17:00 Application in autonomous systems 3: Task allocation games in multi-robot systems (Speaker: Shinkyu Park)
  • 17:00 ∼ 17:30 Discussions: Future research directions (Speaker: Organizers)

  • © Copyright 2023 IEEE – All rights reserved. Use of this website signifies your agreement to the IEEE Terms and Conditions.
    A not-for-profit organization, IEEE is the world’s largest technical professional organization dedicated to advancing technology for the benefit of humanity.