Search

Recent studies have raised concerns on the inevitability of chaos in congestion games with large learning rates. We further investigate this phenomenon by exploring the learning dynamics in simple two-resource congestion games, where a continuum of agents learns according to a simplified experience-weighted attraction algorithm. The model is characterized by three key parameters: a population intensity of choice (learning rate), a discount factor (recency bias or exploration parameter), and the cost function asymmetry. The intensity of choice captures agents' economic rationality in their tendency to approximately best respond to the other agent's behavior. The discount factor captures a type of memory loss of agents, where past outcomes matter exponentially less than the recent ones. Our main findings reveal that while increasing the intensity of choice destabilizes the system for any discount factor, whether the resulting dynamics remains predictable or becomes unpredictable and chaotic depends on both the memory loss and the cost asymmetry. As memory loss increases, the chaotic regime gives place to a periodic orbit of period 2 that is globally attracting except for a countable set of points that lead to the equilibrium. Therefore, memory loss can suppress chaotic behaviors. The results highlight the crucial role of memory loss in mitigating chaos and promoting predictable outcomes in congestion games, providing insights into designing control strategies in resource allocation systems susceptible to chaotic behaviors. [ABSTRACT FROM AUTHOR]

The Nash equilibrium—a, combination of choices by the players of a game from which no self-interested player would deviate—is the predominant solution concept in game theory. Even though every game has a Nash equilibrium, it is not known whether there are deterministic behaviors of the players who play a game repeatedly that are guaranteed to converge to a Nash equilibrium of the game from all starting points. If one assumes that the players’ behavior is a discrete-time or continuous-time rule whereby the current mixed strategy profile is mapped to the next, this question becomes a problem in the theory of dynamical systems. We apply this theory, and in particular Conley index theory, to prove a general impossibility result: There exist games, for which all game dynamics fail to converge to Nash equilibria from all starting points. The games which help prove this impossibility result are degenerate, but we conjecture that the same result holds, under computational complexity assumptions, for nondegenerate games. We also prove a stronger impossibility result for the solution concept of approximate Nash equilibria: For a set of games of positive measure, no game dynamics can converge to the set of approximate Nash equilibria for a sufficiently small yet substantial approximation bound. Our results establish that, although the notions of Nash equilibrium and its computation-inspired approximations are universally applicable in all games, they are fundamentally incomplete as predictors of long-term player behavior. [ABSTRACT FROM AUTHOR]

From a two-agent, two-strategy congestion game where both agents apply the multiplicative weights update algorithm, we obtain a two-parameter family of maps of the unit square to itself. Interesting dynamics arise on the invariant diagonal, on which a two-parameter family of bimodal interval maps exhibits periodic orbits and chaos. While the fixed point b corresponding to a Nash equilibrium of such map f is usually repelling, it is globally Cesàro attracting on the diagonal, that is, lim n → ∞ 1 n ∑ k = 0 n − 1 f k (x) = b for every x ∈ (0 , 1). This solves a known open question whether there exists a 'natural' nontrivial smooth map other than x ↦ a x e − x with centres of mass of all periodic orbits coinciding. We also study the dependence of the dynamics on the two parameters. [ABSTRACT FROM AUTHOR]

The rapid evolution of blockchain technology has brought together stakeholders from fundamentally different backgrounds. The result is a diverse ecosystem, as exemplified by the development of a wide range of different blockchain protocols. This raises questions for decision and policy makers: How do different protocols compare? What are their tradeoffs? Existing efforts to survey the area reveal a fragmented terminology and the lack of a unified framework to reason about the properties of blockchain protocols. In this article, we work toward bridging this gap. We present a five-dimensional design space with a modular structure in which protocols can be compared and understood. Based on these five axes—optimality, stability, efficiency, robustness, and persistence—we organize the properties of existing protocols in subcategories of increasing granularity. The result is a dynamic scheme—termed the PREStO framework—which aids the interaction between stakeholders of different backgrounds, including managers and investors, and which enables systematic reasoning about blockchain protocols. We illustrate its value by comparing existing protocols and identifying research challenges, hence making a first step toward understanding the blockchain ecosystem through a more comprehensive lens. [ABSTRACT FROM AUTHOR]

Summary: We present an overview of hybrid Casper the Friendly Finality Gadget (FFG), a proof‐of‐stake checkpointing protocol overlaid onto Ethereum's proof‐of‐work blockchain. We describe its core functionalities and reward scheme and explore its properties. Our findings indicate that Casper's implemented incentives mechanism ensures liveness, while providing safety guarantees that improve over standard proof‐of‐work protocols. On the basis of a minimal impact implementation of the protocol as a smart contract on the blockchain, we discuss additional issues related to parametrization, funding, throughput, and network overhead and detect potential limitations. [ABSTRACT FROM AUTHOR]

Summary: Proof of stake (PoS) protocols rely on voting mechanisms to reach consensus on the current state. If an enhanced majority of staking nodes, also called validators, agree on a proposed block, then this block is appended to the blockchain. Yet these protocols remain vulnerable to faults caused by validators who abstain either accidentally or maliciously. To protect against such faults while retaining the PoS selection and reward allocation schemes, we study weighted voting in validator committees. We formalize the block creation process and introduce validators' voting profiles which we update by a multiplicative weights algorithm relative to validators' voting behavior and aggregate blockchain rewards. Using this framework, we leverage weighted majority voting rules that optimize collective decision making to show, both numerically and analytically, that the consensus mechanism is more robust if validators' votes are appropriately scaled. We raise potential issues and limitations of weighted voting in trustless, decentralized networks and relate our results to the design of current PoS protocols. [ABSTRACT FROM AUTHOR]

