名额分配

名额分配问题（assignment problem of the number of deputies to be elected）政治学中的一个数学问题，“按人口比例分配议员名额”的计算方法的问题，是数学在政治学中的一个应用。它以应用浅显的数学知识得出了深刻的政治结论，却一直未获根本解决，因此而著称于世。

由来

方法

悖论

问题

由来

根据美国宪法，美国国会分参议院和众议院，参议院中各州有等额议席，而众议院“议员名额……将根据各州的人口比例分配”。这就是名额分配问题的缘起。美国宪法于1787年获得通过，1788年生效，但从1790年以来的200多年间，怎样操作才算公正、合理地按这一原则分配好名额，一直是美国政治家以及许多介人其中的科学家研究和争议的问题。人们创立了许多方法，但没有一种方法得到公认。

把这个问题数学化，则可作如下探讨：设美国一共有s个州，众议院一共设有h个议员席位。再设第i州有人口pi（i=1, 2,…, s），则全国总人口有P=p1+p2+…+ps，第i州的人口占全国总人口的比例为 。按上述宪法原则，第i州应有 h个议员名额，记为qi= h，，称之为第i州的“份额”，则显然有

q1+q2+…+qs=h。

但是一般地，qi不是整数，而议员名额却必须是整数。怎么办？这就是名额分配问题的症结所在。

用“四舍五入法”或“去尾法”或“进一法”对q‘取整数，都不行，因为这就会出现或者名额不够，或者名额剩余。

既然不能通过简单的对份额取整完成名额分配，问题就成为：在众议院席位数h，州数s，各州人口数pi（i=1, 2, 3,…, s）给定的条件下，求出各州的份额qi（i=1, 2,…, s）后，如何找出相应的一组整数a1，a2，…，as，使得

a1+a2+…+as=h，

让第i州取得a i（i=1, 2, 3,…, s）个议员名额，并且“尽可能地”满足美国宪法所规定的“按人口比例分配”的原则？这就是“名额分配问题”。从数学上说，稍加解释，小学生也可明白，但其求解却难倒了众多的政治家和数学家！

方法

美国第一任总统乔治华盛顿时代的财政部长亚历山大汉密尔顿首先于1790年提出了解决名额分配问题的一种方法，1792年被美国国会通过，称之为汉密尔顿方法。

这一方法规定如下操作程序：

（1）取各州的份额qi的整数部分[qi]（如qi=1.5，[qi]=1；qk=0.82，[qk]=0），先让第i州拥有[qi]个议员名额。

（2）再看各州份额qi的小数部分。按从大到小的顺序，把余下的议员名额逐个分配给各相应的州，分完为止。具体做法是：小数部分（qi一[qi]）最大的州优先取得余下名额中的一个，小数部分次大的州取得再余下的名额中的一个……直到名额分完为止。

汉密尔顿方法看起来是相当公正、合理的，但它于1742年被美国国会通过后并未能马上付诸实施。最先采用的是杰斐逊的方法。

杰斐逊方法是一种“除子方法”。在前面我们谈问题的缘起时指出，问题的关键是：虽然有q1+q2+…+qs=h，但对qi以某种方式取整[qi]后，[q1]+[q2]+…十[qs]就不一定等于h了。杰斐逊认识到qi只有相对的意义，而不具有绝对的意义，因而，用一个正数λ去除所有的qi，得到 ，用 代替原来的qi，其对相应的第i州来说表示“份额”的意义不变。这样如果选取适当的λ，使 在某种取整数的方法（如四舍五入法、去尾法、进一法等）下得到的整数[ ]加起来后恰好等于h，则可把ai=[ ]作为第i州应得的议员名额。由于用正数λ除后才得出名额的，所以叫做“除子方法”。如果用“去尾法”取得整数[ ]，就叫做杰斐逊法。

杰斐逊法也有令人不能接受的地方。那就是它不能符合所谓“公平分摊”的原则。这个原则是：按常理，对某一个非整数份额qi，它所取的名额数ai应满足[qi]<ai<[qi]+1（其中方括号仅表示用去尾法取整数）。但采用杰斐逊法，可产生“例外”，例如s=3，h=5，而q1=0.6， q2=0.5，q3=3.9，则显然有q3<4，按“原则”，应有3<a3<4，但按杰斐逊法，取x=0.7，则有al=[ ]=0，a2=[ ]=0， a3=[ ]=5。

这种情况使美国国会在华盛顿总统否决汉密尔顿法50年后，重又接受了汉密尔顿法，并于1851年开始在美国实际使用。

悖论

从1880年，即美国众议院正式采用汉密尔顿法的第50年开始，美国国会出现了关于汉密尔顿法的公正合理性的激烈争论。其原因是1880年美国人口普查后，美国的一个州——亚拉巴马州发现用汉密尔顿方法分配名额使自己吃了亏。后来，1890年和1900年美国人口普查后，缅因州和科罗拉多州也认为自己吃了亏，因而反对汉密尔顿方法。这就是因为产生了一系列的“悖论”。

（1）亚拉巴马悖论。按常理，假定各州的人口比例不变，而众议院议员席位由于某种原因增加了一席，那么各州的议员名额或者不变，或者增加，无论如何不应减少，但是汉密尔顿法却不能保证这一点。

当州数s和各州人口比例 不变，众议院议员席位h增加反而导致某州议员名额减少，就称之为“亚拉巴马悖论”（因1880年该州最先遇到这种情况）。

（2）人口悖论。当h不变时，若各州人口有所增长，则即使第i州的人口增长率比第1州更大，有时也有可能第i州失去一个席位而第j州增加一个席位。这种情况被称为人口悖论。

（3）新州悖论。设有一个新的州加人了美利坚合众国（这在美国历史上发生过数十次），则总人口增加，相应地众议院席位也有所增加。这时原来某个州失去了一个席位，而另一个州增加了一席，虽然原来所有州的人口都没有发生变化，这种情况被称为新州悖论。

这些悖论都显示出汉密尔顿法的不合理之处，因此，它于1910年被废止。

问题

汉密尔顿法不合理，以杰斐逊法为代表的各种除子方法也不尽如人意，怎么办呢？是否存在一种能使各方面都满意的名额分配方法呢？现在美国使用的是数学家E．V．亨廷顿（Huntington）提出的几种方法（1941年通过并被采用）。当然它们也不是没有问题的。

两位著名学者，美国的巴林斯基（M．Balinski）和扬（H．Young）在名额分配问题的研究中引进了公理化方法。即事先根据具体的现实问题给出一系列合理的要求，称之为“公理”，然后用逻辑方法考察这些公理之间是否相容。如果不相容，则说明符合这些公理的对象并不存在。

巴林斯基和扬在1982年证明了关于名额分配问题的一个不可能定理，指出包括“不产生人口悖论”、“不违反‘公平分摊’原则”等在内的5条十分合理的公理不相容，即满足这5条公理的名额分配方法并不存在。

但名额分配问题更广一些，一般分配问题是一个有现实需要的问题，有相当广泛的应用，如货物、任务、人员、成本等的分配问题。怎样尽可能合理地解决这个问题，是当代数学家正在研究的问题之一。