research-article

Multi-dimensional mechanism design with limited information

Authors:

Dirk Bergemann,

Edmund YehAuthors Info & Claims

EC '12: Proceedings of the 13th ACM Conference on Electronic Commerce

Pages 162 - 178

https://doi.org/10.1145/2229012.2229028

Published: 04 June 2012 Publication History

Abstract

We analyze a nonlinear pricing model with limited information. Each buyer can purchase a large variety, d, of goods. His preference for each good is represented by a scalar and his preference over d goods is represented by a d-dimensional vector. The type space of each buyer is given by a compact subset of R^d+ with a continuum of possible types. By contrast, the seller is limited to offer a finite number M of d-dimensional choices.

We provide necessary conditions that the optimal finite menu of the social welfare maximizing problem has to satisfy. We establish an underlying connection to the theory of quantization and provide an estimate of the welfare loss resulting from the usage of the d-dimensional M-class menu. We show that the welfare loss converges to zero at a rate proportional to d/M^2/d.

We show that in higher dimensions, a significant reduction in the welfare loss arises from an optimal partition of the d-dimensional type space that takes advantage of the correlation among the d parameters.

References

[1]

ARMSTRONG, M. 1996. Multiproduct nonlinear pricing. Econometrica 64, 51--75.

[2]

ARMSTRONG, M. 1999. Price discrimination by a many-product firm. Review of Economic Studies.

[3]

BERGEMANN, D. AND PESENDORFER, M. 2007. Information structures in optimal auctions. Journal of Economic Theory 137, 580--609.

[4]

BERGEMANN, D., SHEN, J., XU, Y., AND YEH, E. 2012. Mechanism design with limited information: The case of nonlinear pricing. Game Theory for Networks: Lecture Notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering 0075.

[5]

BLUMROSEN, L. AND FELDMAN, M. 2006. Implementation with a bounded action space. In The 7th ACM Conference on Electronic Commerce.

Digital Library

[6]

BLUMROSEN, L., NISAN, N., AND SEGAL, I. 2007. Auctions with severely bounded communicatione. Journal of Artificial Intelligence Research 28, 233--266.

Digital Library

[7]

CONWAY, J. H. AND SLOANE, N. J. A. 1985. A lower bound on the average error of vector quantizers. IEEE Transactions on Information Theory 31, 1, 106--109.

Digital Library

[8]

GERSHO, A. 1979. Asymptotically optimal block quantization. IEEE Transactions on Information Theory 25, 4, 373--380.

Digital Library

[9]

GERSHO, A. AND GRAY, R. M. 1992. Vector Quantization and Signal Compression. Kluwer Academic Publishers, Norwell, Massachusetts.

Digital Library

[10]

HOPPE, H., MOLDOVANU, B., AND OZDENOREN, E. 2010. Coarse matching with incomplete information. Economic Theory.

[11]

KOS, N. 2011. Communication and efficiency in auction. Game and Economic Behavior.

[12]

LEDYARD, J. O. AND PALFREY, T. R. 2002. The approximation of efficient public good mechanisms by simple voting schemes. Journal of Public Economics 83, 939--979.

[13]

LOOKABAUGH, T. D. AND GRAY, R. M. 1989. High-resolution quantization theory and the vector quantizer advantage. IEEE Transactions on Information Theory 35, 5, 1020--1033.

Digital Library

[14]

MASKIN, E. AND RILEY, J. 1984. Monopoly with incomplete information. Rand Journal of Economics 15, 171--196.

[15]

MCAFEE, P. 2002. Coarse matching. Econometrica 70, 2025--2034.

[16]

MUSSA, M. AND ROSEN, S. 1978. Monopoly and product quality. Journal of Economic Theory 18, 301--317.

[17]

ROCHET, J. C. AND CHONE, P. 1998. Ironing, sweeping and multidimensional screening. Econometrica 66, 783--826.

[18]

ROCHET, J. C. AND STOLE, L. 2003. The economics of multidimensional screening. in Advances in Economic and Econometrics (edited by M. Dewatripont and L. P. Hansen and S. J. Turnovsky), 115--150.

[19]

ROTHKOPF, M. H. AND HARSTAD, R. M. 1994. On the role of discrete bid levels in oral auctions. European Journal of Operational Research 74, 572--581.

[20]

ROYDEN, H. L. 1968. Real Analysis. Collier Macmillan, New York.

[21]

WILSON, R. 1989. Efficient and competitive rationing. Econometrica 57, 1--40.

[22]

WILSON, R. 1993. Nonlinear Pricing. Oxford University Press, Oxford.

[23]

ZADOR, P. 1982. Asymptotic quantization error of continuous signals and the quantization dimension. IEEE Transactions on Information Theory 28, 134--149.

Digital Library

Cited By

Bertomeu JHu PLiu Y(2023)Disclosure and Investor Inattention: Theory and EvidenceThe Accounting Review10.2308/TAR-2022-012298:6(1-36)Online publication date: 27-Sep-2023
https://doi.org/10.2308/TAR-2022-0122
Smolin A(2023)Disclosure and pricing of attributesThe RAND Journal of Economics10.1111/1756-2171.1245154:4(570-597)Online publication date: 18-Oct-2023
https://doi.org/10.1111/1756-2171.12451
Eilat REliaz KMu X(2021)Bayesian privacyTheoretical Economics10.3982/TE439016:4(1557-1603)Online publication date: 2021
https://doi.org/10.3982/TE4390
Show More Cited By

