Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userStatics and dynamics of selfish interactions in distributed service systems
115
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We study a class of games which model the competition among agents to access some service provided by distributed service units and which exhibit congestion and frustration phenomena when service units have limited capacity. We propose a technique, based on the cavity method of statistical physics, to characterize the full spectrum of Nash equilibria of the game. The analysis reveals a large variety of equilibria, with very different statistical properties. Natural selfish dynamics, such as best-response, usually tend to large-utility equilibria, even though those of smaller utility are exponentially more numerous. Interestingly, the latter actually can be reached by selecting the initial conditions of the best-response dynamics close to the saturation limit of the service unit capacities. We also study a more realistic stochastic variant of the game by means of a simple and effective approximation of the average over the random parameters, showing that the properties of the average-case Nash equilibria are qualitatively similar to the deterministic ones.
rate research
Read More
We develop a computationally efficient technique to solve a fairly general distributed service provision problem with selfish users and imperfect information. In particular, in a context in which the service capacity of the existing infrastructure can be partially adapted to the user load by activating just some of the service units, we aim at finding the configuration of active service units that achieves the best trade-off between maintenance (e.g. energetic) costs for the provider and user satisfaction. The core of our technique resides in the implementation of a belief-propagation (BP) algorithm to evaluate the cost configurations. Numerical results confirm the effectiveness of our approach.
Simple binary-state coordination models are widely used to study collective socio-economic phenomena such as the spread of innovations or the adoption of products on social networks. The common trait of these systems is the occurrence of large-scale coordination events taking place abruptly, in the form of a cascade process, as a consequence of small perturbations of an apparently stable state. The conditions for the occurrence of cascade instabilities have been largely analysed in the literature, however for the same coordination models no sufficient attention was given to the relation between structural properties of (Nash) equilibria and possible outcomes of dynamical equilibrium selection. Using methods from the statistical physics of disordered systems, the present work investigates both analytically and numerically, the statistical properties of such Nash equilibria on networks, focusing mostly on random graphs. We provide an accurate description of these properties, which is then exploited to shed light on the mechanisms behind the onset of coordination/miscoordination on large networks. This is done studying the most common processes of dynamical equilibrium selection, such as best response, bounded-rational dynamics and learning processes. In particular, we show that well beyond the instability region, full coordination is still globally stochastically stable, however equilibrium selection processes with low stochasticity (e.g. best response) or strong memory effects (e.g. reinforcement learning) can be prevented from achieving full coordination by being trapped into a large (exponentially in number of agents) set of locally stable Nash equilibria at low/medium coordination (inefficient equilibria). These results should be useful to allow a better understanding of general coordination problems on complex networks.
We provide a compact derivation of the static and dynamic equations for infinite-dimensional particle systems in the liquid and glass phases. The static derivation is based on the introduction of an auxiliary disorder and the use of the replica method. The dynamic derivation is based on the general analogy between replicas and the supersymmetric formulation of dynamics. We show that static and dynamic results are consistent, and follow the Random First Order Transition scenario of mean field disordered glassy systems.
The Bitcoin protocol prescribes certain behavior by the miners who are responsible for maintaining and extending the underlying blockchain; in particular, miners who successfully solve a puzzle, and hence can extend the chain by a block, are supposed to release that block immediately. Eyal and Sirer showed, however, that a selfish miner is incentivized to deviate from the protocol and withhold its blocks under certain conditions. The analysis by Eyal and Sirer, as well as in followup work, considers a emph{single} deviating miner (who may control a large fraction of the hashing power in the network) interacting with a remaining pool of honest miners. Here, we extend this analysis to the case where there are emph{multiple} (non-colluding) selfish miners. We find that with multiple strategic miners, specific deviations from honest mining by multiple strategic agents can outperform honest mining, even if individually miners would not be incentivised to be dishonest. This previous point effectively renders the Bitcoin protocol to be less secure than previously thought.
Regret has been established as a foundational concept in online learning, and likewise has important applications in the analysis of learning dynamics in games. Regret quantifies the difference between a learners performance against a baseline in hindsight. It is well-known that regret-minimizing algorithms converge to certain classes of equilibria in games; however, traditional forms of regret used in game theory predominantly consider baselines that permit deviations to deterministic actions or strategies. In this paper, we revisit our understanding of regret from the perspective of deviations over partitions of the full emph{mixed} strategy space (i.e., probability distributions over pure strategies), under the lens of the previously-established $Phi$-regret framework, which provides a continuum of stronger regret measures. Importantly, $Phi$-regret enables learning agents to consider deviations from and to mixed strategies, generalizing several existing notions of regret such as external, internal, and swap regret, and thus broadening the insights gained from regret-based analysis of learning algorithms. We prove here that the well-studied evolutionary learning algorithm of replicator dynamics (RD) seamlessly minimizes the strongest possible form of $Phi$-regret in generic $2 times 2$ games, without any modification of the underlying algorithm itself. We subsequently conduct experiments validating our theoretical results in a suite of 144 $2 times 2$ games wherein RD exhibits a diverse set of behaviors. We conclude by providing empirical evidence of $Phi$-regret minimization by RD in some larger games, hinting at further opportunity for $Phi$-regret based study of such algorithms from both a theoretical and empirical perspective.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
