Evolutionary anti-coordination games on networks capture real-world strategic situations such as traffic routing and market competition. In such games, agents maximize their utility by choosing strategies (i.e., actions) that differ from their neighbors’ strategies. Two important problems concerning evolutionary games are the existence of a pure Nash equilibrium (NE) and the convergence time of the dynamics. In this work, we study these two problems for anti-coordination games under sequential and synchronous dynamics. For each type of dynamics, we examine two decision-making modes based on whether an agent considers its own previous action (self essential mode) or not (self non-essential mode) in choosing its next action. Using a relationship between anti-coordination games and discrete graphical dynamical systems, we show that for both forms of dynamics, finding an NE can be done efficiently for the self non-essential mode but is computationally intractable under the self essential mode. To cope with this hardness, we identify some special cases for which an NE can be found efficiently, and present the corresponding algorithms. With respect to convergence time, we show that the dynamics converges in a polynomial number of steps in the synchronous case for both modes; for the sequential case, the convergence time is polynomial only for the self non-essential mode. Through experiments, we empirically examine the convergence time and the equilibria for both synthetic and real-world networks.

Networked Anti-Coordination Games Meet Graphical Dynamical Systems: Equilibria and Convergence

Networked discrete dynamical systems are often used to model the spread of contagions and decision-making by agents in coordination games. Fixed points of such dynamical systems represent configurations to which the system converges. In the dissemination of undesirable contagions (such as rumors and misinformation), convergence to fixed points with a small number of affected nodes is a desirable goal. Motivated by such considerations, we formulate a novel optimization problem of finding a nontrivial fixed point of the system with the minimum number of affected nodes. We establish that, unless P = NP, there is no polynomial-time algorithm for approximating a solution to this problem to within the factor n^(1 - epsilon) for any constant epsilon > 0. To cope with this computational intractability, we identify several special cases for which the problem can be solved efficiently. Further, we introduce an integer linear program to address the problem for networks of reasonable sizes. For solving the problem on larger networks, we propose a general heuristic framework along with greedy selection methods. Extensive experimental results on real-world networks demonstrate the effectiveness of the proposed heuristics. A full version of the manuscript, source code and data are
available at: https://github.com/bridgelessqiu/NMIN-FPE

Finding Nontrivial Minimum Fixed Points in Discrete Dynamical Systems: Complexity, Special Case Algorithms and Heuristics

MAS: Multiagent Systems and Markets

poster

The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines. AAAI-23 is the Thirty-Seventh AAAI Conference on Artificial Intelligence. The theme of this conference is to create collaborative bridges within and beyond AI. Like previous AAAI conferences, AAAI-23 will feature technical paper presentations, special tracks, invited speakers, workshops, tutorials, poster sessions, senior member presentations, competitions, and exhibit programs, and two new activities: a Bridge Program and a Lab Program. Many of these activities are tailored to the theme of bridges and all are selected according to the highest standards, with additional programs for students and young researchers. 
AAAI is providing you with a conference planner, which you can use to help organize your itinerary of activities. This includes talks to attend in person, talks to attend remotely, breaks with colleagues and your site seeing activities. To access this conference planner, please go to [https://aaai-2023.takemobi.io](https://aaai-2023.takemobi.io).

In order to access this site, you need to register. If you haven't already, please register [here](https://aaai.org/Conferences/AAAI-23/registration/).


AAAI 2023

The purpose of the AAAI conference series is to promote research in Artificial Intelligence (AI) and foster scientific exchange between researchers, practitioners, scientists, students, and engineers across the entirety of AI and its affiliated disciplines.

Main_Track

technical paper

The purpose of the AAAI conference is to promote research in artificial intelligence (AI) and scientific exchange among AI researchers, practitioners, scientists, and engineers in affiliated disciplines. 

Zirou Qiu

2

SHORT BIO

Presentations

Networked Anti-Coordination Games Meet Graphical Dynamical Systems: Equilibria and Convergence

Finding Nontrivial Minimum Fixed Points in Discrete Dynamical Systems: Complexity, Special Case Algorithms and Heuristics

Stay up to date with the latest Underline news!

PRESENTATIONS

CONFERENCES

COMPANY

RESOURCES