AAAI Publications, Workshops at the Twenty-Eighth AAAI Conference on Artificial Intelligence

Font Size: 
Solving Distributed Constraint Optimization Problems Using Ranks
Mihaela Verman, Philip Stutz, Abraham Bernstein

Last modified: 2014-06-18

Abstract


We present a variation of the classical Distributed Stochastic Algorithm (DSA), a local iterative best-response algorithm for Distributed Constraint Optimization Problems (DCOPs). We introduce weights for the agents, which influence their behaviour. We model DCOPs as graph processing problems, where the variables are represented as vertices and the constraints as edges.This enables us to create the Ranked DSA (RDSA), where the choice of the new state is influenced by the vertex rank as computed by a modified Page Rank algorithm. We experimentally show that this leads to a better speed of convergence to Nash Equilibria. Furthermore, we explore the trade-off space between average utility and convergence to Nash Equilibria, by using algorithms that switch between the DSA and RDSA strategies and by using heterogeneous graphs, with vertices using strategies in different proportions.

Keywords


SCS: Constraint Optimization; SCS: Distributed CSP/Optimization

Full Text: PDF