Optimal Multi-Dimensional Mechanisms are not Locally-Implementable

Research output: Chapter in Book/Report/Conference proceedingConference contribution

1 Scopus citations


We introduce locality: a new property of multi-bidder auctions that formally separates the simplicity of optimal single-dimensional multi-bidder auctions from the complexity of optimal multi-dimensional multi-bidder auctions. Specifically, consider the revenue-optimal, Bayesian Incentive Compatible auction for buyers with valuations drawn from D-> :=xi Di, where each distribution has support-size n. This auction takes as input a valuation profile v-> and produces as output an allocation of the items and prices to charge, Opt D-> (v->). When each Di is single-dimensional, this mapping is locally-implementable: defining each input vi requires φ(log n) bits, and Opt D-> (v->) can be fully determined using just φ(log n) bits from each Di. This follows immediately from Myerson's virtual value theory [36]. Our main result establishes that optimal multi-dimensional mechanisms are not locally-implementable: in order to determine the output Opt D-> (v->) on one particular input v->, one still needs to know (essentially) the entire distribution D->. Formally, ω(n) bits from each Di is necessary: (essentially) enough to fully describe Di, and exponentially more than the φ(log n) needed to define the input vi. We show that this phenomenon already occurs with just two bidders, even when one bidder is single-dimensional, and even when the other bidder is barely multi-dimensional. More specifically, the multi-dimensional bidder is "inter-dimensional"from the FedEx setting with just two days [28]. Our techniques are fairly robust: we additionally establish that optimal mechanisms for single-dimensional buyers with budget constraints are not locally-implementable. This again occurs even with just two bidders, even when one has no budget constraint, and even when the other's budget is public.

Original languageEnglish (US)
Title of host publicationEC 2022 - Proceedings of the 23rd ACM Conference on Economics and Computation
PublisherAssociation for Computing Machinery, Inc
Number of pages22
ISBN (Electronic)9781450391504
StatePublished - Jul 12 2022
Event23rd ACM Conference on Economics and Computation, EC 2022 - Boulder, United States
Duration: Jul 11 2022Jul 15 2022

Publication series

NameEC 2022 - Proceedings of the 23rd ACM Conference on Economics and Computation


Conference23rd ACM Conference on Economics and Computation, EC 2022
Country/TerritoryUnited States

All Science Journal Classification (ASJC) codes

  • Computer Science (miscellaneous)
  • Economics and Econometrics
  • Computational Mathematics
  • Statistics and Probability


  • communication complexity
  • lagrangian duality
  • mechanism design
  • revenue maximization


Dive into the research topics of 'Optimal Multi-Dimensional Mechanisms are not Locally-Implementable'. Together they form a unique fingerprint.

Cite this