We study balanced allocations on graphs with removals. Load arrives at each edge e at an exponential rate and is then allocated to the vertex incident to e with the lowest current load. Load is removed from each vertex at an exponential rate. We identify a "conductance-like" quantity that determines if an equilibrium exists and allows us to bound the maximal load at equilibrium. Our analysis, based on simple potential function arguments, is very robust and can also handle noise in how the load is allocated. We also apply our general techniques to study the synchronous version of the process above, in which allocations and removals happen simultaneously at discrete time steps. We prove that, for any regular graph, in equilibrium, the expected difference in load across an edge, averaged over all edges, is at most 2. This implies, for example, that the two-choice process on the cycle has an O(n) gap between maximal and minimal load, improving the state-of-the-art by a log n factor.

Random walks on expanders play a crucial role in Markov Chain Monte Carlo algorithms, derandomization, graph theory, and distributed computing. A desirable property is that they are rapidly mixing, which is equivalent to having a spectral gap \(\gamma\) bounded away from 0.

We present a theoretical analysis of the Elo rating system, a popular method for ranking skills of players in an online setting. In particular, we study Elo under the Bradley-Terry-Luce model and, using techniques from Markov chain theory, show that Elo learns the model parameters at a rate competitive with the state-of-the-art. We apply our results to the problem of efficient tournament design and discuss a connection with the fastest-mixing Markov chain problem.