代表名額的分配PPT演示文稿

1、1公平的席位分配公平的席位分配2 1. 問(wèn)題：美國(guó)眾議院如何根據(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.美國(guó)憲法自1788年生效開(kāi)始之日起，其第1條第2款就明確指出：“眾議院議員名額 將根據(jù)各州的人口比例分配。”200年以來(lái)，關(guān)于“公正合理”地實(shí)現(xiàn)憲法中所規(guī)定的分配原則，美國(guó)的政治家和科學(xué)家們展開(kāi)了激烈的爭(zhēng)論，雖然

2、設(shè)計(jì)了多種方案，但沒(méi)有一種得到普遍認(rèn)可 。一. 問(wèn)題與背景32. 背景 1787年美國(guó)頒布憲法,規(guī)定“眾議院議員的名額將根據(jù)各州的人口比例分配”, 并于1788年生效. 1791年 alexander hamilton（財(cái)政部長(zhǎng)） 提出了議員席位分配的方法, 并于1792年通過(guò)。 1792年 thomas jefferson 提出了議員席位分配的除子法。 1851年開(kāi)始用hamilton法分配議員的席位。4 1881年當(dāng)議會(huì)的總席位由299席變?yōu)?00席時(shí)，各州的人口數(shù)都沒(méi)有變化，重新調(diào)整議員席位的結(jié)果卻使alabama亞拉巴州的議員席位卻從 8人減少為 7人。這就是著名的 alabama 悖

3、論 后來(lái)，1890年人口普查之后，在各州人口數(shù)沒(méi)有改變的情況下，當(dāng)總席位由359席增加到360席時(shí)，arkensas 州的議員的席位又丟掉了一個(gè)。maine 州也出現(xiàn)了類似的情況。 1910年，hamilton 的分配方法被停止使用了。5 1920年，harvard 大學(xué)的數(shù)學(xué)家 edward huntington，joseph hill 開(kāi)始研究這個(gè)問(wèn)題。 1941年，基于代表性不公平度的數(shù)學(xué)模型，他們提出了ep（equal proportions）法，用以分配議員的席位。并且由roosevelt 總統(tǒng)將它寫(xiě)入了法律，至今仍然延用。 1970年michael balinsky & peyto

4、n young 進(jìn)一步研究，提出公理準(zhǔn)則體系。 1980 年提出了著名的 balinsky & young 不可能定理。6二：二：hamilton (比例加慣例比例加慣例) 方法方法已知已知: m方人數(shù)分別為方人數(shù)分別為 p1, p2, pm, 記總?cè)藬?shù)為記總?cè)藬?shù)為 p= p1+p2+pm, 待分配的總席位為待分配的總席位為n。記記 qi=npi /p, 稱為第稱為第i方的份額方的份額(i =1,2, m) 各方先分配各方先分配qi的整數(shù)部分的整數(shù)部分qi, 總余額為總余額為miiqnn1 記記ri =qi-qi, 則第則第i方的分配名額方的分配名額ni為為其它個(gè)最大的, 1iiiiqnrqn

5、要要求求已知份額向量已知份額向量q=(q1, , qm), 找一個(gè)找一個(gè)n=(n1, , nm), n= n1+n2+nm，使使n與與q最最。問(wèn)問(wèn)題題7hamilton 法（比例加慣例）及有關(guān)悖論法（比例加慣例）及有關(guān)悖論系別系別 學(xué)生學(xué)生 比例比例 20席的分配席的分配 人數(shù)人數(shù) （%） 比例比例 結(jié)果結(jié)果 甲甲 103 51.5 乙乙 63 31.5 丙丙 34 17.0總和總和 200 100.0 20.0 2021席的分配席的分配 比例比例 結(jié)果結(jié)果10.815 6.615 3.570 21.000 21例例子子三個(gè)系學(xué)生共三個(gè)系學(xué)生共200名名(甲甲100，乙，乙60，丙，丙40)，

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

7、%） 比例比例 結(jié)果結(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é)果結(jié)果10.815 11 6.615 7 3.570 321.000 218hamilton方法的不公平性方法的不公平性1. alabama 悖論：悖論： p1, p2, , pm 不變不變, n 的增加會(huì)使某個(gè)的增加會(huì)使某個(gè) ni 減少減少 （上例）。（上例）。2. 人口悖論：人口悖論： n不變不變, pi 比比pj 的增長(zhǎng)率大的增長(zhǎng)率大, 反使反使 ni 減少減少 nj 增加增加 (

8、例例1) 。3. 新州悖論：新州悖論： p1, p2, pm不變不變, m增加增加1, n 的增加會(huì)使某個(gè)的增加會(huì)使某個(gè)ni增加而某個(gè)增加而某個(gè)ni 減少減少(例例2)。pinii=110310i=2636i=3344總和總和 20020pi114(+10.6%)6338(+11.8%)215qi10.605.863.54 20ni116320pi10363346206qi10.506.423.470.61 21ni1121例例1例例29衡量公平分配的數(shù)量指標(biāo)衡量公平分配的數(shù)量指標(biāo) 人數(shù)人數(shù) 席位席位 a方方 p1 n1b方方 p2 n2當(dāng)當(dāng)p1/n1= p2/n2 時(shí)，分配公平時(shí)，分配公平

