←
孔多塞排序
辅助方法
Dodgson Quick 方法
刘易斯·卡罗尔的构想:选出只需最少调整就能胜过所有人的那个选项。思路直观,但缺少 Schulze 那样经过证明的保证。
适用场合: 章程指定采用此方法,或者这种解读结果的方式更容易让投票人理解时。
- 由来
- Charles Dodgson(刘易斯·卡罗尔),1876 年;近似算法由 McCabe-Dansted、Pritchard 和 Slinko 于 2008 年提出
- 可选变体
- Dodgson Quick
- 计算
- 多项式时间,n 个选项时为 n² 量级(精确的 Dodgson 方法为 NP 困难)
基本原理
衡量与孔多塞胜者的距离
Dodgson 方法选出的,是在选票上调换次数最少就能成为孔多塞胜者的选项。精确计算这一结果是 NP 困难问题(Bartholdi、Tovey 和 Trick,1989)。
Dodgson Quick 用简便方法估算:每输一场对决,至少需要扭转一半的票差。得分就是这些半数票差(向上取整)之和,得分最低者胜出。
分步演示
同一个循环,按调换次数衡量
示例中的 100 张选票
- Camille ,其次是 Adèle ,其次是 Sophie 40 名投票人
- Adèle ,其次是 Sophie ,其次是 Camille 35 名投票人
- Sophie ,其次是 Camille ,其次是 Adèle 25 名投票人
- 1 Camille。 以 20 票之差负于 Sophie:得分 10。
- 2 Adèle。 以 30 票之差负于 Camille:得分 15。
- 3 Sophie。 以 50 票之差负于 Adèle:得分 25。
- Camille 负于 Sophie,相差 20 票 10
- Adèle 负于 Camille,相差 30 票 15
- Sophie 负于 Adèle,相差 50 票 25
性质
这一方法能保证什么(与一轮相对多数制对照)
已发表的表格都没有涵盖 Dodgson Quick:这里只填写了由其构造方式或普遍结论所确立的格子。
| 准则 | Dodgson Quick | 一轮相对多数制 |
|---|---|---|
| 多数准则 超过半数投票人排在第一的选项胜出。 | 是 注 1 | 是 |
| 多数败者准则 超过半数投票人排在最后的选项永远不会胜出。 | 未经证实 | 否 |
| 相互多数准则 如果多数投票人把某一组选项排在其他所有选项之前,胜者必定来自这一组。 | 未经证实 | 否 |
| 孔多塞胜者准则 在对决中胜过其他每个选项的选项,一定当选。 | 是 注 2 | 否 |
| 孔多塞败者准则 在对决中输给其他每个选项的选项,一定不会当选。 | 未经证实 | 否 |
| 史密斯准则 胜者属于这样一个最小的选项组:组内每个选项都胜过组外所有选项。 | 未经证实 | 否 |
| 克隆独立性 加入一个与现有选项极为相近的选项,不会改变其他选项之间的胜负。 | 未经证实 | 否 |
| 单调性 把胜者排得更靠前,绝不会让它因此落败。 | 未经证实 | 是 |
| 局部独立性 去掉结果中排在最后(或第一)的选项,其他选项的顺序不变。 | 未经证实 | 否 |
| 反转对称性 如果所有选票的顺序都颠倒过来,原来的胜者就不再胜出。 | 未经证实 | 否 |
| 参与准则 按真实偏好投票,绝不会比弃权对投票人更不利。 | 否 注 3 | 是 |
| 一致性 如果一个选项在两个独立的群体中都胜出,把两个群体合并后它仍然胜出。 | 否 注 3 | 是 |
| 后续无害性 多排一个选择,绝不会损害已经排在它前面的选择。 | 否 注 3 | 是 注 4 |
| 可决性 投票人越多,最终出现并列的可能性越小。 | 未经证实 | 是 |
| 计算快速 结果可在多项式时间内算出,选项很多时也是如此。 | 是 | 是 |
- ✓ 始终满足
- ✕ 在某些投票中可能不满足
- ? 尚无已发表的文献证实
- 1 这是孔多塞准则的直接推论:被多数投票人排在第一的选项,在对决中胜过其他所有选项。
- 2 由算法构造保证:CondorcetPHP 总是把孔多塞胜者排在第一。
- 3 满足孔多塞准则的方法都不可能满足这一准则:这是一个普遍结论。
- 4 平凡成立:一轮相对多数制从不考虑第一选择之后的排序。
在 Condorcet.Vote 中
我们的实现选择
- 孔多塞胜者排在第一 只要存在孔多塞胜者,CondorcetPHP 总是把它排在第一名。
- 有意采用近似算法 不提供精确的 Dodgson 方法:它的计算量可能大到无法实际完成。
- 需要了解的局限 得分只看败场:输给其他所有选项的选项,排名可能反而高于只输了一场对决的选项。
参考资料
延伸阅读
| 类型 | 文献 |
|---|---|
| 百科全书 | Dodgson’s method Wikipedia |
| 技术文档 | Voting Methods CondorcetPHP · docs.condorcet.io |
| 论文 | Approximability of Dodgson’s rule John C. McCabe-Dansted, Geoffrey Pritchard, Arkadii Slinko (2008) · Social Choice and Welfare 31(2) |