Improved Metric Distortion via Threshold Approvals
Authors: Elliot Anshelevich, Aris Filos-Ratsikas, Christopher Jerrett, Alexandros A. Voudouris
AAAI 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We improve upon this bound of 3 by designing deterministic mechanisms that exploit limited cardinal information. We show that it is possible to achieve distortion 1 + 2 by using the ordinal preferences of the agents, the distances between alternatives, and a threshold approval set per agent that contains all alternatives for whom her cost is within an appropriately chosen factor of her cost for her most-preferred alternative. We show that this bound is the best possible for any deterministic mechanism in general metric spaces, and also provide improved bounds for the fundamental case of the line metric. and Theorem 3.1. In general metric spaces, the distortion of αMINISUM-TAS-DISTANCE for the social cost objective is at most max α, 2 + 1 |
| Researcher Affiliation | Academia | Elliot Anshelevich1, Aris Filos-Ratsikas2, Christopher Jerrett1, Alexandros A. Voudouris3 1Rensselaer Polytechnic Institute, USA 2University of Edinburgh, United Kingdom 3University of Essex, United Kingdom |
| Pseudocode | Yes | Mechanism 1: α-MINISUM-TAS-DISTANCE Input: Distances between alternatives, α-TAS; Output: Winner w; w arg minx A P i N minj Ai d(j, x) ; and Mechanism 2: α-MOST-COMPACT-SET Input: Most-preferred alternatives of agents, distances between alternatives, α-TAS; Output: Winner w; if x Ai, i N then ρi = maxx Ai d(x, oi); w arg mini N ρi ; |
| Open Source Code | No | The paper does not provide any statement or link indicating the availability of open-source code for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not utilize or refer to publicly available datasets for training. It discusses abstract 'instances' within a metric space rather than specific named datasets with access information. |
| Dataset Splits | No | The paper is theoretical and does not describe experiments involving data splits for training, validation, or testing. |
| Hardware Specification | No | The paper is theoretical and does not describe any specific hardware used for computations or experiments. |
| Software Dependencies | No | The paper is theoretical and does not mention any specific software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not describe an experimental setup with specific hyperparameters or training configurations. |