冲突最小的多agent策略分配

Question

我有n个代理，每个代理都有k个策略。假设探员是{X1，X2，.，对于一个代理Xm，我们有策略{Xm_1，Xm_2，.Xm_k}有些策略可能与另一种策略有冲突。我有一个已知的函数f(Xn_i，Xm_j)，其中输入是来自不同代理的两个策略，输出是一个布尔值，真意味着它们有冲突。现在我的问题是设计一个算法来为每个代理找到最佳的策略分配，这样冲突的数量就会最小。我的朋友告诉我用遗传算法来解决这个问题。我想知道，如果可能的话，是否有任何有效的“精确”算法来寻找零冲突分配？请给我一些提示或关键词与此有关的问题，谢谢！

说明:这里的“分配”意味着每个代理从其可能的策略集中选择一个策略。例如，如果n个== 3和K个==2，这意味着我们有3个代理，每个代理需要从其两个可能的策略中选择一个，所以解决空间是2^3赋值，并且需要找到冲突最小的策略分配。

Answer 1

在每个agent都有两种策略的特殊情况下，该问题的最小化版本等价于NP-难的最大2-可满足性。然而，决定是否有无冲突的分配是多项式时间。

为了决定是否有一个无冲突的分配，其中代理有三个或更多的策略，这个问题推广了3-着色图的NP-硬问题。