Constant-Factor Distortion Mechanisms for k-Committee Election
Authors: Haripriya Pulyassary, Chaitanya Swamy
AAAI 2025 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We develop the first algorithms (that we call mechanisms) for the ℓ-centrum problem (when k ≥ 2), which achieve O(1)-distortion while eliciting only a very limited amount of cardinal information via value queries. We obtain two types of query-complexity guarantees: O(log k log n) queries per agent, and O(k2 log2 n) queries in total (while achieving O(1)-distortion in both cases). En route, we give a simple adaptive-sampling algorithm for the ℓ-centrum k-clustering problem. The paper focuses on theoretical contributions, presenting new algorithms, theorems, and proofs for achieving O(1)-distortion in k-committee election, without empirical validation using datasets or experimental results. |
| Researcher Affiliation | Academia | 1School of ORIE, Cornell University, Ithaca, NY 14853, USA 2Dept. of Combinatorics & Optimization, University of Waterloo, Waterloo, ON N2L 3G1, CANADA EMAIL, EMAIL |
| Pseudocode | Yes | Mechanism 1: A blackbox reduction Algorithm 1: Extension of Meyerson s for ℓ-centrum Mechanism 2: O(log k log n)per-agent query complexity Algorithm 2: Adaptive sampling for ℓ-centrum Mechanism 3: e O k log(min{ℓ, n/ℓ}) per-agent query complexity mechanism |
| Open Source Code | No | The paper does not contain any explicit statements about code availability, nor does it provide links to source code repositories or mention code in supplementary materials. |
| Open Datasets | No | The paper is theoretical and does not conduct experiments involving specific datasets. Therefore, no information about open or publicly available datasets is provided. |
| Dataset Splits | No | The paper is theoretical and does not involve experiments with datasets, so there is no mention of dataset splits for training, validation, or testing. |
| Hardware Specification | No | This paper is theoretical and does not describe any experimental setup that would require specific hardware. No details about GPU models, CPU specifications, or other hardware are provided. |
| Software Dependencies | No | The paper is theoretical and focuses on algorithm design and proofs. It does not mention any specific software or library versions used for implementation or experimentation. |
| Experiment Setup | No | The paper focuses on theoretical algorithm design and analysis, proving distortion bounds and query complexities. It does not describe any empirical experiments, hyperparameters, training configurations, or system-level settings. |