Nondeterministic 的爱尔兰单一可转移投票制度 PR STV?

前几天我有几位朋友在说爱尔兰选议员的计票方法导致出结果很慢。 我大致看了一下计票规则， 感觉好像也不是太过复杂， 就是一遍一遍人工数票确实很慢。 于是今天中午午休的时候就试着写一段小程序来模拟下爱尔兰的计票过程。 工作人员只要输入每张选票上的排名， 输入完毕以后，计算机在几秒之内就可以出结果的， 哪怕是当中需要不停转移。

具体算法可以参考维基百科上的介绍。

就计算复杂度来说，基本上是计算机系第一学期的家庭作业，有兴趣的中学生也可以写。 但是写代码的过程中我发现一个问题： 这种计票方法其实可能是 nondeterministic 的。 也就是说， 同样的一堆有效选票， 同样的计票方法， 每次计票可以得出不同的最终结果。

为什么是这样呢？ 因为那些成为 surplus 而被转移的选票， 上面还有后续的第二选择， 第三选择等重要信息， 会影响到后几轮的计票结果。 每张选票， 上面的 choice 链是不一样的。 不同的选票在前几轮中被转移， 就会导致后面几轮计票的不同结果。 让我们看一个具体例子。 一般来说， 第一轮计票一定是 deterministic 的。 假设第一位当选者总共得了 11001 张票， 有 1000 张选票可以分给人家。 假如我们把那些给当选者的 11001 张选票全部再数一遍， 按第二选择的比例来给余下的候选人分配多余票， 那么第 2， 3， 4， 。。。 名每人从第一轮的 surplus 中分到多少票也是一件确定的事。 现在就出现问题：



在当选者的 11001 张选票中， 怎样选出 1000 张分给人家？ 具体地说， 假如在这 11001 张选票中， 有 6600 张选票， 也就是 60%， 选 Adam 为第二选择， 那么就要在这 6600 张选票中选出 600 张给 Adam。 怎么选呢？ 假如是随机选， 那么几乎可以保证， 每次点票结果都是不一样的， 从第三轮开始结果不一样。 因为那些以 Adam 为第二选择的每张选票上， 第三选择都是不一样的。 

那些不被转移的 10001 张选票中，所有的第二选择， 第三选择等等都作废了。 事实上， 那些被转移的票子很幸运， 因为， 它们不光成功实现了第一愿望，上面的第二愿望， 乃至第三愿望都可以得到彰显， 至少不是作废信息。 被转移的选票所显示的“民意量” 是大于那些不被转移的选票的。 怎样选这 1000 张才够公平够代表民意？ 除了公平问题， 还有一个确定性的问题。 不同的选票被转移， 会导致不同的后续选择结果。

总之这个 counter 程序写着写着， 我发现还是有一些未知规则的。 或者， 爱尔兰人民接受这样的不确定性。 后来在网上查了一下， 确实， 在爱尔兰好像是这样，如果有候选人不服计票结果， 是可以要求重新计票的。 我只能这么说， 每个地区，第一轮 （无 surplus 转移票的情况下） 和第二轮 （前面只有一次 surplus 转移票的情况下） 计票选出来的议员们还是比较可以确定的， 再数多少遍都会是他们。 但是两轮 surplus 票转移以后选出来的议员， 再计一次票就有可能落选啦。

我觉得， 让民众可以在选票上 rank 自己的喜好是一件很好的事。 但是， 目前的计票模型有可能需要 refine 一下。 怎样 refine 才能使尽可能多的选票上的所有喜好 rank 都可以得到体现？ 或者用统计学的术语这样说， 怎样 refine 这个计票模型才能使每次计票结果都向所有选票上反映的民意 “收敛”， 而尽可能不出现每次计票结果不同的情况？ 这个我会考虑。 有想法了会在这里 update。  

还有 10 天不到我这里要地选了， 现在我还是研究一下本地形势算啦。

update: 刚刚想到， 计算每个候选人的加权名次总分就可以。 即 sum(w_i*x_i),  i 为名次数， 如果有 n 个候选人， 范围就是从 1 到 n。w_i 是名次的权重， 基本上同名次成反比。 比如， 第一名权重就大一些， 最后一名权重很小。  x_i 则是这个候选人在名次 x 上的得票数。 比如， 一共六位候选人， 民众对候选人 Adam 的观感是： 第一喜欢 1000 人， 第二喜欢 2000 人， 第三喜欢 600 人， 第四喜欢 0 人， 第五喜欢 90 人， 第六喜欢 200 人。  假设每个名次的权重分别为 6， 5， 4， 3， 2， 1， 那么 Adam 在这场选举的总得分为：

score (x_i) = 6 * 1000 + 5 * 2000 + 4 * 600 + 3 * 0 + 2 * 90 + 1 * 200 = 18780

每个候选人都可以算出这样一个分数， 然后按分数高低排队就是了。  这个算法， 每张选票的每一个选择都有被采用到， 没有浪费选民的任何感情。

还可以设计这样一个 scaling 函数：

popularity_i = f ( score (x_i) ) = 1 / ( 1 - e ^ (- score(x_i) )

这个 popularity 值在 0 到 1 之间。 越接近 1 的候选人， 越受民众喜爱。


update： 搞清楚了。  当某一轮中发生选票转移时，具体哪几张选票发生转移无关紧要。 必须知道的是： 1. 本轮中有几张选票可以转移；2. 本轮中的下一选择分布情况 (百分比). 对于下一轮接收方来说, 只须知道接收的选票是来自哪里就可以. 因为在候选人遭淘汰的情况下, 必须到选票来源那里去读取相应的下下一轮选择. 这样就不存在随机抽样的情况, 可以保证点票结果是 deterministic 的. 而每轮点票中, 当选门槛必须重新算。许多选票要重新遍历以计算本轮的 valid 选票。还好, 重算当选门槛的复杂度等级是 worst case O(n), n 为选票数。