Search

Graph Contrastive Learning (GCL) seeks to learn nodal or graph representations that contain maximal consistent information from graph-structured data. While node-level contrasting modes are dominating, some efforts commence to explore consistency across different scales. Yet, they tend to lose consistent information and be contaminated by disturbing features. Here, we introduce MUX-GCL, a novel cross-scale contrastive learning paradigm that utilizes multiplex representations as effective patches. While this learning mode minimizes contaminating noises, a commensurate contrasting strategy using positional affinities further avoids information loss by correcting false negative pairs across scales. Extensive downstream experiments demonstrate that MUX-GCL yields multiple state-of-the-art results on public datasets. Our theoretical analysis further guarantees the new objective function as a stricter lower bound of mutual information of raw input features and output embeddings, which rationalizes this paradigm. Code is available at https://github.com/MUX-GCL/Code.

Recent paradigm shifts from imitation learning to reinforcement learning (RL) is shown to be productive in understanding human behaviors. In the RL paradigm, individuals search for optimal strategies through interaction with the environment to make decisions. This implies that gathering, processing, and utilizing information from their surroundings are crucial. However, existing studies typically study pairwise games such as the prisoners' dilemma and employ a self-regarding setup, where individuals play against one opponent based solely on their own strategies, neglecting the environmental information. In this work, we investigate the evolution of cooperation with the multiplayer game -- the public goods game using the Q-learning algorithm by leveraging the environmental information. Specifically, the decision-making of players is based upon the cooperation information in their neighborhood. Our results show that cooperation is more likely to emerge compared to the case of imitation learning by using Fermi rule. Of particular interest is the observation of an anomalous non-monotonic dependence which is revealed when voluntary participation is further introduced. The analysis of the Q-table explains the mechanisms behind the cooperation evolution. Our findings indicate the fundamental role of environment information in the RL paradigm to understand the evolution of cooperation, and human behaviors in general., Comment: 16 pages, 12 figures, comments are appreciated

The inherent huge complexities in human beings show a remarkable diversity in response to complex surroundings, enabling us to tackle problems from different perspectives. In the realm of cooperation studies, however, existing work assumes that individuals get access to the same kind of information to make their decisions, in contrast to the facts that individuals often perceive differently. Here, within the reinforcement learning framework, we investigate the impact of information perception on the evolution of cooperation in a 2-person scenario when playing the prisoner's dilemma game. We demonstrate that distinctly different evolution processes are observed in three information perception scenarios, revealing that the structure of information significantly affects the emergence of cooperation. Notably, the asymmetric information scenario exhibits a rich dynamical process, including the cooperation emergence, breakdown, and reconstruction, akin to psychological changes in humans. Our findings indicate that the information structure is vital to the emergence of cooperation, shedding new light on establishing mutually stable cooperative relationships and understanding human behavioral complexities in general., Comment: 12pages, 13figures, comments are appreciated

The remarkable adaptability of humans in response to complex environments is often demonstrated by the context-dependent adoption of different behavioral modes. However, the existing game-theoretic studies mostly focus on the single-mode assumption, and the impact of this behavioral multimodality on the evolution of cooperation remains largely unknown. Here, we study how cooperation evolves in a population with two behavioral modes. Specifically, we incorporate Q-learning and Tit-for-Tat (TFT) rules into our toy model, where prisoner's dilemma game is played and we investigate the impact of the mode mixture on the evolution of cooperation. While players in Q-learning mode aim to maximize their accumulated payoffs, players within TFT mode repeat what their neighbors have done to them. In a structured mixing implementation where the updating rule is fixed for each individual, we find that the mode mixture greatly promotes the overall cooperation prevalence. The promotion is even more significant in the probabilistic mixing, where players randomly select one of the two rules at each step. Finally, this promotion is robust when players are allowed to adaptively choose the two modes by real-time comparison. In all three scenarios, players within the Q-learning mode act as catalyzer that turns the TFT players to be more cooperative, and as a result drive the whole population to be highly cooperative. The analysis of Q-tables explains the underlying mechanism of cooperation promotion, which captures the ``psychologic evolution" in the players' mind. Our study indicates that the variety of behavioral modes is non-negligible, and could be crucial to clarify the emergence of cooperation in the real world., Comment: 11 pages, 12 figure. Comments are appreciated

