代表名额的分配-共34页PPT资料课件.ppt

1、公平的席位分配公平的席位分配 1.问题：美国众议院如何根据各州人口的比例分配众议院议员的名额。m:州数,pi:第 i 州人口数,p=pi:总人口数 N:议员数,ni:第 i 州议员数,N=ni.qi=(pi/p)N:第 i 州应占有的议员的份额.根据按人口比例分配的原则给出公平的议员席位分配的方案n1,nm，即ni尽可能地接近其应得的份额qi.美国宪法自1788年生效开始之日起，其第1条第2款就明确指出：“众议院议员名额 将根据各州的人口比例分配。”200年以来，关于“公正合理”地实现宪法中所规定的分配原则，美国的政治家和科学家们展开了激烈的争论，虽然设计了多种方案，但没有一种得到普遍认可。一

2、.问题与背景2.背景 1787年美国颁布宪法,规定“众议院议员的名额将根据各州的人口比例分配”,并于1788年生效.1791年 Alexander Hamilton（财政部长）提出了议员席位分配的方法,并于1792年通过。1792年 Thomas Jefferson 提出了议员席位分配的除子法。1851年开始用Hamilton法分配议员的席位。1881年当议会的总席位由299席变为300席时，各州的人口数都没有变化，重新调整议员席位的结果却使Alabama亚拉巴州的议员席位却从 8人减少为 7人。这就是著名的 Alabama 悖论 后来，1890年人口普查之后，在各州人口数没有改变的情况下，当

3、总席位由359席增加到360席时，Arkensas 州的议员的席位又丢掉了一个。Maine 州也出现了类似的情况。1910年，Hamilton 的分配方法被停止使用了。1920年，Harvard 大学的数学家 Edward Huntington，Joseph Hill 开始研究这个问题。1941年，基于代表性不公平度的数学模型，他们提出了EP（Equal Proportions）法，用以分配议员的席位。并且由Roosevelt 总统将它写入了法律，至今仍然延用。1970年Michael Balinsky&Peyton Young 进一步研究，提出公理准则体系。1980 年提出了著名的 Bali

4、nsky&Young 不可能定理。二：二：Hamilton(比例加惯例比例加惯例)方法方法已知已知:m方人数分别为方人数分别为 p1,p2,pm,记总人数为记总人数为 p=p1+p2+pm,待分配的总席位为待分配的总席位为N。记记 qi=Npi/p,称为第称为第i方的份额方的份额(i=1,2,m)各方先分配各方先分配qi的整数部分的整数部分qi,总余额为总余额为miiqNN1 记记ri=qi-qi,则第则第i方的分配名额方的分配名额ni为为其它个最大的,1iiiiqNrqn要要求求已知份额向量已知份额向量q=(q1,qm),找一个找一个n=(n1,nm),N=n1+n2+nm，使使n与与q最最

5、。问问题题Hamilton 法（比例加惯例）及有关悖论法（比例加惯例）及有关悖论系别系别 学生学生 比例比例 20席的分配席的分配 人数人数 （%）比例比例 结果结果 甲甲 103 51.5 乙乙 63 31.5 丙丙 34 17.0总和总和 200 100.0 20.0 2021席的分配席的分配 比例比例 结果结果10.815 6.615 3.570 21.000 21例例子子三个系学生共三个系学生共200名名(甲甲100，乙，乙60，丙，丙40)，代表会，代表会议共议共20席，按比例分配，三个系分别为席，按比例分配，三个系分别为10,6,4席席.因学生转系因学生转系,三系人数为三系人数为1

6、03,63,34,如何分配如何分配20席席?若代表会议增加若代表会议增加1席，如何分配席，如何分配21席席?比比例例加加惯惯例例对对丙丙系系公公平平吗吗系别系别 学生学生 比例比例 20席的分配席的分配 人数人数 （%）比例比例 结果结果 甲甲 103 51.5 10.3 乙乙 63 31.5 6.3 丙丙 34 17.0 3.4 总和总和 200 100.0 20.0 20系别系别 学生学生 比例比例 20席的分配席的分配 人数人数 （%）比例比例 结果结果 甲甲 103 51.5 10.3 10 乙乙 63 31.5 6.3 6 丙丙 34 17.0 3.4 4总和总和 200 100.0

