如何快速查找加权多数投票博弈中的所有最小获胜联盟？

我通过论文《A survey of algorithms for calculating power indices of weighted majority games》找到了对应解决方案。

问题描述 #

给定集合N={1,..,n}，其权重向量W={w_1,..,w_n}按降序排列且总和为1，需要找出N的所有子集C（也称为“联盟”），满足以下两个条件：

• C是“获胜”的：即子集C内元素的权重之和超过指定阈值（例如0.5）
• C是“最小”的：即从C中移除任意一个元素后，该子集将不再属于“获胜”集合

示例说明 #

举个示例方便理解：N={1,2,3}，W={0.45,0.35,0.2}

• 该场景下的“获胜”子集为{1,2}、{2,3}、{1,3}和{1,2,3}，因为它们的总权重都超过0.5
• 其中只有{1,2}、{2,3}、{1,3}是最小获胜联盟，因为{1,2,3}可以移除任意一个元素得到上述三个获胜子集。

已实现代码 #

参考上述论文，实现了如下递归生成所有最小获胜联盟列表的代码：

MWC = function(w,threshold=0.5){
  n = length(w)
  l = list()
  enumerate = function(S1,n1,b1){
    if(n1==n){
      return(list(c(S1,n1)))
    }else{
      if(sum(w[(n1+1):n]) >= b1){
        l = c(l,enumerate(S1,n1+1,b1))
      }
      if(w[n1] >= b1){
        l=c(l,list(c(S1,n1)))
      }else{
        l = c(l,enumerate(c(S1,n1),n1+1,b1-w[n1]))
        return(l)
      }
    }
  }
  return(enumerate(c(),1,threshold))
}

w = c(0.46,0.3,0.19,0.05)
MWC(w)

性能瓶颈 #

该代码在n≈20时可以正常运行，超过该值后指数级复杂度会导致运算无法正常完成。

内容的提问来源于stack exchange，提问作者pier