什么是"让每个人都开心"的投票算法？
我正在寻找一种投票算法,根据大多数选票和投票数来选出获胜者.
真人生活的例子:
我们公司有一个谷物棒.我们有3种不同谷物的空间.我们希望允许我们的员工对他们想要的谷物进行投票.
我们不希望根据受欢迎程度严格挑选前3名获奖者,因为可能会有少数员工只能吃1种特定谷物(无论出于何种原因),我们希望尽可能给予他们特殊津贴.
鉴于以下投票结果,以下是我们希望算法给出的结果.
我正在寻找一种能够进行这种排名的算法.如果你至少可以提供我正在寻找的名称那将是一个很大的帮助,因为我可以更好地搜索它.:)
谢谢!
没有一个完美的投票系统 - 请参阅http://en.wikipedia.org/wiki/Arrow%27s_impossibility_theorem.已经有各种尝试通过弯曲规则来解决这个问题,包括http://en.wikipedia.org/wiki/Range_voting.
接近范围投票的一个想法是给每个人12票并允许他们按照自己的意愿分配.看看你的例子,如果你假设有多个选择的人平均分配他们的12票 - 12x1或6x2或4x3或3x4 - 那么我认为你得到了你想要的结果,幸运符有总共10票和其他一切得到更多.
这个范例的想法是创建一个二分图，其中节点是人和谷物，如果投票赞成，则在人和p谷物之间有一条边。目标是选择 3 种谷物，使得去除所有其他谷物后得到的图表为cpc
连接（每个人都会吃至少一种选定的谷物），并且
最大化每个人的最小/平均程度（最大化最小/平均幸福度）
您可以将其视为最大覆盖问题。在这种情况下，您有一组集合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 问题，但是有已知的算法可以解决它们（查看维基百科文章以获取参考）。