We study the Bitcoin and Ether price series under a financial perspective. Specifically, we use two econometric models to perform a two-layer analysis to study the correlation and prediction of Bitcoin and Ether price series with traditional assets. In the first part of this study, we model the probability of positive returns via a Bayesian logistic model. Even though the fitting performance of the logistic model is poor, we find that traditional assets can explain some of the variability of the price returns. Along with the fact that standard models fail to capture the statistic and econometric attributes—such as extreme variability and heteroskedasticity—of cryptocurrencies, this motivates us to apply a novel Non-Homogeneous Hidden Markov model to these series. In particular, we model Bitcoin and Ether prices via the non-homogeneous Pólya-Gamma Hidden Markov (NHPG) model, since it has been shown that it outperforms its counterparts in conventional financial data. The transition probabilities of the underlying hidden process are modeled via a logistic link whereas the observed series follow a mixture of normal regressions conditionally on the hidden process. Our results show that the NHPG algorithm has good in-sample performance and captures the heteroskedasticity of both series. It identifies frequent changes between the two states of the underlying Markov process. In what constitutes the most important implication of our study, we show that there exist linear correlations between the covariates and the ETH and BTC series. However, only the ETH series are affected non-linearly by a subset of the accounted covariates. Finally, we conclude that the large number of significant predictors along with the weak degree of predictability performance of the algorithm back up earlier findings that cryptocurrencies are unlike any other financial assets and predicting the cryptocurrency price series is still a challenging task. These findings can be useful to investors, policy makers, traders for portfolio allocation, risk management and trading strategies. [ABSTRACT FROM AUTHOR]

In 1950, Nash proposed a natural equilibrium solution concept for games hence called Nash equilibrium, and proved that all finite games have at least one. The proof is through a simple yet ingenious application of Brouwer's (or, in another version Kakutani's) fixed point theorem, the most sophisticated result in his era's topology—in fact, recent algorithmic work has established that Nash equilibria are computationally equivalent to fixed points. In this paper, we propose a new class of universal non-equilibrium solution concepts arising from an important theorem in the topology of dynamical systems that was unavailable to Nash. This approach starts with both a game and a learning dynamics, defined over mixed strategies. The Nash equilibria are fixpoints of the dynamics, but the system behavior is captured by an object far more general than the Nash equilibrium that is known in dynamical systems theory as chain recurrent set. Informally, once we focus on this solution concept—this notion of "the outcome of the game"—every game behaves like a potential game with the dynamics converging to these states. In other words, unlike Nash equilibria, this solution concept is algorithmic in the sense that it has a constructive proof of existence. We characterize this solution for simple benchmark games under replicator dynamics, arguably the best known evolutionary dynamics in game theory. For (weighted) potential games, the new concept coincides with the fixpoints/equilibria of the dynamics. However, in (variants of) zero-sum games with fully mixed (i.e., interior) Nash equilibria, it covers the whole state space, as the dynamics satisfy specific information theoretic constants of motion. We discuss numerous novel computational, as well as structural, combinatorial questions raised by this chain recurrence conception of games. [ABSTRACT FROM AUTHOR]

Small changes to the parameters of a system can lead to abrupt qualitative changes of its behavior, a phenomenon known as bifurcation. Such instabilities are typically considered problematic, however, we show that their power can be leveraged to design novel types of mechanisms. Hysteresis mechanisms use transient changes of system parameters to induce a permanent improvement to its performance via optimal equilibrium selection. Optimal control mechanisms induce convergence to states whose performance is better than even the best equilibrium. We apply these mechanisms in two different settings that illustrate the versatility of bifurcation mechanism design. In the first one we explore how introducing flat taxation could improve social welfare, despite decreasing agent “rationality,” by destabilizing inefficient equilibria. From there we move on to consider a well known game of tumor metabolism and use our approach to derive potential new cancer treatment strategies. [ABSTRACT FROM AUTHOR]

Black-Scholes (BS) is a remarkable quotation model for European option pricing in financial markets. Option prices are calculated using an analytical formula whose main inputs are strike (at which price to exercise) and volatility. The BS framework assumes that volatility remains constant across all strikes; however, in practice, it varies. How do traders come to learn these parameters? We introduce natural agent-based models, in which traders update their beliefs about the true implied volatility based on the opinions of other agents. We prove exponentially fast convergence of these opinion dynamics, using techniques from control theory and leader-follower models, thus providing a resolution between theory and market practices. We allow for two different models, one with feedback and one with an unknown leader., Competing Interests: We declare we have no competing interests., (© 2020 The Authors.)

Biological networks, like most engineered networks, are not the product of a singular design but rather are the result of a long process of refinement and optimization. Many large real-world networks are comprised of well-defined and meaningful smaller modules. While engineered networks are designed and refined by humans with particular goals in mind, biological networks are created by the selective pressures of evolution. In this paper, we seek to define aspects of network architecture that are shared among different types of evolved biological networks. First, we developed a new mathematical model, the Stochastic Block Model with Path Selection (SBM-PS) that simulates biological network formation based on the selection of edges that increase clustering. SBM-PS can produce modular networks whose properties resemble those of real networks. Second, we analyzed three real networks of very different types, and showed that all three can be fit well by the SBM-PS model. Third, we showed that modular elements within the three networks correspond to meaningful biological structures. The networks chosen for analysis were a proteomic network composed of all proteins required for mitochondrial function in budding yeast, a mesoscale anatomical network composed of axonal connections among regions of the mouse brain, and the connectome of individual neurons in the nematode C. elegans. We find that the three networks have common architectural features, and each can be divided into subnetworks with characteristic topologies that control specific phenotypic outputs., (Copyright © 2017 Elsevier Ltd. All rights reserved.)