4 papers
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…
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…