Approximating Optimal Social Choice under Metric Preferences
Authors: Elliot Anshelevich, Onkar Bhardwaj, John Postl
AAAI 2015 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Thus, we seek to bound the distortion: the worst-case ratio between the social cost of the alternative selected and the optimal alternative. Distortion measures how good a mechanism is at approximating the alternative with minimum social cost, while using only ordinal preference information. ... We quantify the distortion of many well-known social choice mechanisms. We show that for both total social cost and median agent cost, many positional scoring rules have large distortion, while on the other hand Copeland and similar mechanisms perform optimally or near-optimally, always obtaining a distortion of at most 5. We also give lower bounds on the distortion that could be obtained by any deterministic social choice mechanism...In this work, we bound the worst-case distortion of many well-known social choice functions. ... Our results show that while the distortion is high for some mechanisms, the distortion of many important social choice functions is bounded by a small constant, assuming that the preferences of the agents are spatial. |
| Researcher Affiliation | Academia | Elliot Anshelevich and Onkar Bhardwaj and John Postl Rensselaer Polytechnic Institute 110 8th Street, Troy NY 12180 |
| Pseudocode | No | The paper describes algorithms like Copeland and Ranked Pairs in text, but does not provide structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide any specific repository links, explicit code release statements, or mention of code in supplementary materials for the methodology described. |
| Open Datasets | No | The paper analyzes theoretical bounds and mechanisms for social choice and does not involve the use of datasets for training. |
| Dataset Splits | No | The paper is theoretical and does not involve empirical experiments with data, thus no dataset split information for validation is provided. |
| Hardware Specification | No | The paper is theoretical and does not involve computational experiments, therefore no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not detail any computational implementations, thus no software dependencies with version numbers are listed. |
| Experiment Setup | No | The paper is theoretical, focusing on mathematical bounds and proofs, and as such does not include specific experimental setup details like hyperparameters or training configurations. |