算法与数据结构 / 把整数名额按比例分下去 待审核
apportionment

把整数名额按比例分下去

把一组带小数的比例四舍五入成整数，结果加起来往往不等于该有的总数。饼图的三块写 20%、30%、49%，合计只有 99%；议会按得票分席位，逐项取下整之后总有几席没分出去。根因是独立取整不守恒：各项的小数被各自截断，丢掉的零头不会自动回到总数上。这一整类问题称为 apportionment（配额分配），本页依次给出三段：补齐总数的做法、它带来的悖论，以及绕开悖论要付出的代价。

记各方的人口或票数为 pip_i，待分配的总名额为 HH，则第 ii 方的精确配额是 qi=H⋅pi/∑jpjq_i = H \cdot p_i / \sum_j p_j，余数是 ri=qi−⌊qi⌋r_i = q_i - \lfloor q_i \rfloor。

1 · 独立取整的不守恒

三块占比 20.3%、30.4%、49.3%，精确值合计正好 100%。各自四舍五入成 20、30、49 之后合计只剩 99%。问题不在某一次取整，而在独立取整本身：∑i⌊qi⌋\sum_i \lfloor q_i \rfloor 一般小于 HH，缺口是 k=H−∑i⌊qi⌋k = H - \sum_i \lfloor q_i \rfloor。

最大余额法把取整拆成两步：先各取下整，再把这 kk 个名额补给余数 rir_i 最大的 kk 方。

图 1-1 · 三块权重变化时朴素四舍五入与最大余额法的合计对照。可拖动权重滑块，观察朴素取整那一行的合计在 99 与 101 之间摆动，以及缺口名额被补到余数最大的哪几块上。

补给余数最大的那几方，等价于在「整数且合计为 HH」的约束下最小化 ∑i∣si−qi∣\sum_i |s_i - q_i|，其中 sis_i 是最终名额。理由是：把名额给第 ii 方使该项偏差由 rir_i 变为 1−ri1 - r_i，净减少 2ri−12r_i - 1，因此优先给 rir_i 最大的方。这一做法在选举语境下称为 Hamilton 法 [2]。

它的落地面比选举宽得多：图表库的百分比标签（ECharts 与 Highcharts 都处理过这个缺陷）、预算按比例摊到整数单位、问卷结果的整数百分比展示，凡是「连续比例落成整数又要求合计守恒」的场合都会遇到。把总名额从 100 换成议会席位数，它就是选举里的 Hare quota 加最大余额。

2 · Alabama 悖论

最大余额法在凑齐总数上无懈可击，却有一处反直觉的行为：各方份额原封不动，仅把 HH 调大一个，某一方的名额会不增反降。

图 2-1 · 固定人口下各方席位随总席位 HH 的变化。折线在 HH 增大时向下拐（红圈处）即一次 Alabama 悖论。默认人口 6 : 6 : 2，H=10→11H = 10 \to 11 时第三方从 2 席跌到 1 席。

以图 2-1 的默认人口验证：H=10H = 10 时三方的精确配额是 4.2864.286、4.2864.286、1.4291.429，下整后合计 9，缺 1 席，余数最大的是第三方（0.4290.429），结果为 4、4、2。H=11H = 11 时配额变成 4.7144.714、4.7144.714、1.5711.571，下整后仍是 9，这次缺 2 席，余数最大的两个变成前两方（各 0.7140.714），结果为 5、5、1，第三方反而少了一席。

Alabama 悖论因此得名于 1881 年：美国众议院依 1880 年人口普查重分席位时，制表员 C. W. Seaton 算遍了 275 至 350 各档众议院规模，发现总席位从 299 增到 300 时，Alabama 州的席位从 8 降到 7 [1]。

警示 · 悖论的成因不是实现缺陷。HH 增加时每一方的配额 qiq_i 按同一比例放大，余数 rir_i 却各涨各的，缺口 kk 也随之改变；最大余额法用余数排名分配缺口，而排名在 HH 变化时并不单调。凡是「先取整、再按某种排名补齐」的方案都会有同类问题。

3 · 除数法与单调性

定义 3.1（除数法） 不计余数，逐席分配：每一席交给当前商 pi/d(si)p_i / d(s_i) 最大的一方，其中 sis_i 是该方已得席数，dd 是一个递增的除数序列。D'Hondt 法（又称 Jefferson 法）取 d=1,2,3,…d = 1, 2, 3, \dots，Sainte-Laguë 法（又称 Webster 法）取 d=1,3,5,…d = 1, 3, 5, \dots。

图 3-1 · 各方票数除以各档除数得到的商表，取前 HH 大的商即为席位归属。可单步执行观察每一席被哪个商夺走（橙框为该步选中的最大商），并切换两种除数序列对比结果。

D'Hondt 的除数增长慢，大党连拿几席后商下降有限，容易继续压过小党；Sainte-Laguë 的除数从 1 直接跳到 3，大党拿到第二席后商近乎减半，机会更快让给小党。图 3-1 的默认票数 47 : 16 : 15 : 12 共 10 席，D'Hondt 给最大党 6 席（其商依次为 47、23.5、15.67、11.75、9.4、7.83），Sainte-Laguë 只给 5 席。

除数法把分配看成从大到小依次取商：HH 增到 H+1H+1 只是再取下一个商，前 HH 席的归属原封不动。席位关于 HH 单调不减，Alabama 悖论被根除。代价是它不保证配额约束，某方席位可能偏离其 qiq_i 超过一席。

定理 3.2（Balinski–Young） 当参与方多于三个时，不存在同时满足下列两条的分配方法：其一，恒不违反配额约束，即每方所得总是 ⌊qi⌋\lfloor q_i \rfloor 或 ⌈qi⌉\lceil q_i \rceil；其二，不出现人口悖论，即甲方得票增加而乙方得票减少时，不会有席位从甲方转到乙方 [1]。

需要留意的是，定理里被权衡的是配额约束与单调性，而非「合计等于 HH」——后者是两类方法共同的前提，不在取舍之列。

按上述数据核算，Sainte-Laguë 与最大余额法在这组票数上结果完全相同：H=10H = 10 时同为 5、2、2、1，H=11H = 11 时同为 6、2、2、1。这是这组数据的巧合而非规律，定理 3.2 保证的恰恰是没有哪种除数法能始终落在配额内。

4 · 参考文献

  1. Balinski, M. L., & Young, H. P. (1982). Fair Representation: Meeting the Ideal of One Man, One Vote. New Haven: Yale University Press.
  2. Balinski, M. L., & Young, H. P. (1975). The quota method of apportionment. The American Mathematical Monthly, 82(7), 701–730.

相关链接

  • 饼图百分比 zhangwenli.com 本系列的缘起：修 ECharts 饼图标签「整数百分比合计不为 100」的 bug，正是最大余额法的应用。
  • Largest remainder method Wikipedia 最大余额法 (Hare / Hamilton) 的定义、配额取法 (Hare / Droop) 与它的几种悖论。
  • Apportionment paradox Wikipedia Alabama / Population / New-states 三大悖论，以及它们的历史背景。
  • Highest averages method Wikipedia 除数法家族：D'Hondt / Sainte-Laguë / Huntington–Hill 各自的除数序列与偏向。
  • Balinski–Young theorem Wikipedia 不可能定理：参与方多于三个时，没有分配法能同时做到恒不违反配额约束与不出现人口悖论。