Efficient Money Burning in General Domains

Abstract

We study mechanism design where the payments charged to the agents are not in the form of monetary transfers, but are effectively burned. In this setting, the objective is to maximize social utility, i.e., the social welfare minus the payments charged. We consider a general setting with m discrete outcomes and n multidimensional agents. We present two essentially orthogonal randomized truthful mechanisms that extract an $O(\log m)$ fraction of the maximum welfare as social utility. Moreover, the first mechanism achieves a $O(\log m)$-approximation for the social welfare, which is improved to an O(1)-approximation by the second mechanism. An interesting feature of the second mechanism is that it optimizes over an appropriately “smoothed” space, thus achieving a nice and smooth tradeoff between welfare approximation and the payments charged.

This research was supported by the project AlgoNow, co-financed by the European Union (European Social Fund - ESF) and Greek national funds, through the Operational Program “Education and Lifelong Learning” of the National Strategic Reference Framework (NSRF) - Research Funding Program: THALES, investing in knowledge society through the European Social Fund.