Payoff-monotonic game dynamics and the maximum clique problem

Evolutionary game-theoretic models and, in particular, the so-called replicator equations have recently proven to be remarkably effective at approximately solving the maximum clique and related problems. The approach is centered around a classic result from graph theory that formulates the maximum clique problem as a standard (continuous) quadratic program and exploits the dynamical properties of these models, which, under a certain symmetry assumption, possess a Lyapunov function. In this letter, we generalize previous work along these lines in several respects. We introduce a wide family of game-dynamic equations known as payoff-monotonic dynamics, of which replicator dynamics are a special instance, and show that they enjoy precisely the same dynamical properties as standard replicator equations. These properties make any member of this family a potential heuristic for solving standard quadratic programs and, in particular, the maximum clique problem. Extensive simulations, performed on random as well as DIMACS benchmark graphs, show that this class contains dynamics that are considerably faster than and at least as accurate as replicator equations. One problem associated with these models, however, relates to their inability to escape from poor local solutions. To overcome this drawback, we focus on a particular subclass of payoff-monotonic dynamics used to model the evolution of behavior via imitation processes and study the stability of their equilibria when a regularization parameter is allowed to take on negative values. A detailed analysis of these properties suggests a whole class of annealed imitation heuristics for the maximum clique problem, which are based on the idea of varying the parameter during the imitation optimization process in a principled way, so as to avoid unwanted inefficient solutions. Experiments show that the proposed annealing procedure does help to avoid poor local optima by initially driving the dynamics toward promising regions in state space. Furthermore, the models outperform state-of-the-art neural network algorithms for maximum clique, such as mean field annealing, and compare well with powerful continuous-based heuristics.     

On the dynamics of judgment: does the butterfly effect take place in human working memory?

Why do people hesitate—to do something, or not to do something—even when the data available to them remain constant? The neural model of human working memory (WM) we present in this paper explains hesitation as an emergent property of a complex dynamic structure of stored/processed information. WM is considered as a geometric space inhabited by a “society” of memes, i.e., complex informational structures. A large population of identical memes can cause a feeling, judgment, or intention in an individual. The memes navigate all over WM and interact with one another in a way resembling genetic cross-over; hence, new memes are born at several places in WM. Since the birth of contradictory memes is possible, populations of memes contributing to contradictory feelings, judgments, and plans grow in WM and fight for domination. A computer simulation of the process showed that WM's state sometimes goes to a two-focal “strange” attractor. Hence, sudden mental shifts, as, say, from love to hate and back from hate to love, may be caused by minute fluctuations in the densities of meme streams entering WM. The complex system theory calls this phenomenon the “butterfly effect”. We argue that this effect takes place in the human mind and also can take place in an advanced robot.     

Emergence of autocatalytic reaction in a meme propagation model based on particle motion

Meme refers to a unit of human cultural transmission, analogous to biological evolution. Meme propagation has an autocatalytic property in the sense that it increases its reproductive rate by duplicating the source of propagation. The purpose of this study is to gain general knowledge about the dynamics of meme propagation. This paper presents a minimal model based on the physical movement of particles for investigating the relationship between the behavior of the hosts (velocity of particles) and the autocatalytic property of the meme. It is demonstrated that two extreme memes, the fastest and the slowest ones, have a strong tendency to survive by autocatalytic properties at individual and aggregate levels, respectively, although all memes seem neutral in terms of fitness in the model definition.     

有限次重复囚徒博弈中的合作机制研究

模仿现实中人们的决策方式,提出类"触发策略"的策略思想,将原问题由双策略的多阶段博弈转换为多策略的一次性博弈,并建立起扩展的支付矩阵;然后运用进化博弈理论,将随机扰动引入复制子动态,从理论上说明有限次重复囚徒博弈之所以能够涌现合作是复制效应和变异效应共同作用的结果;最后通过建立多主体系统的仿真模型,进一步分析和验证了合作涌现的门限条件和稳定状态。     

The effect of learning by imitation on a multi-robot system based on the coupling of low-level imitation strategy and online learning for cognitive map building

It is assumed that future robots must coexist with human beings and behave as their companions. Consequently, the complexities of their tasks would increase. To cope with these complexities, scientists are inclined to adopt the anatomical functions of the brain for the mapping and the navigation in the field of robotics. While admitting the continuous works in improving the brain models and the cognitive mapping for robots’ navigation, we show, in this paper, that learning by imitation leads to a positive effect not only in human behavior but also in the behavior of a multi-robot system. We present the interest of low-level imitation strategy at individual and social levels in the case of robots. Particularly, we show that adding a simple imitation capability to the brain model for building a cognitive map improves the ability of individual cognitive map building and boosts sharing information in an unknown environment. Taking into account the notion of imitative behavior, we also show that the individual discoveries (i.e. goals) could have an effect at the social level and therefore inducing the learning of new behaviors at the individual level. To analyze and validate our hypothesis, a series of experiments has been performed with and without a low-level imitation strategy in the multi-robot system.     

