A Distributed Algorithm for Optimising over Pure Strategy Nash Equilibria

Authors

  • Archie Chapman University of Southampton
  • Alessandro Farinelli University of Verona
  • Enrique Munoz de Cote University of Southampton
  • Alex Rogers University of Southampton
  • Nicholas Jennings University of Southampton

DOI:

https://doi.org/10.1609/aaai.v24i1.7610

Keywords:

Game theory, distributed optimisation

Abstract

We develop an efficient algorithm for computing pure strategy Nash equilibria that satisfy various criteria (such as the utilitarian or Nash-Bernoulli social welfare functions) in games with sparse interaction structure. Our algorithm, called Valued Nash Propagation (VNP), integrates the optimisation problem of maximising a criterion with the constraint satisfaction problem of finding a game's equilibria to construct a criterion that defines a c-semiring. Given a suitably compact game structure, this criterion can be efficiently optimised using message-passing. To this end, we first show that VNP is complete in games whose interaction structure forms a hypertree. Then, we go on to provide theoretic and empirical results justifying its use on games with arbitrary structure; in particular, we show that it computes the optimum >82% of the time and otherwise selects an equilibrium that is always within 2% of the optimum on average.

Downloads

Published

2010-07-04

How to Cite

Chapman, A., Farinelli, A., Munoz de Cote, E., Rogers, A., & Jennings, N. (2010). A Distributed Algorithm for Optimising over Pure Strategy Nash Equilibria. Proceedings of the AAAI Conference on Artificial Intelligence, 24(1), 749-755. https://doi.org/10.1609/aaai.v24i1.7610

Issue

Section

AAAI Technical Track: Multiagent Systems