代表名額的分配-共34頁PPT資料課件

1、公平的席位分配 1. 問題：美國眾議院如何根據(jù)各州人口的比例分配眾議院議員的名額。 m: 州數(shù), pi: 第 i 州人口數(shù), p = pi: 總?cè)丝跀?shù) N: 議員數(shù), ni: 第 i 州議員數(shù), N=ni. qi=(pi/p)N: 第 i 州應(yīng)占有的議員的份額. 根據(jù)按人口比例分配的原則給出公平的議員席位分配的方案n1, , nm，即ni盡可能地接近其應(yīng)得的份額qi.美國憲法自1788年生效開始之日起，其第1條第2款就明確指出：“眾議院議員名額 將根據(jù)各州的人口比例分配?！?00年以來，關(guān)于“公正合理”地實現(xiàn)憲法中所規(guī)定的分配原則，美國的政治家和科學(xué)家們展開了激烈的爭論，雖然設(shè)計了多種方案，但

2、沒有一種得到普遍認(rèn)可 。一. 問題與背景2. 背景 1787年美國頒布憲法,規(guī)定“眾議院議員的名額將根據(jù)各州的人口比例分配”, 并于1788年生效. 1791年 Alexander Hamilton（財政部長） 提出了議員席位分配的方法, 并于1792年通過。 1792年 Thomas Jefferson 提出了議員席位分配的除子法。 1851年開始用Hamilton法分配議員的席位。 1881年當(dāng)議會的總席位由299席變?yōu)?00席時，各州的人口數(shù)都沒有變化，重新調(diào)整議員席位的結(jié)果卻使Alabama亞拉巴州的議員席位卻從 8人減少為 7人。這就是著名的 Alabama 悖論 后來，1890年人

3、口普查之后，在各州人口數(shù)沒有改變的情況下，當(dāng)總席位由359席增加到360席時，Arkensas 州的議員的席位又丟掉了一個。Maine 州也出現(xiàn)了類似的情況。 1910年，Hamilton 的分配方法被停止使用了。 1920年，Harvard 大學(xué)的數(shù)學(xué)家 Edward Huntington，Joseph Hill 開始研究這個問題。 1941年，基于代表性不公平度的數(shù)學(xué)模型，他們提出了EP（Equal Proportions）法，用以分配議員的席位。并且由Roosevelt 總統(tǒng)將它寫入了法律，至今仍然延用。 1970年Michael Balinsky & Peyton Young 進(jìn)一步研

4、究，提出公理準(zhǔn)則體系。 1980 年提出了著名的 Balinsky & Young 不可能定理。二：Hamilton (比例加慣例) 方法已知: m方人數(shù)分別為 p1, p2, pm, 記總?cè)藬?shù)為 p= p1+p2+pm, 待分配的總席位為N。記 qi=Npi /p, 稱為第i方的份額(i =1,2, m) 各方先分配qi的整數(shù)部分qi, 總余額為 記ri =qi-qi, 則第i方的分配名額ni為要求已知份額向量q=(q1, , qm), 找一個整數(shù)分配向量n=(n1, , nm), N= n1+n2+nm，使n與q最接近。問題Hamilton 法（比例加慣例）及有關(guān)悖論系別 學(xué)生 比例 20

5、席的分配 人數(shù) （%） 比例 結(jié)果 甲 103 51.5 乙 63 31.5 丙 34 17.0總和 200 100.0 20.0 2021席的分配 比例 結(jié)果10.815 6.615 3.570 21.000 21例子三個系學(xué)生共200名(甲100，乙60，丙40)，代表會議共20席，按比例分配，三個系分別為10, 6, 4席.因?qū)W生轉(zhuǎn)系, 三系人數(shù)為103, 63, 34, 如何分配20席?若代表會議增加1席，如何分配21席?比例加慣例對丙系公平嗎系別 學(xué)生 比例 20席的分配 人數(shù) （%） 比例 結(jié)果 甲 103 51.5 10.3 乙 63 31.5 6.3 丙 34 17.0 3.4

6、 總和 200 100.0 20.0 20系別 學(xué)生 比例 20席的分配 人數(shù) （%） 比例 結(jié)果 甲 103 51.5 10.3 10 乙 63 31.5 6.3 6 丙 34 17.0 3.4 4總和 200 100.0 20.0 2021席的分配 比例 結(jié)果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,

7、pm不變, m增加1, N 的增加會使某個ni增加而某個ni 減少(例2)。pinii=110310i=2636i=3344總和20020pi114(+10.6%)6338(+11.8%)215qi10.605.863.54 20ni116320pi10363346206qi10.506.423.470.61 21ni1163121例1例2衡量公平分配的數(shù)量指標(biāo) 人數(shù) 席位 A方 p1 n1B方 p2 n2當(dāng)p1/n1= p2/n2 時，分配公平 p1/n1 p2/n2 對A的絕對不公平度p1=150, n1=10, p1/n1=15p2=100, n2=10, p2/n2=10p1=1050

8、, n1=10, p1/n1=105p2=1000, n2=10, p2/n2=100p1/n1 p2/n2=5但后者對A的不公平程度已大大降低!雖二者的絕對不公平度相同若 p1/n1 p2/n2 ，對A不公平p1/n1 p2/n2=5不公平度和Huntington（Q值）方法公平分配方案應(yīng)使兩者之間的不公平度rA (或 rB) 盡量小 對A的相對不公平度將絕對度量改為相對度量類似若p2/n2 p1/n1，定義rB(n1,n2)若 p1/n1 p2/n2 ，定義席位公平分配的Huntington法則：若一州轉(zhuǎn)讓一個席位給另一州導(dǎo)致兩州間相對不公平度的降低，則進(jìn)行這種轉(zhuǎn)讓。連續(xù)進(jìn)行這種席位的轉(zhuǎn)讓

9、，直到任意兩州間的轉(zhuǎn)讓不可能再降低它們之間的不公平度,則可得到最優(yōu)的席位分配方案 。注：在每一個分配方案后，對于A，B兩者之間滿足且只滿足下面三種情況之一：兩者分配絕對公平，此時兩者之間相對不公平度為0；對A不公平，此時兩者之間相對不公平度為rA (n1,n2)；對B不公平，此時兩者之間相對不公平度為rB (n1,n2)；Huntington-Hill 定理：在席位分配方案（ni, nj）的基礎(chǔ)上,再增加一個席位, 方案(ni+1, nj)優(yōu)于(ni, nj+1),當(dāng)且僅當(dāng) Qi Qj, 其中分配策略：將一次性的席位分配轉(zhuǎn)化為動態(tài)的席位分配, 即初始分配給A，B各一個名額，再依次增加分配1個名

10、額，直至名額分配完為止。給出分配的量化指標(biāo)：Q值。1）若 p1/(n1+1) p2/n2 ，即使A得到該席位仍對A不公平，給A應(yīng)討論以下幾種情況初始 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), 則這席應(yīng)給 B應(yīng)比較兩種情況的相對不公平度rB(n1+1, n2)和 rA(n1, n2+1) .當(dāng) rB(n1+1,

11、 n2) rA(n1, n2+1), 該席給A（另一種情況同理）rA, rB的定義該席給A。 定義該席給Q值較大的一方推廣到m方分配席位計算該席給Q值最大的一方Huntington(Q 值)方法稱Q為HuntingtonHill 數(shù)由于Q值只用到了本州自身的參數(shù)，所以可推廣到多州的情況。推導(dǎo)實際上此方法我們做了如下假設(shè)：1：每一個州的每一個人都有選舉權(quán)；2：每一個州至少應(yīng)該分配一個名額，如果一個州不應(yīng)該分配一個名額的話，則剔除在分配之外；3：在分配過程中，分配是穩(wěn)定的，不受如何其它因素影響。HuntingtonHill 算法 1. 令 ni(0 )= 1, 計算 Qi(0), i =1,2,s

12、 . 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 計算結(jié)束, 否則轉(zhuǎn) 2 繼續(xù) . 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