7、 20.0 2021席的分配席的分配 比例比例 结果结果10.815 11 6.615 7 3.570 321.000 21Hamilton方法的不公平性方法的不公平性1.Alabama 悖论：悖论：p1,p2,pm 不变不变,N 的增加会使某个的增加会使某个 ni 减少减少（上例）。（上例）。2.人口悖论：人口悖论：N不变不变,pi 比比pj 的增长率大的增长率大,反使反使 ni 减少减少 nj 增加增加(例例1)。3.新州悖论：新州悖论：p1,p2,pm不变不变,m增加增加1,N 的增加会使某个的增加会使某个ni增加而某个增加而某个ni 减少减少(例例2)。pinii=110310i=26

8、36i=3344总和总和 20020pi114(+10.6%)6338(+11.8%)215qi10.605.863.54 20ni116320pi10363346206qi10.506.423.470.61 21ni1121例例1例例2衡量公平分配的数量指标衡量公平分配的数量指标 人数人数 席位席位 A方方 p1 n1B方方 p2 n2当当p1/n1=p2/n2 时，分配公平时，分配公平 p1/n1 p2/n2 对对A的绝对不公平度的绝对不公平度p1=150,n1=10,p1/n1=15p2=100,n2=10,p2/n2=10p1=1050,n1=10,p1/n1=105p2=1000,n

