Deng, Xiaotie ;
Gao, Yansong ;
Zhang, Jie
Smoothed and AverageCase Approximation Ratios of Mechanisms: Beyond the WorstCase Analysis
Abstract
The approximation ratio has become one of the dominant measures in mechanism design problems. In light of analysis of algorithms, we define the smoothed approximation ratio to compare the performance of the optimal mechanism and a truthful mechanism when the inputs are subject to random perturbations of the worstcase inputs, and define the averagecase approximation ratio to compare the performance of these two mechanisms when the inputs follow a distribution. For the onesided matching problem, FilosRatsikas et al. [2014] show that, amongst all truthful mechanisms, random priority achieves the tight approximation ratio bound of Theta(sqrt{n}). We prove that, despite of this worstcase bound, random priority has a constant smoothed approximation ratio. This is, to our limited knowledge, the first work that asymptotically differentiates the smoothed approximation ratio from the worstcase approximation ratio for mechanism design problems. For the averagecase, we show that our approximation ratio can be improved to 1+e. These results partially explain why random priority has been successfully used in practice, although in the worst case the optimal social welfare is Theta(sqrt{n}) times of what random priority achieves.
These results also pave the way for further studies of smoothed and averagecase analysis for approximate mechanism design problems, beyond the worstcase analysis.
BibTeX  Entry
@InProceedings{deng_et_al:LIPIcs:2017:8093,
author = {Xiaotie Deng and Yansong Gao and Jie Zhang},
title = {{Smoothed and AverageCase Approximation Ratios of Mechanisms: Beyond the WorstCase Analysis}},
booktitle = {42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
pages = {16:116:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770460},
ISSN = {18688969},
year = {2017},
volume = {83},
editor = {Kim G. Larsen and Hans L. Bodlaender and JeanFrancois Raskin},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2017/8093},
URN = {urn:nbn:de:0030drops80936},
doi = {10.4230/LIPIcs.MFCS.2017.16},
annote = {Keywords: mechanism design, approximation ratio, smoothed analysis, averagecase analysis}
}
2017
Keywords: 

mechanism design, approximation ratio, smoothed analysis, averagecase analysis 
Seminar: 

42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Issue date: 

2017 
Date of publication: 

2017 