Truthful mechanisms with implicit payment computation

Abstract

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 for single-parameter domains: creating a randomized truthful mechanism is essentially as easy as a single call to a monotone allocation function. Our main result is a general procedure to take a monotone allocation rule and transform it (via a black-box reduction) into a randomized mechanism that is truthful in expectation and individually rational for every realization. Moreover, the mechanism implements the same outcome as the original allocation rule with probability arbitrarily close to 1, and requires evaluating that allocation rule only once.

Cite this work

No public copy is stored for this record, so only the metadata is cited.

Stored only when both papers are in the corpus — 73 citations exist upstream.

Papers that cite the same references — the relational fallback while embeddings are still backfilling.