In recent years, with the rapid development of graph neural networks (GNN), more and more graph datasets have been published for GNN tasks. However, when an upstream data owner publishes graph data, there are often many privacy concerns, because many real-world graph data contain sensitive information like person's friend list. Differential privacy (DP) is a common method to protect privacy, but due to the complex topological structure of graph data, applying DP on graphs often affects the message passing and aggregation of GNN models, leading to a decrease in model accuracy. In this paper, we propose a novel graph edge protection framework, graph publisher (GraphPub), which can protect graph topology while ensuring that the availability of data is basically unchanged. Through reverse learning and the encoder-decoder mechanism, we search for some false edges that do not have a large negative impact on the aggregation of node features, and use them to replace some real edges. The modified graph will be published, which is difficult to distinguish between real and false data. Sufficient experiments prove that our framework achieves model accuracy close to the original graph with an extremely low privacy budget.

Punishment is a common tactic to sustain cooperation and has been extensively studied for a long time. While most of previous game-theoretic work adopt the imitation learning where players imitate the strategies who are better off, the learning logic in the real world is often much more complex. In this work, we turn to the reinforcement learning paradigm, where individuals make their decisions based upon their past experience and long-term returns. Specifically, we investigate the Prisoners' dilemma game with Q-learning algorithm, and cooperators probabilistically pose punishment on defectors in their neighborhood. Interestingly, we find that punishment could lead to either continuous or discontinuous cooperation phase transitions, and the nucleation process of cooperation clusters is reminiscent of the liquid-gas transition. The uncovered first-order phase transition indicates that great care needs to be taken when implementing the punishment compared to the continuous scenario., Comment: 7 pages, 6 figures

Efficient allocation is important in nature and human society where individuals often compete for finite resources. The Minority Game is perhaps the simplest model that provides deep insights into how human coordinate to maximize the resource utilization. However, this model assumes the static strategies that are provided a priori, failing to capture their adaptive nature. Here, we turn to the paradigm of reinforcement learning, where individuals' strategies are evolving by evaluating both the past experience and rewards in the future. Specifically, we adopt the Q-learning algorithm, each player is endowed with a Q-table that guides their decision-making. We reveal that the population is able to reach the optimal allocation when individuals appreciate both the past experience and rewards in the future, and they are able to balance the exploitation of their Q-tables and the exploration by randomly acting. The optimal allocation is ruined when individuals tend to use either exploitation-only or exploration-only, where only partial coordination and even anti-coordination are observed. Mechanism analysis reveals that a moderate level of exploration can escape local minimums of metastable periodic states, and reaches the optimal coordination as the global minimum. Interestingly, the optimal coordination is underlined by a symmetry-breaking of action preferences, where nearly half of the population choose one side while the other half prefer the other side. The emergence of optimal coordination is robust to the population size and other game parameters. Our work therefore provides a natural solution to the Minority Game and sheds insights into the resource allocation problem in general. Besides, our work demonstrates the potential of the proposed reinforcement learning paradigm in deciphering many puzzles in the socio-economic context., Comment: 10 pages, 7 figures, 1 table. A working paper, comments are welcome

Behavioral experiments on the trust game have shown that trust and trustworthiness are universal among human beings, contradicting the prediction by assuming \emph{Homo economicus} in orthodox Economics. This means some mechanism must be at work that favors their emergence. Most previous explanations however need to resort to some factors based upon imitative learning, a simple version of social learning. Here, we turn to the paradigm of reinforcement learning, where individuals update their strategies by evaluating the long-term return through accumulated experience. Specifically, we investigate the trust game with the Q-learning algorithm, where each participant is associated with two evolving Q-tables that guide one's decision making as trustor and trustee respectively. In the pairwise scenario, we reveal that high levels of trust and trustworthiness emerge when individuals appreciate both their historical experience and returns in the future. Mechanistically, the evolution of the Q-tables shows a crossover that resembles human's psychological changes. We also provide the phase diagram for the game parameters, where the boundary analysis is conducted. These findings are robust when the scenario is extended to a latticed population. Our results thus provide a natural explanation for the emergence of trust and trustworthiness without external factors involved. More importantly, the proposed paradigm shows the potential in deciphering many puzzles in human behaviors., Comment: 12 pages, 11 figures. Comments are appreciated

