代表名额的分配.ppt

公平的席位分配1.问题：美国众议院如何根据各州人口的比例分配众议院议员的名额。
m:州数,pi:第i州人口数,p=Σpi:总人口数
N:议员数,ni:第i州议员数,N=Σni.
qi=(pi/p)N:第i州应占有的议员的份额.
根据按人口比例分配的原则给出公平的议员席位分配的方案{n1,…,nm}，即ni尽可能地接近其应得的份额qi.2.背景
1787年美国颁布宪法,规定“众议院议员的名额…将根据各州的人口比例分配”,并于1788年生效.
1791年AlexanderHamilton（财政部长）提出了议员席位分配的方法,并于1792年通过。
1792年ThomasJefferson提出了议员席位分配的除子法。
1851年开始用Hamilton法分配议员的席位。1881年当议会的总席位由299席变为300席时，各州的人口数都没有变化，重新调整议员席位的结果却使Alabama亚拉巴州的议员席位却从8人减少为7人。这就是著名的Alabama悖论
后来，1890年人口普查之后，在各州人口数没有改变的情况下，当总席位由359席增加到360席时，Arkensas州的议员的席位又丢掉了一个。Maine州也出现了类似的情况。
1910年，Hamilton的分配方法被停止使用了。1920年，Harvard大学的数学家EdwardHuntington，JosephHill开始研究这个问题。
1941年，基于代表性不公平度的数学模型，他们提出了EP（EqualProportions）法，用以分配议员的席位。并且由Roosevelt总统将它写入了法律，至今仍然延用。
1970年MichaelBalinsky&PeytonYoung进一步研究，提出公理准则体系。
1980年提出了著名的Balinsky&Young不可能定理。二：Hamilton(比例加惯例)方法Hamilton法（比例加惯例）及有关悖论Hamilton方法的不公平性衡量公平分配的数量指标公平分配方案应使两者之间的不公平度rA(或rB)尽量小Huntington-Hill定理：在席位分配方案（ni,nj）的基础上,再增加一个席位,方案(ni+1,nj)优于(ni,nj+1),当且仅当Qi>Qj,其中1）若p1/(n1+1)>p2/n2，3）若p1/(n1+1)<p2/n2，当rB(n1+1,n2)<rA(n1,n2+1),该席给A（另一种情况同理）实际上此方法我们做了如下假设：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继续.nABC
15304.5(4)1984.5(5)578.0(9)
21768.2(6)661.5(8)192.7(15)
3884.1(7)330.8(12)96.3(21)
4530.5(10)198.5(14)
5353.6(11)132.3(18)
6252.6(13)94.5
7189.4(16)
8147.3(17)
9117.9(19)
1096.4(20)
1180.4
11个6个4个
1.公理化建模:
事先根据具体的实际问题给出一系列的约束,称之为“公理”。它是所研究问题的基本要求，或所希望达到的基本目标。并据此寻求适当的数学结构来满足这些基本的要求。
如果存在唯一确定的数学结构，将它表达出来。
如果不可能有一个数学系统与公理体系相容，则需要找出虽然违背公理但是可以接受的模型。
如果存在许多模型满足公理的要求，则需要寻出其中最优者。2.席位公平分配的公理模型（1974）
公理1.(份额单调性)一个州人口的增加不会导致它失去席位.
公理2.(无偏性)在整个时间上平均,每个州应得到它自己应分摊的份额.
公理3.(名额单调性)总席位增加不会导致某个州名额减少.ni(N,p1,,…pm)ni(N+1,p1,,…pm)
公理4.(公平分配性)任何州的席位数都不会偏离其比例的份额数.[qi]ni[qi]+1(i=1,2,…m)
公理5.(接近份额性)没有从一个州到另一个州的名额转让会使得这两个州都接近它们应得的份额.3：两类公理：
避免各种悖论的公理(I,III)；
关于份额法则的公理(II,IV,V)。
这些公理表明:一个理想的席位分配方案不应该产生任何前面所提到的悖论,而且还应该满足关于份额的法则.
4：席位分配的不可能定理.
1982年Balinsky和Young研究的结果表明:
不存在既能避免所有席位分配的悖论同时又满足份额法则的席位分配的方法。
M.L.Balinsky&H.P.Young,
FairRepresentat