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..
Every Bit Helps: Achieving the Optimal Distortion with a Few Queries
Authors: Soroush Ebadian, Nisarg Shah
AAAI 2025 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We present a novel algorithm for both one-sided matching and single-winner elections, which leverages a limited number of ΜΈ cardinal queries per agent to achieve asymptotically optimal distortion bounds when ΜΈ is a constant. Tables 1 and 2 provide a summary of our results alongside relevant prior work in one-sided matching and voting, respectively. We impose no restrictions on the utilities, and all our algorithms are deterministic and run in poly-time. Our work builds on the ideas of Amanatidis et al. (2024) and introduces novel applications of the notion of stable committees in multi-winner elections, which is explored by a series of recent works (Aziz et al. 2017; Cheng et al. 2020). |
| Researcher Affiliation | Academia | Soroush Ebadian and Nisarg Shah University of Toronto EMAIL |
| Pseudocode | Yes | Algorithm 1 k-Capacity Serial Dictatorship Input: Preference prole , weights {w(i)}i N, and k Output: A k-capacity mapping 1: B a multiset of k copies of each alternative a A 2: for i N in decreasing order of weights wi do 3: Match i to their most preferred alternative ai B 4: Remove one copy of ai from B 5: end for 6: return g = {i ai}i N |
| Open Source Code | No | The paper does not provide explicit links to source code or state that code will be released for the described methodology. It only provides a link to the full version of the paper for omitted proofs. |
| Open Datasets | No | The paper is theoretical and focuses on algorithm design and distortion bounds; it does not use or reference any datasets for experimental evaluation. |
| Dataset Splits | No | The paper is theoretical and does not perform experiments on datasets, therefore no dataset splits are provided. |
| Hardware Specification | No | The paper is theoretical and describes algorithms and proofs. It does not mention any specific hardware used for running experiments. |
| Software Dependencies | No | The paper is theoretical and focuses on algorithm design and proofs. It does not mention any specific software dependencies or version numbers. |
| Experiment Setup | No | The paper is theoretical, presenting algorithms and their distortion guarantees, rather than empirical results. Therefore, it does not describe an experimental setup with hyperparameters or training settings. |