数学代表名额的分配

1、7.1 代表名额的分配 一. 问题与背景 1. 问题：美国众议院如何根据各州人口的比例分配众议院议员的名额。 s: 州数, pi: 第 i 州人口数, p = pi: 总人口数 N: 议员数, ni: 第 i 州议员数, N=ni. 根据按人口比例分配的原则给出公平的议员席位分配的方案n1, , ns. qi=(pi/p)N: 第 i 州应占有的议员的份额. 求ni，与qi最接近。 二. 背景 1787年美国颁布宪法,规定“众议院议员的名额将根据各州的人口比例分配”, 并于1788年生效. 1791年 Alexander Hamilton 提出了议员席位分配的方法, 并于1792年通过. 17

2、92年 Thomas Jefferson 提出了议员席位分配的除子法。 1851年开始用Hamilton法分配议员的席位。 1881年当议会的总席位由299席变为300席时，各州的人口数都没有变化，重新调整议员席位的结果却使Alabama州的议员席位从 8人减少为 7人。这就是著名的 Alabama 悖论后来，1890年人口普查之后，在各州人口数没有改变的情况下，当总席位由359席增加到360席时，Arkensas 州的议员的席位又丢掉了一个。Maine 州也出现了类似的情况。1910年，Hamilton 的分配方法被停止使用了。1920年，Harvard 大学的数学家 Edward Hunt

3、ington，Joseph Hill 开始研究这个问题。1941年，基于代表性不公平度的数学模型，他们提出了EP（Equal Proportions）法，用以分配议员的席位。并且由Roosevelt 总统将它写入了法律，至今仍然延用。1970年Michael Balinsky & Peyton Young 进一步研究 。1980 年提出了著名的 Balinsky & Young 不可能定理。二. Hamilton 法及有关悖论 1. Hamilton 法： 记qi = int qi, 则有 qi-1qi qi, N-sqiN . 若等号成立, 则有 ni= qi=qi . 否则, 有 qi N

4、 . 令 k = N- qi , 0 k s . 记 ri = qi - qi , 不妨令 r1 r2 rs. 则有ni = qi +1, i = 1,k ni = qi , i = k+1,s 2. 有关悖论 10. Alabama 悖论: 人口不变, 总席位增加导致某州席位减少. 例1. P = 200, s = 3, N = 20 州 pi pi/p qi ni A 103 0.515 10.3 10 B 63 0.315 6.3 6 C 34 0.170 3.4 4 20. 人口悖论: 人口增长, 分额增加的州可能失掉席位. 例 2 . P=1000, s=3, N=3州 pi pi/

5、p qi ni A 420 0.420 1.260 1 B 455 0.455 1.365 1 C 125 0.125 0.375 1 30. 新州悖论: 原州人数不变, 增加新州(人数增), 席位按比例增, 将导致原州席位减少. 例 3. p=1000, s=2, N=4; p=1200, s=3, N=5州 pi qi ni A 623 2.492 2 B 377 1.508 23. Hamilton 法的数学模型 q = (q1,qs)T: 份额向量, 1Tq=qi =N n = (n1,ns)T: 分配向量, 1Tn=ni =N它们均位于s维空间的s-1维单形 (s维空间的超平面)中

6、. 对于 s = 3 的情形: 经变形,有 10. n, q 是高为 N 的正三角形上的点，该点到三个边的距离为它们的坐标。 20. 将三角形各边N等分，分别以平行各边的直线连接相应的等分点。连线在三角形内的交点将是三角形上有整数坐标的格点，这些点构成席位分配向量的集合n。 30. 连线将三角形分为若干小三角形。份额向量q为三角形上任意一点。该点到它所在的小三角形三个边的距离分别为三个坐标的小数部分。 40. 按照最大小数部分增加一个席位的H法相当于在 q 所在的小三角形中选择最靠近 q 点的顶点（格点 n）为席位分配方案。 50. Hamilton 分配域：作小三角形内心，则可以构成以 n

7、为心，以上述若干内心为顶点的正六边形。如果 q 落入某个小六边形内，则选择该六边形的中心 n 为席位的分配方案。三. Jefferson 的除子法 考虑 qi = N 且 qi N 的情形: 选择适当的除子 , 计算 qi* = qi/, 使得qi* =N. 取 ni = qi* . 除子法的数学模型？ “名额分配问题”，淑生，自然杂志，2（1993），4650。例 4 . P = 200, s = 3, N = 20 州 pi qi ni qi ni A 103 10.3 10 10.815 11 B 63 6.3 6 6.615 7 C 34 3.4 4 3.570 3 = 0.92 qi

