No truthful mechanism can be better than $n$ approximate for two natural problems

Stefano Leucci, Akaki Mamageishvili, Paolo Penna

This work gives the first natural non-utilitarian problems for which the trivial $n$ approximation via VCG mechanisms is the best possible. That is, no truthful mechanism can be be…