谈谈比例代表制

Question

最近尝试了下 Golang，练手 Goroutines 实现了个多连接的 http 下载工具 gotit 。所谓的多连接下载，就是对支持 http-range 的资源的同时发起多个 http 请求，每个请求负责资源的不同部分，最终完成整个资源的下载。有一种情况是，下载中断后本地文件会留下多个不连续大小不一的未写入数据的空块。若重新恢复下载，如何为这些空块分配连接呢？考虑到连接数是可配置的，不应假定连接数与空块数存在相关性。一个容易想到的策略是:

• 当连接数小于等于空块数，空块按任意顺序排成队列，每个空闲链接向队列请求空块，直到队列为空。
• 当连接数大于空块数，为了让每个链接都得到分配，直觉的想法是较大的空块占用多一些连接，让每个连接负责的大小接近。

举个例子，存在两个空块大小分别是 10M 、 5M ，可分配连接数为 3 ，连接数大于空块数，根据策略二，基于空块的大小按比例分配连接，可算出 10M 得到 2 个连接， 5M 得到 1 个连接。这里不讨论这样的策略是否有效，而是另外一个问题，假设连接数变为 4 ，继续按比例分配， 10M 得到 2.67 个连接 5M 得到 1.33 个，连接数是整数，一个连接可不能撕成 2 个，肯定不能这样分配。那么多出来一个连接该给 10M 还是 5M ？

如何分配这部分余数看似简单其实并不容易，难度在于如何找出最优解，甚至是如何定义最优解。这问题困扰了我相当长的时间，直到与比例代表制联系起来。 作为一个活到现在还没见过选票的“公民”要不是最近选举的新闻有点密集还真很难认识这个问题就是比例代表制中的整数分配问题（Apportionment）。所谓比例代表制，就是 代议制民主 中的两种主要选举方式之一。

另外一种是多数制，也就是赢者通吃，票高者赢，可看下台湾高中的课件 選舉制度的類型 了解下。比例代表制常用于议会选举中，举一个粗略的例子，比如议会有 S 个席位，各党派按照获得的票数占总票数的比例分配议会的席位。把席位当作连接数，得票数当作空块大小，那么这两个问题就是等价的了。 19 世纪中期，一位英国的大律师 黑尔 ，提出一种方法。假定总投票数为 P，总席位为 S。那可以简单得出获得一席所需要的票数，在这里称为数额（Quota）Q。

Q=PS

计票分为两轮，第一轮是各个党派根据数额和得票数取尽可能的席位，也就是得票数除以数额后取整数部分，比如党派 i 第一轮的得票数：

ni=⌊PiQ⌋

党派 i 得票数的余数也可以被计算出来：

Ri=Pi−niQ

第二轮就是，根据各个党派得票数余数的大小，按从大到小顺序分配剩余席位，直到所有席位分配完成。所以这种方法也叫最大余额法。 最近被取消的香港立法会选举其中的地区直选，就是以黑尔数额的比例代表制。看一下一个实际的例子，以 2012 年立法会选举香港岛选区的结果 为例：

表 1

编号	政党	票数	第一轮	余额	第二轮	总席位
2	民主党	40,558	0	40,558	1	1
4	人民力量	18,667	0	18,667	0	0
5	民建联	33,901	0	33,901	1	1
7	工党	31,523	0	31,523	1	1
8	新民党	30,289	0	26,037	1	1
9	工联会	27,336	0	27,336	1	1
10	公民党	70,475	1	23,222	0	1
12	民建联	36,517	0	36,517	1	1
13	自由党	17,686	0	17,686	0	0

2012 年香港岛选区总席位 S=7，总有效选票 P=330766，根据黑尔配额公式可得 Q=P/S=47252.3 ，篇幅所限，表上省略了得票较低的名单。表上得票数大于 Q 的只有公民党，所有第一轮得票的政党只有公民党(Civic)：

SCivic=⌊PCivic/Q⌋=1
RCivic=PCivic−SCivic∗Q=23165.7

计算余数后继续第二轮分配。第二轮席位余下 6 席，所以再选余额数最大的六个政党，分别是民主党、民建联、工党、新民党、工联会、民建联。至此 7 个席位分配完毕。全部计算结果可见 此 。

可见这种方法是简单直观且容易理解，也有人认为这种方法是美国建国之父 汉密尔顿 首先提出的，所以在美国也有叫汉密尔顿法（Hamilton’s Method of Apportionment）。然而这种看似简单直观似乎又公平的分配方法，并没有直觉认为的那么公平，这个后面再说。

黑尔数额并不是最大余额法的唯一方法，不过这些方法的区别是在数额的计算，而第二轮余数分配的机制是一样的，所有这一类的分配方法都统称为最大余额法。

同样是 19 世纪中期，同样是英国大律师 特罗普 ，认为获取一个席位的票数也就是数额，并不是如黑尔所说的，而是：

Q=PS+1

他是的理由如下，竞争两个席位的情况，得票数超过 1/3 的必将赢得一席，如果是三个席位，那么得票数超过 1/4 将赢得一席。通过归纳法可得出，争夺 S 个席位的选举中，得票数超过 P/(S+1)的党派都将赢得一席。所以特罗普对数额 Q 的定位就是，获得一席所需要的最低票数。

可以观察到，相比黑尔数额，特罗普数额的分母变大了，数额就变小了，也就是说获取一个席位的代价变低了。似乎对小党派更有利了。结合另外一种数额更低的，设计本意是为了偏袒小党派的 因佩里亚利(Imperiali)数额

Q=PS+2

来看看是否如此：

政党	得票数	黑尔	特罗普	因佩里亚利
A	30	64	64	65
B	12	25	26	25
C	5	11	10	10

计算可看 此 。

在采用特罗普法或因佩里亚利法后,得票最少的 C 一席反而分别被 B 和 A 抢去。实践中也发现更小的数额反而更有利于得票多的大党派，这是因为更小的数额，导致第二轮剩下的席位变少了，小党派主要靠第二轮来取得席位，席位变少相应的获得席位的概率也就降低。

上面提到最大余额法并没有直觉上公平，其一便是不同数额的可以微调席位的分配。其二就是会出现非常反直觉的不公平结果。

美国为各州分配众议院席位的方法也是使用比例代表制分配。州相当于候选名单，州的人口就相当于选票。虽然现行的宪法规定众议院的席位固定为 435 席，但 20 世纪前众议院的席位并不是固定 435 席而是随人口的增长而增加。1880 的人口普查发现，总人口不变的情况下，众议院有 299 席位时，阿拉巴马州获得 8 个席位，当总席位增加到 300 时，阿拉巴马州反而失去一席剩下 7 席。制造一个例子很简单：

政党	得票数	4 席	5 席
A	5	2	3
B	3	1	2
C	1	1	0

把场景换成议会的不公平就非常显而易见了，议会总席位增加一席，投票保持不变的情况下某个政党却会因此失去一席。这种现象便称为阿拉巴马悖论（Alabama Paradox）。这就是最大余额法不可避免的问题。

阿拉巴马悖论，只存在理论计算中，现实中并未未发生，并不是阿拉巴马悖论不易发生，实际上预期每 8 次分配就会发生一次，而现实没发生原因是众议院不再采用最大余额法分配席位，实际上还有个前提就是要现实中两次投票的比例保持不变这概率也是几乎不可能