Every Bit Helps: Achieving the Optimal Distortion with a Few Queries
Authors: Soroush Ebadian, Nisarg Shah
AAAI 2025 | Venue PDF | Archive PDF | Plain Text | 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. |