10

对于一个拥有 1000 万玩家的在线扑克网站，描述合谋检测算法复杂性的最佳方式是什么？

假设（我认为这些假设没有太大区别，因此请随意忽略它们，但只是为了澄清）：

  • 该网站拥有10,000,000个注册用户。
  • 即这些玩家一共玩了50亿手牌。
  • 您获得的唯一信息是该网站的“主手牌历史数据库”，其中包含所有玩家底牌和每手牌的下注动作。
  • 换句话说，您可能不会走捷径，例如检查 IP 地址、寻找不寻常的抽水/盈利模式等等。
  • 假设您有一个函数，当传递一组恰好 N（其中 N 在 2 到 10 之间）玩家时，如果该组中的所有玩家都串通在一起，则返回 TRUE。如果部分但不是所有玩家是共谋者，则该函数返回 FALSE。TRUE 的返回值是（例如）75% 的置信度。

Your job is to produce an exhaustive list of every player who's colluded, along with a complete list of the players he's colluded with. I have recently heard this problem described as NP-hard but is this accurate? Sometimes we call things "NP" or "NP-hard" that are merely "hard".

Thanks!

4

4 回答 4

4

我立即看到的蛮力方法是：

Set colluders = new Set();
for(Player p1 : allPlayers)
{
  for(Player p2 : allPlayers)
  {
    if(!p1.equals(p2) && haveColluded(p1, p2))
    {
      colluders.add(p1);
      colluders.add(p2);
    }
  }
}

我认为使用大于 2 的参数计数调用 haveColluded 没有意义，因为这可能会产生误报。我想虽然这取决于该功能的成本。但是上面的结果是 O(n^2) 调用 haveColluded （n 是玩家的数量）。该函数本身似乎是 O(m)，其中 m 是他们一起玩的游戏数。因此，该算法似乎很好地低于 O(n^3)。要成为 NP-hard，你必须证明“一个问题 H 是 NP-hard 当且仅当存在一个 NP 完全问题 L 是多项式时间图灵可约化为 H [...] 换句话说，L 可以由具有 H 的预言机的预言机在多项式时间内求解。” ( http://en.wikipedia.org/wiki/NP-hard）。我研究过 NP 完全问题（例如 3-SAT、旅行推销员问题等），但我不知道您将如何证明这一点。但话又说回来，它似乎确实与集团问题相似。

于 2009-04-26T11:49:32.150 回答
3

看起来像clique detection，这是 NP 难的。另一方面，集团的规模在这里受到限制（10），所以蛮力在最坏的情况下是 n^10。

编辑：这里的关键问题是合谋函数的属性是什么。是否可以通过在两个较小的集合（比如 5 个）玩家上调用该函数来始终检测到 10 个玩家串通在一起？

于 2009-04-27T07:23:54.557 回答
1

在您的模型下，您描述的内容应该相当容易。给你一个隐式图（顶点是玩家，边对应于一起玩过游戏）。您想要该图的子图。

如果合谋函数完全可靠，您只需在图中的每一对顶点上调用它，就可以得到子图。

该子图可能相当不连贯。我希望结果图是断开的或连接非常弱的；通过做一些最小切割，大型连接良好的子图将很快消失。

请注意，我们可以限制自己只查看对，因为合谋函数应该服从（就置信水平而言）Collude(A,B,C)<Collude(A,B)。

构建这个全球共谋功能似乎很难。

于 2009-05-02T02:25:30.613 回答
1

我会将其分为两个步骤：

  1. 迭代超过 50 亿手牌，检查每手牌的玩法。在每只手上使用一些算法，我们称之为算法 A 。随着您的进行，您将构建一个共谋图，其中顶点代表玩家，无向加权边代表两个玩家之间共谋的一些置信度。当算法 A因怀疑玩家 X 与玩家 Y 勾结而触发时，会在勾结图中的加权边 XY 上添加一些值。随着您在已经玩过的手牌中前进，边缘权重会随着时间的推移而累积。当达到某个阈值时，边缘表示 X 和 Y 之间的勾结。

  2. 然后，确定 N 个玩家顶点列表是否全部勾结在一起的函数是验证包含 N 个顶点的子图是全连接的（意味着每个节点的边权重大于子图中每个其他节点的勾结阈值）。IIRC，确定这是 O(n*lg(n) )。

于 2010-01-07T01:23:33.263 回答