Back to Search
Start Over
Truthful randomized mechanisms for combinatorial auctions
- Source :
-
Journal of Computer & System Sciences . Jan2012, Vol. 78 Issue 1, p15-25. 11p. - Publication Year :
- 2012
-
Abstract
- Abstract: We present a new framework for the design of computationally-efficient and incentive-compatible mechanisms for combinatorial auctions. The mechanisms obtained via this framework are randomized, and obtain incentive compatibility in the universal sense (in contrast to the substantially weaker notion of incentive compatibility in expectation). We demonstrate the usefulness of our techniques by exhibiting two mechanisms for combinatorial auctions with general bidder preferences. The first mechanism obtains an optimal -approximation to the optimal social welfare for arbitrary bidder valuations. The second mechanism obtains an -approximation for a class of bidder valuations that contains the important class of submodular bidders. These approximation ratios greatly improve over the best (known) deterministic incentive-compatible mechanisms for these classes. [Copyright &y& Elsevier]
Details
- Language :
- English
- ISSN :
- 00220000
- Volume :
- 78
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- Journal of Computer & System Sciences
- Publication Type :
- Academic Journal
- Accession number :
- 67517868
- Full Text :
- https://doi.org/10.1016/j.jcss.2011.02.010