Improved metric distortion via threshold approvals
File(s)
Published version
Author(s)
Anshelevich, Elliot
Filos-Ratsikas, Aris
Jerrett, Christopher
Voudouris, Alexandros A
Type
Journal Article
Abstract
We consider a social choice setting in which agents and alternatives are represented by points in a metric space, and the cost of an agent for an alternative is the distance between the corresponding points in the space. The goal is to choose a single alternative to (approximately) minimize the social cost (cost of all agents) or the maximum cost of any agent, when only limited information about the preferences of the agents is given. Previous work has shown that the best possible distortion one can hope to achieve is 3 when access to the ordinal preferences of the agents is given, even when the distances between alternatives in the metric space are known. We improve upon this bound of 3 by designing deterministic mechanisms that exploit a bit of 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 that are at distance from the agent within an appropriately chosen factor of the minimum distance of the agents from any 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 a line metric.
Date Issued
2025-04-01
Date Acceptance
2025-01-28
Citation
Artificial Intelligence, 2025, 341
ISSN
0004-3702
Publisher
Elsevier BV
Journal / Book Title
Artificial Intelligence
Volume
341
Copyright Statement
© 2025 The Author(s). Published by Elsevier B.V. This is an open access article under the CC BY-NC-ND license (http://creativecommons.org/licenses/by-nc-nd/4.0/).
Publication Status
Published
Article Number
104295
Date Publish Online
2025-01-30