Randomized methods in algorithmic mechanism design

点击翻译按钮获取中文摘要

The area of algorithmic mechanism design deals with the development and analysis of efficiently computable and incentive compatible algorithms. A core problem in this field is the allocation of resources to agents with privately known valuation functions in combinatorial auctions. Especially in the case of multi-dimensional valuation functions, the algorithmic restrictions imposed by incentive compatibility are severe and not sufficiently well understood. Various deterministic approaches have been ruled out to yield good approximation factors. Recent studies show, however, that randomized mechanisms are able to guarantee good approximation factors for some fundamental allocation problems. In the project, we extend and deepen the state of the art of randomized mechanism design. Towards this end, we explore new algorithmic approaches with applications to various kinds of combinatorial auctions in online and offline settings, and we investigate to which extend the use of randomized methods is essential for the design of incentive compatible mechanisms.