Single valued combinatorial auctions with budgets

A Fiat, S Leonardi, J Saia, P Sankowski - … of the 12th ACM conference on …, 2011 - dl.acm.org
Proceedings of the 12th ACM conference on Electronic commerce, 2011dl.acm.org
We consider budget constrained combinatorial auctions where each bidder has a private
value for each of the items in some subset of the items and an overall budget constraint.
Such auctions capture adword auctions, where advertisers offer a bid for those adwords that
(hopefully) target their intended audience, and advertisers also have budgets. It is known
that even if all items are identical and all budgets are public it is not possible to be truthful
and efficient. Our main result is a novel auction that runs in polynomial time, is incentive …
We consider budget constrained combinatorial auctions where each bidder has a private value for each of the items in some subset of the items and an overall budget constraint. Such auctions capture adword auctions, where advertisers offer a bid for those adwords that (hopefully) target their intended audience, and advertisers also have budgets. It is known that even if all items are identical and all budgets are public it is not possible to be truthful and efficient. Our main result is a novel auction that runs in polynomial time, is incentive compatible, and ensures Pareto-optimality. The auction is incentive compatible with respect to the private valuations whereas the budgets and the sets of interest are assumed to be public knowledge. This extends the result of Dobzinski, Lavi and Nisan (FOCS 2008) for auctions of multiple identical items with bugets to single-valued combinatorial auctions and address one of the basic challenges on auctioning web ads (see Nisan et al, 2009, Google auctions for tv ads).
ACM Digital Library
以上显示的是最相近的搜索结果。 查看全部搜索结果