Convergence guarantees for a decentralized algorithm achieving pareto optimality

We consider N agents, each picking actions from a finite set and receiving a payoff according to its individual utility function that may depend on the actions picked by others. An agent has no knowledge about the functional form of its utility and can only measure its instantaneous value. It is assumed that all agents pick actions and receive payoffs synchronously. For this setting, a fully decentralized iterative algorithm for achieving Pareto optimality i.e. picking actions that maximize the sum of all utilities was proposed by Marden et. al. in [1] that lacks convergence guarantees. By scheduling a certain noise parameter to go to zero along iterations of this algorithm, conditions that guarantee convergence in probability are derived in this paper.