Thumbnail
Access Restriction
Subscribed

Author Dughmi, Shaddin ♦ Roughgarden, Tim ♦ Yan, Qiqi
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Copyright Year ©2016
Language English
Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science
Subject Keyword Algorithmic mechanism design ♦ Combinatorial auctions
Abstract We design the first truthful-in-expectation, constant-factor approximation mechanisms for $\textit{NP}-hard$ cases of the welfare maximization problem in combinatorial auctions with nonidentical items and in combinatorial public projects. Our results apply to bidders with valuations that are nonnegative linear combinations of gross-substitute valuations, a class that encompasses many of the most well-studied subclasses of submodular functions, including coverage functions and weighted matroid rank functions. Our mechanisms have an expected polynomial runtime and achieve an approximation factor of 1 ™ $1/\textit{e}.$ This approximation factor is the best possible for both problems, even for known and explicitly given coverage valuations, assuming $\textit{P}$ ≠ $\textit{NP}.$ Recent impossibility results suggest that our results cannot be extended to a significantly larger valuation class. Both of our mechanisms are instantiations of a new framework for designing approximation mechanisms based on randomized rounding algorithms. The high-level idea of this framework is to optimize directly over the (random) output of the rounding algorithm, rather than the usual (and rarely truthful) approach of optimizing over the $\textit{input}$ to the rounding algorithm. This framework yields truthful-in-expectation mechanisms, which can be implemented efficiently when the corresponding objective function is concave. For bidders with valuations in the cone generated by gross-substitute valuations, we give novel randomized rounding algorithms that lead to both a concave objective function and a (1 ™ $1/\textit{e})-approximation$ of the optimal welfare.
Description Author Affiliation: Stanford University (Roughgarden, Tim); Google Research (Yan, Qiqi); University of Southern California (Dughmi, Shaddin)
ISSN 00045411
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2016-09-01
Publisher Place New York
e-ISSN 1557735X
Journal Journal of the ACM (JACM)
Volume Number 63
Issue Number 4
Page Count 33
Starting Page 1
Ending Page 33


Open content in new tab

   Open content in new tab
Source: ACM Digital Library