Sampling-Based Winner Prediction in District-Based Elections

In a district-based election, we apply a voting rule 𝑟 to decide the winners in each district, and a candidate who wins in a maximum number of districts is the winner of the election. We present efficient sampling-based algorithms to predict the winner of such districtbased election systems in this paper. When 𝑟 is plurality (i.e., the candidate receiving a maximum number of votes is declared as the winner) and the margin of victory is known to be at least 𝜀 fraction of the total population, we present an algorithm to predict the winner with probability at least 1-𝛿, whose sample complexity is O 1 𝜀 4 log 1 𝜀 log 1 𝛿. We complement this result by proving that any algorithm, from a natural class of algorithms, for predicting the winner in a district-based election when 𝑟 is plurality, must sample at least Ω 1 𝜀 4 log 1 𝛿 votes. We then extend this result to any voting rule 𝑟. Loosely speaking, we show that we can predict the winner of a district-based election with an extra overhead of O 1 𝜀 2 log 1 𝛿 over the sample complexity of predicting the single-district winner under 𝑟. We further extend our algorithm for the case when the margin of victory is unknown, but we have only two candidates. We then consider the median voting rule when the set of preferences in each district is single-peaked. We show that the winner of such a district-based election can be predicted with probability at least 1-𝛿 with O 1 𝜀 4 log 1 𝜀 log 1 𝛿 samples.