Approximate Inference of Outcomes in Probabilistic Elections
Authors: Batya Kenig, Benny Kimelfeld2061-2068
AAAI 2019 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We study the complexity of estimating the probability of an outcome in an election over probabilistic votes... The main contribution of this paper is a multiplicative FPRAS for the probability of losing. We do so for a large class of positional scoring rules... To this end, we adapt the Karp-Luby-Madras approximation algorithm (Karp, Luby, and Madras 1989), and the main theoretical challenges we face is in establishing (provable approximations of) the requirements that this algorithm makes on a specific use case. To the best of our knowledge, this paper presents the first multiplicative approximation algorithm in the context of elections over probabilistic voters. |
| Researcher Affiliation | Academia | Batya Kenig Paul G. Allen School of Computer Science and Engineering University of Washington batyak@cs.washington.edu, Benny Kimelfeld Technion Israel Institute of Technology Haifa 3200003, Israel bennyk@cs.technion.ac.il |
| Pseudocode | Yes | Figure 1: Sampling conditioned on L(x, c) Algorithm sample(P = { 1, . . . , n},L(x, c)) |
| Open Source Code | No | The paper does not include an unambiguous statement about releasing code for the work described, nor does it provide a direct link to a source-code repository. |
| Open Datasets | No | This paper is theoretical and does not conduct experiments with empirical datasets, therefore, it does not provide concrete access information for a publicly available or open dataset used for training. |
| Dataset Splits | No | This paper is theoretical and does not conduct experiments with dataset splits, therefore, it does not provide specific dataset split information. |
| Hardware Specification | No | This paper is theoretical and does not describe the hardware used for experiments. |
| Software Dependencies | No | The paper does not provide specific ancillary software details with version numbers, as it is a theoretical paper and does not discuss specific implementation environments. |
| Experiment Setup | No | This paper is theoretical and does not describe experimental setup details such as hyperparameters or training configurations. |