Nearly Group-Separable Elections

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

cs.GTSep 27, 2026

Nearly Group-Separable Elections

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

Organizations: AGH University of Krakow, Poland · University of Warsaw, Poland · Charles University, Czechia · Czech Technical University in Prague, Czechia · ELTE Centre for Economic and Regional Studies, Hungary · Budapest University of Technology and Economics, Hungary

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.

Figures & tables

	—	$n$	$m$	$d$
$\mathrm{GS}$	?	?	$\mathcal{O}^{*}(3^{m})$ [T 4.3 ]	$\mathcal{O}^{*}(6^{d})$ [C 4.8 ]
$\mathrm{GS}\text{/}\allowbreak\mathrm{cat}$	${\mathrm{NP}}$ -c [T 3.1 ]	para- ${\mathrm{NP}}$ -c [T 3.1 ]	$\mathcal{O}^{*}(2^{m})$ [T 4.4 ]	$\mathcal{O}^{*}(8^{d})$ [C 4.8 ]
$\mathrm{GS}\text{/}\allowbreak\mathrm{bal}$	${\mathrm{NP}}$ -c [T 3.2 ]	?	$\mathcal{O}^{*}((2\sqrt{2})^{m})$ [T 4.4 ]	$\mathcal{O}^{*}(2^{2d^{2}})$ [T 4.9 ]
$\mathrm{Identity}$	${\mathrm{NP}}$ -c [BTT]	para- ${\mathrm{NP}}$ -c [DKNS]	$\mathcal{O}^{*}(2^{m})$ [BFGNR]	$\mathcal{O}^{*}(1.53^{d})$ [BFGNR]
$\mathrm{Antagonism}$	${\mathrm{NP}}$ -c [T 3.6 ]	para- ${\mathrm{NP}}$ -c [T 3.6 ]	$\mathcal{O}^{*}(2^{\mathcal{O}\mathopen{}\left(m\log m\right)})$ [T 4.2 ]	$\mathcal{O}^{*}(3.06^{d})$ [T 4.10 ]
$\mathrm{Separation}$	${\mathrm{NP}}$ -c [T 3.4 ]	$\mathcal{O}^{*}(2^{n})$ [T 3.3 ]	$\mathcal{O}^{*}(2^{m})$ [T 4.4 ]	$\mathcal{O}^{*}(5^{d})$ [T 4.10 ]

Table 1: An overview of our complexity and algorithmic results. Citations for known results are abbreviated as follows: BFGNR refers to ( Betzler et al. 2009 ) , BTT to ( Bartholdi III, Tovey, and Trick 1989 ) , DKNS to ( Dwork et al. 2001 ) , ELP to ( Erdélyi, Lackner, and Pfandler 2017 ) , and LPE to ( Lakhani, Peters, and Elkind 2019 ) .

Panel of Figure 1 — Figure 1: Results of our numerical experiments.

Figure 2: Probability of retaining winners (being successful) for

\mathrm{GS}\text{/}\allowbreak\mathrm{cat}

\mathrm{GS}\text{/}\allowbreak\mathrm{bal}

\mathrm{GS}

, and

\mathrm{Single}\text{-\allowbreak}\mathrm{Peaked}

projections.

Appendix figures & tables16 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 3 — Figure 3: Illustration for the proof of Theorem 3.2 . The figure depicts the prefect binary tree $T_{8n}$ . The candidate set displayed in the rectangle at the bottom of a given subtree contains those candidates that are mapped by $\varphi^{\star}$ to the leaves of the given subtree, with the size of this set written underneath.

Figure 4: Running time of our algorithms on 1000 elections sampled from the SP/Conitzer culture.

Figure 5: Running time of our algorithms on 1000 elections sampled from the SP/Walsh culture.

Figure 6: Running time of our algorithms on 1000 elections sampled from the Single-Crossing culture.

Figure 7: Running time of our algorithms on 1000 elections sampled from the GS/cat culture.

Figure 8: Running time of our algorithms on 1000 elections sampled from the GS/bal culture.

Figure 9: Running time of our algorithms on 1000 elections sampled from the Impartial culture.

Figure 10: Running time of our algorithms on 1000 elections sampled from the URN-0.2 culture.

Figure 11: Running time of our algorithms on 1000 elections sampled from the URN-0.5 culture.

Figure 12: Running time of our algorithms on 1000 elections sampled from the EUC/uni culture.

Absolute distance
	GS/cat					GS/bal					GS
