Truthful Mechanisms with Implicit Payment Computation
M. Babaioff, R. Kleinberg, and A. Slivkins. (2010)cite arxiv:1004.3630Comment: This is a full version of the paper in 11th ACM Conf. on Electronic Commerce (EC), 2010..
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. Because our reduction is simple,
versatile, and general, it has many applications to mechanism design problems
in which re-evaluating the allocation function is either burdensome or
informationally impossible. Applying our result to the multi-armed bandit
problem, we obtain truthful randomized mechanisms whose regret matches the
information-theoretic lower bound up to logarithmic factors, even though prior
work showed this is impossible for truthful deterministic mechanisms. We also
present applications to offline mechanism design, showing that randomization
can circumvent a communication complexity lower bound for deterministic
payments computation, and that it can also be used to create truthful shortest
path auctions that approximate the welfare of the VCG allocation arbitrarily
well, while having the same running time complexity as Dijkstra's algorithm.
Description
[1004.3630] Truthful Mechanisms with Implicit Payment Computation
%0 Generic
%1 babaioff2010truthful
%A Babaioff, Moshe
%A Kleinberg, Robert D.
%A Slivkins, Aleksandrs
%D 2010
%K cloud computation payment
%T Truthful Mechanisms with Implicit Payment Computation
%U http://arxiv.org/abs/1004.3630
%X 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. Because our reduction is simple,
versatile, and general, it has many applications to mechanism design problems
in which re-evaluating the allocation function is either burdensome or
informationally impossible. Applying our result to the multi-armed bandit
problem, we obtain truthful randomized mechanisms whose regret matches the
information-theoretic lower bound up to logarithmic factors, even though prior
work showed this is impossible for truthful deterministic mechanisms. We also
present applications to offline mechanism design, showing that randomization
can circumvent a communication complexity lower bound for deterministic
payments computation, and that it can also be used to create truthful shortest
path auctions that approximate the welfare of the VCG allocation arbitrarily
well, while having the same running time complexity as Dijkstra's algorithm.
@misc{babaioff2010truthful,
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. Because our reduction is simple,
versatile, and general, it has many applications to mechanism design problems
in which re-evaluating the allocation function is either burdensome or
informationally impossible. Applying our result to the multi-armed bandit
problem, we obtain truthful randomized mechanisms whose regret matches the
information-theoretic lower bound up to logarithmic factors, even though prior
work showed this is impossible for truthful deterministic mechanisms. We also
present applications to offline mechanism design, showing that randomization
can circumvent a communication complexity lower bound for deterministic
payments computation, and that it can also be used to create truthful shortest
path auctions that approximate the welfare of the VCG allocation arbitrarily
well, while having the same running time complexity as Dijkstra's algorithm.},
added-at = {2012-05-07T12:49:22.000+0200},
author = {Babaioff, Moshe and Kleinberg, Robert D. and Slivkins, Aleksandrs},
biburl = {https://www.bibsonomy.org/bibtex/2ff8c970ff13d755dfacbaad92e7a2374/sac},
description = {[1004.3630] Truthful Mechanisms with Implicit Payment Computation},
interhash = {809ee44fcba0372c1a4abf1065e28972},
intrahash = {ff8c970ff13d755dfacbaad92e7a2374},
keywords = {cloud computation payment},
note = {cite arxiv:1004.3630Comment: This is a full version of the paper in 11th ACM Conf. on Electronic Commerce (EC), 2010.},
timestamp = {2012-05-07T12:49:22.000+0200},
title = {Truthful Mechanisms with Implicit Payment Computation},
url = {http://arxiv.org/abs/1004.3630},
year = 2010
}