Budget Feasible Mechanisms

被引:180
作者
Singer, Yaron [1 ]
机构
[1] Univ Calif Berkeley, Dept Comp Sci, Berkeley, CA 94720 USA
来源
2010 IEEE 51ST ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE | 2010年
关键词
AUCTIONS;
D O I
10.1109/FOCS.2010.78
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
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 submodular functions, a bounded approximation ratio is achievable. Better approximation results are obtained for subclasses of the submodular functions. We explore the space of budget feasible mechanisms in other domains and give a characterization under more restricted conditions.
引用
收藏
页码:765 / 774
页数:10
相关论文
共 27 条
  • [1] Pipage rounding: A new method of constructing algorithms with proven performance guarantee
    Ageev, AA
    Sviridenko, MI
    [J]. JOURNAL OF COMBINATORIAL OPTIMIZATION, 2004, 8 (03) : 307 - 328
  • [2] Aggarwal Gagan, 2008, SIGACT News, V39, P10, DOI 10.1145/1388240.1388242
  • [3] [Anonymous], 2005, Proc. ACM EC
  • [4] Frugal Path Mechanisms
    Archer, Aaron
    Tardos, Eva
    [J]. ACM TRANSACTIONS ON ALGORITHMS, 2007, 3 (01)
  • [5] Ashlagi I, 2009, 10TH ACM CONFERENCE ON ELECTRONIC COMMERCE - EC 2009, P169
  • [6] Blumrosen Liad., 2005, ACM Conference on Electronic Commerce, P29, DOI DOI 10.1145/1064009.1064013
  • [7] Bulow J., WINNING PLAY SPECTRU
  • [8] Cary MC, 2008, PROCEEDINGS OF THE NINETEENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, P304
  • [9] Multi-unit Auctions with Budget Limits
    Dobzinski, Shahar
    Lavi, Ron
    Nisan, Noam
    [J]. PROCEEDINGS OF THE 49TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, 2008, : 260 - +
  • [10] Dobzinski S, 2008, EC'08: PROCEEDINGS OF THE 2008 ACM CONFERENCE ON ELECTRONIC COMMERCE, P38