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 establish that first-order methods avoid strict saddle points for almost all initializations. Our results apply to a wide variety of first-order methods, including (manifold) gradient descent, block coordinate descent, mirror descent and variants thereof. The connecting thread is that such algorithms can be studied from a dynamical systems perspective in which appropriate instantiations of the Stable Manifold Theorem allow for a global stability analysis. Thus, neither access to second-order derivative information nor randomness beyond initialization is necessary to provably avoid strict saddle points. [ABSTRACT FROM AUTHOR]

We design a new class of vertex and set cover games, where the price of anarchy bounds match the best known constant factor approximation guarantees for the centralized optimization problems for linear and also for submodular costs. This is in contrast to all previously studied covering games, where the price of anarchy grows linearly with the size of the game. Both the game design and the price of anarchy results are based on structural properties of the linear programming relaxations. For linear costs we also exhibit simple best response dynamics that converge to Nash equilibria in linear time. [ABSTRACT FROM AUTHOR]

We analyze the performance of protocols for load balancing in distributed systems based on no-regret algorithms from online learning theory. These protocols treat load balancing as a repeated game and apply algorithms whose average performance over time is guaranteed to match or exceed the average performance of the best strategy in hindsight. Our approach captures two major aspects of distributed systems. First, in our setting of atomic load balancing, every single process can have a significant impact on the performance and behavior of the system. Furthermore, although in distributed systems participants can query the current state of the system they cannot reliably predict the effect of their actions on it. We address this issue by considering load balancing games in the bulletin board model, where players can find out the delay on all machines, but do not have information on what their experienced delay would have been if they had selected another machine. We show that under these more realistic assumptions, if all players use the well-known multiplicative weights algorithm, then the quality of the resulting solution is exponentially better than the worst correlated equilibrium, and almost as good as that of the worst Nash. These tighter bounds are derived from analyzing the dynamics of a multi-agent learning system. [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]

We introduce α-Rank, a principled evolutionary dynamics methodology, for the evaluation and ranking of agents in large-scale multi-agent interactions, grounded in a novel dynamical game-theoretic solution concept called Markov-Conley chains (MCCs). The approach leverages continuous-time and discrete-time evolutionary dynamical systems applied to empirical games, and scales tractably in the number of agents, in the type of interactions (beyond dyadic), and the type of empirical games (symmetric and asymmetric). Current models are fundamentally limited in one or more of these dimensions, and are not guaranteed to converge to the desired game-theoretic solution concept (typically the Nash equilibrium). α-Rank automatically provides a ranking over the set of agents under evaluation and provides insights into their strengths, weaknesses, and long-term dynamics in terms of basins of attraction and sink components. This is a direct consequence of the correspondence we establish to the dynamical MCC solution concept when the underlying evolutionary model's ranking-intensity parameter, α, is chosen to be large, which exactly forms the basis of α-Rank. In contrast to the Nash equilibrium, which is a static solution concept based solely on fixed points, MCCs are a dynamical solution concept based on the Markov chain formalism, Conley's Fundamental Theorem of Dynamical Systems, and the core ingredients of dynamical systems: fixed points, recurrent sets, periodic orbits, and limit cycles. Our α-Rank method runs in polynomial time with respect to the total number of pure strategy profiles, whereas computing a Nash equilibrium for a general-sum game is known to be intractable. We introduce mathematical proofs that not only provide an overarching and unifying perspective of existing continuous- and discrete-time evolutionary evaluation models, but also reveal the formal underpinnings of the α-Rank methodology. We illustrate the method in canonical games and empirically validate it in several domains, including AlphaGo, AlphaZero, MuJoCo Soccer, and Poker. [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]