Truthful Mechanisms with Implicit Payment Computation

Moshe Babaioff, Robert D. Kleinberg, Aleksandrs Slivkins

It is widely believed that computing payments needed to induce truthful bidding is somehow harder than simply computing the allocation. We show that the opposite is true: creating…