More Web Proxy on the site http://driver.im/

research-article

Bayesian incentive compatibility via fractional assignments

Authors:

Zhiyi HuangAuthors Info & Claims

SODA '11: Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms

Pages 720 - 733

Published: 23 January 2011 Publication History

Abstract

Very recently, Hartline and Lucier [14] studied single-parameter mechanism design problems in the Bayesian setting. They proposed a black-box reduction that converted Bayesian approximation algorithms into Bayesian-Incentive-Compatible (BIC) mechanisms while preserving social welfare. It remains a major open question if one can find similar reduction in the more important multi-parameter setting. In this paper, we give positive answer to this question when the prior distribution has finite and small support. We propose a black-box reduction for designing BIC multi-parameter mechanisms. The reduction converts any algorithm into an ε-BIC mechanism with only marginal loss in social welfare. As a result, for combinatorial auctions with sub-additive agents we get an ε-BIC mechanism that achieves constant approximation.

References

[1]

S. Bhattacharya, G. Goel, S. Gollapudi, and K. Munagala. Budget constrained auctions with heterogeneous items. In ACM 42nd Annual ACM Symposium on Theory of Computing (STOC), 2010.

Digital Library

[2]

S. Chawla, J. D. Hartline, D. Malec, and B. Sivan. Multi-parameter mechanism design and sequential posted pricing. In ACM 42nd Annual ACM Symposium on Theory of Computing (STOC), 2010.

Digital Library

[3]

E. H. Clarke. Multipart pricing of public goods. Public choice, 11(1):17--33, 1971.

[4]

S. Dobzinski. Two randomized mechanisms for combinatorial auctions. Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, pages 89--103, 2007.

Digital Library

[5]

S. Dobzinski, N. Nisan, and M. Schapira. Approximation algorithms for combinatorial auctions with complement-free bidders. In ACM 37th Annual ACM Symposium on Theory of Computing (STOC), page 618. ACM, 2005.

Digital Library

[6]

S. Dobzinski, N. Nisan, and M. Schapira. Truthful randomized mechanisms for combinatorial auctions. In ACM 38th Annual ACM Symposium on Theory of Computing (STOC), page 652. ACM, 2006.

Digital Library

[7]

S. Dughmi and T. Roughgarden. Black-box randomized reductions in algorithmic mechanism design. In 51st Annual IEEE Symposium on Foundations of Computer Science (FOCS), 2010.

Digital Library

[8]

U. Feige. On maximizing welfare when utility functions are subadditive. In ACM 38th Annual ACM Symposium on Theory of Computing (STOC), page 50. ACM, 2006.

Digital Library

[9]

U. Feige and J. Vondrak. Approximation algorithms for allocation problems: Improving the factor of 1-1/e. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 667--676, 2006.

Digital Library

[10]

T. Groves. Incentives in teams. Econometrica: Journal of the Econometric Society, 41(4):617--631, 1973.

[11]

F. Gul and E. Stacchetti. Walrasian Equilibrium with Gross Substitutes* 1. Journal of Economic Theory, 87(1):95--124, 1999.

[12]

V. Guruswami, J. D. Hartline, A. R. Karlin, D. Kempe, C. Kenyon, and F. McSherry. On profit-maximizing envy-free pricing. In Annual ACM-SIAM Symposium on Discrete algorithms, page 1173. Society for Industrial and Applied Mathematics, 2005.

Digital Library

[13]

J. Hartline, R. Kleinberg, and A. Malekian. Bayesian incentive compatibility via matchings. In Annual ACM-SIAM Symposium on Discrete algorithms, to appear, 2011.

Digital Library

[14]

J. D. Hartline and B. Lucier. Bayesian algorithmic mechanism design. In ACM 42nd Annual ACM Symposium on Theory of Computing (STOC), 2010.

Digital Library

[15]

J. D. Hartline and T. Roughgarden. Optimal mechanism design and money burning. In ACM 40th Annual ACM Symposium on Theory of Computing (STOC), 2008.

Digital Library

[16]

R. Lavi and C. Swamy. Truthful and near-optimal mechanism design via linear programming. In 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 595--604, 2005.

Digital Library

[17]

R. B. Myerson. Optimal auction design. Mathematics of operations research, 6(1):58--73, 1981.

[18]

C. Papadimitriou, M. Schapira, and Y. Singer. On the hardness of being truthful. In 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS), pages 250--259, 2008.

Digital Library

[19]

J. C. Rochet. A necessary and sufficient condition for rationalizability in a quasi-linear context. Journal of Mathematical Economics, 16(2):191--200, 1987.

[20]

W. Vickrey. Counterspeculation, auctions, and competitive sealed tenders. Journal of finance, 16(1):8--37, 1961.

Cited By

Derakhshan MRyu EWeinberg SXue EKleinberg RSaban DBergemann D(2024)Settling the Competition Complexity of Additive Buyers over Independent ItemsProceedings of the 25th ACM Conference on Economics and Computation10.1145/3670865.3673627(420-446)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3670865.3673627
Cai YOikonomou AVelegkas GZhao MMarx D(2021)An efficient ε-BIC to BIC transformation and its application to black-box reduction in revenue maximizationProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458145(1337-1356)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458145
Gonczarowski YWeinberg S(2021)The Sample Complexity of Up-to-ε Multi-dimensional Revenue MaximizationJournal of the ACM10.1145/343972268:3(1-28)Online publication date: 22-Mar-2021
https://dl.acm.org/doi/10.1145/3439722
Show More Cited By

