  We study the power of polynomial-time truthful mechanisms comparing to
polynomial time (non-truthful) algorithms. We show that there is a setting in
which deterministic polynomial-time truthful mechanisms cannot guarantee a
bounded approximation ratio, but a non-truthful FPTAS exists. We also show that
in the same setting there is a universally truthful mechanism that provides an
approximation ratio of 2. This shows that the cost of truthfulness is
unbounded. The proofs are almost standard in the field and follow from known
results.
