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.