This paper introduces a model based upon games on an evolving network, and develops three clustering algorithms according to it. In the clustering algorithms, data points for clustering are regarded as players who can make decisions in games. On the network describing relationships among data points, an edge-removing-and-rewiring (ERR) function is employed to explore in a neighborhood of a data point, which removes edges connecting to neighbors with small payoffs, and creates new edges to neighbors with larger payoffs. As such, the connections among data points vary over time. During the evolution of network, some strategies are spread in the network. As a consequence, clusters are formed automatically, in which data points with the same evolutionarily stable strategy are collected as a cluster, so the number of evolutionarily stable strategies indicates the number of clusters. Moreover, the experimental results have demonstrated that data points in datasets are clustered reasonably and efficiently, and the comparison with other algorithms also provides an indication of the effectiveness of the proposed algorithms.
Evolutionary game theory, which combines the traditional game theory with the idea of evolution, is based on the assumption of bounded rationality. On the contrary, in classical game theory players are supposed to be perfectly rational or hyper-rational, and always choose optimal strategies in complex environments. Finite information and cognitive limitations, however, often make rational decisions inaccessible. Besides, perfect rationality may cause the so-called backward induction paradox @cite_12 in finitely repeated games. On the other hand, as the relaxation of perfect rationality in classical game theory, bounded rationality means people in games need only part rationality @cite_17 , which explains why in many cases people respond or play instinctively according to heuristic rules and social norms rather than adopting the strategies indicated by rational game theory @cite_7 . So, various dynamic rules can be defined to characterize the boundedly rational behavior of players in evolutionary game theory.
@cite_7 @cite_12 @cite_17
1992195122 2145922343 1688243677
Abstract Game theory is one of the key paradigms behind many scientific disciplines from biology to behavioral sciences to economics. In its evolutionary form and especially when the interacting agents are linked in a specific social network the underlying solution concepts and methods are very similar to those applied in non-equilibrium statistical physics. This review gives a tutorial-type overview of the field for physicists. The first four sections introduce the necessary background in classical and evolutionary game theory from the basic definitions to the most important results. The fifth section surveys the topological complications implied by non-mean-field-type social network structures in general. The next three sections discuss in detail the dynamic behavior of three prominent classes of models: the Prisoner's Dilemma, the Rock–Scissors–Paper game, and Competing Associations. The major theme of the review is in what sense and how the graph structure of interactions can modify and enrich the picture of long term behavioral patterns emerging in evolutionary games. Les AA. montrent que le paradoxe de l'induction retrograde (backward induction) est resoluble. Une solution repose sur le fait que les joueurs (ou agents) rationnels ne sont pas necessairement en position d'utiliser l'argument d'induction retrograde Part I Journey to a 21st birthday: the boy in Wisconsin forests and fields education in Chicago encounter with a scientific revolution - political science at Chicago. Part II The scientist as a young man: a taste of research - the City Managers' Association managing research - Berkeley teaching at Illinois Tech a matter of loyalty building a business school - the Graduate School of Industrial Administration research and science politics mazes without minotaurs roots of artificial intelligence climbing the mountain - artificial intelligence achieved. Part III View from the mountain: exploring the plain personal threads in the warp creating a university environment for cognitive science and A.I. on being argumentative the student troubles the scientist as politician foreign adventures. Part IV Research after 60: from Nobel to now the amateur diplomat in China and the Soviet Union guides for choice. Afterword: the scientist as problem solver.