论文标题
最佳的多维机制不是局部可测量的
Optimal Multi-Dimensional Mechanisms are not Locally-Implementable
论文作者
论文摘要
我们介绍了局部性：多价拍卖的新属性，将最佳的单维多价拍卖的简单性与最佳多维多二维多竞争拍卖的复杂性相距甚远。具体来说，考虑收入最佳的，贝叶斯激励拍卖的兼容拍卖，这些拍卖是从$ \ vec {d}中获得的估值的买家：= \ times_i d_i $，每个分发都有支撑大小的$ n $。该拍卖将作为输入作为估值配置文件$ \ vec {v} $，并作为输出分配的项目和价格分配，$ opt _ {\ vec {d}}}（\ vec {v}）$。当每个$ d_i $都是单维的时，此映射是可以局部实现的：定义每个输入$ v_i $需要$θ（\ log n）$ bits，而$ opt _ {\ vec {d}}}（\ vec {vec {v}）$可以完全使用每个$ n）$ bits $ d_ bits $ n）$ d_这立即取决于迈尔森的虚拟价值理论[mye81]。 我们的主要结果表明，最佳的多维机制是不可局部的：为了确定输出$ opt $ opt _ {\ vec {d}}（\ \ vec {v}）$在一个特定的输入$ \ \ vec {v} $上，仍然需要知道（本质上）整个分布$ \ vec {d}。正式地，必须从每种$ d_i $中的$ω（n）$ lits ：（本质上）足以完全描述$ d_i $，并且呈指数超过定义输入$ v_i $所需的$θ（\ log n）$。我们表明，即使一个竞标者是单维的，而且另一个投标人几乎没有多维时，这种现象已经发生了，即使一个竞标者是单维的。更具体地说，多维出价者是FedEx设置的``Intermensional''，仅需两天[FGKK16]。 我们的技术相当强大：我们还确定，具有预算限制的单维买家的最佳机制并非本地实现。即使一个人没有预算限制，即使对方的预算是公开的，也只会发生两个投标人。
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 $\vec{D}:=\times_i D_i$, where each distribution has support-size $n$. This auction takes as input a valuation profile $\vec{v}$ and produces as output an allocation of the items and prices to charge, $Opt_{\vec{D}}(\vec{v})$. When each $D_i$ is single-dimensional, this mapping is locally-implementable: defining each input $v_i$ requires $Θ(\log n)$ bits, and $Opt_{\vec{D}}(\vec{v})$ can be fully determined using just $Θ(\log n)$ bits from each $D_i$. This follows immediately from Myerson's virtual value theory [Mye81]. Our main result establishes that optimal multi-dimensional mechanisms are not locally-implementable: in order to determine the output $Opt_{\vec{D}}(\vec{v})$ on one particular input $\vec{v}$, one still needs to know (essentially) the entire distribution $\vec{D}$. Formally, $Ω(n)$ bits from each $D_i$ is necessary: (essentially) enough to fully describe $D_i$, and exponentially more than the $Θ(\log n)$ needed to define the input $v_i$. We show that this phenomenon already occurs with just two bidders, even when one bidder is single-dimensional, and 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]. Our techniques are fairly robust: we additionally establish that optimal mechanisms for single-dimensional buyers with budget constraints are not locally-implementable. This occurs with just two bidders, even when one has no budget constraint, and even when the other's budget is public.
