File Download
There are no files associated with this item.
Links for fulltext
(May Require Subscription)
- Publisher Website: 10.1007/978-3-642-22935-0_22
- Scopus: eid_2-s2.0-80052369740
- Find via
Supplementary
-
Citations:
- Scopus: 0
- Appears in Collections:
Conference Paper: Black-box reductions in mechanism design
Title | Black-box reductions in mechanism design |
---|---|
Authors | |
Issue Date | 2011 |
Publisher | Springer 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? |
Abstract | A 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 Identifier | http://hdl.handle.net/10722/188492 |
ISSN | 2023 SCImago Journal Rankings: 0.606 |
References |
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Huang, Z | en_US |
dc.contributor.author | Wang, L | en_US |
dc.contributor.author | Zhou, Y | en_US |
dc.date.accessioned | 2013-09-03T04:08:43Z | - |
dc.date.available | 2013-09-03T04:08:43Z | - |
dc.date.issued | 2011 | en_US |
dc.identifier.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 | en_US |
dc.identifier.issn | 0302-9743 | en_US |
dc.identifier.uri | http://hdl.handle.net/10722/188492 | - |
dc.description.abstract | A 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.language | eng | en_US |
dc.publisher | Springer Verlag. The Journal's web site is located at http://springerlink.com/content/105633/ | en_US |
dc.relation.ispartof | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) | en_US |
dc.title | Black-box reductions in mechanism design | en_US |
dc.type | Conference_Paper | en_US |
dc.identifier.email | Huang, Z: hzhiyi@cis.upenn.edu | en_US |
dc.identifier.authority | Huang, Z=rp01804 | en_US |
dc.description.nature | link_to_subscribed_fulltext | en_US |
dc.identifier.doi | 10.1007/978-3-642-22935-0_22 | en_US |
dc.identifier.scopus | eid_2-s2.0-80052369740 | en_US |
dc.relation.references | http://www.scopus.com/mlt/select.url?eid=2-s2.0-80052369740&selection=ref&src=s&origin=recordpage | en_US |
dc.identifier.volume | 6845 LNCS | en_US |
dc.identifier.spage | 254 | en_US |
dc.identifier.epage | 265 | en_US |
dc.publisher.place | Germany | en_US |
dc.identifier.scopusauthorid | Huang, Z=55494568500 | en_US |
dc.identifier.scopusauthorid | Wang, L=36066093100 | en_US |
dc.identifier.scopusauthorid | Zhou, Y=35489722600 | en_US |
dc.identifier.issnl | 0302-9743 | - |