A new algorithm predicts the winner of a district-based election after sampling dramatically fewer votes than previous methods required.
In a district-based election, voters are split into districts, each district picks a winner by plurality, and those district winners are then run through the same plurality rule to pick an overall winner. Researchers studied how few individual votes need to be sampled at random to correctly call that overall winner with high confidence, a setup that mirrors exit polling. A 2023 paper by Dey, Kar, and Sanyal gave an algorithm for two-candidate races with query complexity scaling roughly as the margin of victory to the sixth power, improving to the fourth power when district populations are balanced. The new paper's algorithm cuts that to roughly the margin of victory squared, works for any number of candidates, and drops the balanced-population assumption entirely.
That is a meaningful drop: needing votes proportional to the margin squared instead of the fourth or sixth power means far fewer ballots have to be sampled to reach the same confidence level, which matters for forecasting results cheaply and fast. The authors also show the new bound is nearly optimal for a constant number of candidates, so there is not much room left to improve it further.
It is a tidy result for people who study sampling theory. Real pollsters, though, do not get random, query-level access to secret ballots, so the gap between this math and an actual exit poll on election night is still considerable.