Paper deep dive
Query-efficient winner prediction in district-based elections
Koustav De, Debajyoti Kar, Swagato Sanyal
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 92%
Last extracted: 10/2/2026, 9:17:19 AM
Summary
This paper addresses the problem of predicting the winner in district-based elections using a query complexity model, where the goal is to minimize the number of voter queries (exit polling) while maintaining a low error probability. The authors propose an adaptive randomized algorithm that improves upon previous bounds by Dey, Kar, and Sanyal. Specifically, they achieve a query complexity of O~(1/eps^2 log(m/delta) log(1/delta)) for arbitrary district populations and any number of candidates, which nearly matches the theoretical lower bound for constant candidates. The work connects election prediction to query complexity and property testing.
Entities (8)
Relation Signals (6)
This paper → improvesboundof → Dey, Kar and Sanyal
confidence 98% · Our main result is an adaptive randomised algorithm... In particular, we improve the bounds of Dey et al. for arbitrary district populations
Query Complexity → appliesto → District-based elections
confidence 97% · We study the problem of predicting the winner of a district-based election in the query complexity model
Dey, Kar and Sanyal → publishedalgorithmfor → Query-efficient winner prediction
confidence 95% · 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)
Margin of Victory → determinesdifficultyof → Winner Prediction
confidence 93% · Intuitively speaking, winner-prediction is more difficult for close elections that correspond to low margins of victory.
Bhattacharyya and Dey → proposedalgorithmfor → Single-district winner prediction
confidence 92% · Bhattacharyya and Dey proved the following result... There exists a non-adaptive query algorithm... outputs m estimates
Exit Polling → modeledby → Query Complexity Model
confidence 90% · This setting captures exit polling, where queries correspond to interviewing voters
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2610.00577v1
- Canonical: https://arxiv.org/abs/2610.00577v1
Trouble viewing inline? Open PDF directly →
Full Text
157,464 characters extracted from source content.
Expand or collapse full text
Query-efficient winner prediction in district-based elections Koustav De †thanks: koustavde7@kgpian.iitkgp.ac.in Affiliation: Department of Computer Science and Engineering, Indian Institute of Technology Kharagpur, India Debajyoti Kar †thanks: debajyotikar@iisc.ac.in Affiliation: Department of Computer Science and Automation, Indian Institute of Science Bengaluru, India Swagato Sanyal †thanks: swagato.sanyal@sheffield.ac.uk Affiliation: 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 εN N, Dey, Kar and Sanyal (AAMAS 2023) gave algorithms for the case of two candidates with error probability δ and query complexity O~(1ε6log21δ) O( 1 ^6 ^2 1δ), which improves to O~(1ε4log21δ) O( 1 ^4 ^2 1δ) 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 δ∈(0,1)δ∈(0,1), with probability at least 1−δ1-δ, predicts the winner correctly using O~(1ε2logmδlog1δ) O( 1 ^2 mδ 1δ) queries. In particular, we quantitatively improve the bounds of Dey, Kar and Sanyal for arbitrary district populations and extend their results to any number of candidates. Furthermore, for the special case of a constant number of candidates, our algorithm nearly matches a lower bound of Ω(1ε2log1δ) ( 1 ^2 1δ) on the query complexity that holds even for two candidates and a single district. Keywords and phrases Sampling algorithms, Query algorithms, Sub-linear algorithms, District-based Election, Winner Prediction, Margin of Victory 1 Introduction In a district-based election E, there are N voters partitioned into k districts. Each voter votes for some candidate in a set of m candidates denoted by C. The winner of each district is defined to be the candidate getting the largest number of votes in that district. The winner of E is defined to be the candidate who wins in the largest number of districts. All ties are broken in an arbitrary but fixed way. In this paper, we are interested in predicting the winner of a district-based election in the query model, where an algorithm can query any voter and know their vote. The queries may be made adaptively (i.e. the decision which voter to query next may depend on the previous query outcomes) and using randomness. The objective is to minimise the number of queries made while successfully predicting the winner with probability at least 1−δ1-δ, for a given error parameter δ∈(0,1)δ∈(0,1). We assume that in the given election the winner is unambiguous, i.e., the winner wins in strictly more districts than any other candidate. We assume that the parameters N,m,kN,m,k as well as the populations of the districts are known. We call this problem δ-Winner Prediction. The margin of victory of an election E, denoted by (E) MOV(E), is the minimum number of votes that need to be altered in E so that the current winner ceases to win in strictly more districts than at least one other candidate, i.e., ceases to be the unambiguous district winner. Note that it is possible for the current winner to continue being the winner in the altered election depending on the tie-breaking rule. The margin of victory [7] is a measure of robustness of an election. We would like to bound the query complexity of our predictor in terms of (E) MOV(E). Intuitively speaking, winner-prediction is more difficult for close elections that correspond to low margins of victory. On the other hand, for elections with high margins of victory, one can hope that few well-chosen samples from the population may potentially contain enough statistical information to reliably predict its winner. We note that we do not assume that the predictor knows (E) MOV(E). 1.1 Motivation. δ-Winner Prediction is motivated by a range of applications. 1.1.1 Social choice and voting theory. The setup described above abstracts a common feature of district-based electoral systems, such as those used in countries including the US, the UK, and India: voters are grouped geographically, local outcomes are determined within districts or constituencies, and these local outcomes play a central role in determining the overall political outcome. Our model is not intended to capture all institutional details of these systems, but rather to study the algorithmic problem of winner prediction under this hierarchical aggregation structure. The query model can be viewed as an idealised abstraction of exit polling, in which each query corresponds to interviewing a randomly chosen voter from a chosen district. Our algorithm is adaptive; in each adaptive round we check whether the query outcomes so far are statistically sufficient to predict the winner with high confidence, or we need to make more queries. However, the number of adaptive rounds is only logarithmic in the query complexity of our algorithm. Besides, in order for us to bound the query complexity in terms of (E) MOV(E) which is unknown to the algorithm, adaptivity is inevitable. The model also captures a broader class of hierarchical consensus mechanisms in which individual agents form local decisions that are subsequently aggregated into a global outcome. It ties naturally to the general election-prediction problem for different voting rules which, besides elections, is relevant for applications to post-election audits and social surveys (see [7], [17] and the references therein). More broadly, our work has the potential to motivate the study of query-efficient winner prediction for district-based elections under standard voting rules other than plurality, such as approval voting, Borda count, Copeland’s rule, maximin, or the Schulze rule. Next, we discuss connections of this problem with two fields within computational complexity theory: query complexity and property testing. 1.1.2 Query complexity. A randomised query algorithm computing a Boolean function f:0,1n→0,1f:\0,1\^n→\0,1\ on n bits with error probability δ is given query access to the input bits of f, and for every input bit string x∈0,1nx∈\0,1\^n outputs f(x)f(x) with probability at least 1−δ1-δ when run on x. The aim of the field of query complexity is to study the power and limitation of query algorithms, to relate various query complexity measures with one another and to determine the query complexity of specific Boolean functions [8]. A class of Boolean functions that plays a central role in query complexity is the composition of an outer Boolean function f:0,1n→0,1f:\0,1\^n→\0,1\ and an inner Boolean function g:0,1ℓ→0,1g:\0,1\ →\0,1\, denoted by f∘g:0,1nℓ→0,1f g:\0,1\^n →\0,1\, defined as: f∘g(x(1),…,x(n))=f(g(x(1)),…,g(x(n)))f g(x^(1),…,x^(n))=f(g(x^(1)),…,g(x^(n))). The query complexity of composed functions has seen a long line of research [3, 6, 11, 5, 4, 9, 23], and the study of query complexity of specific composed functions such as NAND tree [21, 22], recursive majority [18, 15, 1] and Tribes [16] has contributed immensely to the development of the field. Consider the δ-Winner Prediction problem in which i) there are only two candidates 00 and 11, i) there is an odd number k of districts, and i) the population of each district is the same odd number, namely N/kN/k. In this special case, the problem is exactly designing a randomised query algorithm with error probability δ for the composed Boolean function k∘N/k Maj_k Maj_N/k, where for an odd positive integer t, t Maj_t denotes the majority function on t bits. It follows from existing lower bounds on the query complexity of composed functions [2, 14] that any randomised query algorithm computing k∘N/k Maj_k Maj_N/k with error probability 1/31/3 makes Ω(N) (N) queries in the worst case. [17] shows that it is possible to sidestep this lower bound with high probability when the margin of victory of the given election is large. This paper improves the query complexity. This paper further extends the upper bound first to allow for arbitrary district populations (which is a generalisation of function composition where multiple inner functions are used, which are in this case majority functions on varying number of bits), and to the non-Boolean setting of arbitrary number of candidates. 1.1.3 Property testing. In property testing [12, 13] we study the problem of deciding whether a large object (a Boolean string, a Boolean function or a graph) satisfies some property, given query access to the object. A property is identified with the subset of objects satisfying the property. For example, the property of monotonicity of Boolean functions is defined to be the set of all monotone Boolean functions. It is assumed that the given object is either in the property or far from being in the property. For a distance parameter η, a Boolean function/graph is called η-far from a property if the minimum fraction of entries in the truth table/adjacency matrix that need to be altered to make it belong to the property is at least η. The objective we seek to optimise is the number of queries made to the object. Specifically, we wish to bound the query complexity in terms of the distance parameter. A property is said to be testable if there exists a tester which can distinguish between the cases of the input object being in the property and the input object being η-far from the property, by making number of queries dependent only on the distance parameter η (and independent of the size of the object) and with error probability 1/31/3. Once again consider the δ-Winner Prediction where there are only two candidates, 00 and 11, and an odd number of districts all with odd populations (so that there is never a tie). Consider the property of 00 being the winner. Our objective is to decide whether a given election is in the property. Note that the distance of an election E where 11 wins from this property is exactly (E) MOV(E). However, there is one distinction between our formulation of the winner-prediction problem and the traditional property-testing setting: in our analysis we assume that even if the given election is in the property (i.e., the winner is 00), the margin of victory is still large. In other words, we assume that the given object (election) is far from the boundary of the property regardless of whether or not it is in the property. If we suitably extend the notion of testability in this setting, our result implies that the property of 00 being the winner is testable.11 1 also shown by [17] for two candidates. Furthermore, we extend our tester to handle multiple candidates, and maintain testability for any constant number of candidates. 1.2 Previous work The problem δ-Winner Prediction was introduced by Dey, Kar and Sanyal [17], who proposed predictors with query complexity bounded in terms of (E) MOV(E). Dey and Mitra [19] studied the reliability of a given survey result and their consistency with the actual election outcome. Mitra [20] studied agent-based simulation of district-based elections, and applied their model to reproduce results of elections held in India and the US. Prior to the introduction of this problem by Dey, Kar and Sanyal, Bhattacharyya and Dey [7] undertook a theoretical study of the task of predicting winners and estimating margins of victory of elections for various voting rules. In particular they designed a winner-predictor for the special case of a single-district election in which the winner is determined by an application of the plurality voting rule (i.e., the candidate getting the largest number of votes is the winner, breaking ties suitably).22 2 This is a special case of a district-based election where there is only one district. The margin of victory for this voting rule is, up to a constant factor, the difference between the numbers of votes obtained by the winner and the runner-up. Bhattacharyya and Dey proved the following result. Lemma 1 ([7]). There exists a non-adaptive query algorithm that, for any given γ,δ∈(0,1)γ,δ∈(0,1) and query access to a district-based election E, makes q(γ,δ)=O(1γ2log1δ)q(γ,δ)=O( 1γ^2 1δ) queries and outputs m estimates θ^CC∈\ θ_C\_C of the true fractions of votes θCC∈\ _C\_C received by the m candidates satisfying: ∀C∈,|θC−θ^C|≤γ.∀ C ,| _C- θ_C|≤γ. with probability at least 1−δ1-δ. Let the margin of victory of the single-district election be at least εN N. One can predict its winner with probability at least 1−δ1-δ by simply invoking Lemma 1 with parameters γ<ε/2γ< /2 and δ, and returning the candidate with the largest predicted number of votes; the algorithm uses O(1ε2log1δ)O( 1 ^2 1δ) queries. Notably, the query complexity of the algorithm is independent of the population size N and the number of candidates m. It is not difficult to show that this algorithm can be adapted so that the knowledge of ε is not needed, and yet with probability at least 1−δ1-δ it makes O~(1ε2log1δ) O( 1 ^2 1δ) queries33 3 Throughout the paper, the notation O~ O and Ω~ hide factors polylogarithmic in 1/ε1/ and log1/δ 1/δ. and returns the correct winner. The idea is to iteratively use Lemma 1 to compute the fractional vote share estimates for various settings of γ starting from a large value of γ (say γ=1/2γ=1/2) and decreasing it by a factor of 22 in each step, until the difference between the two leading estimates is large compared to γ. In order for all the estimates to be correct with high probability, the δ parameter for each invocation will have to be set lower, thereby tolerating a blow-up in the query complexity by a factor of log(1/ε) (1/ ). An analysis of this algorithm shows that comparing the difference of the two leading estimates with the parameter γ reveals whether the estimates can be relied on for the winner-prediction or whether more queries are necessary. Bhattacharyya and Dey also observed that a matching lower bound of Ω(1ε2log1δ) ( 1 ^2 1δ) for the query complexity of this problem follows from standard facts in statistics for ε=Ω(1/N) = (1/ N), even when there are only two candidates. As a single-district election is a special case of a district-based election where there is only one district, the above lower bound holds for δ-Winner Prediction. Dey, Kar and Sanyal proved the following results. Theorem 1 (Dey, Kar and Sanyal [17]). Consider the δ-Winner Prediction problem when there are two candidates. Let the input election E satisfy (E)≥εN MOV(E)≥ N. (i) Assume that the population of each district is within a constant factor of the average population N/kN/k. Then, there exists an algorithm that, with probability at least 1−δ1-δ, makes at most O~(1ε4log21δ) O( 1 ^4 ^2 1δ) queries and outputs the true winner. (i) Assume that the population of each district is arbitrary. Then, there exists an algorithm that, with probability at least 1−δ1-δ, makes at most O~(1ε6log21δ) O( 1 ^6 ^2 1δ) queries and outputs the true winner. The authors also proved a matching lower bound for a natural class of algorithms; see Section 2.1 for a discussion. 1.3 Our result In this paper, we quantitatively improve the result of Dey, Kar and Sanyal and refine it by relaxing several assumptions. In particular, we propose an algorithm with optimal query complexity (up to logarithmic factors) for arbitrary district populations when the number of candidates m is a constant. Theorem 2. Consider the general δ-Winner Prediction problem with arbitrary district populations and arbitrary number of candidates. There exists an algorithm A with the following guarantee: for every ε,δ∈(0,1) ,δ∈(0,1) if the input election E satisfies (E)≥εN MOV(E)≥ N then with probability at least 1−δ1-δ, A makes at most O~(1ε2logmδlog1δ) O ( 1 ^2 mδ 1δ ) queries on E and outputs the true winner of E. In particular for the special case of a constant number of candidates, our algorithm has query complexity O~(1ε2log21δ) O( 1 ^2 ^2 1δ), which is optimal up to factors polylogarithmic in 1/ε1/ and log1/δ 1/δ. 2 Proof ideas In this section we discuss the ideas and techniques underlying our proof. We first discuss the high-level ideas of the proof of Theorem 1 by Dey, Kar and Sanyal. We then discuss the barriers that their approach faces in reducing the query complexity as well as relaxing the assumptions (two candidates, equal district populations). Finally we discuss the new technical ingredients that we develop in this work to bypass these obstacles and prove our main theorem. Throughout this section, we assume that ε is known. This assumption is removed by iteratively guessing and affirming the guess, along the lines of the ideas outlined in Section 1.2. For simplicity, throughout this section we assume that δ is a constant (e.g. 1/31/3). A crucial ingredient in all the proofs is the single-district winner predictor by Bhattacharyya and Dey. It is a randomised algorithm and errs with some probability. However, in this overview we assume that it always outputs correctly as long as the number of votes queried is large enough with respect to the margin of victory. In the actual proof, however, we need to set the δ parameter of this algorithm low enough so that all its invocations can be relied on. This leads to a logarithmic blow-up in its query complexity, which we hide in the O~ O notation. We also assume for simplicity in this section that ε=Ω(1k) = ( 1k). We note here that arguably the most significant technical challenge that we deal with in this work is to handle arbitrary number of candidates. The mathematical structure of elections with more than 22 candidates (even 33 candidates) and high MOV turns out to be significantly deeper and more subtle than elections with only two candidates and bounded MOV. We outline the techniques that we develop and employ to handle arbitrary number of candidates in Section 2.4. Until before Section 2.4 we discuss other challenges that we navigate and to keep the discussion there focussed we assume that we have only 22 candidates. 2.1 Proof ideas of Theorem 1 Recall that in Theorem 1 there are only two candidates. Let W1,…,WkW_1,…,W_k be the district winners. A key technical lemma (Lemma 3) that they showed asserts that the margin of victory of the single-district election E′E defined by W1,…,WkW_1,…,W_k is Ω(εk) ( k). We note that Lemma 3 also holds for an arbitrary number of candidates. The winner of E is the same as the winner of E′E , and (E′)=Ω(εk) MOV(E )= ( k). Hence, if we had query access to the WiW_is, we could have sampled O~(1/ε2) O(1/ ^2) of them and used the predictor by Bhattacharyya and Dey to output a prediction. Since we do not have direct access to the WiW_is, we instead predict WiW_i by running the predictor by Bhattacharyya and Dey on the single-district election defined by the i-th district, which we denote by EiE_i. But the single-district predictor needs a lower bound on the MOV to output reliably. What guarantee do we have on (Ei) MOV(E_i)? The EiE_is with (Ei)≪εNk MOV(E_i) Nk can be shown to not matter much, i.e., it does not hurt the reliability of the final prediction to a significant degree if the predicted winner of EiE_i is wrong. This is a consequence of the lower bound of εN N on the margin of victory of the overall election E. So, while estimating the winner of EiE_i, we assume that (Ei)=Ω(εNk) MOV(E_i)= ( Nk). However, the query complexity of the single-district predictor within the i-th district depends on the (Ei) MOV(E_i) viewed as a fraction of the district population. 2.1.1 Part 1. Here, we additionally assume that the district populations are within a constant factor of N/kN/k. In this case, the bound (Ei)=Ω(εNk) MOV(E_i)= ( Nk) implies that (Ei) MOV(E_i) is at least Ω(ε) ( ) fraction of the district population. Thus, the single-district predictor samples O~(1/ε2) O(1/ ^2) within the i-th district to predict WiW_i. In this case the final predictor takes the following form: 1. Sample ℓ1:=O~(1/ε2) _1:= O(1/ ^2) districts. Let the corresponding single-district elections be Ei1,…,Eiℓ1E_i_1,…,E_i_ _1. 2. For each j∈1,…,ℓ1j∈\1,…, _1\, predict the winner of EijE_i_j by using the single-district predictor by Bhattacharyya and Dey assuming that (Eij)=Ω(εNk) MOV(E_i_j)= ( Nk). Let the predicted winner be W~j W_j. This step involves sampling and querying ℓ2:=O~(1/ε2) _2:= O(1/ ^2) votes from each sampled district. 3. Output the winner of the single-district election defined by W~1,…,W~ℓ1 W_1,…, W_ _1. The overall query complexity is ℓ1ℓ2=O~(1/ε4) _1 _2= O(1/ ^4). 2.1.2 Part 2. However, when the district populations are arbitrary, a lower bound (Ei)=Ω(εNk) MOV(E_i)= ( Nk) does not imply that (Ei) MOV(E_i) is at least Ω(ε) ( ) fraction of the population of the i-th district (denoted by nin_i). Nevertheless the authors could show that the number of districts for which (Ei)=Ω(ε2ni) MOV(E_i)= ( ^2n_i) is at least k(12+Ω(ε))k( 12+ ( )). The intuition behind this result is that if (Ei)=Ω(εNk) MOV(E_i)= ( Nk) and (Ei)≪ε2ni MOV(E_i) ^2n_i, then ni≫N/εkn_i N/ k, i.e., the population of the i-th district is far larger than the average population of a district. Thus, the number of such districts is ≪εk k. In this case we need to invoke Bhattacharyya and Dey’s algorithm for an MOV lower bound of Ω(ε2ni) ( ^2n_i); so O~(1(ε2)2)=O~(1ε4) O( 1( ^2)^2)= O( 1 ^4) votes are queried from each sampled district. The query complexity of the overall predictor is thus O~(1ε2⋅1ε4)=O~(1ε6) O( 1 ^2· 1 ^4)= O( 1 ^6). 2.2 Reducing the query complexity Now we outline our key technical ingredient that enables us to reduce the query complexity to a quadratic dependence on 1/ε1/ (up to logarithmic factors). To keep the discussion focused we assume that there are only two candidates A and B, and the population of each district is within a constant factor of N/kN/k. Removing these assumptions will need additional technical ideas and will be discussed in subsequent sections. How tight is the bound in Theorem 1(i)? In particular, can we reduce either ℓ1 _1 or ℓ2 _2 in the previous section? Dey, Kar and Sanyal proved that neither ℓ1 _1 nor ℓ2 _2 can be reduced while still preserving the performance guarantee of the algorithm, leading to a lower bound of Ω~(1/ε4) (1/ ^4) for the class of algorithms that fit the template of the algorithm presented in the previous section with the freedom to set ℓ1 _1 and ℓ2 _2. An analysis of elections EβE_β discussed next also recovers this lower bound. Consider the following election EβE_β, parameterised by a parameter β∈(0,1)β∈(0,1). EβE_β The winner wins in k(12+εβ)k( 12+ ^β) districts. In each of those districts, the MOV of the corresponding single-district election is ε1−β⋅Nk ^1-β· Nk. In each of the remaining districts in which the other candidate wins, we don’t specify the margin of victory; in particular we allow the MOV to be as small as 11. (Eβ) MOV(E_β) can be easily verified to be εN N. The MOV of the single-district election defined by the district winners is εβk ^βk; so the algorithm in Section 2.1 must set ℓ1 _1 to Θ~(1ε2β) ( 1 ^2β). In particular if β≈1β≈ 1, ℓ1=Θ~(1ε2) _1= ( 1 ^2). Now, in order to reliably predict the winner for the districts where the overall election winner wins, ℓ2 _2 must be set to Θ~(1/ε2(1−β)) (1/ ^2(1-β)). Note that if β≈0β≈ 0, ℓ2 _2 needs to be set to Θ~(1ε2) ( 1 ^2). With the aforementioned settings of ℓ1 _1 and ℓ2 _2, irrespective of the accuracy of the predictions for the districts in which the true winner does not win, we will have enough statistical information to correctly predict the winner. As discussed above, the settings of ℓ1 _1 and ℓ2 _2 in the algorithm in Section 2.1 cannot be reduced in general. However, for any β, if we are allowed to set ℓ1 _1 and ℓ2 _2 depending on β, the overall query complexity is at most Θ~(1ε2β⋅1ε2(1−β))=Θ~(1ε2) ( 1 ^2β· 1 ^2(1-β))= ( 1 ^2). EβE_β demonstrates a trade-off between the MOV of the election defined by the WiW_is, and that of the elections defined by the districts that matter for the prediction task, which can potentially be exploited to reduce the query complexity. The following lemma establishes such a trade-off for any district-level election with MOV at least εN N. Lemma 2. Let E be a district-level election with two candidates satisfying (E)≥εN MOV(E)≥ N and 4/k≤ε≤1/24/k≤ ≤ 1/2. Then there exists an α∈[ε8,12]α∈[ 8, 12] such that there are at least k(12+α)k( 12+α) districts each with MOV at least Ω~(εNαk) ( Nα k) in which the overall winner wins. Lemma 2 is a simplified version of a more general lemma (Lemma 4) which is used to prove Theorem 2. Lemma 4 handles general district-based elections with arbitrary number of candidates, is integrated with structural properties of such elections and is more technical. Lemma 4 is discussed in Section 2.4. For a proof of Lemma 2 see Appendix A. Lemma 2 enables a cheaper algorithm as follows. Let t:=εαt:= α, where α is given by Lemma 2. First, assume that the α is known to the algorithm. In that case, we set ℓ1 _1 to Θ~(1/α2) (1/α^2), ℓ2 _2 to Θ~(1/t2) (1/t^2) and run the algorithm in Section 2.1. We’ve set ℓ2 _2 large enough to correctly predict the winners of each of the districts mentioned in Lemma 2. Since their fraction is at least 12+α 12+α, in our sampled election more than half of the predicted winners would be the actual overall winner, and hence the output will be correct. The overall query complexity is O~(1α2⋅1t2)=O~(1ε2) O( 1α^2· 1t^2)= O( 1 ^2). But the algorithm does not know α. To deal with that, it breaks up the range [ε/8,1/2][ /8,1/2] into O(log1ε)O( 1 ) intervals [ε/8,ε/4),[ε/4,ε/2),…,[1/4,1/2][ /8, /4),[ /4, /2),…,[1/4,1/2] (assuming ε to be an inverse power of 22). For each of these intervals, it guesses α to be in that interval and runs the aforementioned algorithm. This adds an additional factor of O(log(1/ε))O( (1/ )) to the query complexity. A correct guess would lead to the correct prediction. But can a wrong guess lead to a wrong prediction? The key insight here is that the Bhattacharyya-Dey single-district winner predictor can also detect whether the number of queries into a district is insufficient to reliably predict its winner, or whether the number of confident predictions of district winners is too small to predict the overall winner reliably based on them (see the discussion in Section 1.2). So the algorithm can be made to discard guesses of α if the query outcomes do not present clear statistical evidence of a candidate winning more than half of the districts. 2.3 Handling arbitrary district populations The improvement outlined in the preceding section hinges on the following observation: an MOV of Ω~(tNk) (t Nk) for a district is indeed t-fraction of the district population, as the population of each district is within a constant factor of N/kN/k. Thus, sampling O~(1/t2) O(1/t^2) votes from such a district suffices to predict its winner reliably. While Lemma 2 holds for arbitrary district populations, the aforementioned argument fails when the district populations are arbitrary. To tackle this, the first step is to ignore districts which are too large: with population ≫Nεk N k as their total number is ≪εk k, which is too small to matter. Next, the remaining districts are grouped into classes based on their populations; within each class (except one) all districts have their populations within a factor of 22 of one another. We have the set of districts 0D_0 with populations at most N/kN/k, and for each i in [1,…,≈log(1/ε)][1,…,≈ (1/ )] we define a set iD_i of districts with population lying in (2iNk,2i+1Nk]( 2^iNk, 2^i+1Nk].44 4 We remark that in the formal proof the notations used are slightly different from the ones used in this overview. Now for each i we estimate the number of districts in iD_i that satisfy the conditions in Lemma 2: bounded MOV and the winner being the same as the overall winner of the district-level election, within an additive error of O(αlog(1/ε)k)O( α (1/ )k). Since there are ≈log(1/ε)≈ (1/ ) district classes, the sum of these estimates will be an estimate of the total number of districts (leaving out the districts with very large populations as explained before) that satisfy the Lemma conditions within an additive O(αk)O(α k). For a specific i, the number of districts in iD_i is at most O(k/2i)O(k/2^i); so the tolerable error of O(αlog(1/ε)k)O( α (1/ )k) is at least a Ω(αlog(1/ε)2i) ( α (1/ )2^i) fraction of the number of such districts. So it suffices to sample at most O~(log2(1/ε)α222i) O( ^2(1/ )α^22^2i) such districts. Note that here we save a factor of 22i2^2i compared to previous section. However, for a district in iD_i, the MOV lower bound of Ω~(tNk) (t Nk) is Ω~(t2i) ( t2^i) fraction of its population; so we need to query O~(22it2) O( 2^2it^2) votes from each sampled district in iD_i, which is a factor of 22i2^2i worse than the previous section. Hence, the total number of queries for each i is O~(log2(1/ε)α222i⋅22it2)=O~(1/ε2) O( ^2(1/ )α^22^2i· 2^2it^2)= O(1/ ^2). Repeating it for each population class with appropriate settings of the error parameter adds an additional multiplicative overhead of O(log(1/ε))O( poly (1/ )) to the query complexity. We would like to contrast our approach with that of Dey, Kar and Sanyal; they incurred an overhead of a factor of Ω(1/ε2) (1/ ^2) while going from part 1 to part 2 of Theorem 1 by tolerating a deterioration of the MOV guarantee of the single-district elections defined by the districts with arbitrary population. We instead incur an overhead of only O(log(1/ε))O( poly (1/ )) by treating each population class differently. 2.4 Handling more than two candidates As mentioned before, the most significant technical challenge that we faced is to extend our proof to handle more than 22 candidates. All the approaches discussed so far crucially rely on a property of a district-based election involving 22 candidates: to win an election it is both necessary and sufficient to win in more than half the districts. All the algorithms discussed so far focus on finding a candidate who wins in more than half the districts, and declare such a candidate the winner. However, this characterisation does not generalise to m>2m>2: while it is necessary for the winner to win in at least k/mk/m districts, it is no longer a sufficient condition to win the election. So, what condition should an algorithm look for? We look for the condition implied by the definition of winner: W is the winner if and only if for every other candidate C, W wins in more districts than C. So, at a high level the algorithm finds a candidate W that satisfies the above condition. Note that in Theorem 2 the query complexity has a logarithmic dependence on m, and it is a good time to outline the source of this factor. As per the strategy hinted above, pairwise comparisons between candidates are involved. This will translate to accurately estimating various statistics for all the candidates, using the Bhattacharyya-Dey algorithm. In order for all of those estimates to be reliable, the error parameter δ needs to be inversely proportional to m. Since the query complexity of the Bhattacharyya-Dey algorithm has a logarithmic dependence on 1/δ1/δ, our algorithm ends up suffering an extra logm m factor in its query complexity. For the rest of this section, we fix two candidates W and C, and explain at a high level what kind of evidence our algorithm gathers that certifies that W wins in more districts than C. We also switch back to the equal district population setting to focus on the technical ideas developed to handle more than 22 candidates; arbitrary district populations are handled by integrating these ideas with the ones discussed in the preceding section. Informally speaking, for a parameter α∈(0,1)α∈(0,1), call a district d to be (α,W)(α,W)-rich if W is the winner of d and no other candidate can be made the winner by changing O~(εNαk) O( Nα k) votes, and call d to be (α,C)(α,C)-poor if C is either the winner of d or can be made the winner by changing O~(εNαk) O( Nα k) votes. Let R(α,W)R(α,W) and P(α,C)P(α,C) stand for the numbers of (α,W)(α,W)-rich and (α,C)(α,C)-poor districts respectively. We note that these notations are only for this overview, and are not used in the formal proof. Observe that R(α,W)R(α,W) is a lower bound on the number of districts in which W wins, and P(α,C)P(α,C) is an upper bound on the number of districts in which C wins. So, if for some value of α we can certify that R(α,W)>P(α,C)R(α,W)>P(α,C), then that will also certify that W wins in more districts than C. This is enabled by Lemma 4 which, as mentioned before, is a generalisation of Lemma 2. At a high level, Lemma 4 asserts that there exists an α=Ω(ε)α= ( ) (which may depend on W and C) such that if W is indeed the true winner of the election then R(α,W)−P(α,C)=Ω(αk)R(α,W)-P(α,C)= (α k). For simplicity, suppose that α is known to the algorithm; this assumption can be removed along the lines of the ideas discussed in Section 2.2. O~(α2ε2) O( α^2 ^2) queries into a district suffice to figure out whether it is (α,W)(α,W)-rich or (α,C)(α,C)-poor (note that the assumption that all district populations are within a constant factor of N/kN/k is used here). We can use it simultaneously for all m candidates without the query complexity scaling with m, using the Bhattacharyya-Dey algorithm. In order to estimate R(α,W)R(α,W) and P(α,C)P(α,C) within an additive O(αk)O(α k), it is sufficient to sample O~(1α2) O( 1α^2) districts. However this is for a fixed W and C. If we want our estimates to be reliable for all candidates with high probability, it is sufficient for the estimate for each candidate to be accurate with error probability inversely proportional to m: as discussed before this blows up the number of districts sampled to O~(logmα2) O( mα^2). In total, the query complexity sums up to O~(α2ε2⋅logmα2)=O~(logmε2) O( α^2 ^2· mα^2)= O( m ^2). Proving Lemma 4 involves a deep analysis of the structure of elections with ≥εN MOV≥ N. Altering votes optimally to make C win in at least as many districts as W wins in, potentially involves three different kinds of districts: • 1D_1: Districts where neither W nor C wins in the original election, and C is made the winner by altering fewest possible votes. Doing this for one such district reduces the difference of votes between W and C by 11. • 2D_2: Districts where W wins in the original election, and C is made the winner by altering fewest possible votes. Doing this for one such district reduces the difference of votes between W and C by 22. • 3D_3: Districts where W wins in the original election, and a candidate other than W and C is made the winner by altering fewest possible votes. Doing this for one such district reduces the difference of votes between W and C by 11. Lemma 4 is derived by a careful study of the properties of these three sets of districts, the optimality of the strategy under consideration and the guarantee ≥εN MOV≥ N of the election. 3 Organisation For ease of exposition, we first present our result for the special case of balanced district populations. Towards this, in Section 4 we present structural results, some of which hold only for elections with balanced district populations. In Section 5 we present our algorithm for balanced district populations. In Section 6 we refine and extend the structural results of Section 4 to elections with arbitrary district populations. Finally, we present the proof of Theorem 2 (for arbitrary district-based elections) in Section 7. 4 Structural results for election with (E)≥εN MOV(E)≥ N In this section, we derive certain structural properties of an election E satisfying (E)≥εN MOV(E)≥ N that we shall later leverage in designing our algorithm. We assume that ε is a power of 1/21/2; this can be attained by rounding ε down if necessary, thereby reducing it by a factor of at most 22. In Section 2, we implicitly assumed that the number of districts k is sufficiently large, i.e., at least Ω(1ε) ( 1 ). In the complementary case when k is small, a number of additional subtleties arise that need to be handled carefully. We now introduce some notations. We call a value x∈(0,1/2]x∈(0,1/2] to be big if it satisfies x>215kloglog(1/x)δx> 2^15k (1/x)δ x, and tiny otherwise. Define a function g:(0,1/2]→ℝg (0,1/2] as g(x)=log(1/x)g(x)= (1/x) if x is big, and g(x)=log(2k)g(x)= (2k) otherwise. Let D denote the set of all districts and for any candidate C∈C , let C⊆D_C be the set of districts where C wins. Let W∈W be the winner of the election E. We assume that we are in the setting where |W|>|C||D_W|>|D_C| for every candidate C≠WC≠ W. We will need the following result from [17]. Lemma 3 ([17]). Let (E)≥εN MOV(E)≥ N. Then |W|−|C|≥εk3|D_W|-|D_C|≥ k3, for all C∈∖WC \W\. W′D_W C′D_C 1D_13D_32D_21′D_1 CD_C3′D_3 2′D_2 WD_W Figure 1: Division of D into various types of districts. 1,2,3D_1,D_2,D_3 are the districts where votes are altered in the strategy S. 1′,2′,3′D _1,D _2,D _3 are the districts with large values of h(d)h(d) guaranteed by Lemma 4. The blue and green districts correspond to W′D _W and C′D _C, respectively. Consider any candidate C≠WC≠ W. Let ΔC:=|W|−|C| _C:=|D_W|-|D_C|. Note that by our assumption ΔC>0 _C>0. We call a strategy to alter a subset of votes in E to be C-feasible if in the resulting election obtained after altering the votes, the number of districts where C is the winner is at least that of W. A C-feasible strategy is said to be optimal if it alters the minimum number of votes. Observe that an optimal C-feasible strategy S involves altering votes in three types of districts – a set 1⊆∖(W∪C)D_1 (D_W _C) where the winner is changed to C from some candidate in ∖W,CC \W,C\; a set 2⊆WD_2 _W where the winner is changed from W to C; and a set 3⊆WD_3 _W where the winner is changed from W to some candidate in ∖W,CC \W,C\ (see Figure 1). Note that |1|+2|2|+|3|∈[ΔC,ΔC+1]|D_1|+2|D_2|+|D_3|∈[ _C, _C+1]. For d∈1∪2∪3d _1 _2 _3, let h(d)h(d) be the number of votes altered in district d in the strategy S. Since (E)≥εN MOV(E)≥ N, it must hold that ∑d∈1∪2∪3h(d)≥εN _d _1 _2 _3h(d)≥ N. We show the following lemma. Lemma 4. For all candidates C≠WC≠ W, there exists an αC∈(0,1/2] _C∈(0,1/2] such that there are sets i′⊆iD _i _i, for i∈[3]i∈[3], with |1′∪2′∪3′|≥maxαCk,1|D _1 _2 _3|≥ \ _Ck,1\ and h(d)>εN25αCg(ε)kh(d)> N2^5 _Cg( )k, for all d∈1′∪2′∪3′d _1 _2 _3. Further αC _C is an integral power of 1/21/2, and αC≥ε/16 _C≥ /16, if ε is big, and αC≥1/(2k) _C≥ 1/(2k), otherwise. Proof. We first show the existence of a value βC∈(0,1/2] _C∈(0,1/2] such that there are sets i′⊆iD _i _i, for i∈[3]i∈[3] and satisfying |1′∪2′∪3′|≥βCk|D _1 _2 _3|≥ _Ck and h(d)>εN16βCg(ε)kh(d)> N16 _Cg( )k, for all d∈1′∪2′∪3′d _1 _2 _3; later we shall set αC _C to be the largest power of 1/21/2 not exceeding βC _C. Let Δ:=|1∪2∪3| :=|D_1 _2 _3|. We sort the districts d of 1∪2∪3D_1 _2 _3 in non-increasing order of h(d)h(d), and let M1≥M2≥…≥MΔM_1≥ M_2≥…≥ M_ be the values of h(d)h(d) in these districts. Since (E)≥εN MOV(E)≥ N, we have that ∑i∈[Δ]Mi≥εN _i∈[ ]M_i≥ N. We first consider the case when ε is tiny. We will show that there exists an i∈[Δ]i∈[ ] such that Mi>εN16ilog(2k)M_i> N16i (2k). This would imply our desired claim by taking βC=ik _C= ik and observing that M1≥M2≥…≥MiM_1≥ M_2≥…≥ M_i. Towards a contradiction, assume that for all i∈[Δ]i∈[ ], it holds that Mi≤εN16ilog(2k)M_i≤ N16i (2k). Then ∑i∈[Δ]Mi≤εN16log(2k)∑i∈[Δ]1i≤εN16, _i∈[ ]M_i≤ N16 (2k) _i∈[ ] 1i≤ N16, where the last inequality follows since Δ≤k ≤ k, and we obtain a contradiction. Next, let ε be big. In this case, we show that there exists an integer i∈[⌈εk/8⌉,Δ]i∈[ k/8 , ] such that Mi>εN16ilog(1/ε)M_i> N16i (1/ ), from which the claim would again follow by taking βC=ik _C= ik. Assuming to the contrary that for all i∈[⌈εk/8⌉,Δ]i∈[ k/8 , ], Mi≤εN16ilog(1/ε)M_i≤ N16i (1/ ), we then have ∑i=⌈εk/8⌉ΔMi≤εN16log(1/ε)∑i=⌈εk/8⌉Δ1i≤εN16log(1/ε)(ln(Δ⌈εk/8⌉−1)+1)≤εN2. _i= k/8 M_i≤ N16 (1/ ) _i= k/8 1i≤ N16 (1/ ) ( ( k/8 -1 )+1 )≤ N2. This implies that by altering at most εN/2 N/2 votes, we can obtain another election E′E where W wins in at most εk/8 k/8 districts more than C. However, since (E)≥εN MOV(E)≥ N, W must still be the winner in E′E and (E′)≥εN−εN2=εN2 MOV(E )≥ N- N2= N2. Applying Lemma 3 to E′E , it follows that W must win in at least εk/6 k/6 districts more than any other candidate, contradicting the fact that W only wins in at most εk/8 k/8 districts more than C. Thus, in either case, we obtain a value βC _C such that |1′∪2′∪3′|≥βCk|D _1 _2 _3|≥ _Ck and h(d)>εN16βCg(ε)kh(d)> N16 _Cg( )k, for all d∈1′∪2′∪3′d _1 _2 _3. Let αC:=(1/2)⌈log(1/βC)⌉ _C:=(1/2) (1/ _C) . Then |1′∪2′∪3′|≥maxαCk,1|D _1 _2 _3|≥ \ _Ck,1\ and since αC>βC/2 _C> _C/2, we get h(d)>εN25αCg(ε)kh(d)> N2^5 _Cg( )k, for all d∈1′∪2′∪3′d _1 _2 _3. In order to obtain the desired lower bounds on αC _C, note that if ε is tiny, we have βC≥1/k _C≥ 1/k, and hence αC≥1/(2k) _C≥ 1/(2k); otherwise if ε is big, we have βC≥ε/8 _C≥ /8, and thus αC≥ε/16 _C≥ /16. ∎ We remark that till now we have not made any assumptions on the populations of the districts, i.e., Lemma 4 works for the setting of arbitrary district populations. In the remainder of the section, we derive our structural results assuming all districts have equal population N/kN/k. We then leverage these observations to design our algorithm for the equal population case in Section 5. We call a district d∈d to be W-rich if W wins in d, and no other candidate can be made the winner in d by changing at most ε28αCg(ε) 2^8 _Cg( )-fraction of votes in d. Also, we call d to be C-poor if C is either the winner in d, or can be made the winner in d by changing at most ε28αCg(ε) 2^8 _Cg( )-fraction of votes in d. Lemma 5. The following statements hold. (i) All districts in 3′D _3 are W-rich. (i) There does not exist any C-poor district in (W∪1′)∖((2∖2′)∪3)(D_W _1) ((D_2 _2) _3). Proof. (i) Recall that in the strategy S, the winner is changed from W to some candidate in ∖W,CC \W,C\ in the districts of 3D_3. Also by Lemma 4, we have h(d)>εN25αCg(ε)kh(d)> N2^5 _Cg( )k for all d∈3′d _3. It follows from the optimality of the strategy S that changing the winner requires altering at least ε25αCg(ε) 2^5 _Cg( )-fraction of votes in any district of 3′D _3, and thus all such districts are W-rich. (i) First note that since the winner was changed to C in the districts of 1∪2D_1 _2 in the strategy S and h(d)>εN25αCg(ε)kh(d)> N2^5 _Cg( )k for all d∈1′∪2′d _1 _2, it follows from the optimality of the strategy S that no district in 1′∪2′D _1 _2 is C-poor. Suppose there exists a C-poor district d∈W∖(2∪3)d _W (D_2 _3). Let d′∈1′∪2′∪3′d _1 _2 _3. Consider an alternate strategy ′S that alters the same set of votes as S in the districts of (1∪2∪3)∖d′(D_1 _2 _3) \d \ and changes the winner from W to C in the district d. Clearly ′S is C-feasible and alters strictly fewer votes than S, contradicting the optimality of S. ∎ Let W′:=W∖(2∪(3∖3′))D _W:=D_W (D_2∪(D_3 _3)) and C′:=C∪(1∖1′)∪(2∖2′)D _C:=D_C∪(D_1 _1)∪(D_2 _2) (see Figure 1). We now show the following result about W′D _W and C′D _C. Lemma 6. The following statements hold. (i) If |1|+2|2|+|3|=ΔC+1|D_1|+2|D_2|+|D_3|= _C+1, then all districts in W′D _W are W-rich, and no district in ∖C′D _C is C-poor. (i) If |1|+2|2|+|3|=ΔC|D_1|+2|D_2|+|D_3|= _C, then the sum of the numbers of districts in W′D _W that are not W-rich and districts in ∖C′D _C that are C-poor is at most 11. Proof. (i) First, observe that in this case, 1∪3=∅D_1 _3= , otherwise we can consider an alternate strategy ′S that alters the same set of votes as S except in one district of 1∪3D_1 _3. ′S is C-feasible since in the resulting election, C and W win in equal number of districts, thus contradicting the optimality of S. Suppose there exists a district d∈W′d _W that is not W-rich. Then in d, the winner can be changed from W to some other candidate by changing only εN28αCg(ε)k N2^8 _Cg( )k votes. Let d′∈2′d _2. By Lemma 4, at least εN25αCg(ε)k N2^5 _Cg( )k votes were altered in d′d in the strategy S. Consider a strategy ¯ S that alters the same set of votes as S in the districts of 2∖d′D_2 \d \ and changes the winner from W to some other candidate in the district d (which requires altering only εN28αCg(ε)k N2^8 _Cg( )k votes). Observe that ¯ S is C-feasible since in the resulting election, C and W win in equal number of districts. But then ¯ S alters strictly less number of votes than S, a contradiction. Similarly if there exists a d∈∖C′d _C that is C-poor, then by Lemma 5(i) since no district in 2′D _2 is C-poor, it must be the case that d∈∖(W∪C)d (D_W _C). Again, we could consider the strategy ¯ S that alters the same set of votes as S in the districts of 2∖d′D_2 \d \ and changes the winner to C in the district d. Clearly ¯ S is C-feasible and alters strictly less votes than S, a contradiction. (i) Suppose there exists a district dW∈W′d_W _W that is not W-rich and a district dC∈∖C′d_C _C that is C-poor. By Lemma 5(i), we must have dW∈W∖(2∪3)d_W _W (D_2 _3) and by Lemma 5(i), we have dC∈(∖(W∪C∪1))∪3d_C∈(D (D_W _C _1)) _3. We first show that 1′∪3′=∅D _1 _3= in this case. Assume to the contrary that there exists d′∈1′∪3′d _1 _3. Then we can consider an alternate C-feasible strategy ′S that alters the same set of votes as S in the districts of (1∪2∪3)∖d′(D_1 _2 _3) \d \ and changes the winner from W to some other candidate in the district dWd_W (which requires altering at most εN28αCg(ε)k N2^8 _Cg( )k votes). Clearly ′S alters fewer votes than S, a contradiction. Next consider any d′∈2′d _2. If d∈∖(W∪C∪1)d (D_W _C _1), we let ¯ S be the strategy that alters the same set of votes as S in the districts of (1∪2∪3)∖d′(D_1 _2 _3) \d \, changes the winner from W to some other candidate in dWd_W, and changes the winner to C in the district dCd_C. Otherwise if d∈3d _3, let ¯ S be the strategy that alters the same set of votes as S in the districts of (1∪2∪3)∖d,d′(D_1 _2 _3) \d,d \, changes the winner from W to some other candidate in dWd_W, and changes the winner to C in the district dCd_C. Since by Lemma 4, we have h(d′)>εN25αCg(ε)kh(d )> N2^5 _Cg( )k, and the total number of votes altered in the districts dWd_W and dCd_C is only at most εN27αCg(ε)k N2^7 _Cg( )k, ¯ S alters strictly fewer votes than S, contradicting the optimality of S. ∎ Let WrichD_W^rich be the set of W-rich districts and CpoorD_C^poor be the set of C-poor districts. Lemma 7. It holds that |Wrich|−|Cpoor|≥maxαCk−1,0|D_W^rich|-|D_C^poor|≥ \ _Ck-1,0\. Proof. Let xWx_W be the number of districts in W′D _W that are not W-rich, and xCx_C be the number of districts in ∖C′D _C that are C-poor. We divide the proof into two cases. Case 1: |1|+2|2|+|3|=ΔC+1|D_1|+2|D_2|+|D_3|= _C+1 - In this case, we have xW=xC=0x_W=x_C=0 from Lemma 6(i). Therefore |Wrich|≥|W′|=|W|−|2|−(|3|−|3′|).|D_W^rich|≥|D _W|=|D_W|-|D_2|-(|D_3|-|D _3|). Similarly, |Cpoor|≤|C′|=|C|+(|1|−|1′|)+(|2|−|2′|).|D_C^poor|≤|D _C|=|D_C|+(|D_1|-|D _1|)+(|D_2|-|D _2|). Therefore, |Wrich|−|Cpoor|≥(|W|−|C|)−(|1|+2|2|+|3|)+(|1′|+|2′|+|3′|)≥maxαCk−1,0.|D_W^rich|-|D_C^poor|≥(|D_W|-|D_C|)-(|D_1|+2|D_2|+|D_3|)+(|D _1|+|D _2|+|D _3|)≥ \ _Ck-1,0\. Case 2: |1|+2|2|+|3|=ΔC|D_1|+2|D_2|+|D_3|= _C - In this case, xW+xC≤1x_W+x_C≤ 1 from Lemma 6(i). Similar to the previous case, we have |Wrich|≥|W′|−xW=|W|−|2|−(|3|−|3′|)−xW,|D_W^rich|≥|D _W|-x_W=|D_W|-|D_2|-(|D_3|-|D _3|)-x_W, and |Cpoor|≤|C′|+xC=|C|+(|1|−|1′|)+(|2|−|2′|)+xC.|D_C^poor|≤|D _C|+x_C=|D_C|+(|D_1|-|D _1|)+(|D_2|-|D _2|)+x_C. Hence |Wrich|−|Cpoor|≥(|W|−|C|)−(|1|+2|2|+|3|)+(|1′|+|2′|+|3′|)−(xW+xC)≥maxαCk−1,0,|D_W^rich|-|D_C^poor|≥(|D_W|-|D_C|)-(|D_1|+2|D_2|+|D_3|)+(|D _1|+|D _2|+|D _3|)-(x_W+x_C)≥ \ _Ck-1,0\, and we are done. ∎ 5 Algorithm for equal population As a consequence of Lemma 7, if we are able to predict W as the winner in the districts of WrichD_W^rich, and not predict C as the winner in any district outside CpoorD_C^poor, we would still have a gap of maxαCk−1,0 \ _Ck-1,0\ districts between these sets. Also observe that O~(αC2ε2) O( _C^2 ^2) samples inside a district suffice to decide whether it belongs to WrichD_W^rich or CpoorD_C^poor (or neither). This is the main intuition behind our algorithm, which is summarised in Algorithm 1. Algorithm 1 1: δ∈(0,1)δ∈(0,1). 2: ε~←12 ← 12. 3: while ε~>max215kloglog(1/ε~)δε~,1N > \ 2^15k (1/ )δ , 1 N\ do 4: α~←12 α← 12. 5: while α~≥ε~/16 α≥ /16 do 6: Sample a set ~ε~,α~ D_ , α of q(α~27,δε~16mlog(1/ε~))q( α2^7, δ 16m (1/ )) districts uniformly at random and with replacement. 7: From each district in ~ε~,α~ D_ , α, sample and query ℓε~,α~:=q(ε~211α~log(1/ε~),ε~214) _ , α:=q( 2^11 α (1/ ), 2^14) votes uniformly at random and with replacement. 8: For each C∈C , let ^ε~,α~,C⊆~ε~,α~ D_ , α,C D_ , α be the districts where the fraction of sampled votes received by C exceeds the fraction received by any C′≠C ≠ C by strictly more than ε~29α~log(1/ε~) 2^9 α (1/ ) and let ∨ε~,α~,C⊆~ε~,α~ D _ , α,C D_ , α be the districts in which C is either the winner or can be made the winner by altering at most ε~29α~log(1/ε~) 2^9 α (1/ )-fraction of sampled votes. 9: For each C∈C , let f^ε~,α~(C):=|^ε~,α~,C||ε~,α~|k f_ , α(C):= | D_ , α,C||D_ , α|k and f∨ε~,α~(C):=|∨ε~,α~,C||ε~,α~|k f _ , α(C):= | D _ , α,C||D_ , α|k 10: α~←α~2 α← α2. 11: end while 12: if ∃C∈∃ C such that ∀C′≠C,∃α~C′∀ C ≠ C,∃ α_C such that f^ε~,α~C′(C)−f∨ε~,α~C′(C′)≥α~C′k2 f_ , α_C (C)- f _ , α_C (C )≥ α_C k2 then 13: return C as the winner. 14: end if 15: ε~←ε~2 ← 2. 16: end while 17: while ε~>1N > 1 N do 18: α~←12 α← 12. 19: while α~≥12k α≥ 12k do 20: if α~>8k α> 8k then 21: Sample a set ~ε~,α~ D_ , α of q(α~27,δε~16mlog(2k))q( α2^7, δ 16m (2k)) districts uniformly at random and with replacement. 22: else 23: ~ε~,α~← D_ , α . 24: end if 25: From each district in ~ε~,α~ D_ , α, sample and query ℓε~,α~:=q(ε~211α~log(2k),δε~2klog(2k)) _ , α:=q( 2^11 α (2k), δ 2k (2k)) votes uniformly at random and with replacement. 26: For each C∈C , let ^ε~,α~,C⊆~ε~,α~ D_ , α,C D_ , α be the districts where the fraction of sampled votes received by C exceeds the fraction received by any C′≠C ≠ C by strictly more than ε~29α~log(2k) 2^9 α (2k) and let ∨ε~,α~,C⊆~ε~,α~ D _ , α,C D_ , α be the districts in which C is either the winner or can be made the winner by altering at most ε~29α~log(2k) 2^9 α (2k)-fraction of sampled votes. 27: For each C∈C , let f^ε~,α~(C):=|^ε~,α~,C||ε~,α~|k f_ , α(C):= | D_ , α,C||D_ , α|k and f∨ε~,α~(C):=|∨ε~,α~,C||ε~,α~|k f _ , α(C):= | D _ , α,C||D_ , α|k 28: α~←α~2 α← α2. 29: end while 30: if ∃C∈∃ C such that ∀C′≠C,∃α~C′∀ C ≠ C,∃ α_C such that f^ε~,α~C′(C)−f∨ε~,α~C′(C′)≥α~C′k2 f_ , α_C (C)- f _ , α_C (C )≥ α_C k2 if α~C′>8k α_C > 8k, and f^ε~,α~C′(C)−f∨ε~,α~C′(C′)≥0 f_ , α_C (C)- f _ , α_C (C )≥ 0 otherwise then 31: return C as the winner. 32: end if 33: end while 34: Query all votes and return the winner. In order to prove the correctness of our algorithm, we need to establish that whenever the algorithm returns some candidate as the winner for a particular pair of values (ε~,α~)( , α), that candidate must be W with high probability. Further, to bound the query complexity, we shall show that when the estimate ε~ reaches ε , the algorithm halts with high probability. To this end, we call a district d∈D~ε~,α~d∈ D_ , α to be good if for every C∈C , the difference between the fractions of actual and sampled votes received by C in d is at most ε~211α~g(ε~) 2^11 αg( ), and bad otherwise. Lemma 8. The following statements hold. (i) For each big ε~ , with probability at least 1−δε~21- δ 2, it holds that for every α~ α, at least (1−α~26)(1- α2^6)-fraction of districts of D~ε~,α~ D_ , α are good. (i) For each tiny ε~ , with probability at least 1−δε~21- δ 2, it holds that for every α~ α, all districts of D~ε~,α~ D_ , α are good. Proof. (i) We fix a value of α~ α and consider the collection of sampled districts and votes obtained at the end of line 7. An alternate way of obtaining this collection is the following – we imagine we have a sample of ℓε~,α~ _ , α votes uniformly at random and with replacement from each district in D, and then we sample q(α~27,δε~16mlog(1/ε~))q( α2^7, δ 16m (1/ )) districts uniformly at random and with replacement and observe the sampled votes in those districts. By Lemma 1, the probability that a district is good is at least 1−ε~2141- 2^14, and thus the expected number of bad districts is at most ε~k214 k2^14. Therefore, by Lemma 21, the probability that the number of bad districts exceeds ε~k211 k2^11 is at most 2−ε~k/211≤δε~4log(16/ε~)2^- k/2^11≤ δ 4 (16/ ), where the last inequality follows since ε~ is big. Conditioned on this, by Lemma 1, with probability at least 1−δε~16mlog(1/ε~)≥1−δε~4log(16/ε~)1- δ 16m (1/ )≥ 1- δ 4 (16/ ), the fraction of bad districts in D~ε~,α~ D_ , α is at most ε~211+α~27≤α~26 2^11+ α2^7≤ α2^6, since α~≥ε~/16 α≥ /16. Therefore, for every α~ α, with probability at least 1−δε~2log(16/ε~)1- δ 2 (16/ ), it holds that at least (1−α~26)(1- α2^6)-fraction of districts of D~ε~,α~ D_ , α are good. The claim then follows by taking a union bound over all the log(16/ε~) (16/ ) values of α~ α. (i) Once again, we consider the alternate view of obtaining the collection of sampled districts and votes – we sample ℓε~,α~ _ , α votes uniformly at random and with replacement from each district in D; if α~>8/k α>8/k, we sample q(α~27,δε~16mlog(2k))q( α2^7, δ 16m (2k)) districts uniformly at random and with replacement, and observe the votes sampled in that district, otherwise if α~≤8/k α≤ 8/k, we observe the sampled votes in all districts. In this case, the probability that a district is good is at least 1−δε~2klog(2k)1- δ 2k (2k) due to Lemma 1, and thus by a union bound over all districts, we get that the probability that all districts are good is at least 1−δε~2log(2k)1- δ 2 (2k). Since the number of possible values of α~ α is at most log(2k) (2k), a union bound gives us that with probability at least 1−δε~21- δ 2, for each value of α~ α, all districts in D~ε~,α~ D_ , α are good. ∎ Next, for any p>0p>0 and C∈C , we let ε~,α~,C,prich⊆D_ , α,C,p^rich be the districts where the fraction of votes received by C exceeds the fraction received by any C′≠C ≠ C by strictly more than ε~pα~g(ε~) p αg( ). Also, let ε~,α~,C,ppoor⊆D_ , α,C,p^poor be the districts where C is either the winner or can be made the winner by altering at most ε~pα~g(ε~) p αg( )-fraction of votes. Lemma 9. For any ε~ , with probability at least 1−δε~21- δ 2, both the following events hold for each α~ α and each candidate C∈C . (i) The fraction of districts in ~ε~,α~ D_ , α that belong to ε~,α~,C,prichD_ , α,C,p^rich lies in (|ε~,α~,C,prich|k−α~27,|ε~,α~,C,prich|k+α~27)( |D_ , α,C,p^rich|k- α2^7, |D_ , α,C,p^rich|k+ α2^7). (i) The fraction of districts in ~ε~,α~ D_ , α that belong to ε~,α~,C,ppoorD_ , α,C,p^poor lies in (|ε~,α~,C,ppoor|k−α~27,|ε~,α~,C,ppoor|k+α~27)( |D_ , α,C,p^poor|k- α2^7, |D_ , α,C,p^poor|k+ α2^7). Proof. We describe the proof for ε~,α~,C,prichD_ , α,C,p^rich; the proof for ε~,α~,C,ppoorD_ , α,C,p^poor is analogous. For a fixed α~ α and candidate C∈C , by Lemma 1, the probability that the fraction of districts of ε~,α~,C,prichD_ , α,C,p^rich is preserved up to an error of α~27 α2^7 is at least 1−δε~16mg(ε~)1- δ 16mg( ). The desired claim follows by taking a union bound over all candidates and all the at most 8g(ε~)8g( ) possible values of α~ α. ∎ For each ε~ , let ℰε~E_ be the event that both the events mentioned in Lemma 9 and either of the events stated in Lemma 8 depending on whether ε~ is big or tiny, hold. Then from Lemmas 8 and 9, we have Pr(ℰε~)≥1−δε~Pr(E_ )≥ 1-δ . Define ℰ:=∩ε~ℰε~E:= _ E_ . Taking a union bound over all possible values of ε~ , we get that Pr(ℰ)≥1−δ∑i∈ℕ12i=1−δPr(E)≥ 1-δ _i 12^i=1-δ. Let ε∗ ^* be the value of ε~ when Algorithm 1 halts. We are now ready to show that our algorithm returns the true winner W with high probability. Lemma 10. Conditioned on the event ℰE, Algorithm 1 returns W as the winner. Proof. Let C∗C^* be the candidate returned by Algorithm 1. Let C′≠C∗C ≠ C^* be any other candidate. First consider the case when ε∗ ^* is big, and so Algorithm 1 halts at line 13. Let ~ε∗,α~C′bad⊆~ε∗,α~C′ D_ ^*, α_C ^bad D_ ^*, α_C be the set of sampled districts that are bad, i.e., for some candidate C, the absolute difference between the fractions of actual and sampled votes received by C exceeds ε~211α~C′log(1/ε~) 2^11 α_C (1/ ). Then from Lemma 8(i), |~ε∗,α~C′bad||~ε∗,α~C′|≤α~C′26 | D_ ^*, α_C ^bad|| D_ ^*, α_C |≤ α_C 2^6. In all districts of ^ε∗,α~C′,C∗∖~ε∗,α~C′bad D_ ^*, α_C ,C^* D_ ^*, α_C ^bad, the true fraction of votes received by C∗C^* exceeds that received by any other candidate by strictly more than ε∗29α~C′log(1/ε∗)−ε∗211α~C′log(1/ε∗)>ε∗210α~C′log(1/ε∗) ^*2^9 α_C (1/ ^*)- ^*2^11 α_C (1/ ^*)> ^*2^10 α_C (1/ ^*). Applying Lemma 9(i) for p=210p=2^10, it follows that the true fraction of districts where the fraction of votes received by C∗C^* exceeds the fraction received by any other candidate by strictly more than ε~210α~C′log(1/ε~) 2^10 α_C (1/ ), is at least |^ε∗,α~C′,C∗∖~ε∗,α~C′bad||~ε∗,α~C′|−α^C′27 | D_ ^*, α_C ,C^* D_ ^*, α_C ^bad|| D_ ^*, α_C |- α_C 2^7. In particular, C∗C^* wins in all such districts. Therefore |C∗|≥f^ε∗,α~C′(C∗)−α^C′k26−α^C′k27≥f^ε∗,α~C′(C∗)−α^C′k25|D_C^*|≥ f_ ^*, α_C (C^*)- α_C k2^6- α_C k2^7≥ f_ ^*, α_C (C^*)- α_C k2^5. Next, by Lemma 8(i), we have that in all districts of ~ε∗,α~C′∖(∨ε∗,α~C′,C′∪~ε∗,α~C′bad) D_ ^*, α_C ( D _ ^*, α_C ,C ∪ D_ ^*, α_C ^bad), at least ε∗29α~C′log(1/ε∗)−ε∗211α~C′log(1/ε∗)>ε∗210α~C′log(1/ε∗) ^*2^9 α_C (1/ ^*)- ^*2^11 α_C (1/ ^*)> ^*2^10 α_C (1/ ^*)-fraction of votes need to be changed in order to make C′C as the winner. Therefore, by Lemma 9(i), the true fraction of districts where C′C is either the winner or can be made the winner by altering at most ε∗210α~C′log(1/ε∗) ^*2^10 α_C (1/ ^*)-fraction of votes, is at most |∨ε∗,α~C′,C′∪~ε∗,α~C′bad||~ε∗,α~C′|+α^C′27 | D _ ^*, α_C ,C ∪ D_ ^*, α_C ^bad|| D_ ^*, α_C |+ α_C 2^7. In particular, the set C′D_C of districts where C′C wins satisfies |C′|≤f∨ε∗,α~C′(C′)+α^C′k26+α^C′k27≤f∨ε∗,α~C′(C′)+α^C′k25|D_C |≤ f _ ^*, α_C (C )+ α_C k2^6+ α_C k2^7≤ f _ ^*, α_C (C )+ α_C k2^5. Since f^ε∗,α~C′(C∗)−f∨ε∗,α~C′(C′)≥α~C′k2 f_ ^*, α_C (C^*)- f _ ^*, α_C (C )≥ α_C k2, we have |C∗|−|C′|≥α~C′k2−α~C′k24>0|D_C^*|-|D_C |≥ α_C k2- α_C k2^4>0, and therefore it must be the case that C∗=WC^*=W. Next, suppose that ε∗ ^* is tiny, and α~C′>8k α_C > 8k. In this case, by Lemma 8(i), we have ~ε∗,α~C′bad=∅ D_ ^*, α_C ^bad= . By a similar argument as above (with log(1/ε∗) (1/ ^*) replaced by log(2k) (2k)), we have |C∗|≥f^ε∗,α~C′(C∗)−α^C′k27|D_C^*|≥ f_ ^*, α_C (C^*)- α_C k2^7. A similar argument for C′C yields |C′|≤f∨ε∗,α~C′(C′)+α^C′k27|D_C |≤ f _ ^*, α_C (C )+ α_C k2^7. Since f^ε∗,α~C′(C∗)−f∨ε∗,α~C′(C′)≥α~C′k2 f_ ^*, α_C (C^*)- f _ ^*, α_C (C )≥ α_C k2, we again have f(C∗)>f(C′)f(C^*)>f(C ), and therefore C∗=WC^*=W. Finally, consider the case when ε∗ ^* is tiny and α~C′≤8k α_C ≤ 8k. Note that, in this case we have ~ε∗,α~C′= D_ ^*, α_C =D. Again, by a similar argument as above, we conclude that C∗C^* must win in all districts of ^ε∗,α~C′,C∗ D_ ^*, α_C ,C^*, and C′C is not the winner in any district of ∖∨ε∗,α~C′,C′D D _ ^*, α_C ,C . Therefore, we have |C∗|≥f^ε∗,α~C′(C∗)|D_C^*|≥ f_ ^*, α_C (C^*) and |C′|≤f∨ε∗,α~C′(C′)|D_C |≤ f _ ^*, α_C (C ). Since f^ε∗,α~C′(C∗)−f∨ε∗,α~C′(C′)≥0 f_ ^*, α_C (C^*)- f _ ^*, α_C (C )≥ 0, this implies that |C∗|≥|C′||D_C^*|≥|D_C |. Since the choice of C′C was arbitrary, by our assumption that the election E has an unambiguous winner, it must be the case that C∗=WC^*=W, and we are done. ∎ Next, in order to bound the query complexity of our algorithm, we show that in the iteration when ε~=ε = , Algorithm 1 must return the true winner W with high probability. Lemma 11. Conditioned on the event ℰE, it holds that ε∗≥ε ^*≥ . Proof. It suffices to show that conditioned on ℰE, in the iteration when ε~=ε = , Algorithm 1 must return W as the winner. Let C≠WC≠ W be any other candidate. Let αC _C be the value guaranteed by Lemma 4. Recall that by Lemma 7, we have |ε,αC,W,28rich|−|ε,αC,C,28poor|≥maxαCk−1,0|D_ , _C,W,2^8^rich|-|D^poor_ , _C,C,2^8|≥ \ _Ck-1,0\. Consider first the case when ε is big. Let ~ε,αC,W,28rich=ε,αC,W,28rich∩~ε,αC D^rich_ , _C,W,2^8=D_ , _C,W,2^8^rich∩ D_ , _C. Applying Lemma 9(i) with p=28p=2^8, we have |~ε,αC,W,28rich||~ε,αC|≥|ε,αC,W,28rich|k−αC27 | D^rich_ , _C,W,2^8|| D_ , _C|≥ |D_ , _C,W,2^8^rich|k- _C2^7. Let ~ε,αCbad⊆ε,αC D_ , _C^bad _ , _C be the set of sampled districts that are bad. By Lemma 8(i), |~ε,αCbad||ε,αC|≤αC26 | D_ , _C^bad||D_ , _C|≤ _C2^6. In each district of ~ε,αC,W,28rich∖~ε,αCbad D^rich_ , _C,W,2^8 D_ , _C^bad, the fraction of sampled votes received by W will exceed the fraction received by any other candidate by strictly more than ε28αClog(1/ε)−ε211αClog(1/ε)>ε29αClog(1/ε) 2^8 _C (1/ )- 2^11 _C (1/ )> 2^9 _C (1/ ). Therefore, f^ε,αC(W)≥|~ε,αC,W,28rich∖~ε,αCbad||~ε,αC|k≥|ε,αC,W,28rich|−αCk27−αCk26≥|ε,αC,W,28rich|−αCk25 f_ , _C(W)≥ | D^rich_ , _C,W,2^8 D_ , _C^bad|| D_ , _C|k≥|D_ , _C,W,2^8^rich|- _Ck2^7- _Ck2^6≥|D_ , _C,W,2^8^rich|- _Ck2^5. Similarly, let ~ε,αC,C,28poor=ε,αC,C,28poor∩~ε,αC D_ , _C,C,2^8^poor=D^poor_ , _C,C,2^8∩ D_ , _C, so that |~ε,αC,C,28poor||~ε,αC|≤|ε,αC,C,28poor|k+αC27 | D^poor_ , _C,C,2^8|| D_ , _C|≤ |D_ , _C,C,2^8^poor|k+ _C2^7. Then in each district of ~ε,αC∖(~ε,αC,C,28poor∪~ε,αCbad) D_ , _C ( D^poor_ , _C,C,2^8∪ D_ , _C^bad), the fraction of sampled votes that need to be changed to make C the winner is at least ε28αClog(1/ε)−ε211αClog(1/ε)>ε29αClog(1/ε) 2^8 _C (1/ )- 2^11 _C (1/ )> 2^9 _C (1/ ). Thus f∨ε,αC(C)≤|ε,αC,C,28poor|+αCk27+αCk26≤|ε,αC,C,28poor|+αCk25 f _ , _C(C)≤|D_ , _C,C,2^8^poor|+ _Ck2^7+ _Ck2^6≤|D_ , _C,C,2^8^poor|+ _Ck2^5. Hence f^ε,αC(W)−f∨ε,αC(C)≥|ε,αC,W,28rich|−|ε,αC,C,28poor|−αCk24≥15αCk16−1>αCk2 f_ , _C(W)- f _ , _C(C)≥|D_ , _C,W,2^8^rich|-|D_ , _C,C,2^8^poor|- _Ck2^4≥ 15 _Ck16-1> _Ck2, where the last inequality holds since we are in the case when k>215ε≥211αCk> 2^15 ≥ 2^11 _C. Thus, Algorithm 1 will return W as the winner in line 13. Next, consider the case when ε is small and αC>8k _C> 8k. In this case, by Lemma 8(i), we have ~ε,αCbad=∅ D_ , _C^bad= . Therefore, an analogous argument gives f^ε,αC(W)≥|ε,αC,W,28rich|−αCk27 f_ , _C(W)≥|D_ , _C,W,2^8^rich|- _Ck2^7, and f∨ε,αC(C)≤|ε,αC,C,28poor|+αCk27 f _ , _C(C)≤|D_ , _C,C,2^8^poor|+ _Ck2^7, and hence f^ε,αC(W)−f∨ε,αC(C)≥|ε,αC,W,28rich|−|ε,αC,C,28poor|−αCk26≥63αCk64−1>αCk2 f_ , _C(W)- f _ , _C(C)≥|D_ , _C,W,2^8^rich|-|D_ , _C,C,2^8^poor|- _Ck2^6≥ 63 _Ck64-1> _Ck2, where the final inequality holds by our assumption that k>8αCk> 8 _C. Therefore, the condition of line 31 is satisfied and W will be returned as the winner. Finally, we consider the case when ε is small and αC≤8k _C≤ 8k. For this case, ~ε,αC= D_ , _C=D, and thus ~ε,αC,W,28rich=ε,αC,W,28rich D^rich_ , _C,W,2^8=D_ , _C,W,2^8^rich. Therefore f^ε,αC(W)≥|ε,αC,W,28rich| f_ , _C(W)≥|D_ , _C,W,2^8^rich| and f∨ε,αC(C)≤|ε,αC,C,28poor| f _ , _C(C)≤|D_ , _C,C,2^8^poor|. By Lemma 7, we get f^ε,αC(W)−f∨ε,αC(C)≥0 f_ , _C(W)- f _ , _C(C)≥ 0, and hence the condition in line 31 is satisfied. Thus, Algorithm 1 returns W as the winner. ∎ We are now ready to prove the final result. Lemma 12. With probability at least 1−δ1-δ, Algorithm 1 returns W as the winner and queries at most O~(1ε2logmδlog1δ) O( 1 ^2 mδ 1δ) votes. Proof. Again, it suffices to show that the mentioned claims hold conditioned on the event ℰE. From Lemma 10, we know that Algorithm 1 returns W as the winner. Also owing to Lemma 11, it suffices to bound the query complexity till the iteration when ε~=ε = . Let p(ε~)p( ) be the number of queried votes in a fixed iteration of Algorithm 1 with parameter ε~ . Consider first the case when ε~ is big. Then we have |~ε~,α~|=O(1α~2logmlog(1/ε~)δε~)=O~(1α~2logmδ)| D_ , α|=O( 1 α^2 m (1/ )δ )= O( 1 α^2 mδ), and ℓε~,α~=O(α~2log2(1/ε~)ε~2log1ε~)=O~(α~2ε~2) _ , α=O( α^2 ^2(1/ ) ^2 1 )= O( α^2 ^2). Thus for a fixed α~ α, the number of queried votes is at most |~ε~,α~|⋅ℓε~,α~=O~(1ε~2logmδ)| D_ , α|· _ , α= O( 1 ^2 mδ). Since there are only log16ε~ 16 values of α~ α, we have p(ε~)=O~(1ε~2logmδ)p( )= O( 1 ^2 mδ). Next, suppose ε~ is tiny. Then k≤215ε~loglog(1/ε~)δε~k≤ 2^15 (1/ )δ , and so logk=O~(1) k= O(1). Thus we have ℓε~,α~=O(α~2log2kε~2logklogkδ)=O~(α~2ε~2log1δ) _ , α=O( α^2 ^2k ^2 k kδ)= O( α^2 ^2 1δ). For each α~>8/k α>8/k, we have |~ε~,α~|=O(1α~2logmlogkδε~)=O~(1α~2logmδ)| D_ , α|=O( 1 α^2 m kδ )= O( 1 α^2 mδ), and hence |~ε~,α~|⋅ℓε~,α~=O~(1ε~2logmδlog1δ)| D_ , α|· _ , α= O( 1 ^2 mδ 1δ). Again, for each α~≤8/k α≤ 8/k, we have |ε~,α~|=k=O(1α~)|D_ , α|=k=O( 1 α) and therefore |~ε~,α~|⋅ℓε~,α~=O~(1ε~2log1δ)| D_ , α|· _ , α= O( 1 ^2 1δ). Summing over all the log(2k)=O~(1) (2k)= O(1) values of α~ α, we therefore obtain p(ε~)=O~(1ε~2logmδlog1δ)p( )= O( 1 ^2 mδ 1δ). Hence, in either case, we have p(ε~)=O~(1ε~2logmδlog1δ)p( )= O( 1 ^2 mδ 1δ). By a geometric sum argument, the total number of votes queried by our algorithm up to the iteration when ε~=ε = is bounded by O~(1ε2logmδlog1δ) O( 1 ^2 mδ 1δ), and we are done. ∎ 6 Structural results for arbitrary population We begin by noting that in the proof of Lemma 4, we never used the fact that all districts have equal population. Therefore, the guarantee of Lemma 4 continues to hold even when the population of districts are arbitrary. The only difference is that in the equal population setting, h(d)>εN25αCg(ε)kh(d)> N2^5 _Cg( )k implies that at least ε25αCg(ε) 2^5 _Cg( )-fraction of votes were changed in the district d in the optimal C-feasible strategy; however, such a claim does not hold now since the population of d can be arbitrarily larger than Nk Nk. We now introduce some notations. For any d∈d , we shall let ndn_d denote the population of district d. Let 1/2:=d∈∣nd∈(0,Nk]D^1/2:=\d n_d∈(0, Nk]\, and for any r≥1r≥ 1 that is a power of 22, let r:=d∈∣nd∈(rNk,2rNk]D^r:=\d n_d∈( rNk, 2rNk]\. Define ε~pop:=d∈∣nd>29Nε~kD_ ^pop:=\d n_d> 2^9N k\, if ε~ is big, and ε~pop=∅D_ ^pop= otherwise. Clearly |ε~pop|≤ε~k29|D_ ^pop|≤ k2^9. Similar as in Section 4, let W be the winner of E, and for some candidate C∈C , we consider the optimal C-feasible strategy that alters votes in three sets of districts 1,2,3D_1,D_2,D_3. Also let i′⊆iD _i _i be the districts guaranteed by Lemma 4 so that h(d)>εN25αCg(ε)kh(d)> N2^5 _Cg( )k, for all d∈1′∪2′∪3′d _1 _2 _3. We now generalise our notions of W-rich and C-poor districts as defined in Section 4, to the setting of arbitrary population. For any r≤28εr≤ 2^8 (so that r∩εpop=∅D^r _ ^pop= ), we call a district d∈rd ^r to be W-rich if W wins in d, and no other candidate can be made the winner in d by changing at most ε28αCrg(ε) 2^8 _Crg( )-fraction of votes in d. Similarly we call d to be C-poor if C is either the winner in d or can be made the winner by changing at most ε28αCrg(ε) 2^8 _Crg( )-fraction of votes in d. Let W′:=W∖(2∪(3∖3′))D _W:=D_W (D_2∪(D_3 _3)) and C′:=C∪(1∖1′)∪(2∖2′)D _C:=D_C∪(D_1 _1)∪(D_2 _2) (see Figure 1). The following lemma is an analogue of Lemma 6 in the setting of arbitrary population. Essentially the same guarantees continue to hold, except in the districts of εpopD_ ^pop. Lemma 13. The following statements hold. (i) If |1|+2|2|+|3|=ΔC+1|D_1|+2|D_2|+|D_3|= _C+1, then all districts in W′∖εpopD _W _ ^pop are W-rich, and no district in ∖(C′∪εpop)D (D _C _ ^pop) is C-poor. (i) If |1|+2|2|+|3|=ΔC|D_1|+2|D_2|+|D_3|= _C, then the sum of the numbers of districts in W′∖εpopD _W _ ^pop that are not W-rich and districts in ∖(C′∪εpop)D (D _C _ ^pop) that are C-poor is at most 11. Let r,WrichD_r,W^rich be the districts of rD^r that are W-rich, and r,CpoorD_r,C^poor be the districts of rD^r that are C-poor. Let Wrich=∪r,WrichD_W^rich= _rD_r,W^rich, and Cpoor∪r,CpoorD_C^poor _rD_r,C^poor. Lemma 14. If ε is big, it holds that |Wrich|−|Cpoor|≥3αCk4|D_W^rich|-|D_C^poor|≥ 3 _Ck4; otherwise, for tiny ε , it holds that |Wrich|−|Cpoor|≥maxαCk−1,0|D_W^rich|-|D_C^poor|≥ \ _Ck-1,0\. Proof. Note that if ε is tiny, εpop=∅D_ ^pop= , and by the same proof as in Lemma 7, we obtain |Wrich|−|Cpoor|≥maxαCk−1,0|D_W^rich|-|D_C^poor|≥ \ _Ck-1,0\. Therefore, assume that ε is big. Then by Lemma 4, it holds that αC≥ε/16 _C≥ /16. Therefore |εpop|≤εk29≤αCk25|D_ ^pop|≤ k2^9≤ _Ck2^5. As in the proof of Lemma 7, we let xWx_W denote the number of districts in W′∖εpopD _W _ ^pop that are not W-rich, and xCx_C denote the number of districts in ∖(C′∪εpop)D (D _C _ ^pop) that are C-poor. Then from Lemma 13, we have |Wrich|≥|W|−|2|−(|3|−|3′|)−xW−|εpop|,|D_W^rich|≥|D_W|-|D_2|-(|D_3|-|D _3|)-x_W-|D_ ^pop|, and |Cpoor|≤|C|+(|1|−|1′|)+(|2|−|2′|)+xC+|εpop|.|D_C^poor|≤|D_C|+(|D_1|-|D _1|)+(|D_2|-|D _2|)+x_C+|D_ ^pop|. Thus |Wrich|−|Cpoor|≥(αCk−1)−αCk24≥3αCk4|D_W^rich|-|D_C^poor|≥( _Ck-1)- _Ck2^4≥ 3 _Ck4, where the last inequality follows since k>215ε≥211αCk> 2^15 ≥ 2^11 _C. ∎ With the above lemmas in hand, we are now ready to present our algorithm for the case when districts have arbitrary populations. 7 Algorithm for arbitrary population Our algorithm is summarised in Algorithm 2. Since our definitions of rich and poor districts now depend on r, the number of votes sampled inside the districts of rD^r is a function of r. Specifically, for a particular value of ε~ and α~ α, we now need to query a random sample of Θ~(α~2r2ε~2) ( α^2r^2 ^2) votes inside a district of rD^r in order to decide whether it is rich or poor for any candidate. Also, we can tolerate an error of O~(α~k) O( αk) in estimating the fraction of districts of rD^r that are rich or poor for each candidate. Since |r|≤k/r|D^r|≤ k/r, this translates to a fractional error of O~(α~r) O( αr). This is the main intuition behind our algorithm, which is described in Algorithm 2. Algorithm 2 1: δ∈(0,1)δ∈(0,1). 2: ε~←12 ← 12. 3: while ε~>max215kloglog(1/ε~)δε~,1N > \ 2^15k (1/ )δ , 1 N\ do 4: α~←12 α← 12. 5: while α~≥ε~/16 α≥ /16 do 6: r←12r← 12. 7: while r≤min212log(1/ε~)α~,28ε~r≤ \ 2^12 (1/ ) α, 2^8 \ do 8: Sample a set ~ε~,α~,r D_ , α,r of q(α~r211log(1/ε~),δε~28mlog2(1/ε~))q( αr2^11 (1/ ), δ 2^8m ^2(1/ )) districts uniformly at random and with replacement from rD^r. 9: if |r|∈(0,219ε~rlog1ε~loglog(1/ε~)δε~]|D^r|∈(0, 2^19 r 1 (1/ )δ ] then 10: From each district in ~ε~,α~,r D_ , α,r, sample and query ℓε~,α~,r:=q(ε~211α~rlog(1/ε~),δε~27|r|log2(1/ε~)) _ , α,r:=q( 2^11 αr (1/ ), δ 2^7|D^r| ^2(1/ )) votes uniformly at random and with replacement. 11: else 12: From each district in ~ε~,α~,r D_ , α,r, sample and query ℓε~,α~,r:=q(ε~211α~rlog(1/ε~),ε~r218log(1/ε~)) _ , α,r:=q( 2^11 αr (1/ ), r2^18 (1/ )) votes uniformly at random and with replacement. 13: end if 14: For each C∈C , let ^ε~,α~,r,C⊆~ε~,α~,r D_ , α,r,C D_ , α,r be the districts where the fraction of sampled votes received by C exceeds the fraction received by any C′≠C ≠ C by strictly more than ε~29α~rlog(1/ε~) 2^9 αr (1/ ) and let ∨ε~,α~,r,C⊆~ε~,α~,r D _ , α,r,C D_ , α,r be the districts in which C is either the winner or can be made the winner by altering at most ε~29α~rlog(1/ε~) 2^9 αr (1/ )-fraction of sampled votes. 15: r←2r← 2r. 16: end while 17: For each C∈C , let f^ε~,α~(C):=∑r|^ε~,α~,r,C||ε~,α~,r||r| f_ , α(C):= _r | D_ , α,r,C||D_ , α,r||D^r| and f∨ε~,α~(C):=∑r|∨ε~,α~,r,C||ε~,α~,r||r| f _ , α(C):= _r | D _ , α,r,C||D_ , α,r||D^r|. 18: α~←α~2 α← α2. 19: end while 20: if ∃C∈∃ C such that ∀C′≠C,∃α~C′∀ C ≠ C,∃ α_C such that f^ε~,α~C′(C)−f∨ε~,α~C′(C′)≥α~C′k2 f_ , α_C (C)- f _ , α_C (C )≥ α_C k2 then 21: return C as the winner. 22: end if 23: ε~←ε~2 ← 2. 24: end while 25: while ε~>1N > 1 N do 26: α~←12 α← 12. 27: while α~>12k α> 12k do 28: r←12r← 12. 29: while r≤min212log(2k)α~,kr≤ \ 2^12 (2k) α,k\ do 30: if α~>8k α> 8k then 31: Sample a set ~ε~,α~,r D_ , α,r of q(α~r211log(2k),δε~28mlog2(2k))q( αr2^11 (2k), δ 2^8m ^2(2k)) districts uniformly at random and with replacement. 32: else 33: ~ε~,α~,r←r D_ , α,r ^r. 34: end if 35: From each district in ~ε~,α~,r D_ , α,r, sample and query ℓε~,α~,r:=q(ε~211α~rlog(2k),δε~4klog2(2k)) _ , α,r:=q( 2^11 αr (2k), δ 4k ^2(2k)) votes uniformly at random and with replacement. 36: For each C∈C , let ^ε~,α~,r,C⊆~ε~,α~,r D_ , α,r,C D_ , α,r be the districts where the fraction of sampled votes received by C exceeds the fraction received by any C′≠C ≠ C by strictly more than ε~29α~rlog(2k) 2^9 αr (2k) and let ∨ε~,α~,r,C⊆~ε~,α~,r D _ , α,r,C D_ , α,r be the districts in which C is either the winner or can be made the winner by altering at most ε~29α~rlog(2k) 2^9 αr (2k)-fraction of sampled votes. 37: r←2r← 2r. 38: end while 39: For each C∈C , let f^ε~,α~(C):=∑r|^ε~,α~,r,C||ε~,α~,r||r| f_ , α(C):= _r | D_ , α,r,C||D_ , α,r||D^r| and f∨ε~,α~(C):=∑r|∨ε~,α~,r,C||ε~,α~,r||r| f _ , α(C):= _r | D _ , α,r,C||D_ , α,r||D^r|. 40: α~←α~2 α← α2. 41: end while 42: if ∃C∈∃ C such that ∀C′≠C,∃α~C′∀ C ≠ C,∃ α_C such that f^ε~,α~C′(C)−f∨ε~,α~C′(C′)≥α~C′k2 f_ , α_C (C)- f _ , α_C (C )≥ α_C k2 if α~C′>8k α_C > 8k, and f^ε~,α~C′(C)−f∨ε~,α~C′(C′)≥0 f_ , α_C (C)- f _ , α_C (C )≥ 0 otherwise then 43: return C as the winner. 44: end if 45: end while 46: Query all votes and return the winner. We generalise our definitions of good and bad districts from Section 5. We call a district d∈D~ε~,α~,rd∈ D_ , α,r to be good if for every C∈C , the difference between the fractions of actual and sampled votes received by C in d is at most ε~211α~rg(ε~) 2^11 αrg( ); otherwise, d is said to be bad. The following lemma is an analogue of Lemma 8. Lemma 15. The following statements hold. (i) For each big ε~ , with probability at least 1−δε~21- δ 2, it holds that for every α~,r α,r, at least (1−α~r210log(1/ε~))(1- αr2^10 (1/ ))-fraction of districts of D~ε~,α~,r D_ , α,r are good. (i) For each tiny ε~ , with probability at least 1−δε~21- δ 2, it holds that for every α~,r α,r, all districts of D~ε~,α~,r D_ , α,r are good. Proof. (i) The proof is analogous to the proof of Lemma 8. Once again we consider the alternate view of our algorithm wherein we first sample ℓε~,α~,r _ , α,r votes from each district of rD^r and then sample q(α~r211log(1/ε~),δε~28mlog2(1/ε~))q( αr2^11 (1/ ), δ 2^8m ^2(1/ )) districts from rD^r. If |r|∈(0,219ε~rlog1ε~loglog(1/ε~)δε~]|D^r|∈(0, 2^19 r 1 (1/ )δ ], by our choice of parameters, the probability that a district is good is at least 1−δε~27|r|log2(1/ε~)1- δ 2^7|D^r| ^2(1/ ), and therefore all districts in rD^r are good with probability at least 1−δε~27log2(1/ε~)1- δ 2^7 ^2(1/ ). Otherwise if |r|>219ε~rlog1ε~loglog(1/ε~)δε~|D^r|> 2^19 r 1 (1/ )δ , each district is good with probability at least 1−ε~r218log(1/ε~)1- r2^18 (1/ ), and thus the expected number of bad districts in |r||D^r| is at most ε~r218log(1/ε~)|r| r2^18 (1/ )|D^r|. By Lemma 21, the probability that the number of bad districts exceeds ε~r215log(1/ε~)|r| r2^15 (1/ )|D^r| is at most 2−ε~r215log(1/ε~)|r|≤δε~28log2(1/ε~)2^- r2^15 (1/ )|D^r|≤ δ 2^8 ^2(1/ ). Conditioned on this, by Lemma 1, it holds with probability at least 1−δε~28mlog2(1/ε~)≥1−δε~28log2(1/ε~)1- δ 2^8m ^2(1/ )≥ 1- δ 2^8 ^2(1/ ) that the fraction of bad districts in ~ε~,α~,r D_ , α,r is at most ε~r215log(1/ε~)+α~r211log(1/ε~)≤α~r210log(1/ε~) r2^15 (1/ )+ αr2^11 (1/ )≤ αr2^10 (1/ ), since α~≥ε~/16 α≥ /16. Therefore, with probability at least 1−δε~27log2(1/ε~)1- δ 2^7 ^2(1/ ), for each α~ α and r, it holds that at least 1−α~r210log(1/ε~)1- αr2^10 (1/ )-fraction of districts in ~ε~,α~,r D_ , α,r are good. The claim then follows by taking a union bound over all the log210ε~ 2^10 values of r and the log24ε~ 2^4 values of α~ α. (i) For each α~,r α,r, the probability that a district is good is at least 1−δε~4log2(2k)1- δ 4 ^2(2k). The claim follows by taking a union bound over all the at most log(2k) (2k) values of α~ α and at most log(4k) (4k) values of r. ∎ Let p>0p>0 and C∈C . For any ε~,α~,r , α,r, let ε~,α~,r,C,prich⊆rD_ , α,r,C,p^rich ^r be the districts where the fraction of votes received by C exceeds the fraction received by any C′≠C ≠ C by strictly more than ε~pα~rg(ε~) p αrg( ). Also, let ε~,α~,r,C,ppoor⊆rD_ , α,r,C,p^poor ^r be the districts where C is either the winner or can be made the winner by altering at most ε~pα~rg(ε~) p αrg( )-fraction of votes. Let ε~,α~,C,prich=∪rε~,α~,r,C,prichD_ , α,C,p^rich= _rD_ , α,r,C,p^rich, and ε~,α~,C,ppoor=∪rε~,α~,r,C,ppoorD_ , α,C,p^poor= _rD_ , α,r,C,p^poor. The following lemma is an analogue of Lemma 9 in the setting of arbitrary population. Essentially, it states that the true fraction of districts of ε~,α~,r,C,prichD_ , α,r,C,p^rich (and ε~,α~,C,ppoorD_ , α,C,p^poor) in rD^r is preserved in the sampled districts for each value of r. Lemma 16. For any ε~ , with probability at least 1−δε~21- δ 2, both the following events hold for each α~,r α,r and each candidate C∈C . 1. The fraction of districts in ~ε~,α~,r D_ , α,r that belong to ε~,α~,r,C,prichD_ , α,r,C,p^rich lies in (|ε~,α~,C,p,rrich||r|−α~r211g(ε~),|ε~,α~,C,p,rrich||r|+α~r211g(ε~))( |D_ , α,C,p,r^rich||D^r|- αr2^11g( ), |D_ , α,C,p,r^rich||D^r|+ αr2^11g( )). 2. The fraction of districts in ~ε~,α~,r D_ , α,r that belong to ε~,α~,r,C,ppoorD_ , α,r,C,p^poor lies in (|ε~,α~,r,C,ppoor||r|−α~r211g(ε~),|ε~,α~,r,C,ppoor||r|+α~r211g(ε~))( |D_ , α,r,C,p^poor||D^r|- αr2^11g( ), |D_ , α,r,C,p^poor||D^r|+ αr2^11g( )). Similar to Section 5, for each ε~ , we let ℰε~E_ be the event that both the events mentioned in Lemma 16 and either of the events stated in Lemma 15 depending on whether ε~ is big or tiny, hold. Then Pr(ℰε~)≥1−δε~Pr(E_ )≥ 1-δ . Letting ℰ=∩ε~ℰε~E= _ E_ , we obtain Pr(ℰ)≥1−δ∑i∈ℕ12i=1−δPr(E)≥ 1-δ _i 12^i=1-δ. Let ε∗ ^* be the value of ε~ when Algorithm 2 halts. Lemma 17. Conditioned on the event ℰE, Algorithm 2 returns W as the winner. Proof. The proof is analogous to the proof of Lemma 10. Let C∗C^* be the candidate returned by Algorithm 2, and let C′≠C∗C ≠ C^* be any other candidate. Suppose that ε∗ ^* is big. Consider the iteration of the while loop in line 5 with α~=α~C′ α= α_C . Let R1R_1 be the set of values of r considered by the while loop in line 7, and let R2R_2 be the set of remaining values of r, i.e., those that lie in the range (212log(1/ε∗)α~C′,28ε∗]( 2^12 (1/ ^*) α_C , 2^8 ^*] (if any). For each r∈R1r∈ R_1, let ~ε∗,α~C′,rbad⊆~ε∗,α~C′,r D_ ^*, α_C ,r^bad D_ ^*, α_C ,r be the collection of sampled districts that are bad. By Lemma 15(i), |~ε∗,α~C′,rbad||~ε∗,α~C′,r|≤α~C′r210log(1/ε∗) | D_ ^*, α_C ,r^bad|| D_ ^*, α_C ,r|≤ α_C r2^10 (1/ ^*). In all districts of ^ε∗,α~C′,r,C∗∖~ε∗,α~C′,rbad D_ ^*, α_C ,r,C^* D_ ^*, α_C ,r^bad, the true fraction of votes received by C∗C^* exceeds that received by any other candidate by strictly more than ε∗29α~C′rlog(1/ε∗)−ε∗211α~C′rlog(1/ε∗)>ε∗210α~C′rlog(1/ε∗) ^*2^9 α_C r (1/ ^*)- ^*2^11 α_C r (1/ ^*)> ^*2^10 α_C r (1/ ^*). Applying Lemma 16(i) for p=210p=2^10, it follows that in the election E, the fraction of districts in rD^r where the fraction of votes received by C∗C^* exceeds the fraction received by any other candidate by strictly more than ε~210α~C′rlog(1/ε~) 2^10 α_C r (1/ ), is at least |^ε∗,α~C′,r,C∗∖~ε∗,α~C′,rbad||~ε∗,α~C′,r|−α^C′r211log(1/ε∗)>|^ε∗,α~C′,r,C∗||~ε∗,α~C′,r|−α^C′r29log(1/ε∗) | D_ ^*, α_C ,r,C^* D_ ^*, α_C ,r^bad|| D_ ^*, α_C ,r|- α_C r2^11 (1/ ^*)> | D_ ^*, α_C ,r,C^*|| D_ ^*, α_C ,r|- α_C r2^9 (1/ ^*). Summing over all r∈R1r∈ R_1, it follows that |C∗|≥f^ε∗,α~C′(C∗)−∑r∈R1(α^C′r29log(1/ε∗)|r|)≥f^ε∗,α~C′(C∗)−α^C′k25|D_C^*|≥ f_ ^*, α_C (C^*)- _r∈ R_1( α_C r2^9 (1/ ^*)|D^r|)≥ f_ ^*, α_C (C^*)- α_C k2^5, where the final inequality follows since |r|≤k/r|D^r|≤ k/r and |R1||R_1| is trivially upper bounded by log(210/ε∗) (2^10/ ^*). Similarly, by Lemma 15(i), for each r∈R1r∈ R_1, in all districts of ~ε∗,α~C′,r∖(∨ε∗,α~C′,r,C′∪~ε∗,α~C′,rbad) D_ ^*, α_C ,r ( D _ ^*, α_C ,r,C ∪ D_ ^*, α_C ,r^bad), at least ε∗29α~C′rlog(1/ε∗)−ε∗211α~C′rlog(1/ε∗)>ε∗210α~C′rlog(1/ε∗) ^*2^9 α_C r (1/ ^*)- ^*2^11 α_C r (1/ ^*)> ^*2^10 α_C r (1/ ^*)-fraction of votes need to be changed in order to make C′C as the winner. Therefore, by Lemma 16(i), the true fraction of districts in rD^r where C′C is either the winner or can be made the winner by altering at most ε∗210α~C′rlog(1/ε∗) ^*2^10 α_C r (1/ ^*)-fraction of votes, is at most |∨ε∗,α~C′,r,C′∪~ε∗,α~C′,rbad||~ε∗,α~C′,r|+α^C′r211log(1/ε∗)≤|∨ε∗,α~C′,r,C′||~ε∗,α~C′,r|+α~C′r29log(1/ε∗) | D _ ^*, α_C ,r,C ∪ D_ ^*, α_C ,r^bad|| D_ ^*, α_C ,r|+ α_C r2^11 (1/ ^*)≤ | D _ ^*, α_C ,r,C || D_ ^*, α_C ,r|+ α_C r2^9 (1/ ^*). Now, it is important to note that in the election E, C′C might also have won in the districts of ∪r∈R2r _r∈ R_2D^r, and also in the districts of ε∗popD_ ^*^pop. Observe that for each r∈R2r∈ R_2, |r|≤kr≤α~C′k212log(1/ε∗)|D^r|≤ kr≤ α_C k2^12 (1/ ^*). Also |ε∗pop|≤ε∗k29≤α~C′k25|D_ ^*^pop|≤ ^*k2^9≤ α_C k2^5. Therefore, the set C′D_C of districts where C′C wins satisfies |C′|≤f∨ε∗,α~C′(C′)+∑r∈R1(α^C′r29log(1/ε∗)|r|)+∑r∈R2|r|+|ε∗pop|≤f∨ε∗,α~C′(C′)+α~C′k25+α~C′k28+α~C′k25≤f∨ε∗,α~C′(C′)+α~C′k23|D_C |≤ f _ ^*, α_C (C )+ _r∈ R_1( α_C r2^9 (1/ ^*)|D^r|)+ _r∈ R_2|D^r|+|D_ ^*^pop|≤ f _ ^*, α_C (C )+ α_C k2^5+ α_C k2^8+ α_C k2^5≤ f _ ^*, α_C (C )+ α_C k2^3. Since f^ε∗,α~C′(C∗)−f∨ε∗,α~C′(C′)≥α~C′k2 f_ ^*, α_C (C^*)- f _ ^*, α_C (C )≥ α_C k2, we have |C∗|−|C′|≥α~C′k2−α~C′k25−α~C′k23>0|D_C^*|-|D_C |≥ α_C k2- α_C k2^5- α_C k2^3>0, and therefore it must be the case that C∗=WC^*=W. Next, suppose that ε∗ ^* is tiny, and α~C′>8k α_C > 8k. Again, let R1′R _1 be the set of values of r considered in the while loop in line 29, and R2′R _2 be the set of remaining values of r. In this case, by Lemma 15(i), we have ~ε∗,α~C′,rbad=∅ D_ ^*, α_C ,r^bad= for all r∈R1′r∈ R _1. A similar argument as before (with log(1/ε∗) (1/ ^*) replaced by log(2k) (2k)) gives |C∗|≥f^ε∗,α~C′(C∗)−∑r∈R1(α^C′r211log(2k)|r|)≥α^C′k210|D_C^*|≥ f_ ^*, α_C (C^*)- _r∈ R_1( α_C r2^11 (2k)|D^r|)≥ α_C k2^10. A similar argument for C′C yields |C′|≤f∨ε∗,α~C′(C′)+α^C′k210+∑r∈R2′|r|≤f∨ε∗,α~C′(C′)+α^C′k29|D_C |≤ f _ ^*, α_C (C )+ α_C k2^10+ _r∈ R _2|D^r|≤ f _ ^*, α_C (C )+ α_C k2^9, since |r|≤kr≤α~C′k212log(2k)|D^r|≤ kr≤ α_C k2^12 (2k) (recall that in this case ε∗pop=∅D_ ^*^pop= ). Since f^ε∗,α~C′(C∗)−f∨ε∗,α~C′(C′)≥α~C′k2 f_ ^*, α_C (C^*)- f _ ^*, α_C (C )≥ α_C k2, we again have f(C∗)>f(C′)f(C^*)>f(C ), and therefore C∗=WC^*=W. Finally, consider the case when ε∗ ^* is tiny and α~C′≤8k α_C ≤ 8k. In this case, R2′=∅R _2= , since 212log(2k)α~C′>k 2^12 (2k) α_C >k. We have ~ε∗,α~C′,r=r D_ ^*, α_C ,r=D^r for all r. By an identical argument, C∗C^* must win in all districts of ∪r^ε∗,α~C′,r,C∗ _r D_ ^*, α_C ,r,C^*, and C′C is not the winner in any district of ∖(∪r∨ε∗,α~C′,r,C′)D ( _r D _ ^*, α_C ,r,C ). Therefore, we have |C∗|≥f^ε∗,α~C′(C∗)|D_C^*|≥ f_ ^*, α_C (C^*) and |C′|≤f∨ε∗,α~C′(C′)|D_C |≤ f _ ^*, α_C (C ). Since f^ε∗,α~C′(C∗)−f∨ε∗,α~C′(C′)≥0 f_ ^*, α_C (C^*)- f _ ^*, α_C (C )≥ 0, this implies that |C∗|≥|C′||D_C^*|≥|D_C |, and by our assumption that the election E has an unambiguous winner, it must be the case that C∗=WC^*=W, and we are done. ∎ Lemma 18. Conditioned on the event ℰE, it holds that ε∗≥ε ^*≥ . Proof. We show that in the iteration with ε~=ε = , Algorithm 2 must return W as the winner assuming the event ℰE holds. First assume that ε is big. Let C≠WC≠ W be any other candidate, and αC _C be the value guaranteed by Lemma 4. Consider the iteration of the while loop in line 5 with α~=αC α= _C. Let R1R_1 be the set of values of r considered in the while loop of line 7, i.e., the values of r that are at most min212log(1/ε~)αC,28ε~ \ 2^12 (1/ ) _C, 2^8 \. Let R2R_2 be the (possibly) remaining values of r, i.e., those that lie in the range (212log(1/ε~)αC,28ε~]( 2^12 (1/ ) _C, 2^8 ]. For each r∈R1r∈ R_1, let ~ε,αC,r,W,28rich=ε,αC,r,W,28rich∩~ε,αC,r D^rich_ , _C,r,W,2^8=D_ , _C,r,W,2^8^rich∩ D_ , _C,r. Applying Lemma 16(i) with p=28p=2^8, we have |~ε,αC,r,W,28rich||~ε,αC,r|≥|ε,αC,r,W,28rich||r|−αCr211log(1/ε) | D^rich_ , _C,r,W,2^8|| D_ , _C,r|≥ |D_ , _C,r,W,2^8^rich||D^r|- _Cr2^11 (1/ ). Let ~ε,αC,rbad⊆~ε,αC,r D_ , _C,r^bad D_ , _C,r be the set of sampled districts that are bad. By Lemma 15(i), |~ε,αC,rbad||ε,αC,r|≤αCr210log(1/ε) | D_ , _C,r^bad||D_ , _C,r|≤ _Cr2^10 (1/ ). In each district of ~ε,αC,r,W,28rich∖~ε,αC,rbad D^rich_ , _C,r,W,2^8 D_ , _C,r^bad, the fraction of sampled votes received by W will exceed the fraction received by any other candidate by strictly more than ε28αCrlog(1/ε)−ε211αCrlog(1/ε)>ε29αCrlog(1/ε) 2^8 _Cr (1/ )- 2^11 _Cr (1/ )> 2^9 _Cr (1/ ). Therefore, f^ε,αC(W) f_ , _C(W) ≥∑r∈R1|~ε,αC,r,W,28rich∖~ε,αC,rbad||~ε,αC,r||r| ≥ _r∈ R_1 | D^rich_ , _C,r,W,2^8 D_ , _C,r^bad|| D_ , _C,r||D^r| ≥∑r∈R1|ε,αC,r,W,28rich|−∑r∈R1(αCr211log(1/ε)+αCr210log(1/ε))|r| ≥ _r∈ R_1|D_ , _C,r,W,2^8^rich|- _r∈ R_1( _Cr2^11 (1/ )+ _Cr2^10 (1/ ))|D^r| ≥∑r∈R1|ε,αC,r,W,28rich|−αCk25, ≥ _r∈ R_1|D_ , _C,r,W,2^8^rich|- _Ck2^5, where the final inequality follows since |R1|≤log210ε|R_1|≤ 2^10 . Next, observe that for any r∈R2r∈ R_2, we have |ε,αC,r,W,28rich|≤|r|≤kr≤αCk212log(1/ε)|D_ , _C,r,W,2^8^rich|≤|D^r|≤ kr≤ _Ck2^12 (1/ ). Thus ∑r∈R2|ε,αC,r,W,28rich|≤αCk28 _r∈ R_2|D_ , _C,r,W,2^8^rich|≤ _Ck2^8. Therefore, f^ε,αC(W)≥∑r∈R1∪R2|ε,αC,r,W,28rich|−αCk25−αCk28≥|ε,αC,W,28rich|−αCk24 f_ , _C(W)≥ _r∈ R_1∪ R_2|D_ , _C,r,W,2^8^rich|- _Ck2^5- _Ck2^8≥|D_ , _C,W,2^8^rich|- _Ck2^4. Similarly, for each r∈R1r∈ R_1, let ~ε,αC,r,C,28poor=ε,αC,r,C,28poor∩~ε,αC,r D_ , _C,r,C,2^8^poor=D^poor_ , _C,r,C,2^8∩ D_ , _C,r for each r, so that |~ε,αC,r,C,28poor||~ε,αC,r|≤|ε,αC,r,C,28poor||r|+αCr211log(1/ε) | D^poor_ , _C,r,C,2^8|| D_ , _C,r|≤ |D_ , _C,r,C,2^8^poor||D^r|+ _Cr2^11 (1/ ). Then in each district of ~ε,αC,r∖(~ε,αC,r,C,28poor∪~ε,αC,rbad) D_ , _C,r ( D^poor_ , _C,r,C,2^8∪ D_ , _C,r^bad), the fraction of sampled votes that need to be changed to make C the winner is at least ε28αCrlog(1/ε)−ε211αCrlog(1/ε)>ε29αCrlog(1/ε) 2^8 _Cr (1/ )- 2^11 _Cr (1/ )> 2^9 _Cr (1/ ). Thus, f∨ε,αC(C)≤∑r∈R1|ε,αC,r,C,28poor|+∑r∈R1(αCr211log(1/ε)+αCr210log(1/ε))|r|≤|ε,αC,C,28poor|+αCk25 f _ , _C(C)≤ _r∈ R_1|D_ , _C,r,C,2^8^poor|+ _r∈ R_1( _Cr2^11 (1/ )+ _Cr2^10 (1/ ))|D^r|≤|D_ , _C,C,2^8^poor|+ _Ck2^5. Hence f^ε,αC(W)−f∨ε,αC(C)≥|ε,αC,W,28rich|−|ε,αC,C,28poor|−αCk23≥5αCk8>αCk2 f_ , _C(W)- f _ , _C(C)≥|D_ , _C,W,2^8^rich|-|D_ , _C,C,2^8^poor|- _Ck2^3≥ 5 _Ck8> _Ck2, where the penultimate inequality follows from Lemma 14. Thus, Algorithm 1 will return W as the winner in line 43. Next, consider the case when ε is tiny and αC>8k _C> 8k. Again, let R1′R _1 be the set of values of r considered in the while loop in line 29, and R2′R _2 be the remaining values of r. In this case, by Lemma 15(i), we have ~ε,αC,rbad=∅ D_ , _C,r^bad= for all r∈R1r∈ R_1. Also for r∈R2r∈ R_2, |r|≤kr≤αCk212log(2k)|D^r|≤ kr≤ _Ck2^12 (2k), and so ∑r∈R2|ε,αC,r,W,28rich|≤αCk211 _r∈ R_2|D_ , _C,r,W,2^8^rich|≤ _Ck2^11. Therefore, an analogous argument gives f^ε,αC(W)≥∑r∈R1|ε,αC,r,W,28rich|−∑r∈R1(αCr211log(2k)|r|)≥|ε,αC,W,28rich|−αCk29 f_ , _C(W)≥ _r∈ R_1|D_ , _C,r,W,2^8^rich|- _r∈ R_1( _Cr2^11 (2k)|D^r|)≥|D_ , _C,W,2^8^rich|- _Ck2^9, and similarly f∨ε,αC(C)≤|ε,αC,C,28poor|+αCk210 f _ , _C(C)≤|D_ , _C,C,2^8^poor|+ _Ck2^10, and hence f^ε,αC(W)−f∨ε,αC(C)≥|ε,αC,W,28rich|−|ε,αC,C,28poor|−αCk28≥255αCk256−1>αCk2 f_ , _C(W)- f _ , _C(C)≥|D_ , _C,W,2^8^rich|-|D_ , _C,C,2^8^poor|- _Ck2^8≥ 255 _Ck256-1> _Ck2, where the final inequality holds by our assumption that k>8αCk> 8 _C. Therefore, the condition of line 43 is satisfied, and W will be returned as the winner. Finally, we consider the case when ε is small and αC≤8k _C≤ 8k. For this case, ~ε,αC,r=r D_ , _C,r=D^r for all r, and thus ~ε,αC,r,W,28rich=ε,αC,r,W,28rich D^rich_ , _C,r,W,2^8=D_ , _C,r,W,2^8^rich. Therefore f^ε,αC(W)≥|ε,αC,r,W,28rich| f_ , _C(W)≥|D_ , _C,r,W,2^8^rich| and f∨ε,αC(C)≤|ε,αC,r,C,28poor| f _ , _C(C)≤|D_ , _C,r,C,2^8^poor|. By Lemma 14, we get f^ε,αC(W)−f∨ε,αC(C)≥0 f_ , _C(W)- f _ , _C(C)≥ 0, and hence the condition in line 43 is satisfied. Thus, Algorithm 2 returns W as the winner. ∎ Lemma 19. With probability at least 1−δ1-δ, Algorithm 2 returns W as the winner, and queries at most O~(1ε2logmδlog1δ) O( 1 ^2 mδ 1δ) votes. Proof. Due to Lemmas 17 and 18, we obtain that Algorithm 2 must return W as the winner with probability at least 1−δ1-δ. Similar to the proof of Lemma 12, let p(ε~)p( ) be the number of queried votes in the iteration of Algorithm 2 with parameter ε~ . It suffices to establish that p(ε~)=O~(1ε2logmδlog1δ)p( )= O( 1 ^2 mδ 1δ), from which the lemma would follow by a geometric sum argument over all values of ε~ up to ε . First, suppose that ε~ is big. Then for each α~ α and r, we have |~ε~,α~,r|=O~(1α~2r2logmδ)| D_ , α,r|= O( 1 α^2r^2 mδ). If |r|≤219ε~rlog1ε~loglog(1/ε~)δ|D^r|≤ 2^19 r 1 (1/ )δ, then in line 10, we have ℓε~,α~,r=O~(α~2r2ε~2log|r|δ)=O~(α~2r2ε~2log1δ) _ , α,r= O( α^2r^2 ^2 |D^r|δ)= O( α^2r^2 ^2 1δ), since r≥1/2r≥ 1/2. Otherwise, ℓε~,α~,r=O~(α~2r2ε~2) _ , α,r= O( α^2r^2 ^2) in line 12. Therefore, |~ε~,α~,r|⋅ℓε~,α~,r=O~(1ε~2logmδ)| D_ , α,r|· _ , α,r= O( 1 ^2 mδ). Since the number of values of α~ α is O(log1ε~)O( 1 ), and for each α~ α, there are O(log1ε~)O( 1 ) values of r, we obtain p(ε~)=O~(1ε~2logmδ)p( )= O( 1 ^2 mδ). Next, when ε~ is tiny, we have logk=O~(1) k= O(1). For any α~,r α,r, it holds that ℓε~,α~,r=O~(α~2r2ε~2log1δ) _ , α,r= O( α^2r^2 ^2 1δ). If α~>8k α> 8k, we have |~ε~,α~,r|=O~(1α~2r2logmδ)| D_ , α,r|= O( 1 α^2r^2 mδ), for all r≤min212log(2k)α~,kr≤ \ 2^12 (2k) α,k\. Thus, |~ε~,α~,r|⋅ℓε~,α~,r=O~(1ε~2logmδlog1δ)| D_ , α,r|· _ , α,r= O( 1 ^2 mδ 1δ). Since the number of values of r is O~(1) O(1), and the number of values of α~ α that exceed 8/k8/k is also O~(1) O(1), the total number of samples across all values of α~ α exceeding 8/k8/k is bounded by O~(1ε~2logmδlog1δ) O( 1 ^2 mδ 1δ). Finally if α~≤8k α≤ 8k, we have |~ε~,α~,r|=|r|≤kr=O(1α~r)| D_ , α,r|=|D^r|≤ kr=O( 1 αr) for all r. Thus, |~ε~,α~,r|⋅ℓε~,α~,r=O~(α~rε~2log1δ)| D_ , α,r|· _ , α,r= O( αr ^2 1δ). Hence for each α~≤8k α≤ 8k, the total number of samples is bounded by O~(α~ε~2log1δ)⋅∑r≤O~(α~ε~2log1δ)⋅k≤O~(1ε~2log1δ) O( α ^2 1δ)· _rr≤ O( α ^2 1δ)· k≤ O( 1 ^2 1δ). Since the number of such α~ α is only O(1)O(1), we have p(ε~)=O~(1ε~2logmδlog1δ)p( )= O( 1 ^2 mδ 1δ) overall. Thus, in either case, we have established that p(ε~)=O~(1ε~2logmδlog1δ)p( )= O( 1 ^2 mδ 1δ), completing the proof. ∎ 8 Conclusion and future research directions In this paper we propose a predictor for general district-based elections (with arbitrary district population and arbitrary number of candidates) with optimally bounded (up to polylog factors) query complexity for constant number of candidates, and has an additional logarithmic dependence on the number of candidates. The immediate technical question that our work leaves open is to decide the necessity of the logm m factor in the query complexity. Can it be removed or can a lower bound be proven? Bhattacharyya and Dey studied the query complexity of winner prediction for various voting rules in the single-district setting. A natural direction of future research is thus to study the query complexity of district-based elections for voting rules other than plurality. Another interesting set of questions is to estimate the margin of victory of the overall election (measure of the robustness of the election), as well as the margin of victory of the single-district election defined by the district winners (which corresponds to the robustness of the makeup of the House of Representatives in the US, the House of Commons in the UK or the Parliament in India). References [1] B. Al-Dhalaan and S. Ben-David (2026) Monte carlo to las vegas for recursively composed functions. Note: Full paper: arXiv:2601.08073 Cited by: §1.1.2. [2] A. Ambainis, M. Kokainis, and R. Kothari (2016) Nearly optimal separations between communication (or query) complexity and partitions. In 31st Conference on Computational Complexity (C 2016), External Links: ISBN 9783959770088 Cited by: §1.1.2. [3] A. Anshu, D. Gavinsky, R. Jain, S. Kundu, T. Lee, P. Mukhopadhyay, M. Santha, and S. Sanyal (2018) A composition theorem for randomized query complexity. In 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017), p. 10:1–10:13. External Links: ISBN 978-3-95977-055-2, ISSN 1868-8969, Document Cited by: §1.1.2. [4] S. Ben-David, E. Blais, M. Gös, and G. Maystre (2022) Randomised composition and small-bias minimax. In 63rd Annual Symposium on Foundations of Computer Science (FOCS), p. 624–635. Cited by: §1.1.2. [5] S. Ben-David and E. Blais (2020) A tight composition theorem for the randomized query complexity of partial functions. In 61st Annual Symposium on Foundations of Computer Science (FOCS), p. 240–246. Cited by: §1.1.2. [6] S. Ben-David and R. Kothari (2018) Randomized query complexity of sabotaged and composed functions. Theory of Computing 14 (5), p. 1–27. External Links: Document Cited by: §1.1.2. [7] A. Bhattacharyya and P. Dey (2021) Predicting winner and estimating margin of victory in elections using sampling. Artificial Intelligence 296, p. 103476. Cited by: §1.1.1, §1.2, §1, Lemma 1. [8] H. Buhrman and R. De Wolf (2002) Complexity measures and decision tree complexity: a survey. Theoretical Computer Science 288 (1), p. 21–43. Cited by: §1.1.2. [9] S. Chakraborty, C. Kayal, R. Mittal, M. Paraashar, S. Sanyal, and N. Saurabh (2023) On the composition of randomized query complexity and approximate degree. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023), p. 63:1–63:23. External Links: ISBN 978-3-95977-296-9, ISSN 1868-8969, Document Cited by: §1.1.2. [10] D. P. Dubhashi and A. Panconesi (2009) Concentration of measure for the analysis of randomized algorithms. Cambridge University Press. Cited by: Appendix B. [11] D. Gavinsky, T. Lee, M. Santha, and S. Sanyal (2023) Optimal composition theorem for randomized query complexity. Theory of Computing 19 (9), p. 1–35. External Links: Document Cited by: §1.1.2. [12] O. Goldreich, S. Goldwasser, and D. Ron (1998) Property testing and its connection to learning and approximation. Journal of the ACM (JACM) 45 (4), p. 653–750. Cited by: §1.1.3. [13] O. Goldreich (2017) Introduction to property testing. Cambridge University Press. Cited by: §1.1.3. [14] M. Gös, T. Jayram, T. Pitassi, and T. Watson (2018) Randomized communication versus partition number. ACM Transactions on Computation Theory (TOCT) 10 (1), p. 1–20. Cited by: §1.1.2. [15] M. Gös and T. Jayram (2016) A composition theorem for conical juntas. In 31st Conference on Computational Complexity (C 2016), p. 5–1. Cited by: §1.1.2. [16] R. Jain and H. Klauck (2010) The partition bound for classical communication complexity and query complexity. In 25th Annual Conference on Computational Complexity (C 2010), p. 247–258. External Links: ISBN 9780769540603, Document Cited by: §1.1.2. [17] D. Kar, P. Dey, and S. Sanyal (2023) Sampling-based winner prediction in district-based elections. In 22nd International Conference on Autonomous Agents and Multiagent Systems, p. 2661–2663. Note: Full paper: arXiv:2203.00083 Cited by: §1.1.1, §1.1.2, §1.2, §4, Lemma 3, Theorem 1, footnote 1. [18] F. Magniez, A. Nayak, M. Santha, J. Sherman, G. Tardos, and D. Xiao (2016) Improved bounds for the randomized decision tree complexity of recursive majority. Random Structures & Algorithms 48 (3), p. 612–638. Cited by: §1.1.2. [19] A. Mitra and P. Dey (2024) Evaluating district-based election surveys with synthetic dirichlet likelihood. In 23rd International Conference on Autonomous Agents and Multiagent Systems, p. 1400–1408. Cited by: §1.2. [20] A. Mitra (2023) Agent-based simulation of district-based elections with heterogeneous populations. In 22nd International Conference on Autonomous Agents and Multiagent Systems, p. 2730–2732. Cited by: §1.2. [21] M. Saks and A. Wigderson (1986) Probabilistic boolean decision trees and the complexity of evaluating game trees. In 27th Annual Symposium on Foundations of Computer Science (sfcs 1986), Vol. , p. 29–38. External Links: Document Cited by: §1.1.2. [22] M. Santha (1995) On the monte carlo boolean decision tree complexity of read-once formulae. Random Structures & Algorithms 6 (1), p. 75–87. Cited by: §1.1.2. [23] S. Sanyal (2024) Randomized query composition and product distributions. In 41st International Symposium on Theoretical Aspects of Computer Science (STACS 2024), p. 56–1. Cited by: §1.1.2. Appendix A Proof of Lemma 2 In this section, we present a proof of Lemma 2, restated below. Lemma 20 (Restatement of Lemma 2). Let E be a district-based election with two candidates satisfying (E)≥εN MOV(E)≥ N and 4/k≤ε≤1/24/k≤ ≤ 1/2. Then there exists an α∈[ε8,12]α∈[ 8, 12] such that there are at least k(12+α)k( 12+α) districts each with MOV at least Ω~(εNαk) ( Nα k) in which the overall winner wins. Proof. Let A and B be the two candidates, and assume that A is the winner of E. Let AD_A and BD_B be the sets of districts in which A and B win respectively. Let the districts in AD_A be, in non-decreasing order of their MOV, d1,…,d|w|d_1,…,d_|D_w|. Define Δ:=|A|−|B| :=|D_A|-|D_B|. Consider the set S:=d1,…,d⌈Δ2⌉S:=\d_1,…,d_ 2 \ of ⌈Δ2⌉ 2 districts of least MOV in which A wins. The next claim shows that S contains a large number of districts with high MOV. Claim 1. There exists α′∈[ε4,1]α ∈[ 4,1] such that there are at least α′kα k districts in S each of whose MOV is strictly more than εN100log(1/ε)α′k N100 (1/ )α k. Let us first finish the proof of the Lemma assuming the claim, and then prove the claim. |A|=k2+Δ2|D_A|= k2+ 2. By Claim 1 there are at least εk/4≥1 k/4≥ 1 (by the assumptions of the Lemma statement) districts in S with MOV at least εN100log(1/ε)α′k N100 (1/ )α k. By the definition of S, all districts in A∖SD_A S have MOV at least εN100log(1/ε)α′k N100 (1/ )α k. Thus the total number of districts where A wins and where the MOV is at least εN100log(1/ε)α′k N100 (1/ )α k is at least |A∖S|+α′k≥k2+α′k−12≥k2+(α′/2)k|D_A S|+α k≥ k2+α k- 12≥ k2+(α /2)k (as α′k≥1α k≥ 1). The lemma follows by taking α=α′/2α=α /2 Proof. For convenience, for j=1,…,⌈Δ2⌉j=1,…, 2 we denote the district djd_j as d⌈Δ2⌉−j+1′d _ 2 -j+1 so that d1′,…,d⌈Δ2⌉′d _1,…,d _ 2 is the sequence of districts in S in non-increasing order of their MOV. Define (dj′):=vj MOV(d _j):=v_j. We will show that there exists an i∈[⌊εk/8⌋,⌈Δ/2⌉]i∈[ k/8 , /2 ] such that vi>εN100log(1/ε)iv_i> N100 (1/ )i. This will imply the claim by taking α′=i/kα =i/k and observing that v1≥…≥viv_1≥…≥ v_i. Towards a contradiction, assume that for all i∈[⌊εk/4⌋,⌈Δ/2⌉]i∈[ k/4 , /2 ], Ni≤εN100log(1/ε)iN_i≤ N100 (1/ )i. We have that ∑i=⌊εk/4⌋⌈Δ/2⌉Ni _i= k/4 /2 N_i ≤∑i=⌊εk/4⌋⌈Δ/2⌉εN100log(1/ε)i ≤ _i= k/4 /2 N100 (1/ )i =εN100log(1/ε)∑i=⌊εk/4⌋⌈Δ/2⌉1i = N100 (1/ ) _i= k/4 /2 1i ≤εN100log(1/ε)(Hk−Hεk/4) ≤ N100 (1/ )(H_k-H_ k/4) ⌈Δ/2⌉≤k /2 ≤ k ≤εN100log(1/ε)(ln(4/ε)+2) ≤ N100 (1/ )( (4/ )+2) Fact 1 <εN5. < N5. ε≤1/2 ≤ 1/2 Now consider the election E′E obtained by altering votes in districts D⌊εk/4⌋,…,D⌈Δ/2⌉D_ k/4 ,…,D_ /2 such that A is no more the winner in them. This can be accomplished by changing at most ∑i=⌊εk/8⌋⌈Δ/2⌉Ni<εN5<(E) _i= k/8 /2 N_i< N5< MOV(E) votes in E. Hence A is the winner of E′E and furthermore (E′)>(E)−εN5>4εN5 MOV(E )> MOV(E)- N5> 4 N5 votes. However, in the resulting election, the difference between the numbers of districts won by A and B is at most εk8−1 k8-1, which contradicts Lemma 3. ∎ ∎ Appendix B Additional preliminaries In this section, we include two results that we use in our proofs. Definition 1. For positive integer n the n-th harmonic sum HnH_n is defined as Hn=1+12+…+1n.H_n=1+ 12+…+ 1n. Fact 1. For all n≥1n≥ 1, lnn≤Hn≤lnn+1 n≤ H_n≤ n+1. We will need the following form of the Chernoff bound (see [10] for a proof). Lemma 21. Let Xii∈[n]\X_i\_i∈[n] be n independent 0−10-1 random variables and S=∑i∈[n]XiS= _i∈[n]X_i. Let [S]=μE[S]=μ. Then for any R≥2eμR≥ 2eμ, Pr[S≥R]≤2−RPr[S≥ R]≤ 2^-R.