Black-box reductions in mechanism design

Zhiyi Huang, Lei Wang, Yuan Zhou

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationApproximation, Randomization, and Combinatorial Optimization
Subtitle of host publicationAlgorithms and Techniques - 14th International Workshop, APPROX 2011 and 15th International Workshop, RANDOM 2011, Proceedings
Pages254-265
Number of pages12
DOIs
StatePublished - Sep 8 2011
Externally publishedYes
Event14th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2011 and the 15th International Workshop on Randomization and Computation, RANDOM 2011 - Princeton, NJ, United States
Duration: Aug 17 2011Aug 19 2011

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume6845 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference14th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2011 and the 15th International Workshop on Randomization and Computation, RANDOM 2011
CountryUnited States
CityPrinceton, NJ
Period8/17/118/19/11

Fingerprint

Mechanism Design
Black Box
Approximation algorithms
Approximation Algorithms
Algorithmic Mechanism Design
Incentive Compatibility
Combinatorial Auctions
Approximability
Welfare
Convert
Permutation
Trade-offs
Game
Closed
Requirements
Approximation

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Cite this

Huang, Z., Wang, L., & Zhou, Y. (2011). Black-box reductions in mechanism design. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 14th International Workshop, APPROX 2011 and 15th International Workshop, RANDOM 2011, Proceedings (pp. 254-265). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6845 LNCS). https://doi.org/10.1007/978-3-642-22935-0_22

Black-box reductions in mechanism design. / Huang, Zhiyi; Wang, Lei; Zhou, Yuan.

Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 14th International Workshop, APPROX 2011 and 15th International Workshop, RANDOM 2011, Proceedings. 2011. p. 254-265 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 6845 LNCS).

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Huang, Z, Wang, L & Zhou, Y 2011, Black-box reductions in mechanism design. in Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 14th International Workshop, APPROX 2011 and 15th International Workshop, RANDOM 2011, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 6845 LNCS, pp. 254-265, 14th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2011 and the 15th International Workshop on Randomization and Computation, RANDOM 2011, Princeton, NJ, United States, 8/17/11. https://doi.org/10.1007/978-3-642-22935-0_22
Huang Z, Wang L, Zhou Y. Black-box reductions in mechanism design. In Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 14th International Workshop, APPROX 2011 and 15th International Workshop, RANDOM 2011, Proceedings. 2011. p. 254-265. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/978-3-642-22935-0_22
Huang, Zhiyi ; Wang, Lei ; Zhou, Yuan. / Black-box reductions in mechanism design. Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques - 14th International Workshop, APPROX 2011 and 15th International Workshop, RANDOM 2011, Proceedings. 2011. pp. 254-265 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).
@inproceedings{2cfd1c33c91a42499407d6f4afa320a6,
title = "Black-box reductions in mechanism design",
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.",
author = "Zhiyi Huang and Lei Wang and Yuan Zhou",
year = "2011",
month = "9",
day = "8",
doi = "10.1007/978-3-642-22935-0_22",
language = "English (US)",
isbn = "9783642229343",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
pages = "254--265",
booktitle = "Approximation, Randomization, and Combinatorial Optimization",

}

TY - GEN

T1 - Black-box reductions in mechanism design

AU - Huang, Zhiyi

AU - Wang, Lei

AU - Zhou, Yuan

PY - 2011/9/8

Y1 - 2011/9/8

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=80052369740&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=80052369740&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-22935-0_22

DO - 10.1007/978-3-642-22935-0_22

M3 - Conference contribution

AN - SCOPUS:80052369740

SN - 9783642229343

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 254

EP - 265

BT - Approximation, Randomization, and Combinatorial Optimization

ER -