While network science has become an indispensable tool for studying complex systems, the conventional use of pairwise links often shows limitations in describing high-order interactions properly. Hypergraphs, where each edge can connect more than two nodes, have thus become a new paradigm in network science. Yet, we are still in lack of models linking network growth and hyperedge expansion, both of which are commonly observable in the real world. Here, we propose a generative hypergraph model by employing the preferential attachment mechanism in both nodes and hyperedge formation. The model can produce bi-heterogeneity, exhibiting scale-free distributions in both hyperdegree and hyperedge size. We provide a mean-field treatment that gives the expression of the two scaling exponents, which agree with the numerical simulations. Our model may help to understand the networked systems showing both types of heterogeneity and facilitate the study of complex dynamics thereon., Comment: 11 pages, 6 figures

Oscillatory behaviors are ubiquitous in nature and the human society. However, most previous works fail to reproduce them in the two-strategy game-theoretical models. Here we show that oscillatory behaviors naturally emerge if incomplete information is incorporated into the cooperation evolution of a non-Markov model. Specifically, we consider a population playing prisoner's dilemma game, where each individual can only probabilistically get access to their neighbors' payoff information and store them within their memory with a given length. They make their decisions based upon these memories. Interestingly, we find that the level of cooperation generally cannot stabilize but render quasi-periodic oscillation, and this observation is strengthened for a longer memory and a smaller information acquisition probability. The mechanism uncovered shows that there are misperceived payoffs about the player's neighborhood, facilitating the growth of cooperators and defectors at different stages that leads to oscillatory behaviors as a result. Our findings are robust to the underlying structure of the population. Given the omnipresence of incomplete information, our findings may provide a plausible explanation for the phenomenon of oscillatory behaviors in the real world., Comment: 8 pages, 6 figures

We human beings show remarkable adaptability in response to complex surroundings, we adopt different behavioral modes at different occasions, such response multimodality is critical to our survival. Yet, how this behavioral multimodality affects the evolution of cooperation remains largely unknown. Here we build a toy model to address this issue by considering a population with bimodal response behaviors, or specifically, with the Fermi and Tit-for-tat updating rules. While the former rule tends to imitate the strategies of those neighbors who are doing well, the latter repeats what their neighbors did to them. In a structural mixing implementation, where the updating rule is fixed for each individual, we find that a moderate mode mixture unexpectedly boosts the overall cooperation level of the population. The boost is even more pronounced in the probabilistic mixing, where each individual randomly chooses one of the two modes at each step, and full cooperation is seen in a wide range. These findings are robust to the underlying topology of the population. Our mean-field treatment reveals that the cooperation prevalence within the players with the Fermi rule linearly increases with the fraction of TFT players and explains the non-monotonic dependence in the structural mixing. Our study shows that the diversity in response behaviors may help to explain the emergence of cooperation in realistic contexts., Comment: 23 pages, 9 figures

Decent social fairness is highly desired both for socio-economic activities and individuals, as it is one of the cornerstones of our social welfare and sustainability. How to effectively promote the level of fairness thus becomes a significant issue to be addressed. Here, by adopting a pinning control procedure, we find that when a very small fraction of individuals are pinned to be fair players in the Ultimatum Game, the whole population unexpectedly evolves into the full fairness level. The basic observations are quite robust in homogeneous networks, but the converging time as a function of the pinning number shows different laws for different underlying topologies. For heterogeneous networks, this leverage effect is even more pronounced that one hub node is sufficient for the aim, and a periodic on-off control procedure can be applied to further save the control cost. Intermittent failures are seen when the pinning control is marginally strong, our statistical analysis indicates some sort of criticality. Our work suggests that the pinning control procedure could potentially be a good strategy to promote the social fairness for some real scenarios when necessary., Comment: 13 pages, 6 figures

