Browse
Submit Data
Databases
API
Help

Dataset Information

24 Views

0 Connections

0 Citations

0 Reanalyses

0 Downloads

Omics score: 0

Navigable networks as Nash equilibria of navigation games.

ABSTRACT: Common sense suggests that networks are not random mazes of purposeless connections, but that these connections are organized so that networks can perform their functions well. One function common to many networks is targeted transport or navigation. Here, using game theory, we show that minimalistic networks designed to maximize the navigation efficiency at minimal cost share basic structural properties with real networks. These idealistic networks are Nash equilibria of a network construction game whose purpose is to find an optimal trade-off between the network cost and navigability. We show that these skeletons are present in the Internet, metabolic, English word, US airport, Hungarian road networks, and in a structural network of the human brain. The knowledge of these skeletons allows one to identify the minimal number of edges, by altering which one can efficiently improve or paralyse navigation in the network.

SUBMITTER: Gulyas A

PROVIDER: S-EPMC4506547 | biostudies-literature | 2015 Jul

REPOSITORIES: biostudies-literature

ACCESS DATA

Json Xml

Publications

Navigable networks as Nash equilibria of navigation games.

Gulyás András A Bíró József J JJ Kőrösi Attila A Rétvári Gábor G Krioukov Dmitri D

Nature communications 20150703

Common sense suggests that networks are not random mazes of purposeless connections, but that these connections are organized so that networks can perform their functions well. One function common to many networks is targeted transport or navigation. Here, using game theory, we show that minimalistic networks designed to maximize the navigation efficiency at minimal cost share basic structural properties with real networks. These idealistic networks are Nash equilibria of a network construction ...[more]

PMID: 26138277

Similar Datasets

Nash Equilibria in the Response Strategy of Correlated Games.

Project description:In nature and society, problems that arise when different interests are difficult to reconcile are modeled in game theory. While most applications assume that the players make decisions based only on the payoff matrix, a more detailed modeling is necessary if we also want to consider the influence of correlations on the decisions of the players. We therefore extend here the existing framework of correlated strategies by giving the players the freedom to respond to the instructions of the correlation device by probabilistically following or not following its suggestions. This creates a new type of games that we call "correlated games". The associated response strategies that can solve these games turn out to have a rich structure of Nash equilibria that goes beyond the correlated equilibrium and pure or mixed-strategy solutions and also gives better payoffs in certain cases. We here determine these Nash equilibria for all possible correlated Snowdrift games and we find these solutions to be describable by Ising models in thermal equilibrium. We believe that our approach paves the way to a study of correlations in games that uncovers the existence of interesting underlying interaction mechanisms, without compromising the independence of the players.

| S-EPMC6382789 | biostudies-literature

Spike-based decision learning of Nash equilibria in two-player games.

Project description:Humans and animals face decision tasks in an uncertain multi-agent environment where an agent's strategy may change in time due to the co-adaptation of others strategies. The neuronal substrate and the computational algorithms underlying such adaptive decision making, however, is largely unknown. We propose a population coding model of spiking neurons with a policy gradient procedure that successfully acquires optimal strategies for classical game-theoretical tasks. The suggested population reinforcement learning reproduces data from human behavioral experiments for the blackjack and the inspector game. It performs optimally according to a pure (deterministic) and mixed (stochastic) Nash equilibrium, respectively. In contrast, temporal-difference(TD)-learning, covariance-learning, and basic reinforcement learning fail to perform optimally for the stochastic strategy. Spike-based population reinforcement learning, shown to follow the stochastic reward gradient, is therefore a viable candidate to explain automated decision learning of a Nash equilibrium in two-player games.

| S-EPMC3459907 | biostudies-literature

A Quantum Annealing Algorithm for Finding Pure Nash Equilibria in Graphical Games

Project description:We introduce Q-Nash, a quantum annealing algorithm for the NP-complete problem of finding pure Nash equilibria in graphical games. The algorithm consists of two phases. The first phase determines all combinations of best response strategies for each player using classical computation. The second phase finds pure Nash equilibria using a quantum annealing device by mapping the computed combinations to a quadratic unconstrained binary optimization formulation based on the Set Cover problem. We empirically evaluate Q-Nash on D-Wave’s Quantum Annealer 2000Q using different graphical game topologies. The results with respect to solution quality and computing time are compared to a Brute Force algorithm and the Iterated Best Response heuristic.

