公平的席位分配

席位公平分配問題一Q值法的改進(jìn)摘要：本文為建立席位分配問題的公平合理方案.對(duì)經(jīng)典Q值法進(jìn)行了研究并提出改進(jìn)，構(gòu)造了衡量相對(duì)不公平程度的新標(biāo)準(zhǔn)量。通過對(duì)書本中的經(jīng)典席位分配問題實(shí)例的計(jì)算，比較分析了多種席位分配方法的求解結(jié)果，并與經(jīng)典的Q值法進(jìn)行了公平性的比較。結(jié)果表明改進(jìn)的標(biāo)準(zhǔn)量更為合理，從而驗(yàn)證了該方法的有效性和合理性。一、問題背景席位分配問題是人類社會(huì)生活中相當(dāng)普遍的一類資源分配問題，是數(shù)學(xué)在政治領(lǐng)域中應(yīng)用的典型實(shí)例，其目標(biāo)是在一個(gè)大集體對(duì)小集體進(jìn)行某種資源分配時(shí)試圖盡可能做到公平合理。席位分配問題最關(guān)鍵之處是它的悖論觀，無論選擇怎樣的分配方案，總會(huì)產(chǎn)生這樣或那樣的矛盾，著名的有以下幾種悖論：亞拉巴馬悖論、人口悖論和新州悖論。同時(shí)，席位公平分配的關(guān)鍵是提出衡量公平度的一個(gè)量，即滿足下述5條公理：公理1（人口單調(diào)性）：一方的人口增加不會(huì)導(dǎo)致它失去一個(gè)名額。公理2（無偏性）：在整個(gè)時(shí)間平均，每一方應(yīng)接受到它自己應(yīng)分?jǐn)偟姆蓊~。公理3（名額單調(diào)性）：總名額的增加不會(huì)使某一方的名額減少。公理4（公平分?jǐn)傂裕喝魏我环降拿~都不會(huì)偏離其比例份額數(shù)。公理5（接近份額性）：沒有從一方到另一方的名額轉(zhuǎn)讓會(huì)使得這兩方都接近于它們應(yīng)得的份額。然而，1982年M.L.Balinski和H.P.Young證明了一個(gè)B—Y不可能定理，即絕對(duì)公平的分配（滿足公理1?公理5）方案是不存在的，既然絕對(duì)公平的分配方案不存在，人們便致力于席位分配問題的相對(duì)公平的研究。著名的Q值法是1982年由D.N.Burghes和I.Hunttey等人提出的一種相對(duì)不公平衡量標(biāo)準(zhǔn)，該方法簡(jiǎn)單易行，且克服了其他方法的一些矛盾，被廣泛的應(yīng)用于資源公平分配問題中。但不足之處是未考慮名額分配后的整體狀況，而首先給每一方分配一個(gè)名額也是沒有道理的。基于此考慮，這里提出了一種新的衡量相對(duì)不公平的標(biāo)準(zhǔn)，不需要事先給每一方分配一個(gè)名額，其計(jì)算量與Q值法相當(dāng)，但比Q值法更趨于公平。通過實(shí)例比較了該方法與Q值法及其它方法的求解結(jié)果，從而驗(yàn)證該方法的合理性和有效性。二公平標(biāo)準(zhǔn)的構(gòu)造1.1席位分配問題描述席位分配問題是指:假設(shè)有m方參加N個(gè)可供分配的席位，Wp=%p.其中第i方的人數(shù)為七（i=1，2,…，m），m方的總?cè)藬?shù)為 i=1\n.第i方所分配的席位為I，（i=1，2，…，m），如何尋找一組整數(shù)"1,n2,......,"m，使得if' 并且“盡可能”地公平。理想的最公平分配方案是按人數(shù)比例的分配，即第i方應(yīng)分配的“份額”是〃「=S"。但節(jié)N往往不是整數(shù)，而用“四舍五入”或取整的方法導(dǎo)致更不公平，由此提出了經(jīng)典的Q值法。1.2Q值法利用Q值法導(dǎo)出一個(gè)席位分配的標(biāo)準(zhǔn)量Qi，Q尸潟刁=1⑵“5），根據(jù)％值的大小確定下一個(gè)席位應(yīng)分配給那一方，具體操作如下：首先給每一方分配一個(gè)席位，計(jì)算Qi（（=1，2,…，m）值，Q值較大的一方優(yōu)先獲得下一個(gè)席位。然后再計(jì)算Qi值，Q值較大的一方優(yōu)先再獲取一個(gè)席位，如此反復(fù)，直到所有席位分配完為止。由于ni和"?+1分別是不給i方增加一席和給i方增加一席時(shí)該方席位代表的人數(shù)，而Q值法恰是這兩個(gè)數(shù)的幾何平均值的平方，并且從算法描述可看出，可供分配的席位數(shù)N必須能保證每一方至少能分配到一個(gè)席位，而沒有考慮是否應(yīng)該給某一方這個(gè)席位（可能出現(xiàn)該方根本不產(chǎn)生代表），因此Q值法具有一定的局限性。1.3新的衡量標(biāo)準(zhǔn)Cp2Q=zQ值法的定義式'七（氣+1）所示的相對(duì)不公平值只反映了i方本身增加或不增加一席的綜合情況，并沒有把i方放到所有各方構(gòu)成的整體中去考慮，也沒有反應(yīng)相對(duì)于本方每席位代表和人數(shù)的比例關(guān)系與另外一方每席位代表和人數(shù)的比例是否一致或相接近，因此Q值法尚需進(jìn)一步改進(jìn)。定義設(shè)有m方共P人參與總席位為N的席位分配，第i方的人數(shù)為Pi（（=I，2，…，m），第i方所分q=（P,Np-ny配的席位為Ui（i=1，2,…，m），稱'Pi，'=1，2,…，m為第i方的Q值（改進(jìn)的Q值）。LlN新標(biāo)準(zhǔn)量的分子表明第i方應(yīng)分配的份額p與實(shí)際分配n 1pLN_n的席位ni的接近程度，如果p 1為零，則分配是完全公平的。p±N_nQi的值表示相對(duì)于本方總?cè)藬?shù)而言的不公平程度，若p1pMjN_n與p J接近，而第j方比第i方人數(shù)多很多，則對(duì)第i方分配ni個(gè)席位相對(duì)于第j方分配nj個(gè)席位而言，i方感到不公平。Q因此i的值越大，偏離理想狀態(tài)越遠(yuǎn)，越不公平。1.4改進(jìn)的Q值法根據(jù)前面的討論，改進(jìn)的Q值法計(jì)算如下:Step1初始化：每一方分配席位為零，即n(0)=0i(i=1，2，…，m，)，k=0；先n(k)=NStep2終止判斷：若i=1i ，即席位已分配完，結(jié)束;否則轉(zhuǎn)Step3；Q=(P.Np-nj2PStep3計(jì)算 ”i 的值，i=1，2，…，m；Step4比較Qi(i一12，…,，m)的大小，對(duì)Q較大的一方s-maxQi n(k+1)=n(k)+1增加一個(gè)席位，即令 15S ss，Step5k=k+1，轉(zhuǎn)Step2。改進(jìn)的Q值法克服了Q值法首先給每一方分配一席位的不合理規(guī)定，并且考慮了每一方每席位所代表的人數(shù)，每席位代表人數(shù)多的越不公平，所以優(yōu)先得到一個(gè)席位。三應(yīng)用實(shí)例為了驗(yàn)證改進(jìn)的Q值法的合理性和有效性，選擇書中的典型例子，并與經(jīng)典Q值法的計(jì)算過程及相關(guān)文獻(xiàn)中計(jì)算結(jié)果進(jìn)行了比較。書中所給的例子，假設(shè)說，有一個(gè)學(xué)校要召集開一個(gè)代表會(huì)議，席位只有20個(gè)，三個(gè)系總共200人，分別是甲系100，乙系60,丙系40.如果你是會(huì)議的策劃人，你要合理的分配會(huì)議廳的20個(gè)座位，既要保證每個(gè)系部都有人參加，最關(guān)鍵的就是要對(duì)個(gè)公平都公平，保證三個(gè)系部對(duì)你所安排的位置沒有異議。那么這個(gè)問題就要靠數(shù)學(xué)建模的方法來解決。公平而又簡(jiǎn)單的席位分配方法是按學(xué)生人數(shù)的比例分配，顯然甲乙丙三系分別應(yīng)占有10、6、4個(gè)座位?，F(xiàn)在丙系有6名學(xué)生轉(zhuǎn)入甲乙兩系，各系人數(shù)如表1表2第2列所示，仍按比例（原表1第3行）分配席位時(shí)出現(xiàn)了小數(shù)（原表1第4行）。在將取得整數(shù)的19席分配完畢后，三系同意參照所謂慣例分給比例中小數(shù)最大的丙系，于是三系仍分割占有10、6、4個(gè)席（原表1第5行）系名甲乙丙總數(shù)學(xué)生數(shù)1036334200學(xué)生數(shù)103/20063/20034/200100按比例分配席位10.36.33.420按慣例席位分配106420原表1:按照比例并參照分配慣例的席位分配但后來會(huì)議決定下一屆增加1席，她們按照上述辦法重新分配席位，計(jì)算結(jié)果見原表2，顯然這個(gè)結(jié)果對(duì)丙系太不公平了，因?yàn)榭傁辉黾?席，而丙系卻由4席減為3席：系名甲乙丙總數(shù)學(xué)生數(shù)1036334200學(xué)生人數(shù)比例103/20063/20034/200100按比例分配席位10.8156.6153.5721按慣例席位分配117321原表2：增加1席后按照比例并參照慣例的席位分配在這里，我們用Q值法來計(jì)算。其中，m=3,N=21，p=200，曠103，%=63，P,=3七利用改進(jìn)q值法，在Maw.0下編程，計(jì)算結(jié)果見表1。Q值法首先給每個(gè)系分配一個(gè)席位，計(jì)算結(jié)果見表2。從具體操作來看，Q值法是在首先給各系分配一個(gè)席位后，從第4個(gè)席位開始分配的，而改進(jìn)的Q值法無需這一不合理規(guī)定，直接從第1個(gè)席位開始，兩種方法的結(jié)果是一致的。

