Randomized methods in algorithmic mechanism design

• Applicant: Professorin Dr. Britta Peis, since 11/2014
• Subject Area: Theoretical Computer Science
• Term: from 2013 to 2020
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 230665258

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.

• DFG Programme: Research Grants
• Ehemaliger Antragsteller: Professor Dr. Berthold Vöcking, until 11/2014 (†)