席位分配问题.ppt
36页
公平的席位分配模型公平的席位分配模型 1. 问题：美国众议院如何根据各州人口的比例问题：美国众议院如何根据各州人口的比例分配众议院议员的名额分配众议院议员的名额?•s-- 州数州数, pi-- 第第 i 州人口数州人口数, p =Σ pi--总人口数总人口数•N--议员数议员数, ni--第第 i 州议员数州议员数, N=Σni.•根据按人口比例分配的原则给出公平的议员根据按人口比例分配的原则给出公平的议员席位分配的方案席位分配的方案{n1, …, ns}. •qi=(pi/p)N: 第第 i 州应占有的议员的份额州应占有的议员的份额. •求求{ni}，，与与{qi}最接近 一. 问题与背景 2. 背景背景•1787年美国颁布宪法年美国颁布宪法, 规定规定“众议院议员的众议院议员的名额名额…将根据各州的人口比例分配将根据各州的人口比例分配”, 并于并于1788年生效年生效.•1791年年 Alexander Hamilton 提出了议员席位提出了议员席位分配的方法分配的方法, 并于并于1792年通过年通过.•1792年年 Thomas Jefferson 提出了议员席位分提出了议员席位分配的除子法。
配的除子法•1851年开始用年开始用Hamilton法分配议员的席位法分配议员的席位一一. 问题与背景问题与背景 Alabama 悖论悖论• 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 进一步研进一步研究究 •1982 年提出了著名的年提出了著名的 Balinsky & Young 不可能定不可能定理 二二. Hamilton 法及有关悖论法及有关悖论1. Hamilton 法：法：记记[qi] = int qi, 则有则有 qi-1<[qi] qi, N-s<Σ[qi]≤N . 若等号成立若等号成立, 则有则有 ni= qi=[qi] . 否则否则, 有有 Σ[qi] < N . 令令 k = N- Σ[qi] , 0 < k < s . 记记 ri = qi - [qi] , 不妨令不妨令 r1 r2 rs. 则有则有ni = [qi] +1, i = 1,…,k ni = [qi] , i = k+1,…,s 悖论的举例悖论的举例(1)2. 有关悖论有关悖论• 10. Alabama 悖论悖论: 人口不变人口不变, 总席位增加总席位增加导致某州席位减少导致某州席位减少. 例例1. P = 200, s = 3, N = 2021 州州 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, 人口增加人口增加100人后人后…州州 pi pi/p qi ni A 420 0.420 1.260 1B 455 0.455 1.365 1C 125 0.125 0.375 1悖论的举例悖论的举例(2) 悖论的举例悖论的举例(3)•30. 新州悖论新州悖论: 原州人数不变原州人数不变, 增加新州增加新州(人人数增数增), 席位按比例增席位按比例增, 将导致原州席位减少将导致原州席位减少. 例例 3. p=1000, s=2, N=4; p’=1200, s’=3, N’=5州州 pi qi ni A 623 2.492 2B 377 1.508 2 Hamilton 法解释法解释•3. Hamilton 法的数学模型法的数学模型q = (q1,…,qs)T: 份额向量份额向量, 1Tq=Σqi =Nn = (n1,…,ns)T: 分配向量分配向量, 1Tn=Σni =N它们均位于它们均位于s维空间的维空间的s-1维单纯形维单纯形 (s维空间维空间的超平面的超平面)中中 . Hamilton 法解释法解释•对于对于 s = 3 的情形的情形: 经变形经变形,有有10. n, q 是高为是高为 N 的正三角形上的点，该点到三的正三角形上的点，该点到三个边的距离为它们的坐标。
个边的距离为它们的坐标20. 将三角形各边将三角形各边N等分，分别以平行各边的直线等分，分别以平行各边的直线连接相应的等分点连线在三角形内的交点将是三角连接相应的等分点连线在三角形内的交点将是三角形上有整数坐标的格点，形上有整数坐标的格点，这些点构成席位分配向量的集合这些点构成席位分配向量的集合{n}30. 连线将三角形分为若干小三角形份额向量连线将三角形分为若干小三角形份额向量q为三角形上任意一点为三角形上任意一点该点到它所在的小三角形三个边的距离分别为三该点到它所在的小三角形三个边的距离分别为三个坐标的小数部分个坐标的小数部分 Hamilton 法解释法解释40. 按照最大小数部分增加一个席位的按照最大小数部分增加一个席位的Hamilton法相当于在法相当于在 q 所在的小三角形中选择最靠近所在的小三角形中选择最靠近 q 点的顶点（格点点的顶点（格点 n））为席位分配方案为席位分配方案50. Hamilton 分配域：作小三角形内心，则可以分配域：作小三角形内心，则可以构成以构成以 n 为心，以上述若干内心为顶点的正为心，以上述若干内心为顶点的正六边形 如果如果 q 落入某个小六边形内，则选择该六落入某个小六边形内，则选择该六边形的中心边形的中心 n 为席位的分配方案。
为席位的分配方案 三三. . Jefferson的除子法的除子法 考虑考虑 Σqi = N 且且 Σ[qi] < N 的情形的情形:选择适当的除子选择适当的除子 λ, 计算计算 qi* = qi/λ, 使得使得Σ[qi*] =N. 则取则取 ni = [qi*] .除子法的数学模型？除子法的数学模型？“名额分配问题名额分配问题”，淑生，自然杂志，，淑生，自然杂志，2（（1993），），46~50 •例例 4 . P = 200, s = 3, N = 2021• 州州 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* 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, 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 = pj/nj, 则称这两州代表席位的分配是则称这两州代表席位的分配是公平的公平的. 若若pi/ni < pj/nj, 则称第则称第 j 州议员的代州议员的代表性表性低于低于第第 i 州议员的代表性州议员的代表性. (绝对绝对)不公平度不公平度令令 dij = pi/ni - pj/nj, 则称则称|dij|为为 i, j 两州席两州席位分配的位分配的(绝对绝对)不公平度不公平度 .例例 p n p/n |d|A 120 10 12B 100 10 10 2C 1020 10 102 D 1000 10 100 2(绝对绝对)不公平度无法比较不同组间席位分配不公不公平度无法比较不同组间席位分配不公平的程度平的程度 相对不公平度相对不公平度令令A, B两州的代表性指标为两州的代表性指标为 p1/n1, p2/n2, 若若 p1/n1> p2/n2 称称 为席位分配方案为席位分配方案(n1, n2)对对A 的的相对不公平度相对不公平度 . 席位公平分配的席位公平分配的Huntington法则法则2. 席位公平分配的席位公平分配的Huntington法则法则:若若i州转让一个席位给州转让一个席位给j州导致两州间相对州导致两州间相对不公平度的降低不公平度的降低, 则进行这种转让则进行这种转让.连续进行这种席位的转让连续进行这种席位的转让,直到任意两州直到任意两州间的转让不可能再降低它们之间的不公平度间的转让不可能再降低它们之间的不公平度,则可得到最优的席位分配方案则可得到最优的席位分配方案 . Huntington-Hill 算法算法 3. Huntington-Hill 算法算法定理：在席位分配方案定理：在席位分配方案(ni, nj)的基础上的基础上,再增再增加一个席位加一个席位, 方案方案(ni+1, nj)优于优于(ni, nj+1),当当且仅当且仅当 Qi > Qj, 其中其中证明证明: 若方案若方案(ni+1, nj)优于优于(ni, nj+1), 则有则有 pi/ni > pj/nj . 若若 pi/(ni+1) ≥ pj/nj, 可得可得Qi > Qj .若若pi/(ni+1) < pj/nj, 则则由由rj(ni+1, nj)
数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 ≠ h4. Σ ni(k) =N 计算结束计算结束, 否则转否则转 2 继续继续 . Huntington—Hill 算法算法——Q值算法值算法 举例举例 例例 7. 已知已知 p1= 103, p2=63, p3=34, 分配分配 N=21席位席位 n A(1-3) B(1-3) C(1-3) 2 5304.5(4) 1984.5(5) 578.0(9)Q2 3 1768.2(6) 661.5(8) 192.7(15) 4 884.1(7) 330.8(12) 96.3(21) 5 530.5(10) 198.5(14) 6 353.6(11) 132.3(18) 7 252.6(13) 94.5 8 189.4(16) 9 147.3(17) 10 117.9(19) 11 96.4(20) 80.4 11个个 6个个 4个个•问题：若再增加一问题：若再增加一个席位应该给谁？个席位应该给谁？ 各方法比较各方法比较•例例 8. 8. 六个州分配六个州分配100100个席位个席位•州州 人口人口p p 份额份额q Hq H法法 J J法法 EPEP法法•A 9215 92.15 92 95 90A 9215 92.15 92 95 90•B 159 1.59 2 1 2B 159 1.59 2 1 2•C 158 1.58 2 1 2C 158 1.58 2 1 2•D 157 1.57 2 1 2D 157 1.57 2 1 2•E 156 1.56 1 1 2E 156 1.56 1 1 2•F 155 1.55 1 1 2F 155 1.55 1 1 2•Σ 10000 100 100 100 Σ 10000 100 100 100 100100 五五. 席位分配问题的公理化模型席位分配问题的公理化模型1. 公理化建模公理化建模: 事先根据具体的实际问题给出事先根据具体的实际问题给出一系列的约束一系列的约束, 称之为称之为“公理公理”. 它是所研究问题的基本要求，或所希望达它是所研究问题的基本要求，或所希望达到的基本目标。
到的基本目标 并据此寻求适当的数学结构来满足这些基并据此寻求适当的数学结构来满足这些基本的要求本的要求 • 如果存在唯一确定的数学结构，如果存在唯一确定的数学结构， 将它表将它表达出来• 如果不可能有一个数学系统与公理体系如果不可能有一个数学系统与公理体系相容，相容，则需要找出虽然违背公理但是可以则需要找出虽然违背公理但是可以接受的模型接受的模型• 如果存在许多模型满足公理的要求，如果存在许多模型满足公理的要求，则则需要寻出其中最优者需要寻出其中最优者 2. 席位公平分配的公理模型席位公平分配的公理模型公理公理I. (份额单调性份额单调性) 一个州人口的增加不会导一个州人口的增加不会导致它失去席位致它失去席位.公理公理II.(无偏性无偏性) 在整个时间上平均在整个时间上平均, 每个州应每个州应得到它自己应分摊的份额得到它自己应分摊的份额.公理公理III.(席位单调性席位单调性) 总席位增加不会导致某个总席位增加不会导致某个州名额减少州名额减少.公理公理IV. (公平分摊性公平分摊性) 任何州的席位数都不会偏任何州的席位数都不会偏离其比例的份额数离其比例的份额数.公理公理V. (接近份额性接近份额性) 没有从一个州到另一个州没有从一个州到另一个州的名额转让会使得这两个州都接近它们应得的名额转让会使得这两个州都接近它们应得的份额的份额. 公理可以分为两类：公理可以分为两类： 避免各种悖论的公理避免各种悖论的公理(I, III)和关于份额和关于份额公平的公理公平的公理(II, IV, V). 这些公理表明这些公理表明: 一个理想的席位分配方案一个理想的席位分配方案不应该产生任何前面所提到的悖论不应该产生任何前面所提到的悖论, 而且还应而且还应该满足关于份额公平的法则该满足关于份额公平的法则. 遗憾的是遗憾的是………..………..1980年年 Balinsky 和和 Young 研究的结果表明研究的结果表明: 不存在既能避免所有席位分配的悖论同时又不存在既能避免所有席位分配的悖论同时又满足份额法则的席位分配的方法满足份额法则的席位分配的方法. 这就是有名的这就是有名的: 席位分配的不可能定理席位分配的不可能定理. M. L. Balinsky & H.P.Young, Fair Representation, Yale Univ. Press, 1982 进一步阅读资料进一步阅读资料…..参考文献参考文献“席位分配问题的数学模型席位分配问题的数学模型”——数学的实践数学的实践与认识，张建勋，与认识，张建勋，2002年年7月，月，P542~548——将公理较合理的用整数规划模型描述，并将公理较合理的用整数规划模型描述，并给出了解法给出了解法！！ 应用练习有有A、、B、、C、、D、、E五个部门，人数分别为下面五个部门，人数分别为下面(1)中所列，现在要选举若干代表，规定每中所列，现在要选举若干代表，规定每100人选一个人选一个代表代表, 共选共选100名代表，问从公平的角度看，每个部名代表，问从公平的角度看，每个部门应该选几个代表？那么各部门人数要是（门应该选几个代表？那么各部门人数要是（2））(3)的情况呢？的情况呢？ABCDE(1)9330169168167166(2)9370159158157156(3)9450139138137136 。
