翻译稿1996B-樊佩珊

1、MCM96 问题问题-B 竞赛评判问题竞赛评判问题 在确定像数学建模竞赛这种形式的比赛的优胜者时，常常要评阅大量论文。譬如说，有 P100 份论文，一个由 J 位评阅人组成的小组来完成评阅任务，基于竞赛资金对于能够聘 请的评阅人数量和评阅时间的限制，如果 Pl00；通常取 J8理想的情况是每个评阅人 看所有的答卷，并将它们一一排序，但这种方法工作量太大。另一种方法是进行一系列的筛 选， 在一次筛选中每个评阅人只看一定数量的答卷， 并给出分数。 为了减少所看答卷的数量， 考虑如下的筛选模式：如果答卷是被排序的，则在每个评阅人给出的排序中排在最下面的 30答卷被筛除；如果答卷被打分(譬如说从 1

2、分到 10 分)，则某个截止分数线以下的答卷 被筛除。这样，通过筛选的答卷重新放在一起返回给评阅小组，重复上述过程。人们关注的 是，每个评阅人看的答卷总数要显著地小于 P评阅过程直到剩下 W 份答卷时停止，这些 就是优胜者。当 J100 时通常取 W3。 你的任务是利用排序、打分及其它方法的组合，确定一种筛选模式，按照这种模式，最 后选中的 w 份答卷只能来自“最好的”2W 份答卷(所渭“最好的”是指，我们假定存在着 一种评阅人一致赞同的答卷的绝对排序)。例如，用你给出的方法得到的最后 3 份答卷将全 部包括在“最好的”6 份答卷中。在所有满足上述要求的方法中，希望位能给出使每个评阅 人所看答

3、卷份数最少的一种方法。 注意在打分时存在系统偏差的可能。例如，对于一批答卷，一位评阅人平均给 70 分， 而另一位可能给 80 分。在你给出的模型中如何调节尺度来适应竞赛参数(P，J 和 W)的变化? 建立更好的模拟评委模型建立更好的模拟评委模型 摘要摘要 我们要设计一个比赛的论文评阅系统，来尽可能满足两个目标：使每位评阅 员的评阅的论文尽量少，同时要保证比赛的公平性。我们首先设计一个模型，使 之能预先估计出仅对两份论文进行的人为判断和选择。模型的基本前提是，两份 在绝对排序上越靠近的论文，排序上被颠倒的可能性就越大；相反，它们在排序 上越不靠近，被颠倒的可能性越小。 我们的模型适用于任意数量

4、的评阅员、论文和优胜者。P 份论文分成 S 堆。 公平起见，每一堆由两位评阅员评阅。W 份论文晋级到下一轮。如果两位评阅员 对哪 W 份论文晋级上意见不一，由评阅组长决定。每一轮如此进行下去，直到 最终剩下 2W 份论文时， 此时由四位评阅人和评阅组长投票决定出 W 名优胜者。 我们可以预先设定评阅过程中的总评阅次数， 以及每位评阅人需进行的评阅的最 大数量。我们计算出最优的评阅人数使每位评阅人的评阅量大致相同。 经计算机测试，我们发现模型从 2W 份论文中选出 W 份失败的概率不超过 0.1%。失败的情况是由评阅中的人为因素引起的。对于给定由 8 位评阅人从 100 份论文中选出 3 位优胜

5、者的问题中， 合理的假设合理的假设 关于论文： 排序：根据论文的优劣可以进行绝对的排序，因此我们测定优胜的论文是够 在最好的 2W 份论文之内。 数量：论文的数量远大于优胜者的数量。 评阅人： 知识：所有评阅人都对于提出的问题都有很深的认识，且能轻松判断出一份 论文是否有价值。否则，论文不能获得公正的评价。 个人偏好：在允许的误差下，所有的评阅人最终会对某份论文的排名达成一 致。每位评阅人对论文里哪些地方值得肯定有个人的偏好。而且，当一位评阅人 要评阅大量的论文，在排序过程中必然会产生一定误差。 能力：一位评阅员一次可以评阅 20 份的论文并以某一合理的准确度选出优 秀的论文。通过向一些教授和

6、比赛评阅人的了解，我们得出 20 份论文是教授们 认为他们一次能保证公平评价的最大论文数量。 评阅组长： 评阅组长的工作仅为调解评判的分歧和在最终轮投票；评阅组长不计 算在 J 个评阅人内。 人数：最少评阅人数是 5 个，包括评阅组长。我们必须设置足够多的评阅人 对所有论文进行公平评价；评阅人越多，评阅过程的准确性越高。 公平是最根本的变量。在任何的比赛中，评阅人必须愿意为保证最好的论文 在比赛中胜出而牺牲精力和时间。比赛的可靠性是以评判过程的公平性和准 确性为基础的。 常量的定义及术语常量的定义及术语 P：总论文数 J：总评阅人数，不包括评阅组长 k J：表示评阅人 k W：总优胜者数 评阅

7、次数：一位评阅人一次评阅一份论文 轮：一组论文被筛选剩下 W 份论文的一个淘汰的过程 a R：表示第 a 轮 a S：第 a 轮的堆数。一堆是一组数量少于 P 的论文。 N：每堆包含论文的数量 jk S：表示第 k 论的第 j 堆 失误：评阅人排序情况与绝对排序不符 论文竞赛模型论文竞赛模型 模型首先将 P 份论文分成 S 堆，接着评阅人进行一轮淘汰，由每两位评阅 人一起将两堆论文筛选至剩下一堆数量为 W 份的论文。论文间的比较用排序来 表示，不使用评分规则。淘汰阶段重复进行，直到剩下最后的两堆论文。在最后 一轮里采取投票制从最后两堆论文里确定出优胜者。 准备准备 我们首先确定首轮里堆的数目，

8、 。为了保证淘汰能对称地进行， 须为 2 的幂。根据我们的假设，每位评阅人最多可以评阅 20 份论文，因此每一堆的论 文数不超过 20.每堆的论文数 ，这里 n 表示满足下式的最小值： 当 不能整除 P，N 上舍入。论文竟可能地平均分配到 份。我们分配给每 位评阅人一堆，直到没有堆可分配或没有评阅人可分配。如果没有评阅人可分配 了，某些评阅人将被要求在第一轮评阅两堆。 第一轮第一轮 评阅人 和 被分配了堆 和堆 。评阅人 从堆 里选出较好的 W 份以保 证它们在第一轮不被淘汰。完成后，两位评阅人交换堆，评阅人 从 里选出 W 份，而 从 里选 W 份。然后，他们比较各自选出的列表，从堆 和堆

9、里的 集合里确定出最后的 W 份。当分歧出现时，评阅组长最终决定哪份论文晋级。 以相同的方式，每两堆论文都筛选剩 W 份。在第一轮结束时，共有 1 2 2nS 堆和 每堆有NM份论文。 为何每次选为何每次选 W 份？份？ 在每轮都有最佳的 2W 份论文筛选成一堆的过程。如果选出的论文少于 W 份，模型会自然地失败。若选出了论文多于 W 份，将会增加模型的稳定性，但 某程度上不保证必需的评阅次数增加。 第二轮与随后几轮第二轮与随后几轮 整个过程会有 n-2 个“中间”轮（见附录附录 A） 。对于这些中间轮，引进变量 r 代表轮的次序。 在 r R的开始， 我们有 1 2n r r S 堆， 每堆

10、有NM份论文。 把堆 1r S 和堆 2r S分配给接下来的两位评阅人，他们每人各自从 1r S与 2r S的集合中选出 W 份，并最终在评阅组长的协调下达成一致地让 W 份晋级。每两堆论文都以相同 方式筛选剩 W 份。每一轮重复以上规则直到 1n R 轮（包括此轮） ，完成时共剩下 2W 份论文。 最终轮最终轮 最终轮是投票阶段，为保证公平性和表明最终决定的重要性，我们选择了五 位评阅人，包括评阅组长来评价这些论文。这些评阅人评阅剩下的 2W 分论文并 排序，由一位公正员，或许是一名额外的评阅人统计投票结果，记排序第一位的 为 W 分，第二位为 W-1 分，等等，一直到第 W 位为 1 分。

11、得到最高分数的 W 份论文成为优胜者。若这过程中有相同得分等不能继续进行的状况，由评阅组长 的投票来判定。 人为因素人为因素 该模型或其他任何模型的一个不可控变量就是人为因素。 我们通过模仿现实 中的评阅人可能的表现的概率分布来模拟人为因素。 如果所有评阅人的想法完全 一样，那么论文 1 会永远地排在论文 2 的前面。然而，评阅人个体上对他们希望 在论文上看到什么有偏向性。最常见的例子是，一位评阅人认为表达效果比实质 重要，而另一位评阅人则认为实质比表达效果重要。这种情况下，论文 2 可能轻 易地被排在论文 1 之前。为了对认为因素建模，我们选择了一下这个函数作为一 位评阅人对两份论文的排序与

12、绝对排序不相同的概率 这里比赛中共有 P 份论文，d 是两份对照的论文的绝对等级的距离。 图 1：评阅人对两份论文排名的操作特征曲线。 （注意并不是概率密度函数。 ） 该方程给出了评阅人判断错误的概率作为针对描述对两份论文排序时产生 的真正差异。随着两个排名的距离增大，讲它们顺序颠倒的概率就降低得很快。 当两论文间的差距是 0.01P 时，判断错误的概率是 50%。因此，对于 P=100 的情 况论文 5 和论文 6 次序的安排是完全随机的。当距离大于 0.17P 时，判断错误的 概率是 0.这种情况下，两论文之间的差异太大了，比较中不可能产生错误。错误 判断概率的取值范围介于.01P 到.1

