7 papers
Natural Invariant Measures for Chaotic Game Dynamics: Finding Order in Chaos
Jakub Bielawski, Thiparat Chotibut, Fryderyk Falniowski +2
We study the long-term behavior of the Multiplicative Weights Update (MWU) algorithm in game settings where learning dynamics frequently fail to converge to Nash equilibria and ins…
Strange bifurcation diagrams
Jakub Bielawski, Thiparat Chotibut, Fryderyk Falniowski +2
We investigate a family of one dimensional maps for which the bifurcation diagram looks differently than the usual ones. We describe and exemplify various unique and interesting ph…
On the Complexity of Learning Nash Equilibria
Oliver Biggar, Christos Papadimitriou, Georgios Piliouras
We know that the Nash equilibria of a game cannot be computed efficiently unless . But can they be learned? Are there dynamics that (1) can be computed efficiently by the…
Chaos in Autobidding Auctions
Ioannis Anagnostides, Ian Gemp, Georgios Piliouras +1
As autobidding systems increasingly dominate online advertising auctions, characterizing their long-term dynamical behavior is brought to the fore. In this paper, we examine the dy…
Tight Inapproximability for Welfare-Maximizing Autobidding Equilibria
Ioannis Anagnostides, Ian Gemp, Georgios Piliouras +1
We examine the complexity of computing welfare- and revenue-maximizing equilibria in autobidding second-price auctions subject to return-on-spend (RoS) constraints. We show that co…
Charting the Shapes of Stories with Game Theory
Constantinos Daskalakis, Ian Gemp, Yanchen Jiang +3
Stories are records of our experiences and their analysis reveals insights into the nature of being human. Successful analyses are often interdisciplinary, leveraging mathematical…