Memes in a Digital World: Reconciling with a Conceptual Troublemaker

This paper re‐examines the concept of “meme” in the context of digital culture. Defined as cultural units that spread from person to person, memes were debated long before the digital era. Yet the Internet turned the spread of memes into a highly visible practice, and the term has become an integral part of the netizen vernacular. After evaluating the promises and pitfalls of memes for understanding digital culture, I address the problem of defining memes by charting a communication‐oriented typology of 3 memetic dimensions: content, form, and stance. To illustrate the utility of the typology, I apply it to analyze the video meme “Leave Britney Alone.” Finally, I chart possible paths for further meme‐oriented analysis of digital content.     

基于时间自动机的脑网络时空演化建模方法

人类大脑本质上是不断变化的整体,但基于静息态功能磁共振成像重构技术的人脑网络动态特性研究尚在起步阶段,并且大多采用定性的方法描述。采用时间自动机理论对脑网络在时间和空间上的系统动态特征和演化过程展开了建模方法研究,首先通过对采样时间区间上血氧依赖水平信号的处理得到全脑脑区在单个采样点上的状态描述,然后通过无监督聚类获取其状态集,研究其状态随时间转换的可观测性,最后在此基础上结合时间自动机理论对脑网络状态的演化过程进行建模,从而达到对脑网络动态特性定量描述的目的。实验结果显示该方法可定量描述人脑网络的状态转换规律和演变进程,对不同被试数据具有普适性,并且可辨识出被试的异常演化过程,为脑网络动态特性的深入研究提供了理论基础。     

基于演化博弈的蜜罐有效性机理证明

借鉴自然界生物演变进化过程中复制动态的思想,基于演化博弈对蜜罐技术的有效性机理进行研究,分析网络中攻防双方如何根据自身行动策略及支付函数进行演变,从而使博弈收益最大化。演化博弈从一种全新角度诠释了博弈均衡概念,不再是完全理性也非完全信息,为纳什均衡和均衡战略的选择演绎出新方法。演化博弈过程中,防御方是包括普通服务和蜜罐的混合系统,其对手是访问混合系统的恶意攻击者,双方构成了博弈参与者。混合网络系统可看作一个生态系统,而来访者则只有攻击者一个种群;混合系统持续为来访者提供服务,攻击者可选择访问或不访问。论文基于复制动态方程推理计算满足演化稳定策略的均衡点,并利用Matlab平台仿真验证博弈双方的策略演变趋势,从而在理论上证明了蜜罐技术的有效性机理。     

A system for extracting and comparing memes in online forums

