Social welfare in one-sided matchings: random priority and beyond
From MaRDI portal
Publication:2938641
DOI10.1007/978-3-662-44803-8_1zbMATH Open1403.91259arXiv1403.1508OpenAlexW1830090996MaRDI QIDQ2938641FDOQ2938641
Authors: Aris Filos-Ratsikas, Søren Kristoffer Stiil Frederiksen, Jie Zhang 
Publication date: 14 January 2015
Published in: Algorithmic Game Theory (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1403.1508
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)
- Truthful Mechanisms for Matching and Clustering in an Ordinal World
- The revealed preference theory of stable matchings with one-sided preferences
- Efficiency of truthful and symmetric mechanisms in one-sided matching
- A pessimist's approach to one-sided matching
- Bounded incentives in manipulating the probabilistic serial rule
- One-sided version of Gale-Shapley proposal algorithm and its likely behavior under random preferences
- 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
- The price of anarchy of probabilistic serial in one-sided allocation problems
- Welfare maximization and truthfulness in mechanism design with ordinal preferences
- 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
- The distortion of distributed facility location
- Ordinal approximation for social choice, matching, and facility location problems given candidate positions
- 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)