9、2=10,p2/n2=100p1/n1 p2/n2=5但后者对但后者对A的不公平的不公平程度已大大降低程度已大大降低!虽二者的绝对虽二者的绝对不公平度相同不公平度相同若若 p1/n1 p2/n2，对，对A不公平不公平p1/n1 p2/n2=5不公平度和Huntington（Q值）方法公平分配方案应使两者公平分配方案应使两者之间的不公平度之间的不公平度rA(或或 rB)尽量小尽量小),(/21222211nnrnpnpnpA 对对A的相对不公平度的相对不公平度将绝对度量改为相对度量将绝对度量改为相对度量类似若类似若p2/n2 p1/n1，定义定义rB(n1,n2)若若 p1/n1 p2/n2，定

10、义，定义席位公平分配的Huntington法则：若一州转让一个席若一州转让一个席位给另一州导致两州间相对不公平度的降低，则进行位给另一州导致两州间相对不公平度的降低，则进行这种转让。连续进行这种席位的转让，直到任意两州这种转让。连续进行这种席位的转让，直到任意两州间的转让不可能再降低它们之间的不公平度间的转让不可能再降低它们之间的不公平度,则可得到则可得到最优的席位分配方案最优的席位分配方案。注：在每一个分配方案后，对于A，B两者之间满足且只满足下面三种情况之一：两者分配绝对公平，此时两者之间相对不公平度为0；对A不公平，此时两者之间相对不公平度为rA(n1,n2)；对B不公平，此时两者之间相

11、对不公平度为rB(n1,n2)；Huntington-Hill Huntington-Hill 定理定理：在席位分配方案（ni,nj）的基础上,再增加一个席位,方案(ni+1,nj)优于(ni,nj+1),当且仅当 Qi Qj,其中minnpQiiii,2,1,)1(2分配策略：分配策略：将一次性的席位分配转化为动态的席位将一次性的席位分配转化为动态的席位分配分配,即初始分配给即初始分配给A，B各一个名额，再依次增加分各一个名额，再依次增加分配配1个名额，直至名额分配完为止。个名额，直至名额分配完为止。给出分配的量化指标：Q值。1）若）若 p1/(n1+1)p2/n2，即使即使A得到该席位仍得

12、到该席位仍对对A不公平，给不公平，给A应讨论以下几种情况应讨论以下几种情况初始初始 p1/n1 p2/n2 2）若）若p1/n1 p2/n2，即对，即对A不公平不公平.3）若）若 p1/(n1+1)p2/(n2+1)，若若A得到此席位，则对得到此席位，则对B不不公平，两者之间的相对不公平，两者之间的相对不公平度为公平度为rB(n1+1,n2)若若B得到此席位，对得到此席位，对A更加更加不公平，两者之间的相对不公平，两者之间的相对不公平度为不公平度为rA(n1,n2+1)若若rB(n1+1,n2)rA(n1,n2+1),则这席应给则这席应给 B应比较两种情况的相对不公平度应比较两种情况的相对不公

13、平度rB(n1+1,n2)和和 rA(n1,n2+1).当当 rB(n1+1,n2)rA(n1,n2+1),该席给该席给A（另一种情况（另一种情况同理）同理）rA,rB的定义的定义)1()1(11212222nnpnnp该席给该席给A。,2,1,)1(2innpQiiii 定义定义该席给该席给Q值较大的一方值较大的一方推广到推广到m方方分配席位分配席位minnpQiiii,2,1,)1(2计算计算该席给该席给Q值最大的一方值最大的一方Huntington(Q 值值)方法方法称Q为HuntingtonHill 数),(/21222211nnrnpnpnpA由于Q值只用到了本州自身的参数，所以可推

14、广到多州的情况。推导实际上此方法我们做了如下假设：实际上此方法我们做了如下假设：1：每一个州的每一个人都有选举权；：每一个州的每一个人都有选举权；2：每一个州至少应该分配一个名额，如果一：每一个州至少应该分配一个名额，如果一个州不应该分配一个名额的话，则剔除在分个州不应该分配一个名额的话，则剔除在分配之外；配之外；3：在分配过程中，分配是稳定的，不受如：在分配过程中，分配是稳定的，不受如何其它因素影响。何其它因素影响。HuntingtonHill 算法算法 1.令 ni(0)=1,计算 Qi(0),i=1,2,s.2.对于 k=1,2,取 Qh(k)=max Qi(k-1)3.令 nh(k)=

15、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个三系用三系用Q值方法重新分配值方法重新分配 21个席位个席位甲系甲系11席席,乙

16、系乙系6席席,丙系丙系4席席Q值方法分值方法分配结果配结果公平吗？公平吗？1.公理化建模公理化建模:事先根据具体的实际问题给出一系列的约束事先根据具体的实际问题给出一系列的约束,称称之为之为“公理公理”。它是所研究问题的基本要求，或。它是所研究问题的基本要求，或所希望达到的基本目标。并据此寻求适当的数学所希望达到的基本目标。并据此寻求适当的数学结构来满足这些基本的要求。结构来满足这些基本的要求。如果存在唯一确定的数学结构，将它表达出来。如果存在唯一确定的数学结构，将它表达出来。如果不可能有一个数学系统与公理体系相容，则如果不可能有一个数学系统与公理体系相容，则需要找出虽然违背公理但是可以接受的

17、模型。需要找出虽然违背公理但是可以接受的模型。如果存在许多模型满足公理的要求，则需要寻出如果存在许多模型满足公理的要求，则需要寻出其中最优者。其中最优者。模型的公理化研究模型的公理化研究 2.席位公平分配的公理模型（席位公平分配的公理模型（1974）公理公理 1.(份额单调性份额单调性)一个州人口的增加不会导致一个州人口的增加不会导致它失去席位它失去席位.公理公理 2.(无偏性无偏性)在整个时间上平均在整个时间上平均,每个州应得到每个州应得到它自己应分摊的份额它自己应分摊的份额.公理公理 3.(名额单调性名额单调性)总席位增加不会导致某个州总席位增加不会导致某个州名额减少名额减少.ni(N,p

18、1,pm)ni(N+1,p1,pm)公理公理 4.(公平分配性公平分配性)任何州的席位数都不会偏离任何州的席位数都不会偏离其比例的份额数其比例的份额数.qi ni qi+1 (i=1,2,m)公理公理 5.(接近份额性接近份额性)没有从一个州到另一个州的没有从一个州到另一个州的名额转让会使得这两个州都接近它们应得的份额名额转让会使得这两个州都接近它们应得的份额.3：两类公理：两类公理：避免各种悖论的公理避免各种悖论的公理(I,III)；关于份额法则的公理关于份额法则的公理(II,IV,V)。这些公理表明这些公理表明:一个理想的席位分配方案不应该一个理想的席位分配方案不应该产生任何前面所提到的悖

19、论产生任何前面所提到的悖论,而且还应该满足关而且还应该满足关于份额的法则于份额的法则.4：席位分配的不可能定理：席位分配的不可能定理.1982年年 Balinsky 和和 Young 研究的结果表明研究的结果表明:不存在既能避免所有席位分配的悖论同时又满不存在既能避免所有席位分配的悖论同时又满足份额法则的席位分配的方法。足份额法则的席位分配的方法。M.L.Balinsky&H.P.Young,Fair Representation,Yale Univ.Press,1982“比例加惯例比例加惯例”方法满足公理方法满足公理IV，但不满足公理，但不满足公理III.Q值方法满足值方法满足公理公理III

20、,但不满足公理但不满足公理IV.附录1：Jefferson的除子法 考虑 qi=N 且 qi N 的情形：选择适当的除子，计算 qi*=qi/，使得qi*=N。取 ni=qi*得到分配名额。除子法的数学模型？“名额分配问题”，淑生，自然杂志，2（1993），4650。n例 1.P=200,s=3,N=20,N=21n 州 pi qi ni qi nin A 103 10.3 10 10.815 11n B 63 6.3 6 6.615 7n C 34 3.4 4 3.570 3n =0.92 qi*ni qi*ni n A 103 11.2 11 11.75 11 n B 63 6.8 6 7

21、.19 7 n C 34 3.4 3 3.88 3悖论悖论1n例2.P=1000,s=3,N=3n 州 pi qi ni pi qi ni n A 420 1.260 1 430 1.17 1n B 455 1.365 1 520 1.42 2n C 125 0.375 1 150 0.41 0n =0.65 qi*ni pi qi*ni n A 420 1.93 1 430 1.80 1n B 455 2.10 2 520 2.18 2n C 125 0.57 0 150 0.63 0悖论悖论2n 例3.p=1000,s=2,N=4;p=1200,s=3,N=5n 州 pi qi ni pi

22、 qi ni A 623 2.492 2 A 623 2.595 3n B 377 1.508 2 B 377 1.570 1 n C 200 0.835 1n=0.80 qi ni pi qi ni nA 623 3.12 3 A 623 3.24 3 nB 377 1.88 1 B 377 1.96 1n C 200 1.04 1 悖论悖论3n例4.六个州分配100个席位n州 人口p 份额q H法 J法 EP法nA 9215 92.15 92 95 90nB 159 1.59 2 1 2nC 158 1.58 2 1 2nD 157 1.57 2 1 2nE 156 1.56 1 1 2n

23、F 155 1.55 1 1 2n 10000 100 100 100 100dHondt方法有k个单位，每单位的人数为 pi，总席位数为n。做法：用自然数1,2,3,分别除以每单位的人数，从所得的数中由大到小取前 n 个，（这n个数来自各个单位人数用自然数相除的结果），这n个数中哪个单位有几个所分席位就为几个。思考题：思考题：1：请指出：请指出Jefferson方法不会产生人口悖论和新州方法不会产生人口悖论和新州悖论。悖论。2：55页第页第1题。题。3：编程用：编程用Q方法计算书中的例子。方法计算书中的例子。Hamilton 法的数学模型 q=(q1,qs)T:份额向量,1Tq=qi=N n

24、=(n1,ns)T:分配向量,1Tn=ni=N 它们均位于s维空间的s-1维单形(s维空间的超平面)中.以s=3 的情形为例：n 10.n,q 是高为 N 的正三角形上的点，该点到三个边的距离为它们的坐标。n 20.将三角形各边N等分，分别以平行各边的直线连接相应的等分点。连线在三角形内的交点将是三角形上有整数坐标的格点，这些点构成席位分配向量的集合n。n 30.连线将三角形分为若干小三角形。份额向量q为三角形上任意一点。该点到它所在的小三角形三个边的距离分别为三个坐标的小数部分。n 40.按照最大小数部分增加一个席位的H法相当于在 q 所在的小三角形中选择最靠近 q 点的顶点（格点 n）为席

25、位分配方案。n 50.Hamilton 分配域：作小三角形内心，则可以构成以 n 为心，以上述若干内心为顶点的正六边形。如果 q 落入某个小六边形内，则选择该六边形的中心 n 为席位的分配方案。模型的图例分析 三系用三系用Q值方法重新分配值方法重新分配 21个席位（方法个席位（方法2）按人数比例的整数部分已将按人数比例的整数部分已将19席分配完毕席分配完毕甲系：甲系：p1=103,n1=10乙系：乙系：p2=63,n2=6丙系：丙系：p3=34,n3=3用用Q值方法分配值方法分配第第20席和第席和第21席席第第20席席3.964334,5.947663,4.961110103232221QQQ

26、第第21席席3221,4.801211103QQQ同上同上Q3最大，第最大，第21席给丙系席给丙系甲系甲系11席席,乙系乙系6席席,丙系丙系4席席Q值方法分值方法分配结果配结果公平吗？公平吗？Q1最大，第最大，第20席给甲系席给甲系公平的席位分配公平的席位分配 建立建立“公平分配席位公平分配席位”模型的关键是建立衡量公模型的关键是建立衡量公平程度的平程度的数量指标数量指标.在以相对不公平度为衡量指标的前提下在以相对不公平度为衡量指标的前提下,Q值方法值方法比比“比例加惯例比例加惯例”方法更加公平方法更加公平.如果采用如果采用公理化方法公理化方法提出公平分配席位的提出公平分配席位的理想化原则，那么该问题尚未解决理想化原则，那么该问题尚未解决已证明不已证明不存在满足一组公理的席位分配方法存在满足一组公理的席位分配方法.谢谢！