Distributed Algorithms for DCOP: A Graphical-Game-Based Appr

DCOPs
Distributed Constraint Optimization Problems
这篇paper主要讲把DCOP分解为graphical game来解决的一些算法

之前的一些方法：
DBA: Distributed Breakout Algorithm
DSA: Distributed Stochastic Algorithm
这里提到一个概念：
如果我们把一个问题分解后，交给多Agents来解决，那么如果不存在Agents之间的协调(coordination)，那么就称之为1-coordinated algorithms
这个概念可以被引申到k个agents上，如果解决过程中，允许k个agents共同coordination，那么这种方法就叫做k-coordinated algorithms

在这基础上我们来看如何将DCOP分解为graphical game
将DCOP分解的motivation主要是传统方法比如heuristic algorithms在large scale domains上的复杂度过高，而且对于一些tree-based方法来说，如果问题是动态dynamic的，每次问题稍微变化，整个algorithm又要重新跑一遍
下面还先是一些比较简单的定义：
如果E_{ij}=1则 v_j 是 v_i 的 neighbor, (显然的。。。)且我们用N_i表示i的所有neighbors的编号
这里设这些neighbors们的
N_i = {j_1, j_2, ..., j_{K_i}}, (即共有K_i个邻居)
那么，其中某个邻居j_k的行动，即v_{j_k}的值，就可以用x_{j_k}表示
那么i的所有邻居的actions的集合，就是{x_{j_1}, x_{j_2}, ..., x_{j_{K_i}}}
这里为了方便写作x_{-i}
我们把x_{-i}称之为i的context
那么，对于agent i，我们可以定义一个局部收益 local utility:
u_i(x_i;x_{-i}) = \sum_{j \in N_i} U_{ij}(x_i, x_j)
最后，整个DCOP就可以用一个三元组(X, E, u) 来表示了

说一点纳什均衡Nash Equilibruim的事儿
如果通过优化(X, E, u)求的一组最优解x*，那么这组解必然是纳什均衡的
证明过程原文又讲
但这里并没有说这组解就是全局最优的，想想说不定有囚徒困境之类。。。

DSA
每回合开始时，每个agent都生成一个[0,1]随机数，如果这个随机数大于某个阈值p，那么这个agent就可以行动
(就这么简单。。。)

下面说MGM-2
对于两个agent i 和 j ，按照5楼定义的局部收益local utility
agent i 的局部收益为u_i(x_i;x_{-i})
agent j 的局部收益为u_j(x_j;x_{-j})
吐槽：我觉得这样写看起来真是太麻烦了。。。
总之，就是i的local utility，简写做u_i吧，和j的local utility，u_j，我们希望找到一组新的x_i 和 x_j，使u_i+u_j最大化
其实就是能不能找到一组新的action，让i和j的action都改变，使得它们的local utility总和都增加，而不仅仅是某个agent单方面改进
这样增大了搜索空间，也提高了解的质量
比如10楼那个例子

在10楼我们说用MGM找到了一组解，即所有agent都执行1
如果我们换成MGM-2来解，
那么agent就可以多一步协商的过程
这里有个小问题，那就是谁来提出这个协商，如果双方同时提出，会有一些因同步产生的问题，该paper里面用了简单的随机方法，即每次随机出一部分agents作为offer发起者，其他agents作为offer接收者，同时为了避免冲突，发起者不能接受(accept)收到的offer，
关于同步问题这里就先不多说了
那么回到原来问题上，初始agent {1,2,3} 的action分别为 {0,1,1} 假如此时只有agent1被选中成为offer发起者，那么agent 1显然会去找它的好邻居agent 2，然后它发现，如果我和agent 2都选择执行action 0 我们的收益还会增加
这时候这么算：
如果只是agent 1 单独行动，如10楼MGM计算，可以得到的gain为5
如果agent 1 和 2 协商一下呢？那么可以获得的gain为:
agent 1 的local utility - agent 2 当前action(1) 的utility + agent 2 改变action(改为0)之后的utility - agent 1跟agent 2 共同的这部分utility(不然这部分会被算两次)
这里 因为agent 1 的neighbor 只有agent 2，所以agent 1 的local utility 和agent 1 和 2 在修改action后共同的utility都是10
所以上式
= 10 - 11 + 10 - 10
= -1
因为是负数，所以agent 1 发现还是不如他自己行动。。。
为什么会出现这种情况呢，因为如果agent 1和2都执行action 0 ，尽管agent 1 的收益增加了(5->10)但agent2的收益却减少了，最重要的是，全局收益也减少了(11-> 10)
然而，如果agent 2 作为offer 发起者，情况则大不一样了，这里大家可以自己试一下：
(注意：按照paper里面的方法，发起者是随机选择一名offer接收者，所以可能会出现什么有趣的情况呢？)