We consider budget constrained combinatorial auctions where associated with every bidder i is a set of items of interest S_i, and a private value v_i. The value of S \subset S_i to bidder i is v_i |S|.
Such auctions capture adword auctions, where advertisers offer a bid for those adwords that (hopefully) reach their target audience, and advertisers also have budgets. Our main result is a novel auction that runs in polynomial time, is incentive compatible, and ensures Pareto-optimality. We also show that our results are tight in the sense that there is no incentive compatible and Pareto optimal auction for more general valuation functions.
Joint work with Stefano Leonardi, Jared Saia, and Piotr Sankowsky.