Query-efficient winner prediction in district-based elections

Koustav De; Debajyoti Kar; Swagato Sanyal

cs.DSSep 30, 2026

Query-efficient winner prediction in district-based elections

Authors: Koustav De, Debajyoti Kar, Swagato Sanyal

Organizations: 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

Abstract

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.

Figures & tables

Panel of Figure 1 — Figure 1: Division of $\mathcal{D}$ into various types of districts. $\mathcal{D}_{1},\mathcal{D}_{2},\mathcal{D}_{3}$ are the districts where votes are altered in the strategy $\mathcal{S}$ . $\mathcal{D}^{\prime}_{1},\mathcal{D}^{\prime}_{2},\mathcal{D}^{\prime}_{3}$ are the districts with large values of $h(d)$ guaranteed by Lemma 4 . The blue and green districts correspond to $\mathcal{D}^{\prime}_{W}$ and $\mathcal{D}^{\prime}_{C}$ , respectively.

Explore similar work

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

Sep 27, 2026cs.GT

Nearly Group-Separable Elections

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.

Piotr Faliszewski, Jan Jabrocki, Stanisław Kaźmierowski +3

AGH University of Krakow, Poland · University of Warsaw, Poland · Charles University, Czechia +3

Elections Maximum Independent Set Separability Candidate Proximity Operations Open Problems

Ask PDF

Apr 19, 2026cs.GT

Learning Unanimously Acceptable Lotteries via Queries

Many high-stakes AI deployments proceed only if every stakeholder deems the system acceptable relative to their own minimum standard. With randomization over a finite menu of options, this becomes a feasibility question: does there exist a lottery over options that clears all stakeholders' acceptability bars? We study a query model where the algorithm proposes lotteries and receives only binary accept/reject feedback. We give deterministic and randomized algorithms that either find a unanimously acceptable lottery or certify infeasibility; adaptivity can avoid eliciting many stakeholders' constraints, and randomization further reduces the expected elicitation cost relative to full elicitation. We complement these upper bounds with worst-case lower bounds (in particular, linear dependence on the number of stakeholders and logarithmic dependence on precision are unavoidable). Finally, we develop learning-augmented algorithms that exploit natural forms of advice (e.g., likely binding stakeholders or a promising lottery), improving query complexity when predictions are accurate while preserving worst-case guarantees.

Davin Choo, Paul W. Goldberg, Nicholas Teh

Harvard University, USA · University of Oxford, UK

Lotteries Majority Voting Algorithmic Cores Elicitation Worst-Case Random+1

Ask PDF