Nearly Group-Separable Elections

Prelegent(ci)

Šimon Schierreich

Afiliacja

AGH University of Science and Technology

Język referatu

angielski

Termin

15 października 2026 12:00

Informacje na temat wydarzenia

seminar online

Seminarium

Seminarium „Ekonomia algorytmiczna”

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