On Optimal Multi-Dimensional Mechanism Design
We efficiently solve the optimal multi-dimensional mechanism design problem for independent additive bidders with arbitrary demands when either the number of bidders is held constant or the number of items is held constant. In the first setting, we need that each bidder's values for the items a...
| Main Authors: | , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Association for Computing Machinery (ACM)
2015
|
| Online Access: | http://hdl.handle.net/1721.1/99946 https://orcid.org/0000-0002-5451-0490 |
| _version_ | 1826192304231153664 |
|---|---|
| author | Weinberg, Seth Matthew 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 Weinberg, Seth Matthew Daskalakis, Konstantinos |
| author_sort | Weinberg, Seth Matthew |
| collection | MIT |
| description | We efficiently solve the optimal multi-dimensional mechanism design problem for independent additive bidders with arbitrary demands when either the number of bidders is held constant or the number of items is held constant. In the first setting, we need that each bidder's values for the items are sampled from a possibly correlated, item-symmetric distribution, allowing different distributions for each bidder. In the second setting, we allow the values of each bidder for the items to be arbitrarily correlated, but assume that the distribution of bidder types is bidder-symmetric. These symmetric distributions include i.i.d. distributions, as well as many natural correlated distributions. E.g., an item-symmetric distribution can be obtained by taking an arbitrary distribution, and "forgetting" the names of items; this could arise when different members of a bidder population have various sorts of correlations among the items, but the items are "the same" with respect to a random bidder from the population.
For all ∈>0, we obtain a computationally efficient additive ∈-approximation, when the value distributions are bounded, or a multiplicative (1-∈)-approximation when the value distributions are unbounded, but satisfy the Monotone Hazard Rate condition, covering a widely studied class of distributions in Economics. Our running time is polynomial in max{#items,#bidders}, and not the size of the support of the joint distribution of all bidders' values for all items, which is typically exponential in both the number of items and the number of bidders. Our mechanisms are randomized, explicitly price bundles, and in some cases can also accommodate budget constraints.
Our results are enabled by several new tools and structural properties of Bayesian mechanisms, which we expect to find applications beyond the settings we consider here; indeed, there has already been follow-up research [Cai et al. 2012; Cai and Huang 2012] making use of our tools in both symmetric and non-symmetric settings. In particular, we provide a symmetrization technique that turns any truthful mechanism into one that has the same revenue and respects all symmetries in the underlying value distributions. We also prove that item-symmetric mechanisms satisfy a natural strong-monotonicity property which, unlike cyclic-monotonicity, can be harnessed algorithmically. Finally, we provide a technique that turns any given ∈-BIC mechansism (i.e. one where incentive constraints are violated by ∈) into a truly-BIC mechanism at the cost of O(√∈) revenue. |
| first_indexed | 2024-09-23T09:09:07Z |
| format | Article |
| id | mit-1721.1/99946 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T09:09:07Z |
| publishDate | 2015 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/999462022-09-26T10:47:55Z On Optimal Multi-Dimensional Mechanism Design Symmetries and Optimal Multi-Dimensional Mechanism Design Weinberg, Seth Matthew Daskalakis, Konstantinos Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Daskalakis, Konstantinos Weinberg, Seth Matthew We efficiently solve the optimal multi-dimensional mechanism design problem for independent additive bidders with arbitrary demands when either the number of bidders is held constant or the number of items is held constant. In the first setting, we need that each bidder's values for the items are sampled from a possibly correlated, item-symmetric distribution, allowing different distributions for each bidder. In the second setting, we allow the values of each bidder for the items to be arbitrarily correlated, but assume that the distribution of bidder types is bidder-symmetric. These symmetric distributions include i.i.d. distributions, as well as many natural correlated distributions. E.g., an item-symmetric distribution can be obtained by taking an arbitrary distribution, and "forgetting" the names of items; this could arise when different members of a bidder population have various sorts of correlations among the items, but the items are "the same" with respect to a random bidder from the population. For all ∈>0, we obtain a computationally efficient additive ∈-approximation, when the value distributions are bounded, or a multiplicative (1-∈)-approximation when the value distributions are unbounded, but satisfy the Monotone Hazard Rate condition, covering a widely studied class of distributions in Economics. Our running time is polynomial in max{#items,#bidders}, and not the size of the support of the joint distribution of all bidders' values for all items, which is typically exponential in both the number of items and the number of bidders. Our mechanisms are randomized, explicitly price bundles, and in some cases can also accommodate budget constraints. Our results are enabled by several new tools and structural properties of Bayesian mechanisms, which we expect to find applications beyond the settings we consider here; indeed, there has already been follow-up research [Cai et al. 2012; Cai and Huang 2012] making use of our tools in both symmetric and non-symmetric settings. In particular, we provide a symmetrization technique that turns any truthful mechanism into one that has the same revenue and respects all symmetries in the underlying value distributions. We also prove that item-symmetric mechanisms satisfy a natural strong-monotonicity property which, unlike cyclic-monotonicity, can be harnessed algorithmically. Finally, we provide a technique that turns any given ∈-BIC mechansism (i.e. one where incentive constraints are violated by ∈) into a truly-BIC mechanism at the cost of O(√∈) revenue. Alfred P. Sloan Foundation (Fellowship) National Science Foundation (U.S.) (CAREER Award CCF-0953960) National Science Foundation (U.S.) (Award CCF-1101491) 2015-11-20T14:16:19Z 2015-11-20T14:16:19Z 2012-06 Article http://purl.org/eprint/type/ConferencePaper 9781450314152 http://hdl.handle.net/1721.1/99946 Constantinos Daskalakis and Seth Matthew Weinberg. 2012. Symmetries and optimal multi-dimensional mechanism design. In Proceedings of the 13th ACM Conference on Electronic Commerce (EC '12). ACM, New York, NY, USA, 370-387. https://orcid.org/0000-0002-5451-0490 en_US http://dx.doi.org/10.1145/2229012.2229042 Proceedings of the 13th ACM Conference on Electronic Commerce (EC '12) Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery (ACM) arXiv |
| spellingShingle | Weinberg, Seth Matthew Daskalakis, Konstantinos On Optimal Multi-Dimensional Mechanism Design |
| title | On Optimal Multi-Dimensional Mechanism Design |
| title_full | On Optimal Multi-Dimensional Mechanism Design |
| title_fullStr | On Optimal Multi-Dimensional Mechanism Design |
| title_full_unstemmed | On Optimal Multi-Dimensional Mechanism Design |
| title_short | On Optimal Multi-Dimensional Mechanism Design |
| title_sort | on optimal multi dimensional mechanism design |
| url | http://hdl.handle.net/1721.1/99946 https://orcid.org/0000-0002-5451-0490 |
| work_keys_str_mv | AT weinbergsethmatthew onoptimalmultidimensionalmechanismdesign AT daskalakiskonstantinos onoptimalmultidimensionalmechanismdesign AT weinbergsethmatthew symmetriesandoptimalmultidimensionalmechanismdesign AT daskalakiskonstantinos symmetriesandoptimalmultidimensionalmechanismdesign |