A Quantum Annealing Algorithm for Finding Pure Nash Equilibria in Graphical Games
Ontology highlight
ABSTRACT:
SUBMITTER: Krzhizhanovskaya V
PROVIDER: S-EPMC7304779 | biostudies-literature | 2020 May
REPOSITORIES: biostudies-literature
Similar Datasets
Project description: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.
| S-EPMC4506547 | biostudies-literature
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
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
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
Project description:Finding a Hadamard matrix (H-matrix) among the set of all binary matrices of corresponding order is a hard problem, which potentially can be solved by quantum computing. We propose a method to formulate the Hamiltonian of finding H-matrix problem and address its implementation limitation on existing quantum annealing machine (QAM) that allows up to quadratic terms, whereas the problem naturally introduces higher order ones. For an M-order H-matrix, such a limitation increases the number of variables from M2 to (M3 + M2 - M)/2, which makes the formulation of the Hamiltonian too exhaustive to do by hand. We use symbolic computing techniques to manage this problem. Three related cases are discussed: (1) finding N < M orthogonal binary vectors, (2) finding M-orthogonal binary vectors, which is equivalent to finding a H-matrix, and (3) finding N-deleted vectors of an M-order H-matrix. Solutions of the problems by a 2-body simulated annealing software and by an actual quantum annealing hardware are also discussed.
| S-EPMC6779766 | biostudies-literature
Project description:Lattice protein folding models are a cornerstone of computational biophysics. Although these models are a coarse grained representation, they provide useful insight into the energy landscape of natural proteins. Finding low-energy threedimensional structures is an intractable problem even in the simplest model, the Hydrophobic-Polar (HP) model. Description of protein-like properties are more accurately described by generalized models, such as the one proposed by Miyazawa and Jernigan (MJ), which explicitly take into account the unique interactions among all 20 amino acids. There is theoretical and experimental evidence of the advantage of solving classical optimization problems using quantum annealing over its classical analogue (simulated annealing). In this report, we present a benchmark implementation of quantum annealing for lattice protein folding problems (six different experiments up to 81 superconducting quantum bits). This first implementation of a biophysical problem paves the way towards studying optimization problems in biophysics and statistical mechanics using quantum devices.
| S-EPMC3417777 | biostudies-literature
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
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
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
Project description:We introduce the notion of reinforcement quantum annealing (RQA) scheme in which an intelligent agent searches in the space of Hamiltonians and interacts with a quantum annealer that plays the stochastic environment role of learning automata. At each iteration of RQA, after analyzing results (samples) from the previous iteration, the agent adjusts the penalty of unsatisfied constraints and re-casts the given problem to a new Ising Hamiltonian. As a proof-of-concept, we propose a novel approach for casting the problem of Boolean satisfiability (SAT) to Ising Hamiltonians and show how to apply the RQA for increasing the probability of finding the global optimum. Our experimental results on two different benchmark SAT problems (namely factoring pseudo-prime numbers and random SAT with phase transitions), using a D-Wave 2000Q quantum processor, demonstrated that RQA finds notably better solutions with fewer samples, compared to the best-known techniques in the realm of quantum annealing.
| S-EPMC7224393 | biostudies-literature