缘由

最近尝试了下 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\) 个席位，各党派按照获得的票数占总票数的比例分配议会的席位。把席位当作连接数，得票数当作空块大小，那么这两个问题就是等价的了。

最大余额法

黑尔（Hare）数额

19世纪中期，一位英国的大律师黑尔，提出一种方法。假定总投票数为 \(P\)，总席位为 \(S\)。那可以简单得出获得一席所需要的票数，在这里称为数额（Quota）\(Q\)。

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

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

第二轮就是，根据各个党派得票数余数的大小，按从大到小顺序分配剩余席位，直到所有席位分配完成。所以这种方法也叫最大余额法。

最近被取消的香港立法会选举其中的地区直选，就是以黑尔数额的比例代表制。看一下一个实际的例子，以2012年立法会选举香港岛选区的结果为例.

表 1

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

\(S_{Civic} =\Bigl\lfloor{P_{Civic}/Q}\Bigr\rfloor = 1\)
\(R_{Civic} = P_{Civic} - S_{Civic}*Q = 23165.7\)

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

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

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

特罗普（Droop）数额

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

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

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

来看看是否如此：

计算可看此。

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

问题

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

悖论

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

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

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

另外一个悖论就曾在现实出现，1900 年弗吉尼亚得到 10 席缅因州得到 3 席。而 1901 年，这一年尽管当年弗吉尼亚的人口增加速度大于缅因州，反而被缅因州抢去一席。弗吉尼亚 9 席缅因州 4 席，见：1901年美国众议院选举-维基百科。这就是所谓的人口悖论（Population paradox），两个州的人口发生增长，增长率快州反而输给增长率慢的州一席。

配票

回头重新看下2012年立法会区域直选香港岛区的结果（见表 1），可以发现民建联（DBA）出现了两次。为什么要分两个名单参选呢，假设一下如果合并为一个名单会怎么样？演算一下便可以发现，最终民建联只能得 1 个席位，而民主派的公民党反能获得 2 票。

而民建联最终选择了分拆名单，避免了这种情况发生，这种行为就是配票，而且是相当成功的配票例子。但配票也需要对选票分配的预测相当有信心才能执行，切忌不自量力，历史上香港立法会、台湾立法委配票失败的例子也不少见。

余数相等

最大余额法，出现余数相等的情况怎么办？构造这个情况并不难，假设有 n 个候选人竞选 S 个席位，\(V_i\) 为候选人 i 的票数，\(V_i=a_i*Q+C\) ，Q 为黑尔数额，可得出 \(S=\frac{nC}{Q}+\sum\limits_{i=1}^{n}a_i\)，构造任意 a、n、C、Q 满足以下条件便可：

见此例子，出现这种情况只能更换数额算法，或不用最大余额法了。当然现实中是几乎不可能出现这种情况的。

最高均数法

另外一种与最大余额法相对于的就是最高均数法，而且最高均数法已被证明能避免最大余额法遇到的悖论。最高均数法取得席位的方式相当于依次对每个席位进行竞标，只是价格不是绝对而是相对，而且价格依取得的席位数增加而递减。以下表为例，三个政党竞选 4 个席位。

第一轮 A 票数最高，A 得 1 席，A 的票数更新为 \(\frac{V_A}{2}\)，第二轮还是 A 最高，A 获得第二席，所以 A 票数更新为 \(\frac{V_A}{3}\)，第三轮 B 票数最高，B 获得第一席，B 票数更新为 \(\frac{V_B}{2}\)，依次类推，直到所有席位分配完成。

可以看出，获得第 n 席的剩余票数为 \(\frac{V}{n+1}\)。换一句话说也就是，A 能获得 n 个席位，是因为其票数平均 n 分的均数最大，所以叫最高均数法。这是一个比较接近实际的例子，数据来自 2004 年的印度大选。

最高均数法也叫除数法，政党获得第 n 席的剩余票数等于得票数除以一个除数序列的第 n 项，这个序列可以一般化为 \(f(n)\)，\(f(n)=n+1\) 时，称为洪德法(d’Hondt)。其他不同的最高均数法，也就是 \(f(n)\) 的取值不同而已。

const dHondt = (s) => s+1  // 洪德法
const sLague = (s) => s*2+1 // 聖拉古法（Sainte-Laguë）
const imperiali = (s) => (s+2)/2 // 因佩里亚利（Imperiali）
const modSLague = (s) => s==0?1:(2*s+1)*5/7 // 改良圣拉古法

不同的方法，最大的影响是\(f(n)\)的增长率，增长率越快越有利于小党派，相反则的有利大党派。大多方法都是一次函数，所以系数越大就越有利于小党派。除了亨廷顿-希尔法（Huntington–Hill method）：

Huntington–Hill 的增长率其实是非常接近于 d’Hondt 的。它也是美国现行为各州分配众议院席位所用的方法。

数额法则

最高均数法可以避免阿拉巴马悖论和人口悖论，基本上也是现行比例代表制选举中最常用的方法，但它也不是完美的。重新回过头来看这个问题，总投票数为 \(P\)，总席位为 \(S\)。政党 i 的得票为 \(V_i\)。在一个理想的世界里政党 i 的席位为：

我们知道绝大多数情况下 \(A_i\) 是个小数，这个数称为 i 的自然数额（nature quota）。应用分配方法的目的就是对自然数额进行取整，而取整无外乎是向下取整或向上取整。

这个就是数额法则的定义，分配给一方的席位数量应该为其自然数额的向上取整整数或向下取整整数。能称为法则想必是十分重要，但看似完美的最高均数法就违反了这个法则。

结语

实际上 Balinski & Young 已经证明了不违反数额法则同时又能避免悖论的分配方法是不可能的。也就是说整数分摊实际上没有严格意义上的公平解法。那么回最开始遇到的问题，寻找分配连接的最优解，如此绞尽脑汁也就情有可原了。不过公平不可能，最优解却是可能的。只需定义什么是最优，比如说实际席数与自然数额之间的距离最小便是最优（可见参考资料1、2），因为席位是整数搜索空间有限，只需遍历所有可能便可以找到最优，如果满足数额法则那么搜索的空间便更小了。

正因为绝对公平的不可能，国家政策的制定者就可以通过调整这些方法让政策偏向大多数或者少数，比如说加大最大余额法的数额，或者最高均数法选择增长率较快的除数序列，来让少数派的得到发声机会。当然选择相反的策略，也能说成是阻止极端主义的发展。好像政府怎么做都是对的，不过阻止极端主义这方面还真有反例，魏玛共和国的帝国议会让纳粹崛起就是一个鲜明的反例。

• 例子中所用的最大余额法实现见：largest_remainder.js
• 例子中所用的最高均数法实现见：highest_average.js

参考资料

• A Mathematical Exploration of Apportionment Procedures Around the World
• RangeVoting.org - Apportionment and rounding schemes
• 比例代表制是甚麼？
• Apportionment paradox - Wikipedia