Index Terms

Multi-dimensional mechanism design with limited information
1. Theory of computation
  1. Design and analysis of algorithms

Recommendations

Optimal Multi-dimensional Mechanism Design: Reducing Revenue to Welfare Maximization
FOCS '12: Proceedings of the 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science

We provide a reduction from revenue maximization to welfare maximization in multi-dimensional Bayesian auctions with arbitrary (possibly combinatorial) feasibility constraints and independent bidders with arbitrary (possibly combinatorial) demand ...
Mechanism design for fair division: allocating divisible items without payments
EC '13: Proceedings of the fourteenth ACM conference on Electronic commerce

We revisit the classic problem of fair division from a mechanism design perspective and provide an elegant truthful mechanism that yields surprisingly good approximation guarantees for the widely used solution of Proportional Fairness. This solution, ...
Multidimensional screening: online computation and limited information
ICEC '08: Proceedings of the 10th international conference on Electronic commerce

Optimal screening has been studied in economics, game theory, and recently computer science. We study the problem in a nonlinear pricing application, where a monopoly designs a price schedule from which the buyers self-select the quality they wish to ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

EC '12: Proceedings of the 13th ACM Conference on Electronic Commerce

June 2012

1016 pages

ISBN:9781450314152

DOI:10.1145/2229012

General Chair:
Boi Faltings
École Polytechnique Fédérale de Lausanne (EPFL)
,
Program Chairs:
Kevin Leyton-Brown
University of British Columbia
,
Panos Ipeirotis
New York University

Copyright © 2012 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

SIGecom: Special Interest Group on Economics and Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 04 June 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

EC '12

Sponsor:

SIGecom

EC '12: ACM Conference on Electronic Commerce

June 4 - 8, 2012

Valencia, Spain

Acceptance Rates

Overall Acceptance Rate 664 of 2,389 submissions, 28%

Upcoming Conference

EC '25

Sponsor:
sigecom

The 25th ACM Conference on Economics and Computation

July 7 - 11, 2025

Stanford , CA , USA

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
169
Total Downloads

Downloads (Last 12 months)19
Downloads (Last 6 weeks)5

Reflects downloads up to 23 Feb 2025

Other Metrics

View Author Metrics

Citations

Cited By

Bertomeu JHu PLiu Y(2023)Disclosure and Investor Inattention: Theory and EvidenceThe Accounting Review10.2308/TAR-2022-012298:6(1-36)Online publication date: 27-Sep-2023
https://doi.org/10.2308/TAR-2022-0122
Smolin A(2023)Disclosure and pricing of attributesThe RAND Journal of Economics10.1111/1756-2171.1245154:4(570-597)Online publication date: 18-Oct-2023
https://doi.org/10.1111/1756-2171.12451
Eilat REliaz KMu X(2021)Bayesian privacyTheoretical Economics10.3982/TE439016:4(1557-1603)Online publication date: 2021
https://doi.org/10.3982/TE4390
Zhang YGu YPan MTran NDawy ZHan Z(2018)Multi-Dimensional Incentive Mechanism in Mobile Crowdsourcing with Moral HazardIEEE Transactions on Mobile Computing10.1109/TMC.2017.273298217:3(604-616)Online publication date: 1-Mar-2018
https://doi.org/10.1109/TMC.2017.2732982
Stein SGerding ENedea ARosenfeld AJennings N(2017)Evaluating market user interfaces for electric vehicle charging using Bid2ChargeProceedings of the 26th International Joint Conference on Artificial Intelligence10.5555/3171837.3171989(4939-4943)Online publication date: 19-Aug-2017
https://dl.acm.org/doi/10.5555/3171837.3171989
Stein SGerding ENedea ARosenfeld AJennings NJonker CMarsella SThangarajah JTuyls K(2016)Bid2ChargeProceedings of the 2016 International Conference on Autonomous Agents & Multiagent Systems10.5555/2936924.2937053(882-890)Online publication date: 9-May-2016
https://dl.acm.org/doi/10.5555/2936924.2937053
Bertomeu JHu KLiu Y(undefined)Disclosure and Investor InattentionSSRN Electronic Journal10.2139/ssrn.3673225
https://doi.org/10.2139/ssrn.3673225
Smolin A(undefined)Disclosure and Pricing of AttributesSSRN Electronic Journal10.2139/ssrn.3318957
https://doi.org/10.2139/ssrn.3318957
Smolin A(undefined)Disclosure and Pricing of AttributesSSRN Electronic Journal10.2139/ssrn.3047028
https://doi.org/10.2139/ssrn.3047028
Bergemann DShen JXu YYeh E(undefined)Nonlinear Pricing with Finite InformationSSRN Electronic Journal10.2139/ssrn.2553980
https://doi.org/10.2139/ssrn.2553980

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.

Figures

Tables

Media

View Table of Conten