9、p1/n1 p2/n2 對(duì)對(duì)a的絕對(duì)不公平度的絕對(duì)不公平度p1=150, n1=10, p1/n1=15p2=100, n2=10, p2/n2=10p1=1050, n1=10, p1/n1=105p2=1000, n2=10, p2/n2=100p1/n1 p2/n2=5但后者對(duì)但后者對(duì)a的不公平的不公平程度已大大降低程度已大大降低! !雖二者的絕對(duì)雖二者的絕對(duì)不公平度相同不公平度相同若若 p1/n1 p2/n2 ，對(duì)，對(duì)a不公平不公平p1/n1 p2/n2=5不公平度和huntington（q值）方法10公平分配方案應(yīng)使兩者公平分配方案應(yīng)使兩者之間的不公平度之間的不公平度ra (或或 r

10、b) 盡量小盡量小),(/21222211nnrnpnpnpa 對(duì)對(duì)a的相對(duì)不公平度的相對(duì)不公平度將絕對(duì)度量改為相對(duì)度量將絕對(duì)度量改為相對(duì)度量類似若類似若p2/n2 p1/n1，定義定義rb(n1,n2)若若 p1/n1 p2/n2 ，定義，定義席位公平分配的huntington法則：若一州轉(zhuǎn)讓一個(gè)席若一州轉(zhuǎn)讓一個(gè)席位給另一州導(dǎo)致兩州間相對(duì)不公平度的降低，則進(jìn)行位給另一州導(dǎo)致兩州間相對(duì)不公平度的降低，則進(jìn)行這種轉(zhuǎn)讓。連續(xù)進(jìn)行這種席位的轉(zhuǎn)讓，直到任意兩州這種轉(zhuǎn)讓。連續(xù)進(jìn)行這種席位的轉(zhuǎn)讓，直到任意兩州間的轉(zhuǎn)讓不可能再降低它們之間的不公平度間的轉(zhuǎn)讓不可能再降低它們之間的不公平度,則可得到則可得到最優(yōu)

11、的席位分配方案最優(yōu)的席位分配方案 。注：在每一個(gè)分配方案后，對(duì)于a，b兩者之間滿足且只滿足下面三種情況之一：兩者分配絕對(duì)公平，此時(shí)兩者之間相對(duì)不公平度為0；對(duì)a不公平，此時(shí)兩者之間相對(duì)不公平度為ra (n1,n2)；對(duì)b不公平，此時(shí)兩者之間相對(duì)不公平度為rb (n1,n2)；11huntington-hill huntington-hill 定理定理：在席位分配方案（ni, nj）的基礎(chǔ)上,再增加一個(gè)席位, 方案(ni+1, nj)優(yōu)于(ni, nj+1),當(dāng)且僅當(dāng) qi qj, 其中minnpqiiii,2,1,)1(2分配策略：分配策略：將一次性的席位分配轉(zhuǎn)化為動(dòng)態(tài)的席位將一次性的席位分配

12、轉(zhuǎn)化為動(dòng)態(tài)的席位分配分配, 即初始分配給即初始分配給a，b各一個(gè)名額，再依次增加分各一個(gè)名額，再依次增加分配配1個(gè)名額，直至名額分配完為止。個(gè)名額，直至名額分配完為止。給出分配的量化指標(biāo)：q值。121）若）若 p1/(n1+1) p2/n2 ， 即使即使a得到該席位仍得到該席位仍對(duì)對(duì)a不公平，給不公平，給a應(yīng)討論以下幾種情況應(yīng)討論以下幾種情況初始初始 p1/n1 p2/n2 2）若）若p1/n1 p2/n2 ，即對(duì)，即對(duì)a不公平不公平.133）若）若 p1/(n1+1) p2/(n2+1)，若若a得到此席位，則對(duì)得到此席位，則對(duì)b不不公平，兩者之間的相對(duì)不公平，兩者之間的相對(duì)不公平度為公平度為

13、rb(n1+1, n2)若若b得到此席位，對(duì)得到此席位，對(duì)a更加更加不公平，兩者之間的相對(duì)不公平，兩者之間的相對(duì)不公平度為不公平度為ra(n1, n2+1)若若rb(n1+1, n2) ra(n1, n2+1), 則這席應(yīng)給則這席應(yīng)給 b應(yīng)比較兩種情況的相對(duì)不公平度應(yīng)比較兩種情況的相對(duì)不公平度rb(n1+1, n2)和和 ra(n1, n2+1) .14當(dāng)當(dāng) rb(n1+1, n2) ra(n1, n2+1), 該席給該席給a（另一種情況（另一種情況同理）同理）ra, rb的定義的定義)1()1(11212222nnpnnp該席給該席給a。, 2 , 1,)1(2innpqiiii 定義定義該

14、席給該席給q值較大的一方值較大的一方推廣到推廣到m方方分配席位分配席位minnpqiiii,2, 1,)1(2計(jì)算計(jì)算該席給該席給q值最大的一方值最大的一方huntington(q 值值)方法方法稱q為huntingtonhill 數(shù)),(/21222211nnrnpnpnpa由于q值只用到了本州自身的參數(shù)，所以可推廣到多州的情況。推導(dǎo)15實(shí)際上此方法我們做了如下假設(shè)：實(shí)際上此方法我們做了如下假設(shè)：1：每一個(gè)州的每一個(gè)人都有選舉權(quán)；：每一個(gè)州的每一個(gè)人都有選舉權(quán)；2：每一個(gè)州至少應(yīng)該分配一個(gè)名額，如果一：每一個(gè)州至少應(yīng)該分配一個(gè)名額，如果一個(gè)州不應(yīng)該分配一個(gè)名額的話，則剔除在分個(gè)州不應(yīng)該分配一

15、個(gè)名額的話，則剔除在分配之外；配之外；3：在分配過(guò)程中，分配是穩(wěn)定的，不受如：在分配過(guò)程中，分配是穩(wěn)定的，不受如何其它因素影響。何其它因素影響。16huntingtonhill 算法算法 1. 令 ni(0 )= 1, 計(jì)算 qi(0), i =1,2,s . 2. 對(duì)于 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 計(jì)算結(jié)束, 否則轉(zhuǎn) 2 繼續(xù) . 17 n a b c 1 5304.5(4) 1984.5(5) 578.0(9) 2 1768.2(6) 661.

16、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個(gè) 6個(gè) 4個(gè)三系用三系用q值方法重新分配值方法重新分配 21個(gè)席位個(gè)席位甲系甲系11席席, 乙系乙系6席席, 丙系丙系4席席q值方法分值方法分配結(jié)果配結(jié)果公平嗎？公平嗎？18 1.公理化建模公理化建模: 事先根據(jù)具體的實(shí)際問(wèn)題給出一系列的約束事先根據(jù)具體的實(shí)際問(wèn)題給出一

17、系列的約束, 稱稱之為之為“公理公理”。它是所研究問(wèn)題的基本要求，或。它是所研究問(wèn)題的基本要求，或所希望達(dá)到的基本目標(biāo)。并據(jù)此尋求適當(dāng)?shù)臄?shù)學(xué)所希望達(dá)到的基本目標(biāo)。并據(jù)此尋求適當(dāng)?shù)臄?shù)學(xué)結(jié)構(gòu)來(lái)滿足這些基本的要求。結(jié)構(gòu)來(lái)滿足這些基本的要求。 如果存在唯一確定的數(shù)學(xué)結(jié)構(gòu)，將它表達(dá)出來(lái)。如果存在唯一確定的數(shù)學(xué)結(jié)構(gòu)，將它表達(dá)出來(lái)。 如果不可能有一個(gè)數(shù)學(xué)系統(tǒng)與公理體系相容，則如果不可能有一個(gè)數(shù)學(xué)系統(tǒng)與公理體系相容，則需要找出雖然違背公理但是可以接受的模型。需要找出雖然違背公理但是可以接受的模型。 如果存在許多模型滿足公理的要求，則需要尋出如果存在許多模型滿足公理的要求，則需要尋出其中最優(yōu)者。其中最優(yōu)者。模型

