Apr, 2017
对称次模目标的预算可行机制设计
On Budget-Feasible Mechanism Design for Symmetric Submodular Objectives
Georgios Amanatidis, Georgios Birmpas, Evangelos Markakis
TL;DR本文研究了一类采购拍卖问题，涉及到预算约束和非单调子模价值函数。我们提出了可行的机制来最大化拍卖者的估值函数，同时也满足诚实、可行和近似最优的要求，本文所提机制在增加了预算约束的条件下，显著改进了以往的方法。其中以最大割问题为重点，在此问题上，我们的结果显著提高了已知的近似比，同时为只有指数级机制的情况建立了多项式运行时间的结果。