论文标题
基准设计和事先独立优化
Benchmark Design and Prior-independent Optimization
论文作者
论文摘要
本文比较了在线算法和机制设计模型中的两种领先方法，以实现强大的优化。竞争性分析将在线算法的性能与最差的输入中的脱机基准进行比较，并且与先验无关的机制设计比较了在不知情的分布（输入，即代理值）上的机制的预期性能与最佳分布的最佳机械师的预期性能。对于竞争分析，关键问题是基准的选择。本文提供了一种选择良好基准测试的方法。我们表明，最佳基准测试的最佳算法/机制等于先前独立的最佳算法/机制。 我们解决了与先前独立的机制设计中的一个核心开放问题，即我们确定了以前独立的收入 - 最佳的机制，用于将单个物品出售给具有I.I.D.的两个代理商。和定期分布的值。通过该解决方案以及上述非依赖性机制设计和竞争分析（又称未经事先机制的设计）的等效性，我们表明，基准设计程序通常并不是先前无机制的下限的标准方法。
This paper compares two leading approaches for robust optimization in the models of online algorithms and mechanism design. Competitive analysis compares the performance of an online algorithm to an offline benchmark in worst-case over inputs, and prior-independent mechanism design compares the expected performance of a mechanism on an unknown distribution (of inputs, i.e., agent values) to the optimal mechanism for the distribution in worst case over distributions. For competitive analysis, a critical concern is the choice of benchmark. This paper gives a method for selecting a good benchmark. We show that optimal algorithm/mechanism for the optimal benchmark are equal to the prior-independent optimal algorithm/mechanism. We solve a central open question in prior-independent mechanism design, namely we identify the prior-independent revenue-optimal mechanism for selling a single item to two agents with i.i.d. and regularly distributed values. Via this solution and the above equivalence of prior-independent mechanism design and competitive analysis (a.k.a. prior-free mechanism design) we show that the standard method for lower bounds of prior-free mechanisms is not generally tight for the benchmark design program.
