Budget Feasible Mechanisms

By Yaron Singer. IEEE Annual Symposium on Foundations of Computer Science, 2010

298 citations recorded by the source corpus.

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.

Subfields: Economics and Econometrics, Management Science and Operations Research, Marketing

View Paper: https://www.semanticscholar.org/paper/0fd785de3b5e1c1aa5f398f7120cd524e43cc863

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Economics and Econometrics

1. Andreas Krause
2. Guoliang Xue
3. Xi Fang
4. Adish Kumar Singla
5. Jian Tang
6. Dejun Yang

In Management Science and Operations Research

1. Guoliang Xue
2. Xi Fang
3. Jian Tang
4. Dejun Yang
5. Adish Kumar Singla
6. Andreas Krause
7. Iordanis Koutsopoulos
8. Aleksandrs Slivkins

In Marketing

1. Andreas Krause
2. Guoliang Xue
3. Xi Fang
4. Adish Kumar Singla
5. Jian Tang
6. Dejun Yang

Citations in the corpus

• How to crowdsource tasks truthfully without sacrificing utility: Online incentive mechanisms with budget constraint (2014, background): “If by the time the user arrives there are no remaining budget, then the user’s cost declaration will not affect the allocation of the mechanism and thus cannot improve its utility by submitting a false cost.”
• Incentive Mechanisms for Crowdsensing: Crowdsourcing With Smartphones (2016, methodology): “to make use of the off-the-shelf results on the budgeted mechanism design [4], [39].”
• Crowdsourcing to smartphones: incentive mechanism design for mobile phone sensing (2012, background): “One possible direction is to make use of the off-the-shelf results on the budgeted mechanism design [2, 24].”
• Truthful incentives in crowdsourcing tasks using regret minimization mechanisms (2013, background): “In contrast, we are interested in studying truthful budget feasible mechanisms initiated recently in [30] [31].”