13、7P 之间，代表了现实中的情况两份论文 越接近，评阅人个人的风格偏好更可能影响到论文的排序。相似地，两份论文相 差越远，评阅人的偏好更不容易影响到它们之间的比较结果。 结论结论 总评阅次数总评阅次数 不包括评阅组长给出的裁判，总评阅次数为 第一项为 1 R中的评阅次数，第二项是从 2 R到 1n R ，第三项是 n R的评阅次数 （见附录附录 A） 。 评阅人数评阅人数 该模型要求有五位评阅人，包括评阅组长。模型可以应用于所有 J4 的情 况， 但存在一个最优评阅人数使每位评阅人评阅的最大次数最小化。改最有评阅 人数等于 1 S且不包括评阅组长在内。 1 R需要所有 Jo 个评阅人， 2 R需

14、要一半， 3 R 需要四分之一，如此类推。我们在第一轮以及后面的某一轮需要每一位评阅员， 概率 距离 使得每位的评阅次数接近相等（见附录附录 A） 。 最大化每位评阅人的评阅次数最大化每位评阅人的评阅次数 如果JJo，每位的最大评阅次数为 如果JJo， 最大评阅次数可以变得非常大， 甚至不合理的大。 这种情况下， J 位评阅人里的某些人会被要求在第一轮看多于两堆的论文。他们会不得不评阅 超过 40 份论文甚至可能更多，因为第二轮和接下来几轮还没开始。若已确定 JJo，那么 J 必须接近 Jo 否则很多评阅人会不愉快。 模型的检验模型的检验 我们用 C 语言实现该模型，并需要几个次要的假定（见附

15、录附录 B） 。 接着我们对变量组合 P 和 W 进行测试，并总是使用最优评阅人数 Jo。我们对表 1 里的每种情况重复测试了 10000 次。测试数据返回的平均错误率为 0.0023%。 表 1：论文总数P和优胜论文篇数W组合，对每个组合重复测试了 10000 次 该模型是可行的，它每人最大评阅次数和总次数上符合原则，最重要的是它 使最终的 W 分论文包含在选出的 2W 份最佳论文里。微小的错误率产生于人为 因素。在涉及人为因素的问题中，总是会有意外状况发生。 模型的优缺点模型的优缺点 优点优点 模型失败的概率十分低，通常低于 0.1%。 模型把人为错失情况考虑在内。 所有的评阅都是由直接比

16、较产生，至少由两位评阅人决定一份论文晋级。评 阅过程不涉及分数评价，这样不会产生评阅人对评分等级的偏向性，同时， 由于评阅人的错误判断导致无价值的论文晋级的机率降低。 对于解决给出的原始问题（P = 100, W =3, 且 J =8） ，我们的模型有非常好的 表现（见图 2） 。每次的失败率仅为 0.08%，并且把每位评阅人的评阅次数限 制在 32 次里（总论文数的 1/3） ，总评阅次数限制在 254 次。 最重要的是，该模型应用在我们这次 1996 年的 MCM 比赛的论文评论中会 很合适。模型是公平的，最佳的数份论文实际上总能在比赛中胜出。 缺点缺点 失败率 总评阅次数 评阅人最大评阅

17、次数 该模型有明确的有效范围。我们设置了一位评阅人一次能连续评阅 20 份论 文这个范围。 在第一轮结束后， 评阅人们将在接下来的每轮评阅 2W 份论文。 这样，优胜者的数量必须少于或等于 10。若允许设置总论文数的 2%成为优 胜者的话，论文总数须小于或等于 500.对 P 很大的情况，一个可行的解决方 案是将整个比赛分成每份少于 500 份论文的两部分，然后用该模型对每部分 进行操作。 我们不得不把复杂的人为因素考虑在内。基于曲线而得出的数据是我们对人 性能做的最大程度的估计。我们没有能反映人们在这些情况下的实际行为的 数据可供参考。我们所做的所有测试以及结果的正确性都是基于“我们的方 程

18、能真实代表现实世界的状况”这一假设的。如果进一步研究表明该方程不 准确，我们可以方便地把原方程修改为一个新方程。 附录附录 A：依据及证明：依据及证明 中间轮共有中间轮共有 n-2 轮轮 每一轮中，恰好有(1) r W S 分论文晋级到下一轮，其中12n r r S 。由于相 继的下一轮中的堆数都是前一轮的一半，新的每一轮都有 W 份论文。当仅剩下 2W 份论文时，进行最后一轮。最后一轮中，121 n r r S 或22 nr ，即 n=r， 总轮数为 n，包括第一轮和最后一轮。因此中间轮共有 n-2 轮。 图 2：在原始设定P=100，W=3，J=8 下，模型的操作简图 总评阅次数总评阅次数 在第一轮，每份论文被评阅了两次，产生了 2P 次评阅次数。在中间轮，对 每轮有W份一堆的论文 1 2n r 堆。 每一堆被评阅了两次， 在该n-2轮里产生 2 2n rW 次评阅次数。 n R轮有 5 位评阅人，每位都评阅了最后的 2W 份论文。如此，所有 轮中所产生的总评阅次数为 最优评阅人数最优评阅人数 Jo 的设定依据的设定依据 第 3 轮 第 2 轮 每堆 6 份 每堆 3 份 我们希望每位评阅人评阅的论文数大致相等。在第一轮满足了这一条（可能 当论文不能平均分配到每堆时，某些评阅人会额外多评阅一份论文） 。在每一相 继的轮里， 每位评阅人评阅