pivot-libre / tideman
Tideman排序对算法的实现
Requires
- clue/graph: 0.9.0
- graphp/algorithms: 0.8.1
- psr/log: ^1.0.2
Requires (Dev)
- cadre/sniffs: ^0.1.0
- monolog/monolog: ^1.23.0
- pds/skeleton: ^1.0.0
- phing/phing: ^2.16.0
- phpstan/phpstan: ^0.6.3
- phpunit/phpunit: ^6.2.3
- satooshi/php-coveralls: ^1.0.1
- squizlabs/php_codesniffer: ^3.0.1
README
目的
该算法通过对所有选票中所有候选人的排名集合进行处理，使用T.N. Tideman的排序对算法生成一个相对公平的汇总排名。
背景
本文档的目标读者是程序员。有关面向普通人的解释，请参阅维基百科的排序对文章或加拿大国会议员Ron McKinnon的condorcet.ca。
摘要
此算法首先计算所有选票中所有候选人配对之间的支持差异。这种两位候选人的差异称为差额。接下来，算法按差额的降序对差额进行排序。然后，算法通过从最大的差额到最小的差额迭代排序后的差额列表，为每个差额的获胜候选人和失败候选人添加一个指向失败候选人的边来构建图数据结构。如果添加差额的边会引入循环，则忽略该差额。完成图后，没有指向他们的边的候选人就是获胜候选人。换句话说，获胜者是完成图中的源节点。如果希望有多个获胜者，则可以不考虑已经获胜的候选人重复整个算法。
用法
将pivot-libre/tideman添加到项目中的composer.json依赖项。有关示例用法，请参阅tests/RankedPairsCalculatorTest.php。
详细信息
论文
- 作为投票规则的克隆独立性标准。Tideman, T.N. Soc Choice Welfare (1987) 4: 185. https://doi.org/10.1007/BF00433944
- 排序对规则中克隆的完全独立性。Zavist, T.M. & Tideman, T.N. Soc Choice Welfare (1989) 6: 167. https://doi.org/10.1007/BF00303170
原始1987年排序对论文缺少平局解决规则。1989年的后续论文增加了平局解决规则。
配对平局解决
在排名候选人配对时，可能两位候选人之间的支持差异等于两位其他候选人之间的支持差异。在这种情况下，必须通过配对平局解决规则来解决候选人配对之间的平局。该库根据用户指定的平局解决投票对象来打破配对平局。如果用户指定了包含平局的平局解决投票对象（即候选人之间的平局），则库使用PHP的默认随机数生成器来打破该投票对象中的所有平局。库不强制执行平局解决投票对象来源。如果用户希望遵循Zavist, Tideman 1989中指定的平局解决规则，则应从选民提交的投票对象中随机选择一个，并将其用作平局解决投票对象。
阅读材料
- 维基百科的排序对文章
- 加拿大国会议员Ron McKinnon的condorcet.ca提供了关于排序对的优秀面向普通人的概述。务必探索页面中的各种下拉部分和选项卡，因为网站内容的一些重要部分被隐藏在内部。
- 《剑桥计算社会选择手册》提供免费PDF版。第98-101页描述了蒂德曼的排名对算法。
- 在电域邮件列表中，马克斯·舒尔茨博士提供了一种关于蒂德曼-扎维斯特平局规则的另一种描述。解释只有几行，从“托马斯·扎维斯特建议...”开始。
贡献
设置
- 安装PHP 7.1和composer。
- 已知当以下PHP扩展安装时，库可以正常工作，尽管可能需要的扩展列表更短（参见问题#51）：ctype,curl,dom,iconv,json,mbstring,openssl,pdo,pdo_sqlite,phar,sqlite3,tokenizer,xmlreader,xmlwriter,zlib
与代码合作
- 将此存储库分支。
- 克隆您的分支。
- 将此存储库作为上游添加。
- 示例
git remote add upstream git@github.com:pivot-libre/tideman.gitgit remote add upstream https://github.com/pivot-libre/tideman.git
- 示例
- 下载依赖项
composer install
- 构建项目
vendor/bin/phing- 此命令检查文件语法，运行测试，检查格式符合性，并执行静态代码质量分析。
- 在输出结束时，您应该看到
BUILD FINISHED。您不应看到BUILD FAILLED。
可视化测试覆盖率
- 确保您已安装了xdebug。
- 运行
vendor/bin/phing coverage- 在网页浏览器中打开
file:///<file-path-to-cloned-repo>tideman/build/coverage/index.html - 例如：
file:///home/john_doe/src/tideman/build/coverage/index.html
分享您的作品
- 使用Git
add和commit您的本地更改 - 将您的更改推送到GitHub分支
git push origin
- 在您的分支和PivotLibre/tideman存储库之间创建拉取请求。
获取更新
git fetch upstream- 根据您是使用基于合并的工作流程还是基于rebase的工作流程，您将运行以下之一
git merge upstream/0.xgit rebase upstream/0.x