前些天读了一本《推举的窘境》，此中有一章，从好国的推举造度道起，引见好国推举造度的不敷，然后针对其不敷，提出各种改进，但是每种改进皆有其各自的成绩，此中的变革很风趣。

先道好国推举造度，好国的总统推举是一种“赢者通吃”的方法，每一个州按照其生齿几，有几十或几百的“州票”，乡镇的人对总统候选人停止推举，正在某个州得到票最多的谁人候选人，得到那个州一切的“州票”，然后统计一切候选人的“州票”几，得到最多“州票”的候选人得胜。

那样造度的成绩是隐然的，好比假如只要两个州，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选造，中心派候选人城市正在第一轮被裁减。而中心派候选人则是部分公众皆能够承受的人，也最能和谐各派之间冲突，最调和。

那个计划的素质成绩是，固然每一个选平易近能够对候选人排序，可是正在第一轮的时分却只思索了第一选，出有思索选平易近的2、三选。

计划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，也即一定存正在“专制者”，那个成绩的证实，能够参考那篇专客：roba.rushcj/?p=509

按照“不成能的平易近主”实际，战搜索系统分离起去看，仿佛搜索系统很易给出一个开理的网页排序，可是搜索系统战投票又仿佛有所差别，有两个角度能够破解

1. 以为前提3过于强，需求强化。

2. 或许正在网页排序成绩上，实的存正在那样一个“专制特性”，那个“专制特性”从今朝看去，最合适的该当便是“用户合意度”了，根据用户的合意水平去排序网页，便是最开理的网页排序。怎样权衡“用户合意度”呢？那便是我们不断正在勤奋的。

by liangaili

文章滥觞：百度搜刮研收部民圆专客

注：相干网站建立本领浏览请移步到建站教程频讲。