Distributed Multiplicative Weights Methods for DCOP

Authors

  • Daisuke Hatano National Institute of Informatics
  • Yuichi Yoshida National Institute of Informatics, and Preferred Infrastructure, Inc.

DOI:

https://doi.org/10.1609/aaai.v29i1.9425

Abstract

We introduce a new framework for solving distributed constraint optimization problems that extend the domain of each variable into a simplex.We propose two methods for searching the extended domain for good assignments.The first one relaxes the problem using linear programming, finds the optimum LP solution, and rounds it to an assignment.The second one plays a cost-minimization game, finds a certain kind of equilibrium, and rounds it to an assignment.Both methods are realized by performing the multiplicative weights method in a distributed manner.We experimentally demonstrate that our methods have good scalability,and in particular, the second method outperforms existing algorithms in terms of solution quality and efficiency.

Downloads

Published

2015-02-18

How to Cite

Hatano, D., & Yoshida, Y. (2015). Distributed Multiplicative Weights Methods for DCOP. Proceedings of the AAAI Conference on Artificial Intelligence, 29(1). https://doi.org/10.1609/aaai.v29i1.9425

Issue

Section

AAAI Technical Track: Multiagent Systems