Social welfare in one-sided matchings: random priority and beyond
From MaRDI portal
Publication:2938641
Abstract: We study the problem of approximate social welfare maximization (without money) in one-sided matching problems when agents have unrestricted cardinal preferences over a finite set of items. Random priority is a very well-known truthful-in-expectation mechanism for the problem. We prove that the approximation ratio of random priority is Theta(n^{-1/2}) while no truthful-in-expectation mechanism can achieve an approximation ratio better than O(n^{-1/2}), where n is the number of agents and items. Furthermore, we prove that the approximation ratio of all ordinal (not necessarily truthful-in-expectation) mechanisms is upper bounded by O(n^{-1/2}), indicating that random priority is asymptotically the best truthful-in-expectation mechanism and the best ordinal mechanism for the problem.
Recommendations
- Social welfare in one-sided matching markets without money
- Efficiency of truthful and symmetric mechanisms in one-sided matching
- Beyond the worst-case analysis of random priority: smoothed and average-case approximation ratios in mechanism design
- Size versus truthfulness in the house allocation problem
- Welfare maximization and truthfulness in mechanism design with ordinal preferences
Cited in
(28)- The revealed preference theory of stable matchings with one-sided preferences
- Truthful Mechanisms for Matching and Clustering in an Ordinal World
- Efficiency of truthful and symmetric mechanisms in one-sided matching
- A pessimist's approach to one-sided matching
- One-sided version of Gale-Shapley proposal algorithm and its likely behavior under random preferences
- Bounded incentives in manipulating the probabilistic serial rule
- The distortion of distributed metric social choice
- The distortion of distributed metric social choice
- Truthful approximations to range voting
- Peeking behind the ordinal curtain: improving distortion via cardinal queries
- Smoothed and average-case approximation ratios of mechanisms: beyond the worst-case analysis
- Welfare maximization and truthfulness in mechanism design with ordinal preferences
- The price of anarchy of probabilistic serial in one-sided allocation problems
- Truthful facility assignment with resource augmentation: an exact analysis of serial dictatorship
- Optimizing over serial dictatorships
- Don’t Roll the Dice, Ask Twice: The Two-Query Distortion of Matching Problems and Beyond
- Revisiting the distortion of distributed voting
- Metric-distortion bounds under limited information
- Truthful ownership transfer with expert advice
- Tight distortion bounds for distributed metric voting on a line
- Beyond the worst-case analysis of random priority: smoothed and average-case approximation ratios in mechanism design
- Ordinal approximation for social choice, matching, and facility location problems given candidate positions
- The distortion of distributed facility location
- Social welfare in one-sided matching markets without money
- On mechanisms eliciting ordinal preferences
- Tight social welfare approximation of probabilistic serial
- Truthful facility assignment with resource augmentation: an exact analysis of serial dictatorship
- Optimizing over serial dictatorships
This page was built for publication: Social welfare in one-sided matchings: random priority and beyond
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2938641)
