We study the problem of minimizing a convex function over probability measures supported in a graph. We build upon the recent formulation of optimal transport over discrete domains to propose a method that generates a sequence that provably converges to a minimum of the objective function and smoothly transports mass over the edges of the graph. Moreover, we identify novel relation between Riemannian gradient flows and perturbed best response protocols that provide sufficient conditions for the convergence of the proposed algorithm. Numerical results show practical advantages over existing approaches with respect to the implementability and convergence rates.