Estimating the Margin of Victory of an Election Using Sampling
Authors: Palash Dey, Y. Narahari
IJCAI 2015 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this work, we present efficient sampling based algorithms for estimating the margin of victory of elections. More formally, we introduce the (c, ε, δ) MARGIN OF VICTORY problem, where given an election E on n voters, the goal is to estimate the margin of victory M(E) of E within an additive factor of c M(E)+εn. We study the (c, ε, δ) MARGIN OF VICTORY problem for many commonly used voting rules including scoring rules, approval, Bucklin, maximin, and Copelandα. We observe that even for the voting rules for which computing the margin of victory is NP-Hard, there may exist efficient sampling based algorithms, as observed in the cases of maximin and Copelandα voting rules. |
| Researcher Affiliation | Academia | Palash Dey and Y. Narahari Department of Computer Science and Automation, Indian Institute of Science, Bangalore, India {palash|hari}@csa.iisc.ernet.in |
| Pseudocode | No | The paper describes algorithms through proofs and theoretical discussion but does not include any explicitly labeled pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any concrete access information for open-source code, such as a repository link or an explicit statement of code release. |
| Open Datasets | No | The paper is theoretical and focuses on mathematical proofs and sample complexity. It does not use or refer to any specific dataset for training, nor does it provide access information for any dataset. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with dataset splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not report on empirical experiments, therefore no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and focuses on algorithmic design and proofs. It does not mention any specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe any empirical experimental setup details, such as hyperparameters or training configurations. |