Distributed Multiplicative Weights Methods for DCOP

In this game, each player deal with enormous sizes such as a smart grid is rapidly increasing associated with a variable keeps providing probability distributions in AI communities. The distributed constraint optimization over its domain, and tries to minimize the regret, problem (DCOP for short) is arguably the most which is the average additional cost incurred by the probability studied problem in this setting, where the goal is to find an distributions against the strategy of outputting a best assignment that minimizes the total sum of costs incurred single value all the time. We can make the regret of each by (local) cost functions. Since it takes a prohibitively long agent arbitrarily small by utilizing the multiplicative weights time to exactly solve DCOP, we need to resort to incomplete method. Finally, we round the obtained probability distributions algorithms, and a plethora of incomplete algorithms to integer values. We prove that our method converges have been proposed in the literature, such as local search to a certain kind of equilibrium, called a coarse correlated based algorithms (Maheswaran, Pearce, and Tambe 2004; equilibrium. Zhang et al. 2005), inference based algorithms (Farinelli We empirically compare our methods with previous stateof-the-art et al. 2008), graph based algorithms (Bowring et al. 2008; methods. We demonstrate that our methods are Kiekintveld et al. 2010), divide-and-coordinate based algorithms scalable, and that DMW-Game outperforms other methods (Vinyals, Rodriguez-Aguilar, and Cerquides 2010; in terms of solution quality and efficiency. Hatano and Hirayama 2013), and sampling based algorithms (Ottens, Dimitrakakis, and Faltings 2012; Nguyen, Yeoh, and Lau 2013).