skip to main content

Search for: All records

Creators/Authors contains: "Qiu, Zirou"

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

  1. Evolutionary anti-coordination games on networks capture real-world strategic situations such as traffic routing and market competition. Two key problems concerning evolutionary games are the existence of a pure Nash equilibrium (NE) and the convergence time. In this work, we study these two problems for anti-coordination games under sequential and synchronous update schemes. For each update scheme, we examine two decision modes based on whether an agent considers its own previous action (self essential) or not (self non-essential) in choosing its next action. Using a relationship between games and dynamical systems, we show that for both update schemes, finding an NE can be done efficiently under the self non-essential mode but is computationally intractable under the self essential mode. We then identify special cases for which an NE can be obtained efficiently. For convergence time, we show that the dynamics converges in a polynomial number of steps under the synchronous scheme; for the sequential scheme, the convergence time is polynomial only under the self non-essential mode. Through experiments, we empirically examine the convergence time and the equilibria for both synthetic and real-world networks.

    more » « less
    Free, publicly-accessible full text available June 27, 2024
  2. Free, publicly-accessible full text available May 30, 2024
  3. 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 areavailable at: 
    more » « less
  4. Nonpharmaceutical interventions (NPIs) such as mask wearing can be effective in mitigating the spread of infectious diseases. Therefore, understanding the behavioral dynamics of NPIs is critical for characterizing the dynamics of disease spread. Nevertheless, standard infection models tend to focus only on disease states, overlooking the dynamics of “beneficial contagions,” e.g., compliance with NPIs. In this work, we investigate the concurrent spread of disease and mask-wearing behavior over multiplex networks. Our proposed framework captures both the competing and complementary relationships between the dueling contagion processes. Further, the model accounts for various behavioral mechanisms that influence mask wearing, such as peer pressure and fear of infection. Our results reveal that under the coupled disease–behavior dynamics, the attack rate of a disease—as a function of transition probability—exhibits a critical transition. Specifically, as the transmission probability exceeds a critical threshold, the attack rate decreases abruptly due to sustained mask-wearing responses. We empirically explore the causes of the critical transition and demonstrate the robustness of the observed phenomena. Our results highlight that without proper enforcement of NPIs, reductions in the disease transmission probability via other interventions may not be sufficient to reduce the final epidemic size. 
    more » « less