期刊名称：Proceedings of the National Academy of Sciences
印刷版ISSN：0027-8424
电子版ISSN：1091-6490
出版年度：2016
卷号：113
期号：46
页码：12985-12990
DOI：10.1073/pnas.1610244113
语种：English
出版社：The National Academy of Sciences of the United States of America
摘要：SignificanceMany real-life decisions where one out of two actions must be chosen can be modeled on networks consisting of individuals who are either coordinating, that is, take an action only if sufficient neighbors are also doing so, or anticoordinating, that is, take an action only if too many neighbors are doing the opposite. It is not yet known whether such networks tend to reach a state where every individual is satisfied with his decision. We show that indeed any network of coordinating, and any network of anticoordinating individuals always reaches a satisfactory state, regardless of how they are connected, how different their preferences are, and how many simultaneous decisions are made over time. Binary decisions of agents coupled in networks can often be classified into two types: "coordination," where an agent takes an action if enough neighbors are using that action, as in the spread of social norms, innovations, and viral epidemics, and "anticoordination," where too many neighbors taking a particular action causes an agent to take the opposite action, as in traffic congestion, crowd dispersion, and division of labor. Both of these cases can be modeled using linear-threshold-based dynamics, and a fundamental question is whether the individuals in such networks are likely to reach decisions with which they are satisfied. We show that, in the coordination case, and perhaps more surprisingly, also in the anticoordination case, the agents will indeed always tend to reach satisfactory decisions, that is, the network will almost surely reach an equilibrium state. This holds for every network topology and every distribution of thresholds, for both asynchronous and partially synchronous decision-making updates. These results reveal that irregular network topology, population heterogeneity, and partial synchrony are not sufficient to cause cycles or nonconvergence in linear-threshold dynamics; rather, other factors such as imitation or the coexistence of coordinating and anticoordinating agents must play a role.
关键词：evolutionary game theory ; network games ; best-response dynamics ; linear-threshold model ; equilibrium convergence