18、的公理化研究模型的公理化研究19 2.席位公平分配的公理模型（席位公平分配的公理模型（1974） 公理公理 1. (份額單調(diào)性份額單調(diào)性) 一個(gè)州人口的增加不會(huì)導(dǎo)致一個(gè)州人口的增加不會(huì)導(dǎo)致它失去席位它失去席位. 公理公理 2.(無(wú)偏性無(wú)偏性) 在整個(gè)時(shí)間上平均在整個(gè)時(shí)間上平均, 每個(gè)州應(yīng)得到每個(gè)州應(yīng)得到它自己應(yīng)分?jǐn)偟姆蓊~它自己應(yīng)分?jǐn)偟姆蓊~. 公理公理 3.(名額單調(diào)性名額單調(diào)性) 總席位增加不會(huì)導(dǎo)致某個(gè)州總席位增加不會(huì)導(dǎo)致某個(gè)州名額減少名額減少. ni (n, p1, , pm ) ni (n+1, p1, , pm) 公理公理 4. (公平分配性公平分配性) 任何州的席位數(shù)都不會(huì)偏離任何州的

19、席位數(shù)都不會(huì)偏離其比例的份額數(shù)其比例的份額數(shù). qi ni qi+1 (i=1,2, m) 公理公理 5. (接近份額性接近份額性) 沒(méi)有從一個(gè)州到另一個(gè)州的沒(méi)有從一個(gè)州到另一個(gè)州的名額轉(zhuǎn)讓會(huì)使得這兩個(gè)州都接近它們應(yīng)得的份額名額轉(zhuǎn)讓會(huì)使得這兩個(gè)州都接近它們應(yīng)得的份額. 203：兩類公理：兩類公理： 避免各種悖論的公理避免各種悖論的公理(i, iii) ； 關(guān)于份額法則的公理關(guān)于份額法則的公理(ii, iv, v)。 這些公理表明這些公理表明: 一個(gè)理想的席位分配方案不應(yīng)該一個(gè)理想的席位分配方案不應(yīng)該產(chǎn)生任何前面所提到的悖論產(chǎn)生任何前面所提到的悖論, 而且還應(yīng)該滿足關(guān)而且還應(yīng)該滿足關(guān)于份額的法則