表1改匱。值法的分配結(jié)果n甲系乙系丙系1,1356(1)0,6946(4)0.3748(8)20.9353(2)。5004(6)0.1943(13)3Q.7544(3)C,33S1(9)0,0725(17)4@5930(5)0-2074(12)0.0096(20)50.4509(7)0.1085(15)0-00546。?3253(10)0,0414(18)70*2251(11)0.00508。，1413(14)90/769(16)100.032009)110.0064(21)S共11席共6席共1席括號(hào)內(nèi)的數(shù)字/表示第』個(gè)席位分配翳它所在的列的那個(gè)系表20值法的分配結(jié)果71甲系乙系丙系15304.4(4)1934.5<5)578(9)2176&2(6)66L5。）122-7(15)3884.1(7)330,8<12)96.3(21)4530*5(103198.5(14)5353.6(11)132卜3<!8)6252.6(13)94.S7189.4(16)g147.3(17)g117.9(19)1096*4冀。）ii80,4共H席共6席共4席改進(jìn)Q值法與文獻(xiàn)中Q值法、于擬合方法胃】、新Q值法印、最大嫡法回、最大概率法［叮和遺傳算法?等進(jìn)行了比較，其綣果如表3所示。表3各方法對(duì)例1的計(jì)算結(jié)果比較方法21個(gè)席位分配結(jié)果甲系乙系丙系改進(jìn)Q值W1164經(jīng)典Q值法1164新Q值法1074Xs擬合方法114整數(shù)規(guī)劃模型11￡4最大嫡法1164最大概率法1173遺俊算法_10J4雖然在這里Q值法和改進(jìn)Q值法計(jì)算結(jié)果是一致的，但是兩種方法的結(jié)果不總是一致的。同樣是這道題目根據(jù)按比例的原則，其分析結(jié)果如表4所示。表4例2的席位分配表n人數(shù)所占比例,%按比例分配的名額甲系23523.5A585乙系33333-33.663丙系43Z43,24.752100n而利用Q值法和改進(jìn)Q值法的計(jì)算結(jié)果如表5所示。表5Q值法和改進(jìn)。值計(jì)算培果比較方法11個(gè)席位分配結(jié)果甲系 乙系 丙系改逃Q值法3 4 4經(jīng)典Qflyfe2 4 5哪種分配方案更公平呢?首先分析一下Q值法和改進(jìn)Q值法每席位代表的人數(shù)，分析如表6所示。表6例2的席位分配分析表系別按比例分配的名額Q值法每席位代表人數(shù)政進(jìn)Q值法每席位代表人數(shù)甲?系2.585117-5總33乙家3.86383.2582.25丙系4.7528&4010&00Q值法每席位代表的人數(shù)最大值與最小值(即甲系與乙系)相差34.25，改進(jìn)Q值法每席位代表的人數(shù)最大值