Bayesian incentive compatibility via fractional assignments
1. Computing methodologies
  1. Symbolic and algebraic manipulation
2. Theory of computation

Recommendations

Fairness and Incentive Compatibility via Percentage Fees
EC '23: Proceedings of the 24th ACM Conference on Economics and Computation

We study incentive-compatible mechanisms that maximize the Nash Social Welfare. Since traditional incentive-compatible mechanisms cannot maximize the Nash Social Welfare even approximately, we propose changing the traditional model. Inspired by a ...
Testing Incentive Compatibility in Display Ad Auctions
WWW '18: Proceedings of the 2018 World Wide Web Conference

Consider a buyer participating in a repeated auction, such as those prevalent in display advertising. How would she test whether the auction is incentive compatible? To bid effectively, she is interested in whether the auction is single-shot incentive ...
Budget-Constrained Incentive Compatibility for Stationary Mechanisms
EC '20: Proceedings of the 21st ACM Conference on Economics and Computation

Motivated by online advertising applications, we study incentive properties of stationary mechanisms that satisfy budget constraints in expectation at a stationary equilibrium. We consider a general repeated auction setting where a seller sells ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

SODA '11: Proceedings of the twenty-second annual ACM-SIAM symposium on Discrete algorithms

January 2011

1785 pages

Program Chair:
Dana Randall
Georgia Institute of Technology

Sponsors

SIAM Activity Group on Discrete Mathematics
SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Society for Industrial and Applied Mathematics

United States

Publication History

Published: 23 January 2011

Check for updates

Qualifiers

Research-article

Conference

SODA '11

Sponsor:

SIGACT

SODA '11: 22nd ACM-SIAM Symposium on Discrete Algorithms

January 23 - 25, 2011

California, San Francisco

Acceptance Rates

Overall Acceptance Rate 411 of 1,322 submissions, 31%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

32
Total Citations
View Citations
87
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)0

Reflects downloads up to 09 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Derakhshan MRyu EWeinberg SXue EKleinberg RSaban DBergemann D(2024)Settling the Competition Complexity of Additive Buyers over Independent ItemsProceedings of the 25th ACM Conference on Economics and Computation10.1145/3670865.3673627(420-446)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3670865.3673627
Cai YOikonomou AVelegkas GZhao MMarx D(2021)An efficient ε-BIC to BIC transformation and its application to black-box reduction in revenue maximizationProceedings of the Thirty-Second Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3458064.3458145(1337-1356)Online publication date: 10-Jan-2021
https://dl.acm.org/doi/10.5555/3458064.3458145
Gonczarowski YWeinberg S(2021)The Sample Complexity of Up-to-ε Multi-dimensional Revenue MaximizationJournal of the ACM10.1145/343972268:3(1-28)Online publication date: 22-Mar-2021
https://dl.acm.org/doi/10.1145/3439722
Gergatsouli ELucier BTzamos CDaumé HSingh A(2020)Black-box methods for restoring monotonicityProceedings of the 37th International Conference on Machine Learning10.5555/3524938.3525262(3463-3473)Online publication date: 13-Jul-2020
https://dl.acm.org/doi/10.5555/3524938.3525262
Cai YZhao M(2019)Simple mechanisms for subadditive buyers via dualityACM SIGecom Exchanges10.1145/3331033.333103717:1(39-53)Online publication date: 7-May-2019
https://dl.acm.org/doi/10.1145/3331033.3331037
Gergatsouli ELucier BTzamos CKarlin AImmorlica NJohari R(2019)The Complexity of Black-Box Mechanism Design with PriorsProceedings of the 2019 ACM Conference on Economics and Computation10.1145/3328526.3329648(869-883)Online publication date: 17-Jun-2019
https://dl.acm.org/doi/10.1145/3328526.3329648
Suksompong W(2019)On Black-Box Transformations in Downward-Closed EnvironmentsTheory of Computing Systems10.1007/s00224-018-9898-663:6(1207-1227)Online publication date: 1-Aug-2019
https://dl.acm.org/doi/10.1007/s00224-018-9898-6
Braverman MMao JWeinberg SCzumaj A(2018)On simultaneous two-player combinatorial auctionsProceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms10.5555/3174304.3175451(2256-2273)Online publication date: 7-Jan-2018
https://dl.acm.org/doi/10.5555/3174304.3175451
Rubinstein AWeinberg S(2018)Simple Mechanisms for a Subadditive Buyer and Applications to Revenue MonotonicityACM Transactions on Economics and Computation10.1145/31054486:3-4(1-25)Online publication date: 1-Oct-2018
https://dl.acm.org/doi/10.1145/3105448
Sekar S(2017)Posted pricing sans discriminationProceedings of the 26th International Joint Conference on Artificial Intelligence10.5555/3171642.3171698(388-394)Online publication date: 19-Aug-2017
https://dl.acm.org/doi/10.5555/3171642.3171698
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents