上行复选制,跟方案4类似,只不过第一轮淘汰的不是支持最少,而是反对最多的候选人(获得最多末选票的候选人)

    再看上面提到的情况,中间派候选人由于不是任何人的末选,所以第一轮淘汰的是左派或者右派,再第二轮选举中,中间派的候选人就可以获胜了.

    方案5也有方案5的问题,考虑这样一种情况,只有两个候选人AB参选,选民9人,其中6人喜欢A而讨厌B,3人喜欢B而讨厌A,无论按照之前的哪种方式,都会是A获胜.但是现在又多了两个候选人C和D,喜欢B的3人中,都是把A列在最后一个候选的,而喜欢A的6人的末选,却是BCD各2票,这样,在第一轮选举中,A就由于获得了最多的末选票被淘汰了,而通过精心的构造例子,完全可以使B最终当选.仅仅由于CD参选或者不参选,A和B之间的胜负关系就发生了大逆转.

    实际使用此方案的例子不多,只有在公元前507年的雅典有类似的方案,不是让民众投支持票,而是投反对票,把反对最多的人投出局.

    方案6:多赛制,民众对候选人排序,然后候选人之间两两pk,统计每一张选票上看候选人A在候选人B前面还是B在A前面,如此找到获胜场次最多的候选人来赢得选举.

    这样的问题是可能导致循环胜负,如ABC三个候选人,有3个民众,投票分别是ABC,BCA,CAB,可以看出AB之间A获胜两次,A>B;BC之间B获胜两次,B>C,AC之间C获胜两次,C>A,这样就构成了一个A>B>C的循环.这个是不是有点像足球联赛的记分制啊,如果积分相同,足球比赛中可以再看净胜球、进球、胜负关系等,但是作者并没有在这个方面进行展开,而是介绍了另一种方式:博达制.

    方案7:博达制,民众对候选人排序,假如有n个候选人,第一位的候选人得n分,第二位得n-1分,以此类推,然后统计每个候选人的总分,获得最多分的获胜.

    有人对博达制的批评是:可能有选民会利用这种方式进行作弊(投"策略票"),最支持B的候选人本来心目中的排序是B>A>C,但是由于相对A,他们还是更喜欢B,因此,为了把B拉上来,就得把A拉下去,他们的投票就变成了B>C>A.博达对此批评的回应是:我的制度只适用于诚实的投票者.

    而这本书的作者却认为博达制的"策略票"问题没那么严重,如果无法准确预测民意和精确控制策略票的投法,有可能因为用力过猛,不但把A拉下来了,反而让C获得的支持票增加,这样就使得最支持B的那些人的"策略票"反而使得他们最讨厌的C当选了,当年在IMDB上就发生过类似一幕:

    电影《蝙蝠侠6》上映后,蝙蝠侠的粉丝们觉得这部片太酷了,于是就想把蝙蝠侠6投成IMDB第一位,于是他们疯狂的给蝙蝠侠6打高分,而同时,也纷纷的给当时的IMDB第一《教父》投低分,导致的结果就是用力过猛,教父变成了第三名,原来的第二肖申克的救赎(TSR)变成了第二(原来的第二是排在教父后面,新的第二是排在蝙蝠侠6后面),而后来,随着疯狂粉丝的热情消退,理性的意见占据了上风,蝙蝠侠6的得分逐渐下降,跌到了第10.而教父还是在肖申克的救赎后面,很久没有回去了.

    博达制是否有其他问题呢?

    以上只是对这本书第14章的一个笔记,也仅仅针对"多候选人单职位"问题进行了讨论,书的后面还会对"多候选人多职位"的情况继续探讨,也就是根据每个人对候选人的排序,来决定最终的候选人排序.

    回到搜索引擎领域来,如上策略的变迁会给我们一些启示,先看看之前抽象出来的问题:

    有n个候选人,每个选民对这n个候选人投票,最终在n个候选人中选出最合适、最符合民意、也符合逻辑的那个人.

    这很像搜索引擎在解决的问题:

    系统里有n个网页,有m个特征(页面质量、页面内容丰富度、页面超链、文本相关性等)对n个网页有不同的打分,如何根据这些特征的"投票",选出最适合放在第一位的网页呢?

    从选举的例子中,我们可以得到的几个启示:

    1. 设计算法时,要避免出现"赢者通吃"带来的信息丢失问题.

    2. 不要因为某几个特征特别好,就把某个网页排到最前,或者因为某几个特征特别差,就把某个网页抛弃.

    3. 最合适放在首位的网页不一定是在每个特征上都最好,而应该是能够兼顾所有特征,综合表现最好的那个.

    4. 搜索引擎使用者对搜索结果的点击行为,可以看成是对搜索结果进行的"投票",这样的"投票"信息的使用方式,也要注意考虑是否会带来选举过程中出现的种种不合理.

    以上提到的种种选举方案,仅仅是对"多候选人单职位的"的情况进行讨论,而搜索引擎面对的问题,则更类似于"多候选人排序"的情况,也即:

    系统里有n个网页,有m个特征(页面质量、页面内容丰富度、页面超链、文本相关性等)对n个网页有不同的打分,如何根据这些特征的"投票",决定n个网页的顺序?

    而这个"多候选人排序"问题,是有一个"不可能的民主"的理论的,该理论的大意是,"合理"的民主应该满足3个条件:

    1. 如果选民都认为A比B好,那么最终结果应该也是A比B好

    2. 没有"独裁者",也即,不存在这样一个人,无论别人怎么排序,最终结果的排序都和这个人的排序一致

    3. 无关因素独立性,也即,在第一次投票完成后,A排在B前面,现在进行第二次投票,如果所有人都没有改变自己投票中A和B的相对顺序,那最终结果应该也是A在B前面

    而通过数学的证明,可以得出结论:如果某种选举方式满足条件1和3,则必然不满足2,也即必然存在"独裁者",这个问题的证明,可以参考这篇博客:

    根据"不可能的民主"理论,和搜索引擎结合起来看,似乎搜索引擎很难给出一个合理的网页排序,但是搜索引擎和投票又似乎有所不同,有两个角度可以破解

    1. 认为条件3过于强,需要弱化.

    2. 也许在网页排序问题上,真的存在这样一个"独裁特征",这个"独裁特征"从目前看来,最适合的应该就是"用户满意度"了,按照用户的满意程度来排序网页,就是最合理的网页排序.如何衡量"用户满意度"呢?这就是我们一直在努力的.