Distributed constraint optimization
Distributed constraint optimization (DCOP or DisCOP) is the distributed analogue to constraint optimization. A DCOP is a problem in which a group of agents must distributedly choose values for a set of variables such that the cost of a set of constraints over the variables is minimized. Distributed Constraint Satisfaction is a framework for describing a problem in terms of constraints that are known and enforced by distinct participants (agents). The constraints are described on some variables with predefined domains, and have to be assigned to the same values by the different agents. Problems defined with this  framework can be solved by any of the algorithms that are designed for it. The framework was used under different names in the 1980s. The first known usage with the current name is in 1990. Definitions. DCOP. The main ingredients of a DCOP problem are "agents" and "variables". Importantly, each variable is owned by an agent; this is what makes the problem distributed. Formally, a DCOP is a tuple formula_1, where: The objective of a DCOP is to have each agent assign values to its associated variables in order to either minimize or maximize formula_30 for a given assignment of  the variables. Assignments. A "value assignment" is a pair formula_31 where formula_32 is an element of the domain formula_33. A "partial assignment" is a set of value-assignments where each formula_10 appears at most once. It is also called a "context." This can be thought of as a function mapping variables in the DCOP to their current values:formula_35 Note that a context is essentially a partial solution and need not contain values for "every" variable in the problem; therefore, formula_36 implies that the agent formula_37 has not yet assigned a value to variable formula_38. Given this representation, the "domain  (that is, the set of input values) of the function codice_1 can be thought of as the set of all possible contexts for the DCOP. Therefore, in the remainder of this article we may use the notion of a context (i.e., the formula_39 function) as an input to the formula_11 function. A full assignment" is an assignment in which each formula_10 appears exactly once, that is, all variables are assigned. It is also called a "solution" to the DCOP. An "optimal solution" is a full assignment in which the objective function formula_30 is optimized (i.e., maximized or minimized, depending on  the type of problem). Example problems. Various problems from different domains can be presented as DCOPs. Distributed graph coloring. The graph coloring problem is as follows: given a graph formula_43 and a set of colors formula_14, assign each vertex, formula_45, a color, formula_46, such that the number of adjacent vertices with the same color is minimized. As a DCOP, there is one agent per vertex that is assigned to decide the associated color. Each agent has a single variable whose associated domain is of cardinality formula_47 (there is one domain value for each possible color). For each vertex formula_48, there  is a variable formula_49 with domain formula_50. For each pair of adjacent vertices formula_51, there is a constraint of cost 1 if both of the associated variables are assigned the same color: formula_52 The objective, then, is to minimize formula_30. Distributed multiple knapsack problem. The "distributed multiple-" variant of the knapsack problem is as follows: given a set of items of varying volume and a set of knapsacks of varying capacity, assign each item to a knapsack such that the amount of overflow is minimized. Let formula_54 be the set of items, formula_55 be the set of knapsacks, formula_56 be  a function mapping items to their volume, and formula_57 be a function mapping knapsacks to their capacities. To encode this problem as a DCOP, for each formula_58 create one variable formula_49 with associated domain formula_60. Then for all possible contexts formula_39:formula_62where formula_63 represents the total weight assigned by context formula_39 to knapsack formula_65:formula_66 Distributed item allocation problem. The item allocation problem is as follows. There are several items that have to be divided among several agents. Each agent has a different valuation for the items. The goal is to optimize some global goal, such as maximizing the sum  of utilities or minimizing the envy. The item allocation problem can be formulated as a DCOP as follows. Other applications. DCOP was applied to other problems, such as: Algorithms. DCOP algorithms can be classified in several ways: ADOPT, for example, uses best-first search, asynchronous synchronization, point-to-point communication between neighboring agents in the constraint graph and a constraint tree as main communication topology. Hybrids of these DCOP algorithms also exist. BnB-Adopt, for example, changes the search strategy of Adopt from best-first search to depth-first branch-and-bound search. Asymmetric DCOP. An asymmetric DCOP is a  extension of DCOP in which the cost of each constraint may be different for different agents. Some example applications are: One way to represent an ADCOP is to represent the constraints as functions: formula_67 Here, for each constraint there is not a single cost but a vector of costs - one for each agent involved in the constraint. The vector of costs is of length "k" if each variable belongs to a different agent; if two or more variables belong to the same agent, then the vector of costs is shorter - there is a single cost for each involved "agent", not  for each variable. Approaches to solving an ADCOP. A simple way for solving an ADCOP is to replace each constraint formula_68 with a constraint formula_69, which equals the sum of the functions formula_70. However, this solution requires the agents to reveal their cost functions. Often, this is not desired due to privacy considerations. Another approach is called Private Events as Variables (PEAV). In this approach, each variable owns, in addition to his own variables, also "mirror variables" of all the variables owned by his neighbors in the constraint network. There are additional constraints (with a cost of infinity) that guarantee  that the mirror variables equal the original variables. The disadvantage of this method is that the number of variables and constraints is much larger than the original, which leads to a higher run-time. A third approach is to adapt existing algorithms, developed for DCOPs, to the ADCOP framework. This has been done for both complete-search algorithms and local-search algorithms. Comparison with strategic games. The structure of an ADCOP problem is similar to the game-theoretic concept of a simultaneous game. In both cases, there are agents who control variables (in game theory, the variables are the agents ' possible actions or strategies). In both cases, each choice of variables by the different agents result in a different payoff to each agent. However, there is a fundamental difference: Partial cooperation. There are some intermediate models in which the agents are "partially-cooperative": they are willing to decrease their utility to help the global goal, but only if their own cost is not too high. An example of partially-cooperative agents are employees in a firm. On one hand, each employee wants to maximize their own utility; on the other hand, they also want to contribute to the success of  the firm. Therefore, they are willing to help others or do some other time-consuming tasks that help the firm, as long as it is not too burdensome on them. Some models for partially-cooperative agents are: Solving such partial-coopreation ADCOPs requires adaptations of ADCOP algorithms.