跳至主要内容
Condorcet.vote Alpha
← 孔多塞排序
辅助方法

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. 1 Camille。 以 20 票之差负于 Sophie:得分 10。
  2. 2 Adèle。 以 30 票之差负于 Camille:得分 15。
  3. 3 Sophie。 以 50 票之差负于 Adèle:得分 25。
得分(最低者胜)
  1. Camille 负于 Sophie,相差 20 票 10
  2. Adèle 负于 Camille,相差 30 票 15
  3. Sophie 负于 Adèle,相差 50 票 25
结果:Camille › Adèle › Sophie,在这个例子中与 Schulze 的顺序相同。
性质

这一方法能保证什么(与一轮相对多数制对照)

已发表的表格都没有涵盖 Dodgson Quick:这里只填写了由其构造方式或普遍结论所确立的格子。

准则 Dodgson Quick 一轮相对多数制
多数准则 超过半数投票人排在第一的选项胜出。 是 注 1 是
多数败者准则 超过半数投票人排在最后的选项永远不会胜出。 未经证实 否
相互多数准则 如果多数投票人把某一组选项排在其他所有选项之前,胜者必定来自这一组。 未经证实 否
孔多塞胜者准则 在对决中胜过其他每个选项的选项,一定当选。 是 注 2 否
孔多塞败者准则 在对决中输给其他每个选项的选项,一定不会当选。 未经证实 否
史密斯准则 胜者属于这样一个最小的选项组:组内每个选项都胜过组外所有选项。 未经证实 否
克隆独立性 加入一个与现有选项极为相近的选项,不会改变其他选项之间的胜负。 未经证实 否
单调性 把胜者排得更靠前,绝不会让它因此落败。 未经证实 是
局部独立性 去掉结果中排在最后(或第一)的选项,其他选项的顺序不变。 未经证实 否
反转对称性 如果所有选票的顺序都颠倒过来,原来的胜者就不再胜出。 未经证实 否
参与准则 按真实偏好投票,绝不会比弃权对投票人更不利。 否 注 3 是
一致性 如果一个选项在两个独立的群体中都胜出,把两个群体合并后它仍然胜出。 否 注 3 是
后续无害性 多排一个选择,绝不会损害已经排在它前面的选择。 否 注 3 是 注 4
可决性 投票人越多,最终出现并列的可能性越小。 未经证实 是
计算快速 结果可在多项式时间内算出,选项很多时也是如此。 是 是
  • ✓ 始终满足
  • ✕ 在某些投票中可能不满足
  • ? 尚无已发表的文献证实
  1. 1 这是孔多塞准则的直接推论:被多数投票人排在第一的选项,在对决中胜过其他所有选项。
  2. 2 由算法构造保证:CondorcetPHP 总是把孔多塞胜者排在第一。
  3. 3 满足孔多塞准则的方法都不可能满足这一准则:这是一个普遍结论。
  4. 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)

选择允许 Condorcet.Vote 在公开页面上统计哪些数据。您的选择保存在本设备上,随时可以修改。

必要功能 始终启用

语言、主题,以及记住这些选择。