Nearly Group-Separable Elections

Speaker(s)

Šimon Schierreich

Affiliation

AGH University of Science and Technology

Language of the talk

English

Date

Oct. 15, 2026, noon

Information about the event

seminar online

Seminar

Seminar Algorithmic Economics

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, thereby resolving a well-established open problem. We supplement our theoretical findings with experimental analysis.

We even have a preprint available: https://arxiv.org/abs/2609.33535!

Authors: Piotr Faliszewski, Jan Jabrocki, Stanisław Kaźmierowski, Kristýna Pekárková, Šimon Schierreich, Ildikó Schlotter

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, thereby resolving a well-established open problem. We supplement our theoretical findings with experimental analysis.

We even have a preprint available: https://arxiv.org/abs/2609.33535!

Authors: Piotr Faliszewski, Jan Jabrocki, Stanisław Kaźmierowski, Kristýna Pekárková, Šimon Schierreich, Ildikó Schlotter