| S-EPMC7304779 | biostudies-literature

Cooperation and self-interest: Pareto-inefficiency of Nash equilibria in finite random games.

Project description:The relative merits of cooperation and self-interest in an ensemble of strategic interactions can be investigated by using finite random games. In finite random games, finitely many players have finite numbers of actions and independently and identically distributed (iid) random payoffs with continuous distribution functions. In each realization, players are shown the values of all payoffs and then choose their strategies simultaneously. Noncooperative self-interest is modeled by Nash equilibrium (NE). Cooperation is advantageous when a NE is Pareto-inefficient. In ordinal games, the numerical value of the payoff function gives each player's ordinal ranking of payoffs. For a fixed number of players, as the number of actions of any player increases, the conditional probability that a pure strategic profile is not pure Pareto-optimal, given that it is a pure NE, apparently increases, but is bounded above strictly below 1. In games with transferable utility, the numerical payoff values may be averaged across actions (so that mixed NEs are meaningful) and added across players. In simulations of two-player games when both players have small, equal numbers of actions, as the number of actions increases, the probability that a NE (pure and mixed) attains the cooperative maximum declines rapidly; the gain from cooperation relative to the Nash high value decreases; and the gain from cooperation relative to the Nash low value rises dramatically. In the cases studied here, with an increasing number of actions, cooperation is increasingly likely to become advantageous compared with pure self-interest, but self-interest can achieve all that cooperation could achieve in a nonnegligible fraction of cases. These results can be interpreted in terms of cooperation in societies and mutualism in biology.

| S-EPMC21404 | biostudies-other

Nash equilibria in multi-agent motor interactions.

Project description:Social interactions in classic cognitive games like the ultimatum game or the prisoner's dilemma typically lead to Nash equilibria when multiple competitive decision makers with perfect knowledge select optimal strategies. However, in evolutionary game theory it has been shown that Nash equilibria can also arise as attractors in dynamical systems that can describe, for example, the population dynamics of microorganisms. Similar to such evolutionary dynamics, we find that Nash equilibria arise naturally in motor interactions in which players vie for control and try to minimize effort. When confronted with sensorimotor interaction tasks that correspond to the classical prisoner's dilemma and the rope-pulling game, two-player motor interactions led predominantly to Nash solutions. In contrast, when a single player took both roles, playing the sensorimotor game bimanually, cooperative solutions were found. Our methodology opens up a new avenue for the study of human motor interactions within a game theoretic framework, suggesting that the coupling of motor systems can lead to game theoretic solutions.

| S-EPMC2714462 | biostudies-literature

Navigable maps of structural brain networks across species.

Project description:Connectomes are spatially embedded networks whose architecture has been shaped by physical constraints and communication needs throughout evolution. Using a decentralized navigation protocol, we investigate the relationship between the structure of the connectomes of different species and their spatial layout. As a navigation strategy, we use greedy routing where nearest neighbors, in terms of geometric distance, are visited. We measure the fraction of successful greedy paths and their length as compared to shortest paths in the topology of connectomes. In Euclidean space, we find a striking difference between the navigability properties of mammalian and non-mammalian species, which implies the inability of Euclidean distances to fully explain the structural organization of their connectomes. In contrast, we find that hyperbolic space, the effective geometry of complex networks, provides almost perfectly navigable maps of connectomes for all species, meaning that hyperbolic distances are exceptionally congruent with the structure of connectomes. Hyperbolic maps therefore offer a quantitative meaningful representation of connectomes that suggests a new cartography of the brain based on the combination of its connectivity with its effective geometry rather than on its anatomy only. Hyperbolic maps also provide a universal framework to study decentralized communication processes in connectomes of different species and at different scales on an equal footing.

| S-EPMC7018228 | biostudies-literature

Growing Homophilic Networks Are Natural Navigable Small Worlds.

