1

我有一个大约 1000 种不同资产的列表,我想按我正在制作的游戏的价值对它们进行排名。

玩家有机会选择两个资产篮子之一。例如,他们可能会被问到他们更喜欢 A +​​ B 还是 C。

从大量的篮子偏好列表中,我希望按感知价值对资产进行排名。

这是一些示例输入,相应地玩家说:

A > B
A + A > B + C
C > B

即他们宁愿有一个A而不是一个B。他们宁愿有2个A而不是一个B和一个C。等等。

从这个输入中,我认为最有可能的价值排名是:

A > C > B

我应该使用哪种算法来解决这个问题?

有时偏好列表会相互矛盾(一些玩家认为 A > B,其他玩家可能会说 B > A)。如果我有一个单独的玩家技能水平衡量标准,我如何利用它来获得更准确的排名?

我还需要能够处理篮子之间的关系中存在“孤岛”的情况。例如:

A > B
C > D

即你不能说如果 A <> C。

在我看来,这似乎是一个类似于各种打包算法的优化问题。这个排名问题是 NP 难的吗?

4

2 回答 2

1

对我来说,它实际上听起来更像是图论。

假设您有一个带有A -> B的有向图,表示A < B。那么你可以


所以问题是如何构建这样的图表。我有一种预感(不幸的是还不止于此),唯一重要的多变量规则是以下形式:

A_1 + A1 + ... + A_i < A_{i + 1}

他们应该简化为

A_j < A_{i + 1}, j = 1, .., i

(除此之外,RHS 多值规则的唯一用途是传递扣除(根据我的直觉),即

A < B + CB + C < D意味着A < D。但这可以使用虚拟变量来处理总和。)


也许您应该看看您是否可以验证或反驳这一点。

于 2015-05-19T22:18:34.203 回答
1

在阿罗定理的合理假设下,您尝试做的事情通常是不可能的。

更好的方法是要求玩家得分而不是排名;例如,问他们:“你愿意为 A 支付多少兹罗提?为 B 支付?为 C 支付?”,然后由回答的玩家平均每个项目的得分。因此,如果只有玩家 2、5 和 11 回答了他们对项目 A 的估计值,您将把他们的答案相加并除以 3。您还可以给更有经验的玩家的答案更多的权重。

如果您仍然想使用一篮子资产,您可以使用线性代数根据 A+B 和 AB 的分数来解开 A 和 B 的分数,比如说。

如果您想使用排名数据(例如,如果您只有这些并且不能再问任何问题),那么 Ami 的方法可能是您能做的最好的。

于 2015-05-19T23:25:52.270 回答