席位分配问题的D’hondt模型和相对尾数模型
摘要：讨论公平席位分配的模型已有很多。本文首先用比例加惯例法、Q值法、D’hondt法对问题中名额进行了分配，再对D’hondt法的合理性进行了分析，并在Q值法对绝对尾数（绝对不公平度）的处理方式基础上，提出了相对尾数模型，并讨论了其满足Young公理的1，3，4条；在模型求解上，全部由MATLAB程序来实现名额分配。 关键词：相对尾数 Balinsky & Young不可能定理 MATLAB
正文
1 问题复述
公平的席位分配问题是一个非常有趣而重要的问题，它在政治学、管理学和对策论等领域具有广泛的应用价值。处理这个问题的最早的方法是Hamilton法，即比例加惯例法；后来出现了Q值法；1974年M.L.Balinski和H.P.Young引入了席位分配问题的公理体系研究方法，并于1982年证明了同时满足五个公理的席位分配方法是不存在的；因此，我们只能根据实际建立在一定公平准则下成立并尽量多的满足Young公理的算法。这里，我们需要理解并运用比例加惯例法、Q值法、D’hondt法对宿舍委员会名额进行分配，继而提出更优的公平分配席位的方法。 2 模型假设 2.1合理假设
2.1.1 比例加惯例法、Q值法等分配模型均为已知； 2.1.2 各个宿舍相互独立互不影响，人数保持不变； 2.1.3 委员分配以各宿舍人数为唯一权重。 2.2 符号约定 符号 意义 第i个宿舍的Q值 第i个宿舍的人数 第i个宿舍分配的名额 总人数 总名额数 第i个宿舍的理想分配名额 总席位增加一个时第i个宿舍的理想分配名额 Qi ni mi n m pi pi ?qi 第i个宿舍的分配比例，即nim nsi ri ri ?第i个宿舍的绝对尾数值 第i个宿舍的相对尾数值 总席位增加一席时第i个宿舍的相对尾数值 t 按比例分配后剩余名额
3 模型的建立与求解
3.1按比例加惯例模型分配
根据比例加惯例分配模型的原理，编写MATLAB程序实现（附录-程序1，2，3，附录-输入及运行结果1），结果如表所示：
表1（比例加惯例法分配结果）： 10个席位的分配 宿舍 A B C 总数
3.2按Q值法模型分配
学生人数 235 333 432 1000 比例分配的席位 2 3 4 9 惯例分配的结果 3 3 4 10 15个席位的分配 比例分配的席位 3 4 6 13 惯例分配的结果 4 5 6 15 ni首先用比例分配法对名额进行初步分配，再根据表达式Qi? i?A,B,Cmi(mi?1)对剩下的名额进行分配，编写MATLAB程序实现求解（附录-程序4，5，附录-输入及运行结果2）：
表2（Q值法分配结果）： 10个席位的分配 宿舍 学生人数 比例分配名额 A B C 总数 235 333 432 1000 2 3 4 9 Q值 9204.17 9240.75 9331.2 最终分配名额 2 3 5 10 15个席位的分配 比例分配名额 3 4 6 13 Q值 4602.08 5544.45 4443.43 最终分配名额 4 5 6 15 2
3.3 D’hondt模型 3.3.1 模型建立
设n，m分别表示宿舍总人数和总分配席位数，ni(i?1,2,3)表示各宿舍人数，令
aij?ni(i?1,2,3,j?1,2,...)，则得到一个数列?aij?，将该数列按递减顺序重新排列，得j(k)(k)(k)(k)
到aij，其中aij表示aij中第k大的项。取aij中前m项，则相应得到
??????mp???a?(k=1,2,...,m)中i?p的元素的个数?(p?1,2,3)，m,m(k)ij12,m3即为按
D’hondt模型分配的结果。 3.3.2 按D’hondt模型分配
根据建立的D’hondt模型，编写MATLAB程序求出结果（附件-程序6，附录-输入及运
行结果3）：
表3（D’hondt模型分配结果）： 宿舍 A B C 总数
3.4 相对尾数模型 3.4.1 模型准备
讨论一般情况:k个宿舍人数分别为ni,i?1,2,...,k,总人数为n?n1?...?nk,待分配的席位为m个,理想化的分配结果是pi(i?1,2,...,k),满足m?人数 235 333 432 1000 10个名额的分配 2 3 5 10 15个名额的分配 3 5 7 15 ?pi?1ki,记
qi?nim(i?1,2,...,k)。显然,若qi全为整数,应有qi=pi(i?1,2,...,k),当qi不全为整数n公理一：?qi???pi??qi??(i?1,2,...,k),即pi取?qi??或?qi??之一,其中
时,需要确定同时满足下面公理的分配方案。
?qi??=?qi?,?qi??=?qi??1,?qi?表示qi的整数部分。
公理二：pi(m,n1,n2,...,nk)?pi(m?1,n1,n2,...,nk),i?1,2,...,k,即总席位增加时,各宿舍的席位数不应该减少。
公理一显然满足Balinsky & Young不可能定理 (见附录) 中的公理4（公平分摊性）,公理二满足其的公理1（人口单调性）和公理3（名额单调性）。令si?ni?n?m??im??qi??qi??,n?n??称其为对第i个宿舍的绝对尾数值。令ri?3.4.2 模型建立与求解
si,称其为对第i个宿舍的相对尾数值。 ?qi??由于人数都是整数,为使分配趋于公平,需所有的ri越小越好,所以趋于公平的分配方案应该是最大的ri达到最小,即所有的ri达到最小。
为方便起见,首先考虑只有两个宿舍的情形,即k?2,n?n1?n2,且n1?n2,q1和q2不全是整数(实际上,他们同为整数或小数)。记pi,ri为总席位增加一席时的分配结果和相对尾数。给出定理:
定理:以下分配方案满足公理一,二，
??1) 若r1?r2,且s1?s2,则取p1??1m??1,p2??2m?,即按比例加惯例
?n???n??法分配;
2) 若r1?r2,则取p1??1m??1,p2??2m?;
?n???n??3) 若r1?r2,则取p1??1m?,p2??2m??1。 ?n???n??定理证明见附录。
按照定理，对三个宿舍的情形进行讨论。设r1,r2,r3全部为零(实际上,如果有一个为零,即是按两个宿舍分配),可以做以下分配:
1) 当r1?r2?r3时,按比例分配取整后,剩余的席位分配给绝对尾数较大的宿舍,即按比例加惯例法分配;
2)
当r1?r2?r3时,按比例分配后,若剩余一个席位,则分配给第一个宿舍,若剩余两
?n??n??n??n??n??n?个席位,则分配一席给第一个宿舍,另外一席分配给第二三个宿舍中绝对尾数值较大者；
3) 当r1?r2?r3时，按比例分配后，若剩余一个席位分配给第一二个宿舍中绝对尾数值较大者，若剩余两个席位，则分配给第一二宿舍各一席；
4)
当r1?r2?r3时，按比例分配后,若剩余一个席位,则分配给第一个宿舍,若剩余两
个席位,则分配给第二个宿舍。
一般地，对k个宿舍，设r1,r2,?，rn不全为零，且rt?rt?1时，1?r2?...?rk，则当r将剩余的t?m?k?ni???nm?个席位分配给第一至第t个宿舍各一席，当rt?1?rt?rt?1?rt?2??i?1?k时，t?m??ni???nm? 个席位分配给第一至第t?1个宿舍及st和st?1较大的宿舍各一席，
??i?1??ni???nm? 个席位分配给第一至第t?1??i?1?k当rt?1?rt?rt?1?rt?s（1?s?k?t）时，t?m?个宿舍及st，st?1，?st?s中较大的宿舍各一席，当rt?s?rt?s?1?rt?s'（1?s,s'?k?t），
?ni? 个席位分配给第一至第t?s个宿舍及st，st?1，?st?s中s个较大的所t?m???m???i?1?n对应的宿舍各一席。
最后，编写出尾数法的MATLAB程序，实现3本题中的名额分配（附录-程序7，附录-
k输入及运行结果4）。
表4（尾数法分配结果）： 宿舍 A B C 总数 人数 235 333 432 1000 10个名额的分配 3 3 4 10 15个名额的分配 4 5 6 15
4 模型检验及结果分析
席位分配的尾数模型满足Young公理的1、3、4条，是以严格证明了的定理形式给出。对按上述四种分配模型分配的结果列表比较。 表5（各方法分配结果的比较1）： 宿舍 A B C 总数 学生人数 103 63 34 200 20个席位的分配 B 10 6 4 20 Q 11 6 3 20 D 11 6 3 20 R 10 6 4 20 B 11 7 3 21 21个席位的分配 Q 11 6 4 21 D 11 7 3 21 R 10 7 4 21
表6（各方法分配结果的比较2）： 学生宿舍 人数 A B C 235 333 432 10个席位的分配 B 3 3 4 10 Q 2 3 5 10 D 2 3 5 10 R 3 3 4 10 B 4 5 6 15 15个席位的分配 Q 4 5 6 15 D 3 5 7 15 R 4 5 6 15 总数 1000
表格中，B表示比例加惯例法，Q表示Q值法，D表示D'hondt法，R表示相对尾数法。 “比例加惯例”法用各团体人数占团体总人数的比例乘以总席位数, 取其整数位为第一次分配, 再次分配时, 则按小数位的大小分, 大的先分配, 直到席位分完。从表4看到，当总席位数增加时，C宿舍分得的席位却减少；
Q值法利用相对不公平度建立了衡量不公平程度的数量指标, 进而将席位分给最不公平的一方。 D’hondt方法将各团体的人数用正整数相除, 其商数组成一个表, 将数从大到小取, 直到取得的商数的个数等于总席位数, 统计出每个团体被取到的商数的个数, 即为该团体分得的席位数。
5 优缺点分析及改进
从对模型的检验与分析可以看到，上面讨论的三个模型都有自身的不足：比例加惯例法满足公理一，却不满足公理二；Q值法满足公理二但不满足公理一；D’hondt法也不能解决对每个宿舍成员公平的大小问题；尾数法虽然满足公理一和二，但由于两个公理本身只满足Young公理体系的部分，也不尽完美。
优点：尾数模型打破Q值法的对绝对尾数的比较方法，以相对尾数来讨论，使得模型满足了Young公理体系中更多的公理，虽不尽完善，但相比之前的四种方法是很大的改进。并