114 citations · 813 across the 92 of their papers we have counts for
21 papers · 1 filter
A Blockchain-Based Approach for Collaborative Formalization of Mathematics and Programs
Jin Xing Lim, Barnabé Monnot, Shaowei Lin +1
Formalization of mathematics is the process of digitizing mathematical knowledge, which allows for formal proof verification as well as efficient semantic searches. Given the large…
Online Learning in Periodic Zero-Sum Games
Tanner Fiez, Ryann Sim, Stratis Skoulakis +2
A seminal result in game theory is von Neumann's minmax theorem, which states that zero-sum games admit an essentially unique equilibrium solution. Classical learning results build…
Beyond Time-Average Convergence: Near-Optimal Uncoupled Online Learning via Clairvoyant Multiplicative Weights Update
Georgios Piliouras, Ryann Sim, Stratis Skoulakis
In this paper, we provide a novel and simple algorithm, Clairvoyant Multiplicative Weights Updates (CMWU) for regret minimization in general games. CMWU effectively corresponds to…
Learning Equilibria in Mean-Field Games: Introducing Mean-Field PSRO
Paul Muller, Mark Rowland, Romuald Elie +6
Recent advances in multiagent learning have seen the introduction ofa family of algorithms that revolve around the population-based trainingmethod PSRO, showing convergence to Nash…
Stochastic Multiplicative Weights Updates in Zero-Sum Games
James P. Bailey, Sai Ganesh Nagarajan, Georgios Piliouras
We study agents competing against each other in a repeated network zero-sum game while applying the multiplicative weights update (MWU) algorithm with fixed learning rates. In our…
Transaction Fees on a Honeymoon: Ethereum's EIP-1559 One Month Later
Daniël Reijsbergen, Shyam Sridhar, Barnabé Monnot +3
Ethereum Improvement Proposal (EIP) 1559 was recently implemented to transform Ethereum's transaction fee market. EIP-1559 utilizes an algorithmic update rule with a constant learn…
Constants of Motion: The Antidote to Chaos in Optimization and Game Dynamics
Georgios Piliouras, Xiao Wang
Several recent works in online optimization and game dynamics have established strong negative complexity results including the formal emergence of instability and chaos even in sm…
On the Approximability of Multistage Min-Sum Set Cover
Dimitris Fotakis, Panagiotis Kostopanagiotis, Vasileios Nakos +2
We investigate the polynomial-time approximability of the multistage version of Min-Sum Set Cover (), a natural and intriguing generalization of the classical List U…
Evolutionary Dynamics and -Regret Minimization in Games
Georgios Piliouras, Mark Rowland, Shayegan Omidshafiei +4
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 t…
Exploration-Exploitation in Multi-Agent Competition: Convergence with Bounded Rationality
Stefanos Leonardos, Georgios Piliouras, Kelly Spendlove
The interplay between exploration and exploitation in competitive multi-agent learning is still far from being well understood. Motivated by this, we study smooth Q-learning, a pro…
From Griefing to Stability in Blockchain Mining Economies
Yun Kuen Cheung, Stefanos Leonardos, Georgios Piliouras +1
We study a game-theoretic model of blockchain mining economies and show that griefing, a practice according to which participants harm other participants at some lesser cost to the…
Online Optimization in Games via Control Theory: Connecting Regret, Passivity and Poincaré Recurrence
Yun Kuen Cheung, Georgios Piliouras
We present a novel control-theoretic understanding of online optimization and learning in games, via the notion of passivity. Passivity is a fundamental concept in control theory,…
Efficient Online Learning for Dynamic k-Clustering
Dimitris Fotakis, Georgios Piliouras, Stratis Skoulakis
We study dynamic clustering problems from the perspective of online learning. We consider an online learning problem, called \textit{Dynamic -Clustering}, in which centers a…
Global Convergence of Multi-Agent Policy Gradient in Markov Potential Games
Stefanos Leonardos, Will Overman, Ioannis Panageas +1
Potential games are arguably one of the most important and widely studied classes of normal form games. They define the archetypal setting of multi-agent coordination as all agent…
Learning in Markets: Greed Leads to Chaos but Following the Price is Right
Yun Kuen Cheung, Stefanos Leonardos, Georgios Piliouras
We study learning dynamics in distributed production economies such as blockchain mining, peer-to-peer file sharing and crowdsourcing. These economies can be modelled as multi-prod…
Learning in Matrix Games can be Arbitrarily Complex
Gabriel P. Andrade, Rafael Frongillo, Georgios Piliouras
A growing number of machine learning architectures, such as Generative Adversarial Networks, rely on the design of games which implement a desired functionality via a Nash equilibr…
Scaling up Mean Field Games with Online Mirror Descent
Julien Perolat, Sarah Perrin, Romuald Elie +5
We address scaling up equilibrium computation in Mean Field Games (MFGs) using Online Mirror Descent (OMD). We show that continuous-time OMD provably converges to a Nash equilibriu…
Follow-the-Regularized-Leader Routes to Chaos in Routing Games
Jakub Bielawski, Thiparat Chotibut, Fryderyk Falniowski +3
We study the emergence of chaotic behavior of Follow-the-Regularized Leader (FoReL) dynamics in games. We focus on the effects of increasing the population size or the scale of cos…
Dynamical Analysis of the EIP-1559 Ethereum Fee Market
Stefanos Leonardos, Barnabé Monnot, Daniël Reijsbergen +2
Participation in permissionless blockchains results in competition over system resources, which needs to be controlled with fees. Ethereum's current fee mechanism is implemented vi…
Poincaré-Bendixson Limit Sets in Multi-Agent Learning
Aleksander Czechowski, Georgios Piliouras
A key challenge of evolutionary game theory and multi-agent learning is to characterize the limit behavior of game dynamics. Whereas convergence is often a property of learning alg…
Solving Min-Max Optimization with Hidden Structure via Gradient Descent Ascent
Lampros Flokas, Emmanouil-Vasileios Vlatakis-Gkaragkounis, Georgios Piliouras
Many recent AI architectures are inspired by zero-sum games, however, the behavior of their dynamics is still not well understood. Inspired by this, we study standard gradient desc…