Randomized methods in algorithmic mechanism design

算法机制设计中的随机方法

• 批准号: 230665258
• 负责人: Professorin Dr. Britta Peis, since 11/2014
• 金额: --
• 依托单位: Lehrstuhl für Management Science (OMS)
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2013
• 资助国家: 德国
• 起止时间: 2012-12-31 至 2019-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/230665258?language=en
• 关键词: Randomized; methods; 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.

算法机制设计领域涉及高效计算和激励兼容算法的开发和分析。这一领域的一个核心问题是在组合拍卖中将资源分配给具有私下已知估值函数的代理人。特别是在多维估值函数的情况下，激励相容对算法的限制是严格的，而且还没有得到充分的理解。各种确定性的方法已经被排除，以产生良好的近似因子。然而，最近的研究表明，对于一些基本的分配问题，随机机制能够保证良好的逼近因子。在该项目中，我们扩展和深化了随机化机制设计的最新进展。为此，我们探索了新的算法方法，并将其应用于在线和离线环境中的各种组合拍卖，并研究了随机化方法的使用对于设计激励相容机制的必要性。

项目成果

Extensions of secretary problems towards submodular objectives and temporal arrival

秘书问题向子模目标和时间到达的扩展

• DOI: 10.18154/rwth-2017-02825
• 作者: Andreas Tönnis

An Optimal Truthful Mechanism for the Online Weighted Bipartite Matching Problem

• DOI: 10.1137/1.9781611975482.120
• 发表时间: 2019-01
• 作者: Rebecca Reiffenhäuser