Advances in STV Margin Computation
摘要
Single transferable vote (STV) is a multi-winner preferential proportional electoral system. The margin is the smallest number of ballots that need to be manipulated to alter the set of winners. If we can compute the margin of an STV election, or a reasonable lower bound on the margin, we can use recent advances in auditing research to conduct a risk-limiting audit of the election's winners. Knowledge of the margin also provides insight into whether uncovered mistakes, or a known error rate in ballot interpretation, could have influenced the outcome. This paper presents substantial improvements on an existing algorithm for computing lower bounds on the margin of an STV election. These improvements allow us to compute higher lower bounds for real STV elections, making mismatch-based risk-limiting audits more practical.
正文
Single transferable vote (STV) is a multi-winner preferential proportional electoral system. The margin is the smallest number of ballots that need to be manipulated to alter the set of winners. If we can compute the margin of an STV election, or a reasonable lower bound on the margin, we can use recent advances in auditing research to conduct a risk-limiting audit of the election's winners. Knowledge of the margin also provides insight into whether uncovered mistakes, or a known error rate in ballot interpretation, could have influenced the outcome. This paper presents substantial improvements on an existing algorithm for computing lower bounds on the margin of an STV election. These improvements allow us to compute higher lower bounds for real STV elections, making mismatch-based risk-limiting audits more practical. Authors: Michelle Blom, Alexander Ek, Peter J. Stuckey, Vanessa Teague, Damjan Vukcevic Categories: cs.GT, cs.CR, cs.CY PDF: https://arxiv.org/pdf/2607.21178v1 Comment: 19 pages, accepted for E-Vote-ID 2026
标签
- category:cs.cr
- category:cs.cy
- category:cs.gt
- primary_category:cs.gt
- source:arxiv
- type:paper
扩展字段
{
"arxiv_id": "2607.21178v1",
"authors": [
"Michelle Blom",
"Alexander Ek",
"Peter J. Stuckey",
"Vanessa Teague",
"Damjan Vukcevic"
],
"categories": [
"cs.GT",
"cs.CR",
"cs.CY"
],
"comment": "19 pages, accepted for E-Vote-ID 2026",
"doi": null,
"entry_id": "https://arxiv.org/abs/2607.21178v1",
"pdf_url": "https://arxiv.org/pdf/2607.21178v1",
"primary_category": "cs.GT",
"search_query": "cat:cs.CR",
"updated_at": "2026-07-23T11:08:52+00:00"
}