Sampling-Based Winner Prediction in District-Based Elections
- URL: http://arxiv.org/abs/2203.00083v1
- Date: Mon, 28 Feb 2022 20:32:48 GMT
- Title: Sampling-Based Winner Prediction in District-Based Elections
- Authors: Palash Dey, Debajyoti Kar, Swagato Sanyal
- Abstract summary: In a district-based election, we apply a voting rule $r$ to decide the winners in each district, and a candidate who wins in a maximum number of districts is the winner.
We present efficient sampling-based algorithms to predict the winner of such district-based election systems.
- Score: 6.241494296494433
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: In a district-based election, we apply a voting rule $r$ 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 district-based election systems in
this paper. When $r$ is plurality and the margin of victory is known to be at
least $\varepsilon$ fraction of the total population, we present an algorithm
to predict the winner. The sample complexity of our algorithm is
$\mathcal{O}\left(\frac{1}{\varepsilon^4}\log
\frac{1}{\varepsilon}\log\frac{1}{\delta}\right)$. 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 $r$ is plurality, must sample at
least $\Omega\left(\frac{1}{\varepsilon^4}\log\frac{1}{\delta}\right)$ votes.
We then extend this result to any voting rule $r$. Loosely speaking, we show
that we can predict the winner of a district-based election with an extra
overhead of
$\mathcal{O}\left(\frac{1}{\varepsilon^2}\log\frac{1}{\delta}\right)$ over the
sample complexity of predicting the single-district winner under $r$. 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 a district-based election can be predicted with
$\mathcal{O}\left(\frac{1}{\varepsilon^4}\log\frac{1}{\varepsilon}\log\frac{1}{\delta}\right)$
samples even when the harmonious order in different districts can be different
and even unknown. Finally, we also show some results for estimating the margin
of victory of a district-based election within both additive and multiplicative
error bounds.
Related papers
- Efficient Lower Bounding of Single Transferable Vote Election Margins [56.12949230611067]
Single transferable vote (STV) is a system of preferential proportional voting employed in multi-seat elections.
The margin of victory, or simply'margin', is the smallest number of ballots that need to be manipulated to alter the set of winners.
Lower bounds on the margin can also be used for this purpose, in cases where exact margins are difficult to compute.
arXiv Detail & Related papers (2025-01-24T13:39:23Z) - Simple and Nearly-Optimal Sampling for Rank-1 Tensor Completion via Gauss-Jordan [49.1574468325115]
We revisit the sample and computational complexity of completing a rank-1 tensor in $otimes_i=1N mathbbRd$.
We present a characterization of the problem which admits an algorithm amounting to Gauss-Jordan on a pair of random linear systems.
arXiv Detail & Related papers (2024-08-10T04:26:19Z) - Ahead of the Count: An Algorithm for Probabilistic Prediction of Instant Runoff (IRV) Elections [0.0]
We introduce a novel algorithm designed to predict outcomes in Instant Runoff Voting (IRV) elections.
The algorithm takes as input a set of discrete probability distributions describing vote totals for each candidate ranking.
We calculate all possible sequences of eliminations that might occur in the IRV rounds and assign a probability to each.
arXiv Detail & Related papers (2024-05-15T00:25:51Z) - Low-Rank Bandits via Tight Two-to-Infinity Singular Subspace Recovery [45.601316850669406]
We present efficient algorithms for policy evaluation, best policy identification and regret minimization.
For policy evaluation and best policy identification, we show that our algorithms are nearly minimax optimal.
All the proposed algorithms consist of two phases: they first leverage spectral methods to estimate the left and right singular subspaces of the low-rank reward matrix.
arXiv Detail & Related papers (2024-02-24T06:36:08Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
We show that any efficient SQ algorithm for the problem requires sample complexity at least $Omega(d1/2/(maxp, epsilon)2)$.
Our lower bound suggests that this quadratic dependence on $1/epsilon$ is inherent for efficient algorithms.
arXiv Detail & Related papers (2023-07-13T18:59:28Z) - Horizon-free Reinforcement Learning in Adversarial Linear Mixture MDPs [72.40181882916089]
We show that our algorithm achieves an $tildeObig((d+log (|mathcalS|2 |mathcalA|))sqrtKbig)$ regret with full-information feedback, where $d$ is the dimension of a known feature mapping linearly parametrizing the unknown transition kernel of the MDP, $K$ is the number of episodes, $|mathcalS|$ and $|mathcalA|$ are the cardinalities of the state and action spaces
arXiv Detail & Related papers (2023-05-15T05:37:32Z) - Streaming Algorithms for Learning with Experts: Deterministic Versus
Robust [62.98860182111096]
In the online learning with experts problem, an algorithm must make a prediction about an outcome on each of $T$ days (or times)
The goal is to make a prediction with the minimum cost, specifically compared to the best expert in the set.
We show a space lower bound of $widetildeOmegaleft(fracnMRTright)$ for any deterministic algorithm that achieves regret $R$ when the best expert makes $M$ mistakes.
arXiv Detail & Related papers (2023-03-03T04:39:53Z) - Accelerating Voting by Quantum Computation [35.03314687289671]
We propose a quantum-accelerated voting algorithm that can be applied to any anonymous voting rule.
Our algorithm outputs the correct winner with high probability in $Thetaleft(fracntextMOVright)$ time.
arXiv Detail & Related papers (2023-01-08T07:29:38Z) - Best Policy Identification in Linear MDPs [70.57916977441262]
We investigate the problem of best identification in discounted linear Markov+Delta Decision in the fixed confidence setting under a generative model.
The lower bound as the solution of an intricate non- optimization program can be used as the starting point to devise such algorithms.
arXiv Detail & Related papers (2022-08-11T04:12:50Z) - Expected Frequency Matrices of Elections: Computation, Geometry, and
Preference Learning [58.23459346724491]
We use the "map of elections" approach of Szufa et al. (AAMAS 2020) to analyze several well-known vote distributions.
We draw the "skeleton map" of distributions, evaluate its robustness, and analyze its properties.
arXiv Detail & Related papers (2022-05-16T17:40:22Z) - Private High-Dimensional Hypothesis Testing [4.133655523622441]
We provide improved differentially private algorithms for identity testing of high-dimensional distributions.
Specifically, we can test whether the distribution comes from $mathcalN(mu*, Sigma)$ for some fixed $mu*$ or from some $mathcalN(mu*, Sigma)$ with total variation distance at least $alpha$.
arXiv Detail & Related papers (2022-03-03T06:25:48Z) - Differentially Private Multi-Armed Bandits in the Shuffle Model [58.22098764071924]
We give an $(varepsilon,delta)$-differentially private algorithm for the multi-armed bandit (MAB) problem in the shuffle model.
Our upper bound almost matches the regret of the best known algorithms for the centralized model, and significantly outperforms the best known algorithm in the local model.
arXiv Detail & Related papers (2021-06-05T14:11:01Z) - Fine-Grained Complexity and Algorithms for the Schulze Voting Method [9.399840807973545]
We study computational aspects of a well-known single-winner voting rule called the Schulze method.
Our paper is the first to bring fine-grained complexity into the field of computational social choice.
arXiv Detail & Related papers (2021-03-05T22:27:36Z) - Resolving the Optimal Metric Distortion Conjecture [27.344649091365067]
We study the following metric distortion problem.
There are two finite sets of points, $V$ and $C$, that lie in the same metric space.
We propose algorithms that choose a point in $C$ using only these rankings as input.
arXiv Detail & Related papers (2020-04-16T04:13:06Z) - Locally Private Hypothesis Selection [96.06118559817057]
We output a distribution from $mathcalQ$ whose total variation distance to $p$ is comparable to the best such distribution.
We show that the constraint of local differential privacy incurs an exponential increase in cost.
Our algorithms result in exponential improvements on the round complexity of previous methods.
arXiv Detail & Related papers (2020-02-21T18:30:48Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.