Interdependent values make basic auction design tasks -- in particular maximizing welfare truthfully in single-item auctions -- quite challenging. Eden et al. recently established that if the bidders valuation functions are submodular over their signals (a.k.a. SOS), a truthful 4-approximation to the optimal welfare exists. We show existence of a mechanism that is truthful and achieves a tight 2-approximation to the optimal welfare when signals are binary. Our mechanism is randomized and assigns bidders only 0 or 0.5 probabilities of winning the item. Our results utilize properties of submodular set functions, and extend to matroid settings.
翻译:相互依存的价值使得基本的拍卖设计任务 -- -- 特别是在单一项目拍卖中真正地最大限度地实现福利 -- -- 变得相当具有挑战性。Eden等人最近确定,如果投标人的估值功能低于其信号(a.k.a.SOS),则存在对最佳福利的真诚的4赞同。我们表明存在一个真实的机制,当信号为二元时,实现对最佳福利的严格2同意。我们的机制是随机化的,只分配出0或0.5的胜标概率。我们的结果利用了子模块设定功能的特性,并扩展到了配制环境。