A unifying framework for iterative approximate best-response algorithms for distributed constraint optimization problems1

Cf. partial monitoring, as in multi-armed Bandit problems. See Blum and Mansour (2007) for a discussion of the issues surrounding these two monitoring models.

Note that, when applied to DCOPs, many approaches to distributed optimization usually can be placed into one of the three categories defined above. For example, many negotiation models and local exchange markets are, in effect, local approximate best-response algorithms. Consider a negotiation model in which at each time step one agent in each neighbourhood announces a new configuration of the variables under its control to its neighbours, with the constraint that each new configuration weakly improves the agent's payoff (as is commonly employed). This type of negotiation model is captured by our framework, as messages are local (only neighbours receive the agent's update to its state) and the process is iterative. We also point out that other approaches to the general problem of distributed optimization that can be applied to DCOPs, such as token-passing (e.g. Xu et al., 2005) or auction protocols (e.g. Gerkey & Mataric, 2002), do not fall into any of these three categories. However, we consider an exhaustive classification and analysis of these distributed optimization techniques outside the scope of this paper, because we are primarily concerned with local approximate best-response algorithms in the specific case of DCOPs.

The complete algorithms are typically used in applications where their optimality is the key concern and timeliness is not a limiting factor, such as industrial scheduling and timetabling problems (Petcu & Faltings, 2005) or routing protocols for fixed environmental sensor networks (Kho et al., 2009).

One notable exception to this trend is Marden et al. (2009a), who illustrate the connections between potential games and consensus problems. In a consensus problem, a set of agents must reach consensus upon a given value (such as a meeting point). These problems may be modelled as a DCOP containing binary and unary constraints. Each binary constraint between two agents is satisfied when their variables are set to the same value, and violations are penalized in proportion to their distance between their variables’ values. However, an agent's strategy set may be limited by its unary constraints such that it is not possible for it to simultaneously satisfy all its binary constraints.

Generally, any optimization problem that forms a commutative semi-ring can be expressed as a bipartite factor graph—see Aji and McEliece (2000) for details.

Indeed, this result holds for any problem that can be represented as a factor graph and in which the variable domains are finite.

Tumer and Wolpert (2004) provide another method for showing that DCOP games are potential games. Generally, any global utility function whose variables are controlled by independent agents can be instantiated as a potential game by setting each agent's utility function equal to its marginal effect on the global utility (as in the alignment criterion above). Then, by definition, any change in an agent's utility is matched by an equivalent change in the global utility. In a DCOP, one way to achieve this is to set each agent's utility to the sum of the payoffs for constraints that it is involved in, as in Equation (2).

Although Nash equilibria correspond to 1-optima, note that strong equilibria (Aumann, 1959) do not correspond to n-optima. A strong equilibrium is robust to deviations from all coalitions of n players and less, where a coalition deviates if at least one member's individual payoff improves and none decrease. In a DCOP game, an n-optimum always exists, while a strong equilibrium may not. However, if a strong equilibrium does exist, it is n-optimal.

Maheswaran et al. (2005) show that MGM is anytime and converges to an element in the set of Nash equilibrium in DCOP games directly, without using a potential game characterization of the problem.