Budget Feasible Mechanisms
Budget Feasible Mechanisms
复制标题
DOI：
10.1109/focs.2010.78
复制
发表时间：
2010-02
期刊：
影响因子：
--
通讯作者：
Yaron Singer
中科院分区：
文献类型：
--
作者：
Yaron Singer
我们研究了一类新颖的机制设计问题，其中结果受到支付的限制。这一类基本的机制设计问题涵盖了许多常见的经济情况，但据我们所知，过去尚未对其进行研究。我们关注采购拍卖的情况，其中卖方有私人成本，拍卖师的目标是在该机制提供的付款总和不超过给定预算的约束下最大化物品子集的效用函数。标准机制设计思想（例如 VCG 机制及其变体）在这里不适用。我们表明，对于一般功能，预算约束可以使机制在购买者的效用方面变得任意糟糕。然而，我们的主要结果表明，对于重要的子模函数类别，可以实现有界逼近比。对于子模函数的子类可以获得更好的近似结果。我们探索其他领域的预算可行机制空间，并在更受限的条件下给出特征。
We study a novel class of mechanism design problems in which the outcomes are constrained by the payments. This basic class of mechanism design problems captures many common economic situations, and yet it has not been studied, to our knowledge, in the past. We focus on the case of procurement auctions in which sellers have private costs, and the auctioneer aims to maximize a utility function on subsets of items, under the constraint that the sum of the payments provided by the mechanism does not exceed a given budget. Standard mechanism design ideas such as the VCG mechanism and its variants are not applicable here. We show that, for general functions, the budget constraint can render mechanisms arbitrarily bad in terms of the utility of the buyer. However, our main result shows that for the important class of sub modular functions, a bounded approximation ratio is achievable. Better approximation results are obtained for subclasses of the sub modular functions. We explore the space of budget feasible mechanisms in other domains and give a characterization under more restricted conditions.