Consider the problem of implementing a revenue-optimal, Bayesian Incentive Compatible auction when buyers values are drawn from distributions $times_i D_i$ on a particular instance $vec{v}$. Optimal single-dimensional mechanisms are local: in order to allocate the item correctly on a particular valuation profile $vec{v}$, only $tilde{O}(1)$ bits are needed from each player (specifically, their Myerson virtual value [Mye81]), rather than the entire distribution. We show that optimal multi-dimensional mechanisms are not local: in order to allocate the item correctly on a particular valuation profile $vec{v}$, one still needs to know (essentially) the entire distribution. Specifically, if the distributions have support-size $n$, then $Omega(n)$ bits are necessary from each bidder. 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 [FGKK16].
تحميل البحث