File Download

There are no files associated with this item.

  Links for fulltext
     (May Require Subscription)
Supplementary

Conference Paper: Black-box reductions in mechanism design

TitleBlack-box reductions in mechanism design
Authors
Issue Date2011
PublisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/
Citation
Lecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2011, v. 6845 LNCS, p. 254-265 How to Cite?
AbstractA central question in algorithmic mechanism design is to understand the additional difficulty introduced by truthfulness requirements in the design of approximation algorithms for social welfare maximization. In this paper, by studying the problem of single-parameter combinatorial auctions, we obtain the first black-box reduction that converts any approximation algorithm to a truthful mechanism with essentially the same approximation factor in a prior-free setting. In fact, our reduction works for the more general class of symmetric single-parameter problems. Here, a problem is symmetric if its allocation space is closed under permutations. As extensions, we also take an initial step towards exploring the power of black-box reductions for general single-parameter and multi-parameter problems by showing several positive and negative results. We believe that the algorithmic and game theoretic insights gained from our approach will help better understand the tradeoff between approximability and the incentive compatibility. © 2011 Springer-Verlag.
Persistent Identifierhttp://hdl.handle.net/10722/188492
ISSN
2005 Impact Factor: 0.402
2015 SCImago Journal Rankings: 0.252
References

 

DC FieldValueLanguage
dc.contributor.authorHuang, Zen_US
dc.contributor.authorWang, Len_US
dc.contributor.authorZhou, Yen_US
dc.date.accessioned2013-09-03T04:08:43Z-
dc.date.available2013-09-03T04:08:43Z-
dc.date.issued2011en_US
dc.identifier.citationLecture Notes In Computer Science (Including Subseries Lecture Notes In Artificial Intelligence And Lecture Notes In Bioinformatics), 2011, v. 6845 LNCS, p. 254-265en_US
dc.identifier.issn0302-9743en_US
dc.identifier.urihttp://hdl.handle.net/10722/188492-
dc.description.abstractA central question in algorithmic mechanism design is to understand the additional difficulty introduced by truthfulness requirements in the design of approximation algorithms for social welfare maximization. In this paper, by studying the problem of single-parameter combinatorial auctions, we obtain the first black-box reduction that converts any approximation algorithm to a truthful mechanism with essentially the same approximation factor in a prior-free setting. In fact, our reduction works for the more general class of symmetric single-parameter problems. Here, a problem is symmetric if its allocation space is closed under permutations. As extensions, we also take an initial step towards exploring the power of black-box reductions for general single-parameter and multi-parameter problems by showing several positive and negative results. We believe that the algorithmic and game theoretic insights gained from our approach will help better understand the tradeoff between approximability and the incentive compatibility. © 2011 Springer-Verlag.en_US
dc.languageengen_US
dc.publisherSpringer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/en_US
dc.relation.ispartofLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)en_US
dc.titleBlack-box reductions in mechanism designen_US
dc.typeConference_Paperen_US
dc.identifier.emailHuang, Z: hzhiyi@cis.upenn.eduen_US
dc.identifier.authorityHuang, Z=rp01804en_US
dc.description.naturelink_to_subscribed_fulltexten_US
dc.identifier.doi10.1007/978-3-642-22935-0_22en_US
dc.identifier.scopuseid_2-s2.0-80052369740en_US
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-80052369740&selection=ref&src=s&origin=recordpageen_US
dc.identifier.volume6845 LNCSen_US
dc.identifier.spage254en_US
dc.identifier.epage265en_US
dc.publisher.placeGermanyen_US
dc.identifier.scopusauthoridHuang, Z=55494568500en_US
dc.identifier.scopusauthoridWang, L=36066093100en_US
dc.identifier.scopusauthoridZhou, Y=35489722600en_US

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats