Amplified Hardness of Approximation for VCG-Based Mechanisms

Shaddin Dughmi, Hu Fu, Robert Kleinberg

If a two-player social welfare maximization problem does not admit a PTAS, we prove that any maximal-in-range truthful mechanism that runs in polynomial time cannot achieve an appr…