公平的席位分配

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

表1改匱。值法的分配結果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席括號內的數(shù)字/表示第』個席位分配翳它所在的列的那個系表20值法的分配結果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席改進Q值法與文獻中Q值法、于擬合方法胃】、新Q值法印、最大嫡法回、最大概率法［叮和遺傳算法?等進行了比較，其綣果如表3所示。表3各方法對例1的計算結果比較方法21個席位分配結果甲系乙系丙系改進Q值W1164經(jīng)典Q值法1164新Q值法1074Xs擬合方法114整數(shù)規(guī)劃模型11￡4最大嫡法1164最大概率法1173遺俊算法_10J4雖然在這里Q值法和改進Q值法計算結果是一致的，但是兩種方法的結果不總是一致的。同樣是這道題目根據(jù)按比例的原則，其分析結果如表4所示。表4例2的席位分配表n人數(shù)所占比例,%按比例分配的名額甲系23523.5A585乙系33333-33.663丙系43Z43,24.752100n而利用Q值法和改進Q值法的計算結果如表5所示。表5Q值法和改進。值計算培果比較方法11個席位分配結果甲系 乙系 丙系改逃Q值法3 4 4經(jīng)典Qflyfe2 4 5哪種分配方案更公平呢?首先分析一下Q值法和改進Q值法每席位代表的人數(shù)，分析如表6所示。表6例2的席位分配分析表系別按比例分配的名額Q值法每席位代表人數(shù)政進Q值法每席位代表人數(shù)甲?系2.585117-5總33乙家3.86383.2582.25丙系4.7528&4010&00Q值法每席位代表的人數(shù)最大值與最小值(即甲系與乙系)相差34.25，改進Q值法每席位代表的人數(shù)最大值