Project description:Navigability, an ability to find a logarithmically short path between elements using only local information, is one of the most fascinating properties of real-life networks. However, the exact mechanism responsible for the formation of navigation properties remained unknown. We show that navigability can be achieved by using only two ingredients present in the majority of networks: network growth and local homophily, giving a persuasive answer how the navigation appears in real-life networks. A very simple algorithm produces hierarchical self-similar optimally wired navigable small world networks with exponential degree distribution by using only local information. Adding preferential attachment produces a scale-free network which has shorter greedy paths, but worse (power law) scaling of the information extraction locality (algorithmic complexity of a search). Introducing saturation of the preferential attachment leads to truncated scale-free degree distribution that offers a good tradeoff between these parameters and can be useful for practical applications. Several features of the model are observed in real-life networks, in particular in the brain neural networks, supporting the earlier suggestions that they are navigable.

| S-EPMC4922669 | biostudies-literature

Pedestrian motion modelled by Fokker-Planck Nash games.

Project description:A new approach to modelling pedestrians' avoidance dynamics based on a Fokker-Planck (FP) Nash game framework is presented. In this framework, two interacting pedestrians are considered, whose motion variability is modelled through the corresponding probability density functions (PDFs) governed by FP equations. Based on these equations, a Nash differential game is formulated where the game strategies represent controls aiming at avoidance by minimizing appropriate collision cost functionals. The existence of Nash equilibria solutions is proved and characterized as a solution to an optimal control problem that is solved numerically. Results of numerical experiments are presented that successfully compare the computed Nash equilibria to the output of real experiments (conducted with humans) for four test cases.

| S-EPMC5627107 | biostudies-literature

Approximation of Nash equilibria and the network community structure detection problem.

Project description:Game theory based methods designed to solve the problem of community structure detection in complex networks have emerged in recent years as an alternative to classical and optimization based approaches. The Mixed Nash Extremal Optimization uses a generative relation for the characterization of Nash equilibria to identify the community structure of a network by converting the problem into a non-cooperative game. This paper proposes a method to enhance this algorithm by reducing the number of payoff function evaluations. Numerical experiments performed on synthetic and real-world networks show that this approach is efficient, with results better or just as good as other state-of-the-art methods.

| S-EPMC5415147 | biostudies-literature

Navigation of brain networks.

Project description:Understanding the mechanisms of neural communication in large-scale brain networks remains a major goal in neuroscience. We investigated whether navigation is a parsimonious routing model for connectomics. Navigating a network involves progressing to the next node that is closest in distance to a desired destination. We developed a measure to quantify navigation efficiency and found that connectomes in a range of mammalian species (human, mouse, and macaque) can be successfully navigated with near-optimal efficiency (>80% of optimal efficiency for typical connection densities). Rewiring network topology or repositioning network nodes resulted in 45-60% reductions in navigation performance. We found that the human connectome cannot be progressively randomized or clusterized to result in topologies with substantially improved navigation performance (>5%), suggesting a topological balance between regularity and randomness that is conducive to efficient navigation. Navigation was also found to (i) promote a resource-efficient distribution of the information traffic load, potentially relieving communication bottlenecks, and (ii) explain significant variation in functional connectivity. Unlike commonly studied communication strategies in connectomics, navigation does not mandate assumptions about global knowledge of network topology. We conclude that the topology and geometry of brain networks are conducive to efficient decentralized communication.

| S-EPMC6004443 | biostudies-literature

OmicsDI is part of the ELIXIR infrastructure

OmicsDI is an Elixir interoperability service. Learn more ›

Tweets

OmicsDI Databases

PRIDE
PeptideAtlas
MassIVE
JPOST Repository
Physiome Model Repository

EGA
EVA
ENA
LINCS
PAXDB
Cell Collective

MetaboLights
Metabolomics Workbench
MetabolomeExpress
GNPS
BioModels
FAIRDOMHub

ArrayExpress
dbGaP
ExpressionAtlas
GEO
NODE

Information

Databases
Help
API
Contact us
Code on GitHub
Terms of use
Submit Data