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.