Algorithms measure how close elections are to ideal voting patterns
Nearly Group-Separable Elections
Computer Science and Game TheoryMultiagent Systems
Summary
Sometimes, elections don’t perfectly follow expected patterns that make the results easier to analyze or predict. This paper looks at how to measure how close an election is to a special kind of pattern called group-separability by counting how many changes are needed in voters’ rankings. The authors design efficient algorithms to do this, especially when only a few changes or candidates are involved. They also test their methods to see how well they work in practice. Their work helps understand and analyze elections that are nearly structured in ideal ways, which was a problem that wasn’t solved before.
What this means in practice
- •For voting system designers: Identify nearly ideal voting scenarios to improve vote counting and decision-making algorithms in complex elections.
- •For political data analysts: Analyze election data to detect how much voter preferences deviate from known structured domains for better election interpretation.
Authors
Piotr Faliszewski, Jan Jabrocki, Stanisław Kaźmierowski, Kristýna Pekárková, Šimon Schierreich, Ildikó Schlotter
Abstract
We study the problem of computing how close a given election is to being group-separable, measuring proximity by swaps of adjacent candidates in the votes. We also consider several other domains, including caterpillar group-separable, balanced group-separable, single-peaked, and single-crossing ones. Our problem is generally intractable, but we find practical FPT algorithms parameterized by the number of candidates or swaps. For the latter case, our algorithm applies to all domains characterized by finite forbidden subelections, resolving a well-established open problem. We supplement our theoretical findings with experimental analysis.