Convergence Guarantees for a Decentralized Algorithm Achieving Pareto Optimality

We consider N agents, each picking actions froma finite set and receiving a payoff according to its individualutility function that may depend on the actions picked byothers. An agent has no knowledge about the functional formof its utility and can only measure its instantaneous value.It is assumed that all agents pick actions and receive payoffssynchronously. For this setting, a fully decentralized iterativealgorithm for achieving Pareto optimality i.e. picking actionsthat maximize the sum of all utilities was proposed by Mardenet. al. in [1] that lacks convergence guarantees. By schedulinga certain noise parameter to go to zero along iterations of thisalgorithm, conditions that guarantee convergence in probabilityare derived in this paper.