Efficient computation of exact IRV margins

Michelle Blom, Vanessa Teague, Peter J. Stuckey, Ron Tidhar

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

3 Citations (Scopus)

Abstract

Computing the margin of victory (MOV) in an Instant Runoff Voting (IRV) election is NP-hard. In an IRV election with winning candidate w, the MOV defines the smallest number of cast votes that, if modified, result in the election of a candidate other than w. The ability to compute such margins has significant value. Arguments over the correctness of an election outcome usually rely on the size of the electoral margin. Risk-limiting audits use the size of this margin to determine how much post-election auditing is required. We present an efficient branch-and-bound algorithm for computing exact margins that substantially improves on the current best-known approach. Although exponential in the worst case, our algorithm runs efficiently in practice, computing margins in instances that could not be solved by the current state-of-the-art in a reasonable time frame.

Original languageEnglish
Title of host publicationFrontiers in Artificial Intelligence and Applications
Subtitle of host publicationECAI 2016 - 22nd European Conference on Artificial Intelligence 29 August–2 September 2016, The Hague, The Netherlands
EditorsGal A. Kaminka, Maria Fox, Paolo Bouquet, Eyke Hullermeier, Virginia Dignum, Frank Dignum, Frank van Harmelen
Place of PublicationAmsterdam Netherlands
PublisherIOS Press
Pages480-488
Number of pages9
ISBN (Electronic)9781614996729
ISBN (Print)9781614996712
DOIs
Publication statusPublished - 2016
Externally publishedYes
EventEuropean Conference on Artificial Intelligence 2016 - The Hague, Netherlands
Duration: 29 Aug 20162 Sep 2016
Conference number: 22nd
http://www.ecai2016.org/

Publication series

NameFrontiers in Artificial Intelligence and Applications
Volume285
ISSN (Print)0922-6389

Conference

ConferenceEuropean Conference on Artificial Intelligence 2016
Abbreviated titleECAI 2016
CountryNetherlands
CityThe Hague
Period29/08/162/09/16
Internet address

Cite this