Optimal Pricing Is Hard
We show that computing the revenue-optimal deterministic auction in unit-demand single-buyer Bayesian settings, i.e. the optimal item-pricing, is computationally hard even in single-item settings where the buyer’s value distribution is a sum of independently distributed attributes, or multi-item set...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer-Verlag
2015
|
| Online Access: | http://hdl.handle.net/1721.1/99956 https://orcid.org/0000-0002-7560-5069 https://orcid.org/0000-0002-5451-0490 |
| _version_ | 1826214281050324992 |
|---|---|
| author | Deckelbaum, Alan Tzamos, Christos Daskalakis, Konstantinos |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Deckelbaum, Alan Tzamos, Christos Daskalakis, Konstantinos |
| author_sort | Deckelbaum, Alan |
| collection | MIT |
| description | We show that computing the revenue-optimal deterministic auction in unit-demand single-buyer Bayesian settings, i.e. the optimal item-pricing, is computationally hard even in single-item settings where the buyer’s value distribution is a sum of independently distributed attributes, or multi-item settings where the buyer’s values for the items are independent. We also show that it is intractable to optimally price the grand bundle of multiple items for an additive bidder whose values for the items are independent. These difficulties stem from implicit definitions of a value distribution. We provide three instances of how different properties of implicit distributions can lead to intractability: the first is a #P-hardness proof, while the remaining two are reductions from the SQRT-SUM problem of Garey, Graham, and Johnson [14]. While simple pricing schemes can oftentimes approximate the best scheme in revenue, they can have drastically different underlying structure. We argue therefore that either the specification of the input distribution must be highly restricted in format, or it is necessary for the goal to be mere approximation to the optimal scheme’s revenue instead of computing properties of the scheme itself. |
| first_indexed | 2024-09-23T10:40:46Z |
| format | Article |
| id | mit-1721.1/99956 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:40:46Z |
| publishDate | 2015 |
| publisher | Springer-Verlag |
| record_format | dspace |
| spelling | mit-1721.1/999562022-09-30T22:12:05Z Optimal Pricing Is Hard Deckelbaum, Alan Tzamos, Christos Daskalakis, Konstantinos Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Department of Mathematics Daskalakis, Konstantinos Deckelbaum, Alan Tzamos, Christos We show that computing the revenue-optimal deterministic auction in unit-demand single-buyer Bayesian settings, i.e. the optimal item-pricing, is computationally hard even in single-item settings where the buyer’s value distribution is a sum of independently distributed attributes, or multi-item settings where the buyer’s values for the items are independent. We also show that it is intractable to optimally price the grand bundle of multiple items for an additive bidder whose values for the items are independent. These difficulties stem from implicit definitions of a value distribution. We provide three instances of how different properties of implicit distributions can lead to intractability: the first is a #P-hardness proof, while the remaining two are reductions from the SQRT-SUM problem of Garey, Graham, and Johnson [14]. While simple pricing schemes can oftentimes approximate the best scheme in revenue, they can have drastically different underlying structure. We argue therefore that either the specification of the input distribution must be highly restricted in format, or it is necessary for the goal to be mere approximation to the optimal scheme’s revenue instead of computing properties of the scheme itself. Microsoft Research (Fellowship) Alfred P. Sloan Foundation (Fellowship) National Science Foundation (U.S.) (CAREER Award CCF-0953960) National Science Foundation (U.S.) (Award CCF-1101491) Hertz Foundation (Daniel Stroock Fellowship) 2015-11-20T16:47:07Z 2015-11-20T16:47:07Z 2012 Article http://purl.org/eprint/type/ConferencePaper 978-3-642-35310-9 978-3-642-35311-6 0302-9743 1611-3349 http://hdl.handle.net/1721.1/99956 Daskalakis, Constantinos, Alan Deckelbaum, and Christos Tzamos. “Optimal Pricing Is Hard.” Internet and Network Economics (2012): 298–308. https://orcid.org/0000-0002-7560-5069 https://orcid.org/0000-0002-5451-0490 en_US http://dx.doi.org/10.1007/978-3-642-35311-6_22 Internet and Network Economics Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Springer-Verlag arXiv |
| spellingShingle | Deckelbaum, Alan Tzamos, Christos Daskalakis, Konstantinos Optimal Pricing Is Hard |
| title | Optimal Pricing Is Hard |
| title_full | Optimal Pricing Is Hard |
| title_fullStr | Optimal Pricing Is Hard |
| title_full_unstemmed | Optimal Pricing Is Hard |
| title_short | Optimal Pricing Is Hard |
| title_sort | optimal pricing is hard |
| url | http://hdl.handle.net/1721.1/99956 https://orcid.org/0000-0002-7560-5069 https://orcid.org/0000-0002-5451-0490 |
| work_keys_str_mv | AT deckelbaumalan optimalpricingishard AT tzamoschristos optimalpricingishard AT daskalakiskonstantinos optimalpricingishard |