From their origins in the sociological field, memes have recently become of interest in the context of `viral' transmission of basic information units (memes) in online social networks. However, much work still needs to be done in terms of metrics and practical data processing issues. In this paper we define a theoretical basis and processing system for extracting and matching memes from free format text. The system facilitates the work of a text analyst in extracting this type of data structures from online text corpuses and n performing empirical experiments in a controlled manner. The general aspects related to the solution are the automatic processing of unstructured text without need for preprocessing (such as labelling and tagging), identification of co-occurences of concepts and corresponding relations, construction of semantic networks and selecting the top memes. The system integrates these processes which are generally separate in other state of the art systems. The proposed system is important because unstructured online text content is growing at a greater rate than other content (e.g. semi-structured, structured) and integrated and automated systems for knowledge extraction from this content will be increasingly important in the future. To illustrate the method and metrics we process several real online discussion forums, extracting the principal concepts and relations, building the memes and then identifying the key memes for each document corpus using a sophisticated matching process. The results show that our method can automatically extract coherent key knowledge from free text, which is corroborated by benchmarking with a set of other text analysis approaches, as well as a user study evaluation.     

AN EPIDEMIOLOGICAL MODEL OF KNOWLEDGE DIFFUSION IN VIRTUAL LEARNING NETWORKS: AN APPLICATION TO LEARNING STATISTICS IN MEDICINE

ABSTRACT

Some authors claim that the genetic metaphor can be used for describing intergenerational cultural transmission. In analogy with genes, memes can be conceived as cultural units that can be transmitted from one generation to another. A variant of this metaphor conceives cultural transmission as a sort of contagion within a social network of individuals.In this respect, distance learning networks provide a valuable tool for analyzing the spreading of information in virtual communities. In this article, the time evolution of the student's applications to an interactive distance learning platform was analysed. The platform DVLN was developed at the University of Naples and allows tracking all the students' interactions with the system.

The diffusion of the innovation among the students of the Course of Medical Statistics was modelled by means of a system of differential Equations where the diffusion of the innovation adoption depends on the contact rate between two types of students: the innovators and the potential imitators.

Furthermore, by means of k-means cluster analysis of the interactions of the students with the system, three learning styles, i.e. lurkers, socializers, utilitarists, were found. An attempt to explain the macroscopic spreading of innovation adoption on the basis of individual microscopic decisions to accept or refute the innovation was carried out.

The authors claim that the representation of the learning process as a temporal dynamics of a network of cognitive agents opens new perspectives to the scientific analysis of the learning process in human groups.     

Polygene-based evolutionary algorithms with frequent pattern mining

In this paper, we introduce polygene-based evolution, a novel framework for evolutionary algorithms (EAs) that features distinctive operations in the evolutionary process. In traditional EAs, the primitive evolution unit is a gene, wherein genes are independent components during evolution. In polygene-based evolutionary algorithms (PGEAs), the evolution unit is a polygene, i.e., a set of co-regulated genes. Discovering and maintaining quality polygenes can play an effective role in evolving quality individuals. Polygenes generalize genes, and PGEAs generalize EAs. Implementing the PGEA framework involves three phases: (I) polygene discovery, (II) polygene planting, and (III) polygene-compatible evolution. For Phase I, we adopt an associative classification-based approach to discover quality polygenes. For Phase II, we perform probabilistic planting to maintain the diversity of individuals. For Phase III, we incorporate polygene-compatible crossover and mutation in producing the next generation of individuals. Extensive experiments on function optimization benchmarks in comparison with the conventional and state-of-the-art EAs demonstrate the potential of the approach in terms of accuracy and efficiency improvement.     

VoD集群副本结合代理策略的设计与分析

副本和代理策略是目前在VoD服务中应用最广泛的两种主流技术方案,都是保证终端用户VoD服务实时流畅的有效手段,但以往的研究都局限于研究单一策略对系统性能的提升。本文提出了一种VoD集群文件副本加代理的复合策略,集群中的服务器作为文件副本服务器存在,而同时又具有内容代理服务器的功能,并建立了相应的数学模型。仿真实验表明,相比单一的策略,副本结合代理的复合策略可以减少30%以上的点播延时,满足系统的负载均衡需求,较大程度地减少重定向引起的延时,提高系统的准入概率。     

Evolutionary farsightedness in international environmental agreements

This paper proposes a dynamic game model of the process through which countries join international environmental agreements (IEAs). The model assumes that both the number of signatory countries and the stock of accumulated pollution evolve over time, as a result of countries’ emission and membership decisions. The evolution of the number of signatory countries is described by a discrete‐time replicator dynamics, while that of the stock of pollution results from feedback emission strategies. We show that evolutionary farsightedness, that is, the capacity of players to account for the impact of their decisions on the evolution of the number of signatory countries, is beneficial to the formation and stability of self‐enforcing IEAs.     

系统直和博弈模型下的合作演化

演化博弈论是生物进化论与博弈论结合产生的理论,已成为研究合作演化行为的有力工具.本文研究了基于系统直和博弈模型下的合作演化行为.首先,利用复制者方程分析了双人双策略及三策略对称博弈的演化动力学过程.然后,以石头剪刀布模型和雪堆模型为基础,采用矩阵直和构建系统直和博弈模型,并将所构造的直和矩阵转化为含参数的系统总支付矩阵.随后,说明了这种方法可推广到n个博弈的情形.最后,利用MATLAB对系统直和博弈模型进行仿真模拟,从系统整体的角度分析合作演化.仿真结果表明,混合之后的系统直和博弈较单一博弈而言,合作策略的占比明显增加,且整个系统稳定性更好.这种合作演化机制呈现了全局互惠.     

An overview of recent applications of Game Theory to bioinformatics

The goal of this work is to provide a comprehensive review of different Game Theory applications that have been recently used to predict the behavior of non-rational agents in interaction situations arising from computational biology.In the first part of the paper, we focus on evolutionary games and their application to modelling the evolution of virulence. Here, the notion of Evolutionary Stable Strategy (ESS) plays an important role in modelling mutation mechanisms, whereas selection mechanisms are explained by means of the concept of replicator dynamics.In the second part, we describe a couple of applications concerning cooperative games in coalitional form, namely microarray games and Multi-perturbation Shapley value Analysis (MSA), for the analysis of genetic data. In both of the approaches, the Shapley value is used to assess the power of genes in complex regulatory pathways.     

Adaptive recognition of Chinese characters: imitation ofpsychological process in machine recognition

This paper is focused on imitation of human psychological process in machine recognition of Chinese characters. Some results of research on human Chinese character recognition have been discussed and unified into a compound mechanism with an adaptive and self-developing nature. A machine imitation model has been proposed for Chinese character recognition with different routines. By some simplification but with the crucial feature of the model being retained, an experimental system for handprinted Chinese character recognition based on the novel concept has been built. Experimental results have shown that the associated routines continuously improve their performance during their work even after supervised training is halted. The routine of the global pattern approach eventually learns most of the classes and the recognition process gradually shifts from the subpattern approach to the global pattern approach     

Replicator dynamics under perturbations and time delays

Along with the appearance of new optimization and control problems, novel paradigms emerge. A large number of them are based on behavioral ecology, where population dynamics play an important role. One of the most known models of population dynamics is the replicator equation, whose applications in optimization and control have increased in recent years. This fact motivates the study of the replicator dynamics’ properties that are related to the implementation of this method for solving optimization and control problems. This paper addresses implementation issues of the replicator equation in engineering problems. We show by means of the Lyapunov theory that the replicator dynamics model is robust under perturbations that make the state to leave the simplex (among other reasons, this phenomenon can emerge due to numerical errors of the solver employed to obtain the replicator dynamic’s response). A refinement of these results is obtained by introducing a novel robust dynamical system inspired by the replicator equation that allows to control and optimize plants under arbitrary initial conditions on the positive orthant. Finally, we characterize stability bounds of the replicator dynamics model in problems that involve N strategies that are subject to time delays. We illustrate our results via simulations.     

Replicator Dynamics in the Iterative Process for Accurate Range Image Matching

Iterative algorithms are often used for range image matching. In this paper, we treat the iterative process of range image matching as a live biological system: evolving from one generation to another. Whilst different generations of the population are regarded as range images captured at different viewpoints, the iterative process is simulated using time. The well-known replicator equations in theoretical biology are then adapted to estimate the probabilities of possible correspondences established using the traditional closest point criterion. To reduce the effect of image resolutions on the final results for efficient and robust overlapping range image matching, the relative fitness difference (rather than the absolute fitness difference) is employed in the replicator equations in order to model the probability change of possible correspondences being real over successive iterations. The fitness of a possible correspondence is defined as the negative of a power of its squared Euclidean distance. While the replicator dynamics penalize those individuals with low fitness, they are further penalised with a parameter, since distant points are often unlikely to represent their real replicators. While the replicator equations assume that all individuals are equally likely to meet each other and thus treat them equally, we penalise those individuals competing for the same points as their possible replicators. The estimated probabilities of possible correspondences being real are finally embedded into the powerful deterministic annealing scheme for global optimization, resulting in the camera motion parameters being estimated in the weighted least squares sense. A comparative study based on real range images with partial overlap has shown that the proposed algorithm is promising for automatic matching of overlapping range images.     

Experience-based imitation using RNNPB

Robot imitation is a useful and promising alternative to robot programming. Robot imitation involves two crucial issues. The first is how a robot can imitate a human whose physical structure and properties differ greatly from its own. The second is how the robot can generate various motions from finite programmable patterns (generalization). This paper describes a novel approach to robot imitation based on its own physical experiences. We considered the target task of moving an object on a table. For imitation, we focused on an active sensing process in which the robot acquires the relation between the object's motion and its own arm motion. For generalization, we applied the RNNPB (recurrent neural network with parametric bias) model to enable recognition/generation of imitation motions. The robot associates the arm motion which reproduces the observed object's motion presented by a human operator. Experimental results proved the generalization capability of our method, which enables the robot to imitate not only motion it has experienced, but also unknown motion through nonlinear combination of the experienced motions.     

Chaotic interactions of self-replicating RNA

A general system of high-order differential equations describing complex dynamics of replicating biomolecules is given. Symmetry relations and coordinate transformations of general replication systems leading to topologically equivalent systems are derived. Three chaotic attractors observed in Lotka-Volterra equations of dimension n = 3 are shown to represent three cross-sections of one and the same chaotic regime. Also a fractal torus in a generalized three-dimensional Lotka-Volterra Model has been linked to one of the chaotic attractors. The strange attractors are studied in the equivalent four-dimensional catalytic replicator network. The fractal torus has been examined in adapted Lotka-Volterra equations. Analytic expressions are derived for the Lyapunov exponents of the flow in the replicator system. Lyapunov spectra for different pathways into chaos has been calculated. In the generalized Lotka-Volterra system a second inner rest point--coexisting with (quasi)-periodic orbits--can be observed; with an abundance of different bifurcations. Pathways from chaotic tori, via quasi-periodic tori, via limit cycles, via multi-periodic orbits--emerging out of periodic doubling bifurcations--to "simple" chaotic attractors can be found.