Extreme-Value Theorems for Optimal Multidimensional Pricing
Original manuscript: June 2, 2011
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2014
|
| Online Access: | http://hdl.handle.net/1721.1/86100 https://orcid.org/0000-0002-5451-0490 |
| _version_ | 1826217032248459264 |
|---|---|
| author | Cai, Yang Daskalakis, Konstantinos |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Cai, Yang Daskalakis, Konstantinos |
| author_sort | Cai, Yang |
| collection | MIT |
| description | Original manuscript: June 2, 2011 |
| first_indexed | 2024-09-23T16:56:58Z |
| format | Article |
| id | mit-1721.1/86100 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T16:56:58Z |
| publishDate | 2014 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/861002022-10-03T09:20:03Z Extreme-Value Theorems for Optimal Multidimensional Pricing Cai, Yang Daskalakis, Konstantinos Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Cai, Yang Daskalakis, Konstantinos Original manuscript: June 2, 2011 We provide a Polynomial Time Approximation Scheme for the multi-dimensional unit-demand pricing problem, when the buyer's values are independent (but not necessarily identically distributed.) For all ϵ >; 0, we obtain a (1 + ϵ)-factor approximation to the optimal revenue in time polynomial, when the values are sampled from Monotone Hazard Rate (MHR) distributions, quasi-polynomial, when sampled from regular distributions, and polynomial in n[superscript poly(log r)] when sampled from general distributions supported on a set [u[subscript min],ru[subscript min]]. We also provide an additive PTAS for all bounded distributions. Our algorithms are based on novel extreme value theorems for MHR and regular distributions, and apply probabilistic techniques to understand the statistical properties of revenue distributions, as well as to reduce the size of the search space of the algorithm. As a byproduct of our techniques, we establish structural properties of optimal solutions. We show that, for all ϵ >; 0, g(1/ϵ) distinct prices suffice to obtain a (1 + ϵ)-factor approximation to the optimal revenue for MHR distributions, where g(1/ϵ) is a quasi-linear function of 1/ϵ that does not depend on the number of items. Similarly, for all ϵ >; 0 and n >; 0, g(1/ϵ · log n) distinct prices suffice for regular distributions, where n is the number of items and g(·) is a polynomial function. Finally, in the i.i.d. MHR case, we show that, as long as the number of items is a sufficiently large function of 1/ϵ, a single price suffices to achieve a (1 + ϵ)-factor approximation. Our results represent significant progress to the single-bidder case of the multidimensional optimal mechanism design problem, following Myerson's celebrated work on optimal mechanism design [Myerson 1981]. National Science Foundation (U.S.) (Award CCF-0953960) National Science Foundation (U.S.) (Award CCF-1101491) Alfred P. Sloan Foundation (Fellowship) 2014-04-11T14:27:48Z 2014-04-11T14:27:48Z 2011-10 Article http://purl.org/eprint/type/ConferencePaper 978-0-7695-4571-4 978-1-4577-1843-4 http://hdl.handle.net/1721.1/86100 Cai, Yang, and Constantinos Daskalakis. “Extreme-Value Theorems for Optimal Multidimensional Pricing.” 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science (n.d.). https://orcid.org/0000-0002-5451-0490 en_US http://dx.doi.org/10.1109/focs.2011.76 Proceedings of the 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) arXiv |
| spellingShingle | Cai, Yang Daskalakis, Konstantinos Extreme-Value Theorems for Optimal Multidimensional Pricing |
| title | Extreme-Value Theorems for Optimal Multidimensional Pricing |
| title_full | Extreme-Value Theorems for Optimal Multidimensional Pricing |
| title_fullStr | Extreme-Value Theorems for Optimal Multidimensional Pricing |
| title_full_unstemmed | Extreme-Value Theorems for Optimal Multidimensional Pricing |
| title_short | Extreme-Value Theorems for Optimal Multidimensional Pricing |
| title_sort | extreme value theorems for optimal multidimensional pricing |
| url | http://hdl.handle.net/1721.1/86100 https://orcid.org/0000-0002-5451-0490 |
| work_keys_str_mv | AT caiyang extremevaluetheoremsforoptimalmultidimensionalpricing AT daskalakiskonstantinos extremevaluetheoremsforoptimalmultidimensionalpricing |