Sample Complexity for Non-Truthful Mechanisms
Sample Complexity for Non-Truthful Mechanisms
复制标题
非真实机制的复杂性示例
DOI：
10.1145/3328526.3329632
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Sam Taggart
中科院分区：
文献类型：
--
作者：
Jason D. Hartline;Sam Taggart
本文从样本出发，研究了非真实机制的设计问题。我们确定了一个参数化的机制与战略简单的赢家支付出价，所有支付，真实的支付格式。在一般（不一定向下封闭）的单参数可行性环境中，我们证明了家庭具有低的代表性和推广错误。具体来说，多项式许多投标样本足以识别和运行一个机制，是ε-接近贝叶斯纳什均衡收入或福利的最佳真实机制。
This paper considers the design of non-truthful mechanisms from samples. We identify a parameterized family of mechanisms with strategically simple winner-pays-bid, all-pay, and truthful payment formats. In general (not necessarily downward-closed) single-parameter feasibility environments we prove that the family has low representation and generalization error. Specifically, polynomially many bid samples suffice to identify and run a mechanism that is ε-close in Bayes-Nash equilibrium revenue or welfare to that of the optimal truthful mechanism.