Metric Distortion with Elicited Pairwise Comparisons
Authors: Soroush Ebadian, Daniel Halpern, Evi Micha
IJCAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our main contributions are nearly optimal algorithms for all settings considered. Next, we consider algorithms that match this lower bound. We are especially interested in algorithms that require few rounds of interactions, as it may not be reasonable to assume that agents return later in the process after answering queries. Of particular importance is the extreme case: single-pass algorithms needing only one round of interaction. Strikingly, we show that there exists a single-pass algorithm that achieves optimal distortion of O(m/t) (Section 3.2). Finally, we consider other kinds of restrictions on the adaptivity of the algorithm, i.e., how the queries depend on previous answers. We focus on two types of adaptivity. The first, called inter-agent adaptivity, indicates whether the queries made to an agent can depend on responses from other agents. The second, called intra-agent adaptivity, indicates whether the queries made to an agent can depend on previous responses from that agent. Here, we devise nearly tight (up to logarithmic factors) upper and lower bounds for the optimal distortion achievable under all combinations of these restrictions (Section 4). |
| Researcher Affiliation | Academia | Soroush Ebadian1 , Daniel Halpern2 , Evi Micha2 1University of Toronto 2Harvard University soroush@cs.toronto.edu, dhalpern@g.harvard.edu, emicha@cs.toronto.edu |
| Pseudocode | Yes | Algorithm 1 Single-Pass Plurality Veto... Algorithm 2 t-Query Single-Pass Adaptive... Algorithm 3 t-Query Single-Pass Intra-agent Nonadaptive |
| Open Source Code | No | The paper does not mention providing open-source code for the methodology described. |
| Open Datasets | No | This paper is theoretical and does not use or refer to any specific publicly available datasets for empirical evaluation. |
| Dataset Splits | No | This paper is theoretical and does not involve empirical experiments with dataset splits for training, validation, or testing. |
| Hardware Specification | No | This paper is theoretical and does not describe any empirical experiments that would require specific hardware for execution. |
| Software Dependencies | No | This paper is theoretical and does not describe any empirical experiments that would require specific software dependencies with version numbers. |
| Experiment Setup | No | This paper is theoretical and does not describe any empirical experiments with specific setup details like hyperparameters or training settings. |