代表名额的分配ppt课件.pptVIP

1. 问题：美国众议院如何根据各州人口的比例分配众议院议员的名额。 m: 州数, pi: 第 i 州人口数, p =Σ pi: 总人口数 N: 议员数, ni: 第 i 州议员数, N=Σni. qi=(pi/p)N: 第 i 州应占有的议员的份额. 根据按人口比例分配的原则给出公平的议员席位分配的方案{n1, …, nm}，即ni尽可能地接近其应得的份额qi. 2. 背景 1787年美国颁布宪法,规定“众议院议员的名额…将根据各州的人口比例分配”, 并于1788年生效. 1791年 Alexander Hamilton（财政部长） 提出了议员席位分配的方法, 并于1792年通过。 1792年 Thomas Jefferson 提出了议员席位分配的除子法。 1851年开始用Hamilton法分配议员的席位。 1881年当议会的总席位由299席变为300席时，各州的人口数都没有变化，重新调整议员席位的结果却使Alabama亚拉巴州的议员席位却从 8人减少为 7人。这就是著名的 Alabama 悖论 后来，1890年人口普查之后，在各州人口数没有改变的情况下，当总席位由359席增加到360席时，Arkensas 州的议员的席位又丢掉了一个。Maine 州也出现了类似的情况。 1910年，Hamilton 的分配方法被停止使用了。 1920年，Harvard 大学的数学家 Edward Huntington，Joseph Hill 开始研究这个问题。 1941年，基于代表性不公平度的数学模型，他们提出了EP（Equal Proportions）法，用以分配议员的席位。并且由Roosevelt 总统将它写入了法律，至今仍然延用。 1970年Michael Balinsky Peyton Young 进一步研究，提出公理准则体系。 1980 年提出了著名的 Balinsky Young 不可能定理。 Huntington—Hill 算法 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 继续 . 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) 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个 1.公理化建模: 事先根据具体的实际问题给出一系列的约束, 称之为“公理”。它是所研究问题的基本要求，或所希望达到的基本目标。并据此寻求适当的数学结构来满足这些基本的要求。 如果存在唯一确定的数学结构，将它表达出来。 如果不可能有一个数学系统与公理体系相容，则需要找出虽然违背公理但是可以接受的模型。 如果存在许多模型满足公理的要求，则需要寻出其中最优者。 2.席位公平分配的公理模型（1974） 公理 1. (份额单调性) 一个州人口的增加不会导致它失去席位. 公理 2.(无偏性) 在整个时间上平均, 每个州应得到它自己应分摊的份额. 公理 3.(名额单调性) 总席位增加不会导致某个州名额减少. ni (N, p1, ,… pm ) ? ni (N+1, p1, ,… pm) 公理 4. (公平分配性) 任何州的席