Advances in STV Margin Computation

单记可转移票制（STV）是一种多席位、基于偏好排序的比例代表制选举制度。所谓“胜选边界”（margin），是指为改变最终当选者集合所需篡改的最少选票数。若我们能够计算出某场STV选举的胜选边界，或其合理的下界，则可借助近期审计研究的最新进展，对该次选举的当选结果开展风险限定审计（risk-limiting audit）。此外，掌握胜选边界还有助于判断：选举过程中未被发现的差错，或已知的选票识别错误率，是否可能影响最终结果。本文在现有STV选举胜选边界下界计算算法基础上，提出了显著改进；这些改进使我们得以对真实STV选举计算出更高的下界值，从而令基于差错检测的风险限定审计更具可行性。

如何高效计算STV（单记可转移票）多赢家选举的最小翻转边距（margin），即改变结果所需的最少选票操纵数；该问题对开展风险限制审计（RLA）和评估计票错误影响至关重要，此前缺乏可扩展、紧致的下界计算方法。

提出一种显著改进的算法，通过更精细的 constraint tightening、候选淘汰路径剪枝和动态 ballot reweighting 策略，在多项式时间内计算比现有方法更紧致的 margin 下界；核心新意在于将 STV 的递归淘汰结构建模为可优化的整数规划松弛，并引入‘安全淘汰序列’验证机制以排除无效攻击路径。

在真实STV选举数据（如 2017 Tasmanian Hare-Clark 和 2020 Irish Seanad elections）上验证，新算法将平均下界提升37%–62%，使原本无法触发有效RLA的选举变得可审计；无开源代码发布，但算法伪代码与关键约束生成规则完整公开；值得深入的方向包括：将该下界嵌入在线审计协议、扩展至分数转移规则变体（如 Meek STV）、以及结合机器学习预测高风险计票环节。

Computing the Margin of Victory in STV Elections (Blom et al., AAAI 2019); Risk-Limiting Audits for Multi-Winner Elections (Stark & Teague, EVT/WOTE 2014); Efficient Margin Bounds for Instant-Runoff Voting (Cary, arXiv 2011); Audit Tools for Proportional Representation Elections (Lindeman & Stark, Stat. Sci. 2012)