13、 117.9(19) 10 96.4(20) 11 80.4 11個 6個 4個三系用Q值方法重新分配 21個席位甲系11席, 乙系6席, 丙系4席Q值方法分配結(jié)果公平嗎？ 1.公理化建模: 事先根據(jù)具體的實際問題給出一系列的約束, 稱之為“公理”。它是所研究問題的基本要求，或所希望達(dá)到的基本目標(biāo)。并據(jù)此尋求適當(dāng)?shù)臄?shù)學(xué)結(jié)構(gòu)來滿足這些基本的要求。 如果存在唯一確定的數(shù)學(xué)結(jié)構(gòu)，將它表達(dá)出來。 如果不可能有一個數(shù)學(xué)系統(tǒng)與公理體系相容，則需要找出雖然違背公理但是可以接受的模型。 如果存在許多模型滿足公理的要求，則需要尋出其中最優(yōu)者。模型的公理化研究 2.席位公平分配的公理模型（1974） 公理 1.

14、(份額單調(diào)性) 一個州人口的增加不會導(dǎo)致它失去席位. 公理 2.(無偏性) 在整個時間上平均, 每個州應(yīng)得到它自己應(yīng)分?jǐn)偟姆蓊~. 公理 3.(名額單調(diào)性) 總席位增加不會導(dǎo)致某個州名額減少. ni (N, p1, , pm ) ni (N+1, p1, , pm) 公理 4. (公平分配性) 任何州的席位數(shù)都不會偏離其比例的份額數(shù). qi ni qi+1 (i=1,2, m) 公理 5. (接近份額性) 沒有從一個州到另一個州的名額轉(zhuǎn)讓會使得這兩個州都接近它們應(yīng)得的份額. 3：兩類公理： 避免各種悖論的公理(I, III) ； 關(guān)于份額法則的公理(II, IV, V)。 這些公理表明: 一個理

15、想的席位分配方案不應(yīng)該產(chǎn)生任何前面所提到的悖論, 而且還應(yīng)該滿足關(guān)于份額的法則. 4：席位分配的不可能定理. 1982年 Balinsky 和 Young 研究的結(jié)果表明: 不存在既能避免所有席位分配的悖論同時又滿足份額法則的席位分配的方法。 M. L. Balinsky & H.P.Young, Fair Representation, Yale Univ. Press, 1982 “比例加慣例”方法滿足公理IV，但不滿足公理III.Q值方法滿足公理III, 但不滿足公理IV .附錄1： Jefferson的除子法 考慮 qi = N 且 qi N 的情形： 選擇適當(dāng)?shù)某?，計?qi* =

16、 qi/， 使得qi* =N。 取 ni = qi*得到分配名額。 除子法的數(shù)學(xué)模型？ “名額分配問題”，淑生，自然雜志，2（1993），4650。例 1 . P = 200, s = 3, N = 20, N=21 州 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悖論1例2 . P=1000, s=3, N=3 州 pi qi

17、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悖論2 例3. 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

18、 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 悖論3例4. 六個州分配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 100dHondt方法有k個單位，每單位的人數(shù)為 pi ，總席位數(shù)為n。做法：用自

19、然數(shù)1,2,3,分別除以每單位的人數(shù)，從所得的數(shù)中由大到小取前 n 個，（這n個數(shù)來自各個單位人數(shù)用自然數(shù)相除的結(jié)果），這n個數(shù)中哪個單位有幾個所分席位就為幾個。思考題：1：請指出Jefferson方法不會產(chǎn)生人口悖論和新州悖論。2：55頁第1題。3：編程用Q方法計算書中的例子。Hamilton 法的數(shù)學(xué)模型 q = (q1,qs)T: 份額向量, 1Tq = qi =N n = (n1,ns)T: 分配向量, 1Tn = ni =N 它們均位于s維空間的s-1維單形 (s維空間的超平面)中 . 以s = 3 的情形為例： 10. n, q 是高為 N 的正三角形上的點，該點到三個邊的距離為它們的坐標(biāo)。 20. 將三角形各邊N等分，分別以平行各邊的直線連接相