什么是“让大家开心”的投票算法？

我正在寻找一种基于大多数选票和票数组合的优胜者的投票算法。什么是“让大家开心”的投票算法？

活生生的例子：

公司拥有谷物棒。我们有3个不同的谷物的空间。我们想让我们的员工投票选择他们想要的谷物。

我们不想挑严格根据受欢迎程度的前3名，因为有可能是员工的少数谁只能吃（无论何种原因）1种特别是谷物，我们想给他们尽可能的特殊津贴。

鉴于以下投票结果，下面是我们希望算法给我们的结果。

Vote scenario and desired outcome

我正在寻找一种算法，做这种排名。如果你至少可以提供我正在寻找的名字，这将是一个很大的帮助，因为我可以更好地搜索它。 :)

谢谢！

来源

2011-12-14 joshuapoehls

要记住的一件事是，所描述的问题为选择较少选择的人提供了更多的权力。如果我对他们中的任何人都感到满意，但是特别喜欢他们，我可以声称这是我喜欢的唯一一个，并且实际上'迫使'你选择它，因为我没有提供任何替代品。 – 2011-12-14 22:58:10

@NickJohnson也许就是这样，因为在那种情况下，你说如果你不能拥有X，那么你对其他人没有偏好。如果问题不能解决，我们不保证您会选择一个约束。 – PengOne 2011-12-14 23:18:02

@PengOne没有保证，不，但是你的偏好比另一个更诚实的选民更有可能受到尊重。如果要求您按照偏好顺序对项目进行排名，则这一点更为明显。如果我诚实并且从1到3排列我最喜欢的3，我不太可能得到我想要的结果，而不是我仅排名我最喜欢的结果，并且没有给别人带来任何价值。 – 2011-12-14 23:32:03

你可能想要考虑Hall's marriage theorem和/或assignment problem的概括。

的理念，为这个范式是建立一个二分图，其中节点是人民和谷物，以人p和谷类c之间的边缘，如果p投票c。我们的目标是选择3种谷物，使得从删除所有其它谷类得到的曲线图是

连接（大家会吃所选谷物中的至少一种），和
最大化的最小/平均每个人的程度（最大化最小/平均快乐）

你可以改为考虑这个为Maximum Coverage Problem。在这种情况下，您已经设置了C1,C2,...,Cm其中Ci是一组喜欢谷类i的人。对于你举例来说，以谷类和人民在表中列出的顺序，你有

C1 = {1,5} 
C2 = {2} 
C3 = {1,4,5} 
C4 = {3,5}

让n是人的数量，从而使Ci是{1,2,...,n}一个子集。目标是找到k集合，使联合的基数最大化。如果存在多种解决方案，请选择最小化交叉点基数的方法（最小化一个人主导的数量）或最大化最不频繁元素重复的次数（使最不快乐的人的幸福最大化）。

对于此示例，其中涵盖所有元素的最小的k是k=3并且它给出了唯一的解决方案C2,C3,C4。

然而，你看它，你有一个NP问题，但有已知的算法来解决它们（检查维基百科文章的参考）。

来源

2011-12-14 23:12:16 PengOne

没有一个完美的投票系统 - 见http://en.wikipedia.org/wiki/Arrow%27s_impossibility_theorem。已经有各种尝试通过弯曲规则来解决这个问题，包括http://en.wikipedia.org/wiki/Range_voting。

接近范围投票的一个想法是给每个人12张选票，并允许他们分发他们，如他们所愿。看看你的例子，如果你假设有多种选择的人平均分配他们的12张选票--12x1或6x2或4x3或3x4 - 那么我认为你可以得到你想要的结果，幸运符咒总共得到10张选票和其他一切比这更多。

来源

2011-12-14 20:39:45 mcdowella

我喜欢那个定理。我想，这个问题的标题立即引发你的想法。 – 2011-12-15 00:53:30

如果谷物的数量较少，您可以查看您的问题作为一个子集覆盖问题和蛮力用自己的方式寻找什么样的配置给最“当幸福来敲门”

var max_happyness = -INF 
for every subset {c1, c2, c3} of C: 
    max_hapyness = max(max_happyness, happyness(i1,i2,i3))

您仍然有问题定义一个合适的幸福功能。例如，你可以选择一个快乐功能，作为第一优先级来计算可以吃任何食物的人数。然后作为第二优先级的人喜欢两个谷类，那些喜欢三谷类的人等等。

优点：如果您可以定义一个幸福感函数，这可以给出最好的结果。

缺点：你必须能够定义一个幸福函数。

来源

2011-12-14 20:52:44 hugomg

什么是“让大家开心”的投票算法？

回答

相关问题