论文标题
超越最差预算的机制设计
Beyond Worst-Case Budget-Feasible Mechanism Design
论文作者
论文摘要
在众包等大型市场应用程序中，我们在“小型竞标假设”下重新审视了预算可行的机制设计问题。 Anari，Goel和Nikzad（2018）提供了一种最佳竞争比率$ 1-1/e $ $ $ $ $的机制。但是，我们观察到，在许多现实情况下，Ensthaler and Giebe（2014）的更简单的开放时钟拍卖显着优于其机制，尽管在最坏情况下，开放时钟拍卖只能达到竞争性比率$ 1/2 $。是否有一种机制可以使两全其美的机制，即一种最佳案例最佳且在现实实例上表现出色的机制？ 我们的第一个主要结果是对自然机制的设计和分析，该机制对上述问题给出了肯定的答案：（i）我们证明，在每种情况下，我们的机制的性能至少与包括Anari，Goel，Nikzad和Nikzad和Ensthaler和Giebe机制在内的所有统一机制一样好。 （ii）此外，我们对各种现实实例进行了经验评估我们的机制，并观察到它以很大的利润率超过了最差的$ 1-1/e竞争比率，并与上述两种机制进行了比较。 我们的第二个主要结果在理论上更有趣：我们表明，在预算平滑分析的半反向模型中，对手设计了一个最差的预算市场，用于预算的分配，我们的机制在所有（包括非统一）机制中都是最佳的。此外，我们的机制可确保严格的比（1-1/e）$（1-1/e）$预期的竞争比率，无论市场如何。我们通过对任何给定的预算分配的最坏情况市场的表征来补充积极的结果，并证明了相当坚固的硬度结果，可以抵抗任何预算分配和任何机制。
Motivated by large-market applications such as crowdsourcing, we revisit the problem of budget-feasible mechanism design under a "small-bidder assumption". Anari, Goel, and Nikzad (2018) gave a mechanism that has optimal competitive ratio $1-1/e$ on worst-case instances. However, we observe that on many realistic instances, their mechanism is significantly outperformed by a simpler open clock auction by Ensthaler and Giebe (2014), although the open clock auction only achieves competitive ratio $1/2$ in the worst case. Is there a mechanism that gets the best of both worlds, i.e., a mechanism that is worst-case optimal and performs favorably on realistic instances? Our first main result is the design and the analysis of a natural mechanism that gives an affirmative answer to our question above: (i) We prove that on every instance, our mechanism performs at least as good as all uniform mechanisms, including Anari, Goel, and Nikzad's and Ensthaler and Giebe's mechanisms. (ii) Moreover, we empirically evaluate our mechanism on various realistic instances and observe that it beats the worst-case $1-1/e$ competitive ratio by a large margin and compares favorably to both mechanisms mentioned above. Our second main result is more interesting in theory: We show that in the semi-adversarial model of budget-smoothed analysis, where the adversary designs a single worst-case market for a distribution of budgets, our mechanism is optimal among all (including non-uniform) mechanisms; furthermore our mechanism guarantees a strictly better-than-$(1-1/e)$ expected competitive ratio for any non-trivial budget distribution regardless of the market. We complement the positive result with a characterization of the worst-case markets for any given budget distribution and prove a fairly robust hardness result that holds against any budget distribution and any mechanism.