Behavioral experiments on the Ultimatum Game have shown that we human beings have remarkable preference in fair play, contradicting the predictions by the game theory. Most of the existing models seeking for explanations, however, strictly follow the assumption of \emph{Homo economicus} in orthodox Economics that people are self-interested and fully rational to maximize their earnings. Here we relax this assumption by allowing that people probabilistically choose to be "good Samaritans", acting as fair players from time to time. For well-mixed and homogeneously structured populations, we numerically show that as this probability increases the level of fairness undergoes from the low scenario abruptly to the full fairness state, where occasional fair behaviors ($\sim5\%$) are sufficient to drive the whole population to behave in the half-half split manner. We also develop a mean-field theory, which correctly reproduces the first-order phase transition and points out that the bistability is an intrinsic property of this game and small fair acts lead to dramatical change due to its bifurcation structure. Heterogeneously structured populations, however, display continuous fairness transition; surprisingly, very few hub nodes acting as fair players are able to entrain the whole population to the full fairness state. Our results thus reveal the unexpected strength of "good Samaritans", which may constitute a new explanation for the emergence of fairness in our society., Comment: 8 pages, 6 figures

The success of modern civilization is built upon widespread cooperation in human society, deciphering the mechanisms behind has being a major goal for centuries. A crucial fact is, however, largely missing in most prior studies that games in the real world are typically played simultaneously and interactively rather than separately as assumed. Here we introduce the idea of interacting games that different games coevolve and influence each other's decision-making. We show that as the game-game interaction becomes important, the cooperation phase transition dramatically improves, a fairly high level of cooperation is reached for all involved games when interaction goes to be strong. A mean-field theory indicates that a new mechanism -- \emph{the dynamical reciprocity}, as a counterpart to the well-known network reciprocity, is at work to foster cooperation, which is confirmed by the detailed analysis. This revealed reciprocity is robust against variations in the game type, the population structure, and the updating rules etc, and more games generally yield a higher level of cooperation. Our findings point out the great potential towards high cooperation for many issues are interwoven with each other in the real world, and also the possibility of sustaining decent cooperation even in extremely adverse circumstances., Comment: 5 pages, 4 figures, 1 table, a companion long paper (arXiv:2102.00360) is also posted. Comments are welcomed

We study the evolution of two mutually interacting games with both pairwise games as well as the public goods game on different topologies. On 2d square lattices, we reveal that the game-game interaction can promote the cooperation prevalence in all cases, and the cooperation-defection phase transitions even become absent and fairly high cooperation is expected when the interaction goes to be very strong. A mean-field theory is developed that points out new dynamical routes arising therein. Detailed analysis shows indeed that there are rich categories of interactions in either individual or bulk scenario: invasion, neutral, and catalyzed types; their combination puts cooperators at a persistent advantage position, which boosts the cooperation. The robustness of the revealed reciprocity is strengthened by the studies of model variants, including asymmetrical or time-varying interactions, games of different types, games with time-scale separation, different updating rules etc. The structural complexities of the underlying population, such as Newman--Watts small world networks, Erd\H{o}s--R\'enyi random networks, and Barab\'asi--Albert networks, also do not alter the working of the dynamical reciprocity. In particular, as the number of games engaged increases, the cooperation level continuously improves in general. Our work thus uncovers a new class of cooperation mechanism and indicates the great potential for human cooperation where concurrent issues are so often seen in the real world., Comment: 22 pages, 19 figures, 2 tables, a companion short paper (arXiv:2101.00359) is also posted. Any comments are welcomed

Social hierarchy is important that can not be ignored in human socioeconomic activities and in the animal world. Here we incorporate this factor into the evolutionary game to see what impact it could have on the cooperation outcome. The probabilistic strategy adoption between two players is then not only determined by their payoffs, but also by their hierarchy difference -- players in the high rank are more likely to reproduce their strategies than the peers in the low rank. Through simulating the evolution of Prisoners' dilemma game with three hierarchical distributions, we find that the levels of cooperation are enhanced in all cases, and the enhancement is optimal in the uniform case. The enhancement is due to the fact that the presence of hierarchy facilitates the formation of cooperation clusters with high-rank players acting as the nucleation cores. This mechanism remains valid on Barab\'asi-Albert scale-free networks, in particular the cooperation enhancement is maximal when the hubs are of higher social ranks. We also study a two-hierarchy model, where similar cooperation promotion is revealed and some theoretical analyses are provided. Our finding may partially explain why the social hierarchy is so ubiquitous on this planet., Comment: 8 pages, 8 figures