论文标题
简单机制中的采样和最佳偏好引起
Sampling and Optimal Preference Elicitation in Simple Mechanisms
论文作者
论文摘要
在这项工作中，我们关注的是有效机制的设计，同时引起了代理商的有限信息。首先，我们研究设施位置游戏中采样近似的性能。我们的关键结果是表明，对于任何$ε> 0 $，大小$ c（ε）=θ（1/ε^2）$的样本预期的是，相对于$ 1 +ε$的近似值，相对于吨位上的普遍中位置机制的最佳社会成本，公制空间$（\ mathbb {\ mathb {r}^d，\ r}^d，\ cdot $ n cdot cdot $ n to \ infty $。此外，我们研究了从拍卖理论到通信复杂性框架的一系列示例环境，从而测量了代理引起的预期数量。我们认为，任何估值都可以用$ k $位表示，我们主要假设$ k $独立于代理商$ n $的数量。在这种情况下，我们表明，Vickrey的规则可以通过平均投标人的预期通信为$ 1 +ε$位，对于任何$ε> 0 $，渐近地与琐碎的下限匹配。作为推论，我们提供了一种令人信服的方法来促进英语拍卖中的价格。我们还使用有效的编码方案利用单个项目格式来证明可以通过同时升级拍卖在附加估值领域中恢复相同的通信绑定，假设项目数量是常数。最后，我们提出了单位需求投标人的上升型多单位拍卖；我们的机制宣布在每个第二轮单独的价格上宣布，并基于采样算法，该算法在沟通有限的情况下执行近似选择，再次导致渐近最佳的沟通。我们的结果不需要关于代理商估值的任何先验知识，并且主要遵循自然采样技术。
In this work we are concerned with the design of efficient mechanisms while eliciting limited information from the agents. First, we study the performance of sampling approximations in facility location games. Our key result is to show that for any $ε> 0$, a sample of size $c(ε) = Θ(1/ε^2)$ yields in expectation a $1 + ε$ approximation with respect to the optimal social cost of the generalized median mechanism on the metric space $(\mathbb{R}^d, \| \cdot \|_1)$, while the number of agents $n \to \infty$. Moreover, we study a series of exemplar environments from auction theory through a communication complexity framework, measuring the expected number of bits elicited from the agents; we posit that any valuation can be expressed with $k$ bits, and we mainly assume that $k$ is independent of the number of agents $n$. In this context, we show that Vickrey's rule can be implemented with an expected communication of $1 + ε$ bits from an average bidder, for any $ε> 0$, asymptotically matching the trivial lower bound. As a corollary, we provide a compelling method to increment the price in an English auction. We also leverage our single-item format with an efficient encoding scheme to prove that the same communication bound can be recovered in the domain of additive valuations through simultaneous ascending auctions, assuming that the number of items is a constant. Finally, we propose an ascending-type multi-unit auction under unit demand bidders; our mechanism announces at every round two separate prices and is based on a sampling algorithm that performs approximate selection with limited communication, leading again to asymptotically optimal communication. Our results do not require any prior knowledge on the agents' valuations, and mainly follow from natural sampling techniques.
