The Complexity of Optimal Mechanism Design
Myerson's seminal work provides a computationally efficient revenue-optimal auction for selling one item to multiple bidders [18]. Generalizing this work to selling multiple items at once has been a central question in economics and algorithmic game theory, but its complexity has remained poorl...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Society for Industrial and Applied Mathematics
2015
|
| Online Access: | http://hdl.handle.net/1721.1/99968 https://orcid.org/0000-0002-7560-5069 https://orcid.org/0000-0002-5451-0490 |
| _version_ | 1826207473254531072 |
|---|---|
| author | Deckelbaum, Alan Tzamos, Christos 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 Deckelbaum, Alan Tzamos, Christos Daskalakis, Konstantinos |
| author_sort | Deckelbaum, Alan |
| collection | MIT |
| description | Myerson's seminal work provides a computationally efficient revenue-optimal auction for selling one item to multiple bidders [18]. Generalizing this work to selling multiple items at once has been a central question in economics and algorithmic game theory, but its complexity has remained poorly understood. We answer this question by showing that a revenue-optimal auction in multi-item settings cannot be found and implemented computationally efficiently, unless zpp ⊇ P[superscript #P]. This is true even for a single additive bidder whose values for the items are independently distributed on two rational numbers with rational probabilities. Our result is very general: we show that it is hard to compute any encoding of an optimal auction of any format (direct or indirect, truthful or non-truthful) that can be implemented in expected polynomial time. In particular, under well-believed complexity-theoretic assumptions, revenue-optimization in very simple multi-item settings can only be tractably approximated.
We note that our hardness result applies to randomized mechanisms in a very simple setting, and is not an artifact of introducing combinatorial structure to the problem by allowing correlation among item values, introducing combinatorial valuations, or requiring the mechanism to be deterministic (whose structure is readily combinatorial). Our proof is enabled by a flow-interpretation of the solutions of an exponential-size linear program for revenue maximization with an additional supermodularity constraint. |
| first_indexed | 2024-09-23T13:50:12Z |
| format | Article |
| id | mit-1721.1/99968 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T13:50:12Z |
| publishDate | 2015 |
| publisher | Society for Industrial and Applied Mathematics |
| record_format | dspace |
| spelling | mit-1721.1/999682022-10-01T17:24:35Z The Complexity of Optimal Mechanism Design Deckelbaum, Alan Tzamos, Christos Daskalakis, Konstantinos Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Department of Mathematics Daskalakis, Konstantinos Deckelbaum, Alan Tzamos, Christos Myerson's seminal work provides a computationally efficient revenue-optimal auction for selling one item to multiple bidders [18]. Generalizing this work to selling multiple items at once has been a central question in economics and algorithmic game theory, but its complexity has remained poorly understood. We answer this question by showing that a revenue-optimal auction in multi-item settings cannot be found and implemented computationally efficiently, unless zpp ⊇ P[superscript #P]. This is true even for a single additive bidder whose values for the items are independently distributed on two rational numbers with rational probabilities. Our result is very general: we show that it is hard to compute any encoding of an optimal auction of any format (direct or indirect, truthful or non-truthful) that can be implemented in expected polynomial time. In particular, under well-believed complexity-theoretic assumptions, revenue-optimization in very simple multi-item settings can only be tractably approximated. We note that our hardness result applies to randomized mechanisms in a very simple setting, and is not an artifact of introducing combinatorial structure to the problem by allowing correlation among item values, introducing combinatorial valuations, or requiring the mechanism to be deterministic (whose structure is readily combinatorial). Our proof is enabled by a flow-interpretation of the solutions of an exponential-size linear program for revenue maximization with an additional supermodularity constraint. Alfred P. Sloan Foundation (Fellowship) Microsoft Research (Faculty 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-20T18:26:59Z 2015-11-20T18:26:59Z 2014 Article http://purl.org/eprint/type/ConferencePaper 978-1-61197-338-9 978-1-61197-340-2 http://hdl.handle.net/1721.1/99968 Daskalakis, Constantinos, Alan Deckelbaum, and Christos Tzamos. “The Complexity of Optimal Mechanism Design.” Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (December 18, 2013): 1302–1318. https://orcid.org/0000-0002-7560-5069 https://orcid.org/0000-0002-5451-0490 en_US http://dx.doi.org/10.1137/1.9781611973402.96 Proceedings of the Twenty-fifth Annual ACM-SIAM Symposium on Discrete Algorithms Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Society for Industrial and Applied Mathematics arXiv |
| spellingShingle | Deckelbaum, Alan Tzamos, Christos Daskalakis, Konstantinos The Complexity of Optimal Mechanism Design |
| title | The Complexity of Optimal Mechanism Design |
| title_full | The Complexity of Optimal Mechanism Design |
| title_fullStr | The Complexity of Optimal Mechanism Design |
| title_full_unstemmed | The Complexity of Optimal Mechanism Design |
| title_short | The Complexity of Optimal Mechanism Design |
| title_sort | complexity of optimal mechanism design |
| url | http://hdl.handle.net/1721.1/99968 https://orcid.org/0000-0002-7560-5069 https://orcid.org/0000-0002-5451-0490 |
| work_keys_str_mv | AT deckelbaumalan thecomplexityofoptimalmechanismdesign AT tzamoschristos thecomplexityofoptimalmechanismdesign AT daskalakiskonstantinos thecomplexityofoptimalmechanismdesign AT deckelbaumalan complexityofoptimalmechanismdesign AT tzamoschristos complexityofoptimalmechanismdesign AT daskalakiskonstantinos complexityofoptimalmechanismdesign |