Randomized social choice functions under metric preferences
From MaRDI portal
Abstract: We determine the quality of randomized social choice mechanisms in a setting in which the agents have metric preferences: every agent has a cost for each alternative, and these costs form a metric. We assume that these costs are unknown to the mechanisms (and possibly even to the agents themselves), which means we cannot simply select the optimal alternative, i.e. the alternative that minimizes the total agent cost (or median agent cost). However, we do assume that the agents know their ordinal preferences that are induced by the metric space. We examine randomized social choice functions that require only this ordinal information and select an alternative that is good in expectation with respect to the costs from the metric. To quantify how good a randomized social choice function is, we bound the distortion, which is the worst-case ratio between expected cost of the alternative selected and the cost of the optimal alternative. We provide new distortion bounds for a variety of randomized mechanisms, for both general metrics and for important special cases. Our results show a sizable improvement in distortion over deterministic mechanisms.
Recommendations
- The distortion of distributed metric social choice
- Approximating optimal social choice under metric preferences
- Optimal social choice functions: a utilitarian view
- Awareness of voter passion greatly improves the distortion of metric social choice
- Ordinal approximation for social choice, matching, and facility location problems given candidate positions
Cited in
(30)- The metric distortion of multiwinner voting
- Ordinal approximation for social choice, matching, and facility location problems given candidate positions
- Facility location games with optional preference
- Reallocating multiple facilities on the line
- Peeking behind the ordinal curtain: improving distortion via cardinal queries
- Approximate mechanism design for distributed facility location
- Metric-distortion bounds under limited information
- Truthful Mechanisms for Matching and Clustering in an Ordinal World
- Aggregation over metric spaces: proposing and voting in elections, budgeting, and legislation
- A Few Queries Go a Long Way: Information-Distortion Tradeoffs in Matching
- Representative committees of peers
- The distortion of distributed metric social choice
- The distortion of distributed voting
- The distortion of distributed metric social choice
- Strategyproof facility location with limited locations
- Truthful facility assignment with resource augmentation: an exact analysis of serial dictatorship
- More effort towards multiagent knapsack
- Don’t Roll the Dice, Ask Twice: The Two-Query Distortion of Matching Problems and Beyond
- The distortion of distributed facility location
- Primarily about primaries
- Approximating optimal social choice under metric preferences
- On the distortion of multi-winner election using single-candidate ballots
- Locating two facilities on a square with a minimum distance requirement
- Locating two facilities on a square with a minimum distance requirement
- Breaking the metric voting distortion barrier
- Improved metric distortion via threshold approvals
- The Condorcet dimension of metric spaces
- Utilitarian distortion with predictions
- Awareness of voter passion greatly improves the distortion of metric social choice
- Optimal social choice functions: a utilitarian view
This page was built for publication: Randomized social choice functions under metric preferences
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2985108)
