Monday, April 19, 2010
4:00pm

5130 Upson Hall

Abstract:

This talk will focus on a new setting in which the goal is to design truthful mechanisms under a budget constraint on the mechanism's 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 will show that many ideas from the literature are no longer applicable in this environment, and that in many cases the budget constraint can render mechanisms with arbitrarily bad performance. 

Our main result shows that for the class of submodular maximization problems, budget feasible mechanisms with bounded approximation ratios are achievable.   In our exploration of the space of budget feasible mechanisms we will highlight interesting connections between this setting and ideas from cost sharing, frugality, and convex optimization.