4 papers
Computing stable limit cycles of learning in games
Oliver Biggar, Christos Papadimitriou
Many well-studied learning dynamics, such as fictitious play and the replicator, are known to not converge in general -player games. The simplest mode of non-convergence is cycl…
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…
Faster shortest-path algorithms using the acyclic-connected tree
Elis Stefansson, Oliver Biggar, Karl H. Johansson
We provide a method to obtain beyond-worst-case time complexity for any single-source-shortest-path (SSSP) algorithm by exploiting modular structures in graphs. The key novelty is…
Sink equilibria and the attractors of learning in games
Oliver Biggar, Christos Papadimitriou
Characterizing the limit behavior -- that is, the attractors -- of learning dynamics is one of the most fundamental open questions in game theory. In recent work on this front, it…