Title: Distributed Computation of Pareto Solutions in n-Player Games

Authors: Markku Verkama, Harri Ehtamo and Raimo P. Hämäläinen

Status: Mathematical Programming, 74, 1996, pp. 29-45

Keywords: Distributed algorithm, Game theory, Pareto optimality, Optimization

The problem of computing Pareto optimal solutions with distributed algorithms is considered in n-player games. We shall first formulate a new geometric problem for finding Pareto solutions. It involves solving joint tangents for the players' objective functions. This problem can then be solved with distributed iterative methods, and two such methods are presented. The principal results are related to the analysis of the geometric problem. We give conditions under which its solutions are Pareto optimal, characterize the solutions, and prove an existence theorem. There are two important reasons for the interest in distributed algorithms. First, they can carry computational advantages over centralized schemes. Second, they can be used in situations where the players do not know each others' objective functions.