  The approximation ratio has become one of the dominant measures in mechanism
design problems. In light of analysis of algorithms, we define the
\emph{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 worst-case inputs, and define the \emph{average-case
approximation ratio} to compare the performance of these two mechanisms when
the inputs follow a distribution. For the one-sided matching problem,
\citet{FFZ:14} show that, amongst all truthful mechanisms, \emph{random
priority} achieves the tight approximation ratio bound of $\Theta(\sqrt{n})$.
We prove that, despite of this worst-case bound, random priority has a
\emph{constant smoothed approximation ratio}. This is, to our limited
knowledge, the first work that asymptotically differentiates the smoothed
approximation ratio from the worst-case approximation ratio for mechanism
design problems. For the average-case, 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
average-case analysis for approximate mechanism design problems, beyond the
worst-case analysis.

Computer Science and Game Theory