Convergence to Equilibria in Distributed, Selfish Reallocation Processes with Weighted Tasks

We consider the problem of dynamically reallocating (or re‐routing) m weighted tasks among a set of n uniform resources (one may think of the tasks as selfish players). We assume an arbitrary initial placement of tasks, and we study the performance of distributed, natural reallocation algorithms. We are interested in the time it takes the system to converge to an equilibrium (or get close to an equilibrium). Our main contributions are (i) a modification of the protocol in 2006 that yields faster convergence to equilibrium, together with a matching lower bound, and (ii) a non‐trivial extension to weighted tasks.