公平的席位分配

席位公平分配问题一Q值法的改进摘要：本文为建立席位分配问题的公平合理方案.对经典Q值法进行了研究并提出改进，构造了衡量相对不公平程度的新标准量。通过对书本中的经典席位分配问题实例的计算，比较分析了多种席位分配方法的求解结果，并与经典的Q值法进行了公平性的比较。结果表明改进的标准量更为合理，从而验证了该方法的有效性和合理性。一、问题背景席位分配问题是人类社会生活中相当普遍的一类资源分配问题，是数学在政治领域中应用的典型实例，其目标是在一个大集体对小集体进行某种资源分配时试图尽可能做到公平合理。席位分配问题最关键之处是它的悖论观，无论选择怎样的分配方案，总会产生这样或那样的矛盾，著名的有以下几种悖论：亚拉巴马悖论、人口悖论和新州悖论。同时，席位公平分配的关键是提出衡量公平度的一个量，即满足下述5条公理：公理1（人口单调性）：一方的人口增加不会导致它失去一个名额。公理2（无偏性）：在整个时间平均，每一方应接受到它自己应分摊的份额。公理3（名额单调性）：总名额的增加不会使某一方的名额减少。公理4（公平分摊性）：任何一方的名额都不会偏离其比例份额数。公理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方的人数为七（i=1，2,…，m），m方的总人数为 i=1\n.第i方所分配的席位为I，（i=1，2，…，m），如何寻找一组整数"1,n2,......,"m，使得if' 并且“尽可能”地公平。理想的最公平分配方案是按人数比例的分配，即第i方应分配的“份额”是〃「=S"。但节N往往不是整数，而用“四舍五入”或取整的方法导致更不公平，由此提出了经典的Q值法。1.2Q值法利用Q值法导出一个席位分配的标准量Qi，Q尸潟刁=1⑵“5），根据％值的大小确定下一个席位应分配给那一方，具体操作如下：首先给每一方分配一个席位，计算Qi（（=1，2,…，m）值，Q值较大的一方优先获得下一个席位。然后再计算Qi值，Q值较大的一方优先再获取一个席位，如此反复，直到所有席位分配完为止。由于ni和"•+1分别是不给i方增加一席和给i方增加一席时该方席位代表的人数，而Q值法恰是这两个数的几何平均值的平方，并且从算法描述可看出，可供分配的席位数N必须能保证每一方至少能分配到一个席位，而没有考虑是否应该给某一方这个席位（可能出现该方根本不产生代表），因此Q值法具有一定的局限性。1.3新的衡量标准Cp2Q=zQ值法的定义式'七（气+1）所示的相对不公平值只反映了i方本身增加或不增加一席的综合情况，并没有把i方放到所有各方构成的整体中去考虑，也没有反应相对于本方每席位代表和人数的比例关系与另外一方每席位代表和人数的比例是否一致或相接近，因此Q值法尚需进一步改进。定义设有m方共P人参与总席位为N的席位分配，第i方的人数为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的值表示相对于本方总人数而言的不公平程度，若p1pMjN_n与p J接近，而第j方比第i方人数多很多，则对第i方分配ni个席位相对于第j方分配nj个席位而言，i方感到不公平。Q因此i的值越大，偏离理想状态越远，越不公平。1.4改进的Q值法根据前面的讨论，改进的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值法首先给每一方分配一席位的不合理规定，并且考虑了每一方每席位所代表的人数，每席位代表人数多的越不公平，所以优先得到一个席位。三应用实例为了验证改进的Q值法的合理性和有效性，选择书中的典型例子，并与经典Q值法的计算过程及相关文献中计算结果进行了比较。书中所给的例子，假设说，有一个学校要召集开一个代表会议，席位只有20个，三个系总共200人，分别是甲系100，乙系60,丙系40.如果你是会议的策划人，你要合理的分配会议厅的20个座位，既要保证每个系部都有人参加，最关键的就是要对个公平都公平，保证三个系部对你所安排的位置没有异议。那么这个问题就要靠数学建模的方法来解决。公平而又简单的席位分配方法是按学生人数的比例分配，显然甲乙丙三系分别应占有10、6、4个座位。现在丙系有6名学生转入甲乙两系，各系人数如表1表2第2列所示，仍按比例（原表1第3行）分配席位时出现了小数（原表1第4行）。在将取得整数的19席分配完毕后，三系同意参照所谓惯例分给比例中小数最大的丙系，于是三系仍分割占有10、6、4个席（原表1第5行）系名甲乙丙总数学生数1036334200学生数103/20063/20034/200100按比例分配席位10.36.33.420按惯例席位分配106420原表1:按照比例并参照分配惯例的席位分配但后来会议决定下一届增加1席，她们按照上述办法重新分配席位，计算结果见原表2，显然这个结果对丙系太不公平了，因为总席位增加1席，而丙系却由4席减为3席：系名甲乙丙总数学生数1036334200学生人数比例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值法无需这一不合理规定，直接从第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席括号内的数字/表示第』个席位分配翳它所在的列的那个系表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经典Q值法1164新Q值法1074Xs拟合方法114整数规划模型11£4最大嫡法1164最大概率法1173遗俊算法_10J4虽然在这里Q值法和改进Q值法计算结果是一致的，但是两种方法的结果不总是一致的。同样是这道题目根据按比例的原则，其分析结果如表4所示。表4例2的席位分配表n人数所占比例,%按比例分配的名额甲系23523.5A585乙系33333-33.663丙系43Z43,24.752100n而利用Q值法和改进Q值法的计算结果如表5所示。表5Q值法和改进。值计算培果比较方法11个席位分配结果甲系 乙系 丙系改逃Q值法3 4 4经典Qflyfe2 4 5哪种分配方案更公平呢?首先分析一下Q值法和改进Q值法每席位代表的人数，分析如表6所示。表6例2的席位分配分析表系别按比例分配的名额Q值法每席位代表人数政进Q值法每席位代表人数甲•系2.585117-5总33乙家3.86383.2582.25丙系4.7528&4010&00Q值法每席位代表的人数最大值与最小值(即甲系与乙系)相差34.25，改进Q值法每席位代表的人数最大值