Distributed Search for Pure Nash Equilibria in Graphical Games

Graphical games introduce a compact representation, where agents' outcomes depend only on their neighbors. A distributed search algorithm for pure Nash equilibria of graphical games is presented. The algorithm uses the analogy of graphical games with asymmetric distributed constraints optimization problems (ADCOPs). The proposed algorithm includes three components - an admissible pruning heuristic; a back-checking mechanism; and a pseudo tree representation of the game. An experimental evaluation of the components of the proposed search algorithm is presented for randomly generated networks of multiple agents. The major speedup over a naive search algorithm is shown to arise from the use of a pseudo tree representation. A simple assessment method of the privacy loss due to back-checking is presented and is shown to result in a tradeoff between the performance of the complete algorithm and its privacy loss.