Not logged in.

Contribution Details

Type Conference or Workshop Paper
Scope Discipline-based scholarship
Published in Proceedings Yes
Title Solving Distributed Constraint Optimization Problems Using Ranks
Organization Unit
  • Coralia-Mihaela Verman
  • Philip Stutz
  • Abraham Bernstein
Presentation Type paper
Item Subtype Original Work
Refereed Yes
Status Published in final form
  • English
ISBN 978-1-57735-674-5
Page Range 125 - 130
Event Title Statistical Relational AI. Papers Presented at the Twenty-Eighth AAAI Conference on Artificial Intelligence.
Event Type workshop
Event Location Quebec City, Canada
Event Start Date July 27 - 2014
Event End Date July 27 - 2014
Place of Publication Palo Alto, California
Publisher AAAI Press
Abstract Text 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.
Export BibTeX