20、于份額的法則. 4：席位分配的不可能定理：席位分配的不可能定理. 1982年年 balinsky 和和 young 研究的結(jié)果表明研究的結(jié)果表明: 不存在既能避免所有席位分配的悖論同時(shí)又滿不存在既能避免所有席位分配的悖論同時(shí)又滿足份額法則的席位分配的方法。足份額法則的席位分配的方法。 m. l. balinsky & h.p.young, fair representation, yale univ. press, 1982 “比例加慣例比例加慣例”方法滿足公理方法滿足公理iv，但不滿足公理，但不滿足公理iii.q值方法滿足值方法滿足公理公理iii, , 但不滿足公理但不滿足公理iv .21附

21、錄1： jefferson的除子法 考慮 qi = n 且 qi n 的情形： 選擇適當(dāng)?shù)某?，?jì)算 qi* = qi/， 使得qi* =n。 取 ni = qi*得到分配名額。 除子法的數(shù)學(xué)模型？ “名額分配問(wèn)題”，淑生，自然雜志，2（1993），4650。22n例 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

22、b 63 6.8 6 7.19 7 n c 34 3.4 3 3.88 3悖論悖論123n例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悖論悖論224n 例3. p=1000, s=2, n=4; p=

23、1200, s=3, n=5n 州 pi qi ni pi 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 悖論悖論325n例4. 六個(gè)州分配100個(gè)席位n州 人口p 份額q h法 j法 ep法na 9215 92.15 92 95 90nb 159 1.59 2 1 2nc 158 1.58 2 1 2n

24、d 157 1.57 2 1 2ne 156 1.56 1 1 2nf 155 1.55 1 1 2n 10000 100 100 100 100dhondt方法有k個(gè)單位，每單位的人數(shù)為 pi ，總席位數(shù)為n。做法：用自然數(shù)1,2,3,分別除以每單位的人數(shù)，從所得的數(shù)中由大到小取前 n 個(gè)，（這n個(gè)數(shù)來(lái)自各個(gè)單位人數(shù)用自然數(shù)相除的結(jié)果），這n個(gè)數(shù)中哪個(gè)單位有幾個(gè)所分席位就為幾個(gè)。27思考題：思考題：1：請(qǐng)指出：請(qǐng)指出jefferson方法不會(huì)產(chǎn)生人口悖論和新州方法不會(huì)產(chǎn)生人口悖論和新州悖論。悖論。2：55頁(yè)第頁(yè)第1題。題。3：編程用：編程用q方法計(jì)算書(shū)中的例子。方法計(jì)算書(shū)中的例子。28hamilton 法的數(shù)學(xué)模型 q = (q1,qs)t: 份額向量, 1tq = qi =n n = (n1,ns)t: 分配向量, 1tn = ni =n 它們均位于s維空間的s-1維單形 (s維空間的超平面)中 . 以s = 3 的情形為例：n 10. n, q 是高為 n 的正三角形上的點(diǎn)，該點(diǎn)到三個(gè)邊的距離為它們的坐標(biāo)。n 20. 將三角形各邊n等分，分別以平行各邊的直線連接相應(yīng)的等分點(diǎn)。連線在三角形內(nèi)的交點(diǎn)將是三角形上有整數(shù)坐標(biāo)的格點(diǎn)，這些點(diǎn)構(gòu)成席位分