Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Tight Bounds on the Distortion of Randomized and Deterministic Distributed Voting
Authors: Mohammad Abam, Davoud Kareshki, Marzieh Nilipour, MohammadHossein Paydar, Masoud Seddighin
NeurIPS 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We present improved distortion bounds for both deterministic and randomized mechanisms, offering a near-complete characterization of distortion in this model. For deterministic mechanisms, we reduce the upper bound for avg-max from 11 to 7, establish a tight lower bound of 5 for max-avg (improving on 2 + 5), and tighten the upper bound for max-max from 5 to 3. For randomized mechanisms, we consider two settings... In this paper, we take a significant step toward understanding randomized mechanisms in distributed voting. We study two natural classes of randomized mechanisms rand-det and rand-rand within general metric spaces, and analyze their performance with respect to the four objectives. See Table 2 for an overview of our results. For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [Yes] |
| Researcher Affiliation | Academia | Computer Engineering Department, Sharif University of Technology, Tehran, Iran Computer Science Department, Tehran Institute for Advanced Studies (Te IAS), Tehran, Iran |
| Pseudocode | No | The paper describes various voting rules and mechanisms such as "Plurality Matching rule (fpm)", "Random Dictatorship rule (frd)", "Uniform selection rule (fur)", and "Arbitrary Dictator mechanism (mad)" in paragraph form. It does not provide any explicitly labeled pseudocode blocks or algorithms with structured steps. |
| Open Source Code | No | 5. Open access to data and code Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [NA] Justification: [TODO] |
| Open Datasets | No | 5. Open access to data and code Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [NA] Justification: [TODO]. The paper constructs theoretical instances with specific configurations of candidates and voters to derive lower bounds, for example: "We construct an instance with candidates C = {c1, c2, c3} and voters V = {v1, v2}, where each voter belongs to a distinct group: v1 g1 and v2 g2." It does not use or provide access to pre-existing open datasets. |
| Dataset Splits | No | The paper is theoretical and does not involve experimental evaluation on datasets, therefore it does not mention training, test, or validation splits. The NeurIPS Paper Checklist has 'Answer: [NA]' for experimental reproducibility, settings, and statistical significance, indicating no experimental data or splits were used. |
| Hardware Specification | No | The paper is theoretical and does not report on experimental results that would require specific hardware. The NeurIPS Paper Checklist sections for experimental results (4, 6, 7, 8) all have 'Answer: [NA]' for reproducibility, setting details, statistical significance, and compute resources, confirming no hardware specifications are provided. |
| Software Dependencies | No | The paper is theoretical and does not report on experimental results. Therefore, it does not list any specific software dependencies with version numbers for reproducibility. The NeurIPS Paper Checklist sections for experimental results (4, 6, 7, 8) all have 'Answer: [NA]', confirming no such details are provided. |
| Experiment Setup | No | The paper is theoretical and focuses on mathematical proofs and bounds rather than empirical experiments. Therefore, it does not provide details on experimental setups, hyperparameters, or training configurations. The NeurIPS Paper Checklist sections for experimental results (4, 6, 7, 8) all have 'Answer: [NA]', confirming no such details are provided. |