A distributed algorithm to obtain repeated games equilibria with discounting

摘要

We introduce a distributed algorithm to negotiate equilibria on repeated games with discounting. It is based on the Folk Theorem, which allows obtaining better payoffs for all players by enforcing cooperation among players when possible. Our algorithm works on incomplete information games: each player needs not knowing the payoff function of the rest of the players. Also, it allows obtaining Pareto-efficient payoffs for all players using either Nash or correlated equilibrium concepts. We explain the main ideas behind the algorithm, explain the two key procedures on which algorithm relies on, provide a theoretical bound on the error introduced and show empirically the performance of the algorithm on four well-known repeated games.