Ordinal approximation for social choice, matching, and facility location problems given candidate positions

DOI10.1007/978-3-030-04612-5_1zbMATH Open1443.91130arXiv1805.03103OpenAlexW3161198832MaRDI QIDQ2190377FDOQ2190377

Authors: Elliot Anshelevich, Wennan Zhu 

Publication date: 18 June 2020

Abstract: In this work we consider general facility location and social choice problems, in which sets of agents $mathcalA$ and facilities $mathcalF$ are located in a metric space, and our goal is to assign agents to facilities (as well as choose which facilities to open) in order to optimize the social cost. We form new algorithms to do this in the presence of only {em ordinal information}, i.e., when the true costs or distances from the agents to the facilities are {em unknown}, and only the ordinal preferences of the agents for the facilities are available. The main difference between our work and previous work in this area is that while we assume that only ordinal information about agent preferences in known, we know the exact locations of the possible facilities $mathcalF$. Due to this extra information about the facilities, we are able to form powerful algorithms which have small {em distortion}, i.e., perform almost as well as omniscient algorithms but use only ordinal information about agent preferences. For example, we present natural social choice mechanisms for choosing a single facility to open with distortion of at most 3 for minimizing both the total and the median social cost; this factor is provably the best possible. We analyze many general problems including matching, $k$-center, and $k$-median, and present black-box reductions from omniscient approximation algorithms with approximation factor $$ to ordinal algorithms with approximation factor $$; doing this gives new ordinal algorithms for many important problems, and establishes a toolkit for analyzing such problems in the future.

Full work available at URL: https://arxiv.org/abs/1805.03103

Recommendations

• Randomized social choice functions under metric preferences
• The distortion of distributed metric social choice
• Peeking behind the ordinal curtain: improving distortion via cardinal queries
• Truthful Mechanisms for Matching and Clustering in an Ordinal World
• Approximating optimal social choice under metric preferences

zbMATH Keywords

matchingsocial choicefacility location problemsordinal algorithms

Mathematics Subject Classification ID

Social choice (91B14) Discrete location and assignment (90B80) Matching models (91B68)

Cites Work

• A Best Possible Heuristic for the k-Center Problem
• A 1.488 Approximation Algorithm for the Uncapacitated Facility Location Problem
• Advances in the spatial theory of voting.
• Sequential Deliberation for Social Choice
• An Improved Approximation for k-median, and Positive Correlation in Budgeted Optimization
• Random Matching Under Dichotomous Preferences
• Optimal social choice functions: a utilitarian view
• Social welfare in one-sided matching markets without money
• Randomized social choice functions under metric preferences
• Approximating optimal social choice under metric preferences
• Social welfare in one-sided matchings: random priority and beyond
• Subset selection via implicit utilitarian voting
• Combinatorial secretary problems with ordinal information
• Truthful facility assignment with resource augmentation: an exact analysis of serial dictatorship
• Truthful Mechanisms for Matching and Clustering in an Ordinal World

Cited In (10)

• On stable solutions to the ordinal social choice problem
• The distortion of distributed metric social choice
• The distortion of distributed metric social choice
• Randomized social choice functions under metric preferences
• Peeking behind the ordinal curtain: improving distortion via cardinal queries
• Don’t Roll the Dice, Ask Twice: The Two-Query Distortion of Matching Problems and Beyond
• Approximate mechanism design for distributed facility location
• Metric-distortion bounds under limited information
• Awareness of voter passion greatly improves the distortion of metric social choice
• Facility location games with optional preference

This page was built for publication: Ordinal approximation for social choice, matching, and facility location problems given candidate positions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2190377)