Optimal Multi-Dimensional Mechanisms are not Locally-Implementable

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.