搜索引擎的投票选举的模式与网页排序的问题
程序员文章站
2022-06-20 13:54:13
本文从选举的模式来谈网页排序的问题... 12-06-12...
前些天读了一本《选举的困境》，其中有一章，从美国的选举制度说起，介绍美国选举制度的不足，然后针对其不足，提出种种改善，然而每种改善都有其各自的问题，其中的变化很有趣。
先说美国选举制度，美国的总统选举是一种“赢者通吃”的方式，每个州根据其人口多少，有几十或几百的“州票”，州里的人对总统候选人进行选举，在某个州获得票最多的那个候选人，获得这个州所有的“州票”，然后统计所有候选人的“州票”多少，获得最多“州票”的候选人获胜。
这样制度的问题是显然的，比如如果只有两个州，a州5个人，而b州4个人，州票也分别是5和4，如果某候选人x在a州以3:2获胜，另一个候选人y在b州以4:0获胜，这样显然候选人y在全国范围内获得了6张票，而候选人x只有在a州的3张票，但是由于“赢者通吃”，x获得了a周的全部5张“州票”，y只获得了b周的4张“州票”，在全国只有1/3民众支持的x居然获得了选举的胜利。
这样的情况在2000年美国总统选举中就出现过，小布什的州票领先于戈尔，然而在全国民众中统计支持戈尔的人数却是大于小布什的，当然戈尔输给小布什还有另一个原因，这里按下不表。
如果放在算法领域，可以看出这里的问题在于，为了统计结果r（最适合的总统人选），找到了一个特征a（每个民众的投票），而决定结果r的，却不是特征a，而是由特征a推导出来的特征b（州票），在特征a向特征b的推导过程中，信息丢失了（每个洲的支持百分比不一样）。
“赢者通吃”这种制度的具体历史原因先不说，有兴趣的朋友可以去看原著。解决这种问题的最直接方案就是从“赢者通吃”变成直选，也就是一人一票，直接统计票数，然而这样也会遇到一系列问题。
在谈那一系列问题之前，先把要解决的问题抽象一下：
有n个候选人，每个选民对这n个候选人投票，最终在n个候选人中选出最合适、最符合民意、也符合逻辑的那个人。
方案1：一票制，每人一票，选出自己最喜欢的候选人，对结果进行统计，得票最多的那个人当选。
这样做的问题是会导致作者定义的一种“鹬蚌困局”，举例说，如果有abc三个候选人，其中bc政见比较类似，支持b的人也比较支持c，反之亦然，在全民中，喜欢bc的人占多数，a的政见和bc相反，支持a的人在全民中占少数。这样导致的后果就是，bc获得的票会比较分散，而a获得的票比较集中从而获得胜利，如果bc中有1人不参加选举，票就会集中到b或者c一个人的手中，从而使多数选民的支持者当选。前面按下不表的戈尔失败的另一个原因，就是有人认为有跟戈尔政见类似的耐德的参与，他分散了部分戈尔的选票。
可以对此问题有所改善的方案叫做“二选制”。
方案2：二选制，每人一票，如果无人获得大于50%的支持，则将得票最高的两个候选人拿出来，再进行一轮选举，得票多的人获胜。
法国总统选举就是这样的二选制，但是这样的方法只能改善“鹬蚌困局”，而不能彻底解决，2002年的法国总统大选就出现了类似的情况，当时支持左派政见的民众较多，然而在二选制下，最终的前两名却是一个右派和一个极右派。出现这种情况的原因是当年有16个总统候选人，且多数是持左派政见者，这样就导致左派的票极端分散。
方案3：n选制，每人一票，如果无人获得大于50%的支持，则去掉支持最少的候选人，再进行一轮投票，若依旧无人获得大于50%的支持，再去掉得票最少的候选人，直到有人大于50%支持为止。
2001年奥委会决定北京为2008年奥运会主办城市的时候，就是用的这样的制度，在第一轮投票里大阪被淘汰，北京在第二轮就获得了半数以上的支持，从而当选。
n选制的问题在于不实用，如果是奥委会这种只有几百个人投票的情况还可以使用，如果类似前面法国总统选举，有16个候选人，举国上下最多可能进行15次投票，成本太高。
方案4：即刻复选制，每个民众对候选人进行排序，如果某个候选人获得了50%以上的首选，则直接获得胜利，否则淘汰票数最低的候选人，并且把票数最低候选人的得票中的第二候选人拿出来，分给对应的候选人，如果有人获得50%以上，则当选，否则再淘汰一位最低的，并且把他票分给里面排序最高的且未被淘汰的候选人，如此往复。
爱尔兰总统选举和伦敦市长选举采用的是类似的方案，此方案也有问题，试想如此场景：选民共10人，中间派候选人是3人的首选，左派和右派的候选人分别是4人的首选，当然左派选民最讨厌右派候选人，而右派选民也最讨厌左派候选人，而左派右派的民众对中间派候选人倒是都可以接受，不管是即可复选制还是n选制，中间派候选人都会在第一轮被淘汰。而中间派候选人则是全体民众都可以接受的人，也最能调和各派之间矛盾，最和谐。
这个方案的本质问题是，虽然每个选民可以对候选人排序，但是在第一轮的时候却只考虑了第一选，没有考虑选民的二、三选。
方案5：上行复选制，跟方案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. 也许在网页排序问题上，真的存在这样一个“*特征”，这个“*特征”从目前看来，最适合的应该就是“用户满意度”了，按照用户的满意程度来排序网页，就是最合理的网页排序。如何衡量“用户满意度”呢？这就是我们一直在努力的。
by liangaili
先说美国选举制度，美国的总统选举是一种“赢者通吃”的方式，每个州根据其人口多少，有几十或几百的“州票”，州里的人对总统候选人进行选举，在某个州获得票最多的那个候选人，获得这个州所有的“州票”，然后统计所有候选人的“州票”多少，获得最多“州票”的候选人获胜。
这样制度的问题是显然的，比如如果只有两个州，a州5个人，而b州4个人，州票也分别是5和4，如果某候选人x在a州以3:2获胜，另一个候选人y在b州以4:0获胜，这样显然候选人y在全国范围内获得了6张票，而候选人x只有在a州的3张票，但是由于“赢者通吃”，x获得了a周的全部5张“州票”，y只获得了b周的4张“州票”，在全国只有1/3民众支持的x居然获得了选举的胜利。
这样的情况在2000年美国总统选举中就出现过，小布什的州票领先于戈尔，然而在全国民众中统计支持戈尔的人数却是大于小布什的，当然戈尔输给小布什还有另一个原因，这里按下不表。
如果放在算法领域，可以看出这里的问题在于，为了统计结果r（最适合的总统人选），找到了一个特征a（每个民众的投票），而决定结果r的，却不是特征a，而是由特征a推导出来的特征b（州票），在特征a向特征b的推导过程中，信息丢失了（每个洲的支持百分比不一样）。
“赢者通吃”这种制度的具体历史原因先不说，有兴趣的朋友可以去看原著。解决这种问题的最直接方案就是从“赢者通吃”变成直选，也就是一人一票，直接统计票数，然而这样也会遇到一系列问题。
在谈那一系列问题之前，先把要解决的问题抽象一下：
有n个候选人，每个选民对这n个候选人投票，最终在n个候选人中选出最合适、最符合民意、也符合逻辑的那个人。
方案1：一票制，每人一票，选出自己最喜欢的候选人，对结果进行统计，得票最多的那个人当选。
这样做的问题是会导致作者定义的一种“鹬蚌困局”，举例说，如果有abc三个候选人，其中bc政见比较类似，支持b的人也比较支持c，反之亦然，在全民中，喜欢bc的人占多数，a的政见和bc相反，支持a的人在全民中占少数。这样导致的后果就是，bc获得的票会比较分散，而a获得的票比较集中从而获得胜利，如果bc中有1人不参加选举，票就会集中到b或者c一个人的手中，从而使多数选民的支持者当选。前面按下不表的戈尔失败的另一个原因，就是有人认为有跟戈尔政见类似的耐德的参与，他分散了部分戈尔的选票。
可以对此问题有所改善的方案叫做“二选制”。
方案2：二选制，每人一票，如果无人获得大于50%的支持，则将得票最高的两个候选人拿出来，再进行一轮选举，得票多的人获胜。
法国总统选举就是这样的二选制，但是这样的方法只能改善“鹬蚌困局”，而不能彻底解决，2002年的法国总统大选就出现了类似的情况，当时支持左派政见的民众较多，然而在二选制下，最终的前两名却是一个右派和一个极右派。出现这种情况的原因是当年有16个总统候选人，且多数是持左派政见者，这样就导致左派的票极端分散。
方案3：n选制，每人一票，如果无人获得大于50%的支持，则去掉支持最少的候选人，再进行一轮投票，若依旧无人获得大于50%的支持，再去掉得票最少的候选人，直到有人大于50%支持为止。
2001年奥委会决定北京为2008年奥运会主办城市的时候，就是用的这样的制度，在第一轮投票里大阪被淘汰，北京在第二轮就获得了半数以上的支持，从而当选。
n选制的问题在于不实用，如果是奥委会这种只有几百个人投票的情况还可以使用，如果类似前面法国总统选举，有16个候选人，举国上下最多可能进行15次投票，成本太高。
方案4：即刻复选制，每个民众对候选人进行排序，如果某个候选人获得了50%以上的首选，则直接获得胜利，否则淘汰票数最低的候选人，并且把票数最低候选人的得票中的第二候选人拿出来，分给对应的候选人，如果有人获得50%以上，则当选，否则再淘汰一位最低的，并且把他票分给里面排序最高的且未被淘汰的候选人，如此往复。
爱尔兰总统选举和伦敦市长选举采用的是类似的方案，此方案也有问题，试想如此场景：选民共10人，中间派候选人是3人的首选，左派和右派的候选人分别是4人的首选，当然左派选民最讨厌右派候选人，而右派选民也最讨厌左派候选人，而左派右派的民众对中间派候选人倒是都可以接受，不管是即可复选制还是n选制，中间派候选人都会在第一轮被淘汰。而中间派候选人则是全体民众都可以接受的人，也最能调和各派之间矛盾，最和谐。
这个方案的本质问题是，虽然每个选民可以对候选人排序，但是在第一轮的时候却只考虑了第一选，没有考虑选民的二、三选。
方案5：上行复选制，跟方案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. 也许在网页排序问题上，真的存在这样一个“*特征”，这个“*特征”从目前看来，最适合的应该就是“用户满意度”了，按照用户的满意程度来排序网页，就是最合理的网页排序。如何衡量“用户满意度”呢？这就是我们一直在努力的。
by liangaili
上一篇： 拆解企业建站选择疑问，实现网站价值最大化