Culture	avg $\pm$ std	med	min	max	share	avg $\pm$ std	med	min	max	share	avg $\pm$ std	med	min	max	share
NM-0.1	108.6 $\pm$ 4.7	109	99	115	0	80.3 $\pm$ 6.5	79.5	69	91	20	76.6 $\pm$ 4.9	75.5	69	85	80
NM-0.3	270.1 $\pm$ 14.0	274.5	245	284	0	270.2 $\pm$ 20.3	273	247	312	0	247.3 $\pm$ 18.2	248	218	275	100
NM-0.5	383.5 $\pm$ 21.4	384	358	415	80	448.5 $\pm$ 31.7	448	401	492	0	383.1 $\pm$ 21.4	382.5	358	415	20
NM-0.7	448.9 $\pm$ 16.6	447.5	421	475	100	578.3 $\pm$ 14.6	580	560	604	0	448.9 $\pm$ 16.6	447.5	421	475	0

Appendix

Table 2: Swap distance to the closest election of each group-separable domain for the elections of the map experiment (

8

candidates,

96

voters,

10

elections per culture). The top panel reports absolute distances, the bottom panel the same statistics normalized per voter (i.e., divided by

n=96

). The share column gives the percentage of elections for which the domain is the closest of the three (ties split evenly; the general group-separable domain is only credited when strictly closer than both special cases). In every row the domain with the largest share is set in bold; cells are shaded proportionally to their value relative to the maximum of their statistic over all cells (shares relative to

100\%

Absolute distance
	GS/cat					GS/bal					GS					SPeak
Culture	avg $\pm$ std	med	min	max	share	avg $\pm$ std	med	min	max	share	avg $\pm$ std	med	min	max	share	avg $\pm$ std	med	min	max	share
NM-0.1	101.2 $\pm$ 9.4	101	66	133	0	75.0 $\pm$ 9.9	75	44	112	0	70.9 $\pm$ 8.4	71	44	97	0	31.5 $\pm$ 6.7	31	13	55	100
NM-0.3	268.6 $\pm$ 15.1	268	222	313	0	260.2 $\pm$ 20.2	260	195	324	0	239.3 $\pm$ 17.1	239	190	293	0	179.6 $\pm$ 17.0	180	129	233	100
NM-0.5	383.2 $\pm$ 15.7	384	334	422	5.4	443.7 $\pm$ 24.7	443	354	519	0	381.7 $\pm$ 16.2	382	334	422	0.3	352.5 $\pm$ 22.9	352	272	436	94.3
NM-0.7	447.0 $\pm$ 12.3	448	401	481	99.3	582.3 $\pm$ 20.1	583	502	641	0	447.0 $\pm$ 12.3	448	398	481	0.6	513.5 $\pm$ 23.4	514	439	591	0.1

Appendix

Table 3: Swap distance to the closest election of each restricted domain (

8

candidates,

96

voters,

1000

elections per culture). The top panel reports absolute distances, the bottom panel the same statistics normalized per voter (i.e., divided by

n=96

). The share column gives the percentage of elections for which the domain is the closest of the four (ties split evenly; the general group-separable domain is only credited when strictly closer than both special cases). In every row the domain with the largest share is set in bold; cells are shaded proportionally to their value relative to the maximum of their statistic over all cells (shares relative to

100\%

Figure 13: The overall fraction of elections where

\mathrm{GS}\text{/}\allowbreak\mathrm{cat}

\mathrm{GS}\text{/}\allowbreak\mathrm{bal}

\mathrm{GS}

, or

\mathrm{Single}\text{-\allowbreak}\mathrm{Peaked}

is the closest structured domain.

Figure 14: An overview of closest domains per dataset and category.

Figure 15: An overview of closest domains per the number of candidates within an election.

Figure 16: Probability of retaining original winners (success rate) under the STV voting rule for

\mathrm{GS}\text{/}\allowbreak\mathrm{cat}

\mathrm{GS}\text{/}\allowbreak\mathrm{bal}

\mathrm{GS}

, and

\mathrm{Single}\text{-\allowbreak}\mathrm{Peaked}

projections.

Explore similar work

Jul 30, 2026cs.GT

Algorithms for Structured Elections under Thiele Voting Rules

We study the computational complexity of winner determination problems in approval-based committee elections under Thiele voting rules. These form a class of rules parameterized by a fixed weight vector that specifies how a voter's satisfaction depends on the number of approved candidates elected. We first analyze the structure of optimal solutions based on the sets of voters who approve each candidate---that is, how voters' approval ballots induce dependencies between candidates---revealing constraints on a winning committee under any fixed Thiele voting rule. Using this, we design FPT algorithms for Proportional Approval Voting (PAV) and other Thiele rules on a natural restricted domain known as the Voter Interval (VI) domain---that is, after a suitable ordering of voters, each candidate is approved by a consecutive interval of voters. In particular, we show that every Thiele rule on VI is FPT with respect to a parameter for which the problem is NP-hard on general instances, even when the parameter takes constant values. Our results advance the understanding of the computational complexity of PAV on Voter Interval instances, which remains one of the central open questions in this area. We further resolve two open questions from the literature on PAV (and other Thiele voting rules) by providing a polynomial-time algorithm for instances where each candidate is approved by at most two voters, and an FPT algorithm parameterized by the total score of a winning committee.

Alexandra Lassota, Krzysztof Sornat

TU Eindhoven, the Netherlands · AGH University, Poland

Elections Majority Voting

Ask PDF

Sep 30, 2026cs.DS

Query-efficient winner prediction in district-based elections

In a district-based election, N voters are partitioned into k districts, and each voter votes for one of m candidates. Each district elects a winner using the plurality rule (i.e. the candidate getting the largest number of votes is declared the winner, breaking ties as per some fixed rule), and the overall winner is determined by applying plurality to the district winners; we assume that there is a unique winner amongst the district winners. The margin of victory of such an election is the minimum number of votes that must be altered so that the current winner ceases to be the unique district winner. We study the problem of predicting the winner of a district-based election in the query complexity model, where one has query access to individual votes. The objective is to minimise the number of queries. This setting captures exit polling, where queries correspond to interviewing voters, and is closely related to problems in query complexity and property testing. Assuming that the margin of victory of the election is at least eps N, Dey, Kar and Sanyal (AAMAS 2023) gave algorithms for the case of two candidates with error probability del and query complexity tilde{O}(1/eps^6 log^2 1/del), which improves to tilde{O}(1/eps^4 log^2 1/del) under the additional assumption that district populations are balanced. Our main result is an adaptive randomised algorithm that, for an arbitrary district-based election and any error parameter del, with probability at least 1-del, predicts the winner correctly using tilde{O}(1/eps^2 log m/del log 1/del) queries. In particular, we improve the bounds of Dey et al. for arbitrary district populations and extend their results to any number of candidates. Furthermore, for constantly many candidates, our algorithm nearly matches a lower bound of Omega(1/eps^2 log 1/del) on the query complexity that holds even for two candidates and a single district.

Koustav De, Debajyoti Kar, Swagato Sanyal

Department of Computer Science and Engineering, Indian Institute of Technology Kharagpur, India · Department of Computer Science and Automation, Indian Institute of Science Bengaluru, India · School of Computer Science, University of Sheffield, United Kingdom

Elections Majority Voting O(\Bar{K}\Log N)$Equal Error Rate

Ask PDF

Apr 21, 2026cs.GT

Is Four Enough? Automated Reasoning Approaches and Dual Bounds for Condorcet Dimensions of Elections

In an election where

n

voters rank

m

candidates, a Condorcet winning set is a committee of

k

candidates such that for any outside candidate, a majority of voters prefer some committee member. Condorcet's paradox shows that some elections admit no Condorcet winning sets with a single candidate (i.e.,

k=1

), and the same can be shown for

k=2

. On the other hand, recent work proves that a set of size

k=5

exists for every election. This leaves an important theoretical gap between the best known lower bound

(k\geq 3)

and upper bound

(k \leq 5)

for the number of candidates needed to guarantee existence. We aim to close the gap between the existence guarantees and impossibility results for Condorcet winning sets. We explore an automated reasoning approach to tighten these bounds. We design a mixed-integer linear program (MILP) to search for elections that would serve as counter-examples to conjectured bounds. We employ a number of optimizations, such as symmetry breaking, subsampling, and constraint generation, to enhance the search and model effectively infinite electorates. Furthermore, we analyze the dual of the linear programming relaxation as a path towards obtaining a new upper bound. Despite extensive search on moderate-sized elections, we fail to find any election requiring a committee larger than size 3. Motivated by our experimental results in this direction, we simplify the dual linear program and formulate a conjecture which, if true, implies that a winning set of size 4 always exists. Our automated reasoning results provide strong empirical evidence that the Condorcet dimension of any election may be smaller than currently known upper bounds, at least for small instances. We offer a general-purpose framework for searching elections in ranked voting and a new, concrete analytical path via duality toward proving that smaller committees suffice.

Itai Zilberstein, Ratip Emin Berker, George Li +1

Carnegie Mellon University Pittsburgh, USA

Elections Majority Voting Upper Bounds Maximum Independent Set Candidate Mixed-Integer Programming

Ask PDF