基于概率成对比较的模糊排序算法

Question

假设有n个玩家玩两两博弈。每场比赛的结果主要取决于两个球员的实力以及一点运气。

如何在较少游戏的情况下获得更准确的每个玩家的排名？

Answer 1

在理想的情况下，实力较强的玩家总是获胜，你可以使用像mergesort或quicksort这样的比较排序来对玩家列表进行排序，甚至可以使用排序网络来要求尽可能少的比较。由于这不是理想的情况(涉及运气)，这些算法可能会由于违反传递性而不能产生正确的结果，但是我相信有一种方法可以检测和纠正许多运气击败强度的实例，如下所述：

首先，使用类似mergesort的东西对玩家进行排序(违反可传递属性不会导致无限循环)。将执行的比较转换为有向图，其中每条边都指向比赛的获胜者。现在，对于G中的每一对连接的边，通过比较“结束”顶点来添加第三条边(创建一个三角形)，并将更新后的图放在G‘中(保留G不修改)。完成此操作后，检查G‘中是否存在循环-如果存在循环，则它们表示违反了传递属性。要解决这些问题，请将循环的成员与图的其他成员进行比较，这不可避免地会产生更多的循环。这些循环之间的相互优势很可能是违规者，我们可以假设这是一次“幸运”的胜利。将所有这些边标记为否定。

一旦解决了所有循环，您可能会发现由于一些模糊性，您无法按拓扑对图进行排序。根据需要执行比较，以解决歧义，但请注意，这些新的比较无法保证其正确性(目前还没有)。要解决此问题，请递归地对图G1中的这些新边重复上述过程，直到生成明确的图。将这些边插入到G中，并按拓扑排序。

如果你愿意，你可以修改上面的算法来提高速度或准确性。为了准确，只需将每条边与更多冗余边进行比较，以更可靠地暴露和澄清循环。为了获得更快的速度，测试更大的周期组-而不是试图找到长度为3的周期，而不是尝试寻找长度为3的周期，而是比较每6个边的“结束”，以找到长度为7左右的周期。如果循环/“幸运赢”足够罕见，那么通过一次检查多个边可以节省相当多的时间，尽管a)如果两个违规相互“抵消”，你可能会忽略一个循环，以及b)你仍然会花费大量时间在一个更大的循环中定位特定的违规边。