Beyond the worst-case analysis of random priority: Smoothed and average-case approximation ratios in mechanism design

Xiaotie Deng, Yansong Gao, Jie Zhang

Research output: Contribution to journalArticlepeer-review

Abstract

A mechanism for the random assignment problem takes agents' private preferences over items as input and outputs an allocation. One of the mainstream mechanisms, Random Priority, is asymptotically the best mechanism for welfare maximization. However, its approximation ratio is , which implies that there is a large discrepancy between its performance and the optimal social welfare. We evaluate the performance of Random Priority beyond the worst-case analysis in the hope of addressing the inconsistency between the widespread use of the mechanism in practice and the undesired theoretical performance guarantee. We show that with small random noise applied to the worst-case inputs, Random Priority has a constant smoothed approximation ratio. When agents' preference values are independent random variables, Random Priority is nearly optimal evaluated by the average-case approximation ratio. En route to these results, we develop analytics tools to show the insights that the efficiency loss is small on most instances. To our limited knowledge, this is the first work that introduces smoothed analysis to algorithmic mechanism design problems. These results may pave the way for further studies for approximate mechanism design problems beyond the worst-case analysis.
Original languageEnglish
Article number104920
JournalInformation and Computation
Volume285
Issue numberPart B
Early online date18 May 2022
DOIs
Publication statusPublished - 31 May 2022

Keywords

  • Approximation ratio
  • Average-case analysis
  • Mechanism design
  • Smoothed analysis

Fingerprint

Dive into the research topics of 'Beyond the worst-case analysis of random priority: Smoothed and average-case approximation ratios in mechanism design'. Together they form a unique fingerprint.

Cite this