8、* ni qi* ni A 103 11.2 11 11.75 11 B 63 6.8 6 7.19 7 C 34 3.4 3 3.88 3例 5 . P=1000, s=3, N=3 州 pi qi ni pi qi ni A 420 1.260 1 430 1.17 1 B 455 1.365 1 520 1.42 2 C 125 0.375 1 150 0.41 0 = 0.65 qi* ni pi qi* ni A 420 1.93 1 430 1.80 1 B 455 2.10 2 520 2.18 2 C 125 0.57 0 150 0.63 0名额分配 例 6. p=1000,

9、 s=2, N=4; p=1200, s=3, N=5 州 pi qi ni pi qi ni A 623 2.492 2 A 623 2.595 3 B 377 1.508 2 B 377 1.570 1 C 200 0.835 1 = 0.80 qi ni pi qi ni A 623 3.12 3 A 623 3.24 3 B 377 1.88 1 B 377 1.96 1 C 200 1.04 1 四. 局部不公平度和Huntington法 1. 不公平度 称第 i 州平均每位议员代表的人口数 pi/ni为该州议员的代表性指标。 它可以用来度量议员席位分配公平的程度： 若 pi/ni

10、= pj/nj, 则称这两州代表席位的分配是公平的. 若pi/ni p2/n2 称 为席位分配方案(n1, n2)对A 的相对不公平度 . 2. 席位公平分配的Huntington法则: 若i州转让一个席位给j州导致两州间相对不公平度的降低, 则进行这种转让. 连续进行这种席位的转让,直到任意两州间的转让不可能再降低它们之间的不公平度, 则可得到最优的席位分配方案 . 3. Huntington-Hill 算法定理：在席位分配方案（ni, nj）的基础上,再增加一个席位, 方案(ni+1, nj)优于(ni, nj+1),当且仅当 Qi Qj, 其中证明: 若方案(ni+1, nj)优于(ni

11、, nj+1), 则有 pi/ni pj/nj . 若 pi/(ni+1) pj/nj, 可得Qi Qj .若pi/(ni+1) pj/nj, 则由rj(ni+1, nj) Qj , 则有当pi/(ni+1) pj/nj, 时, 有pi/ni pi/(ni+1) pj/nj,显然, 方案(ni+1, nj)优于(ni, nj+1) .当pi/(ni+1) ri(ni+1, nj), 从而可知方案(ni+1, nj)优于(ni, nj+1) . 注. 关于Q: 是代表性指标pi/ni和pi/(ni+1)的几何平均值. 它表示在当前拥有ni 个席位的条件下, 考虑到再增加一个席位时的平均代表性指标

12、. 称Q为HuntingtonHill 数。 HuntingtonHill 算法 1. 令 ni(0 )= 1, 计算 Qi(0), i =1,2,s . 2. 对于k=1,2,取Qh(k)=max Qi(k-1) 3. 令 nh(k)=nh(k-1)+1, ni(k)=ni(k-1), i h 4. ni(k) =N 计算结束, 否则转 2 继续 . 例 7. 已知 p1= 103, p2=63, p3=34, 分配 N=21席位 n A B C 1 5304.5(4) 1984.5(5) 578.0(9) 2 1768.2(6) 661.5(8) 192.7(15) 3 884.1(7)

13、330.8(12) 96.3(21) 4 530.5(10) 198.5(14) 5 353.6(11) 132.3(18) 6 252.6(13) 94.5 7 189.4(16) 8 147.3(17) 9 117.9(19) 10 96.4(20) 11 80.4 11个 6个 4个例 8. 六个州分配100个席位州 人口p 份额q H法 J法 EP法A 9215 92.15 92 95 90B 159 1.59 2 1 2C 158 1.58 2 1 2D 157 1.57 2 1 2E 156 1.56 1 1 2F 155 1.55 1 1 2 10000 100 100 100

14、100五. 席位分配问题的公理化模型 1.公理化建模: 事先根据具体的实际问题给出一系列的约束, 称之为“公理”. 它是所研究问题的基本要求，或所希望达到的基本目标。并据此寻求适当的数学结构来满足这些基本的要求。 如果存在唯一确定的数学结构， 将它表达出来。 如果不可能有一个数学系统与公理体系相容， 则需要找出虽然违背公理但是可以接受的模型。 如果存在许多模型满足公理的要求， 则需要寻出其中最优者。 2.席位公平分配的公理模型 公理 1. (份额单调性) 一个州人口的增加不会导致它失去席位. 公理 2.(无偏性) 在整个时间上平均, 每个州应得到它自己应分摊的份额. 公理 3.(席位单调性) 总席位增加不会导致某个州名额减少. 公理 4. (公平分摊性) 任何州的席位数都不会偏离其比例的份额数. 公理 5. (接近份额性) 没有从一个州到另一个州的名额转让会使得这两个州都接近它们应得的份额. 公理可以分为两类：避免各种悖论的公理(I, III)和关于份额公平